Neuro-symbolic Static Analysis with LLM-generated Vulnerability Patterns

1. Problem Statement

Pattern-based static analysis is a cornerstone of modern vulnerability detection (e.g., CodeQL, Joern), offering high scalability and code coverage. However, its effectiveness relies entirely on the quality of vulnerability patterns (queries).

• Manual Bottleneck: Creating these patterns is labor-intensive, requiring weeks of expert effort per vulnerability type.
• Knowledge Gaps: Human experts may miss subtle attack variants or linguistic nuances, leading to false negatives.
• LLM Limitations: While Large Language Models (LLMs) possess strong semantic reasoning, they struggle with:
  • DSL Syntax: They often fail to generate syntactically correct queries for Domain-Specific Languages (DSLs) used by static analyzers (e.g., CodeQL's SQL-like syntax, Joern's Scala-like syntax).
  • Semantic Errors: Even syntactically valid queries may fail to capture vulnerabilities due to overfitting (too specific) or underfitting (too general).
  • Hallucinations: LLMs frequently invent non-existent APIs or incorrect logic.

Existing hybrid approaches (e.g., IRIS, KNighter) only automate parts of the process (like identifying taint sources) while leaving the core logic manual, or they lack interprocedural analysis capabilities.

2. Methodology: MoCQ Framework

The authors propose MoCQ (Model-Generated Code Queries), a neuro-symbolic framework that automates end-to-end vulnerability pattern generation. It combines LLMs for semantic reasoning with symbolic static analysis for validation.

Core Workflow

1. DSL Extraction and Subsetting:
   • MoCQ automatically parses documentation and source code of static analysis tools (Joern, CodeQL) to extract formal DSL specifications (grammars, APIs, types).
   • Key Innovation: It applies DSL Subsetting. Since full DSLs are too complex for LLMs, MoCQ selects a core, non-redundant subset of APIs. This reduces complexity while preserving expressiveness, significantly improving the LLM's ability to generate valid syntax.
2. Iterative Query Generation & Refinement:
   • Input: A natural language description of a vulnerability and a few representative code examples.
   • Process: The LLM generates an initial query.
   • Symbolic Validator: A trace-driven validator executes the query against the code examples. It captures fine-grained runtime states (syntax errors, execution exceptions, intermediate variable values).
   • Feedback Loop: The validator provides specific feedback to the LLM:
     • Syntax/Runtime: Corrects grammar and API usage errors.
     • Semantic: Identifies if the query misses the target (false negative) or matches irrelevant code (false positive).
     • Generalization: Detects overfitting (e.g., hardcoded variable names) and instructs the LLM to abstract the pattern.
3. Query Merging:
   • Once valid queries are generated for individual examples, an LLM merges them into a single, optimized query to improve execution efficiency and reduce redundancy.

3. Key Contributions

• Automated End-to-End Generation: Unlike prior works that only assist with specific parts, MoCQ generates complete, executable vulnerability detection patterns from scratch.
• DSL Subsetting Technique: A novel method to refine complex DSLs into LLM-friendly subsets without losing detection capability.
• Trace-Driven Symbolic Validation: A feedback mechanism that instruments the query runtime to provide granular debugging information (program states) to the LLM, enabling precise error correction.
• Multi-Language Support: The framework is implemented for Joern and CodeQL, supporting C/C++, Java, PHP, and JavaScript.

4. Experimental Results

The authors evaluated MoCQ on 12 vulnerability types across 4 languages using a dataset of 555 vulnerabilities.

• Generation Success: MoCQ successfully generated valid queries for 77.4% of the test cases (123 out of 164 unique examples) within hours, compared to weeks of manual effort.
• Detection Performance:
  • MoCQ achieved a 78.4% True Positive Rate (TPR) on the testing set, comparable to expert-developed queries (which had a similar TPR but required massive manual effort).
  • Complementary Strengths: Combining MoCQ-generated queries with expert queries yielded the highest coverage (85%), proving that LLMs and humans have different strengths (LLMs catch subtle linguistic nuances; humans excel at high-level logic).
• New Discoveries:
  • 46 New Patterns: MoCQ uncovered 46 vulnerability patterns missed by existing expert queries (e.g., specific PHP type juggling mechanisms, new prototype pollution vectors).
  • 25 Zero-Day Vulnerabilities: Applied to real-world applications, MoCQ discovered 25 previously unknown vulnerabilities. 14 were acknowledged by maintainers, and 5 have been fixed.
• Comparison to SOTA:
  • Outperformed pure LLM approaches (which lack cross-file context) and specialized tools like KNighter (which lacks interprocedural analysis).
  • Showed better precision than Silent-Spring (JS prototype pollution) and comparable recall to Cred (C/C++ UAF).

5. Significance

• Scalability & Efficiency: Reduces the engineering effort for creating vulnerability detectors from weeks to hours.
• Accessibility: Lowers the barrier to entry for creating custom static analysis rules, allowing developers to rapidly generate patterns for newly disclosed threats.
• Hybrid Paradigm: Demonstrates that a neuro-symbolic approach (LLM reasoning + Symbolic validation) is superior to either pure learning-based or pure symbolic approaches for static analysis tasks.
• Practical Impact: The discovery of 25 real-world vulnerabilities and the integration of 5 new patterns into upstream tool repositories (Joern/CodeQL) validates the practical utility of the framework.

In conclusion, MoCQ represents a significant step forward in automating security analysis, effectively bridging the gap between the semantic understanding of LLMs and the precision of formal static analysis.