SHFuzz: Selective Hybrid Fuzzing with Branch Scheduling Based on Binary Instrumentation
Source abstract
Abstract
Hybrid fuzzing is a popular software testing technique that combines random fuzzing with concolic execution. It is widely used in the security domain known for its ability to find deeply hidden vulnerabilities and reach high code coverage. Hybrid fuzzing is based on negating branches in the execution path of a specific input to generate new test cases. However, due to numerous inputs and related branches, it does not show the best of its effectiveness without input and branch selection methods. In this paper, we systematically analyze the branch scheduling problem in the internal attributes of hybrid fuzzing, focusing on the synchronization mechanism. To solve the problems, we propose the Selective Hybrid Fuzzing (SHF) approach with branch scheduling based on binary instrumentation. There are two major parts to the SHF approach: (1) we propose a critical branch selection algorithm to select critical branches by three metrics: hit accuracy, solvability, and complexity; (2) we propose a priority score calculation algorithm to select inputs by the number of critical branches. With the SHF approach, we choose only the branches that can be negated to generate new coverage, instead of repeatedly executing the same branches and generating duplicates of inputs. We implement a hybrid fuzzer called SHFuzz with our SHF approach and compare it with the state-of-the-art hybrid fuzzer QSYM. In the evaluation, SHFuzz outperforms QSYM in 20 real-world applications from the Google Fuzzer Test Suite and other program suites in a 12 h test. On average, SHFuzz achieves 8.40% more code coverage and 100 more unique crashes in each application. Our work also finds existing vulnerabilities 7.85× faster than QSYM. We also find new bugs by SHFuzz, which QSYM fails to find. Our evaluation shows that the selective hybrid fuzzing approach can reduce the number of branches executed in concolic execution, enhancing hybrid fuzzing on code coverage and bug finding capabilities.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Software Testing and Debugging Techniques · Advanced Malware Detection Techniques · Software Reliability and Analysis Research
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
College of Computer, National University of Defense Technology, Changsha 410073, China
Funding
National Key Research and Development Program of China · Natural Science Foundation of Hunan Province in China · Natural Science Foundation of China
References (39)
Show source-provided references
1. Klees, G., Ruef, A., Cooper, B., Wei, S., and Hicks, M. (2018, January 15–19). Evaluating Fuzz Testing. Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, Toronto, ON, Canada.10.1145/3243734.3243804 ↗
2. Michal, Z. (2020, May 20). American Fuzzy Lop (AFL). Available online: http://lcamtuf.coredump.cx/afl/.
3. Rawat, S., Jain, V., Kumar, A., Cojocar, L., Giuffrida, C., and Bos, H. (March, January 26). VUzzer: Application-Aware Evolutionary Fuzzing. Proceedings of the NDSS Symposium 2017, San Diego, CA, USA.10.14722/ndss.2017.23404 ↗
4. Aschermann, C., Schumilo, S., Blazytko, T., Gawlik, R., and Holz, T. (2019, January 24–27). REDQUEEN: Fuzzing with Input-to-State Correspondence. Proceedings of the 26th Annual Network and Distributed System Security Symposium, San Francisco, CA, USA.10.14722/ndss.2019.23371 ↗
5. Chen, P., and Chen, H. (2018, January 20–24). Angora: Efficient fuzzing by principled search. Proceedings of the IEEE Symposium on Security and Privacy(SP), San Francisco, CA, USA.10.1109/SP.2018.00046 ↗
6. Godefroid, P., Kiezun, A., and Levin, M.Y. (2008, January 7–13). Grammar-based whitebox fuzzing. Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, Tucson, AZ, USA.10.1145/1375581.1375607 ↗
7. Blazytko, T., Bishop, M., Aschermann, C., Cappos, J., Schlogel, M., Korshun, N., Abbasi, A., Schweighauser, M., Schinzel, S., and Schumilo, S. (2019, January 14–16). GRIMOIRE: Synthesizing Structure while Fuzzing. Proceedings of the USENIX Security, Santa Clara, CA, USA.
8. Gopinath, R., Mathis, B., Hoschele, M., Kampmann, A., and Zeller, A. (2018). Sample-Free Learning of Input Grammars for Comprehensive Software Fuzzing. arXiv.
9. Stephens, N., Grosen, J., Salls, C., Dutcher, A., Wang, R., Corbetta, J., Shoshitaishvili, Y., Kruegel, C., and Vigna, G. (2016, January 21–24). Driller: Augmenting Fuzzing through Selective Symbolic Execution. Proceedings of the NDSS, San Diego, CA, USA.10.14722/ndss.2016.23368 ↗
10. Yun, I., Lee, S., Xu, M., Jang, Y., and Kim, T. (2018, January 15–17). QSYM: A Practical Concolic Execution Engine Tailored for Hybrid Fuzzing. Proceedings of the USENIX Security, Baltimore, MD, USA.
11. Zhao, L., Duan, Y., Yin, H., and Xuan, J. (2019, January 24–27). Send Hardest Problems My Way: Probabilistic Path Prioritization for Hybrid Fuzzing. Proceedings of the NDSS, San Diego, CA, USA.10.14722/ndss.2019.23504 ↗
12. The S2E Platform: Design, Implementation, and Applications10.1145/2110356.2110358 ↗
13. Saudel, F., and Salwan, J. (2015, January 3–5). Triton: A Dynamic Symbolic Execution Framework. Proceedings of the Symposium sur la sécurité des Technologies de l’Information et Des Communications, SSTIC, Rennes, France.
14. Shoshitaishvili, Y., Wang, R., Salls, C., Stephens, N., Polino, M., Dutcher, A., John, G., Feng, S., Hauser, C., and Kruegel, C. (2016, January 22–26). SoK: (State of) The Art of War: Offensive Techniques in Binary Analysis. Proceedings of the IEEE Symposium on Security and Privacy(SP), San Jose, CA, USA.10.1109/SP.2016.17 ↗
15. Majumdar, R., and Sen, K. (2007, January 20–26). Hybrid Concolic Testing. Proceedings of the 29th International Conference on Software Engineering, Minneapolis, MN, USA.10.1109/ICSE.2007.41 ↗
16. Sen, K. (2007, January 5–9). Concolic testing. Proceedings of the Twenty-Second IEEE/ACM International Conference on Automated Software Engineering, Atlanta, GA, USA.10.1145/1321631.1321746 ↗
17. A Survey of Symbolic Execution Techniques10.1145/3182657 ↗
18. De Moura, L., and Bjorner, N. (April, January 29). Z3: An efficient SMT solver. Proceedings of the International conference on Tools and Algorithms for the Construction and Analysis of Systems, Budapest, Hungary.
19. Wang, X., Sun, J., Chen, Z., Zhang, P., Wang, J., and Lin, Y. (June, January 27). Towards optimal concolic testing. Proceedings of the 2018 IEEE/ACM 40th International Conference on Software Engineering (ICSE), Gothenburg, Sweden.10.1145/3180155.3180177 ↗
20. (2020, May 20). Google Fuzzer Test Suite. Available online: https://github.com/google/fuzzer-test-suite/.
21. Gan, S., Zhang, C., Qin, X., Tu, X., Li, K., Pei, Z., and Chen, Z. (2018, January 20–24). CollAFL: Path Sensitive Fuzzing. Proceedings of the IEEE Symposium on Security and Privacy (SP), San Francisco, CA, USA.10.1109/SP.2018.00040 ↗
22. Rebert, A., Cha, S.K., Avgerinos, T., Foote, J., Warren, D., Grieco, G., and Brumley, D. (2014, January 20–22). Optimizing seed selection for fuzzing. Proceedings of the 23rd USENIX Security, San Diego, CA, USA.
23. Eddington, M. (2020, May 20). Peach Fuzzer. Available online: http://www.peachfuzzer.com/.
24. Serebryany, K. (2016, January 3–4). Continuous fuzzing with libfuzzer and addresssanitizer. Proceedings of the IEEE Cybersecurity Development (SecDev), Boston, MA, USA.10.1109/SecDev.2016.043 ↗
25. Swiecki, R. (2020, May 20). Honggfuzz. Available online: http://code.google.com/p/honggfuzz.
26. Coverage-Based Greybox Fuzzing as Markov Chain10.1109/TSE.2017.2785841 ↗
27. (2020, May 20). QSYM: A Practical Concolic Execution Engine Tailored for Hybrid Fuzzing. Available online: https://github.com/sslab-gatech/qsym.
28. (2020, May 20). Pin: A Dynamic Binary Instrumentation Tool. Available online: https://software.intel.com/en-us/articles/pin-a-dynamic-binary-instrumentation-tool.
29. Pin: Building Customized Program Analysis Tools with Dynamic Instrumentation10.1145/1064978.1065034 ↗
30. (2020, May 20). VUzzer(64) Version 1.0. Available online: https://github.com/vusec/vuzzer64.
31. Kemerlis, V.P., Portokalidis, G., Jee, K., and Keromytis, A.D. (2012, January 3–4). Libdft: Practical Dynamic Data Flow Tracking for Commodity Systems. Proceedings of the ACM SIGPLAN/SIGOPS International Conference on Virtual Execution Environments, London, UK.10.1145/2151024.2151042 ↗
32. (2020, May 20). Bug 25447—Objcopy: Free() Invalid Pointer in _bfd_coff_free_symbols. Available online: https://sourceware.org/bugzilla/show_bug.cgi?id=25447.
33. (2020, May 20). Sanitizercoverage: Clang documentation. Available online: https://clang.llvm.org/docs/SanitizerCoverage.html.
34. Bohme, M., Pham, V., Nguyen, M., and Roychoudhury, A. (November, January 30). Directed Greybox Fuzzing. Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, Dallas, TX, USA.10.1145/3133956.3134020 ↗
35. Wang, S., Nam, J., and Tan, L. (2017, January 4–8). QTEP: Quality-aware test case prioritization. Proceedings of the 2017 11th Joint Meeting on Foundations of Software Engineering, Paderborn, Germany.10.1145/3106237.3106258 ↗
36. Chen, Y., Li, P., Xu, J., Guo, S., Zhou, R., Zhang, Y., Wei, T., and Lu, L. (2020, January 18–21). SAVIOR: Towards Bug-Driven Hybrid Testing. Proceedings of the 41st IEEE Symposium on Security and Privacy, San Francisco, CA, USA.10.1109/SP40000.2020.00002 ↗
37. Han, W., Rahman, M.L., Chen, Y., Song, C., Lee, B., and Shin, I. (2019). SynFuzz: Efficient Concolic Execution via Branch Condition Synthesis. arXiv.
38. Xie, T., Tillmann, N., De Halleux, J., and Schulte, W. (July, January 29). Fitness-guided path exploration in dynamic symbolic execution. Proceedings of the IEEE/IFIP International Conference on Dependable Systems & Networks, Lisbon, Portugal.
39. Bottinger, K., and Eckert, C. (2016, January 7–8). DeepFuzz: Triggering Vulnerabilities Deeply Hidden in Binaries. Proceedings of the International Conference on Detection of Intrusions and Malware, and Vulnerability Assessment, San Sebastián, Spain.10.1007/978-3-319-40667-1_2 ↗