Summary Constraint solving is the enabling technique for symbolic execution. The advancement of constraint solving boosts the development and application of symbolic execution. Modern Satisfiability Modulo Theories (SMT) solvers provide the mechanism of solving strategy, allowing users to control the solving procedure. This mechanism significantly improves the solver's generalization ability. We observe that the symbolic executions of different programs are different constraint solving problems. Therefore, we propose synthesizing solving strategies for a program to fit the program's symbolic execution best. To achieve this, we propose an adaptive framework for synthesizing solving strategies, in which the constraints are classified into different categories, and the solving strategies are synthesized for different categories on demand. We propose novel synthesis algorithms that combine the offline trained deep learning models and online tuning to synthesize the solving strategy. The algorithms balance the synthesis overhead and the improvement achieved by the synthesized solving strategy. We have implemented our method on the state‐of‐the‐art symbolic execution engine KLEE for C programs and Symbolic Pathfinder (SPF) for Java programs. The results of the extensive experiments indicate that our method effectively improves the efficiency of symbolic execution. For the Coreutils benchmark, our method, on average, increases the numbers of paths and queries by 74.37% and 73.94% under Breadth First Search (BFS), respectively. Besides, we applied our method to a different benchmark of C programs and a benchmark of Java programs to validate the generalization ability. The results demonstrate that for the C benchmark, our method increases the numbers of paths and queries by 71.09% and 70.60% under BFS, respectively; For the Java benchmark, our method increases the numbers of paths and queries by 50.31% and 49.93% under BFS, respectively. These results show that our method has a good generalization ability.

Symbolic execution is powered by constraint solving. The advancement of constraint solving boosts the development and the applications of symbolic execution. Modern SMT solvers provide the mechanism of solving strategy that allows the users to control the solving procedure, which significantly improves the solver's generalization ability. We observe that the symbolic executions of different programs are actually different constraint solving problems. Therefore, we propose synthesizing a solving strategy for a program to fit the program's symbolic execution best. To achieve this, we divide symbolic execution into two stages. The SMT formulas solved in the first stage are used to online synthesize a solving strategy, which is then employed during the constraint solving in the second stage. We propose novel synthesis algorithms that combine offline trained deep learning models and online tuning to synthesize the solving strategy. The algorithms balance the synthesis overhead and the improvement achieved by the synthesized solving strategy.

Parsing code exists extensively in software. Symbolic execution of complex parsing programs is challenging. The inputs generated by the symbolic execution using the byte-level symbolization are usually rejected by the parsing program, which dooms the effectiveness and efficiency of symbolic execution. Complex parsing programs usually adopt token-based input grammar checking. A token sequence represents one case of the input grammar. Based on this observation, we propose grammar-agnostic symbolic execution that can automatically generate token sequences to test complex parsing programs effectively and efficiently. Our method's key idea is to symbolize tokens instead of input bytes to improve the efficiency of symbolic execution. Technically, we propose a novel two-stage algorithm: the first stage collects the byte-level constraints of token values; the second stage employs token symbolization and the constraints collected in the first stage to generate the program inputs that are more possible to pass the parsing code.

Constraint solving is a key challenge in symbolic execution.Usually, symbolic execution uses the fixed-size bitvector theory to precisely model the program's behavior and generates the bit-vector formula to query the SMT solver.To solve such bit-vector formula, SMT solvers usually adopt a bitblasting and conjunctive normal form (CNF) conversion step, transforming the original formula into a equi-satisfiable CNF formula, and then check the formula's satisfiability.However, the different CNF conversions can significantly affect the efficiency of SAT solving.We observe that each CNF encoding algorithm has its suitable applications, while adopting a specific CNF conversion algorithm for all formulas is often not optimal.Therefore, we propose to intelligently select a suitable CNF encoding algorithm for each logical formula.We have integrated our selection algorithm into the symbolic execution framework based on KLEE and STP, which are the state-of-the-art symbolic execution engine for C programs and its default underlying constraint solver, respectively.The experimental results, based on extensive evaluation of 86 real-world C programs in Coreutils benchmark, indicate that our method can effectively improve the efficiency of symbolic execution.On average, our method increases the number of the explored paths by 27.2%.

Constraint solving is one of the challenges for symbolic execution. Modern SMT solvers allow users to customize the internal solving procedure by solving strategies. In this extended abstract, we report our recent progress in synthesizing a program-specific solving strategy for the symbolic execution of a program. We propose a two-stage procedure for symbolic execution. At the first stage, we synthesize a solving strategy by utilizing deep learning techniques. Then, the strategy will be used in the second stage to improve the performance of constraint solving. The preliminary experimental results indicate the promising of our method.

The robustness of deep neural network (DNN) is critical and challenging to ensure. In this paper, we propose a general data-oriented mutation framework, called Styx, to improve the robustness of DNN. Styx generates new training data by slightly mutating the training data. In this way, Styx ensures the DNN's accuracy on the test dataset while improving the adaptability to small perturbations, i.e., improving the robustness. We have instantiated Styx for image classification and proposed pixel-level mutation rules that are applicable to any image classification DNNs. We have applied Styx on several commonly used benchmarks and compared Styx with the representative adversarial training methods. The preliminary experimental results indicate the effectiveness of Styx.