收稿日期：2014－03－08

基金項目：國家自然科學基金(61173021，61202092)。

作者簡介：龔丹丹(1982-)，女，吉林省吉林市人，博士研究生，主要研究方向: 軟件錯誤定位、測試用例約簡;

蘇小紅(1966-)，女，黑龍江哈爾濱人，博士，教授，博士生導師，主要研究方向: 軟件缺陷檢測、軟件錯誤定位;

王甜甜(1980-)，女，遼寧丹東人，博士，副教授，主要研究方向: 程序分析、軟件錯誤定位;

馬培軍(1963-)，男，山東濰坊人，博士，教授，博士生導師，主要研究方向: 軟件工程、智能信息處理與信息融合。

摘要：在整個軟件開發(fā)周期中，軟件測試占軟件開發(fā)和維護成本的一半以上，而軟件錯誤定位是一個最困難，最耗時的任務。錯誤定位技術以定位軟件中的錯誤代碼為目的，通過在待測程序上運行合適的測試用例的基礎上，分析并定位錯誤語句。由于錯誤定位的精度高度依賴于選擇的測試用例，測試用例的數量和質量是決定錯誤定位的成本和有效性的關鍵因素，因此，面向錯誤定位選擇有效的測試用例，不僅有助于分析軟件錯誤產生的原因，還能極大地提高軟件錯誤定位的效率。首先對面向錯誤定位的測試用例約簡方法進行了分類，并對各類測試用例約簡方法進行了分析和總結，進而指出了其中存在的問題和未來的研究方向。

關鍵詞：軟件測試； 錯誤定位； 測試用例約簡

中圖分類號：TP311.5文獻標識碼：A文章編號：2095-2163（2014）03-0039-03

A Survey of Test Cases Reduction Approach Oriented to Software Fault Localization

GONG Dandan，SU Xiaohong，WANG Tiantian，MA Peijun

(School of Computer Science and Technology，Harbin Institute of Technology，Harbin 150001，China)

Abstract：Software testing run through the entire software development cycle，which consumes more than 50% of the development and maintenance effort.Fault localization is the most difficult and time-consuming task.Aimed at locating faults in software，fault-localization approach locates faults by running suitable test cases.The effectiveness of fault localization highly depends on the test cases，and the quantity and quality of the test cases are to demine the cost and effectiveness of fault localization.Thus，selecting suitable test cases is helpful to understanding why a faulty statement cause failure and improving the efficient of fault localization.In this paper，the test cases reduction approach oriented to fault localization is classified，and the different methods of test cases reduction approach are analyzed and summarized.After that，the paper points out the existing problems and the future research direction.

Key words：Software Testing; Fault Localization; Test Cases Reduction

0引言

計算機軟件正廣泛應用于經濟、軍事、商業(yè)等各個領域中，對其可靠性問題的研究也日益得到了人們的廣泛重視。保證軟件高可靠性已成為系統(tǒng)開發(fā)和維護工作中不可或缺的一個重要方面。隨著軟件規(guī)模越來越大、邏輯越來越復雜，對軟件可靠性的要求也日漸提高。然而，軟件并不是如人們預期般總能可靠地運行，影響軟件可靠性的一個主要因素就是軟件中潛在的錯誤，這些潛在的軟件錯誤極有可能對計算機應用系統(tǒng)帶來不利影響。在此背景下，軟件錯誤自動定位的目的就是通過執(zhí)行程序源代碼，分析程序運行過程中的運行時狀態(tài)，檢測程序中的異常情況，并將其獨立出來作為需要進一步調試的可疑代碼，從而將與軟件錯誤無關的代碼自動過濾掉，縮小錯誤代碼的搜索范圍，輔助開發(fā)人員快速有效地定位軟件錯誤。

