[發(fā)明專利]一種實時系統(tǒng)的循環(huán)邊界內(nèi)向分析方法

有效

• 申請?zhí)枺?/td>: 201410520726.8
• 申請日: 2014-09-30
• 公開（公告）號: CN104317572B
• 公開（公告）日: 2017-05-24
• 發(fā)明（設(shè)計）人: 湯恩義;鮑鐵勻;李宣東;王林章;陳鑫;潘敏學(xué)
• 申請（專利權(quán)）人: 南京大學(xué)
• 主分類號: G06F9/44
• 分類號: G06F9/44
• 代理公司: 南京瑞弘專利商標(biāo)事務(wù)所(普通合伙)32249
• 代理人: 楊曉玲

1.一種實時系統(tǒng)的循環(huán)邊界內(nèi)向分析方法，其特征在于該方法結(jié)合靜態(tài)分析技術(shù)和動態(tài)符號執(zhí)行方法，且在符號執(zhí)行過程中改變搜索方式而使得執(zhí)行引擎能夠快速定位到各循環(huán)的最大迭代路徑，并以此為基礎(chǔ)高效地獲得循環(huán)邊界的估計值，本方法包含的具體步驟為：

1-1)、使用靜態(tài)分析方法定位系統(tǒng)中的循環(huán)塊，并將所定位到的循環(huán)塊信息緩存，以便后續(xù)的符號執(zhí)行進行進一步處理，在實現(xiàn)循環(huán)定位的過程中，緩存各循環(huán)塊的起始位置點、入口數(shù)、出口數(shù)、各入口和出口的位置點、循環(huán)條件的基本信息，以便后續(xù)步驟使用；

1-2)、將當(dāng)前待分析的實時系統(tǒng)編譯到符號執(zhí)行平臺，以獲得待分析系統(tǒng)在符號執(zhí)行平臺上的字節(jié)碼，直接使用已有的符號化平臺的配套編譯工具，所生成的執(zhí)行碼將用于步驟1-3)的符號執(zhí)行；

1-3)、在針對循環(huán)分析定制的目標(biāo)制導(dǎo)引擎上，對步驟1-2)所生成的字節(jié)碼完成符號執(zhí)行，并在執(zhí)行過程中比對由步驟1-1)所保存的循環(huán)塊信息，針對特定路徑進行符號推導(dǎo)，從而迅速獲得各循環(huán)塊邊界的內(nèi)向分析結(jié)果。

2.根據(jù)權(quán)利要求1所述的一種實時系統(tǒng)的循環(huán)邊界內(nèi)向分析方法，其特征在于所述步驟1-3)中的符號執(zhí)行方法針對循環(huán)邊界分析的要求改變了搜索方式，從而使得執(zhí)行引擎能夠快速定位到系統(tǒng)中各循環(huán)的最大迭代路徑；該方法具有兩個執(zhí)行模式——模式a和模式b，模式a的主要作用在于建立狀態(tài)池，以獲得系統(tǒng)中各循環(huán)的入口符號狀態(tài)，而模式b的作用在于為已經(jīng)具備條件的循環(huán)塊計算內(nèi)向邊界；具體如下：

2-1)將引擎的初始模式置為模式a，構(gòu)建系統(tǒng)的初始符號狀態(tài)；在初始的符號狀態(tài)中，系統(tǒng)輸入由具體變量值改成了可以代表任意值的“符號”；

2-2)以模式a對系統(tǒng)執(zhí)行碼進行符號執(zhí)行，并在執(zhí)行過程中比對步驟1-1)緩存的循環(huán)塊信息，當(dāng)發(fā)現(xiàn)當(dāng)前的符號狀態(tài)到達循環(huán)入口時，將該狀態(tài)加入循環(huán)內(nèi)部狀態(tài)集S留待模式b處理，而選擇另一個符號狀態(tài)執(zhí)行；如果沒有其它符號狀態(tài)，則切換到模式b進行循環(huán)塊邊界分析；

2-3)切換到模式b以后，引擎會從循環(huán)內(nèi)部狀態(tài)集S中任取一個狀態(tài)開始，具體分析每一個循環(huán)塊的內(nèi)向邊界；這一模式的符號執(zhí)行被約束在程序的各個循環(huán)塊內(nèi)，通過一系列符號制導(dǎo)求解過程，最終獲得各個循環(huán)塊的內(nèi)向邊界以及各循環(huán)塊的出口狀態(tài)；

