模式語言與模式模板在運行時驗證中的應(yīng)用.pdf

1、運行時驗證作為一種輕量級的形式化驗證方法，已被應(yīng)用到許多領(lǐng)域，如 Java程序的運行時異常驗證、硬件運行時行為驗證、列車控制系統(tǒng)驗證等。運行時驗證中采用形式化規(guī)約描述性質(zhì)，形式化規(guī)約最主要的優(yōu)點在于可以準確描述被監(jiān)控對象的一類錯誤。盡管優(yōu)勢明顯，但現(xiàn)有形式化規(guī)約仍存在兩點不足：其一，通常采用常量來描述事件，限制了規(guī)約的描述范圍；其二，構(gòu)造形式化規(guī)約需要具有較強的專業(yè)知識，影響了運行時驗證的推廣使用。因此，研究新的形式化規(guī)約，并提出相應(yīng)的

2、運行時驗證算法，具有重要的理論意義與應(yīng)用價值。
　　本文針對利用模式語言和模式模板，解決運行時驗證問題進行了研究，取得的創(chuàng)新研究成果如下：
　　1.針對規(guī)約描述能力方面的不足，本文提出了模式以及模式語言的形式化定義，通過形式化定義將模式語言理論引入到運行時驗證領(lǐng)域中，并在此基礎(chǔ)上給出了模式語言在解決運行時驗證匹配問題中的應(yīng)用舉例。
　　2.針對推廣使用形式化規(guī)約過程中存在的困難，本文提出了用于簡化形式化規(guī)約構(gòu)造的模式模

3、板以及模板庫。首先，針對離線監(jiān)控下運行時驗證問題，本文提出并實現(xiàn)了Brute Force擴展算法，Boyer-Moore擴展算法和Sunday擴展算法。針對在線監(jiān)控下運行時驗證問題，提出并實現(xiàn)了模式模板匹配問題的算法，上述算法在工程應(yīng)用中達到了簡化形式化規(guī)約構(gòu)造過程的目的。然后，通過模擬運行時驗證的實驗，得出相比較其他算法Sunday擴展算法，帶有HashMap結(jié)構(gòu)的模式模板以及指定關(guān)系模式模板在匹配時效率更高。此外，為了增強模式模板的

4、表達能力，提出了可接受狀態(tài)自動機以及模式推導(dǎo)算法。
　　3.在運行時驗證工具Monitor Verification Control中，設(shè)計并實現(xiàn)了支持模式語言和模式模板的驗證功能，進一步從工程上驗證了本文所提出的模式語言相關(guān)概念以及算法的有效性。
　　綜上所述，使用模式語言可以增強規(guī)約的描述能力，通過調(diào)用模式庫中的模式模板，可以快速將自然語言規(guī)約表示為相應(yīng)的形式化規(guī)約，從而簡化自然語言規(guī)約向形式化語言規(guī)約轉(zhuǎn)化的過程，降低開