Ulf Kargén
ABSTRACT
Greybox fuzzing has recently emerged as a scalable and practical approach to finding security bugs in software. For example, AFL ---the current state-of-the-art greybox fuzzer --- has found hundreds of vulnerabilities in popular software since its release in 2013. The combination of lightweight coverage instrumentation and a simple evolutionary algorithm allows AFL to quickly generate inputs that exercise new code. AFL also obviates the need to manually set adhoc fuzzing ratios, which has been a major limitation of classical black-box fuzzers. Instead, AFL's first fuzzing pass exhaustively applies a set of mutations to every byte of a program input. While this approach allows for more thorough exploration of the input space, and therefore improves the chances of finding complex bugs, it also drastically slows down the fuzzing progress for "heavyweight" programs, or programs that take large inputs. This makes AFL less suitable for fuzzing input formats with large size overhead, such as various document formats. In this paper, we propose focused fuzzing as a practical trade-off between thoroughness and speed, for fuzzers that employ input mutation. We extend the notion of code coverage to individual bytes of input, and show how forward dynamic slicing can be used to efficiently determine the set of program instructions that are affected by a particular input byte. This information can then be used to restrict expensive mutations to a small subset of input bytes. We implement focused fuzzing on top of AFL, and evaluate it on four "real-life" Linux programs. Our evaluation shows that focused fuzzing noticeably improves bug discovery, compared to vanilla AFL.
- Hiralal Agrawal and Joseph R Horgan. 1990. Dynamic program slicing. In ACM SIGPlan Notices, Vol. 25. ACM, 246--256. Google Scholar
Digital Library
- Dave Aitel. 2002. SPIKE Fuzzer. http://www.immunityinc.com/resources/index.html. (2002).Google Scholar
- Brad Arkin. 2009. Adobe Reader and Acrobat Security Initiative. http://blogs.adobe.com/security/2009/05/adobe_reader_and_acrobat_secur.html. (2009).Google Scholar
- Hanno Böck. 2017. The Fuzzing Project. https://fuzzing-project.org/software.html. (2017).Google Scholar
- Marcel Böhme, Van-Thuan Pham, Manh-Dung Nguyen, and Abhik Roychoudhury. 2017. Directed greybox fuzzing. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. ACM, 2329--2344. Google ScholarDigital Library
- Marcel Böhme, Van-Thuan Pham, and Abhik Roychoudhury. 2016. Coverage-based Greybox Fuzzing as Markov Chain. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. ACM, 1032--1043. Google ScholarDigital Library
- Cristian Cadar, Daniel Dunbar, Dawson R Engler, et al. 2008. KLEE: Unassisted and Automatic Generation of High-Coverage Tests for Complex Systems Programs. In Proceedings of the 8th USENIX conference on Operating systems design and implementation. 209--224. Google ScholarDigital Library
- Sang Kil Cha, T. Avgerinos, A. Rebert, and D. Brumley. 2012. Unleashing Mayhem on Binary Code. In Proceedings of the 2012 IEEE Symposium on Security and Privacy. 380--394. Google ScholarDigital Library
- Sang Kil Cha, Maverick Woo, and David Brumley. 2015. Program-adaptive mutational fuzzing. In 2015 IEEE Symposium on Security and Privacy (SP). IEEE, 725--741. Google ScholarDigital Library
- Vijay Ganesh, Tim Leek, and Martin Rinard. 2009. Taint-based directed whitebox fuzzing. In Proceedings of the 31st International Conference on Software Engineering. IEEE Computer Society, 474--484. Google ScholarDigital Library
- Patrice Godefroid, Michael Y. Levin, and David A. Molnar. 2008. Automated Whitebox Fuzz Testing. In Proceedings of the Network and Distributed System Security Symposium.Google Scholar
- Patrice Godefroid, Hila Peleg, and Rishabh Singh. 2017. Learn&fuzz: Machine learning for input fuzzing. In Proceedings of the 32nd IEEE/ACM International Conference on Automated Software Engineering. IEEE Press, 50--59. Google ScholarDigital Library
- Istvan Haller, Asia Slowinska, Matthias Neugschwandtner, and Herbert Bos. 2013. Dowsing for Overflows: A Guided Fuzzer to Find Buffer Boundary Violations. In USENIX Security Symposium. 49--64. Google ScholarDigital Library
- Sam Hocevar. 2010. zzuf - multi-purpose fuzzer. http://caca.zoy.org/wiki/zzuf. (2010).Google Scholar
- Christian Holler, Kim Herzig, and Andreas Zeller. 2012. Fuzzing with Code Fragments. In Proceedings of the 21st USENIX Security Symposium. Google ScholarDigital Library
- Allen D Householder and Jonathan M Foote. 2012. Probability-based parameter selection for black-box fuzz testing. Technical Report. CERT.Google Scholar
- Michael Howard and Steve Lipner. 2006. The Security Development Lifecycle. Microsoft Press. Google ScholarDigital Library
- Ulf Kargén and Nahid Shahmehri. 2014. Efficient Utilization of Secondary Storage for Scalable Dynamic Slicing. In Proceedings of the 2014 IEEE 14th International Working Conference on Source Code Analysis and Manipulation. 155--164. Google ScholarDigital Library
- Ulf Kargén and Nahid Shahmehri. 2015. Turning programs against each other: high coverage fuzz-testing using binary-code mutation and dynamic slicing. In Proceedings of the 2015 10th Joint Meeting on Foundations of Software Engineering. ACM, 782--792. Google ScholarDigital Library
- Vasileios P Kemerlis, Georgios Portokalidis, Kangkook Jee, and Angelos D Keromytis. 2012. libdft: Practical dynamic data flow tracking for commodity systems. In Acm Sigplan Notices, Vol. 47. ACM, 121--132. Google ScholarDigital Library
- Yuekang Li, Bihuan Chen, Mahinthan Chandramohan, Shang-Wei Lin, Yang Liu, and Alwen Tiu. 2017. Steelix: program-state based binary fuzzing. In Proceedings of the 2017 11th Joint Meeting on Foundations of Software Engineering. ACM, 627--637. Google ScholarDigital Library
- Chi-Keung Luk, Robert Cohn, Robert Muth, Harish Patil, Artur Klauser, Geoff Lowney, Steven Wallace, Vijay Janapa Reddi, and Kim Hazelwood. 2005. Pin: Building Customized Program Analysis Tools with Dynamic Instrumentation. In Proceedings of the 2005 ACM SIGPLAN Conference on Programming Language Design and Implementation. 190--200. Google ScholarDigital Library
- Sean Luke and Liviu Panait. 2006. A comparison of bloat control methods for genetic programming. Evolutionary Computation 14, 3 (2006), 309--344. Google ScholarDigital Library
- Barton P. Miller, Louis Fredriksen, and Bryan So. 1990. An Empirical Study of the Reliability of UNIX Utilities. Commun. ACM 33, 12 (Dec. 1990), 32--44. Google ScholarDigital Library
- Barton Paul Miller, David Koski, Cjin Pheow Lee, Vivekananda Maganty, Ravi Murthy, Ajitkumar Natarajan, and Jeff Steidl. 1995. Fuzz revisited: A reexamination of the reliability of UNIX utilities and services. Technical Report. University of Wisconsin-Madison, Computer Sciences Department.Google Scholar
- David Molnar, Xue Cong Li, and David Wagner. 2009. Dynamic Test Generation to Find Integer Bugs in x86 Binary Linux Programs. In USENIX Security Symposium, Vol. 9. 67--82. Google ScholarDigital Library
- Max Moroz and Kostya Serebryany. 2016. Guided in-process fuzzing of Chrome components. https://security.googleblog.com/2016/08/guided-in-process-fuzzing-of-chrome.html. (2016).Google Scholar
- Matthias Neugschwandtner, Paolo Milani Comparetti, Istvan Haller, and Herbert Bos. 2015. The borg: Nanoprobing binaries for buffer overreads. In Proceedings of the 5th ACM Conference on Data and Application Security and Privacy. ACM, 87--97. Google ScholarDigital Library
- James Newsome and Dawn Song. 2005. Dynamic taint analysis for automatic detection, analysis, and signature generation of exploits on commodity software. In Proceedings of the Network and Distributed System Security Symposium (NDSS).Google Scholar
- Oulu University Secure Programming Group. 2017. A Crash Course to Radamsa. https://github.com/aoh/radamsa. (2017).Google Scholar
- Peachtech. 2018. Peach fuzzer platform. https://www.peach.tech/products/peach-fuzzer/. (2018).Google Scholar
- LLVM Project. 2016. libFuzzer -- a library for coverage-guided fuzz testing. https://llvm.org/docs/LibFuzzer.html. (2016).Google Scholar
- Sanjay Rawat, Vivek Jain, Ashish Kumar, Lucian Cojocar, Cristiano Giuffrida, and Herbert Bos. 2017. VUzzer: Application-aware evolutionary fuzzing. In Proceedings of the Network and Distributed System Security Symposium (NDSS).Google ScholarCross Ref
- Alexandre Rebert, Sang Kil Cha, Thanassis Avgerinos, Jonathan Foote, David Warren, Gustavo Grieco, and David Brumley. 2014. Optimizing Seed Selection for Fuzzing. In Proceedings of the 23rd USENIX Security Symposium. 861--875. Google ScholarDigital Library
- Eric Rizzi. 2016. The Cyber Grand Challenge. http://blogs.grammatech.com/the-cyber-grand-challenge. (2016).Google Scholar
- Nick Stephens, John Grosen, Christopher Sails, Andrew Dutcher, Ruoyu Wang, Jacopo Corbetta, Yan Shoshitaishvili, Christopher Kruegel, and Giovanni Vigna. 2016. Driller: Augmenting Fuzzing Through Selective Symbolic Execution. In Proceedings of the Network and Distributed System Security Symposium.Google ScholarCross Ref
- Michael Sutton, Adam Greene, and Pedram Amini. 2007. Fuzzing: brute force vulnerability discovery. Pearson Education. Google ScholarDigital Library
- Spandan Veggalam, Sanjay Rawat, Istvan Haller, and Herbert Bos. 2016. Ifuzzer: An evolutionary interpreter fuzzer using genetic programming. In European Symposium on Research in Computer Security. Springer, 581--601.Google ScholarCross Ref
- Junjie Wang, Bihuan Chen, Lei Wei, and Yang Liu. 2017. Skyfire: Data-driven seed generation for fuzzing. In 2017 IEEE Symposium on Security and Privacy. IEEE, 579--594.Google ScholarCross Ref
- Tielei Wang, Tao Wei, Guofei Gu, and Wei Zou. 2010. TaintScope: A Checksum-Aware Directed Fuzzing Tool for Automatic Software Vulnerability Detection. In Proceedings of the 2010 IEEE Symposium on Security and Privacy. 497--512. Google ScholarDigital Library
- Maverick Woo, Sang Kil Cha, Samantha Gottlieb, and David Brumley. 2013. Scheduling Black-box Mutational Fuzzing. In Proceedings of the 2013 ACM SIGSAC Conference on Computer and Communications Security. 511--522. Google ScholarDigital Library
- Xuejun Yang, Yang Chen, Eric Eide, and John Regehr. 2011. Finding and Understanding Bugs in C Compilers. In Proceedings of the 32nd ACM SIGPLAN Conference on Programming Language Design and Implementation. 283--294. Google ScholarDigital Library
- Michal Zalewski. 2017. American Fuzzy Lop. http://lcamtuf.coredump.cx/afl/. (2017).Google Scholar
Index Terms
- Speeding Up Bug Finding using Focused Fuzzing
Recommendations
Turning programs against each other: high coverage fuzz-testing using binary-code mutation and dynamic slicing
ESEC/FSE 2015: Proceedings of the 2015 10th Joint Meeting on Foundations of Software EngineeringMutation-based fuzzing is a popular and widely employed black-box testing technique for finding security and robustness bugs in software. It owes much of its success to its simplicity; a well-formed seed input is mutated, e.g. through random bit-...
Fine-Grained Coverage-Based Fuzzing
Fuzzing is a popular software testing method that discovers bugs by massively feeding target applications with automatically generated inputs. Many state-of-art fuzzers use branch coverage as a feedback metric to guide the fuzzing process. The fuzzer ...
Finding Software Vulnerabilities by Smart Fuzzing
ICST '11: Proceedings of the 2011 Fourth IEEE International Conference on Software Testing, Verification and ValidationNowadays, one of the most effective ways to identify software vulnerabilities by testing is the use of fuzzing, whereby the robustness of software is tested against invalid inputs that play on implementation limits or data boundaries. A high number of ...
Comments