💻 computer science

NESA: Relational Neuro-Symbolic Static Program Analysis

This paper introduces NESA, a compositional neuro-symbolic framework that leverages large language models guided by a restricted Datalog policy to enable compilation-free, customizable static program analysis with significantly reduced hallucinations, achieving performance comparable to or better than existing techniques in tasks like bug detection and program slicing.

Original authors: Chengpeng Wang, Yifei Gao, Wuqi Zhang, Xuwei Liu, Jinyao Guo, Mingwei Zheng, Qingkai Shi, Xiangyu Zhang

Published 2026-04-15

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Chengpeng Wang, Yifei Gao, Wuqi Zhang, Xuwei Liu, Jinyao Guo, Mingwei Zheng, Qingkai Shi, Xiangyu Zhang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to find a specific typo in a massive, unfinished novel. You have two options:

The Old Way (Traditional Static Analysis): You hire a team of strict, rule-following editors. They are incredibly accurate, but they have a catch: they can only read the book if it's been fully printed, bound, and formatted by a specific publishing machine. If the author is still typing the last chapter, or if the book was written in a different font, the editors refuse to work. Also, if you want them to look for a specific kind of mistake (like "find all sentences where the hero forgets his umbrella"), you have to hire a specialist editor who knows exactly how to reprogram the main editor's brain. It's rigid, expensive, and slow to set up.
The New Way (LLMs Alone): You hire a brilliant, imaginative storyteller (an AI) who can read the unfinished draft instantly. They understand the plot, the characters, and the mood perfectly. However, this storyteller has a bad habit of hallucinating. They might confidently tell you, "The hero forgot his umbrella," even if the text actually says he packed it. They make up facts to fill in the gaps, leading to false alarms.

Enter NESA: The "Smart Project Manager"

The paper introduces NESA, a new tool that acts like a brilliant project manager who combines the best of both worlds. It uses the imaginative AI storyteller but puts them on a strict, step-by-step workflow to stop them from making things up.

Here is how NESA works, broken down into simple metaphors:

1. Breaking the Big Problem into Tiny Puzzles (Decomposition)

Instead of asking the AI, "Find all the bugs in this 10,000-line code," NESA breaks the task down. It says, "First, let's just find where the variable userCity is defined. Then, let's just find where it is used."

The Analogy: Imagine trying to find a lost key in a messy room. Instead of telling the AI, "Find the key," NESA says, "First, look under the lamp. Then, look in the drawer." By narrowing the scope, the AI is less likely to get confused or make up a fake location for the key.

2. The "Fact-Checker" vs. The "Storyteller" (Neuro-Symbolic)

NESA splits the work into two types of tasks:

The Fact-Checker (Symbolic): For things that are easy to count or see (like "Is this line of code on line 26?" or "Does this function call that one?"), NESA uses a strict, math-based parser. This part never hallucinates. It's like a calculator; it just gives the right answer.
The Storyteller (Neural/LLM): For things that require understanding meaning (like "Does this user input affect that database?"), NESA asks the AI. But it only asks the AI about the tiny, specific puzzle piece it just created.

3. The "Lazy" and "Incremental" Strategies

NESA is very smart about how it asks the AI questions to save money and time:

Lazy Prompting: NESA waits until it has all the "hard facts" from the Fact-Checker before asking the Storyteller a question.
- Analogy: Instead of asking the AI, "What's the weather?" (which is vague), NESA waits until it knows it's "Tuesday in London" and then asks, "What's the weather in London on Tuesday?" This gives the AI a much better chance of being right.
Incremental Prompting: NESA remembers what it has already asked.
- Analogy: If the AI has already told you that "Alice is friends with Bob," NESA won't ask the AI again, "Is Alice friends with Bob?" It just writes that down and moves on. This saves a lot of time and money.

4. The "Policy Language" (The Rulebook)

NESA uses a special, simple language (based on something called Datalog) that lets users write their own rules without needing to be a computer genius.

The Analogy: Instead of writing a complex computer program to find bugs, a developer can just write a simple recipe: "If you see a 'Source' (like user input) and a 'Sink' (like a database), and they are connected, flag it." NESA takes this simple recipe and does the heavy lifting.

Why Does This Matter?

The researchers tested NESA on real-world software and found:

It works on unfinished code: You don't need to compile the software first.
It catches more bugs: In tests, it found more real bugs and made fewer mistakes than current industrial tools.
It found real-world secrets: It actually found 13 memory leak bugs in real software used by companies like Uber, which the developers then fixed.
It's customizable: You can teach it to look for any specific type of bug just by giving it a few examples, without needing to rewrite the tool's core code.

In a nutshell: NESA is like giving a super-smart but slightly scatterbrained AI a strict checklist and a team of fact-checkers. It keeps the AI focused, stops it from making things up, and allows anyone to customize it to find exactly the bugs they care about, even in messy, unfinished code.

1. Problem Statement

Static program analysis is crucial for optimization, bug detection, and debugging, yet its adoption in industry is hindered by two primary limitations:

Reliance on Compilation: Traditional analyzers (e.g., FlowDroid, Infer) require source code to be compiled into Intermediate Representations (IR). This makes them ineffective for incomplete code (common in IDEs) and creates compatibility issues with diverse build systems and IR versions.
Lack of Customization: Existing tools offer limited support for custom analysis requirements. Adapting them often requires deep expertise in compiler infrastructure and IRs, creating a high barrier for developers.

