基于距離的軟件故障分析方法

潘建生+程實+文萬志

摘 要：鑒于多故障之間的干擾，提出一種基于距離的軟件故障分析方法，這種方法首先計算測試軌跡之間的歐式距離，然后選取距離最大的兩個失效測試，基于不同的失效測試進行故障分析以提高故障定位效率，文章通過一個兩故障程序實例說明了這種方法的有效性。

關鍵詞：軟件；距離；故障

軟件在開發和維護過程中不可避免地會引入故障，為了分析定位這些故障，軟件人員經常需要花費大量的時間和費用。因此，軟件研究者們一直在尋找高效的故障分析定位方法，其中最常見的分析定位方法是基于程序覆蓋的方法，如Tarantula方法[1]、程序切片方法[2]等。其基本原理是通過的失效測試越多、成功測試越少的程序元素，出現故障的可能性越大。然而在實際的程序中，程序故障通常非單一故障，基于前述基本原理進行故障分析的有效性降低。本文提出的基于距離的軟件故障分析方法致力于在一定程度上分解多故障，從而提高故障分析的有效性。

1 多故障實例

文中基于一個簡單的兩故障實例來說明本文方法的有效性，實例如圖1所示。

圖1是一個簡單的兩故障程序片段，程序功能是如果a和b中最小值大于等于0輸出1，小于0輸出﹣1。其中，語句4和10是故障語句。不失一般性，我們考慮所有分支所有可能的輸出結果，設輸入（a，b）的值依次為（10，2），（10，-2），（-2，-10），（2，10），（2，-10），（-10，-2），其執行軌跡與執行結果如表1所示。

根據傳統的測試方式，以Tarantula為例，其可疑度值如表中最后一行所示，根據可疑度從大到小，順序語句從前到后的定位順序，定位程序中故障的語句檢查次序是9→10→1→2→3→4→5→6→7→11→8。完全定位程序中的兩個故障所需要的Wasted_effort（即所需遍歷的非故障元素個數）是4。顯然，在這個簡單例子中，傳統的方法分析定位效率是低下的。

2 基于距離的軟件故障分析方法

基于距離的軟件故障分析方法通過度量失效測試之間的距離分離軟件程序故障，以提高故障分析效率，其基本思想是距離越遠的測試失效由不同的故障（或故障組合）引起的概率越大，即如果失效測試T1與測試T2是距離較遠的兩個測試，令Trace（T）為測試T的測試覆蓋元素集合，則集合Trace（T1）-Trace（T2）和Trace（T2）-Trace（T1）包含兩種不同的故障（或故障組合）元素的概率較大。因此，將軟件程序分為兩組Trace（T1）-Trace（T2）及Trace（T2）-Trace（T1），兩組分別進行約減以提高分析定位故障的效率。

進一步地，如果失效測試T1與成功測試T3距離較近，且Trace（T1）≠Trace（T3），則Trace（T1）-Trace（T3）包含故障元素的可能性較大。因此，Trace（T1）-Trace（T2） -Trace（T3）可進一步約減故障分析范圍。同理，如果失效測試T2與成功測試T4距離較近，且Trace（T2）≠Trace（T4），Trace（T2）-Trace（T1） -Trace（T4）可進一步約減故障分析范圍。

（1）中，m是程序所含程序元素數目，tir和tjr分別表示測試Ti和Tj的通過程序元素r的情況，如果通過，值為1；否則，值為0。

3 實例分析

基于上節的算法，針對表1中實例，計算各測試距離值如表2所示。

由于失效測試為T2，T3，T5，T6，取距離最大的兩失效測試T2和T5或者T2和T6，按序選取第一對T2和T5，并置d25=﹣1。選取與T2距離不等0的最近的成功測試為T4（T1與T2的距離為0，具有不可區分性，故不選取距離為0的測試），選取與T5距離不等0的最近的成功測試T4，則Trace（T2）-Trace（T5）-Trace（T4）={4}，Trace（T5）-Trace（T2）-Trace（T4）={9，10}。根據軟件故障分析算法，依次檢測語句4，9，10，成功定位故障，其wasted_effort=1。效率遠高于經典的故障分析定位算法Tarantula，其wasted_effort 在第一節中已定義，值為4。

4 結語

文中提出了一種基于距離的多故障分析方法，其核心思想是通過距離度量，盡可能地將多個故障分離開來分別進行故障分析以提高故障分析定位的效率，文中通過實例驗證了這種方法。未來，我們將在實際應用的軟件程序中擴展深化本文思想，通過距離度量將不同類的故障進行聚類，降低故障數目來提高故障分析定位效率。

基金項目：江蘇省現代教育技術項目；項目編號：2017-R-54131。南通大學杏林學院科研基金項目；項目編號：2014K110。

作者簡介：潘建生（1980— ），男，江蘇南通，碩士，講師；研究方向：計算機應用。

[參考文獻]

[1]JONES JA，HARROLD MJ. Empirical evaluation of the tarantula automatic fault localization technique[C].Long Beach：Proceedings of the 20th IEEE/ACM International Conference on Automated Software Engineering，2005：273-282.

[2]WONG E，QI Y. Effective program debugging based on execution slices and inter-block data dependency[J].Journal of Systems and Software，2006（7）：891-903.

[3]HAN J，KAMBER M，PEI J. Data mining： concepts and techniques[J].Data Mining Concepts Models Methods & Algorithms Second Edition，2011（4）：1-18.

Abstract： In view of the interference between multiple faults， a distance based software fault analysis method is proposed. This method first calculates the Euclidean Distance between test trajectories， and then selects two failure tests with the largest distance， and makes fault analysis based on different failure tests to improve the efficiency of fault location. The effectiveness of this method is illustrated by an example of a two failure program in this paper.

Key words： software； distance； fault