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

Authors: 

Jia-Ju Bai and Yu-Ping Wang, Tsinghua University; Julia Lawall, Sorbonne Université/Inria/LIP6; Shi-Min Hu, Tsinghua University

Abstract: 

In a modern OS, kernel modules often use spinlocks and interrupt handlers to monopolize a CPU core for executing concurrent code in atomic context. In this situation, if the kernel module performs an operation that can sleep at runtime, a system hang may occur in execution. We refer to this kind of concurrency bug as a sleep-in-atomic-context (SAC) bug. In practice, SAC bugs have received insufficient attention and are hard to find, as they do not always cause problems in real executions.

In this paper, we propose a practical static approach named DSAC, to effectively detect SAC bugs and automatically recommend patches to help fix them. DSAC uses four key techniques: (1) a hybrid of flow-sensitive and -insensitive analysis to perform accurate and efficient code analysis; (2) a heuristics-based method to accurately extract sleep-able kernel interfaces that can sleep at runtime; (3) a path-check method to effectively filter out repeated reports and false bugs; (4) a pattern-based method to automatically generate recommended patches to help fix the bugs.

We evaluate DSAC on kernel modules (drivers, file systems, and network modules) of the Linux kernel, and on the FreeBSD and NetBSD kernels, and in total find 401 new real bugs. 272 of these bugs have been confirmed by the relevant kernel maintainers, and 43 patches generated by DSAC have been applied by kernel maintainers.

Open Access Media

USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.

BibTeX
@inproceedings {215947,
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 = {2018 {USENIX} Annual Technical Conference ({USENIX} {ATC} 18)},
year = {2018},
isbn = {978-1-931971-44-7},
address = {Boston, MA},
pages = {587--600},
url = {https://www.usenix.org/conference/atc18/presentation/bai},
publisher = {{USENIX} Association},
month = jul,
}

Presentation Audio