A Shape-inference-based Approach to Enhance Constraint Independence Optimization

Constraint independence optimization is one of the most important constraint solving optimizations and widely used by symbolic executions. Constraint independence optimization divides the set of constraints into multiple independent subsets as the symbolic variables of constraint. But existing constraint independence optimization is not efficient for binary symbolic execution because the symbolic variables are coarse-grained. In this paper, we propose a shape-inference-based approach to enhance constraint independence optimization.We propose a shape inference algorithm to split the symbolic variable into multiple fields and perform constraint independence optimization as the fields of symbolic variables. We implement a prototype system, angr-shape, based on the proposed approach and verify its effectiveness according to experimentation. Compared with state-of-the-art approach, the experimental results demonstrate that the number of generated test cases increases by 2.37% and the time of constraint solving reduces by 14.00%.