Abstract:

Dynamic symbolic execution is an effective testing method. However, due to the limitation of the constraint solving capability, the path coverage of the dynamic symbol execution needs to be improved in the face of complicated programs and path conditions. To improve the path coverage of testing, this paper proposes a dynamic symbol execution method based on the assistance of genetic algorithm, and a prototype tool JDart-Ga is implemented based on the method. The proposed method leverages the advantages of the genetic algorithm to generate test inputs for the program path conditions that cannot be handled by the dynamic symbolic execution. The experimental results show that the path coverage of JDart-Ga is increased from 16% to 23% with respect to JDart, when testing 3 experimental programs that contain feasible path conditions cannot solved by the constraint solver.

Key words: dynamic symbolic execution, constraint solving, path coverage, genetic algorithm

摘要：

动态符号执行是一种有效的软件测试方法，但由于受到约束求解器求解能力的限制，在面对较为复杂的程序和路径条件时，动态符号执行的路径覆盖率还有待提升。针对上述问题，提出了一种遗传算法辅助的动态符号执行测试方法，并基于此方法实现了原型工具JDart-Ga。该方法结合遗传算法的优势，生成约束求解器无法求解的约束条件对应测试输入，从而提升动态符号执行的路径覆盖率。实验结果表明，在测试存在动态符号执行无法覆盖路径的3个实验对象时，所提出方法的路径覆盖率与JDart相比分别提升了16%至23%。

关键词: 动态符号执行, 约束求解, 路径覆盖, 遗传算法