基于迭代預測降低巧合正確性測試用例影響的軟件錯誤定位方法

趙 群，蘇小紅，王甜甜，馬培軍

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

基于迭代預測降低巧合正確性測試用例影響的軟件錯誤定位方法

趙 群，蘇小紅，王甜甜，馬培軍

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

巧合正確性測試用例是指某個測試用例雖然在執(zhí)行程序時覆蓋了錯誤的代碼行，但是其測試結果依然是正確的。在測試用例集中，巧合正確性測試用例是普遍存在的。巧合正確性測試用例對基于程序譜的軟件錯誤定位方法的錯誤定位精度產生很大的影響。為了避免這一影響，本文提出一種基于迭代預測降低巧合正確性測試用例影響的方法。該方法的基本思想是通過迭代的方法，預測巧合正確性測試用例的數(shù)目N，再對候選測試用例的巧合正確性可疑值進行排序，去掉可疑值較高的前N個巧合正確性測試用例，利用新的測試集進行錯誤定位，直到找到錯誤語句，或者候選的巧合正確性測試用例的個數(shù)小于迭代預測值N為止。使用Siemens Suite測試用例集對系統(tǒng)進行了測試，測試結果表明該方法能夠有效提高基于程序譜的軟件錯誤定位方法的錯誤定位精度。

錯誤定位；巧合正確性；測試用例；迭代；預測

0　引 言

目前，自動化軟件錯誤定位技術有多種［1］，但是，由于巧合正確性測試用例的存在，使得這類錯誤定位方法所計算出來的錯誤語句的可疑值偏低，影響軟件錯誤定位方法的精確性。本文首先通過舉例，解釋巧合正確性測試用例的含義，然后具體介紹方法是如何實現(xiàn)的，主要從方法提出的動機，方法的基本框架，預測當前測試用例集中巧合正確性測試用例個數(shù)和對巧合正確性測試用例進行排序4個方面展開，最后通過實驗測試方法的有效性，得出結論。

1　巧合正確性測試用例的特征

1.1 巧合正確性測試用例的特征

巧合正確性測試用例是指某個測試用例雖然在執(zhí)行程序時覆蓋了錯誤的代碼行，但是其測試結果依然是正確的。編程人員在源代碼開發(fā)過程中不可避免地會引入程序錯誤，當測試人員進行測試的時候，對可執(zhí)行程序執(zhí)行測試用例，可能發(fā)生如下情況：Tests運行到了錯誤的代碼行，使得錯誤的代碼被感染（infection），錯誤的程序狀態(tài)產生了，而后感染又被傳播（infection propagation），最終導致軟件失效（failure）［2］。當對出錯的程序進行測試的時候，只有同時具備了下述3個條件［2］，程序員才能夠發(fā)現(xiàn)錯誤：

1）這次測試運行到了錯誤代碼行，也就是說，缺陷被激活；

2）錯誤的程序狀態(tài)被傳播，影響到后續(xù)程序的運行狀態(tài)；

3）錯誤狀態(tài)的傳播影響到了最終的輸出結果。

由此可見，有2種特殊的情況出現(xiàn)：

1）測試運行到了錯誤的代碼行，但是缺陷并沒有被傳播，也沒有影響到后續(xù)程序的運行狀態(tài)，即僅滿足了上述條件1）；

2）測試運行到了錯誤的代碼行，同時，缺陷被傳播了，但是，沒有影響到最終的輸出結果，即滿足了條件1）和條件2），但是，沒有滿足條件3）。

當上述2種情況發(fā)生時，并不會影響程序的輸出結果，這便是巧合正確性測試用例。

1.2巧合正確性測試用例舉例

程序中使用到的一些運算符，例如算術運算符+、-、?、/、%，當程序員在設計測試用例的時候，可能會產生巧合正確性測試用例。這種情況下產生的巧合正確性測試用例的偽代碼示例如下：

針對上面這個第4行存在錯誤的程序，進行測試，當測試用例選擇a=3，b=0的時候，并且當if語句條件為計算sum的時候，執(zhí)行該測試用例，其執(zhí)行軌跡通過了第5行的出錯語句，這時的result=a-b=3-0=3，此時其與正確的結果result=a+b=3+0=3是完全一樣的。顯然，這個bug并不會影響輸出的結果。即測試運行到了錯誤的代碼行，但是沒有影響輸出結果，依然為成功的測試用例，這個測試用例就是本文所說的巧合正確性測試用例。

2　基于迭代預測降低巧合正確性影響的錯誤定位方法

2.1方法的基本思想

本文的主要思想就是預測當前巧合正確性測試用例個數(shù)和使用TOP（k）加權排名方法對測試用例排名。如圖1所示，本文在執(zhí)行過程中，當獲得可疑度排名序列以后，預測當前可能的巧合正確性測試用例（Coincidental Correctness，簡稱為CC）個數(shù)，再利用TOP（k）加權排名方法，對經過篩選的測試用例排序，刪除排名較高的前N個測試用例，用新的測試集繼續(xù)迭代，直到找到錯誤語句，或者求得的候選測試用例的個數(shù)小于迭代預測出的N值為止。

