基于信息流的關(guān)鍵軟件缺陷定位技術(shù)

周東紅，石 柱，王 瑞，李 沫

（中國航天系統(tǒng)科學(xué)與工程研究院，北京100048）

基于信息流的關(guān)鍵軟件缺陷定位技術(shù)

周東紅，石 柱，王 瑞，李 沫

（中國航天系統(tǒng)科學(xué)與工程研究院，北京100048）

針對軟件因涉及多程序要素間相互作用而來的復(fù)雜缺陷，研究了基于信息流的關(guān)鍵軟件缺陷定位技術(shù)，對現(xiàn)有的信息流進(jìn)行了擴(kuò)展，并對經(jīng)典方法的可疑度度量公式進(jìn)行了改進(jìn)，而且將其融入了相關(guān)算法；并進(jìn)行了與語句覆蓋、分支覆蓋和定義使用對覆蓋等缺陷定位技術(shù)的對比試驗，結(jié)果表明：此方法比基于語句覆蓋、分支覆蓋和定義使用對覆蓋的方法更可靠、更精確，能高效率地定位軟件中的缺陷。

軟件測試；復(fù)雜缺陷；信息流覆蓋；語句覆蓋；分支覆蓋；定義使用對覆蓋

1　引言

由于軟件的原因而導(dǎo)致的航空航天事故很多，其中由于軟件中存在整數(shù)溢出的缺陷而導(dǎo)致的事故，就有歐洲Ariane5火箭在發(fā)射時爆炸和Comair航空公司機(jī)組調(diào)度軟件崩潰等［1］。

據(jù)統(tǒng)計，在軟件研發(fā)和后期維護(hù)的成本中，軟件測試占到了50%～75%［2］。其中在測試中發(fā)現(xiàn)軟件缺陷，對缺陷進(jìn)行檢測定位和修正的調(diào)試過程是最困難且成本最高的步驟之一。傳統(tǒng)的測試工作一般由軟件測試人員手動完成，耗時耗力。

本文研究了基于信息流覆蓋的缺陷定位技術(shù)，并基于該技術(shù)設(shè)計了一個缺陷定位的原型工具，通過該工具能快速地找到軟件的缺陷，有效提高缺陷定位的效率。

2　基于動態(tài)信息流覆蓋的缺陷定位技術(shù)

本文中所使用的算法，是動態(tài)信息流分析的前向計算（forward computing）算法［3］，本章介紹了該算法的一些基本定義和擴(kuò)展研究，并說明了如何基于該方法進(jìn)行缺陷定位。

2.1 動態(tài)信息流

2.1.1 動態(tài)控制依賴

假設(shè)活動表示一個可執(zhí)行語句（或基本塊），則執(zhí)行路徑就是活動的一個序列。路徑T上的第k個活動表示為T（k）或sk（s為對應(yīng)的語句或基本塊）。“判斷活動”是指語句s是分支判斷語句的活動sk。子路徑T（k，m）表示的是一條從活動T（k）開始到活動T（m）結(jié)束的子序列［1］。動態(tài)控制依賴關(guān)系的形式化定義如下［3］：

定義1：假設(shè)sk和tm是執(zhí)行路徑T上的兩個活動（k＜m且sk是判斷活動），當(dāng)且僅當(dāng)子路徑T（k，m）證明了t直接控制依賴于s（t DCD s）時［4］，活動tm直接動態(tài)控制依賴于活動sk，表示為tmDDynCDsk。活動tm直接動態(tài)控制依賴的判斷活動如果存在，則它是唯一，表示為DDynCD（tm）。

其中DCD的含義為語句能通過它的控制分支決定是否執(zhí)行語句。直觀來看，DDynCD（tm）就是先于活動tm最后出現(xiàn)的判斷活動。

2.1.2 動態(tài)數(shù)據(jù)依賴

建模活動之間的動態(tài)數(shù)據(jù)依賴時，需要將下面兩個集合與每個活動聯(lián)系起來［5］：在活動sk中定義（或賦值）的變量或?qū)ο蠹疍（sk），和在sk中使用（或引用）的變量或?qū)ο蠹疷（sk）。

定義2：假設(shè)sk和tm是執(zhí)行路徑T上的兩個活動（k＜m）。當(dāng)且僅當(dāng)（D（sk）∩U（tm））-D（T（k+1，m-1））≠φ時，活動tm直接動態(tài)數(shù)據(jù)依賴于活動sk，表示為tmDDynDDsk［5］。活動tm直接動態(tài)數(shù)據(jù)依賴的活動集表示為DDynDD（tm）。