While Large Language Models (LLMs) offer a promising, compilation-free alternative capable of understanding semantics, they suffer from hallucinations (generating incorrect facts), leading to low precision and recall in static analysis tasks.

2. Methodology: NESA Framework

The authors propose NESA, a Relational Neuro-Symbolic approach that combines the deterministic nature of parsing with the semantic understanding of LLMs to enable compilation-free and customizable analysis.

A. Analysis Policy Language (Datalog-based)

NESA uses a restricted form of Datalog as an analysis policy language. This allows users to decompose complex analysis problems into smaller sub-problems via rules. The language introduces three types of relations:

Symbolic Relations: Represent syntactic properties (e.g., expression names, line numbers, control dependencies) derived deterministically via a Program Parser (using tree-sitter). These are hallucination-free.
Neural Relations: Represent semantic properties (e.g., data dependencies, taint flows) that are difficult to formalize syntactically. These are populated using LLM prompting.
Intensional Relations: The output relations derived from the rules, representing the final analysis result (e.g., a program slice or a list of bugs).

B. Problem Decomposition Strategy

Instead of asking an LLM to solve a complex problem directly, NESA decomposes it:

Syntactic Sub-problems: Handled by the parser (Symbolic Relations).
Semantic Sub-problems: Handled by the LLM (Neural Relations) but constrained by the results of the syntactic analysis.

C. Evaluation Procedure & Hallucination Mitigation

To evaluate the analysis policy, NESA employs a worklist algorithm with two key innovations to mitigate LLM hallucinations and reduce costs:

Lazy Prompting:
- The system delays prompting the LLM to populate a neural relation until all other non-neural relations (symbolic and intensional) in the rule body are fully determined.
- Benefit: This provides the LLM with "bounded terms" (specific values derived from the parser), narrowing the search space and significantly reducing the likelihood of hallucinations.
Incremental Prompting:
- In iterative fixed-point computations, rules may be re-evaluated. NESA tracks which tuples have already been processed.
- Benefit: The LLM is only prompted for new tuples, avoiding redundant API calls and reducing token costs.

D. Neural Constructors

The system defines "Neural Constructors" (e.g., 0-arity, 1-arity, 2-arity) to guide how the LLM populates relations.

Constrained Constructors: By using bounded terms from symbolic relations, NESA forces the LLM to use higher-arity constructors (e.g., checking if a specific pair $(e_1, e_2)$ has a dependency) rather than open-ended generation (0-arity), which is more prone to errors.

3. Key Contributions

Relational Neuro-Symbolic Framework: A novel approach that composes syntactic (parser-based) and semantic (LLM-based) analysis results using a Datalog-like policy language.
Compilation-Free & Customizable: Users can define analysis tasks using natural language descriptions and few-shot examples (Neural Relation Specifications) without modifying compiler internals or compiling code.
Hallucination Mitigation Strategies: Introduction of Lazy Prompting and Incremental Prompting to systematically reduce LLM errors and computational overhead.
Comprehensive Evaluation: Extensive experiments on program slicing and diverse bug detection tasks (APT, XSS, DBZ, NPD, RE, UOWH) demonstrating superior performance over both traditional tools and end-to-end LLM prompting.

4. Experimental Results

NESA was evaluated on the Juliet Test Suite, CodeNet, TaintBench, and real-world projects (h3, dynamips).

Program Slicing:
- Achieved 91.50% Precision and 84.61% Recall (F1: 0.88).
- Outperformed the state-of-the-art learning-based slicer (NS-Slicer) by 0.06 F1 score.
Bug Detection (Juliet Test Suite):
- XSS: 98.95% Precision, 94.00% Recall.
- APT: 94.74% Precision, 90.00% Recall.
- UOWH: 100% Precision and Recall.
- DBZ: 54.62% Precision, 71.00% Recall (lower due to path feasibility challenges, but still effective).
- Comparison: NESA significantly outperformed end-to-end few-shot CoT prompting with GPT-3.5, GPT-4, and Claude models, which suffered from low precision due to hallucinations.
Real-World Impact:
- Detected 13 real-world memory leak bugs in the h3 and dynamips projects, all of which were confirmed and fixed by developers.
- On TaintBench (Android malware), NESA achieved 66.27% Precision and 78.57% Recall, surpassing an industrial approach by 0.20 in F1 score.
Efficiency:
- While NESA incurs higher token costs than raw prompting, it detects significantly more true bugs. The cost-per-true-bug is lower than using stronger models (e.g., GPT-4) directly.
- Incremental prompting skipped ~30-80% of prompting rounds depending on the task.

5. Significance

NESA represents a paradigm shift in static analysis by bridging the gap between symbolic rigor and LLM flexibility.

Usability: It lowers the barrier to entry for static analysis, allowing developers to customize tools via natural language without compiler expertise.
Robustness: It solves the "hallucination" problem in LLM-based analysis by grounding semantic reasoning in deterministic syntactic facts.
Practicality: It operates without compilation, making it suitable for development environments with incomplete code, and has already proven effective in finding and fixing real-world security vulnerabilities.

The paper concludes that NESA offers a scalable, general framework that can reshape static analysis, making it more accessible and effective for modern software engineering workflows.