PaperlayerView exact revision on arXiv

Source-linked AI summary

KNighter: Transforming Static Analysis with LLM-Synthesized Checkers

Chenyuan Yang, Zijie Zhao, Zichen Xie, Haoyu Li, Lingming Zhang

arXiv:2503.09002v3cs.SEcs.AIcs.CRcs.OS

TL;DR

Static analyzers are difficult to build and often cover only narrow bug patterns, while directly scanning massive systems with LLMs is constrained by context and computational costs. KNighter synthesizes static checkers from historical patches, validates and refines them, and has uncovered 92 new Linux-kernel vulnerabilities, 57 of which were fixed.

  • Problem

    Traditional static analyzers depend on predefined checks and substantial expertise, while direct LLM analysis of large systems faces context-window and computational-cost constraints.

    Source: §1 · p. 2

  • Method

    KNighter uses LLMs to synthesize static checkers from historical patches, validates them against original patches, and iteratively refines them to reduce false positives.

    Source: §1 · p. 2

  • Results

    92 new Linux-kernel vulnerabilities, averaging 4.3 years old, were uncovered; 77 were confirmed, 57 fixed, and 30 assigned CVEs.

    Source: §1 · p. 2

  • Takeaways & Limitations

    KNighter’s detected vulnerabilities were orthogonal to those found by existing expert-written analyzers.

    Source: §1 · p. 2

    KNighter struggles with complex state-machine bugs such as use-after-free and concurrency issues involving multithreaded code and locking.

    Source: §6 · p. 12

Abstract

from arXiv · show

Static analysis is a powerful technique for bug detection in critical systems like operating system kernels. However, designing and implementing static analyzers is challenging, time-consuming, and typically limited to predefined bug patterns. While large language models (LLMs) have shown promise for static analysis, directly applying them to scan large systems remains impractical due to computational constraints and contextual limitations. We present KNighter, the first approach that unlocks scalable LLM-based static analysis by automatically synthesizing static analyzers from historical bug patterns. Rather than using LLMs to directly analyze massive systems, our key insight is leveraging LLMs to generate specialized static analyzers guided by historical patch knowledge. KNighter implements this vision through a multi-stage synthesis pipeline that validates checker correctness against original patches and employs an automated refinement process to iteratively reduce false positives. Our evaluation on the Linux kernel demonstrates that KNighter generates high-precision checkers capable of detecting diverse bug patterns overlooked by existing human-written analyzers. To date, KNighter-synthesized checkers have discovered 92 new, critical, long-latent bugs (average 4.3 years) in the Linux kernel; 77 are confirmed, 57 fixed, and 30 have been assigned CVE numbers. This work establishes an entirely new paradigm for scalable, reliable, and traceable LLM-based static analysis for real-world systems via checker synthesis.

1 Introduction

Static analysis offers broad source-code inspection but existing analyzers cover narrow bug patterns, while direct LLM scanning faces scale and context constraints. KNighter synthesizes and refines checkers from historical patches, with Linux-kernel evaluation and vulnerability discoveries demonstrating its practical impact.

1 Introduction

  • Static analysis examines source without execution, making it useful for hardware-dependent drivers, rarely exercised paths, and difficult-to-reproduce configurations.Unlike fuzzing, it can in principle cover potential execution paths, including seldom-triggered corner cases.Source: §1 · p. 1
  • Traditional analyzers rely on predefined or formally modeled checks that require substantial expertise and engineering, often limiting them to narrow bug-pattern subsets.Direct LLM scanning also faces context-window limits, prohibitive repeated-scan costs, and hallucination risks in large systems.Source: §1 · p. 2
  • KNighter uses LLMs to synthesize dedicated static checkers from historical patches rather than applying LLM analysis directly to massive codebases.The approach validates checkers against original patches and uses automated refinement to reduce false positives.Source: §1 · p. 2
  • 92 new Linux-kernel vulnerabilities, averaging 4.3 years old, were uncovered; 77 were confirmed, 57 fixed, and 30 assigned CVEs.KNighter synthesized high-quality checkers for 61% of 61 diverse bug-fix patches, with an approximately 35% false positive rate aided by the triage agent.Source: §1 · p. 2
  • KNighter’s synthesized vulnerabilities are orthogonal to those found by existing expert-written analyzers.The paper presents checker synthesis as a new paradigm for LLM-based static analysis.Source: §1 · p. 2

2 Background and Motivation

The background explains how Clang Static Analyzer checkers track program behavior through event callbacks and custom state. A devm_kzalloc null-dereference example motivates synthesizing a checker that tracks null checks and aliases, then validates and refines generated checkers.

