SPATA: Effective OS Bug Detection with Summary-Based, Alias-Aware, and Path-Sensitive Typestate Analysis
ACM Transactions on Computer Systems · 30.11.2024 · 42 (3-4) · 1-40
DOI: 10.1145/3695250 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Computer Systems, online erschienen am 13.11.2024. Verfasst von Tuo Li und 3 weiteren Autor:innen. Die Arbeit wurde bisher 6-mal zitiert (Crossref) und nennt 108 Literaturangaben. Gefördert von: CCF-Huawei Populus Grove Fund, CCF-Tencent Rhino-Bird Open Research Fund.
Abstract (Originalsprache)
The operating system (OS) is the cornerstone for computer systems. It manages hardware and provides fundamental service for user-level applications. Thus, detecting bugs in OSes is important to improve the reliability of computer systems. Static typestate analysis is a common technique for detecting various types of bugs, but it is often inaccurate or unscalable for large-size OS code, due to imprecision of identifying alias relationships as well as high costs of typestate tracking, path-feasibility validation, and inter-procedural analysis. In this article, 1 we present SPATA, a novel summary-based, alias-aware, and path-sensitive typestate analysis framework to detect OS bugs. To identify precise alias relationships in the OS code, SPATA performs a path-based alias analysis based on control-flow paths and access paths. With these alias relationships, SPATA reduces the costs of typestate tracking and path-feasibility validation, to accelerate path-sensitive typestate analysis for accurate bug detection. Moreover, SPATA uses an alias-summary-based analysis to accelerate inter-procedural bug detection, without time-consuming alias analysis across functions. We have evaluated SPATA on the Linux kernel and three popular IoT OSes, and it finds 651 real bugs with a false-positive rate of 18%. Besides, our alias-summary-based analysis achieves a 6.7x speedup in bug detection compared to non-summary-based analysis.
Förderung
- CCF-Huawei Populus Grove Fund
- CCF-Tencent Rhino-Bird Open Research Fund
Zitieren
APA
Li, T., Bai, J., Sui, Y., & Hu, S. (2024). SPATA: Effective OS Bug Detection with Summary-Based, Alias-Aware, and Path-Sensitive Typestate Analysis. ACM Transactions on Computer Systems, 42(3-4), 1-40. https://doi.org/10.1145/3695250
Vancouver
Li T, Bai J, Sui Y, Hu S. SPATA: Effective OS Bug Detection with Summary-Based, Alias-Aware, and Path-Sensitive Typestate Analysis. ACM Transactions on Computer Systems. 2024;42(3-4):1-40. doi:10.1145/3695250
BibTeX
@article{Li2024,
author = {Li, Tuo and Bai, Jia-Ju and Sui, Yulei and Hu, Shi-Min},
title = {SPATA: Effective OS Bug Detection with Summary-Based, Alias-Aware, and Path-Sensitive Typestate Analysis},
journal = {ACM Transactions on Computer Systems},
year = {2024},
volume = {42},
number = {3-4},
pages = {1--40},
doi = {10.1145/3695250}
}
EUVIMED