TyPatch improves Linux kernel bug detection using patch-based typestate rules
TyPatch: Transforming Patches into Typestate Rules for Kernel Bug Detection
Software EngineeringArtificial IntelligenceCryptography and SecurityOperating Systems
Summary
Detecting bugs in the Linux kernel is hard because some bugs involve complex interactions within the code. The authors created TyPatch, a tool that turns past bug fixes into clear rules about how objects in the code should behave. Instead of building big, complicated checkers for each bug, TyPatch separates the bug knowledge from the checking process. This approach helps find many bugs more efficiently and with fewer mistakes than previous methods.
What this means in practice
- •For kernel developers: Find more reliable and precise bugs in Linux kernel code by applying typestate rules derived from historical patches.
- •For software security teams: Enhance automated vulnerability detection in large codebases by converting past fix patches into reusable semantic rules.
Authors
Ruoyu Wang, Tuo Li, Jia Li
Abstract
Historical Linux kernel patches capture defect knowledge that applies beyond their original repair sites. Recent work has shown that large language models (LLMs) can generate static-analysis checkers from historical patches and use them to uncover new kernel bugs. However, complete-checker generation requires the model both to recover the defect semantics expressed by a patch and to implement sophisticated program-analysis machinery, including object tracking, alias analysis, path-state maintenance, and interprocedural propagation. Coupling these responsibilities in a single end-to-end code-generation task can turn a simple defect rule into an unstable and expensive analyzer-implementation problem. To address this problem, we present TyPatch, which decouples patch-specific defect semantics from analyzer implementation. An LLM translates each patch into a typestate rule specifying its tracked object, actions, guards, transitions, and violations. A shared backend then executes these rules, binding their actions to program events, tracking object identity across aliases, propagating typestate along program paths, and producing reports for all rules. On Linux v6.16, TyPatch finds 559 distinct bugs, 121 of which have been confirmed by kernel developers. In a matched 38-patch comparison with the state-of-the-art complete-checker construction workflow, TyPatch uses 88.3-90.1% fewer generation tokens, while its initial report pools achieve 3.42-14.95$\times$ the precision of those produced by that workflow.