仅基于失败运行的错误定位

1、仅基于失败运行的错误定位背景介绍错误定位通常依赖成功与失败运行两方面，但成功运行通常易受巧合正确性的影响，并且现代软件自动产生大量关于失败运行的bug报告。仅基于失败运行的错误定位方法（简称FOnly）是一个有效的仅基于失败运行来错误定位的新技术。当错误程序的一次运行传递了一个错误时，可能是程序内部语句的原因。在运行中，通常也会执行其他程序的语句，这些语句可能将错误传播给其他的内部语句。如果这些语句产生了显著影响，就会导致失败的出现。一旦程序工程师发现失败的出现，就会调试、定位错误、弥补错误并确认移除了这一错误，然而，调试过程依旧很艰辛，错误定位也通常被认为是这之中最难的一部分。最近亚洲的研究

2、在程序错误定位自动化上有了显著突破，这些技术通常是基于成功运行与失败运行共同实现的。然而，这之中的成功运行可能激活了错误但不至于引起失败运行的出现。更进一步讲，很多系统如今能自动检测失败并产出大量有用的关于失败运行的bug报告。基于此，我们提出FOnly，一个仅基于失败运行数据定位错误的革命性技术。技术介绍在过去20年，有很多新颖的错误定位技术出现，为了比较这些技术，我们将他们分类，分类依据是研发时是否使用错误/成功运行数据，并列出他们使用这些运行的数目。我们仅列出在源代码中定位错误的技术，包含了诸如delta debugging,semi-proving这些仅揭露导致程序失败的可疑输入范围的

3、技术，也有检测或制止失败出现的技术如Eraser。下表便是这些数据的详细信息，最左两列是失败/成功运行数，第三列列出了这一原理早年的代表性项目，最后一列是与亚洲一流学者相关的最近提出的项目。使用成功运行的隐患是可能出现激活了错误却没有引发失败出现的情况，这就是巧合正确性。上表下面三个技术就存在这样的隐患，早先的原理诸如chislice,nearest neighbor ,Tarantula也不可靠如若巧合正确情况出现。最近亚洲的研究就在解决这一问题。CP是一种通过计算运行中基本块转变为错误块的频率并通过程序控制流图中的相似系数测量后向传播错误失败关联的技术，这样的计算结果是传递错误的代码有较高

4、的秩。Hong Cheng和他的同事在C程序中通过分析bug报告中的最具识别图模式来定位错误。Saha与其合作者在ABAP语言的SAP系统中定位错误切片，其方法是从失败运行中得到程序环，构建数据库需要独立切片作为起始点，在将单独的错误运行划分给这些切片，他们之中存在正确数据记录并被视为成功运行，然而在成功运行中依旧蕴含着巧合正确性。另一种方法解决巧合正确性影响的是完全放弃正确运行的使用。Findbug这种数据分析工具是同时不使用成功与失败运行的，他在程序运行时产生报警，再通过多次运行来确认警报点。动态切片技术是在只有一个错误运行的情况下生成所需的语句切片集。与Tarantula类似，Ochia

5、i这类调试工具也能不使用成功运行来定位，但是这种野蛮的方法是非常没有效率的。据目前所知，使用一个或多个失败运行而不使用成功运行来定位错误的研究是非常少的，在过去这种方法被认为是不现实的是因为任何程序编译时候都是希望出现0错误，但是由于目前新兴的动态bug监测器能快速监听运行过程并给出大量错误报告，这种方法就不再是不可行的了。因为现代软件的内置工具通常可以监测失败运行并汇报出来，软件调试者就会收到大量错误报告，然而生成与其数目相等的成功运行来进行定位分析又会花费大量时间，这就促使了仅用失败运行来定位错误的技术的出现。我们基于以下概念假设提出FOnly技术：若已知一个错误程序的一次特定运行，若该运