直觀看來，tmDDynDDsk表示的是tm使用（或引用）了最后由sk進(jìn)行定義（或賦值）的變量或?qū)ο蟆?.1.3 直接影響和影響

另外，本文還引用了其他三種活動間的動態(tài)依賴關(guān)系［6］：

1）函數(shù)使用了一個由return語句返回的值；

2）函數(shù)使用了一個由形式化參數(shù)傳遞的值；

3）函數(shù)的請求調(diào)用方法指令中存在控制依賴。

對于兩個活動sk和tm（k＜m），當(dāng)且僅當(dāng)活動tm在上述的5類依賴關(guān)系中依賴于活動sk時，就認(rèn)為sk直接影響tm［7］。直接影響tm的活動集表示為DInfluence（tm），簡稱為DInf（tm）。

“影響”關(guān)系則表示一個語句能影響到其他語句的執(zhí)行，包含直接和間接影響［1］。

定義3：假設(shè)T為一條執(zhí)行路徑，sk和tm為T中的兩個活動（k＜m）。當(dāng)且僅當(dāng)在T中存在著活動序列a1，a2，……，an，其中a1=sk，an= tm，并且對于i=1，……，n-1，都有aiDInfluenceai+1，則有sk“影響”tm，表示為skInfluence tm。影響tm的活動集表示為Influence（tm），簡稱為Inf（tm），計算公式如公式（1）：

2.1.4 動態(tài)信息流分析

動態(tài)信息流分析是確定在活動sk中影響了其他變量或?qū)ο蟮乃凶兞炕驅(qū)ο蟮募希?］。

定義：設(shè)T為一條程序執(zhí)行路徑，sk和tm為T中的兩個活動（k＜m），設(shè)x和y是兩個變量：活動sk定義了變量x并且活動tm使用了變量y。當(dāng)且僅當(dāng)skInfluence tm時，存在著從活動sk中的變量x到活動tm中的變量y的信息流，該信息流表示為（sk，x，tm，y）［9］。目標(biāo)為tm內(nèi)的y變量的信息流中包含的變量和對象集合如式（2）：

式中，U（tm）是活動tm中使用了的變量或?qū)ο蟮募希琔（Inf（tm））則是影響tm的活動中使用了的變量或?qū)ο蟮募稀?/p>

信息流實例的表示方法為四元組（sk，x，tm，y），其中sk表示最后定義或使用了源對象x的活動，tm表示最后定義或使用了目標(biāo)對象y的活動。

2.1.5 信息流及其長度

信息流的長度，定義為它包含的動態(tài)數(shù)據(jù)依賴鏈和控制依賴鏈的長度［10］。我們規(guī)定信息流長度的計算規(guī)則如下：如果tm使用了對象x，則長度為1；否則，長度就是最短依賴鏈的長度，而且信息通過該依賴鏈從對象x流入到對象y。這樣，通過綜合考慮信息流及其長度就能區(qū)分兩個有著完全相同的源和目標(biāo)但長度不同的信息流了。很明顯，通過這些信息還是不能區(qū)分兩個有完全相同的源、目標(biāo)和長度的信息流。

2.2 對動態(tài)信息流的擴(kuò)展

動態(tài)信息流分析能夠識別程序運行時程序?qū)ο笾g的信息流，但是現(xiàn)有的研究中，沒有考慮分支和定義使用對，在源和目標(biāo)處的依賴關(guān)系是條件語句、返回語句和方法請求時，不能捕獲該信息流。因此，需要對動態(tài)信息流技術(shù)進(jìn)行擴(kuò)展，使其包含定義使用對和分支，從而可捕獲上述的依賴關(guān)系。標(biāo)準(zhǔn)的信息流格式為（sk，x，tm，y）［9］，其中sk表示最后定義了源對象x的活動，tm表示最后定義了目標(biāo)對象y的活動。而通過引入分支和定義使用對，如果源或目標(biāo)為返回語句或條件判決語句時，就用‘-'號作為對象名。如表1中就有擴(kuò)展的信息流（7，-，8，ch），這里第7條源代碼為條件判斷語句，所以其對象名應(yīng)為‘-'。

2.3 語句可疑度度量標(biāo)準(zhǔn)

