Towards Optimal Concolic Testing
Towards Optimal Concolic Testing
复制标题
DOI：
10.1145/3180155.3180177
复制
发表时间：
2018-05
期刊：
影响因子：
--
通讯作者：
Xinyu Wang;Jun Sun;Zhenbang Chen;Peixin Zhang;Jingyi Wang;Yun Lin
中科院分区：
文献类型：
--
作者：
Xinyu Wang;Jun Sun;Zhenbang Chen;Peixin Zhang;Jingyi Wang;Yun Lin
Concolic测试集成了具体的执行（例如，随机测试）和用于测试用例生成的符号执行。它被证明是更符合成本效益的随机测试或符号执行。concolic测试策略是一个函数，它决定何时应用随机测试或符号执行，如果是后者，则符号执行哪个程序路径。已经提出了许多基于生态学的策略。什么是最佳的concolic测试策略仍然是一个悬而未决的问题。在这项工作中，我们为解决这个问题做出了两个贡献。首先，我们证明了最优策略可以根据程序路径的概率和约束求解的成本来定义。最优策略的确定问题被归结为一个带费用的马尔可夫决策过程的模型检验问题。其次，针对最优策略识别的复杂性，设计了一种近似最优策略的贪婪算法。我们进行了两组实验。一种是基于随机生成的模型，另一种是基于一组C程序。结果表明，现有的算法有很大的改进空间，我们的贪婪算法往往优于现有的算法。
Concolic testing integrates concrete execution (e.g., random testing) and symbolic execution for test case generation. It is shown to be more cost-effective than random testing or symbolic execution sometimes. A concolic testing strategy is a function which decides when to apply random testing or symbolic execution, and if it is the latter case, which program path to symbolically execute. Many heuristics-based strategies have been proposed. It is still an open problem what is the optimal concolic testing strategy. In this work, we make two contributions towards solving this problem. First, we show the optimal strategy can be defined based on the probability of program paths and the cost of constraint solving. The problem of identifying the optimal strategy is then reduced to a model checking problem of Markov Decision Processes with Costs. Secondly, in view of the complexity in identifying the optimal strategy, we design a greedy algorithm for approximating the optimal strategy. We conduct two sets of experiments. One is based on randomly generated models and the other is based on a set of C programs. The results show that existing heuristics have much room to improve and our greedy algorithm often outperforms existing heuristics.