Search papers, labs, and topics across Lattice.
This paper introduces Spear, a parallel synthesis framework designed to optimize the synthesis of abstract transformers for low-level code using fixed-size bit-vectors. By leveraging the independence of inter-objective bits, Spear significantly enhances scalability and runtime performance compared to existing Optimization Modulo Theories (OMT) solvers. Experimental results demonstrate that Spear not only solves more instances but also achieves markedly improved runtimes across various binary analysis benchmarks.
Spear accelerates the synthesis of optimal abstract transformers by exploiting parallelism, outperforming state-of-the-art solvers in both efficiency and scalability.
Abstract interpretation provides a principled foundation for constructing sound static analyses through systematic abstraction. A central challenge is synthesizing the best abstract transformers that achieve optimal precision within a given abstract domain. This paper addresses this problem for low-level code modeled with fixed-size bit-vectors. Recent approaches formulate the synthesis task as a multi-objective Optimization Modulo Theories (OMT) problem, but suffer from limited scalability. We introduce Spear, a parallel synthesis framework that exploits a key structural insight: while the bits within each objective must be processed sequentially, the objectives themselves are independent. Spear leverages the independence of inter-objective bits to better parallelize the synthesis. Experimental results on benchmarks across two binary analysis domains show that Spear consistently outperforms state-of-the-art OMT solvers, solving more instances and achieving significantly improved runtimes. To our knowledge, this is the first approach to apply parallelism to accelerate the synthesis of optimal abstract transformers.
