Marcel Böhme
Abhik Roychoudhury
ABSTRACT
Existing Greybox Fuzzers (GF) cannot be effectively directed, for instance, towards problematic changes or patches, towards critical system calls or dangerous locations, or towards functions in the stack-trace of a reported vulnerability that we wish to reproduce. In this paper, we introduce Directed Greybox Fuzzing (DGF) which generates inputs with the objective of reaching a given set of target program locations efficiently. We develop and evaluate a simulated annealing-based power schedule that gradually assigns more energy to seeds that are closer to the target locations while reducing energy for seeds that are further away. Experiments with our implementation AFLGo demonstrate that DGF outperforms both directed symbolic-execution-based whitebox fuzzing and undirected greybox fuzzing. We show applications of DGF to patch testing and crash reproduction, and discuss the integration of AFLGo into Google's continuous fuzzing platform OSS-Fuzz. Due to its directedness, AFLGo could find 39 bugs in several well-fuzzed, security-critical projects like LibXML2. 17 CVEs were assigned.
Supplemental Material
- Andrea Arcuri and Lionel Briand. 2014. A Hitchhiker's guide to statistical tests for assessing randomized algorithms in software engineering. Software Testing, Verification and Reliability 24, 3 (2014), 219--250. Google Scholar
Digital Library
- Hanno Böck. 2015. Wie man Heartbleed hätte finden können. Golem.de (April 2015). http://www.golem.de/news/fuzzing-wie-man-heartbleedhaette- finden-koennen-1504--113345.html (DE); https://blog.hboeck.de/archives/868- How-Heartbleed-couldve-been-found.html (EN).Google Scholar
- Marcel Böhme, Bruno C. d. S. Oliveira, and Abhik Roychoudhury. 2013. Partition- based Regression Verification. In Proceedings of the 2013 International Conference on Software Engineering (ICSE '13). 302--311. Google ScholarCross Ref
- Marcel Böhme, Bruno C. d. S. Oliveira, and Abhik Roychoudhury. 2013. Regression Tests to Expose Change Interaction Errors. In Proceedings of the 2013 9th Joint Meeting on Foundations of Software Engineering (ESEC/FSE 2013). 334--344. Google ScholarDigital Library
- Marcel Böhme and Soumya Paul. 2016. A Probabilistic Analysis of the Efficiency of Automated Software Testing. IEEE Transactions on Software Engineering 42, 4 (April 2016), 345--360. 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 (CCS '16). 1032--1043. Google ScholarDigital Library
- Cristian Cadar, Daniel Dunbar, and Dawson Engler. 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 (OSDI'08). 209--224.Google ScholarDigital Library
- Vitaly Chipounov, Volodymyr Kuznetsov, and George Candea. 2011. S2E: A Platform for In-vivo Multi-path Analysis of Software Systems. In ASPLOS XVI. 265--278.Google Scholar
- Maria Christakis, Peter Müller, and Valentin Wüstholz. 2016. Guiding Dynamic Symbolic Execution Toward Unverified Program Executions. In Proceedings of the 38th International Conference on Software Engineering (ICSE '16). 144--155. Google ScholarDigital Library
- Leonardo De Moura and Nikolaj Bjørner. 2008. Z3: An Efficient SMT Solver. In Proceedings of the Theory and Practice of Software, 14th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS'08/ETAPS'08). 337--340.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 (ICSE '09). 474--484. Google ScholarDigital Library
- Patrice Godefroid, Michael Y. Levin, and David Molnar. 2012. SAGE: Whitebox Fuzzing for Security Testing. Queue 10, 1, Article 20 (Jan. 2012), 8 pages.Google Scholar
- Patrice Godefroid, Michael Y. Levin, and David A. Molnar. 2008. Automated Whitebox Fuzz Testing.. In NDSS '08 (2009-06--18). The Internet Society.Google Scholar
- Istvan Haller, Yuseok Jeon, Hui Peng, Mathias Payer, Cristiano Giuffrida, Her- bert Bos, and Erik van der Kouwe. 2016. TypeSan: Practical Type Confusion Detection. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security (CCS '16). 517--528. 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 Proceedings of the 22Nd USENIX Conference on Security (SEC'13). 49--64.Google ScholarDigital Library
- Mark Harman, Yue Jia, and William B. Langdon. 2011. Strong Higher Order Mutation-based Test Data Generation. In Proceedings of the 19th ACM SIGSOFT Symposium and the 13th European Conference on Foundations of Software Engineering (ESEC/FSE '11). 212--222. Google ScholarDigital Library
- Andrew Henderson, Lok Kwong Yan, Xunchao Hu, Aravind Prakash, Heng Yin, Stephen McCamant, undefined, undefined, undefined, and undefined. 2017. DECAF: A Platform-Neutral Whole-System Dynamic Binary Analysis Platform. IEEE Transactions on Software Engineering 43, 2 (2017), 164--184. Google ScholarDigital Library
- Wei Jin and Alessandro Orso. 2012. BugRedux: Reproducing Field Failures for In- house Debugging. In Proceedings of the 34th International Conference on Software Engineering (ICSE '12). 474--484. Google ScholarCross Ref
- S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. 1983. Optimization by simulated annealing. SCIENCE 220, 4598 (1983), 671--680. Google ScholarCross Ref
- Kin-Keung Ma, Khoo Yit Phang, Jeffrey S. Foster, and Michael Hicks. 2011. Di- rected Symbolic Execution. In Proceedings of the 18th International Conference on Static Analysis (SAS'11). 95--111.Google ScholarCross Ref
- Paul Dan Marinescu and Cristian Cadar. 2013. KATCH: High-coverage Testing of Software Patches. In Proceedings of the 2013 9th Joint Meeting on Foundations of Software Engineering (ESEC/FSE 2013). 235--245. Google ScholarDigital Library
- Björn Matthis, Vitalii Avdiienko, Ezekiel Soremekun, Marcel Böhme, and Andreas Zeller. 2017. Detecting Information Flow by Mutating Input Data. In Proceedings of the 32nd IEEE/ACM International Conference on Automated Software Engineering (ASE '17). 1--11.Google ScholarCross Ref
- Kurt Mehlhorn. 1984. Data structures and algorithms: 1. Searching and sorting. Springer 84 (1984), 90.Google Scholar
- 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
- James Newsome, Dawn Song, James Newsome, and Dawn Song. 2005. Dynamic taint analysis: Automatic detection, analysis, and signature generation of exploit attacks on commodity software. In Proceedings of the 12th Network and Distributed Systems Security Symposium (NDSS).Google Scholar
- Brian S. Pak. 2012. Hybrid Fuzz Testing: Discovering Software Bugs via Fuzzing and Symbolic Execution. Ph.D. Dissertation. Carnegie Mellon University Pittsburgh.Google Scholar
- Suzette Person, Guowei Yang, Neha Rungta, and Sarfraz Khurshid. 2011. Directed Incremental Symbolic Execution. In Proceedings of the 32Nd ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI '11). 504-- 515. Google ScholarDigital Library
- V. T. Pham, M. Böhme, and A. Roychoudhury. 2016. Model-based whitebox fuzzing for program binaries. In Proceedings of the 31st IEEE/ACM International Conference on Automated Software Engineering (ASE 2016). 543--553. Google ScholarDigital Library
- Van-Thuan Pham, Wei Boon Ng, Konstantin Rubinov, and Abhik Roychoudhury. 2015. Hercules: Reproducing Crashes in Real-world Application Binaries. In Proceedings of the 37th International Conference on Software Engineering - Volume 1 (ICSE '15). 891--901. Google ScholarCross Ref
- Dawei Qi, Abhik Roychoudhury, and Zhenkai Liang. 2010. Test Generation to Expose Changes in Evolving Programs. In Proceedings of the IEEE/ACM International Conference on Automated Software Engineering (ASE '10). 397--406. Google ScholarDigital Library
- Sanjay Rawat, Vivek Jain, Ashish Kumar, Lucian Cojocar, Cristiano Giuffrida, and Herbert Bos. 2017. VUzzer: Application-aware Evolutionary Fuzzing. In NDSS '17. 1--14.Google Scholar
- Eric F. Rizzi, Sebastian Elbaum, and Matthew B. Dwyer. 2016. On the Techniques We Create, the Tools We Build, and Their Misalignments: A Study of KLEE. In Proceedings of the 38th International Conference on Software Engineering (ICSE '16). 132--143. Google ScholarDigital Library
- J. Rößler, A. Zeller, G. Fraser, C. Zamfir, and G. Candea. 2013. Reconstructing Core Dumps. In 2013 IEEE Sixth International Conference on Software Testing, Verification and Validation. 114--123. Google ScholarDigital Library
- R. Santelices, P. K. Chittimalli, T. Apiwattanapong, A. Orso, and M. J. Harrold. 2008. Test-Suite Augmentation for Evolving Software. In Proceedings of the 2008 23rd IEEE/ACM International Conference on Automated Software Engineering (ASE '08). 218--227. Google ScholarDigital Library
- Konstantin Serebryany, Derek Bruening, Alexander Potapenko, and Dmitry Vyukov. 2012. AddressSanitizer: A Fast Address Sanity Checker. In Proceedings of the 2012 USENIX Conference on Annual Technical Conference (USENIX ATC'12). 28--28.Google Scholar
- S. Sparks, S. Embleton, R. Cunningham, and C. Zou. 2007. Automated Vulner- ability Analysis: Leveraging Control Flow for Evolutionary Input Crafting. In Twenty-Third Annual Computer Security Applications Conference (ACSAC 2007). 477--486. Google ScholarCross Ref
- E. Stepanov and K. Serebryany. 2015. MemorySanitizer: Fast detector of unini- tialized memory use in C. In 2015 IEEE/ACM International Symposium on Code Generation and Optimization (CGO). 46--55.Google Scholar
- Nick Stephens, John Grosen, Christopher Salls, Andrew Dutcher, Ruoyu Wang, Jacopo Corbetta, Yan Shoshitaishvili, Christopher Kruegel, and Giovanni Vigna. 2016. Driller: Augmenting Fuzzing Through Selective Symbolic Execution. In NDSS '16. 1--16.Google Scholar
- András Vargha and Harold D. Delaney. 2000. A Critique and Improvement of the "CL" Common Language Effect Size Statistics of McGraw and Wong. Journal of Educational and Behavioral Statistics 25, 2 (2000), 101--132.Google Scholar
- 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 (SP '10). 497--512. Google ScholarDigital Library
- Website. 2017. AFL - Pulling Jpegs out of Thin Air, Michael Zalewski. https: //lcamtuf.blogspot.com/2014/11/pulling-jpegs-out-of-thin-air.html. (2017). Accessed: 2017-05--13.Google Scholar
- Website. 2017. AFL Vulnerability Trophy Case. http://lcamtuf.coredump.cx/afl/ #bugs. (2017). Accessed: 2017-05-13.Google Scholar
- Website. 2017. American Fuzzy Lop (AFL) Fuzzer. http://lcamtuf.coredump.cx/ afl/technical_details.txt. (2017). Accessed: 2017-05--13.Google Scholar
- Website. 2017. Announcing OSS-Fuzz. https://testing.googleblog.com/2016/12/ announcing-oss-fuzz-continuous-fuzzing.html. (2017). Accessed: 2017-05-13.Google Scholar
- Website. 2017. BoringSSL -- Google's fork of OpenSSL. https://boringssl. googlesource.com/. (2017). Accessed: 2017-05-13.Google Scholar
- Website. 2017. Commit to OpenSSL that introduced Heartbleed. https://git. openssl.org/gitweb/?p=openssl.git;a=commitdiff;h=4817504. (2017). Accessed: 2017-05-13.Google Scholar
- Website. 2017. Descriptive statistics of OpenSSL library. https://www.openhub. net/p/openssl. (2017). Accessed: 2017-05--13.Google Scholar
- Website. 2017. Expat XML Parser. https://libexpat.github.io/. (2017). Accessed: 2017-05-13.Google Scholar
- Website. 2017. Heartbleed - A vulnerability in OpenSSL. http://heartbleed.com/. (2017). Accessed: 2017-05-13.Google Scholar
- Website. 2017. Libav Open source audio and video processing tools. https: //libav.org/. (2017). Accessed: 2017-05-13.Google Scholar
- Website. 2017. "libc++abi" C++ Standard Library Support. https://libcxxabi.llvm. org/. (2017). Accessed: 2017-05--13.Google Scholar
- Website. 2017. LibDwarf is parser for the DWARF information used by compilers and debuggers. https://www.prevanders.net/dwarf.html/. (2017). Accessed: 2017-05-13.Google Scholar
- Website. 2017. LibFuzzer: A library for coverage-guided fuzz testing. http: //llvm.org/docs/LibFuzzer.html. (2017). Accessed: 2017-05-13.Google Scholar
- Website. 2017. LibPNG - A library for processing PNG files. http://www.libpng. org/pub/png/libpng.html. (2017). Accessed: 2017-05-13.Google Scholar
- Website. 2017. Libxml2 is the XML C parser and toolkit developed for the Gnome project. http://xmlsoft.org/. (2017). Accessed: 2017-05-13.Google Scholar
- Website. 2017. Ming is a library for generating Macromedia Flash files. http: //www.libming.org/. (2017). Accessed: 2017-05--13.Google Scholar
- Website. 2017. MITRE -- Common Vulnerabilities and Exposures. https://cve. mitre.org/. (2017). Accessed: 2017-05-13.Google Scholar
- Website. 2017. OSS-Fuzz: Continuous Fuzzing Framework for Open-Source Projects. https://github.com/google/oss-fuzz. (2017). Accessed: 2017-05-13.Google Scholar
- Website. 2017. OSS-Fuzz: Five Months Later. https://testing.googleblog.com/ 2017/05/oss-fuzz-five-months-later-and.html. (2017). Accessed: 2017-05-13.Google Scholar
- Website. 2017. Peach Fuzzer Platform. http://www.peachfuzzer.com/products/ peach-platform/. (2017). Accessed: 2017-05--13.Google Scholar
- Website. 2017. Search engine for the internet of things -- devices still vulnerable to Heartbleed. https://www.shodan.io/report/89bnfUyJ. (2017). Accessed: 2017-05-13.Google Scholar
- Website. 2017. SPIKE Fuzzer Platform. http://www.immunitysec.com. (2017). Accessed: 2017-05-13.Google Scholar
- Website. 2017. US National Vulnerability Database. https://nvd.nist.gov/vuln/ search. (2017). Accessed: 2017-05-13.Google Scholar
- Website. 2017. Video Lan Client -- Open-source Media Player. https://www. videolan.org. (2017). Accessed: 2017-05-13.Google Scholar
- Website. 2017. Zzuf: multi-purpose fuzzer. http://caca.zoy.org/wiki/zzuf. (2017). Accessed: 2017-05-13.Google Scholar
- Zhihong Xu, Yunho Kim, Moonzoo Kim, Gregg Rothermel, and Myra B. Cohen. 2010. Directed Test Suite Augmentation: Techniques and Tradeoffs. In Proceedings of the Eighteenth ACM SIGSOFT International Symposium on Foundations of Software Engineering (FSE '10). 257--266. Google ScholarDigital Library
Index Terms
- Directed Greybox Fuzzing
Recommendations
Sequence coverage directed greybox fuzzing
ICPC '19: Proceedings of the 27th International Conference on Program ComprehensionExisting directed fuzzers are not efficient enough. Directed symbolic-execution-based whitebox fuzzers, e.g. BugRedux, spend lots of time on heavyweight program analysis and constraints solving at runtime. Directed greybox fuzzers, such as AFLGo, ...
TargetFuzz: Using DARTs to Guide Directed Greybox Fuzzers
ASIA CCS '22: Proceedings of the 2022 ACM on Asia Conference on Computer and Communications SecuritySoftware development is a continuous and incremental process. Developers continuously improve their software in small batches rather than in one large batch. The high frequency of small batches makes it essential to use effective testing methods that ...
DiPri: Distance-Based Seed Prioritization for Greybox Fuzzing (Registered Report)
FUZZING 2023: Proceedings of the 2nd International Fuzzing WorkshopGreybox fuzzing is a powerful testing technique. Given a set of initial seeds, greybox fuzzing continuously generates new test inputs to execute the program under test and gravitates executions towards rarely explored program regions with code ...
Comments