冗余代碼缺陷檢測方法

龔丹丹，王甜甜，蘇小紅，馬培軍

(哈爾濱工業大學計算機科學與技術學院，150001 哈爾濱)

冗余代碼缺陷檢測方法

龔丹丹，王甜甜，蘇小紅，馬培軍

(哈爾濱工業大學計算機科學與技術學院，150001 哈爾濱)

為解決冗余代碼缺陷檢測復雜度較高且檢測精度較低的問題，設計并實現了基于控制結構的冗余代碼檢測模型.通過對TOKEN序列建立復合語句結構信息表，精簡了程序的控制依賴關系，并在此基礎上對冪等操作、死代碼以及冗余賦值3種冗余代碼進行檢測，有效降低了缺陷檢測復雜度.通過分析Linux開源代碼表明，本模型可以快速的檢測大規模程序，并且具有較低的誤報率和漏報率.因此本模型可以幫助程序員發現進而修正軟件缺陷，維護軟件可靠性.

冗余代碼;TOKEN序列;代碼標準化

程序中的冗余代碼意味著算法設計、代碼實現中存在著問題.冗余代碼不僅影響軟件的測試評估和運行效率，同時還存在著潛在的安全隱患，并由此而引發語義和邏輯缺陷，而這些缺陷很難被已有的軟件缺陷檢測工具檢測到，因此，需要對程序中的冗余代碼進行檢測.目前的冗余代碼檢測算法普遍誤報率較高，很多學者針對缺陷誤報率，進行了廣泛的研究.其中，符號執行類方法［1－5］成為當前熱門的檢測方法，但在遇到循環、過程調用、選擇分支過多時，符號執行實現困難.文獻［6－9］根據區間運算理論提高檢測精度，但目前現有的區間運算理論支持的數據類型單一，并不能解決非線性函數的區間運算和復雜條件表達式的區間運算.同時，這些方法都是基于控制依賴圖和數據依賴圖，分析的復雜度高，并不適合測試大型軟件.本文具體分析了冗余代碼不同類型所產生的誤檢原因，制定了相關的抑制誤檢的策略，有效提高了檢測的精確度.

基于TOKEN序列的檢測方法，由于其具有最佳的時空效率，已經被廣泛用于重復代碼檢測.基于TOKEN序列的重復代碼檢測是將程序表示成TOKEN序列，使用模式匹配技術檢查代碼間的相似度，識別詞法相似的程序代碼，代表工具有Duploc、 NICAD、 Dup、 CCFinder、 CP-Miner等［10－14］.這些方法的時間與空間開銷較低，因此適合于分析大規模程序，然而它們只是在詞法級別上對代碼進行分析，并不能考慮語法或語義，僅僅只是處理程序的順序結構，而無法處理選擇和循環結構.簡單的結構代碼改變就可使該方法失效，因此不適合直接在TOKEN序列的基礎上檢測冗余代碼.系統依賴圖是程序的語義表示，能夠充分表示程序的數據依賴、控制依賴信息以及函數調用信息，這適合于檢測冗余代碼缺陷，但因其系統依賴圖的復雜度較高，并不適合于檢測大規模程序.

針對上述分析，本文提出了精簡的控制依賴關系，通過對TOKEN序列建立復合語句控制結構信息表，降低程序表示和分析的復雜度，以達到檢測大型軟件中的冗余代碼的目的.

1 代碼標準化

由于編程語言語法的多樣性和代碼實現的靈活性，相同的算法可能有多種不同的代碼表達方式.例如，有些程序元素可以用一條語句表示，也可以用多條語句構成的語句序列表示(int i，j;等價于int i;int j;)，這種現象稱為代碼多樣化.識別這種語法表達形式多樣但語義等價的代碼，給程序分析帶來了困難［15］，直接影響了缺陷檢測的精確度.程序標準化［16］是根據一系列標準化規則對程序進行語義等價的轉換［17］的過程，目的是使語法表示不同但語義等價的程序有相同的系統表示，從而消除代碼多樣化，簡化程序分析.

本文在TOKEN序列的基礎上，根據一系列標準化規則進行結構語義等價的轉換.轉換規則如下.

1)將表達式轉換為只引用變量而不定義變量的形式，從而消除副作用.例如:

2)拆分變量聲明語句.例如:

3)拆分變量聲明與初始化語句.例如:

4)拆分連續的賦值語句.例如:

5)轉換++、－－運算符.例如:

6)轉換符合運算符(+=、－ =、*=、/=、%=).例如:

