DiverJS: path exploration heuristic for difference analysis of event-driven code
DiverJS: path exploration heuristic for difference analysis of event-driven code
复制标题
DOI：
10.1145/3412841.3442049
复制
发表时间：
2021-03
期刊：
影响因子：
--
通讯作者：
Ena Tominaga;Yoshitaka Arahori;K. Gondow
中科院分区：
文献类型：
--
作者：
Ena Tominaga;Yoshitaka Arahori;K. Gondow
现有的差异分析方法不能很好地处理事件驱动的代码，因为它们只探索整数和字符串等程序输入的输入空间，而不探索所有可能的事件序列的事件空间。本文提出了一种新的启发式算法，以及一个称为DiverJS的工具，用于执行能够很好地处理输入空间和事件空间的差异分析。为了有效地挖掘巨大的空间，DiverJS基于动态偏序降阶算法(DPOR)对冗余事件序列进行剪枝。DiverJS还随机切换了两个探索启发式：(1)一个旨在增加代码覆盖率，使用来自写-读(WR)集和动态污点分析的共享变量信息；(2)另一个旨在引导执行到代码更改的位置，使用要求反的分支与更改之间的距离。我们进行了初步的实验，以评估程序行为差异的检测准确率，以及通过路径数来评估探索的效率。结果表明，DiverJS的检测性能优于已有的方法；DiverJS在更少的路径上以更高的检测准确率检测出差异，这表明我们的DiverJS差异分析是有效和高效的。
The existing methods of difference analysis cannot cope with event-driven code well, since they explore only the input space for program input like integers and strings, but do not explore the event space for all possible event sequences. This paper proposes a novel heuristic, as well as a tool called DiverJS, for performing difference analysis that copes well with both the input space and event space. To efficiently explore huge space, DiverJS prunes redundant event sequences based on Dynamic Partial Order Reduction (DPOR). DiverJS also stochastically switches two exploration heuristics: (1) one aims to increase code coverage, using shared variable information, derived from Write-Read (WR) set and dynamic taint analysis, (2) the other aims to guide the execution to the location of code changes, using the distance between the branch to be negated and the change. We conducted a preliminary experiment to evaluate the detection accuracy of program behavioral differences, and the efficiency of exploration by the number of paths. The result shows DiverJS outperformed the existing methods; DiverJS detected the differences with higher detection accuracy in fewer paths, which suggests our DiverJS's difference analysis is effective and efficient.