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

Show all 29 references

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

Items 201–300 of 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.