7)如果復合表達式中含有函數調用語句，則用臨時變量替換該函數調用語句.例如:

8)如果函數調用語句中的實參是復合表達式，則用臨時變量替換該復合表達式.例如:

9)如果return語句返回的是復合表達式，則用臨時變量替換該復合表達式.例如:

在消除代碼多樣化后大多數語法不同但語義等價的程序具有相同的TOKEN表示.這為冗余代碼缺陷檢測奠定了良好的基礎，不僅可以簡化程序分析，而且可以消除由于代碼多樣化所產生的誤檢.

2 復合語句控制結構信息表

復合語句控制結構信息表(CNT)記錄了各復合語句的開始－結束位置等重要信息，按照CNT遍歷程序的TOKEN序列，可以準確控制程序的掃描路徑，CNT只記錄復合語句信息，不需要分析整個程序的控制依賴關系，其復雜度遠遠低于控制依賴圖.

冗余代碼缺陷檢測，需要考慮程序的控制依賴關系，因此，不能直接利用傳統的TOKEN序列進行檢測.

針對上述問題，本文針對每個函數建立復合語句控制結構信息表，存儲復合語句的結構信息.根據結構信息表掃描TOKEN序列，充分考慮了程序的控制信息，節省了時間與空間，以達到應用于大規模程序的目的.

定義1(復合語句控制結構信息表(Compound node table，CNT)) 復合語句控制結構信息表是記錄程序P中的所有復合語句(選擇、循環)的開始、結束位置等關鍵信息的集合，它能夠精簡的記錄程序的所有控制依賴關系，其結構定義如圖1所示.

圖1 復合語句控制結構信息表結構

對于多分支的選擇結構，不僅應該記錄選擇結構的結束位置(endID)和結束行(endline)，還應該記錄各個分支內部的結束位置(ifendID)和結束行(ifendline)，以便進行精確的路徑分析.例如圖2所示，多分支選擇結構if(第13行)，其內部分支結束位置ifendline=16，總分支結束位置endline=20;對于第33行的else分支，其內部分支結束位置即為總分支的結束位置，即endline=ifendline=20.循環結構無需考慮多分支情況，因此for的endline與ifendline的值相同.

圖2 復合語句控制結構信息表實例

3 冗余代碼缺陷檢測

3.1 方法框架描述

冗余代碼檢測模型如圖3所示，主要包括3個部分:

1)將程序轉換為TOKEN序列，并在其基礎上進行代碼標準化，簡化程序分析的同時消除由于代碼多樣化所產生的誤檢，進而在標準化的TOKEN序列基礎上檢測冪等缺陷.

2)TOKEN序列缺少程序的結構化信息，因而不能很好的表示變量的依賴關系.系統依賴圖的復雜度較高，不適合分析大規模程序.針對此點，本文建立CNT，精簡了控制依賴關系，即能保證時間與空間復雜度，又能充分表示程序的控制依賴關系.

3)根據CNT，在標準化后的TOKEN序列上檢測死代碼和冗余賦值缺陷.

最后根據缺陷檢測結果，輸出缺陷檢測報告.

圖3 冗余代碼缺陷檢測模型

3.2 冪等操作檢查器

冪等操作包括下列3種情況:

1)賦值給自己(x=x);

2)被自身除(x/x);

3)自己與自己的位操作(x|x)或(x＆x).

本檢查器直接掃描程序的TOKEN序列，當所掃描的 TOKEN 為運算符“=”、“/”、“|”、“＆”任一運算符時，比較運算符左右兩端的TOKEN是否相等，如果相等，報告此缺陷.圖4為利用冪等操作檢查器所檢查到的缺陷.

圖4 利用冪等操作檢查器可以檢測出的軟件缺陷

3.3 死代碼檢測器

所謂檢查器，是指檢測在程序運行時不可到達的代碼.通過在Linux中的實驗表明，此類缺陷的產生原因主要是由于break和return所導致的奇怪控制流.例如:break后面但和break同屬一個塊的執行語句為死代碼;所有條件分支都包含return，則后面的代碼將不會被執行等等.

該檢查器涉及程序的控制信息，因此，根據CNT，在TOKEN序列的基礎上進行控制結構分析.對每條路徑，標記所有可由路徑所到達的語句.對于未標記的語句給出錯誤信息.為了提高效率，本檢查器以函數為單位進行檢測，并跳過宏定義，圖5為死代碼檢測具體算法.

此算法的關鍵之處在于按復合語句結構列表計算結束位置，充分考慮選擇、循環的嵌套情況，根據不同的情況計算TOKEN序列的掃描跳轉位置，即根據不同情況選擇ifendID和endID.此檢查器找到很多明顯的錯誤，并且無誤檢.

