基于距离的软件故障分析方法

    潘建生+程实+文万志

    

    

    

    摘 要：鉴于多故障之间的干扰，提出一种基于距离的软件故障分析方法，这种方法首先计算测试轨迹之间的欧式距离，然后选取距离最大的两个失效测试，基于不同的失效测试进行故障分析以提高故障定位效率，文章通过一个两故障程序实例说明了这种方法的有效性。

    关键词：软件；距离；故障

    软件在开发和维护过程中不可避免地会引入故障，为了分析定位这些故障，软件人员经常需要花费大量的时间和费用。因此，软件研究者们一直在寻找高效的故障分析定位方法，其中最常见的分析定位方法是基于程序覆盖的方法，如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