信息流f可疑度的計算可采用式（3）［10］：

式中，%P（f）運行過程包含信息流f的成功測試用例個數(shù)與總的成功用例數(shù)的比值；%F（f）運行過程包含信息流f的失敗測試用例個數(shù)與總的失敗用例數(shù)的比值。

但是，僅僅根據(jù)這個公式進(jìn)行可疑度排序是不夠的。例如給定兩個信息流f1和f2，其中%F（f1）=0.1，%F（f2）=1.0，%P（f1）=%P（f2）=0。如果使用公式（3），會得到SF1（f1）= SF1（f2）=1.0。但是根據(jù)%F（f1）=0.1和% F（f2）=1.0，可以判斷出f2的可疑度高于f1。為解決這個問題，本文引入了第二個度量值SF2=%F（f）。使用這個度量值，就能判斷出f2的可疑度高于f1。

綜合考慮度量值SF1和SF2，基于信息流的缺陷覆蓋技術(shù)就可以使用式（4）所示的度量準(zhǔn)則：

較高的SF（f）值意味著較高的可疑度排列。當(dāng)兩個信息流的SF值相同時，規(guī)定較短的信息流可疑度較高。而程序語句的可疑度值就是包含該語句的全部信息流中SF值最大的信息流的可疑度值。最后根據(jù)程序語句的可疑度值降序排列所有程序語句。

3　算法實現(xiàn)

本章用圖1的案例演示如何實現(xiàn)該算法。該程序中出錯的程序語句為S6，正常情況下，power［0］的值應(yīng)該為128，但是程序中會是-128。這樣當(dāng)輸入的8位二進(jìn)制數(shù)的最左邊一位為1時，結(jié)果就會出錯。

3.1 動態(tài)依賴關(guān)系實現(xiàn)算法

計算直接動態(tài)控制依賴關(guān)系（DDynCD）的算法如圖2所示，它計算動態(tài)信息流，能同時應(yīng)用于結(jié)構(gòu)化的和非結(jié)構(gòu)化的程序中。該算法中用到的數(shù)據(jù)結(jié)構(gòu)是棧CDSTACK（m），該棧存儲影響范圍還沒有完全退出的判定活動。當(dāng)執(zhí)行到了棧頂元素的ipd（s）時，程序就認(rèn)為退出了判定活動Sk的動態(tài)領(lǐng)域，此時從棧CDSTACK（m）中彈出活動Sk。

圖1　示例程序代碼Fig.1 Code of the typical example program

表1　示例程序的信息流覆蓋信息Table 1 Information flow coverage information of the example program

算法主要分為四步：

1）如果被訪問的路徑結(jié)點為判斷結(jié)點時，將該結(jié)點入棧CDSTACK（m）；

2）如果被訪問的結(jié)點是棧頂元素的直接后控制結(jié)點，則將該棧頂元素出棧CDSTACK（m）；

3）如果棧不為空，則當(dāng)前結(jié)點直接動態(tài)控制依賴于棧CDSTACK（m）的棧頂元素；如果棧為空，則當(dāng)前結(jié)點直接動態(tài)控制依賴的頂點為空；

4）如果當(dāng)前訪問結(jié)點的直接后控制結(jié)點與棧頂元素的直接后控制結(jié)點相同，則將棧頂?shù)呐袛嘟Y(jié)點出棧CDSTACK（m）（目的是為了限制棧的大小）。

按上述算法，可以得到圖1中的程序在執(zhí)行路徑T=＜S1，S2，S3，S4，S5，S6，S5，S6，S5，S6，S5，……＞的DDynCD關(guān)系，如表2所示，它與直接使用DDynCD關(guān)系的定義得到的結(jié)果相同。

3.2 動態(tài)依賴關(guān)系實現(xiàn)算法

動態(tài)信息流分析和動態(tài)切片算法如圖3所示。算法在執(zhí)行程序時對每個活動tm頻繁地使用公式（2），計算完成后存儲計算結(jié)果以便隨后使用。因為該算法是前向算法，當(dāng)輸入活動為活動tm時，算法計算時所有需要使用的值應(yīng)該都已經(jīng)計算得到并且可用。