圖6、7為利用死代碼檢查器所檢查到的缺陷.圖6中第6行return語句后的語句不會執行，圖7中循環中包含的if-else語句中兩個分支均跳出循環，則后面的第13～18行語句不會被執行.

圖5 死代碼檢查器算法

圖6 死代碼檢測實例1

圖7 死代碼檢測實例2

3.4 冗余的賦值語句檢查器

該檢查器跟蹤變量的生存周期，在每個賦值語句處向前跟蹤所有路徑上的該變量.如果變量在退出所在域或被重新賦值前沒被使用，并且變量并非作為函數參數返回值，則發送錯誤信息.

該檢查器涉及程序的控制依賴分析，則僅在TOKEN序列的基礎上掃描必然帶來大量誤檢.因此，本文根據CNT，在TOKEN序列的基礎上進行控制結構分析，在最佳的時空效率下保證了檢測精度.

此檢查器的誤檢大多來自于保守編程.本文分析了保守編程的具體情況，根據不同的情況，制定不同的策略:

1)特殊賦值或前面有類型定義:p=head;int i=5;此類情況為保守編程，不給出錯誤信息.

2)第1次賦值(除情況1外).可能是保守編程為變量賦初值，也可能是直接為變量賦值，對于此情況給出警告信息.具體算法如圖8所示.

圖8 冗余的賦值語句檢查器算法

對于賦值語句位于循環結構中的情況，不僅要考慮”x=”中的”x”以及后面賦值的變量直接使用了循環變量，還要檢測”x”以及后面賦值的變量間接使用循環變量的情況，以減少誤檢.

圖9中列出了此檢查器檢測的Linux代碼冗余缺陷，第5行第1次為變量賦值，給出警告信息，第7行變量賦值后未使用，給出錯誤提示.

圖9 冗余的賦值語句檢測實例

4 實驗結果與分析

4.1 實際開源代碼缺陷檢測結果分析

本文對開源代碼Linux-2.6.6中的部分模塊進行了檢測.本文實驗條件為:Intel酷睿2雙核T5670，1.80 GHzCPU，1GB 內存，開發用工具為VC++6.0.表1～表3列出了實際開源代碼缺陷檢測的實驗結果.

表1 冪等缺陷檢測結果統計

表2 死代碼缺陷檢測結果統計

表3 冗余賦值缺陷檢測結果統計

4.2 人工注入缺陷檢測結果分析

為了統計漏檢率，本文對部分Linux源代碼進行了人工注入缺陷實驗.表4～表6列出了人工注入缺陷檢測實驗結果.

通過在Linux源代碼中實驗表明，本文所提出的冗余代碼缺陷檢測算法可以快速的識別大規模程序中的冪等操作、死代碼以及冗余賦值缺陷，并且檢測精度高，誤報率及漏報率均為0.冪等缺陷檢查器直接在TOKEN序列基礎上進行掃描，時間復雜度最低.而死代碼和冗余賦值缺陷檢測以函數為單位，在TOKEN序列的基礎上，利用CNT查找程序的控制依賴關系，時間復雜度略有提高.冗余賦值檢測器為了有效抑制誤檢，對于變量定義后第1次賦值，有可能是保守編程，給出警告.若變量不是第1次賦值，報告冗余賦值缺陷.

表4 人工注入冪等缺陷檢測結果統計

表5 人工注入死代碼缺陷檢測結果統計

表6 人工注入冗余賦值缺陷檢測結果統計

5 結論

1)提出了代碼標準化規則，且消除代碼多樣化，并簡化程序分析，有利于消除缺陷檢測中因代碼多樣化產生的誤檢.

2)本文提出了CNT，精簡了程序中控制依賴關系的表示.

3)設計并實現了基于控制結構的冗余代碼缺陷檢測模型，對程序中的冪等操作、死代碼以及冗余賦值3種冗余代碼進行檢測.該模型針對各種可能產生誤檢的原因進行了分析，制定了相關的抑制誤檢的策略.通過實驗證明，本模型可以快速檢測大規模程序，并且具有較低的誤報率和漏報率.

［1］ZHANG Jian.Constraint solving and symbolic execution［C］//Proceedings of the Verified Software:Theories，Tools，Experiments.Heidelberg，Berlin:Springer-Vierlag，2005:539 －544.

