How to construct globally sound abstract interpreters to safely approximate program behaviors remains a bottleneck in abstract interpretation. In this paper, we show the potential of using state-of-the-art LLMs to automate this tedious process. Focusing on the neural network verification area, we synthesize non-trivial sound abstract transformers across diverse abstract domains using LLMs to search within infinite space from scratch. We formalize the synthesis task as a constrained optimization problem, for which we design a novel mathematically grounded cost function that measures the degree of unsoundness of each generated candidate transformer, while enforcing hard syntactic and semantic validity constraints. Building on this formulation, we introduce SAIL, a novel unified framework that combines model generation, syntactic and semantic validation, and cost-function-based refinement to synthesize globally sound abstract transformers. Evaluation results show that SAIL not only matches the performance of manually designed transformers, but also is able to synthesize sound and high-precision transformers that do not exist in the literature for complex non-linear operators.
Wed 17 JunDisplayed time zone: Mountain Time (US & Canada) change
16:10 - 17:50 | Abstract InterpretationPLDI Research Papers at Flatirons 2 Chair(s): Mukund Raghothaman University of Southern California | ||
16:10 20mTalk | SAIL: Sound Abstract Interpreters with LLMs PLDI Research Papers Qiuhan Gu University of Illinois Urbana-Champaign, Avaljot Singh University of Illinois Urbana-Champaign, Gagandeep Singh University of Illinois Urbana-Champaign DOI | ||
16:30 20mTalk | Evolving Abstract Transformers for Gradient-Guided, Adaptable Abstract Interpretation PLDI Research Papers Shaurya Gomber University of Illinois Urbana-Champaign, Debangshu Banerjee University of Illinois Urbana-Champaign, Gagandeep Singh University of Illinois Urbana-Champaign DOI Pre-print | ||
16:50 20mTalk | Abstract Interpretation with Confidence PLDI Research Papers DOI | ||
17:10 20mTalk | Optimism in Equality Saturation PLDI Research Papers Russel Arbore University of California at Berkeley, Alvin Cheung University of California at Berkeley, Max Willsey University of California at Berkeley DOI Pre-print | ||