SymBisect: accurate bisection for fuzzer-exposed vulnerabilities
AUTHORs: 
Zheng Zhang, Yu Hao, Weiteng Chen, Xiaochen Zou, Xingyu Li, Haonan Li, Yizhuo Zhai, Zhiyun Qian, Billy LauAuthors Info & Claims
Article No.: 140, Pages 2493 - 2510
Abstract
The popularity of fuzzing has led to its tight integration into the software development process as a routine part of the build and test, i.e., continuous fuzzing. This has resulted in a substantial increase in the reporting of bugs in open-source software, including the Linux kernel. To keep up with the volume of bugs, it is crucial to automatically analyze the bugs to assist developers and maintainers. Bug bisection, i.e., locating the commit that introduced a vulnerability, is one such analysis that can reveal the range of affected software versions and help bug prioritization and patching. However, existing automated solutions fall short in a number of ways: most of them either (1) directly run the same PoC on older software versions without adapting to changes in bug-triggering conditions and are prone to broken dynamic environments or (2) require patches that may not be available when the bug is discovered. In this work, we take a different approach to looking for evidence of fuzzer-exposed vulnerabilities by looking for the underlying bug logic. In this way, we can perform bug bisection much more precisely and accurately. Specifically, we apply under-constrained symbolic execution with several principled guiding techniques to search for the presence of the bug logic efficiently. We show that our approach achieves significantly better accuracy than the state-of-the-art solution by 16% (from 74.7% to 90.7%).
References
[1]
Linux Kernel Faces Reduction in Long-Term Support Due to Maintenance Challenges. https://www.linuxjournal.com/content/linux-kernel-reduction-longterm-support.
[2]
SymBisect Source Code. https://github.com/zhangzhenghsy/SymBisect.
[3]
Syzbot Bisection. https://android.googlesource.com/platform/external/syzkaller/+/HEAD/docs/syzbot.md#bisection.
[4]
Syzbot Bisection Motivation. https://lore.kernel.org/all/CACT4Y+Y3nN=nLEkHXLFcX7vxp_vs1JrD=8auJ3cX9we6TQHO+w@mail.gmail.com/T/#u.
[5]
V0Finder Source Code. https://github.com/WOOSEUNGHOON/V0Finderpublic.
[6]
VSZZ Source Code. https://figshare.com/ndownloader/files/31748777.
[7]
R. Abreu, F. Ivančić, F. Nikšić, H. Ravanbakhsh, and R. Viswanathan. Reducing time-to-fix for fuzzer bugs. In 2021 36th IEEE/ACM International Conference on Automated Software Engineering (ASE), pages 1126-1130. IEEE, 2021.
[8]
Q. U. Ain, W. H. Butt, M. W. Anwar, F. Azam, and B. Maqbool. A systematic review on code clone detection. IEEE access, 7:86121-86144, 2019.
[9]
N. Alexopoulos, M. Brack, J. P. Wagner, T. Grube, and M. Muhlhauser. How long do vulnerabilities live in the code? a {Large-Scale} empirical measurement study on {FOSS} vulnerability lifetimes. In 31st USENIX Security Symposium (USENIX Security 22), pages 359-376, 2022.
[10]
G. An, J. Hong, N. Kim, and S. Yoo. Fonte: Finding bug inducing commits from failures. In 2023 IEEE/ACM 45th International Conference on Software Engineering (ICSE), pages 589-601. IEEE, 2023.
[11]
C. Ascherm, S. Schumilo, T. Blazytko, R. Gawlik, and T. Holz. Fuzzing with input-to-state correspondence. NDSS, 2019.
[12]
L. Bao, X. Xia, A. E. Hassan, and X. Yang. V-szz: automatic identification of version ranges affected by cve vulnerabilities. In Proceedings of the 44th International Conference on Software Engineering, pages 2352-2364, 2022.
[13]
R. Bhagwan, R. Kumar, C. S. Maddila, and A. A. Philip. Orca: Differential bug localization in {Large-Scale} services. In 13th USENIX Symposium on Operating Systems Design and Implementation (OSDI 18), pages 493-509, 2018.
[14]
B. Bowman and H. H. Huang. Vgraph: A robust vulnerable code clone detection system using code property triplets. In 2020 IEEE European Symposium on Security and Privacy (EuroS & P), pages 53-69. IEEE, 2020.
[15]
W. Chen, X. Zou, G. Li, and Z. Qian. Koobe: Towards facilitating exploit generation of kernel out-of-bounds write vulnerabilities. USENIX Security, 2020.
[16]
D. E. Cristian Cadar, Daniel Dunbar. Klee: Unassisted and automatic generation of high-coverage tests for complex systems programs. USENIX Symposium on Operating Systems Design and Implementation (OSDI 2008) December 8-10, 2008, San Diego, CA, USA.
[17]
J. Dai, Y. Zhang, H. Xu, H. Lyu, Z. Wu, X. Xing, and M. Yang. Facilitating vulnerability assessment through poc migration. In Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security, pages 3300-3317, 2021.
[18]
D. E. David A Ramos. Under-constrained symbolic execution: Correctness checking for real code. USENIX Security, 2015.
[19]
Eng Chen and H. Chen. Angora: Efficient fuzzing by principled search. In 2018 IEEE Symposium on Security and Privacy (SP). IEEE, 2018.
[20]
C. Fang, Z. Liu, Y. Shi, J. Huang, and Q. Shi. Functional code clone detection with syntax and semantics fusion learning. In Proceedings of the 29th ACM SIGSOFT international symposium on software testing and analysis, pages 516-527, 2020.
[21]
X. Ge, W. Cui, and T. Jaeger. Griffin: Guarding control flows using intel processor trace. In Proceedings of the Twenty-Second International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS '17, 2017.
[22]
Google. Google syzbot. https://syzkaller.appspot.com/upstream/.
[23]
Google. Google syzkaller. https://github.com/google/syzkaller.
[24]
Y. Hao, G. Li, X. Zou, W. Chen, S. Zhu, Z. Qian, and A. A. Sani. Syzdescribe: Principled, automated, static generation of syscall descriptions for kernel drivers. In 2023 IEEE Symposium on Security and Privacy (SP), pages 3262-3278. IEEE Computer Society, 2023.
[25]
J. Jang, A. Agrawal, and D. Brumley. Redebug: finding unpatched code clones in entire os distributions. Oakland'12.
[26]
S. Kim, S. Woo, H. Lee, and H. Oh. Vuddy: A scalable approach for vulnerable code clone discovery. Oakland' 17.
[27]
X. Li, Z. Zhang, Z. Qian, T. Jaeger, and C. Song. An investigation of patch porting practices of the linux kernel ecosystem. arXiv preprint arXiv:2402.05212, 2024.
[28]
Z. Li, D. Zou, S. Xu, H. Jin, H. Qi, and J. Hu. Vulpecker: an automated vulnerability detection system based on code similarity analysis. ACSAC' 16.
[29]
K. Lu and H. Hu. Where does it go? refining indirect-call targets with multi-layer type analysis. In Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, pages 1867-1881, 2019.
[30]
V. Murali, L. Gross, R. Qian, and S. Chandra. Industry-scale ir-based bug localization: A perspective from facebook. In 2021 IEEE/ACM 43rd International Conference on Software Engineering: Software Engineering in Practice (ICSE-SEIP), pages 188-197. IEEE, 2021.
[31]
H. Peng, Y. Shoshitaishvili, and M. Payer. Tfuzz: fuzzing by program transformation. In IEEE Symposium on Security and Privacy. IEEE, 2018.
[32]
D. A. Ramos and D. Engler. Under-constrained symbolic execution: Correctness checking for real code. USENIX Security'15.
[33]
D. A. Ramos and D. R. Engler. Under-constrained symbolic execution: Correctness checking for real code. In J. Jung and T. Holz, editors, 24th USENIX Security Symposium, USENIX Security 15, Washington, D.C., USA, August 12-14, 2015, pages 49-64. USENIX Association, 2015.
[34]
G. Rodríguez-Pérez, G. Robles, A. Serebrenik, A. Zaidman, D. M. Germán, and J. M. Gonzalez-Barahona. How bugs are born: a model to identify how bugs are introduced in software components. Empirical Software Engineering, 25:1294-1340, 2020.
[35]
C. K. Roy, J. R. Cordy, and R. Koschke. Comparison and evaluation of code clone detection techniques and tools: A qualitative approach. Science of computer programming, 74(7):470-495, 2009.
[36]
H. Sajnani, V. Saini, J. Svajlenko, C. K. Roy, and C. V. Lopes. Sourcerercc: Scaling code clone detection to big-code. In Proceedings of the 38th international conference on software engineering, pages 1157-1168, 2016.
[37]
E. C. H. L. Seunghoon Woo, Hyunji Hong. Movery: A precise approach for modified vulnerable code clone discovery from modified open-source software components. USENIX Security, 2022.
[38]
Y. Shi, Y. Zhang, T. Luo, X. Mao, and M. Yang. Precise (un) affected version analysis for web vulnerabilities. In 37th IEEE/ACM International Conference on Automated Software Engineering, pages 1-13, 2022.
[39]
G. Shobha, A. Rana, V. Kansal, and S. Tanwar. Code clone detection—a systematic review. Emerging Technologies in Data Mining and Information Security: Proceedings of IEMIS 2020, Volume 2, pages 645-655, 2021.
[40]
J. Sliwerski, T. Zimmermann, and A. Zeller. When do changes induce fixes? ACM sigsoft software engineering notes, 30(4):1-5, 2005.
[41]
D. Trabish, S. Itzhaky, and N. Rinetzky. A bounded symbolic-size model for symbolic execution. In D. Spinellis, G. Gousios, M. Chechik, and M. D. Penta, editors, ESEC/FSE, pages 1190-1201. ACM, 2021.
[42]
D. Wang, Z. Zhang, H. Zhang, Z. Qian, S. V. Krishnamurthy, and N. Abu-Ghazaleh. Syzvegas: Beating kernel fuzzing odds with reinforcement learning. USENIX Security, 2021.
[43]
M. Wen, R. Wu, and S.-C. Cheung. Locus: Locating bugs from software changes. In Proceedings of the 31st IEEE/ACM International Conference on Automated Software Engineering, pages 262-273, 2016.
[44]
S. Wi, S. Woo, J. J. Whang, and S. Son. Hiddencpg: large-scale vulnerable clone detection using subgraph isomorphism of code property graphs. In Proceedings of the ACM Web Conference 2022, pages 755-766, 2022.
[45]
S. Woo, D. Lee, S. Park, H. Lee, and S. Dietrich. Vøfinder: Discovering the correct origin of publicly reported software vulnerabilities. In USENIX Security Symposium, pages 3041-3058, 2021.
[46]
Q. Wu, Y. He, S. McCamant, and K. Lu. Precisely characterizing security impact in a flood of patches via symbolic rule comparison. NDSS, 2020.
[47]
R. Wu, M. Wen, S.-C. Cheung, and H. Zhang. Changelocator: locate crash-inducing changes based on crash reports. Empirical Software Engineering, 23:2866-2900, 2018.
[48]
W. Wu, Y. Chen, J. Xu, X. Xing, X. Gong, and W. Zou. {FUZE}: Towards facilitating exploit generation for kernel {Use-After-Free} vulnerabilities. In 27th USENIX Security Symposium (USENIX Security 18), pages 781-797, 2018.
[49]
Y. Xiao, B. Chen, C. Yu, Z. Xu, Z. Yuan, F. Li, B. Liu, Y. Liu, W. Huo, W. Zou, et al. {MVP}: Detecting vulnerabilities using {Patch-Enhanced} vulnerability signatures. In 29th USENIX Security Symposium (USENIX Security 20), pages 1165-1182, 2020.
[50]
M. Xu, C. Qian, K. Lu, M. Backes, and T. Kim. Precise and scalable detection of double-fetch bugs in os kernels. In 2018 IEEE Symposium on Security and Privacy (SP), pages 661-678. IEEE, 2018.
[51]
T. Yavuz. Sift: A tool for property directed symbolic execution of multithreaded software. In 2022 IEEE Conference on Software Testing, Verification and Validation (ICST), pages 433-443, 2022.
[52]
Y. Zhai, Y. Hao, H. Zhang, D. Wang, C. Song, Z. Qian, M. Lesani, S. V. Krishnamurthy, and P. L. Yu. Ubitect: a precise and scalable method to detect use-before-initialization bugs in linux kernel. In ESEC/FSE, pages 221-232. ACM, 2020.
[53]
Y. Zhai, Y. Hao, Z. Zhang, W. Chen, G. Li, Z. Qian, C. Song, M. Sridharan, S. V. Krishnamurthy, T. Jaeger, and P. L. Yu. Progressive scrutiny: Incremental detection of UBI bugs in the linux kernel. In 29th Annual Network and Distributed System Security Symposium, NDSS 2022, San Diego, California, USA, April 24-28, 2022. The Internet Society, 2022.
[54]
H. Zhang and Z. Qian. Precise and accurate patch presence test for binaries. USENIX Security, 2018.
[55]
H. Zhang and K. Sakurai. A survey of software clone detection from security perspective. IEEE Access, 9:48157-48173, 2021.
[56]
D. Zou, H. Qi, Z. Li, S. Wu, H. Jin, G. Sun, S. Wang, and Y. Zhong. Scvd: A new semantics-based approach for cloned vulnerable code detection. In DIMVA, pages 325-344. Springer, 2017.
[57]
X. Zou, G. Li, W. Chen, H. Zhang, and Z. Qian. {SyzScope}: Revealing {High-Risk} security impacts of {Fuzzer-Exposed} bugs in linux kernel. In 31st USENIX Security Symposium (USENIX Security 22), pages 3201-3217, 2022.
Index Terms
- SymBisect: accurate bisection for fuzzer-exposed vulnerabilities
Index terms have been assigned to the content through auto-classification.
Recommendations
Bug localization via searching crowd-contributed code
Internetware '14: Proceedings of the 6th Asia-Pacific Symposium on InternetwareBug localization, i.e., locating bugs in code snippets, is a frequent task in software development. Although static bug-finding tools are available to reduce manual effort in bug localization, these tools typically detect bugs with known project-...
Effective Bug Triage Based on Historical Bug-Fix Information
ISSRE '14: Proceedings of the 2014 IEEE 25th International Symposium on Software Reliability EngineeringFor complex and popular software, project teams could receive a large number of bug reports. It is often tedious and costly to manually assign these bug reports to developers who have the expertise to fix the bugs. Many bug triage techniques have been ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 2024 The USENIX Association.
Sponsors
- Bloomberg Engineering
- Google Inc.
- NSF
- Futurewei Technologies
- IBM
Publisher
USENIX Association
United States
Publication History
Published: 12 August 2024
Qualifiers
- Research-article
- Research
- Refereed limited
Acceptance Rates
Overall Acceptance Rate 40 of 100 submissions, 40%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 19 Feb 2025