錯誤定位技術以定位軟件中的錯誤代碼為目的，可通過在待測程序上運行合適的測試用例，進而分析并定位錯誤語句。因此，錯誤定位的精度要更多地依賴于所執(zhí)行的測試用例的質量。相應地，制定合適的測試用例約簡方法，得到適合定位程序錯誤的測試用例的集合，已經成為亟需解決的問題。

本文在介紹測試用例的基礎上，對面向錯誤定位的測試用例約簡方法進行了分類，并對各類測試用例約簡方法進行了介紹，最后對現有的測試用例約簡方法進行了分析和總結。

1面向軟件錯誤定位的測試用例約簡方法概述

目前，關于測試用例的研究大多用于軟件測試\\[1-2\\]，該方法首先在被測程序上執(zhí)行測試用例，分析被測程序的動態(tài)行為和運行結果，由此而發(fā)現程序錯誤或功能缺陷，追求的目標是測試的充分性，因此，軟件測試所使用的測試用例的集合一般都會比較大。但是該測試用例的集合中，很大一部分測試用例對錯誤定位的貢獻不大，甚至一些冗余或偶然正確的測試用例還會降低錯誤定位的精度和效率。針對這一問題，很多學者提出了不同的測試用例約簡方法，并進一步研究測試用例的約簡對錯誤定位精度的影響。

測試用例約簡是指在原測試用例的集合基礎上，根據不同的測試需求，采用相應的約簡策略，刪除與測試需求無關的測試用例。目前，測試用例約簡的研究大多面向軟件測試，而用于錯誤定位的測試用例約簡方法的研究較少。在研究面向錯誤定位的測試用例約簡方法\\[7-12\\]中，學者們的研究對象主要是程序在執(zhí)行過程中的程序譜\\[13\\]信息，即根據程序運行測試用例時的語句覆蓋情況進行分析，據此再進行測試用例的約簡。

2面向軟件錯誤定位的測試用例約簡方法分類

面向錯誤定位的測試用例約簡方法主要分為基于語句覆蓋的測試用例約簡方法、基于語句向量的測試用例約簡方法和突出考慮錯誤測試用例對錯誤定位影響的測試用例約簡方法。下面對這三種約簡方法逐一地展開分析。

第3期龔丹丹，等：面向軟件錯誤定位的測試用例約簡技術綜述智能計算機與應用第4卷 2.1基于語句覆蓋的測試用例約簡方法

該類方法主要目的是保證各語句在約簡后的測試用例的集合中皆被執(zhí)行。即在原測試用例集合的基礎上，制訂不同的策略，選擇部分測試用例，最終達到各語句皆被執(zhí)行的目的。通常，基于語句覆蓋的測試用例約簡方法得到的約簡后的測試用例數目較少，但與未約簡的測試用例的集合相比，約簡后的測試用例的集合很難提高錯誤定位的精度。

下面舉例說明基于語句覆蓋的測試用例約簡方法。圖1為實例程序mid()和所執(zhí)行的測試用例的集合{t1，t2，t3，t4，t5，t6，t7，t8}。該實例程序mid()已廣泛應用于錯誤定位和測試用例約簡方法中，以驗證其方法的有效性。其中，程序mid()的功能為，輸入三個整數，輸出三個整數的中間值。程序的第7行“m=y”為錯誤語句，正確語句應為“m=x”。程序的右側為8個測試用例t1～t8?！癖硎緢?zhí)行測試用例t時，第i條語句被執(zhí)行。由此可以看出，語句5僅被測試用例t2覆蓋，則約簡后的測試用例的集合應包含t2，語句11僅被t4覆蓋，則約簡后的測試用例的集合也應包含t4。對于語句6，同時被t1、t5、t7和t8覆蓋，各學者對此提出了不同的策略，在t1、t5、t7和t8中選取其一。按照以上方法，當所有語句皆被覆蓋時，即可得到最終約簡后的測試用例的集合。在語句覆蓋的測試用例約簡方法中，一些學者首先將正確測試用例和錯誤測試用例進行區(qū)分，再制訂相應的測試用例約簡策略，最終得到不同的測試用例的集合。