在動態(tài)信息流分析算法中，并集操作對算法性能有著很大的影響。假設(shè)程序中語句的數(shù)量為m、活動對象的數(shù)量為n、用于實現(xiàn)并集的集合元運算（如添加、包含等）需要單位時間成本。則在最壞的情況下，計算活動tm的動態(tài)信息流的時間復(fù)雜度為O（n2）（包含計算該活動之前所需要的時間）；此時，信息流從每個對象流入到其他所有的對象、并且所有的活動對象都對tm有直接影響。此時并集操作涉及n個子集，每個子集有n個對象。另外，最壞的情況下，計算活動tm的動態(tài)切片［6］的時間復(fù)雜度為O（n*m）（包含計算該活動之前所需要的時間），此時，所有n個活動對象的每一個切片都包含m個程序語句、并且所有的活動對象都對tm有直接影響。此時并集操作涉及n個子集，每個子集有m個對象。

圖2　計算直接動態(tài)控制依賴的算法Fig.2 DDynCD algorithm

表2　控制流圖1中執(zhí)行路徑T對應(yīng)的DDynCD關(guān)系表Table 2 Relationship of trace T in CFG of Fig.1 with DDynCD

圖3　動態(tài)信息流分析和動態(tài)切片算法Fig.3 InfoFlow algorithm and DynSlice algorithm

對圖1所示的程序設(shè)計了6個測試用例，其輸入分別為T1=00000000、T2=00001111、T3= 01010101、T4=01101101、T5=11111111、T6= 10101010，其中前4個執(zhí)行通過，T5和T6執(zhí)行失敗。通過使用圖3的算法對其分析，可得如表1所示的信息流覆蓋信息。表1中，信息流InF1=（6，powers［0］，10，decimal），InF2=（6，powers［0］，11，decimal），InF3=（6，powers［6］，10，decimal），InF4=（6，powers［6］，11，decimal），InF5=（6，powers［5］，10，decimal），InF6=（6，powers［5］，11，decimal），InF7=（8，ch，9，-），InF8=（10，decimal，11，-），InF9=（7，-，8，ch），InF10=（2，decimal，10，decimal），R*為可疑度值高于或等于出錯語句可疑度值的語句數(shù)。

4　試驗評價

4.1 試驗概述

本文選擇SIR的西門子測試套件的TCAS軟件作為被測對象，TCAS（Traffic Alert and Collision Avoidance System，交通警戒和避撞系統(tǒng)）是一套被航空公司采用的飛機(jī)碰撞檢測和回避系統(tǒng)。

4.2 試驗數(shù)據(jù)

對試驗中使用的軟件進(jìn)行了修改，注入了5個缺陷，注入情況如表3所示。

表3　TCAS軟件中注入的缺陷Table 3 The seeded defects in TCAS program

表4　TCAS軟件的測試結(jié)果Table 4 The test results of TCAS program

4.3 試驗結(jié)果

為了說明方法的有效性，將結(jié)果與標(biāo)準(zhǔn)的語句覆蓋技術(shù)［11］、分支覆蓋技術(shù)和定義使用對覆蓋技術(shù)［12］得到的結(jié)果進(jìn)行對比。使用中共設(shè)計了172個測試用例。

測試結(jié)果如表4所示，其中S*max為用相關(guān)方法計算所有語句的可疑度值中的最大值，S*為用相關(guān)方法計算得到的出錯語句可疑度值，R*為可疑度值高于或等于出錯語句可疑度值的語句數(shù)，RS-*為用對應(yīng)的方法排查軟件缺陷時需要人工核查的程序語句數(shù)。

從表4中的F2可以看到：

1）172個測試用例中，有36個運行失敗。

2）出錯語句的SS和SB值均為0.93，與最大值1.0都有些差距，這意味著一些正常的語句會比出錯語句更可疑。另外，出錯語句的SDU值為空，因為這里沒有定義使用對。但是該語句的SF和SFmax均為1.0。這證明了信息流覆蓋比其他的技術(shù)要更可靠。

3）測試人員按排列順序核查到出錯語句時，使用語句覆蓋技術(shù)需要多檢查63條程序語句，使用分支覆蓋技術(shù)時是31條，使用信息流覆蓋技術(shù)時則為8條。使用定義使用對技術(shù)時更是需要檢查所有的程序語句。這一結(jié)果證明了信息流覆蓋技術(shù)要更加精確。

試驗結(jié)果表明，信息流覆蓋技術(shù)比語句覆蓋技術(shù)更可靠、更精確。在所有數(shù)據(jù)中，它的可靠性都高于其他三種技術(shù)，雖然個別缺陷上它的精確性不如分支覆蓋或定義使用對覆蓋技術(shù)，但是從平均數(shù)上看，它的精確性優(yōu)于其他三種技術(shù)。

