This paper tries to find the proper strategy of invoking concolic execution in hybrid fuzzing, since its high overhead. Based on the observation of avaliable methods, demand launch and optimal switch, the authors give two principles: use concolic execution to solve the hardest problems and a lightweight way to decide which one is harder (Or which execution path is harder to arrive).
This paper proposes a new way to deicide which lucky testcase will be accepted by concolic execution and disclose some hard to arrive path. During the conventional fuzzing, the following extra tasks are done.
- save the hit times of each branch during fuzzing loop (called execution sampling in original paper)
- get every branch that avaliable testcases ever arrive and calculate their probabilities according to equation 1 (called execution tree construction in original paper)
- leveraging CFG and hitted branches, calculate the probabilities (indicate the ability to be touched by conventional fuzzing) of all untouched branches and use concolic execution on branch with lowest probability. As for the detail implementation, concolic execution accepts the testcase which can touch its neghbor branch, which means most similar exectuion path. (called probability based path prioritization in original paper)