Baudry等\\[14\\]將相同測試用例所覆蓋的語句定義為動態(tài)基本塊，研究了動態(tài)基本塊的數量對錯誤定位精度的影響。結果表明錯誤定位的精度受動態(tài)基本塊數量的影響。

Zhang等\\[15\\]將相對冗余的思想應用于錯誤定位約簡方法中，研究成果表明，均衡語句覆蓋可以提高錯誤定位的精度。

2.2基于語句覆蓋的測試用例約簡方法

該方法主要將測試用例執(zhí)行后的覆蓋信息以向量為對象進行分析。例如，執(zhí)行測試用例t1的向量為<1，1，1，1，0，1，1，0，0，0，0，0，1>，執(zhí)行測試用例t2的向量為<1，1，1，1，1，0，0，0，0，0，0，0，1>，由此可以看出，t1的向量與t2的向量不同，則約簡后的測試用例的集合應同時包含t1和t2。t1、t7和t8所對應的向量相同，則可根據不同的策略，選擇其中之一。同時，也可以將正確測試用例和錯誤測試用例區(qū)別對待，再制訂相應的測試用例約簡策略，最終得到不同的測試用例的集合。

mid() {

int x ，y ，z ，m ;測試用例t1t2t3t4t5t6t7t83，3，51，2，33，2，15，5，55，3，47，5，42，1，34，3，51: read ( x，y，z ) ;●●●●●●●●2:m=z;●●●●●●●●3:if(yy)●●●10:m=y;●●11:else if (x>z )●12:m=x;13:printf(m);●●●●●●●●}Pass / Fail StatusPPPPPPFF圖1實例程序及測試用例

Fig.1Example program and its test cases

Yu\\[16\\]等在語句向量的基礎上，將相對冗余思想用于測試用例約簡，并將結果與基于語句覆蓋的測試用例約簡方法相對比。實驗結果證明，與基于語句覆蓋的測試用例約簡方法相比，基于語句向量的測試用例約簡方法刪除了較少的測試用例，但約簡后的測試用例更有利于錯誤定位。

2.3突出考慮錯誤測試用例對錯誤定位影響的測試用例約簡方法該類方法主要目的是保證各語句在約簡后的測試用例的集合中皆可得到執(zhí)行。即在原測試用例的集合的基礎上，制訂不同的策略，選擇部分測試用例，最終達到各語句皆可執(zhí)行的目的。通常，基于語句覆蓋的測試用例約簡方法得到的約簡后的測試用例數目較少，但與未約簡的測試用例的集合相比，約簡后的測試用例的集合很難提高錯誤定位的精度。

在以上兩類測試用例約簡方法中，盡管一些學者提出了將正確測試用例和錯誤測試用例分類，但并未突出考慮錯誤測試用例對錯誤定位的影響。而研究表明，與正確測試用例相比，錯誤測試用例更有助于錯誤定位。

Wang\\[18\\]等提出根據錯誤路徑生成最相似的正確路徑，但算法的復雜度很高并只能生成一條成功路徑且對賦值錯誤的定位不太敏感。

Chen\\[19\\]等研究了根據測試需求直接生成測試用例集合的方法。文中指出，測試用例需求的好壞，直接影響所生成的測試用例的質量。在構造需求關系圖的基礎上，首先生成測試用例需求，并在此基礎上進行測試需求的優(yōu)化，由此即構造出與測試需求相關的測試用例。

3結束語

目前的測試用例約簡方法，都只研究了程序運行時的語句覆蓋情況，忽略了程序運行時的具體執(zhí)行路徑信息，因為具有相同語句覆蓋的測試用例所對應的執(zhí)行路徑未必相同，而且約簡測試用例時對錯誤定位的需求考慮并不充分，因此，約簡后的測試用例對錯誤定位的精度沒有明顯提高，甚至某些測試用例選擇方法還會降低錯誤定位的精度。如果能夠在分析程序執(zhí)行路徑基礎上，面向錯誤定位需求約簡出對錯誤定位有效的測試用例，那么不僅能降低錯誤定位的復雜度，而且也必將有助于提高錯誤定位的精度。

