Progress Report 2018.07.01
ICSE'18 Alessandro Orso的团队（佐治亚理工）
Alessandro Orso之前做了一些bug复现的工作，包括了我读的第一篇也是bug复现相关研究里大家都会提及的BugRedux。他们组的主要工作是bug复现（2015年以前）、故障定位（一直在做）、测试样例生成（一直在做）
研究背景：在故障定位领域，有很多不同的方法，其中statistical fault localization是其中一类比较成功的方法。（之前Lushan那篇用statistical debug来定位性能bug的文章也是借鉴了这一类方法）。statistical fault localization是通过一组正确的和一组会引发错误的输入，分别执行某段程序，然后对得到的执行路径进行统计分析，进而得到从统计上来讲只会在错误执行中才会被执行的语句，然后将这些语句按“可疑度”排序报给开发者。
历史地位：当前，这种方法最终提供给开发者的是可疑语句的列表，但是作者认为这个列表并不能很好地让开发者明白和理解bug，换句话说，开发者只看见一个单独的语句而没有上下文信息，他也很难断定是不是一段代码具有bug。例如下面的例子：
#!c++
Integer[] elems;
int numElems;
pop(){
numElems--;
System.out.print("pop");
}
函数pop实现弹栈操作，如果现在我告诉开发者 “numElems--;” 这条语句是可疑的，但乍看上去，开发者不一定能判断出是不是真的有问题。这段代码真正的问题是，应该先检查numElems是否为0（即栈是否为空）。因此作者提出，要告诉开发者更多的上下文信息，具体以怎样的形式告诉呢？对于这个例子，就应该告诉开发者：pop这个函数输入为numElems=0时，执行完函数，numElems=-1，其中可疑的语句是numElems--。而且，为了使得结果更加精确，作者不期望工具跑一次，就能找到rootcause（因为哪怕是开发者都不一定能一下就找到root cause）。而是跑一次，告诉开发者一个可疑语句（而不是一个list）及其上下文，开发者判断这个语句是不是真的有问题，如果是真的有问题，那么debug就结束了。而如果不是真的有问题，则会给工具一个feedback，然后工具再算出一个可疑语句及其上下文让开发者判断。如此反复，直到开发者认为工具所提供的语句是真的bug所在。
方法： 上述过程实际上就是一个典型的开发者debug的过程：发现一个failure后，开发者会首先猜测一个root cause，然后他就去检查程序出错前的执行路径、数据变化等，看看是不是可以印证他对rootcause的猜测，如果印证失败，则至少会“learn something”，然后再进行猜测，再重复。作者的工具就是把这个workflow中的部分给自动化了，但还是需要人的知识，因此作者说工具只是help human，而不是replace human。那么自动化的是哪些部分呢？首先可以自动化的就是帮助开发者“猜测root cause”而且猜测出来的root cause以“可疑语句+上下文”的形式告诉开发者。再就让开发者的反馈指导下一次工具对rootcause的“猜测”。
对于前一部分的自动化如何做：
上面提到的“可疑语句+上下文”是什么呢？以上面例子为例：{"可疑语句"=“numElemes--;”, "上下文"="pop()函数开始时，numElems=0，pop()函数结束时，numElems=-1"}，开发者看到这个信息，会很容易发现这就是bug所在，然后debug结束。那么工具是如何算出来可疑语句是numElems--;这句话呢？作者使用的是前人都用的经典的statistical fault localization方法，文章就没有对此详细描述。上下文信息（实际上就是函数运行前后变量的值）是如何得到的呢？这个是比较容易的，因为statistical fault localization方法就默认了我有导致错误的test case，那么运行一下就知道一个函数运行前后变量的值了。
对于后一部分的自动化如何做：
开发者拿到{"可疑语句"=“numElemes--;”, "上下文"="pop()函数开始时，numElems=0，pop()函数结束时，numElems=-1"}之后，会进行标注，如果他认为这就是bug所在那么任务就完成了。如果他觉得不是bug所在，那么工具会自动添加一个测试样例，这个测试样例只调用了这个一个函数pop(),且调用前numElems=0，调用后numElems=-1。**并把这个测试样例算作正常运行的测试样例，而不是导致错误的测试样例。**这样一来，在下一轮迭代中，工具就会因为这个函数在正确的运行中执行了而使得计算出来的这个函数的可疑程度大大下降。而其他的可疑语句就会被报给开发者。
实验：作者在3个开源软件中人工注入了1807个bug，其中96%的都可以被查到，而且迭代次数最多10次。然后找了其中4个bug，让24个人分组一组用这个工具，一组不用，发现用了这个工具的发现bug用的时间明显短。
现在很多工作都有feedback的过程，引入feedback的原因主要是一些知识实在需要人的介入，而且人只需要给一点点指示就可以为工具提供更多的指导，这个迭代的过程会一点一点逼近真相。那么我的工作是不是也可以加入feedback，需要开发者给的提示可以是一些比较basic的指示，具体是什么初步感觉可以是“配置A 的调高导致性能有个分布为B的变化，开发者说-是正常的”。以及，我目前找到的有性能bug的配置比较少，目前有20+个，而且是bool、enum、int都有的，数量比较少，那么我能不能也注入一些性能bug，这部分工作我是完全没看到过，所以我觉得如果找到好的注入方法那么我觉得比较有意义。最简单的其实还是sleep[/facepalm]
##** Static Detection of Asymptotic Performance Bugs in Collection Traversals** ## PLDI'15
背景：这篇文章发表时，性能bug相关的研究还比较少，很具有代表性的Lushan的研究Inefficient Loop的那篇还没出。因此当时的背景就是功能bug测试的方法不能应用的性能领域，性能的测试缺少oracle。只不过，本文并不是给出了一个oracle，而是绕开了oracle的问题，研究inefficient pattern。更具体地说，本文就是研究循环语句中的重复计算问题，就是Lushan那篇InefficentLoop的子工作。
**历史地位：**本文和Todder（ICSE'13 Lushan）类似，只不过Todder是动态插桩，本文是纯静态分析，没有额外负载。其他工作的方法有的关注于配置引发的性能下降,非bug（X-ray）。但没有与本文重叠。
方法：如何定义循环中的重复计算？需要满足两个条件：1.某个列表类型的变量，在循环的每次迭代中，都被遍历了至少一次。2.这个变量在每次循环中，没有被改动过。换句话说，上述两个条件就描述了这样一个情况：如果一个列表不会被改动，那么相同的遍历操作只需要执行一次（比如询问‘a’是否在列表中）。然后就是pattern匹配工作。
实验：本文工具找到了9个java软件中的92个bug，其中72个是新的。作者修复后，取得了至少2.45倍的加速。由于本文研究的主要是小段代码的性能问题，因此，不需要对大规模代码进行整体分析。
到本周，已经测试和复现的结果如下： 实验结果（百度云提取码：uiii） 不设提取码感觉有点不安全