2.2預測當前測試用例集中巧合正確性測試用例個數(shù)

本文在首次獲得待測程序的可疑值排名序列后，需要程序員來人工檢測排在第一位（包括并列第一的）的程序語句，假設為E，并且判斷某條（或多條）是否是錯誤的語句，如果是，則迭代過程停止，輸出錯誤語句；如果不是，則繼續(xù)迭代預測。在每次迭代預測過程中，都要預測當前測試用例集中含有的巧合正確性測試用例的個數(shù)N。下面就詳細解釋N如何得到的。

目前的自動化軟件錯誤定位技術通常假設待測程序只含有一個錯誤，如果程序員在檢測集合E的時候，發(fā)現(xiàn)E并不包含錯誤語句的時候，在最好的情況下，程序語句可疑值排名在次高位置的語句集合E’將包含錯誤語句，并且由于假設待測程序中僅包含一個錯誤，即可假設在最好的情況下，覆蓋了排名次高位的語句集合E’的那些成功的測試用例包含了當前所有巧合正確性測試用例，記為N。

2.3對巧合正確性測試用例進行排序

為了進一步預測到底哪些測試用例屬于巧合正確性測試用例，本文采用TOP（k）加權排名方法，預測一個成功的測試用例是巧合正確性測試用例的可能性大小，這個方法最終會得到一個測試用例可疑值降序排名列表，列表中隨著排名的降低，使巧合正確性測試用例的可能性也隨之降低，反之則升高。該方法目的是去掉列表中前N個測試用例，用剩下的測試用例繼續(xù)迭代。

這個TOP（k）加權排名方法第一步是要獲得與巧合性正確測試用例有關系的程序語句集合CCE（Coincidental Correctness Element），然后認為覆蓋了一條或者多條這樣的語句的測試用例集合為CCT（Coincidental Correctness Test），集合CCT里面的測試用例都有可能是巧合正確性測試用例，再對這部分測試用例進行加權排名，最后得到巧合正確性測試用例的可能性排名。

2.3.1求解CCE［3］

CCE（Coincidental Correctness Element）指的是滿足指定條件的程序語句的集合，使得集合中的程序語句與巧合正確性測試用例的關系相對較大，把集合中的一條語句稱為CCE。

可以成為CCE中的一條程序語句，必須滿足以下兩個條件：

1）fT（cce）=1.0——被所有錯誤的測試用例所覆蓋；2）0＜PT（cce）＜θ——被少部分正確的測試用例所覆蓋；

其中，fT（cce）是指被失敗的測試用例所覆蓋的概率；PT（cce）是指被成功的測試用例所覆蓋的概率。

這里θ的取值范圍需要說明一下，因為已有文獻表明，目前的測試用例集中大部分含有60%以下的巧合正確性測試用例，還有一部分測試用例集是含有60%～90%的巧合正確性測試用例，如果θ的值取到小于60%的話，那么很可能有一部分cce就找不到了，被遺漏下了，帶來實驗誤差，因此，本文將θ的取值限定在（0.6，0.9）之間。

2.3.2求解CCT［3］

TOP（k）加權排名方法的目的就在于獲得CCT這個集合，為集合中的測試用例賦權值排名。CCT指的是與巧合正確性測試用例關系密切的測試用例的集合。把覆蓋一條上述方法求得的cce或者多條cce的測試用例叫做cct，cct的集合就是CCT，并且為其賦權值，求出巧合正確性測試用例可能性大小的排序序列。

2.3.3CCT排名

采用TOP（k）加權排名方法對求得的CCT中的測試用例賦以一定的權值。研究表明，如果一個成功的測試用例和一個失敗的測試用例的語句覆蓋信息越相似，就越有可能是巧合正確性測試用例?；谶@個理論，通過計算成功測試用例和失敗測試用例覆蓋信息的相似程度，來評價一個成功的測試用例為巧合正確性測試用例的可能性，相似程度越高，則巧合正確性的可能性越高，反之則越低。相似度的計算方法如下。

式中，Ei（i=1，2）表示測試用例Ti（i=1，2）所執(zhí)行的程序語句的集合。用2個集合的交集中元素的個數(shù)除以2個集合并集中元素的個數(shù)就得到了任意2個測試用例的相似度。

利用上述公式可以求得測試用例集中任意一個成功的測試用例與任意一個失敗的測試用例的相似程度，那么計算一個成功的測試用例與整個測試集中所有失敗測試用例的評價相似度，計算方法如下。

圖1　方法的總體框架圖Fig.1 Overall frame of the algorithm

式中，Prox（p）代表該測試用例集中每一個成功的測試用例p和其他所有的失敗的測試用例F之間的相似度。同理，Prox（p）結果越大，這個測試用例就越可能是巧合正確性測試用例。

在計算得到相似度以后，可用如下公式（3）計算每個CCT的權值。計算公式為：

2.4實驗結果

