Publication Type

Conference Proceeding Article

Version

acceptedVersion

Publication Date

6-2018

Abstract

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.

Discipline

Computer Engineering | Software Engineering

Research Areas

Software and Cyber-Physical Systems

Publication

Proceedings of the 40th International Conference on Software Engineering, Gothenburg, Sweden, 2018 May 27 - June 3

First Page

291

Last Page

302

Identifier

10.1145/3180155.3180177

Publisher

IEEE

City or Country

Gothenburg, Sweden

Comments

ACM Distinguished Paper Award

Additional URL

https://doi.org/10.1145/3180155.3180177

Download

Share

COinS