[發明專利]一種基于重構控制流圖的控制流錯誤檢測優化方法

無效

• 申請號: 201010504386.1
• 申請日: 2010-10-12
• 公開（公告）號: CN101944064A
• 公開（公告）日: 2011-01-12
• 發明（設計）人: 譚慶平;李建立;寧洪;徐建軍;周會平;譚蘭芳;徐錫山
• 申請（專利權）人: 中國人民解放軍國防科學技術大學
• 主分類號: G06F11/36
• 分類號: G06F11/36
• 代理公司: 國防科技大學專利服務中心 43202
• 代理人: 郭敏

1.一種基于重構控制流圖的控制流錯誤檢測優化方法，包括以下步驟：

第一步，將源程序劃分為基本塊，構建基本塊表；

第二步，基于基本塊表，構建程序控制流圖；

其特征在于還包括以下步驟：

第三步，基于控制流圖，劃分邏輯塊，構建邏輯塊表：?

3.1?構造并初始化局部路徑鏈和標志位：分別為每個基本塊構造一個局部路徑鏈，局部路徑鏈是多個基本塊組成的鏈表，鏈表中每個結點存放一個基本塊編號，鏈表的第一個結點定義為鏈頭，鏈表的最后一個結點定義為鏈尾；為基本塊B_m構造的局部路徑鏈L_m的鏈頭存放B_m的編號；針對每個局部路徑鏈分別創建一個對應的標志位，初始值置為真；

3.2?基于控制流圖更新局部路徑鏈：針對每個對應標志位為真的局部路徑鏈，若該鏈表的鏈尾對應的基本塊B_end是分界塊，則將該鏈表對應的標志位置為假；若B_end不是分界塊，則查找控制流圖中B_end的后繼基本塊，并將后繼基本塊的編號作為一個新結點插入到鏈表尾部；分界塊指多扇出塊、程序結束塊、函數調用塊的前驅、函數調用塊或出口塊，多扇出塊是指控制流圖中有多于一個后繼的基本塊；

3.3?判斷是否所有局部路徑鏈對應的標志位都為假，如果是則執行第3.4步，否則轉到第3.2步；

3.4?刪除符合條件的局部路徑鏈：選擇滿足如下刪除條件的鏈表L_short和L_long，然后刪除L_short：

lL_short是L_long中的一段；且

lL_short的鏈頭對應的基本塊在控制流圖中的任何前驅基本塊都不是分界塊；

3.5?判斷是否還存在符合第3.4步刪除條件的局部路徑鏈，如果是則執行第3.4步，否則轉到第3.6步；

3.6?基于局部路徑鏈構建邏輯塊表：為每個局部路徑鏈分配編號，將每個局部路徑鏈和對應的編號作為一條記錄存入邏輯塊表，此時，每個局部路徑鏈里的所有基本塊構成一個邏輯塊，每個局部路徑鏈的編號即為對應邏輯塊的編號；邏輯塊是一個確定先后執行的基本塊序列，邏輯塊的最后一個基本塊是分界塊，第一個基本塊在控制流圖中的前驅至少有一個是分界塊；

第四步，復制基本塊，使得邏輯塊相互獨立。

2.本步驟的具體過程是：

4.1?復制公共基本塊：從邏輯塊表中選擇含有公共基本塊的兩個邏輯塊L₁和L₂，然后選擇距離L₁的鏈頭最近的公共基本塊B，并在源程序中復制B得到副本基本塊B--；?

4.2?修改控制流關系：保持邏輯塊L₁不變，修改L₂內部的控制流關系，將L₂中基本塊B的前驅的后繼變為副本基本塊B--；

4.3更新基本塊表和邏輯塊表：為復制得到的副本基本塊分配不同的編號，將副本基本塊的編號和入口指令地址、出口指令地址存入基本塊表；更新L₂在邏輯塊表中的局部路徑鏈信息；

4.4?判斷是否所有的邏輯塊都不存在公共基本塊，如果是則第四步結束，否則轉到第4.1步；

第五步，根據配置要求均勻切割邏輯塊，構建基本邏輯塊表：

5.1?基于邏輯塊表和基本塊表，統計每個邏輯塊包含的指令數量N；

5.2?對每個邏輯塊，如果其長度N大于長度上限n，則將其平均分割為éN/nù個基本邏輯塊；如果其長度N小于等于n，該邏輯塊也為一個基本邏輯塊；基本邏輯塊為長度原本小于n的邏輯塊和將邏輯塊根據n進行平均分割得到的塊，所有基本邏輯塊的長度都小于或等于n；n為所有的基本邏輯塊大小的上限，取值范圍是1≤n≤N_max，N_max是最大的邏輯塊的長度；é?ù表示上取整運算；

5.3?為分割得到的每個基本邏輯塊分配不同的編號，并將基本邏輯塊編號和入口指令地址、出口指令地址存入基本邏輯塊表；

第六步，基于基本邏輯塊表，重構程序控制流圖。

3.2.如權利要求1所述的基于重構控制流圖的控制流錯誤檢測優化方法，其特征在于n取5。