TY - GEN
T1 - Progressive Scrutiny
T2 - 29th Annual Network and Distributed System Security Symposium, NDSS 2022
AU - Zhai, Yizhuo
AU - Hao, Yu
AU - Zhang, Zheng
AU - Chen, Weiteng
AU - Li, Guoren
AU - Qian, Zhiyun
AU - Song, Chengyu
AU - Sridharan, Manu
AU - Krishnamurthy, Srikanth V.
AU - Jaeger, Trent
AU - Yu, Paul
N1 - Publisher Copyright:
© 2022 29th Annual Network and Distributed System Security Symposium, NDSS 2022. All Rights Reserved.
PY - 2022
Y1 - 2022
N2 - The Linux kernel has a rapid development cycle, with 10 commits every hour, on average. While these updates provide new features and bug fixes, they can also introduce new bugs and security vulnerabilities. Recent techniques showed how to detect some types of vulnerabilities using static analysis, but these tools cannot run quickly enough to keep up with the pace of kernel development. Ideally, an incremental analysis technique could address this problem, by doing a complete analysis once and then only analyzing changed portions of the code subsequently. However, incremental analysis of the Linux kernel poses unique challenges, due to its enormous scale and the high precision required to reduce false positives. In this paper, we design and implement INCRELUX, a novel Linux kernel incremental analysis tool. It allows rapid vulnerability detection after each update, via targeted analysis of the new code and affected prior code, and also speeds the tracking of pre-existing bugs to understand how long they have been present, thereby increasing awareness of such bugs. Our approach hinges on a bottom-up, function-summary-based approach, which leverages the benefits of a one-time clean-slate, but expensive analysis of a prior Linux baseline. INCRELUX also uses an effective heuristic to apply symbolic execution to incremental results to improve precision. Via extensive experiments on the challenging problem of finding use-before-initialization (UBI) bugs, we showcase a number of benefits of INCRELUX: (a) we can rapidly check if any new releases introduce UBI bugs and help eliminate them early in the process. (b) we perform a historical analysis to determine when a bug was first introduced and when it was fixed (a critical procedure in bug triage in the Linux kernel). (c) we compare the incremental analysis results with a clean-slate analysis and show our approach yields nearly the exact same results, demonstrating its fidelity in addition to efficiency. While the clean-slate analysis took 106.45 hours, the incremental analysis was often completed within minutes, achieving an average 200× speed-up for the mainline kernel and 440× on average, when analyzing stable branches.
AB - The Linux kernel has a rapid development cycle, with 10 commits every hour, on average. While these updates provide new features and bug fixes, they can also introduce new bugs and security vulnerabilities. Recent techniques showed how to detect some types of vulnerabilities using static analysis, but these tools cannot run quickly enough to keep up with the pace of kernel development. Ideally, an incremental analysis technique could address this problem, by doing a complete analysis once and then only analyzing changed portions of the code subsequently. However, incremental analysis of the Linux kernel poses unique challenges, due to its enormous scale and the high precision required to reduce false positives. In this paper, we design and implement INCRELUX, a novel Linux kernel incremental analysis tool. It allows rapid vulnerability detection after each update, via targeted analysis of the new code and affected prior code, and also speeds the tracking of pre-existing bugs to understand how long they have been present, thereby increasing awareness of such bugs. Our approach hinges on a bottom-up, function-summary-based approach, which leverages the benefits of a one-time clean-slate, but expensive analysis of a prior Linux baseline. INCRELUX also uses an effective heuristic to apply symbolic execution to incremental results to improve precision. Via extensive experiments on the challenging problem of finding use-before-initialization (UBI) bugs, we showcase a number of benefits of INCRELUX: (a) we can rapidly check if any new releases introduce UBI bugs and help eliminate them early in the process. (b) we perform a historical analysis to determine when a bug was first introduced and when it was fixed (a critical procedure in bug triage in the Linux kernel). (c) we compare the incremental analysis results with a clean-slate analysis and show our approach yields nearly the exact same results, demonstrating its fidelity in addition to efficiency. While the clean-slate analysis took 106.45 hours, the incremental analysis was often completed within minutes, achieving an average 200× speed-up for the mainline kernel and 440× on average, when analyzing stable branches.
UR - http://www.scopus.com/inward/record.url?scp=85174990935&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85174990935&partnerID=8YFLogxK
U2 - 10.14722/ndss.2022.24380
DO - 10.14722/ndss.2022.24380
M3 - Conference contribution
AN - SCOPUS:85174990935
T3 - 29th Annual Network and Distributed System Security Symposium, NDSS 2022
BT - 29th Annual Network and Distributed System Security Symposium, NDSS 2022
PB - The Internet Society
Y2 - 24 April 2022 through 28 April 2022
ER -