The Havoc Paradox in Generator-Based Fuzzing (Registered Report)
Pages 3 - 12
Abstract
Parametric generators are a simple way to combine coverage-guided and generator-based fuzzing. Parametric generators can be thought of as decoders of an arbitrary byte sequence into a structured input. This allows mutations on the byte sequence to map to mutations on the structured input, without requiring the writing of specialized mutators. However, this technique is prone to the havoc effect, where small mutations on the byte sequence cause large, destructive mutations to the structured input. This registered report first provides a preliminary investigation of the paradoxical nature of the havoc effect for generator-based fuzzing in Java. In particular, we measure mutation characteristics and confirm the existence of the havoc effect, as well as scenarios where it may be more detrimental. The proposed evaluation extends this investigation over more benchmarks, with the tools Zest, JQF’s EI, BeDivFuzz, and Zeugma.
References
[1]
[n. d.]. American Fuzzy Lop. https://github.com/google/AFL Accessed: 2021-08-31
[2]
[n. d.]. Apache Ant is a Java-based build tool. https://github.com/apache/ant
[3]
[n. d.]. cargo-fuzz. https://github.com/rust-fuzz/cargo-fuzz Accessed: 2023-05-01
[4]
[n. d.]. Closure Compiler. https://developers.google.com/closure/compiler Accessed: 2021-08-31
[5]
[n. d.]. GSON: A Java serialization/deserialization library to convert Java Objects into JSON and back. https://github.com/google/gson
[6]
[n. d.]. Jackson Project Home @github. https://github.com/FasterXML/jackson
[7]
[n. d.]. libFuzzer – a library for coverage-guided fuzz testing. https://llvm.org/docs/LibFuzzer.html Accessed: 2021-08-31
[8]
[n. d.]. libFuzzer – How To Split A Fuzzer-Generated Input Into Several Parts. https://github.com/google/fuzzing/blob/41d7725/docs/split-inputs.md Accessed: 2021-08-31
[9]
[n. d.]. libprotobuf-mutator. https://github.com/google/libprotobuf-mutator Accessed: 2021-08-31
[10]
[n. d.]. Rhino: JavaScript in Java. https://github.com/mozilla/rhino
[11]
[n. d.]. Structure-Aware Fuzzing with libFuzzer. https://github.com/google/fuzzing/blob/master/docs/structure-aware-fuzzing.md Accessed: 2022-06-02
[12]
Cornelius Aschermann, Tommaso Frassetto, Thorsten Holz, Patrick Jauernig, Ahmad-Reza Sadeghi, and Daniel Teuchert. 2019. NAUTILUS: Fishing for Deep Bugs with Grammars. In NDSS.
[13]
Juan Caballero, Heng Yin, Zhenkai Liang, and Dawn Song. 2007. Polyglot: Automatic Extraction of Protocol Message Format Using Dynamic Binary Analysis. In Proceedings of the 14th ACM Conference on Computer and Communications Security (CCS ’07). Association for Computing Machinery, New York, NY, USA. 317–329. isbn:9781595937032 https://doi.org/10.1145/1315245.1315286
[14]
Peng Chen and Hao Chen. 2018. Angora: Efficient fuzzing by principled search. In 2018 IEEE Symposium on Security and Privacy (SP). 711–725.
[15]
Koen Claessen and John Hughes. 2000. QuickCheck: A Lightweight Tool for Random Testing of Haskell Programs. In Proceedings of the Fifth ACM SIGPLAN International Conference on Functional Programming. Association for Computing Machinery, New York, NY, USA. 268–279. isbn:1581132026 https://doi.org/10.1145/351240.351266
[16]
Andrea Fioraldi, Dominik Maier, Heiko Eiß feldt, and Marc Heuse. 2020. AFL++: Combining Incremental Steps of Fuzzing Research. In 14th USENIX Workshop on Offensive Technologies (WOOT 20). USENIX Association.
[17]
Andrea Fioraldi, Dominik Christian Maier, Dongjia Zhang, and Davide Balzarotti. 2022. LibAFL: A Framework to Build Modular and Reusable Fuzzers. In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security (CCS ’22). Association for Computing Machinery, New York, NY, USA. 1051–1065. isbn:9781450394505 https://doi.org/10.1145/3548606.3560602
[18]
Shuitao Gan, Chao Zhang, Peng Chen, Bodong Zhao, Xiaojun Qin, Dong Wu, and Zuoning Chen. 2020. GREYONE: Data Flow Sensitive Fuzzing. In 29th $USENIX$ Security Symposium ($USENIX$ Security 20). 2577–2594.
[19]
Harrison Green and Thanassis Avgerinos. 2022. GraphFuzz: Library API Fuzzing with Lifetime-Aware Dataflow Graphs. In Proceedings of the 44th International Conference on Software Engineering (ICSE ’22). Association for Computing Machinery, New York, NY, USA. 1070–1081. isbn:9781450392211 https://doi.org/10.1145/3510003.3510228
[20]
Christian Holler, Kim Herzig, and Andreas Zeller. 2012. Fuzzing with Code Fragments. In 21st USENIX Security Symposium (USENIX Security 12). USENIX Association, Bellevue, WA. 445–458. isbn:978-931971-95-9 https://www.usenix.org/conference/usenixsecurity12/technical-sessions/presentation/holler
[21]
Katherine Hough and Jonathan Bell. 2024. Crossover in Parametric Fuzzing. In Proceedings of the IEEE/ACM 46th International Conference on Software Engineering. 1–12.
[22]
Pallavi Joshi, Chang-Seo Park, Koushik Sen, and Mayur Naik. 2009. A Randomized Dynamic Program Analysis Technique for Detecting Real Deadlocks. In Proceedings of the 30th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI ’09). Association for Computing Machinery, New York, NY, USA. 110–120. isbn:9781605583921 https://doi.org/10.1145/1542476.1542489
[23]
James Kukucka, Luís Pina, Paul Ammann, and Jonathan Bell. 2022. Confetti: Amplifying concolic guidance for fuzzers. In Proceedings of the 44th International Conference on Software Engineering. 438–450.
[24]
Caroline Lemieux and Koushik Sen. 2018. Fairfuzz: A targeted mutation strategy for increasing greybox fuzz testing coverage. In Proceedings of the 33rd ACM/IEEE International Conference on Automated Software Engineering. 475–485.
[25]
Jiawei Liu, Yuxiang Wei, Sen Yang, Yinlin Deng, and Lingming Zhang. 2022. Coverage-Guided Tensor Compiler Fuzzing with Joint IR-Pass Mutation. Proc. ACM Program. Lang., 6, OOPSLA1 (2022), Article 73, apr, 26 pages. https://doi.org/10.1145/3527317
[26]
Jonathan Metzman, László Szekeres, Laurent Simon, Read Sprabery, and Abhishek Arya. 2021. FuzzBench: An Open Fuzzer Benchmarking Platform and Service. In Proceedings of the 29th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE 2021). Association for Computing Machinery, New York, NY, USA. 1393–1403. isbn:9781450385626 https://doi.org/10.1145/3468264.3473932
[27]
Charlie Miller and Zachary NJ Peterson. 2007. Analysis of mutation and generation-based fuzzing. Independent Security Evaluators, Tech. Rep, 4 (2007).
[28]
Frederic P Miller, Agnes F Vandome, and John McBrewster. 2010. Apache Maven. Alpha Press.
[29]
Hoang Lam Nguyen and Lars Grunske. 2022. BEDIVFUZZ: Integrating Behavioral Diversity into Generator-based Fuzzing. In 2022 IEEE/ACM 44th International Conference on Software Engineering (ICSE). 249–261. https://doi.org/10.1145/3510003.3510182
[30]
Rohan Padhye, Caroline Lemieux, and Koushik Sen. 2019. JQF: Coverage-Guided Property-Based Testing in Java. In Proceedings of the 28th ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA 2019). Association for Computing Machinery, New York, NY, USA. 398–401. isbn:9781450362245 https://doi.org/10.1145/3293882.3339002
[31]
Rohan Padhye, Caroline Lemieux, Koushik Sen, Mike Papadakis, and Yves Le Traon. 2019. Semantic fuzzing with Zest. In Proceedings of the 28th ACM SIGSOFT International Symposium on Software Testing and Analysis. 329–340.
[32]
R. Padhye and K. Sen. 2017. Travioli: A Dynamic Analysis for Detecting Data-Structure Traversals. In 2017 IEEE/ACM 39th International Conference on Software Engineering (ICSE). 473–483. https://doi.org/10.1109/ICSE.2017.50
[33]
Rohan Padhye, Koushik Sen, and Paul N. Hilfinger. 2019. ChocoPy: A Programming Language for Compilers Courses. In Proceedings of the 2019 ACM SIGPLAN Symposium on SPLASH-E (SPLASH-E 2019). Association for Computing Machinery, New York, NY, USA. 41–45. isbn:9781450369893 https://doi.org/10.1145/3358711.3361627
[34]
Soyeon Park, Wen Xu, Insu Yun, Daehee Jang, and Taesoo Kim. 2020. Fuzzing JavaScript Engines with Aspect-preserving Mutation. In 2020 IEEE Symposium on Security and Privacy (SP). 1629–1642. https://doi.org/10.1109/SP40000.2020.00067
[35]
Van-Thuan Pham, Marcel Böhme, Andrew Edward Santosa, Alexandru Razvan Caciulescu, and Abhik Roychoudhury. 2019. Smart greybox fuzzing. IEEE Transactions on Software Engineering.
[36]
Sameer Reddy, Caroline Lemieux, Rohan Padhye, and Koushik Sen. 2020. Quickly generating diverse valid test inputs with reinforcement learning. In Proceedings of the ACM/IEEE 42nd International Conference on Software Engineering. 1410–1421.
[37]
Sergej Schumilo, Cornelius Aschermann, Ali Abbasi, Simon Wör-ner, and Thorsten Holz. 2021. Nyx: Greybox Hypervisor Fuzzing using Fast Snapshots and Affine Types. In 30th USENIX Security Symposium (USENIX Security 21). USENIX Association, 2597–2614. isbn:978-1-939133-24-3 https://www.usenix.org/conference/usenixsecurity21/presentation/schumilo
[38]
Prashast Srivastava and Mathias Payer. 2021. Gramatron: Effective Grammar-Aware Fuzzing. In Proceedings of the 30th ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA 2021). Association for Computing Machinery, New York, NY, USA. 244–256. isbn:9781450384599 https://doi.org/10.1145/3460319.3464814
[39]
Vasudev Vikram, Isabella Laybourn, Ao Li, Nicole Nair, Kelton OBrien, Rafaello Sanna, and Rohan Padhye. 2023. Guiding Greybox Fuzzing with Mutation Testing. In Proceedings of the 32nd ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA 2023). Association for Computing Machinery, New York, NY, USA. 929–941. isbn:9798400702211 https://doi.org/10.1145/3597926.3598107
[40]
Junjie Wang, Bihuan Chen, Lei Wei, and Yang Liu. 2019. Superion: Grammar-aware greybox fuzzing. In 2019 IEEE/ACM 41st International Conference on Software Engineering (ICSE). 724–735.
[41]
Mingyuan Wu, Ling Jiang, Jiahong Xiang, Yanwei Huang, Heming Cui, Lingming Zhang, and Yuqun Zhang. 2022. One Fuzzing Strategy to Rule Them All. In Proceedings of the 44th International Conference on Software Engineering (ICSE ’22). Association for Computing Machinery, New York, NY, USA. 1634–1645. isbn:9781450392211 https://doi.org/10.1145/3510003.3510174
[42]
Bin Xin, William N. Sumner, and Xiangyu Zhang. 2008. Efficient Program Execution Indexing. In Proceedings of the 29th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI ’08). Association for Computing Machinery, New York, NY, USA. 238–248. isbn:9781595938602 https://doi.org/10.1145/1375581.1375611
[43]
Rui Zhong, Yongheng Chen, Hong Hu, Hangfan Zhang, Wenke Lee, and Dinghao Wu. 2020. SQUIRREL: Testing Database Management Systems with Language Validity and Coverage Feedback. In Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security (CCS ’20). Association for Computing Machinery, New York, NY, USA. 955–970. isbn:9781450370899 https://doi.org/10.1145/3372297.3417260
Index Terms
- The Havoc Paradox in Generator-Based Fuzzing (Registered Report)
Recommendations
Crossover in Parametric Fuzzing
ICSE '24: Proceedings of the IEEE/ACM 46th International Conference on Software EngineeringParametric fuzzing combines evolutionary and generator-based fuzzing to create structured test inputs that exercise unique execution behaviors. Parametric fuzzers internally represent inputs as bit strings referred to as "parameter sequences". ...
Generator-based Fuzzing with Input Features
SBFT '24: Proceedings of the 17th ACM/IEEE International Workshop on Search-Based and Fuzz TestingGenerator-based fuzzing is a capable technique for testing semantic processing stages of a system under test (SUT). The idea is to use format-specific input generators, which can guarantee that inputs will be syntactically valid. One open question ...
FormatFuzzer: Effective Fuzzing of Binary File Formats
Effective fuzzing of programs that process structured binary inputs, such as multimedia files, is a challenging task, since those programs expect a very specific input format. Existing fuzzers, however, are mostly format-agnostic, which makes them ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
September 2024
89 pages
Copyright © 2024 Owner/Author.
This work is licensed under a Creative Commons Attribution International 4.0 License.
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 13 September 2024
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- NSF (National Science Foundation)
- Defense Advanced Research Projects Agency
Conference
FUZZING '24
Sponsor:
Upcoming Conference
ISSTA '25
- Sponsor:
- sigsoft
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 101Total Downloads
- Downloads (Last 12 months)101
- Downloads (Last 6 weeks)55
Reflects downloads up to 23 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in