Abstract:Symbolic execution is a powerful program analysis technique, but its effectiveness is fundamentally limited by solver-hostile program fragments, complex numerical reasoning, and unbounded heap structures. Recent work proposed replacing constraint solvers with large language models (LLMs) to bypass these limitations, but such approaches struggle to analyze real-world codebases, where deep execution paths require globally consistent reasoning across many interacting constraints. We present Gordian, a hybrid symbolic execution framework that uses LLMs selectively to generate lightweight ghost code that aids an SMT solver in handling solver-hostile code fragments, while preserving its precise, global reasoning capability. In particular, we propose three types of ghost code: (1) inversion of difficult code fragments with iterative bidirectional constraint propagation, (2) modeling via solver-friendly surrogates while preserving relevant behavior, and (3) semantic partitioning of unbounded heap spaces. We implemented Gordian on top of the KLEE symbolic execution engine and evaluated it on synthetic "logic bombs" capturing distinct symbolic reasoning challenges, a popular mathematical library FDLibM, and four structured-input programs (libexpat, jq, bc and libyaml). Across benchmarks, Gordian improves coverage by 28.5-115.2% over traditional symbolic execution baseline and by 74.1-189.8% over LLM-based symbolic execution baselines, while reducing LLM token usage by an average of 91-96%. This highlights the practicality and effectiveness of this approach in real-world settings.
From: Sergey Mechtaev [view email]
[v1]
Sat, 31 Jan 2026 07:14:57 UTC (267 KB)
[v2]
Tue, 8 Sep 2026 07:27:48 UTC (2,535 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。