DSAC: Effective Static Analysis of Sleep-in-Atomic-Context Bugs in Kernel Modules

Jia-Ju Bai, Yu-Ping Wang, Julia Lawall, Shi-Min Hu

TL;DR

This paper introduces DSAC, a novel static analysis tool designed to automatically detect "sleep-in-atomic-context" (SAC) bugs in operating system kernels. By combining hybrid flow analysis, heuristic-based interface extraction, and a unique path-checking mechanism, DSAC effectively identifies these critical bugs and even suggests patches, significantly reducing manual debugging effort and improving kernel reliability.

What Problem Does This Paper Address?

Operating system kernels are complex pieces of software where certain code sections, known as "atomic contexts" (e.g., when holding a spinlock or inside an interrupt handler), must execute very quickly to avoid blocking the entire system. If code within these critical sections performs an operation that might "sleep" (i.e., wait for an external event, like I/O), it can lead to severe system hangs or deadlocks. These "sleep-in-atomic-context" (SAC) bugs are notoriously difficult to find because they don't always manifest, are hard to reproduce, and require deep OS-specific knowledge to identify. Existing tools often miss these bugs or are not specifically designed to detect them.

Methods

DSAC employs a four-pronged approach to tackle SAC bugs:

  • Hybrid Flow Analysis: This technique intelligently combines flow-sensitive (examining every code path) and flow-insensitive (examining each line) analysis. Flow-sensitive analysis is used in critical areas where spinlocks are acquired or interrupt handlers are involved, ensuring accuracy. Flow-insensitive analysis is used elsewhere to maintain efficiency. This hybrid approach balances precision with performance.
  • Heuristics-Based Sleep-able Function Extraction: To identify functions that can potentially cause a sleep, DSAC uses heuristics. It analyzes call graphs and kernel comments to pinpoint functions that are likely to sleep. This is crucial because determining if a function sleeps often requires specialized knowledge.
  • Path-Check Bug Filtering: To reduce noise and false positives, DSAC uses a path-check method. It filters out duplicate bug reports by comparing code paths and identifies false positives by looking for common semantic patterns in conditional checks (e.g., checking a can_sleep parameter) that indicate a sleep operation is intentionally guarded.
  • Pattern-Based Patch Generation: For bugs identified, DSAC automatically generates recommended patches. It has learned four common patterns for fixing SAC bugs, focusing on replacing sleep-able functions with non-sleep alternatives or moving sleep-able operations outside of atomic contexts.

Datasets

The paper evaluates DSAC on:

  • Linux Kernel Drivers: Specifically, versions 3.17.2 and 4.11.1.
  • Linux Kernel File Systems and Network Modules.
  • FreeBSD 11.0 and NetBSD 7.1 Kernels.

No new benchmarks were introduced; the evaluation focused on applying DSAC to existing, real-world kernel codebases.

Key Insights and Ideas

  • The "Atomic Context" is Tricky: The paper highlights that even experienced kernel developers can introduce SAC bugs, underscoring the complexity of managing atomic contexts, especially across multiple function calls.
  • Heuristics are Key for Practicality: Relying solely on exhaustive analysis for sleep-able function identification would be too slow. The paper shows that well-chosen heuristics, combined with code analysis, can efficiently narrow down the search space.
  • False Positives are Manageable: While static analysis inherently faces false positives, DSAC's path-checking mechanism, informed by common kernel coding patterns, significantly reduces them.
  • Patch Generation is a Game-Changer: Automatically suggesting fixes, even for a subset of bugs, dramatically lowers the barrier to adoption and speeds up the development cycle. The identified patterns (P1 and P2) are simple yet effective for many common SAC bugs.

Key Results

DSAC successfully identified a significant number of real SAC bugs:

  • 401 new real bugs found across Linux, FreeBSD, and NetBSD kernels.
  • 272 of these bugs were confirmed by kernel developers.
  • 61 recommended patches were generated, with 43 successfully applied by kernel maintainers.
  • The false positive rate was remarkably low, around 6.3% for Linux drivers.
  • DSAC's analysis was efficient, taking less than 10 minutes for bug detection and patch generation on large codebases.

Limitations and Future Work

The authors acknowledge several limitations:

  • Macro Expansion: DSAC analyzes LLVM bytecode, meaning macros need to be expanded, which can complicate analysis. Future work aims to incorporate source code information to address this.
  • Function Pointers: DSAC currently struggles with function pointers. Alias analysis is proposed as a solution.
  • Incomplete Path Filtering: While effective, the path-check method cannot filter out all invalid code paths, leading to some false positives. Improving path condition checking is a future goal.
  • Limited Patching Patterns: DSAC currently only automatically generates patches for two of the four identified patterns (P1 and P2). Supporting more complex patterns (P3 and P4) involving moving code or changing lock types is a key area for future development.
  • Single Kernel Configuration: DSAC's analysis is tied to a specific kernel configuration, potentially missing bugs in configurations not analyzed.

Summary updated

Abstract

International audience
BibTeX
@inproceedings{bai2018dsac,
  author = {Jia-Ju Bai and Yu-Ping Wang and Julia Lawall and Shi-Min Hu},
  title = {{DSAC: Effective Static Analysis of Sleep-in-Atomic-Context Bugs in Kernel Modules}},
  booktitle = {USENIX ATC},
  year = {2018},
  url = {https://openreview.net/forum?id=ESRLGITNir},
}
Figure