Technical Summary: Generating Complex Code Analyzers from Natural Language Questions

Problem Statement

Software development frequently involves developers posing analytical questions about codebases to understand global structure, semantics, and potential bugs. However, answering these questions in large-scale systems (millions of lines of code across thousands of files) presents significant challenges:

1. Limitations of Standard Tools: Tools like grep or IDE search features are limited to syntactic or local pattern matching and cannot perform the inter-procedural reasoning or semantic analysis required for complex queries (e.g., finding methods that call overridable methods within constructors).
2. Limitations of Large Language Models (LLMs): While LLMs offer a natural interface, they struggle with large codebases due to context window constraints, resource limits, and the lack of a structured, persistent view of the code. Directly prompting LLMs often leads to inconsistent outputs, hallucinations, or empty results. Furthermore, generating complex program analysis queries (specifically in CodeQL) is difficult due to the scarcity of training data and the "delicate" semantics of the language, where minor variations can lead to syntactically invalid or semantically degenerate queries.

Methodology: The Merlin System

The authors present Merlin, a system that integrates Large Language Models with CodeQL, a declarative program analysis framework. Merlin translates natural language questions into executable CodeQL queries, grounding the answers in the results of static analysis rather than the LLM's internal text representation.

The system operates through a workflow comprising three main components:

1. Question Preprocessing

Before query generation, Merlin prepares two key artifacts:

• Self-Test Generation: The LLM is prompted to generate concrete code examples (test cases) that should or should not satisfy the user's goal. These serve as a "litmus test" to detect degenerate queries (those that produce empty results despite being syntactically correct) before they are run on the full codebase.
• Iterative Documentation Retrieval: Instead of asking the LLM to list necessary CodeQL constructs directly (which leads to hallucinations), Merlin uses an iterative RAG-based loop. It first extracts keywords from the user's question, then asks the LLM to map these to CodeQL constructs. The system validates these constructs against the official CodeQL documentation, providing feedback on non-existent constructs and iterating until a valid set is established.

2. RAG-Based Query Debugging

The LLM generates an initial CodeQL query based on the user's goal, the output schema, the self-tests, and the retrieved documentation. This query is compiled using the CodeQL compiler.

• If the compiler returns syntax errors, Merlin extracts the error messages, retrieves relevant documentation for the specific constructs involved, and prompts the LLM to revise the query.
• This loop continues until a syntactically valid query is produced.

3. Semantic Verification via Assistive Queries

Even syntactically valid queries may fail to capture the intended semantics (e.g., being overly selective and returning empty results). To address this, Merlin employs Assistive Queries:

• If a query fails the self-test (returns empty results), the system prompts the LLM to generate an auxiliary "assistive" query.
• These queries are designed to be permissive (e.g., printing types or intermediate properties) to expose why the original query failed.
• The results of the assistive query are fed back to the LLM to diagnose the semantic flaw and refine the original query.
• This "compile-test-assist" loop repeats until the query produces non-empty results on the self-tests.

Finally, the validated query is executed over the entire codebase, and the results are presented to the user in a tabular format, accompanied by the generated CodeQL query as justification.

Key Contributions

1. Merlin System: A novel architecture integrating LLMs with program analyzers (CodeQL) to answer free-form natural language questions about large codebases reliably.
2. Novel Debugging Techniques:
   • A RAG-based iterative procedure for generating syntactically correct queries despite the scarcity of CodeQL training data.
   • A self-test technique using automatically generated code examples to detect degenerate queries.
   • Assistive queries that function like diagnostic print statements to expose and explain semantic flaws in candidate queries.
3. Empirical Evaluation: A comprehensive evaluation including benchmarks, a survey, and a user study demonstrating the system's effectiveness.

Results

Experimental Evaluation (Benchmarks)

The authors evaluated Merlin against 182 natural language questions derived from SpotBugs (142 detectors) and the GitHub Security Lab (40 queries) across 13 large codebases.

• Recall: Merlin significantly outperformed baseline approaches (direct LLM answering, LLM-to-CodeQL generation without debugging). Merlin achieved a macro-recall of 0.62 and micro-recall of 0.64, compared to baselines that often struggled with recall (e.g., GPT-4o/CQL had 0.08 micro-recall).
• Precision and Discovery: While baselines often missed issues, Merlin not only reproduced the results of reference analyzers but also identified previously unknown locations. A user survey confirmed that many of these "new" findings were genuinely relevant code snippets that other tools had missed, suggesting Merlin achieves higher precision and recall than the reference tools when human judgment is the ground truth.
• Resource Efficiency: Unlike baselines that require uploading entire codebases to LLMs (hitting file limits and context windows), Merlin synthesizes queries independently of the codebase, resulting in significantly lower prompt lengths and computational costs.

User Study

A within-subject study with 18 participants (13 students, 5 professionals) tasked with finding and fixing violations of SEI CERT coding standards revealed:

• Accuracy: Access to Merlin increased task accuracy by an average of 3.8×. The improvement was most pronounced for complex tasks (Task T1: 5.6×; Task T3: 4.9×) and less for tasks solvable by simple grep (Task T2: 1.6×).
• Efficiency: Participants using Merlin completed tasks 31% faster on average.
• Behavioral Shift: Merlin shifted user strategies from labor-intensive pattern matching (regex, keyword search) to high-level reasoning. It also reduced reliance on external AI for the "finding" phase, though the authors note a risk of users over-trusting Merlin's outputs.

Significance and Claims

The paper claims that Merlin successfully bridges the gap between the natural language interface of LLMs and the rigorous, structured reasoning of program analyzers. By addressing the specific challenges of generating complex, low-resource analysis queries (CodeQL) through iterative debugging and self-testing, Merlin enables developers to perform exhaustive, auditable, and repeatable analyses on large codebases.

The authors emphasize that Merlin is not merely a chatbot but a system that produces certifiable outputs (the generated CodeQL query), allowing developers to verify the logic behind the results. This approach overcomes the unreliability of purely LLM-based reasoning and the rigidity of traditional static analysis tools, offering a practical solution for modern software engineering tasks that require deep semantic understanding of code.

The paper remains modest regarding its scope, acknowledging that it currently focuses on bug-finding and analytical questions, and that future work is needed to support broader developer workflows, interactive debugging, and non-analytical questions.