［2］XU Xiao，ZHANG Xiaosong S，LI Xiongda.New approach to path explosion problem of symbolic execution［C］//Proceedings of the 2010 First International Conference on Pervasive Computing，Signal Processing and Applications.Washington，DC:IEEE Computer Society，2010:301－304.

［3］COHEN M B，DWYER M B，SHI Jiangfan.Exploiting constraint solving history to construct interaction test suites［C］//Proceedings of the Testing:Academia and Industry Conference-Practice And Research Techniques.Washington，DC:IEEE Computer Society，2007:121 －130.

［4］PAPADAKIS M，MALEVRIS N.Automatic mutation test case generation via dynamic symbolic execution［C］//Proceedings of the 2010 IEEE 21st International Symposium on Software Reliability Engineering.Washington，DC:IEEE Computer Society，2010:121－130.

［5］PAPADAKIS M，MALEVRIS N.A symbolic execution tool based on the elimination of infeasible paths［C］//Proceedings of the 2010 Fifth International Conference on Software Engineering Advances.Washington，DC:IEEE Computer Society，2010:435 －440.

［6］王雅文，宮云戰，肖慶，等.區間運算在軟件缺陷檢測中的應用［C］.蘇州:第五屆中國測試學術會議論文集，2008:51－52.

［7］王雅文，宮云戰，肖慶，等.擴展區間運算的變量值范圍分析技術［J］.北京郵電大學學報，2009，32(3):36－41.

［8］王志言，劉椿年.區間算術在軟件測試中的應用［J］.軟件學報，1998，9(6):438－443.

［9］GHODRAT M A，GIVARGIS T，NICOLAN A.Expression equivalence checking using interval analysis［J］.IEEE Transactions on Very Large Scale Integration(VLSI)Systems，2006，14(8):830 －842.

［10］DUSCASSE S，RIEGER M，DEMEYER S.A language independent approach for detecting duplicated code［C］//Proceedings of the IEEE International Conference on Software Maintenance.Washington，DC:IEEE Computer Society，1999:109－118.

［11］ROY C K，CORDY J R.NICAD:accurate detection of near-miss intentional clones using flexible pretty-printing and code normalization［C］//Proceedings of the 2008 the 16th IEEE International Conference on Program Comprehension.Washington，DC:IEEE Computer Society，2008:172 －181.

［12］BAKER B.Parameterized duplication in strings:algorithms and an application to software maintenance［J］.SIAM Journal on Computing，1997，26(5):1343 －1362.

［13］KAMIYA T，KUSUMOTO S，INOUE K.CCFinder:a multilinguistic token-based code clone detection system for large scale source code［J］.IEEE Transactions on Software Engineering，2002，28(7):654－670.

［14］LI Zhenmin，LU Shan，MYAGMAR S，et al.CP-miner:finding copy-paste and related bugs in large-scale software code［J］.IEEE Transactions on Software Engineering，2006，32(3):176－192.

［15］RIEGER M.Effective clone detection without language barriers［D］.Switzerland:Dissertation，University of Bern，2005.

［16］De JONGE M，VISSER E，VISSER J.XT:a bundle of program transformation tools system description［J］.E-lectronic Notes in Theoretical Computer Science，2001，44(2):79－86.

［17］VISSER E.A survey of strategies in rule-based program transformation systems［J］.Journal of Symbolic Computation，2005，40(1):831 －873.

Redundancy detection based on control structure analysis

GONG Dan-dan，WANG Tian-tian，SU Xiao-hong，MA Pei-jun
(School of Computer Science and Technology，Harbin Institute of Technology，150001 Harbin，China)

To deal with the problems such as high complexity and low accuracy of redundancy detection，a model of redundancy detection based on control structure analysis is proposed and implemented.This paper predigests the complexity of control structure by establishing a compound node table for tokens，which reduces the complexity of redundancy detection，and then detects the idempotent operations，dead code and redundant assignment.Experimental results of the open source code of Linux show that this model can find redundant code accurately and also has a low time-complexity.With this model，it is very convenient for developers to detect and correct these kinds of defects，and thereby to further guarantee the software quality.

redundant code;TOKEN;code standardization

TP311

A

0367－6234(2012)07－0058－06

2011－06－21.

國家自然科學基金資助項目(61173021);高等學校博士學科點專項科研基金資助項目(20112302120052，20092302110040);中央高校基本科研業務費專項資金資助項目(HIT.NSRIF.201178).

龔丹丹(1982—)，女，博士研究生;

蘇小紅(1966—)，女，教授，博士生導師;

馬培軍(1963—)，男，教授，博士生導師.

龔丹丹，gongdandan0418@126.com.

(編輯 張 `紅)