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

（哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，哈爾濱　150001）

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

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

（哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，哈爾濱150001）

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

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

0　引 言

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

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

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

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

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

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

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

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

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

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

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

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

程序中使用到的一些運(yùn)算符，例如算術(shù)運(yùn)算符+、-、?、/、%，當(dāng)程序員在設(shè)計(jì)測試用例的時候，可能會產(chǎn)生巧合正確性測試用例。這種情況下產(chǎn)生的巧合正確性測試用例的偽代碼示例如下：

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

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

2.1方法的基本思想

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

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

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

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

2.3對巧合正確性測試用例進(jìn)行排序

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

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

2.3.1求解CCE［3］

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

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

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

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

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

2.3.2求解CCT［3］

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

2.3.3CCT排名

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

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

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

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

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

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

2.4實(shí)驗(yàn)結(jié)果

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

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

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

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

3　結(jié)束語

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

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

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

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

［1］梅宏，王千祥，張路，等.軟件分析技術(shù)進(jìn)展［J］.計(jì)算機(jī)學(xué)報(bào)，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

國家自然科學(xué)基金（61173021）。

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