FairFuzz: a targeted mutation strategy for increasing greybox fuzz testing coverage
Open accessThe DOI matches its Crossref record; 29 of the 29 references it cites were found in a registry or an index.
Abstract
In recent years, fuzz testing has proven itself to be one of the most effective techniques for finding correctness bugs and security vulnerabilities in practice. One particular fuzz testing tool, American Fuzzy Lop (AFL), has become popular thanks to its ease-of-use and bug-finding power. However, AFL remains limited in the bugs it can find since it simply does not cover large regions of code. If it does not cover parts of the code, it will not find bugs there. We propose a two-pronged approach to increase the coverage achieved by AFL. First, the approach automatically identifies branches exercised by few AFL-produced inputs (rare branches), which often guard code that is empirically hard to cover by naively mutating inputs. The second part of the approach is a novel mutation mask creation algorithm, which allows mutations to be biased towards producing inputs hitting a given rare branch. This mask is dynamically computed during fuzz testing and can be adapted to other testing targets. We implement this approach on top of AFL in a tool named FairFuzz. We conduct evaluation on real-world programs against state-of-the-art versions of AFL. We find that on these programs FairFuzz achieves high branch coverage at a faster rate that state-of-the-art versions of AFL. In addition, on programs with nested conditional structure, it achieves sustained increases in branch coverage after 24 hours (average 10.6% increase). In qualitative analysis, we find that FairFuzz has an increased capacity to automatically discover keywords.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The check wasn’t confident either way, so it gives no verdict — never disputed.
In the citing paper
“Compared to our coverage-guided baseline which only adds programs with new coverage to the seed bank for later mutation, our fitness function has minimal additional overhead.”
From Large Language Models Are Zero-Shot Fuzzers: Fuzzing Deep-Learning Libraries via Large Language Models (2023) · cites this paper as [42]
Experimental — accuracy not yet measured
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Symbolic execution and program testing
King, J. C. (1976) · Communications of the ACM · doi:10.1145/360248.360252 · Cited by 3,031 · cited 1×
“While many of the individual test inputs it generates may be garbage, due to its low computational overhead, CGF generates test inputs much faster than more sophisticated methods such as symbolic execution [17, 34] and dynamic symbolic execution (a.”
MethodCUTE: a concolic unit testing engine for C
Sen, K., Marinov, D., & Agha, G. (2005) · Proceedings of the 10th European software engineering conference held jointly with 13th ACM SIGSOFT international symposium on Foundations of software engineering · doi:10.1145/1081706.1081750 · Cited by 1,651 · cited 2×
“concolic testing) techniques [5, 7, 13, 16, 21, 22, 36, 45, 47].”
MethodSelf-citationDART: directed automated random testing
Godefroid, P., Klarlund, N., & Sen, K. (2005) · Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation · doi:10.1145/1065010.1065036 · Cited by 1,570 · cited 3×
“concolic testing) techniques [5, 7, 13, 16, 21, 22, 36, 45, 47].”
BackgroundMethodSelf-citationEvoSuite: automatic test suite generation for object-oriented software
Fraser, G., & Arcuri, A. (2011) · Proceedings of the 19th ACM SIGSOFT symposium and the 13th European conference on Foundations of software engineering · doi:10.1145/2025113.2025179 · Cited by 1,110 · cited 1×
“Evosuite [19] uses seed inputs and genetic algorithms to achieve high code coverage.”
MethodAutomated software test data generation
Korel, B. (1990) · IEEE Transactions on Software Engineering · doi:10.1109/32.57624 · Cited by 971 · cited 1×
“Search-based software testing (SBST) [19, 20, 22–24, 29, 31, 32, 42] uses optimization techniques such as hill climbing and genetic algorithms to generate inputs that optimize some observable fitness function.”
MethodDriller: Augmenting Fuzzing Through Selective Symbolic Execution
Stephens, N., Grosen, J., Salls, C., Dutcher, A., Wang, R., Corbetta, J., Shoshitaishvili, Y., Kruegel, C., & Vigna, G. (2016) · Proceedings 2016 Network and Distributed System Security Symposium · doi:10.14722/ndss.2016.23368 · Cited by 887
Finding and understanding bugs in C compilers
Yang, X., Chen, Y., Eide, E., & Regehr, J. (2011) · Proceedings of the 32nd ACM SIGPLAN Conference on Programming Language Design and Implementation · doi:10.1145/1993498.1993532 · Cited by 825 · cited 3×
“In practice, this trade-off has paid off, and fuzz testers have found numerous correctness bugs and security vulnerabilities in widely used software [9, 14, 25, 26, 28, 34, 39, 41, 43].”
BackgroundMethodBöhme, M., Pham, V.-T., Nguyen, M.-D., & Roychoudhury, A. (2017) · Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/3133956.3134020 · Cited by 747 · cited 3×
“The success of one particular fuzz tester, American Fuzzy Lop (or simply AFL) [43], has gained attention both in practice and in the research community [8, 9, 30, 39].”
BackgroundMethodResultInfluentialCoverage-based Greybox Fuzzing as Markov Chain
Böhme, M., Pham, V.-T., & Roychoudhury, A. (2016) · Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/2976749.2978428 · Cited by 649
The Current State and Future of Search Based Software Engineering
Harman, M. (2007) · Future of Software Engineering (FOSE '07) · doi:10.1109/fose.2007.29 · Cited by 631 · cited 1×
“Search-based software testing (SBST) [24, 25, 27–29, 35, 38, 39, 50] uses optimization techniques such as hill climbing and genetic algorithms to generate inputs that optimize some observable fitness function.”
MethodVUzzer: Application-aware Evolutionary Fuzzing
Rawat, S., Jain, V., Kumar, A., Cojocar, L., Giuffrida, C., & Bos, H. (2017) · Proceedings 2017 Network and Distributed System Security Symposium · doi:10.14722/ndss.2017.23404 · Cited by 584 · cited 1×
“VUzzer’s [35] approach is reminiscent of these, using both static and dynamic analysis to get immediate values used in comparisons (likely to be magic numbers), positions in the input likely to be magic numbers are offset, and information about which basic blocks are hard to get to.”
BackgroundRandoop: feedback-directed random testing for Java
Pacheco, C., & Ernst, M. D. (2007) · Companion to the 22nd ACM SIGPLAN conference on Object-oriented programming systems and applications companion · doi:10.1145/1297846.1297902 · Cited by 558 · cited 1×
“Randoop [41] automatically generates test cases for object oriented-programs through feedback-directed random test generation.”
Angora: Efficient Fuzzing by Principled Search
Chen, P., & Chen, H. (2018) · 2018 IEEE Symposium on Security and Privacy (SP) · doi:10.1109/sp.2018.00046 · Cited by 552
Grammar-based whitebox fuzzing
Godefroid, P., Kiezun, A., & Levin, M. Y. (2008) · Proceedings of the 29th ACM SIGPLAN Conference on Programming Language Design and Implementation · doi:10.1145/1375581.1375607 · Cited by 462 · cited 2×
“It has been used successfully by major software companies such as Microsoft [16] and Google [5, 13, 33] for security testing and quality assurance.”
BackgroundMethodCUTE and jCUTE: Concolic Unit Testing and Explicit Path Model-Checking Tools
Sen, K., & Agha, G. (2006) · Lecture Notes in Computer Science · doi:10.1007/11817963_38 · Cited by 389 · cited 3×
“While many individual test inputs generated by fuzz testing may be garbage, due to its low computational overhead, fuzz testing can generate test inputs much faster than more sophisticated methods such as dynamic symbolic execution [11, 17, 37, 38].”
BackgroundSelf-citationTaintScope: A Checksum-Aware Directed Fuzzing Tool for Automatic Software Vulnerability Detection
Wang, T., Wei, T., Gu, G., & Zou, W. (2010) · 2010 IEEE Symposium on Security and Privacy · doi:10.1109/sp.2010.37 · Cited by 380 · cited 1×
“BuzzFuzz [15] and TaintScope [40] pair taint analysis with the detection of potential attack points (i.e. array allocations) to find crashes more effectively.”
BackgroundPareto efficient multi-objective test case selection
Yoo, S., & Harman, M. (2007) · Proceedings of the 2007 international symposium on Software testing and analysis · doi:10.1145/1273463.1273483 · Cited by 357 · cited 1×
“Search-based software testing (SBST) [19, 20, 22–24, 29, 31, 32, 42] uses optimization techniques such as hill climbing and genetic algorithms to generate inputs that optimize some observable fitness function.”
MethodTaint-based directed whitebox fuzzing
Ganesh, V., Leek, T., & Rinard, M. (2009) · 2009 IEEE 31st International Conference on Software Engineering · doi:10.1109/icse.2009.5070546 · Cited by 348
Search-Based Software Testing: Past, Present and Future
McMinn, P. (2011) · 2011 IEEE Fourth International Conference on Software Testing, Verification and Validation Workshops · doi:10.1109/icstw.2011.100 · Cited by 322 · cited 1×
“Search-based software testing (SBST) [19, 20, 22–24, 29, 31, 32, 42] uses optimization techniques such as hill climbing and genetic algorithms to generate inputs that optimize some observable fitness function.”
MethodSteelix: program-state based binary fuzzing
Li, Y., Chen, B., Chandramohan, M., Lin, S.-W., Liu, Y., & Tiu, A. (2017) · Proceedings of the 2017 11th Joint Meeting on Foundations of Software Engineering · doi:10.1145/3106237.3106295 · Cited by 269 · cited 5×
“While playing with AFL and its extensions, we observed—as others have in the past [1, 9, 30, 39] — one important limitation of AFL: AFL often fails to explore programs very deeply, i.”
BackgroundInfluentialAutomatic Generation of Floating-Point Test Data
Miller, W., & Spooner, D. L. (1976) · IEEE Transactions on Software Engineering · doi:10.1109/tse.1976.233818 · Cited by 252
Program-Adaptive Mutational Fuzzing
Cha, S. K., Woo, M., & Brumley, D. (2015) · 2015 IEEE Symposium on Security and Privacy · doi:10.1109/sp.2015.50 · Cited by 231 · cited 1×
“BFF [28] and Sym-Fuzz [12] adapt this parameter automatically, by measuring crash density (number of mutated inputs finding crashes) and doing input bit dependence, respectively.”
BackgroundEnhancing symbolic execution with veritesting
Avgerinos, T., Rebert, A., Cha, S. K., & Brumley, D. (2014) · Proceedings of the 36th International Conference on Software Engineering · doi:10.1145/2568225.2568293 · Cited by 218 · cited 1×
“Prior work demonstrates that after a certain amount of coverage is achieved, even small increases in branch coverage can yield more bug finding power [7].”
BackgroundThe S2E Platform: Design, Implementation, and Applications
Chipounov, V., Kuznetsov, V., & Candea, G. (2012) · ACM Transactions on Computer Systems · doi:10.1145/2110356.2110358 · Cited by 206 · cited 1×
“concolic testing) techniques [5, 7, 13, 16, 21, 22, 36, 45, 47].”
Maintaining and evolving GUI-directed test scripts
Grechanik, M., Xie, Q., & Fu, C. (2009) · 2009 IEEE 31st International Conference on Software Engineering · doi:10.1109/icse.2009.5070540 · Cited by 161
Clarke, L. A. (1976) · ACM Annual Conference · doi:10.1145/800191.805647 · Cited by 139 · cited 1×
“While many of the individual test inputs it generates may be garbage, due to its low computational overhead, CGF generates test inputs much faster than more sophisticated methods such as symbolic execution [17, 34] and dynamic symbolic execution (a.”
MethodSynthesizing program input grammars
Bastani, O., Sharma, R., Aiken, A., & Liang, P. (2017) · Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation · doi:10.1145/3062341.3062349 · Cited by 131 · cited 1×
“…methods to learn the structure of pdf objects, leveraging this to produce new valid pdf. Autogram [27] proposes a taint analysis-based approach to learning input grammars, while Glade [6] uses an iterative approach and repeated calls to an oracle to learn a context-free grammar for a set of inputs.”
MethodMining input grammars from dynamic taints
Höschele, M., & Zeller, A. (2016) · IEEE/ACM International Conference on Automated Software Engineering (ASE) · doi:10.1145/2970276.2970321 · Cited by 126 · cited 1×
“Learn&Fuzz [18] uses sequence-based learning methods to learn the structure of pdf objects, leveraging this to produce new valid pdf. Autogram [27] proposes a taint analysis-based approach to learning input grammars, while Glade [6] uses an iterative approach and repeated calls to an oracle to…”
MethodLearn&Fuzz: Machine Learning for Input FuzzingPreprint
Godefroid, P., Peleg, H., & Singh, R. K. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1701.07232 · Cited by 41 · cited 1×
“Learn&Fuzz [23] uses sequencebased learning methods to learn the structure of PDF objects, Autogram [32] proposes a taint analysis-based approach to learning input grammars, while Glade [8] uses an iterative approach and repeated calls to an oracle to learn a context-free grammar for a set of inputs.”
Method
Research works printed but not linked: 18
- 10.5555/1763507.1763523 · doi:10.5555/1763507.1763523
- [7] Marcel Böhme. 2016. AFLFast.new. https://groups.google.com/d/msg/afl-users/ 1PmKJC-EKZ0/lbzRb8AuAAAJ. (2016). Accessed August 23rd, 2017. -
- [11] 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) . -
- [13] Chris Evans, Matt Moore, and Tavis Ormandy. 2011. Fuzzing at Scale. https:// security.googleblog.com/2011/08/fuzzing-at-scale.html. (2011). Accessed August 24th, 2017. -
- [19] Mark Grechanik, Chen Fu, and Qing Xie. 2012. Automatically finding performance problems with feedback-directed learning software testing. In 2012 34th International Conference on Software Engineering (ICSE) . IEEE, 156-166. - · doi:10.5555/2337223.2337242
- [21] 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) . -
- [23] Mark Harman and John Clark. 2004. Metrics are fitness functions too. In Software Metrics, 2004. Proceedings. 10th International Symposium on . IEEE, 58-69. - · doi:10.5555/1018439.1021893
- [24] Mark Harman and Bryan F Jones. 2001. Search-based software engineering. Information and software Technology 43, 14 (2001), 833-839. -
- [25] Sam Hocevar. 2007. zzuf. http://caca.zoy.org/wiki/zzuf/. (2007). Accessed August 22nd, 2017. -
- [26] Christian Holler, Kim Herzig, and Andreas Zeller. 2012. Fuzzing with Code Fragments. In Presented as part of the 21st USENIX Security Symposium (USENIX Security 12) . -
- [28] Allen D. Householder and Jonathan M. Foote. 2012. Probability-Based Parameter Selection for Black-Box Fuzz Testing . Technical Report. Carnegie Mellon University Software Engineering Institute. -
- Guodong Li , Indradeep Ghosh , and Sreeranga P . Rajan . 2011 . KLOVER : A Symbolic Execution and Automatic Test Generation Tool for C++ Programs. In CAV. 609–615. Guodong Li, Indradeep Ghosh, and Sreeranga P. Rajan. 2011. KLOVER: A Symbolic Execution and Automatic Test Generation Tool for C++ Programs. In CAV. 609–615.
- 10.5555/1792786.1792798 · doi:10.5555/1792786.1792798
- [43] Michał Zalewski. 2014. American Fuzzy Lop. http://lcamtuf.coredump.cx/afl. (2014). Accessed August 18th, 2017. -
- [44] Michał Zalewski. 2016. FidgetyAFL. https://groups.google.com/d/msg/afl-users/ fOPeb62FZUg/CES5lhznDgAJ. (2016). Accessed August 23rd, 2017. -
- [45] Michał Zalewski. 2016. Unique crashes as a metric. https://groups.google.com/ d/msg/afl-users/fOPeb62FZUg/LYxgPYheDwAJ. (2016). Accessed August 24th, 2017. -
- [46] Michał Zalewski. 2017. American Fuzzy Lop Technical Details. http://lcamtuf. coredump.cx/afl/technical\_details.txt. (2017). Accessed August 18th, 2017. -
- [47] Andreas Zeller and Ralf Hildebrandt. 2002. Simplifying and Isolating FailureInducing Input. IEEE Transactions on Software Engineering 28, 2 (2002), 183-200.
Cited by
Deep Learning Based Vulnerability Detection: Are We There Yet?
Chakraborty, S., Krishna, R., Ding, Y., & Ray, B. (2022) · IEEE Transactions on Software Engineering · doi:10.1109/tse.2021.3087402 · Cited by 790
“Traditional vulnerability detection systems fall into three major categories – static analysis [26], [65], dynamic analysis [66], [67], and symbolic analysis [68], [69].”
BackgroundKlees, G., Ruef, A., Cooper, B., Wei, S., & Hicks, M. (2018) · Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/3243734.3243804 · Cited by 633
(2021) · doi:10.1109/tse.2019.2946563 · Cited by 574
“FairFuzz [141] H# ✓ ✓ ✓† H#† ✓ ✓ ✓ go-fuzz [225] H# ✓ ✓ ✓ ✓ ✓ ✓ H# ✓ Hawkeye [56] H# ✓ ✓ ✓ ✓ H# ✓ ✓ honggfuzz [213] H# ✓ ✓ ✓ kAFL [191] H# ✓ ✓ LibFuzzer [9] H# ✓ ✓ ✓ ✓ ✓ ✓ MagicFuzzer [50] H# ✓ ✓ ✓ Nautilus [25] H# ✓ ✓ ✓ H# ✓ ✓ RaceFuzzer [197] H# ✓ ✓ ✓ RedQueen [26] H# ✓ ✓ H# ✓”
BackgroundInfluentialQSYM: a practical concolic execution engine tailored for hybrid fuzzing
Yun, I., Lee, S.-H., Xu, M., Jang, Y., & Kim, T. (2018) · USENIX Security Symposium · Cited by 343
Zhu, X., Wen, S., Camtepe, S., & Xiang, Y. (2022) · ACM Computing Surveys · doi:10.1145/3512345 · Cited by 334
“Most fuzzers select bytes heuristically based on execution information [7, 37, 38, 67, 101, 103, 157, 160, 187] or randomly [22, 23, 118, 203, 206].”
Background
Metadata
- Authors
- Lemieux, C., & Sen, K.
- Affiliations
- University of California, Berkeley (US)
- Venue
- Proceedings of the 33rd ACM/IEEE International Conference on Automated Software Engineering
- Publisher
- ACM
- Published
- 2018-09-03
- Pages
- 475-485
- OpenAlex
- W2757104921
- Cited by
- 477
- References
- 29
- Citations by year
- 2026: 39 · 2025: 60 · 2024: 69 · 2023: 65 · 2022: 62 · 2021: 68 · 2020: 59 · 2019: 47 · 2018: 8
- FWCI
- 30.83
- Type
- conference paper
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- IEEE/ACM International Conference on Automated Software Engineering (ASE) (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- Funders
- National Science Foundation (CCF-1409872, CCF-1423645)
- Topics
- Physical Sciences › Computer Science › Software › Software Testing and Debugging Techniques
- Physical Sciences › Computer Science › Hardware and Architecture › Security and Verification in Computing
- Physical Sciences › Computer Science › Information Systems › Software Engineering Research
- Keywords
- targeted mutations, branch coverage, code coverage, software testing, bug detection
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.