Progress Report 2018.03.25
ICSE 17 Nier
-
这篇文章针对性能测试提出了一种新的方法。在性能测试中最challenge的问题是缺少oracles—不像功能测试中，测出bug时会crash或hang，并且报出日志等信息。而性能测试很难断定一次测试是不是有性能问题。在功能测试中，有一种测试方法叫Metamorphic Testing，适用于缺少oracle的情况。例如测试sin(x)是否计算准确，我们无法知道sin(1.2)=x.xx是否准确，但通过比较sin(π-1.2)与sin(1.2)之间的误差，就可以大致推断准确度。最近一篇关于Metamorphic Testing的综述表明，相关的120多篇paper里，没有一篇是把这种Metamorphic Testing方法用于性能测试的。那么这种方法是否能解决性能测试缺少oracle的问题呢？作者在本文中给了几个例子，提出了几点可能的研究点，也提出了几点挑战。
-
挑战用例子说明：现在有一个被测函数是merge(L1, L2)，功能是合并两个list。T(merge(L1,L2))表示合并L1和L2的时间。那么T(merge(L1, L2)) ≤ T(merge(L1 ∪ L3, L2 ∪ L4))是一个比较合理的关系式。如果找到不满足上述等式的L1 L2 L3 L4则暴露了性能问题并找到了相应地测试样例（复现成功）。
-
挑战1：关系式的确定。在上述例子中，关系式T(merge(L1, L2)) ≤ T(merge(L1 ∪ L3, L2 ∪ L4))的确定是十分依靠domain knowledge的，想要在软件under test阶段找到这样一个关系式势必要对已有的性能故障进行建模。但是Metamorphic Testing的初衷就是不需要理解性能bug的domain knowledge（如监测CPU、MEM，并对之建模）。除非能通过不需要或者需要很少domain knowledge的方法构建关系式。
-
挑战2：假阳性和假阴性。有些bug无法用这种关系式来表现，例如在某软件中，执行A操作1次用时200ms，执行10次用时2h。此时简单的构建T(A(1))≤T(A(20))则会导致假阴性。再比如，有些性能bug对于任何输入都会发生，那么这种方法也会失效。假阳性的意思是说性能这个东西是不确定性的，某次执行因为什么原因T(merge(L1, L2)) 就是比T(merge(L1 ∪ L3, L2 ∪ L4))要长，但是merge函数其实没有bug。对这种情况，我们可以假设是小概率的，因此多次测试+假设检验或者给不等号加个阈值，要大于一定程度才算。这些都涉及到更细致的模型，作者没有对实际的bug进行检验是否可行。对于这类挑战，我认为还是需要很多领域知识，要对每种类型的性能问题分情况讨论。
**想法:**这篇文章的想法比较新颖，是针对性能做测试，而下一篇是针对性能进行debug。看了这两篇后，我有了一些想法。
OOPSLA 14
-
什么是Statistical Debugging：“Specifically, statistical debugging collects program predicates, such as whether a branch is taken, during both success runs and failure runs, and then uses statistical models to automatically identify predicates that are most correlated with a failure, referred to as failure predictors.”
-
其实上一篇文章的思想在前一年的这篇文章中已经有了。先说这篇文章，作者发现，在用户上报的65个（5个软件）性能bug中，57个都是通过对比的方法来描述性能bug的，也就是说，用户会提供两组有差异输入（同功能不同size；同输入不同配置；两个类似的操作；在同软件不同版软件的结果；两个不同软件的结果）。基于这个supporting detail，作者认为，用于功能性debug的statistical debugging方法可以拿过来用。而且在性能bugreport中，用户提供的输入特征正好满足statistical debugging所需的输入特征—输入相似，但表现不同。反而在功能debug中通常没有这样一对儿输入，需要研究者帮助生成。因此，作者说“Our study shows that statistical debugging is a natural fit for diagnosing performance problems”。
-
这个方法不仅是新提出来的，而且也比前人的方法好。好在更加general，前人很多都是局限于某一领域。此外，前人工作X-ray，是站在用户角度，帮用户分析哪个配置或者输入导致了性能下降，这个不能解决根本性能问题。这就引发了我的想法4。
-
作者的工作主要是通过实验，比较了不同的Predicate design（5种）和不同的Statistical model design（2种）对于性能故障诊断的效果如何。实验发现分支类型的Predicate最能帮助诊断，而且能诊断出profiler诊断不出来的故障。
-
上一篇文章的思想实际上与这篇很相似，都是基于有差异的输入来观测是否出现了性能bug。只不过这篇文章是debug，上一篇是testing。我的想法1就是这条线上的。本文作者提出他们在做实验时有的bug容易根据用户描述的规则生成多组测试样例（好输入+坏输入），有的却比较难，因为用户也不知道怎么算好怎么算坏。所以生成针对性能的测试样例是有必要的。
想法1: test case生成似乎可以做。需要解决的问题：一是怎么生成、二是怎么更多地生成，因为一个可能不行，对于性能问题，测试样例更多才会使得问题更明确。怎么生成的问题一时不好回答。最近concolic testing很火，这种生成测试样例的方法是需要oracle的，性能bug有没有oracle。那么前一篇文章提的方法我觉得很可行，这组在IST18(B会)又发了一篇短的Performance Metamorphic Testing: A Proof of Concept。同样的主题，看起来他们组之后就会做实验了，我觉得是可以做的，因为传统的testcase生成方法因为oracle的问题不能用于性能诊断。只不过我可能要用一种和他们不同的方法了。看了一下Shan Lu最近的paper全是性能的…找不到下载，我看了一下题目，也和test case生成没什么关系：
想法2: 在这篇文章中作者提到一点：对于一般的function bug，已经有方法（有paper）可以通过profile聚类得到哪些是导致错误的测试样例，哪些是正常的。但对于性能bug来说，行吗？又有哪些新的挑战
想法3: 搞一个bug测试集行不行，囊括各种类型的bug。或者总结一下很多工具没有做很solid的实验，为什么，是不是因为当前的软件有什么局限，能不能解决，帮助研究者更好地进行实验？当然这个集合一定也都是真实系统中来的，不能手工制造。
**想法4:**和性能有关的配置项 =？ 容易导致性能问题的配置项（我看到这几篇论文中的实际的配置bug有些不一定能用静态的方法找出来），就算能找到容易导致性能问题的配置项，也还有一个问题：emse16yutingting那篇里说大部分配置bug最终都是改源码，很少改配置本身。那么我知道了性能bug和配置有关、并且知道了和哪个配置有关，知道这个不是目的，然后呢？下面这篇paper（LuShan）看题目只是自适应调整配置。。。
ICSE 15
-
文章题目中Non-Intrusive Fixes的意思是“修复这个性能bug带来的收益比带来的风险大而进行的修复”。我认为这个立意有点牵强：1.凭什么说某个修复的收益小于或者大于风险，怎么衡量？2.它毕竟是个性能bug，如果因为可能带来风险就不修复了，那算什么开发者？因此，我认为文章的这个立足点就是为了体现出本文所针对的这类性能bug比较有价值。
-
这篇文章针对循环冗余进行检查来提高代码效率。更确切地讲，就是对于一个循环，如果在中间某个位置加上if(condition)break;不影响结果，那么一定能提升性能。文章主题就是分析在哪些情况下可以加上这个语句。我认为这个不能算是一个bug，而是实现上的deficit，我想这也是题目叫performance problem而不是bug的原因。
想法: 实验使用很多开源软件做的，检测出的都是一些新的deficit，而没有那种bugreport中的。更加验证了这种性能问题不能算bug这一点。 作者LuShan后来有深入研究loop，在ICSE 17上发了Performance Diagnosis for Inefficient Loops，这篇就更像bug了，因为对循环中的语义进行了分析，实验部分也都是现实中的bugreport。但是所分析的语义也有局限，只有她总结出的几种（循环不产生结果、只有最后一次迭代有结果等等），还是有局限性。对于这一点，我就想能不能更加深入地分析语义。我之前看到一个bug：
这个bug其实就是在一个循环中，如果输入满足一个条件，那么循环就可以break。这个条件是语义层面的东西，用上面两篇文章的方法是搞不定的。那么如果我能找到这个条件，也是一个进步。其实这个想法也来源于c++<algorithm.h>里的sort函数，这个函数对于不同长度的数组，会采用不同的排序算法，以达到较好的性能。再比如之前还见过一个bug：
他的patch就是加了一个条件。 这种条件怎么找？我觉得第一步是要判断是不是在当前循环中，是否需要加这个条件，也就是一个loop需不需要采用这种分治的思想。第二步，是看循环中的哪个变量满足什么条件时需要被分治。如：当a<10时明显比a>=10的速度慢那么应该考虑分情况。 以上是一个初步的想法，还需要更多真实bug来支撑。
这个bug其实就是在一个循环中，如果输入满足一个条件，那么循环就可以break。这个条件是语义层面的东西，用上面两篇文章的方法是搞不定的。那么如果我能找到这个条件，也是一个进步。其实这个想法也来源于c++<algorithm.h>里的sort函数，这个函数对于不同长度的数组，会采用不同的排序算法，以达到较好的性能。再比如之前还见过一个bug：
他的patch就是加了一个条件。
这种条件怎么找？我觉得第一步是要判断是不是在当前循环中，是否需要加这个条件，也就是一个loop需不需要采用这种分治的思想。第二步，是看循环中的哪个变量满足什么条件时需要被分治。如：当a<10时明显比a>=10的速度慢那么应该考虑分情况。
以上是一个初步的想法，还需要更多真实bug来支撑。看了以前、现在读的paper中的十几个性能bug，试图跟着论文作者的讲解更加深入地理解它们，有几个我读了patch发现和作者说的吻合，有的不吻合原因应该是我没有完全看懂。上文提到的两个bug就在其中