參考文獻：

\\[1\\]VESSEY I.Expertise in debugging computer programs\\[J\\].International Journal of Man-Machine Studies: A Process Analysis，1985，23(5):459-494.

\\[2\\]WAGNER D.A first step towards automated detection of buffer overrun vulnerabilities\\[C\\]// Proc.7th Network and Distributed System Security Symp，Internet Soc，2002: 3-17.

\\[3\\]ALEXANDRE P，RUI A，ANDRE R.A dynamic code coverage approach to maximize fault localization efficiency\\[J\\].Journal of Systems and Software，2014:18-28.

\\[4\\]JARED D D，RICHARD J E，WILLIAM F P.Systematic bug finding and fault localization enhanced with input data tracking\\[J\\].Computer Security，2013，32:130-157.

\\[5\\]MAO X G，YAN L，DAI Z Y，et al.Slice-based statistical fault localization\\[J\\].Journal of Systems and Software，2014，89:51-62.

\\[6\\]FEYZULLAH K，HASAN S，RRI A.Spectrum-based fault localization for diagnosing concurrency faults\\[J\\].Testing Software and Systems，2013，8254:239-254.

\\[7\\]GROCE A．Error explanation with distance metrics\\[C\\]//Tools and Algorithms for the Construction and Analysis of Systems(TACAS)，Barcelona，Spain，March/April，2004:108-122.

\\[8\\]CHAKI S，GROCE A，STRICHMAN O.Explaining abstract counterexamples\\[C\\]//Foundations of Software Engineering.Newport Beach，California，November，2004:73-82.

\\[9\\]JEFFREY D，GUPTA N.Improving fault detection capability by selectively retaining test cases during test suite reduction\\[J\\].IEEE Trans.Softw.Eng.，2007，33 (2):108-123.

\\[10\\]SHEN Shengyu，QIN Ying，LI Sikun.Localizing errors in counterexample with iteratively witness searching\\[C\\]//the Proceedings of 2nd International Conference on Automated Technology for Verification and Analysis，Taipei，Taiwan，2004:56-469.

\\[11\\]葉俊民，張濤，董威，等.基于程序靜態(tài)分析和故障樹的軟件故障檢測\\[J\\].計算機工程，2008，34(16):75-79.

\\[12\\]呂春燕.用于程序錯誤定位的運行路徑聚類方法\\[D\\].大連海事大學，2011.6.

\\[13\\] REPS T，BALL T，DAS M，et al．The use of program profiling for software maintenance with applications to the year 2000 problem\\[C\\]//Proceedings of the 6th European Software Engineering Conference Held Jointly with the 5th ACM SIGSoFT International Symposium on Foundations of SoftwareEngineering(ESEC’97/FSE-5).Zurich，Switzerland，1997:432-449.

\\[14\\] BAUDREY B，FLEUREY F，TRAON Y L.Improving test suites for efficient fault localization\\[C\\]//International Conference on Software Engineering，Shanghai，China，May 2006: 82-91.

\\[15\\] ZHANG X，GU Q，CHEN X，et al.A study of relative redundancy in test-suite reduction while retaining or improving fault-localization effectiveness.SAC，2010:2229-2236.

\\[16\\] SANTELICES R，JONES J A，YU Yanbing，et al.Lightweight fault-localization using multiple coverage types\\[C\\]//Proceedings of the 31st International Conference on Software Engineering，May 16-24，2009:56-66.

\\[18\\] WANG Tao，ROYCHOUDHURY A.Automated Path Generation for Software Fault Localization，2005:347-351.

\\[19\\] CHEN Z，XU B，ZHANG X，et al.A novel approach for test suite reduction based on requirement relation contraction.SAC，2008:390-394.