2.1 Clang Static Analyzer

  • Clang Static Analyzer checkers register for analysis events and can extend ProgramState with checker-specific data to maintain state across analysis.A checker defines a bug pattern, implements callbacks, registers with the framework, and integrates with testing and reporting mechanisms.Source: §2.1 · p. 3
  • The example checker tracks devm_kzalloc results as potentially null, records null checks and pointer aliases, and warns when an unchecked region is dereferenced.Its callbacks update custom state after calls, branch checks, memory accesses, and pointer assignments.Source: §2.1 · p. 3

2.2 Motivating Example

  • A missing null check after devm_kzalloc can lead to a crash if allocation fails and the returned pointer is dereferenced.The described pattern had at least six historical patches but no systematic static-analysis tool; even specialized kernel checkers missed it because they lacked devm_kzalloc-specific knowledge.Source: §2.2 · pp. 3–4
  • The synthesized checker tracks null-check status across paths and handles aliases; it found three new Linux-kernel vulnerabilities, including one fixed as CVE-2024-50103.KNighter validates checkers against historical patches and uses a bug-triage agent to identify false alarms for iterative refinement.Source: §2.2 · p. 4

3 Design

KNighter turns historical patch commits into CSA checkers through staged bug-pattern analysis, planning, implementation, validation, and refinement. It validates checkers against buggy and patched code, then uses LLM agents to triage and reduce false positives during whole-codebase scanning.

3 Design

  • KNighter takes a patch commit through checker synthesis and refinement, presenting plausible checkers and filtered reports for review.Synthesis identifies a bug pattern, creates a detection plan, implements a CSA checker, and repairs compilation errors; refinement follows whole-codebase scanning.Source: §3 · p. 4

3.1.1 Bug Pattern Analysis.

  • Bug-pattern analysis uses the patch and complete modified-function code, favoring targeted patterns that are more tractable for LLM checker synthesis.Broader patterns can pose static-analysis challenges and hinder robust LLM implementation.Source: §3.1.1 · p. 5

3.1.2 Plan Synthesis.

  • Plan synthesis structures checker implementation and makes the LLMs’ reasoning transparent and traceable.The planning agent receives the summarized bug pattern and descriptions of curated utility functions.Source: §3.1.2 · pp. 5–6

3.1.3 Analyzer Implementation and Syntax Repair.

  • The implementation agent receives the bug pattern and plan, while a debugging agent repairs compilation errors using compiler messages.Checkers are validated by comparing warnings on patch-modified files and dependencies before and after the patch.Source: §3.1.3 · p. 6, §3.1.4 · p. 6

3.2 Checker Refinement

  • Checker refinement distills reports to relevant lines and trace paths, then uses specialized LLM agents to triage false positives and revise checkers.A refinement is accepted only if it removes the identified false-positive warnings while still distinguishing buggy from patched code.Source: §3.2 · p. 7
  • When a report is a false positive, the refinement agent adjusts checker logic to handle the missed code construct, as in the `unlikely()` null-check example.The revised checker must avoid the earlier false positive without losing its ability to detect the original vulnerability.Source: §3.2 · p. 7

4 Implementation

The implementation evaluation uses a manually classified benchmark of patch commits spanning ten bug categories. Checker validity and plausibility are assessed on the original patch and whole-kernel scans, with bounded sampling and refinement.

Input commit collection

  • The benchmark selection process defined 10 bug categories and required two authors to agree independently on each commit’s category.Researchers reviewed the first 20 matching commits per bug type and continued searching when fewer than five qualifying commits had been collected, where possible.Source: §4 · p. 7, Table 1 · p. 7

Few-shot examples and utility functions

  • Three end-to-end few-shot examples required approximately 40 person-hours to design and implement, and the system includes nine utility functions for checker development.The examples were a one-time effort intended to yield reusable examples.Source: §4 · p. 7

Validity and plausibility criteria

  • A checker is valid when it reports more bugs on pre-patch code than patched code, with fewer than 50 remaining patched-code reports by default.Plausibility requires fewer than 20 whole-kernel reports or an acceptable false-positive rate; refinement samples five warnings and allows up to three iterations.Source: §4 · pp. 7–8

5 Evaluation

The evaluation asks whether KNighter can synthesize high-quality checkers, find real kernel bugs, complement human-written checkers, and benefit from its key components. It measures checker quality, bug detection, and resource use, while also classifying checker failures.

Research questions

  • The evaluation poses four questions about checker quality, real-world kernel bug detection, complementarity with human-written checkers, and component effectiveness.The RQ list frames the evaluation’s scope.Source: §5 · p. 8

