TyPatch: Transforming Patches into Typestate Rules for Kernel Bug Detection
cs.SE · cs.AI · cs.CR · cs.OS
Quick verdict
TyPatch turns kernel patches into LLM typestate rules for one shared analyzer: 559 bugs at 88-90% less cost than KNighter; initial precision just 4.7-9.1%.
Summary
TyPatch attacks the instability of LLM-generated complete static-analysis checkers, exemplified by KNighter, by separating patch-specific defect semantics from analyzer implementation. An LLM converts each historical Linux fix — its commit message, diff, and surrounding source — into a structured typestate rule naming the tracked object, actions, guards, transitions, and violation evidence; deterministic validation and repair yield a rule or NoRule. A shared C++/LLVM backend then executes every rule with alias-aware, path-sensitive, interprocedural propagation. On Linux v6.16, rule pools generated by GPT-5.5, DeepSeek-v4-pro, and Claude Opus 4.8 from 100 seed fixes report 559 distinct bugs, 121 of them developer-confirmed. On KNighter's 38-patch public benchmark, TyPatch constructs more artifacts with 88.3–90.1% fewer generation tokens, and its initial report pools reach 4.67%/9.11% precision against 0.31%/2.66% for KNighter (GPT-5.5/DeepSeek-v4-pro) — a 3.42–14.95× relative gain that still leaves over 90% false positives. Fidelity review finds 236/249 rules preserve the seed relation, and aligned rules produce 1,131 of 1,132 true positives. Limitations: rules cannot express numeric-bounds or concurrency semantics (a sequential stand-in for one concurrent UAF seed alone emitted 1,753 reports), SEAL is excluded, adjudication is author-performed without inter-annotator data, and kernel-scale scans demand heavy compute.
Review complete
Assessment at a glance
4
risk flags identified
● high 0
● medium 3
● low 1
5 strengths · 5 weaknesses · 5 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- Decoupling patch-specific defect semantics (LLM-generated typestate rules) from analyzer implementation (one shared backend) makes patch-to-checker construction more reliable and far cheaper than complete-checker generation.
- On Linux v6.16, rule pools from GPT-5.5, DeepSeek-v4-pro, and Claude Opus 4.8 over 100 seed fixes find 559 distinct bugs, 121 confirmed by kernel developers.
- In the matched 38-patch study, TyPatch constructs more artifacts, uses 88.3–90.1% fewer generation tokens, and achieves initial-pool precision of 4.67%/9.11% versus KNighter's 0.31%/2.66% under GPT-5.5/DeepSeek-v4-pro.
- 94.8% of generated rules (236/249) preserve their seed's core defect relation, and nearly all true positives (1,131 of 1,132) come from seed-aligned rules.
Strengths
Decoupling is empirically motivated, not just asserted
Section 2 shows for the cgbc patch that all 20 generated plans recovered the missing-null-check relation and all 20 checkers compiled, yet only 2/10 (GPT-5.5) and 0/10 (Opus 4.8) distinguished buggy from fixed seeds — pinpointing analyzer implementation, consistent with KNighter's own 13/22 implementation-failure attribution cited in §1.
Large-scale results with external validation
RQ1 reports 559 distinct bugs in Linux v6.16 across all eight families, 121 developer-confirmed; cross-model overlap is analyzed honestly (196 found by all three pools, 377 = 67.4% by at least two), with per-model precision given in Table 2 (8.71%/7.93%/7.59%).
Matched comparison is carefully instrumented
Fidelity is linked to outcomes
Full artifact release
Weaknesses
Absolute precision remains very low
Narrow expressiveness biases the comparison
No variance or inferential treatment of stochastic generation
Author-performed adjudication without protocol detail
Backend idealizations unquantified
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Scope & Claims
TyPatch (arXiv 2609.13728) is a systems/method paper on LLM-assisted static analysis for the Linux kernel. Central claim: generating a complete CSA checker per patch (KNighter, the SOTA) couples two hard tasks — recovering patch semantics and implementing analyzer machinery — and restricting the LLM to a declarative typestate rule executed by one shared alias-aware, path-sensitive backend improves yield, cost, and report quality. Evidence: (1) RQ1 — 559 distinct bugs in Linux v6.16 (commit 98a11dadac64) from 100 seed fixes × three LLMs, 121 developer-confirmed; (2) RQ2 — matched 38-patch comparison vs KNighter: 88.3–90.1% fewer generation tokens, initial-pool precision 4.67%/9.11% vs 0.31%/2.66% (GPT-5.5/DeepSeek-v4-pro); (3) RQ3 — fidelity audit of all 249 rules.
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 5 strengths & 5 weaknesses, analyzed in detail
- 4 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
What is TyPatch?
TyPatch is a system in which an LLM converts historical Linux kernel fix patches into structured typestate rules (tracked object, actions, guards, state transitions, violation evidence), which a single shared static-analysis backend — alias-aware and path-sensitive over LLVM IR — then executes to find similar bugs across the whole kernel, instead of generating a complete checker per patch.
How many bugs did TyPatch find in the Linux kernel?
The paper reports 559 distinct bugs in Linux v6.16 across eight defect families (null dereference, double action, missing release, refcount imbalance, uninitialized use, use-after-release, acquire-release order, publish-before-init), of which 121 were confirmed by kernel developers. Rules came from 100 seed fixes generated independently by GPT-5.5, DeepSeek-v4-pro, and Claude Opus 4.8.
How does TyPatch differ from KNighter?
KNighter asks an LLM to implement a complete Clang Static Analyzer checker per patch, combining defect semantics with analysis machinery. TyPatch restricts the LLM to a declarative typestate rule and reuses one shared analyzer. In a matched 38-patch comparison, TyPatch used 88.3–90.1% fewer generation tokens and reached higher initial report precision (4.67%/9.11% vs 0.31%/2.66% under GPT-5.5/DeepSeek-v4-pro), though absolute precision stays below 10% before triage.
Is TyPatch's code and data available?
Yes. The paper points to a project repository (github.com/THU-Agent/TyPatch) containing the rule synthesizer, shared backend, 100 seed commits, three frozen rule pools, and deduplication code, plus a Docker image with the Linux v6.16 source, LLVM IR, and compilation database needed to rerun scans.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- Provided extraction ends at a complete sentence in Appendix A.4 (after the Table 6 discussion of DeepSeek vs GPT-5.5 precision); any content beyond that point, if it exists, was not available for review.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.