Abstract
We design and implement from scratch a new fuzzer called Sivo that refines multiple stages of grey-box fuzzing. First, Sivo refines data-flow fuzzing in two ways: (a) it provides a new taint inference engine that requires only logarithmic number of tests in the input size to infer dependency of many program branches on the input bytes, and (b) it employs a novel method for inverting branches by solving a systems of inequalities efficiently. Second, our fuzzer refines accurate tracking and detection of code coverage with simple and easily implementable methods. Finally, Sivo refines selection of parameters and strategies by parameterizing all stages of fuzzing and then dynamically selecting optimal values during fuzzing. Thus the fuzzer can easily adapt to a target program and rapidly increase coverage. We compare our fuzzer to 11 other state-of-the-art grey-box fuzzers on 27 popular benchmarks. Our evaluation shows that Sivo scores the highest both in terms of code coverage and in terms of number of found vulnerabilities.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Despite having comparable numbers, Sivo and AFL use mostly different mutations and thus subroutines.
- 2.
C-type branches that contain multiple variables connected with AND/OR statements, during compilation are split into subsequent independent branches. Our inference is applied at assembly level, thus most of the branches depend only on a few variables.
- 3.
The matrix with rows \(V_0,V_1,\ldots \) is 1-disjunct and thus it can detect 1 dependency.
- 4.
This holds even in the case of FTI. However, the probabilities there are higher because there is a single mutated byte.
- 5.
The impact can be reduced with various methods, e.g., the MAB-based optimization presented in this paper.
- 6.
This refers to optimization only – some fuzzers improve (but not optimize) multiple fuzzing subroutines.
References
Circumventing fuzzing roadblocks with compiler transformations (2016). https://lafintel.wordpress.com/
Aschermann, C., Schumilo, S., Blazytko, T., Gawlik, R., Holz, T.: Redqueen: fuzzing with input-to-state correspondence. NDSS. 19, 1–15 (2019)
Böhme, M., Pham, V.T., Nguyen, M.D., Roychoudhury, A.: Directed greybox fuzzing. In: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pp. 2329–2344 (2017)
Böhme, M., Pham, V.T., Roychoudhury, A.: Coverage-based greybox fuzzing as Markov chain. IEEE Trans. Softw. Eng. 45(5), 489–506 (2017)
Cadar, C., Dunbar, D., Engler, D.R., et al.: Klee: unassisted and automatic generation of high-coverage tests for complex systems programs. OSDI 8, 209–224 (2008)
Chen, P., Chen, H.: Angora: efficient fuzzing by principled search. In: 2018 IEEE Symposium on Security and Privacy (SP), pp. 711–725. IEEE (2018)
Chen, P., Liu, J., Chen, H.: Matryoshka: fuzzing deeply nested branches. In: Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security (2019)
Choi, J., Jang, J., Han, C., Cha, S.K.: Grey-box concolic testing on binary code. In: 2019 IEEE/ACM 41st International Conference on Software Engineering (ICSE), pp. 736–747. IEEE (2019)
Dolan-Gavitt, B., et al.: Lava: large-scale automated vulnerability addition. In: S&P (2016)
Du, D., Hwang, F.K., Hwang, F.: Combinatorial group testing and its applications, vol. 12. World Scientific (2000)
Fioraldi, A., Maier, D., Eißfeldt, H., Heuse, M.: Afl++: combining incremental steps of fuzzing research. In: 14th USENIX Workshop on Offensive Technologies WOOT) (2020)
Gan, S., et al.: Greyone: data flow sensitive fuzzing. In: 29th USENIX Security Symposium (USENIX Security 20). USENIX Association, Boston, MA (2020). https://www.usenix.org/conference/usenixsecurity20/presentation/gan
Gan, S., et al.: CollAFL: path sensitive fuzzing. In: 2018 IEEE Symposium on Security and Privacy (SP), pp. 679–696. IEEE (2018)
Ganesh, V., Leek, T., Rinard, M.: Taint-based directed whitebox fuzzing. In: 2009 IEEE 31st International Conference on Software Engineering, pp. 474–484. IEEE (2009)
Google: OSS-Fuzz - continuous fuzzing of open source software (2020). https://github.com/google/oss-fuzz
Huang, H., Yao, P., Wu, R., Shi, Q., Zhang, C.: Pangolin: incremental hybrid fuzzing with polyhedral path abstraction. In: 2020 IEEE Symposium on Security and Privacy (SP), pp. 1613–1627. IEEE (2020)
Inozemtseva, L., Holmes, R.: Coverage is not strongly correlated with test suite effectiveness. In: Proceedings of the 36th International Conference on Software Engineering, pp. 435–445 (2014)
Klees, G., Ruef, A., Cooper, B., Wei, S., Hicks, M.: Evaluating fuzz testing. In: Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, pp. 2123–2138 (2018)
Kocsis, L., Szepesvári, C.: Discounted UCB. In: 2nd PASCAL Challenges Workshop, vol. 2 (2006)
Lemieux, C., Sen, K.: Fairfuzz: a targeted mutation strategy for increasing greybox fuzz testing coverage. In: Proceedings of the 33rd ACM/IEEE International Conference on Automated Software Engineering, pp. 475–485 (2018)
Li, Y., Chen, B., Chandramohan, M., Lin, S.W., Liu, Y., Tiu, A.: Steelix: program-state based binary fuzzing. In: Proceedings of the 2017 11th Joint Meeting on Foundations of Software Engineering, pp. 627–637 (2017)
Lyu, C., Ji, S., Zhang, C., Li, Y., Lee, W.H., Song, Y., Beyah, R.: MOPT: optimized mutation scheduling for fuzzers. In: 28th USENIX Security Symposium (USENIX Security 2019), pp. 1949–1966 (2019)
Manès, V.J., Kim, S., Cha, S.K.: Ankou: guiding grey-box fuzzing towards combinatorial difference. In: Proceedings of the ACM/IEEE 42nd International Conference on Software Engineering, pp. 1024–1036 (2020)
Nethercote, N., Seward, J.: Valgrind: a framework for heavyweight dynamic binary instrumentation. In: PLDI (2007)
Nikolic, I., Mantu, R.: Sivo: Refined gray-box fuzzer. https://github.com/ivicanikolicsg/SivoFuzzer
Rawat, S., Jain, V., Kumar, A., Cojocar, L., Giuffrida, C., Bos, H.: Vuzzer: application-aware evolutionary fuzzing. NDSS 17, 1–14 (2017)
Ryabinin, A.: Ubsan: run-time undefined behavior sanity checker (2014). https://lwn.net/Articles/617364/
Serebryany, K., Bruening, D., Potapenko, A., Vyukov, D.: Addresssanitizer: a fast address sanity checker. In: USENIX ATC (2012)
Serebryany, K.: Continuous fuzzing with libfuzzer and addresssanitizer. In: 2016 IEEE Cybersecurity Development (SecDev), pp. 157–157. IEEE (2016)
She, D., Krishna, R., Yan, L., Jana, S., Ray, B.: Mtfuzz: fuzzing with a multi-task neural network. In: FSE (2020)
Stephens, N., et al.: Driller: augmenting fuzzing through selective symbolic execution. NDSS 16, 1–16 (2016)
Swiecki, R.: Honggfuzz: Security oriented software fuzzer. supports evolutionary, feedback-driven fuzzing based on code coverage (SW and HW based) (2020). https://honggfuzz.dev/
Wang, Y., et al.: Not all coverage measurements are equal: fuzzing by coverage accounting for input prioritization. NDSS (2020)
You, W., et al.: Profuzzer: On-the-fly input type probing for better zero-day vulnerability discovery. In: 2019 IEEE Symposium on Security and Privacy (SP), pp. 769–786. IEEE (2019)
Yue, T., et al.: Ecofuzz: adaptive energy-saving greybox fuzzing as a variant of the adversarial multi-armed bandit. In: 29th USENIX Security Symposium (USENIX Security 20) (2020)
Yun, I., Lee, S., Xu, M., Jang, Y., Kim, T.: QSYM: a practical concolic execution engine tailored for hybrid fuzzing. In: 27th USENIX Security Symposium (USENIX Security 2018), pp. 745–761 (2018)
Zalewski, M.: American fuzzy lop (2.52b) (2019). https://lcamtuf.coredump.cx/afl/
Acknowledgments
We thank our shepherd Erik van der Kouwe for his helpful feedback. Abhik Roychoudhury, Zhijingcheng Yu, Shin Hwei Tan, Lu Yan, Andrea Fioraldi, and the anonymous reviewers gave us valuable comments and improvements on this work, for which we are thankful. All opinions expressed in this paper are solely those of the authors. This research is supported in part by the Crystal Centre at NUS and by the research grant DSOCL17019 from DSO in Singapore.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Nikolić, I., Mantu, R., Shen, S., Saxena, P. (2021). Refined Grey-Box Fuzzing with Sivo. In: Bilge, L., Cavallaro, L., Pellegrino, G., Neves, N. (eds) Detection of Intrusions and Malware, and Vulnerability Assessment. DIMVA 2021. Lecture Notes in Computer Science(), vol 12756. Springer, Cham. https://doi.org/10.1007/978-3-030-80825-9_6
Download citation
DOI: https://doi.org/10.1007/978-3-030-80825-9_6
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-80824-2
Online ISBN: 978-3-030-80825-9
eBook Packages: Computer ScienceComputer Science (R0)