Symbolic execution is a powerful technique that can accurately synthesize program inputs for program testing through constraint solving. Applying symbolic execution effectively means that we must solve two searching problems efficiently. One is to search through the many program paths and the other is, given a particular path condition, to search through the numerous variable assignments to identify one satisfying solution. With few exceptions, existing symbolic execution engines treat constraint solvers as black boxes. As a result, the two searches are completely separated, which results in much redundancy (i.e., the same variable assignments may be tried for solving many program paths). Existing attempts on addressing this issue include those approaches based on constrained Horn clauses (in which the whole program is encoded as one constraint) and one preliminary attempt on caching and reusing partial solving results from the constraint solver. In this work, we propose SEC , which systematically computes the reward of concretizing a program path (for symbolic execution) and a variable (for constraint solving) and uses the reward as guide for integrating the two searches. We implemented SEC based on KLEE and evaluated it on a diverse set of programs. The results show that SEC is effective, i.e., achieving 15% more code coverage than the state-of-the-art baseline symbolic execution engines. Furthermore, we show that SEC can be readily combined with a state-of-the-art concolic testing engine to improve its performance

Symbolic execution is a powerful technique that can accurately synthesize program inputs for program testing. However, the scalability of symbolic execution is often limited by the capability of the constraint solver and time for testing. With limited time budget, it is desirable to optimally select paths for symbolic execution and furthermore variables for symbolization in order to achieve the maximum code coverage. In this work, we make two technical contributions towards solving this problem. First, different from most existing solving strategies based on heuristic path selection, we formally define the ‘optimal’ strategy based onthe reward of executing a given program path considering both possible code coverage and the cost of constraint solving. We further prove that the problem of identifying the optimal strategy for symbolic execution can be reduced to a classic knapsack problem, whose decision problem form is NP-complete. Second, in view of the complexity in identifying the optimal strategy, we design a practical greedy algorithm, named OPTSE, for approximating the optimal strategy. We implemented OPTSE in KLEE and extensively evaluate it on a diverse set of programs. The results show that OPTSE is effective, i.e., achieving 12% more code coverage and detects 17% more security violations than the state-of-the-art symbolic execution tool and outperforming a collection of strategies that only consider either path selection, solving strategies or simply superimpose them.

Fuzzing is one of the prevailing methods for vulnerability detection. However, even state-of-the-art fuzzing methods become ineffective after some period of time, i.e., the coverage hardly improves as existing methods are ineffective to focus the attention of fuzzing on covering the hard-to-trigger program paths. In other words, they cannot generate inputs that can break the bottleneck due to the fundamental difficulty in capturing the complex relations between the test inputs and program coverage. In particular, existing fuzzers suffer from the following main limitations: 1) lacking an overall analysis of the program to identify the most “rewarding” seeds, and 2) lacking an effective mutation strategy which could continuously select and mutates the more relevant “bytes” of the seeds. In this work, we propose an approach calledATTuzzto address these two issues systematically. First, we propose a lightweight dynamic analysis technique that estimates the “reward” of covering each basic block and selects the most rewarding seeds accordingly. Second, we mutate the selected seeds according to a neural network model which predicts whether a certain “rewarding” block will be covered given certain mutations on certain bytes of a seed. The model is a deep learning model equipped with an attention mechanism which is learned and updated periodically whilst fuzzing. Our evaluation shows thatATTuzzsignificantly outperforms 5 state-of-the-art grey-box fuzzers on 6 popular real-world programs and MAGMA data sets at achieving higher edge coverage and finding new bugs. In particular,ATTuzzachieved 1.2X edge coverage and 1.8X bugs detected than AFL++ over 24-hour runs. In addition,ATTuzzalso finds 4 new bugs in the latest version of some popular software including p7zip and openUSD.