Evaluation metrics

  • Evaluation metrics cover checker validity, plausible-checker rate, real-world bug detection, and computational time and monetary cost.Validity checks whether a checker distinguishes original buggy code from its patched version; plausibility adds low false-positive rates or manageable report counts.Source: §5 · p. 8

Failure categories and setup

  • Checker failures are grouped as compilation failures, runtime errors, or semantic issues that cannot distinguish buggy from patched code.Experiments used Linux v6.13 with allyesconfig on a workstation running Ubuntu 20.04.5 LTS, with O3-mini as the default LLM backend.Source: §5 · p. 8

5.1 RQ1: Synthesized Checkers

Across 61 evaluated commits, KNighter produced valid checkers for 39 and plausible checkers for 37 after refinement. Its reported false positives and synthesis failures expose challenges in pattern precision, implementation, and complex bug classes.

5.1.1 Checker Synthesis

  • 39 of 61 commits yielded valid checkers, averaging 125.7 lines; 37 were path-sensitive, 13 region-sensitive, 16 used advanced state tracking, and two used AST travelers.Synthesis required 15.9 hours and cost about $0.24 per commit using O3-mini.Source: §5.1 · p. 8
  • Of 61 commits, 22 yielded no valid checker; inaccurate implementation caused 13 failures, inaccurate plans seven, and inaccurate bug patterns two.A common implementation issue was compiler inlining that prevented the checker from intercepting function calls such as `strcp` and `memset`.Source: §5.1 · p. 9

Limitations

  • KNighter has difficulty with buffer-overflow and use-after-free commits, as well as complex state-machine and concurrency issues.The paper attributes these challenges to precise compile-time value and buffer-bound reasoning, multi-threaded analysis, and locking schemes.Source: §5.1 · p. 9

5.1.2 Checker Refinement

  • 37 checkers were plausible after refinement: 26 qualified directly, and refinement succeeded for 11 of the remaining 13 valid checkers.The refinement pipeline completed 19 successful refinement steps, refining 84.6% of the initially non-plausible valid checkers.Source: §5.1 · p. 9

5.1 RQ1: Synthesized Checkers

  • Among 90 reports labeled as bugs, manual verification confirmed 61 true positives, for a 32.2% false-positive rate.Manual analysis found 29 false positives: 5 involved inaccurate patterns, 6 overly broad matching, and 18 trigger-condition management.Source: §5.1 · p. 9

5.2 RQ2: Detected Bugs

KNighter-synthesized checkers found 92 new Linux kernel bugs, including long-latent vulnerabilities across subsystems and bug classes. Case studies illustrate detection of use-after-free and buffer-overflow issues.

5.2 RQ2: Detected Bugs

  • 77 of 92 discovered bugs were confirmed, 57 were fixed, and 30 received CVE numbers.The remaining 15 were awaiting developer review.Source: §5.2.1 · p. 9

5.2.1 Overall.

  • 26 bugs had existed for over five years, and the average lifetime was 4.3 years.Drivers contained 67 of the 92 bugs; sound contained 10 and net contained 7.Source: §5.2.1 · p. 10, Figure 9 · p. 10
  • Checkers from 39 bug-fix commits found an average of 2.4 new bugs each, with five checkers finding at least five bugs apiece.Recurring error patterns generally yielded more findings than specialized fixes.Source: §5.2.1 · p. 10
  • A checker derived from a use-after-free patch found a similar bug in dm9000_drv_remove, assigned CVE-2025-21715.The bug involved use of private data after ndev was freed.Source: §5.2.2 · p. 10, Figure 10 · p. 11

5.2.2 Case Study.

  • A checker derived from a buffer-overflow patch found missing trailing-zero handling in nsim_nexthop_bucket_activity_write; the issue was fixed and assigned CVE-2024-50259.The omission could cause improper string handling and potential overflow.Source: §5.2.2 · p. 11, Figure 10 · p. 11

5.3 RQ3: Orthogonality with Smatch

KNighter and Smatch detected different bugs in the Linux kernel: Smatch found none of KNighter’s true-positive bugs, despite reporting thousands of errors and warnings.

5.3 RQ3: Orthogonality with Smatch

  • Smatch detected none of the true-positive bugs identified by KNighter, despite reporting 1970 errors and 2870 warnings across the kernel.The comparison ran Smatch over the entire codebase and manually inspected files where bugs were detected.Source: §5.3 · p. 11
  • Smatch’s check_deref uses static range analysis but misses that devm_kzalloc may return NULL under error conditions.The authors attribute the difference to Smatch not fully using Linux kernel domain knowledge embedded in historical patches.Source: §5.3 · p. 11

5.4 RQ4: Effectiveness of Components

