DLOS: Effective Static Detection of Deadlocks in OS Kernels

Authors: 

Jia-Ju Bai, Tuo Li, and Shi-Min Hu, Tsinghua University

Abstract: 

Deadlocks in OS kernels can cause critical problems like performance degradation and system hangs. However, detecting deadlocks in OS kernels is quite challenging, due to high complexity of concurrent execution and large code bases of OS kernels. In this paper, we design a practical static analysis approach named DLOS, to effectively detect deadlocks in OS kernels. DLOS consists of three key techniques: (1) a summary-based lock-usage analysis to efficiently extract the code paths containing distinct locking constraints from kernel code; (2) a reachability-based comparison method to efficiently detect locking cycles from locking constraints; (3) a two-dimensional filtering strategy to effectively drop false positives by validating code-path feasibility and concurrency. We have evaluated DLOS on Linux 5.10, and find 54 real deadlocks, with a false positive rate of 17%. We have reported these deadlocks to Linux kernel developers, and 31 of them have been confirmed.

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 {280756,
author = {Jia-Ju Bai and Tuo Li and Shi-Min Hu},
title = {{DLOS}: Effective Static Detection of Deadlocks in {OS} Kernels},
booktitle = {2022 USENIX Annual Technical Conference (USENIX ATC 22)},
year = {2022},
isbn = {978-1-939133-29-47},
address = {Carlsbad, CA},
pages = {367--382},
url = {https://www.usenix.org/conference/atc22/presentation/bai},
publisher = {USENIX Association},
month = jul,
}

Presentation Video