2-4)當(dāng)步驟2-3)完成時，引擎會得到一個完整循環(huán)塊的內(nèi)向邊界值，以及該循環(huán)塊的出口符號狀態(tài)，這時引擎將切換回到模式a，以循環(huán)塊出口狀態(tài)開始繼續(xù)尋找新的循環(huán)塊，直到當(dāng)前系統(tǒng)的所有符號狀態(tài)都運行完成，即步驟2-2)中循環(huán)內(nèi)部狀態(tài)集S為空集，則求解各記錄的符號狀態(tài)約束，獲得能覆蓋對應(yīng)路徑輸入值的最終結(jié)果。

3.根據(jù)權(quán)利要求2所述的一種實時系統(tǒng)的循環(huán)邊界內(nèi)向分析方法，其特征在于步驟2-3)切換到具體模式b以后，引擎將切換到一個循環(huán)塊內(nèi)的符號狀態(tài)上執(zhí)行；在該模式下，每一個符號狀態(tài)將會維護一個信息棧I，用以存放多層嵌套循環(huán)的信息；當(dāng)遇到嵌套循環(huán)時，外層循環(huán)的信息被壓棧到I，并開始分析內(nèi)層循環(huán)的信息；當(dāng)內(nèi)層循環(huán)分析完成后，外層循環(huán)的信息會從I出棧，從而可以繼續(xù)進行外層循環(huán)的分析；在執(zhí)行步驟2-3)時，平臺會為當(dāng)前所分析的循環(huán)塊分配兩個符號狀態(tài)集——S和S’：狀態(tài)集S用于緩存當(dāng)前在循環(huán)內(nèi)部等待執(zhí)行的符號狀態(tài)，而狀態(tài)集S’用于緩存已經(jīng)執(zhí)行到當(dāng)前循環(huán)出口的符號狀態(tài)；在剛切換到模式b時，由于僅有一個符號狀態(tài)在當(dāng)前循環(huán)塊內(nèi)執(zhí)行，故而S中僅有該符號狀態(tài)，而S’初始時為空集；符號執(zhí)行平臺每次從S中取出一個符號狀態(tài)并往前執(zhí)行一步，并處理以下四種不同的具體情形：

當(dāng)遇到分支時，會產(chǎn)生新的狀態(tài)，新狀態(tài)與當(dāng)前狀態(tài)會擁有同樣的信息棧I，并且會被加入到狀態(tài)集S中；

當(dāng)進入內(nèi)層的嵌套循環(huán)時，S與S’會被壓入信息棧I中，平臺為當(dāng)前內(nèi)層循環(huán)重建新的S與S’，S的初值為當(dāng)前狀態(tài)，S’的初值為空集；

當(dāng)?shù)竭_程序中的break語句所標(biāo)識的循環(huán)額外出口分支時，平臺會求解當(dāng)前符號狀態(tài)內(nèi)的符號信息，并將解得繼續(xù)在循環(huán)內(nèi)執(zhí)行分支上的符號狀態(tài)與沿循環(huán)出口運行的符號狀態(tài)，將其分別加入S與S’，并進行循環(huán)出口處理，統(tǒng)計循環(huán)的內(nèi)向邊界值，并判斷集合S是否為空集與信息棧I是否已到達棧底，如仍未到達棧底則表示當(dāng)前循環(huán)為嵌套循環(huán)的內(nèi)層循環(huán)，將執(zhí)行信息棧I的出棧操作以便繼續(xù)進行嵌套循環(huán)的外層循環(huán)分析；

當(dāng)符號執(zhí)行到達循環(huán)條件時，說明當(dāng)前的循環(huán)經(jīng)過了完整的一輪迭代執(zhí)行，需將符號狀態(tài)上所標(biāo)注的迭代次數(shù)加1，將繼續(xù)在循環(huán)內(nèi)運行的符號狀態(tài)加入S，離開循環(huán)的狀態(tài)加入S’，并進行循環(huán)出口處理，以判斷當(dāng)前循環(huán)是否完成，并統(tǒng)計當(dāng)前所在循環(huán)的內(nèi)向邊界值。