5　結(jié)論

本文研究了基于信息流覆蓋的缺陷定位技術(shù)，并基于該技術(shù)設(shè)計了一個缺陷定位的原型工具，通過該工具能快速地找到軟件的缺陷，提高缺陷定位的效率。通過試驗證明了該方法比語句覆蓋、分支覆蓋和定義使用對覆蓋更有效。試驗結(jié)果表明，在一些案例中信息流覆蓋的性能要優(yōu)于分支覆蓋和定義使用對覆蓋技術(shù)，而且在所有的數(shù)據(jù)中其性能都要優(yōu)于語句覆蓋技術(shù)；在可靠性方面，它在所有的數(shù)據(jù)中都要優(yōu)于其他三種技術(shù)。

（References）

［1］Masri W，Podgurski A.Algorithms and tool support for dynamic information flow analysis［J］.Information and Software Technology，2009，51（2）：386-404.

［2］Hailpern B，Santhanam P.Software debugging，testing，and verification［J］.IBM Systems Journal，2002，41（1）：4-12.

［3］Shchekotykhin K，F(xiàn)riedrich G，F(xiàn)leiss P，et al.Interactive ontology debugging：Two query strategies for efficient fault localization［J］.Web Semantics：Science，Services and Agents on the World Wide Web，2012（12）：88-103.

［4］Sahoo S K，Criswell J，Geigle C，et al.Using likely invariants for automated software fault localization［J］.ACM SIGARCH Computer Architecture News，2013，41（1）：139-152.

［5］Weiser M.Program slicing［C］//Proceedings of the 5th international conference on Software engineering.IEEE Press，1981：439-449.

［6］Korel B，Laski J.Dynamic program slicing［J］.Information Processing Letters，1988，29（3）：155-163.

［7］虞凱，林夢香.自動化軟件錯誤定位技術(shù)研究進(jìn)展［J］.計算機(jī)學(xué)報，2011，34（8）：1411-1422.YU Kai，LIN Mengxiang.Advances in automatic fault localization techniques［J］.Chinese Journal of Computers，2011，34（8）：1411-1422.（in Chinese）

［8］Masri W.Fault localization based on information flow coverage［J］.Software Testing，Verification and Reliability，2010，20（2）：121-147.

［9］Masri W，Podgurski A，Leon D.detecting and debugging insecure information flows［C］//Piscataway，NJ：IEEE Press.2004.198-209.

［10］Masri W，Podgurski A，Leon D.An empirical study of test case filtering techniques based on exercising information flows［J］.IEEE Transactions on Software Engineering，2007，33（7）：454-477.

［11］惠戰(zhàn)偉，黃松，嵇孟雨.基于程序特征譜整數(shù)溢出錯誤定位技術(shù)研究［J］.計算機(jī)學(xué)報，2012，35（10）：2204-2214.HUI Zhanwei，HUANG Song，JI Mengyu.Research on spectra-based integer bug localization［J］.Chinese Journal of Computers，2012，35（10）：2204-2214.（in Chinese）

［12］Yu K，Lin M，Gao Q，et al.Locating faults using multiple spectra-specific models［C］//Proceedings of the 2011 ACM Symposium on Applied Computing.ACM，2011：1404-1410.

The Critical Defect Localization Technique Based on Information Flow in Software

ZHOU Donghong，SHI Zhu，WANG Rui，LI Mo
（China Academy of Aerospace Systems Science and Engineering，Beijing 100048，China）

The complex defects imposed by the interactions among many program elements in the software are difficult to exclude.To solve this problem，the critical software fault localization techniques based on information flow coverage were studied.The present information flow was extended and the suspicious metric formula of the classical methods was improved and incorporated into the related algorithm.Then comparative tests were conducted with the defect localization techniques including the statements coverage，branches coverage and define-use pair coverage methods.The experiment results showed that this method could efficiently locate the software defects and was more precise and reliable than the other methods.

software test；complex defect；information flow coverage；statement coverage；branch coverage；define-use pair coverage

TP311

A

1674-5825（2016）05-0635-06

2015-06-30；

2016-06-29

周東紅（1981-），男，碩士，工程師，研究方向為軟件工程軟件缺陷定位。E-mail：19781970@qq.com