6、行通过错误程序实体（语句）次数越多，就越可能导致失败运行的出现。对于另一个语句而言，若上述趋势在错误运行中没有被发现，则后者的错误几率就相对小些。趋势估计，是目前非常流行的技术之一，也是我们FOnly的核心。这一概念的简单阐释是使用最小二乘方法找到回归线，这样的线就能揭露出给定案例的趋势。在统计不同失败运行通过同一语句的次数的基础上， FOnly可以进一步找到拟合误差最小化的回归线，然后使用回归线的斜率和拟合误差值计算信噪比，这一数据代表了对语句错误关联性的估计。高信噪比的语句被视为有更高的错误相关性。我们使用一个例子来证明Fonly如何应用错误假设来实现趋势估计从而定位错误：图1a是两个代码

7、段，上面的代码段包含了if语句和变量检测及对应功能，若布尔表达式是真，则函数addstr修改变量dest。否则不改变它的值，下面的代码实现了输出功能。若此时在上面的代码段中L115开始的if语句错误（遗失L116），那么产生错误后的代码就更有可能使表达式为真，所以L121执行几率也就相应增加。因此，dest就可能有了错误的值。除非isalnum函数返回假值，L115的错误都是与原有正确结果不同的。一般来讲静态预测字串内容是困难的，所以错误语句产生错误的概率我们很难知道。我们在SIR提供的5542个测试用例上执行错误程序，对每条语句，我们记录每次运行中执行该语句的次数为c。对于一次执行计数中的每

8、个值C0，我们记录编号N（c）的运行有一个计数c=c0，并计算其失败率，也就是N（c）次运行中失败部分的比率。通过将L121，L497，L500与L115的距离进行比较，我们可以知道L121距离错误语句最近，而它也确实是最可疑的，因为可以通过它修改变量的值。同时我们检查代码以保证错误与L497，L500无关。对于上述4句话，我们绘制关于其失败率与执行计数的图，并使用最小二乘法进行回归线线性拟合。其结果如图1b所示。可以看出，随着执行计数的增加，L115与L121的失败率增加明显快于L497与L500，所以错误无关的语句也就有相对小的斜率，对于L500而言，其与错误语句最不相关，所以变化也最不明

9、显。然而，这个简单的实例并没有考虑线性拟合误差，这一误差需要成功运行与失败运行两方面的信息，在接下来的章节里，我们的工具会处理这些问题。FONLY如何工作设想一个程序是由一系列程序实体（诸如语句）来构建的，给定一些程序的执行结果，将其定义为程序运行集。Fonly通过比较每个程序实体的可疑性来进行错误定位，而可疑性是通过运行集中的失败趋势来度量的。下图（图2）显示了其四个阶段，接下来我们依次介绍。分割阶段：给定程序实体（诸如语句）,Fonly划分程序运行集为不相交的分割，每个分割包含了所有经过同一实体相同次数（假定c次）的运行记录，之后计算每个分割中失败运行的比率，记为失败率F(c).校准阶段：

