CoChat

FairFuzz: a targeted mutation strategy for increasing greybox fuzz testing coverage

Open access
Lemieux, Caroline, Sen, Koushik · 2018 · Proceedings of the 33rd ACM/IEEE International Conference on Automated Software Engineering

The 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.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1145/3238147.3238176

Cites

29 of 29 references verified0 citation errors · 0 not checkable

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.

A few free checks a day · papers already verified open instantly · results are public

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?

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.”
    Method
  • CUTE: 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-citation
  • DART: 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-citation
  • EvoSuite: 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.”
    Method
  • Automated 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.”
    Method
  • Driller: 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].”
    BackgroundMethod
  • Directed Greybox Fuzzing

    Bö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].”
    BackgroundMethodResultInfluential
  • Coverage-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.”
    Method
  • VUzzer: 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.”
    Background
  • Randoop: 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.”
    BackgroundMethod
  • CUTE 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-citation
  • TaintScope: 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.”
    Background
  • Pareto 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.”
    Method
  • Taint-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.”
    Method
  • Steelix: 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.”
    BackgroundInfluential
  • Automatic 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.”
    Background
  • Enhancing 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].”
    Background
  • The 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

  • A program testing system

    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.”
    Method
  • Synthesizing 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.”
    Method
  • Mining 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…”
    Method
  • Learn&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

  1. 10.5555/1763507.1763523 · doi:10.5555/1763507.1763523
  2. [7] Marcel Böhme. 2016. AFLFast.new. https://groups.google.com/d/msg/afl-users/ 1PmKJC-EKZ0/lbzRb8AuAAAJ. (2016). Accessed August 23rd, 2017. -
  3. [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) . -
  4. [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. -
  5. [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
  6. [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) . -
  7. [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
  8. [24] Mark Harman and Bryan F Jones. 2001. Search-based software engineering. Information and software Technology 43, 14 (2001), 833-839. -
  9. [25] Sam Hocevar. 2007. zzuf. http://caca.zoy.org/wiki/zzuf/. (2007). Accessed August 22nd, 2017. -
  10. [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) . -
  11. [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. -
  12. 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.
  13. 10.5555/1792786.1792798 · doi:10.5555/1792786.1792798
  14. [43] Michał Zalewski. 2014. American Fuzzy Lop. http://lcamtuf.coredump.cx/afl. (2014). Accessed August 18th, 2017. -
  15. [44] Michał Zalewski. 2016. FidgetyAFL. https://groups.google.com/d/msg/afl-users/ fOPeb62FZUg/CES5lhznDgAJ. (2016). Accessed August 23rd, 2017. -
  16. [45] Michał Zalewski. 2016. Unique crashes as a metric. https://groups.google.com/ d/msg/afl-users/fOPeb62FZUg/LYxgPYheDwAJ. (2016). Accessed August 24th, 2017. -
  17. [46] Michał Zalewski. 2017. American Fuzzy Lop Technical Details. http://lcamtuf. coredump.cx/afl/technical\_details.txt. (2017). Accessed August 18th, 2017. -
  18. [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].”
    Background
  • Evaluating Fuzz Testing

    Klees, 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

  • “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# ✓”
    BackgroundInfluential
  • QSYM: 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

  • Fuzzing: A Survey for Roadmap

    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

See all 477

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
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.