Component evaluations examine KNighter’s triage agent and checker-synthesis choices. Multi-stage synthesis produced more valid checkers than single-stage synthesis, while model choice affected checker validity and syntax errors.

5.4 RQ4: Effectiveness of Components

  • The triage agent produced 7 true positives, 22 false positives, 50 true negatives, and zero false negatives across 79 reports.The reports came from 18 checkers; 21 other valid checkers generated no reports.Source: §5.4.1 · p. 11

5.4.1 Bug Triage Agent.

  • Five-way majority voting kept true positives at 7; a threshold of 4 reduced false positives from 22 to 20.A threshold of 3 kept 7 true positives but increased false positives to 24; the authors report only a slight shift overall.Source: §5.4.1 · pp. 11–12

5.4.2 Ablation Study.

  • Multi-stage synthesis yielded valid checkers for 12 commits versus 8 with single-stage synthesis, and had 28 syntax errors versus 52.The study sampled 20 commits, two from each of 10 bug types.Source: §5.4.2 · p. 12, Table 3 · p. 12
  • RAG example selection also generated valid checkers for 12 commits, comparable to fixed examples, but incurred approximately double the input/output token cost.RAG retrieved examples from a knowledge base of 118 official CSA checkers.Source: §5.4.2 · p. 12
  • O3-mini yielded 12 valid checkers, GPT-4o and DeepSeek-R1 generated 11 each, and Gemini-2-flash produced valid checkers for 4 commits, substantially worse.Gemini-2-flash frequently used non-existent CSA APIs and generated 130 syntax errors.Source: §5.4.2 · p. 12

6 Limitations and Discussion

KNighter’s checker synthesis faces challenges with complex temporal and interprocedural bug patterns, while its workflow is described as applicable beyond the Linux kernel under stated project and framework conditions.

6 Limitations and Discussion

  • Precise checkers remain difficult for state-machine bugs such as use-after-free and concurrency issues involving multithreaded code and locking schemes.The authors cite the need to understand temporal and interprocedural behavior.Source: §6 · p. 12
  • The authors propose formal state-machine abstractions and filtering for canonical, reusable bug fixes as ways to improve checker precision and synthesis.Source: §6 · p. 12
  • Applying the workflow to another project requires bug-fix history and a static-analysis framework as a synthesis target.The paper says the implementation can be adapted beyond C/C++ and Clang Static Analyzer, including to CodeQL or Semgrep.Source: §6 · p. 12

7 Related Work

KNighter differs from prior static-analysis work by synthesizing checkers from patches rather than relying on predefined rules, inferred specifications, or direct LLM scanning. Related approaches include runtime checks, traditional analyzers, and LLM-assisted analysis, each with distinct scope or scalability constraints.

7 Related Work

  • Runtime checker synthesis learns rules from test executions and concrete runtime states, whereas KNighter learns from source-code patches to cover potential execution paths.This includes corner cases rarely triggered during execution.Source: §7 · p. 13

7.1 Traditional Static Analysis

  • Prior kernel analyzers use predefined rules or models, infer deviations from common usage, or derive specifications from patches for separate checkers.These approaches may require substantial expertise, rely on majority-correct or similarity assumptions, or depend on existing analysis infrastructure.Source: §7.1 · p. 13
  • KNighter synthesizes the static analyzer itself from historical patches, learning both bug patterns and detection logic rather than relying on predefined rules or existing checkers.The approach can cover patch-demonstrated issues beyond interface misuse, including certain integer overflows and complex logic errors.Source: §7.1 · p. 13

7.2 LLM-Based Static Analysis

  • LLM-augmented tools assist human-developed analyzer cores, while direct LLM code analysis faces high costs and scalability challenges on systems such as the Linux kernel.KNighter instead generates reusable static checkers and uses closed-loop triage and refinement to improve precision.Source: §7.2 · pp. 13–14

8 Conclusion

KNighter synthesizes static checkers and has discovered new, long-latent bugs in the Linux kernel. The authors identify extensions beyond Linux, additional learning paradigms, and improved checker generation as future work.

8 Conclusion

  • 92 new, long-latent Linux kernel bugs were discovered; 77 were confirmed, 57 fixed, and 30 assigned CVE numbers.The authors report an average bug latency of 4.3 years in the paper context.Source: §8 · p. 14
  • KNighter synthesizes static analyzers rather than using LLMs to analyze massive codebases directly, which the authors describe as a scalable, reliable, and traceable paradigm.Source: §8 · p. 14
  • Future work could extend KNighter beyond the Linux kernel, incorporate additional learning paradigms, and refine checker generation for more complex bug patterns.Source: §8 · p. 14

Related papers

Loading 2503.09002v3…