TyPatch: Transforming Patches into Typestate Rules for Kernel Bug Detection

Details

Historical Linux patches encode knowledge about bug patterns that often recur in similar code. TyPatch exploits this by using an LLM not to generate a complete static analyzer, but to extract a simpler typestate rule from each patch: which object is tracked, what actions on it are valid, what transitions exist, and what constitutes a violation. A shared backend then executes all rules uniformly — handling object tracking, alias analysis, path-state maintenance, and interprocedural propagation. This separation of concerns is the key architectural contribution: the LLM only needs to recover defect semantics from the patch, not implement program analysis infrastructure. The result is dramatically more efficient: 88.3-90.1% fewer generation tokens versus state-of-the-art complete-checker workflows, while achieving 3.42-14.95x higher precision in initial report pools. Applied to Linux v6.16, TyPatch found 559 distinct bugs across all active rules. 121 of those have been confirmed by Linux kernel developers — a strong external validation that the discovered bugs are real. The approach generalizes across 38 patches in a matched comparison against the prior workflow. This is directly useful to security researchers and kernel contributors. The system reduces both the cost of generating checkers from patches and the false-positive rate that makes static analysis tooling painful to use in practice.