[發(fā)明專利]基于靜態(tài)分析的冗余代碼缺陷檢測方法

無效

• 申請?zhí)枺?/td>: 201110216640.2
• 申請日: 2011-07-29
• 公開（公告）號: CN102231134A
• 公開（公告）日: 2011-11-02
• 發(fā)明（設(shè)計(jì)）人: 蘇小紅;馬培軍;王甜甜;龔丹丹;逄龍
• 申請（專利權(quán)）人: 哈爾濱工業(yè)大學(xué)
• 主分類號: G06F11/36
• 分類號: G06F11/36
• 代理公司: 哈爾濱市松花江專利商標(biāo)事務(wù)所 23109
• 代理人: 牟永林

技術(shù)領(lǐng)域

本發(fā)明涉及計(jì)算機(jī)程序分析技術(shù)和計(jì)算機(jī)軟件代碼檢測方法，具體涉及冗余代碼檢測方法。

背景技術(shù)

冗余代碼缺陷檢測是計(jì)算機(jī)軟件開發(fā)和維護(hù)活動(dòng)中一項(xiàng)重要的任務(wù)，在軟件維護(hù)、軟件缺陷檢測、程序理解等多個(gè)領(lǐng)域中都有廣泛的應(yīng)用。

程序中的冗余代碼通常存在兩種情況，一種是可達(dá)的，例如顯式冪等操作、隱式冪等操作、冗余的賦值語句、冗余的函數(shù)參數(shù)等，另一些是不可達(dá)的，例如死代碼、冗余的條件表達(dá)式等。冗余代碼不僅影響軟件的測試評估和運(yùn)行效率，而且還存在潛在的安全隱患，并由此而引發(fā)語義和邏輯缺陷，而這些缺陷很難被已有的軟件缺陷檢測工具檢測到。目前專門用來檢測冗余代碼及相關(guān)缺陷的方法和工具比較少，有文獻(xiàn)報(bào)道的只有Yichen?Xie和Dawson?Engler兩位學(xué)者研究了用于檢測顯式冪等、冗余的賦值語句、死代碼、冗余的條件表達(dá)式四種冗余代碼的缺陷檢查器，文中并未檢測隱式冪等和冗余的函數(shù)參數(shù)，也沒有給出檢測其余四種冗余代碼缺陷的具體解決方案。由于對冗余代碼及相關(guān)缺陷的關(guān)注較少，目前缺少成熟的對冗余代碼及相關(guān)缺陷檢測的方法。

發(fā)明內(nèi)容

本發(fā)明的目的是為了解決目前缺少成熟的對冗余代碼及相關(guān)缺陷檢測的方法的問題，提供一種基于靜態(tài)分析的冗余代碼缺陷檢測方法。

基于靜態(tài)分析的冗余代碼缺陷檢測方法，它包括具體步驟如下：

步驟1：輸入待測試程序，將其解析為抽象語法樹；

步驟2：分析可能包含顯式冪等操作的語句，檢測顯式冪等操作：遍歷程序的抽象語法樹，對可能包含冪等操作的特定類型的抽象語法樹子樹進(jìn)行處理，判斷是否存在缺陷；

步驟3：對局部定義的變量，采用過程內(nèi)部分析方法，檢測冗余的賦值語句：在抽象語法樹的基礎(chǔ)上，跟蹤每一個(gè)被賦值的變量，如果在函數(shù)結(jié)束之前或重新被賦值之前沒有被使用，則判為缺陷；

步驟4：遍歷程序的抽象語法樹，對每一個(gè)函數(shù)子樹創(chuàng)建對應(yīng)的程序依賴圖PDG，并將程序依賴圖PDG進(jìn)行選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)的標(biāo)準(zhǔn)化，在標(biāo)準(zhǔn)化后的程序依賴圖PDG的基礎(chǔ)上查找包含缺陷的結(jié)構(gòu)，檢測死代碼；

步驟5：在抽象語法樹的基礎(chǔ)上，分析程序的每條路徑，計(jì)算賦值表達(dá)式和條件表達(dá)式的值，檢測冗余的條件表達(dá)式：遍歷程序的抽象語法樹，跟蹤抽象語法樹中的賦值語句、條件分支中的謂詞集合、以及條件語句中的變量值的界限，來檢測分支語句中冗余——總是真或總是假的條件表達(dá)式；

步驟6：對程序的路徑進(jìn)行分析，檢測隱式冪等操作：遍歷程序的抽象語法樹，分析程序的每條路徑，跟蹤抽象語法樹中的賦值語句，根據(jù)賦值語句維護(hù)一個(gè)等價(jià)類集合，該集合記錄值相等的變量；當(dāng)具有相同值的變量之間互相賦值時(shí)，則判為存在隱式冪等缺陷；

步驟7：對每個(gè)函數(shù)的參數(shù)，采用過程內(nèi)部分析方法，檢測冗余的函數(shù)參數(shù)：在抽象語法樹的基礎(chǔ)上，采用過程內(nèi)部分析方法，跟蹤每一個(gè)函數(shù)參數(shù)，如果在函數(shù)結(jié)束之前或重新被賦值之前沒有被使用，則判為存在冗余的函數(shù)參數(shù)缺陷；

根據(jù)步驟2至7獲得的六種缺陷的檢測結(jié)果，給出缺陷檢測報(bào)告。

本發(fā)明的冗余代碼缺陷檢測方法能檢測程序中顯式冪等操作、冗余的賦值語句、死代碼、冗余的條件表達(dá)式、隱式冪等操作和冗余的函數(shù)參數(shù)，誤檢率和漏檢率低于3％，適用于大規(guī)模程序代碼的檢測分析技術(shù)領(lǐng)域。

附圖說明

圖1是本發(fā)明的方法的流程示意圖，圖2是本發(fā)明的方法所采用的基于抽象語法樹的冗余的賦值語句檢測模型示意圖，圖3是基于程序依賴圖的死代碼檢測過程示意圖，圖4為程序代碼的if語句的示意圖，圖5是程序依賴圖中if語句的標(biāo)準(zhǔn)化示意圖，圖6為程序代碼的switch語句的示意圖，圖7是程序依賴圖中switch語句的標(biāo)準(zhǔn)化示意圖，圖8為程序代碼的循環(huán)結(jié)構(gòu)的示意圖，圖9是程序依賴圖中循環(huán)結(jié)構(gòu)的標(biāo)準(zhǔn)化示意圖，圖10是根據(jù)程序的每條路徑，檢測冗余的條件表達(dá)式示意圖，圖11是具體實(shí)施方式一中所述檢測冗余的條件表達(dá)式過程中，處理選擇和循環(huán)結(jié)構(gòu)分支的示意圖，圖12是基于路徑分析的隱式冪等操作檢測過程示意圖，圖13是具體實(shí)施方式一中所述檢測隱式冪等操作過程中，處理選擇和循環(huán)結(jié)構(gòu)分支的過程示意圖。

具體實(shí)施方式

具體實(shí)施方式一：結(jié)合圖1說明本實(shí)施方式，本實(shí)施方式包括的具體步驟如下：

步驟1：輸入待測試程序，將其解析為抽象語法樹；

步驟2：分析可能包含顯式冪等操作的語句，檢測顯式冪等操作：遍歷程序的抽象語法樹，對可能包含冪等操作的特定類型的抽象語法樹子樹進(jìn)行處理，判斷是否存在缺陷；