10、对于一个给定的实体s，F(0)这一分割的失败率，既没有一次运行经过了s。如果分割中所有运行都没有经过s，后者不应与任何失败相关联，若F(0)此时非0，则应置为0，同样的，其他分割可能也对s进行了非0赋值，基于此，Fonly提出了校准失败率G(c)=F(c)-F(0)，从而对经过程序实体s正好c次的运行导致失败的几率进行更准确的度量。线性拟合阶段：基于上一阶段，Fonly在线性拟合阶段对每一个程序实体进行失败趋势估计。对于任何给定的实体，通过给每个c配对相应的G(c)，Fonly在2D空间创建一个点(c,G(c).对于一个错误相关的实体，G(c)是关于c的离散且单调递增的函数。在2D空间中Fon

11、ly使用线性拟合对程序实体进行错误相关性度量。这里有两种方法度量经过s正好c次没有引发失败的可能性：第一种是直接使用G(c)并设置可能性为1-G(c)；第二种是使用执行实体s直至c次都没有引发任何失败的可能性。这个可能性表达式是： ，这里p表示运行一次而导致失败的可能性。将二者结合为公式：f(x)能被展开为无穷级数： ，这里 表示f(x)在0点的i阶导数。所以我们推导校准正确率可近似表达为：从而简化为G(c)=l*c.所以，巧合正确率是由过(0,G(0)点且斜率为l的直线来表示的。Fonly使用最小二乘分析将线性拟合误差最小化。给定程序实体，斜率l可以表示为： 标准差可以表示为： 其中D是所有

12、可能经过实体的运行次数的集合。然而，经过实体的运行次数可能各不相同，所以在比较前我们应该将每个特定实体的l标准化为： ，这里 cmax 表示程序运行可能经过特定实体的最大可能次数。为了在同时存在成功运行与失败运行的情况下度量每个实体的错误相关性，Fonly计算秩数R，它等同于信噪比并以标准化后的l和标准差来定义：秩越大，程序实体错误相关性越高。秩的值域是，若程序实体s没有样本点，没有经过s的失败运行，则秩R为-，其意思是s具有最小可疑性；若实体s只有一个样本点，斜率l未定义，秩R定为0；若标准差为0，秩无法直接计算，此时，若经过s的失败数为0，则为-，否则就是其上限+ 。 消除阶段：与其他相关

13、研究不同，Fonly添加了一个阶段消除在计算程序实体错误相关性时对成功运行次数的依赖。在这一阶段，它使用了仅基于失败运行的公式。对于任何程序实体s，N(c)表示程序运行次数，这之中每个运行都正好经过s实体c次。Fonly计算与c值无关的平均运行次数 ，它替代了每个不同的N(c)从而计算得到平均秩 这是与失败运行相关而与成功运行无关的。其中Y(c)是正好经过实体c次的运行中的失败运行次数。当然，若成功运行集可靠，消除阶段就是可选择的了。实验分析为了验证Fonly的效果，我们使用SIR中的错误程序来进行相关研究，下表2就是实验数据。在每个程序版本中使用1到3个错误来模拟单一/多错误情况，结果是18

14、6个单错误版本，20个多错误版本。为了比较Fonly的性能，我们将它与Tarantula,Ochiai,Jaccard,与统计定位bug技术（SBI）因为这些技术都是在失败与成功运行都存在的情况下研发的，所以我们先将测试库中的每个程序版本在上述测试工具中都运行一遍，之后再进行仅失败情况的测试。依据之前的研究，我们定位错误的效率通过找到错误语句时检查语句的百分比来度量。上图3展示了在失败/成功运行情况与仅失败情况的结果，在每个图中，x轴都代表着执行代码的百分比，y轴代表定位出错误占总错误的百分比。如图3a所示当执行代码在10%到100%之间，Fonly处于上峰或至少能与其他齐平，我们选取20%时

15、，Fonly此时检测出了86%的错误，而其余四个分别是77%到79%。然而在最开始的5%我们的方法就不如其他方法那么有效了。当没有正确运行时，除了SBI的另三种方法效率相同，SBI不做比较是因为此时它的公式给所有执行过的语句相同的秩从而失去了错误定位能力。如图，在这一情况下Fonly一直都比其他方法优秀或至少战平诸如10%时其检查出来57%的错误，而其他的3种方法只有37%。上图中，在执行50%的代码前，它的效率总是高于其他方法的，而过了50%它就可以检测出全部错误。所以综上，Fonly在失败-成功运行情况下与其他方法具有可比性，而在仅有失败运行的情况下，它的性能比其他方法有显著提高。上图显示

16、了当程序语句作为诊断对象时，Fonly具有其错误定位能力。当成功运行不出现或不可靠时，它的性能没有像其他方法一样衰减，尽管在失败-成功运行下的前5%时Fonly没有很好的运行效果，但这也是因为在这种情况下能被使用的失败运行次数过少，从而造成Fonly没有充分的样本点来进行趋势估计。一个直接的提高Fonly效率的方法是在数据块级别应用它，因为同一块内的语句大多有相同的秩，这就保证了精度不会损失；对粗粒度也就是函数层面使用Fonly也能得到很好的效率，但这样的结果是只能得到少量精确的错误定位结果。为了验证程序大小与错误数量对Fonly效率的影响，我们将程序依据其大小与包含单一或多个错误版本的情况进行分类。如上图4所示，在失败-成功运行与仅失败运行的情况下，它对于上千行代码的中型程序的表现都要比成百行的小型程序好在比较单一错误的