為了驗證本文方法的有效性，現(xiàn)采用Siemens Suite測試集進行實驗，實驗對照組采用經典的SBFL方法Tarantula和 Ochiai方法，分別在不同的θ取值下完成實驗，評價指標采用發(fā)現(xiàn)錯誤時候，比經典SBFL方法需要檢查代碼減少量百分比。實驗結果如表1所示。

表1　不同θ取值下發(fā)現(xiàn)錯誤時平均檢查代碼減少量的百分比結果Tab.1 Code reduction percentage when finding error under different value of θ

從表1中可以看出當θ分別取0.7、0.8和0.9時，發(fā)現(xiàn)錯誤情況下，基于迭代預測降低巧合正確性測試用例影響的錯誤定位方法比Tarantula方法平均少檢查的代碼比例分別為2.1%、2.7%和3%，而比Ochiai方法平均少檢查的代碼比例分別為2.3%、3.1%和3.5%。還可以看出，隨著θ取值的增大，平均檢查的代碼量在逐漸減少。分析原因，這是因為，當θ取值逐漸減小，而當前測試集中實際含有的巧合正確性測試用例又相當多的時候，此時根據(jù)2.3中介紹的理論，就會有一部分CCE沒有被挑選出來，而與此同時，如果錯誤的語句正好又被遺漏了，相應計算的CCT實際上根本沒有覆蓋錯誤語句，這樣就會在客觀上增加巧合正確性測試用例識別的誤報率，因此使得θ逐漸減小的時候，代碼檢測減少量也隨之變小。

通過實驗得出，本文的方法可以在降低巧合正確性測試用例對基于程序譜的軟件錯誤定位方法精度的影響的基礎上，進一步提高錯誤定位精度。

3　結束語

為了降低巧合正確性測試用例對基于程序譜的軟件錯誤定位方法精度的影響，本文應用迭代預測和TOP（k）加權排名的思想，在每次迭代過程中預測出當前測試集中巧合正確性測試用例的個數(shù)N，再通過TOP（k）加權排名方法，對候選測試用例集進行排序，去除排名較高的前N個巧合正確性測試用例。本文的創(chuàng)新點主要有如下2點：

1）使用TOP（k）加權排名方法時，對測試集中的測試用例進行篩選，選出了與巧合正確性測試用例關系密切的測試集CCT，再對候選CCT集合進行排序；

2）TOP（k）加權排名方法中，對CCT進行排序時采用相似度作為權值計算公式進行排序。

但是，本文在為CCT排序時所使用的權值計算公式，只考慮到了2個影響因子，在以后的工作中會嘗試將更多的影響因子考慮進來；在求解CCE的過程中使用的θ值都是固定的，后續(xù)研究將嘗試每次迭代的過程都選用不同的θ值，進一步提高錯誤定位的精度。

［1］梅宏，王千祥，張路，等.軟件分析技術進展［J］.計算機學報，2009，32（9）：1697-1710.

［2］LATTNER C，ADVE V.LLVM：A compilation framework for lifelong program analysis&transformation［C］//Code Generation and Optimization，2004，CGO 2004.Interational Symposium on.IEEE. Palo Alto，California：IEEE，2004：75-86.

［3］CHANG C H，PAIGE R.From regular expressions to dfa＇s using compressed nfa′s［C］//Combinatorial Pattern Matching.Berlin Heidelberg：Springer，1992：90-110.

［4］RABIN M O，SCOTT D.Finite automata and their decision problems［J］.IBM journal of research and development，1959，3（2）：114-125.

［5］DeRemer F L.Practical translators for LR（k）languages［D］. Massachusetts：Massachusetts Institute of Technology，1969.

A method based on iterative prediction to lower the effection from coincidental correctness

ZHAO Qun，SU Xiaohong，WANG Tiantian，MA Peijun
（School of Computer Science and Technology，Harbin Institute of Technology，Harbin 150001，China）

There are lots of coincidental correctness in tests suit.As a result of the existence of coincidental correctness，the software error locating method based on the application spectrum of precision could be affected by a lot of coincidental correctness test cases. Therefore，this paper proposes a method based iterative prediction to improve the error code lines of dubious value.The main idea of the method is by iterative method，prediction accuracy of coincidence N is the number of test cases，and then the correctness suspicious coincidence that test cases to the candidate value for sorting，get rid of dubious value higher N coincidence correctness before test cases，until you find false statements，or seeking candidates for the number of test cases is less than the number of iteration to predict N.The system is tested by using Siemens Suite，and the results show that the method could effectively improve the software error locating precision based on the application spectrum.

error locating；coincidental correctness；test cases；iteration；prediction

TP311

A

2095-2163（2016）03-0119-04

2015-06-23

國家自然科學基金（61173021）。

趙 群（1989-），女，碩士研究生，主要研究方向：軟件工程、軟件錯誤定位；蘇小紅（1966-），女，博士后，教授，博士生導師，主要研究方向：軟件工程、智能信息處理與信息融合、圖像處理等；王甜甜（1980-），女，博士，副教授，主要研究方向：程序分析、計算機輔助教學；馬培軍（1963-），男，博士，教授，博士生導師，主要研究方向：軟件工程、智能信息處理與信息融合。