American Fuzzy Lop (software) explained

American Fuzzy Lop
Developer:Michał Zalewski
Latest Release Version:2.57b
Latest Release Date:[1]
Operating System:Cross-platform
Programming Language:C, assembly
Genre:Fuzzer
License:Apache License 2.0

American Fuzzy Lop (AFL), stylized in all lowercase as , is a free software fuzzer that employs genetic algorithms in order to efficiently increase code coverage of the test cases. So far it has detected dozens of significant software bugs in major free software projects, including X.Org Server,[2] PHP,[3] OpenSSL,[4] [5] pngcrush, bash,[6] Firefox,[7] BIND,[8] [9] Qt,[10] and SQLite.[11]

For many years after its release, AFL has been considered a "state of the art" fuzzer.[12] AFL is considered "a de-facto standard for fuzzing", and the release of AFL contributed significantly to the development of fuzzing as a research area.[13] AFL is widely used in academia; academic fuzzers are often forks of AFL, and AFL is commonly used as a baseline to evaluate new techniques.[14]

The source code of American fuzzy lop is published on GitHub. Its name is a reference to a breed of rabbit, the American Fuzzy Lop.

American Fuzzy Lop (AFL), stylized in all lowercase as american fuzzy lop, is a free software fuzzer that employs genetic algorithms in order to efficiently increase code coverage of the test cases. Initially released in November 2013, AFL[15] quickly became one of the most widely used fuzzers in security research.

Overview

AFL requires the user to provide a sample command that runs the tested application and at least one small example input. The input can be fed to the tested program either via standard input or as an input file specified in the process command line. Fuzzing networked programs is currently not directly supported, although in some cases there are feasible solutions to this problem.[16] For example, in case of an audio player, American fuzzy lop can be instructed to open a short sound file with it. Then, the fuzzer attempts to actually execute the specified command and if that succeeds, it tries to reduce the input file to the smallest one that triggers the same behavior.

After this initial phase, AFL begins the actual process of fuzzing by applying various modifications to the input file. When the tested program crashes or hangs, this usually implies the discovery of a new bug, possibly a security vulnerability. In this case, the modified input file is saved for further user inspection.

In order to maximize the fuzzing performance, American fuzzy lop expects the tested program to be compiled with the aid of a utility program that instruments the code with helper functions which track control flow. This allows the fuzzer to detect when the target's behavior changes in response to the input. In cases when this is not possible, black-box testing is supported as well.

Fuzzing algorithm

Fuzzers attempt to find unexpected behaviors (i.e., bugs) in a target program by repeatedly executing the program on various inputs. As described above, AFL is a gray-box fuzzer, meaning it injects instrumentation to measure code coverage into the target program at compile time and uses the coverage metric to direct the generation of new inputs. AFL's fuzzing algorithm has influenced many subsequent gray-box fuzzers.[17]

The inputs to AFL are an instrumented target program (the system under test) and corpus, that is, a collection of inputs to the target. Inputs are also known as test cases. The algorithm maintains a queue of inputs, which is initialized to the input corpus. The overall algorithm works as follows:[18]

  1. Load the next input from the queue
  2. Minimize the test case
  3. Mutate the test case. If any mutant results in additional code coverage, add it to the queue. If the mutant results in a crash or hang, save it to disk for later inspection.
  4. Go to step 1

Mutation

To generate new inputs, AFL applies various mutations to existing inputs. These mutations are mostly agnostic to the input format of the target program; they generally treat the input as simple blob of binary data.

At first, AFL applies a deterministic sequence of mutations to each input. These are applied at various offsets in the input. They include:[19] [20]

After applying all available deterministic mutations, AFL moves on to havoc, a stage where between 2 and 128 mutations are applied in a row. These mutations are any of:

If AFL cycles through the entire queue without generating any input that achieves new code coverage, it begins splicing. Splicing takes two inputs from the queue, truncates them at arbitrary positions, concatenates them together, and applies the havoc stage to the result.

Measuring coverage

AFL pioneered the use of binned hitcounts for measuring code coverage. The author claims that this technique mitigates path explosion.[23] [24]

Conceptually, AFL counts the number of times a given execution of the target traverses each edge in the target's control-flow graph; the documentation refers to these edges as tuples and the counts as hitcounts. At the end of the execution, the hitcounts are binned or bucketed into the following eight buckets: 1, 2, 3, 4–7, 8–15, 16–31, 32–127, and 128 and greater. AFL maintains a global set of (tuple, binned count) pairs that have been produced by any execution thus far. An input is considered "interesting" and is added to the queue if it produces a (tuple, binned count) pair that is not yet in the global set.

In practice, the hitcounts are collected and processed using an efficient but lossy scheme. The compile-time instrumentation injects code that is conceptually similar to the following at each branch in the control-flow graph of the target program:[25]

cur_location = ;shared_mem[cur_location ^ prev_location]++;prev_location = cur_location >> 1;

where <COMPILE_TIME_RANDOM> is a random integer and shared_mem is a 64 kilobyte region of memory shared between the fuzzer and the target.

This representation is more fine-grained (distinguishes between more executions) than simple block or statement coverage, but still allows for a linear-time "interestingness" test.

Minimization

On the assumption that smaller inputs take less time to execute, AFL attempts to minimize or trim the test cases in the queue.[26] Trimming works by removing blocks from the input; if the trimmed input still results in the same coverage (see

  1. Measuring coverage
), then the original input is discarded and the trimmed input is saved in the queue.

Scheduling

AFL selects a subset of favored inputs from the queue, non-favored inputs are skipped with some probability.[27]

Features

Performance features

One of the challenges American fuzzy lop had to solve involved an efficient spawning of hundreds of processes per second. Apart from the original engine that spawned every process from scratch, American fuzzy lop offers the default engine that relies heavily on the [[fork (system call)|fork]] system call.[28] This can further be sped up by leveraging LLVM deferred fork server mode or the similar persistent mode, but this comes at the cost of having to modify the tested program.[29] Also, American fuzzy lop supports fuzzing the same program over the network.

User interface

American fuzzy lop features a colorful command line interface that displays real-time statistics about the fuzzing process. Various settings may be triggered by either command line options or environment variables. Apart from that, programs may read runtime statistics from files in a machine-readable format.

Utility programs

In addition to afl-fuzz and tools that can be used for binary instrumentation, American fuzzy lop features utility programs meant for monitoring of the fuzzing process. Apart from that, there is afl-cmin and afl-tmin, which can be used for test case and test corpus minimization. This can be useful when the test cases generated by afl-fuzz would be used by other fuzzers.

Forks

AFL has been forked many times in order to examine new fuzzing techniques, or to apply fuzzing to different kinds of programs. A few notable forks include:

AFL++

Qid:Q105970848
AFL++
Released:2.52c /
Latest Release Version:4.08c
Latest Release Date:[35]

AFL++ (AFLplusplus)[36] is a community-maintained fork of AFL created due to the relative inactivity of Google's upstream AFL development since September 2017. It includes new features and speedups.[37]

Google's OSS-Fuzz initiative, which provides free fuzzing services to open source software, replaced its AFL option with AFL++ in January 2021.[38]

References

Sources

Further reading

External links

Notes and References

  1. Web site: Releases - google/AFL. January 19, 2021. GitHub.
  2. Web site: Advisory-2015-03-17. x.org.
  3. Web site: NVD - Detail. nist.gov.
  4. Web site: NVD - Detail. nist.gov.
  5. Web site: NVD - Detail. nist.gov.
  6. Web site: CVE - CVE-2014-6278. mitre.org.
  7. Web site: CVE - CVE-2014-8637. mitre.org.
  8. Web site: How to fuzz a server with American Fuzzy Lop. Fastly. July 21, 2015 .
  9. Web site: CVE - CVE-2015-5477. mitre.org.
  10. Web site: [Announce] Qt Project Security Advisory - Multiple Vulnerabilities in Qt Image Format Handling]. qt-project.org. April 13, 2015 .
  11. Web site: How SQLite Is Tested # 4.1.1. SQL Fuzz Using The American Fuzzy Lop Fuzzer. sqlite.org.
  12. Book: Poncelet . Clement . Sagonas . Konstantinos . Tsiftes . Nicolas . Proceedings of the 37th IEEE/ACM International Conference on Automated Software Engineering . So Many Fuzzers, So Little Time✱ . January 5, 2023 . https://doi.org/10.1145/3551349.3556946 . ASE '22 . New York, NY, USA . Association for Computing Machinery . 1–12 . 10.1145/3551349.3556946 . 978-1-4503-9475-8. 253456740 .
  13. Book: Fioraldi . Andrea . Maier . Dominik Christian . Zhang . Dongjia . Balzarotti . Davide . Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security . LibAFL . November 7, 2022 . https://doi.org/10.1145/3548606.3560602 . CCS '22 . New York, NY, USA . Association for Computing Machinery . 1051–1065 . 10.1145/3548606.3560602 . 978-1-4503-9450-5. 253410747 . . "The release of AFL marked an important milestone in the area of software security testing, revitalizing fuzzing as a major research topic".
  14. Hazimeh . Ahmad . Herrera . Adrian . Payer . Mathias . June 15, 2021 . Magma: A Ground-Truth Fuzzing Benchmark . Proceedings of the ACM on Measurement and Analysis of Computing Systems . 4 . 3 . 49:1–49:29 . 10.1145/3428334. 2009.01120 . 227230949 .
  15. Web site: Test Management and Reporting Software . 2024-08-13 . www.aflglobal.com . en.
  16. Web site: Fuzzing nginx - Hunting vulnerabilities with afl-fuzz. Technion. lolware.net.
  17. Book: Chen . Peng . Chen . Hao . 2018 IEEE Symposium on Security and Privacy (SP) . Angora: Efficient Fuzzing by Principled Search . May 2018 . https://ieeexplore.ieee.org/document/8418633 . 711–725 . 10.1109/SP.2018.00046. 978-1-5386-4353-2 . 3729194 .
  18. Web site: Motivation behind AFL — AFL 2.53b documentation . February 26, 2023 . afl-1.readthedocs.io.
  19. Web site: Binary fuzzing strategies: what works, what doesn't. lcamtuf.blogspot.com. August 8, 2014 .
  20. Web site: AFL User Guide — AFL 2.53b documentation . February 26, 2023 . afl-1.readthedocs.io.
  21. Web site: Finding bugs in SQLite, the easy way. lcamtuf.blogspot.com. April 14, 2015 .
  22. Manès . Valentin J.M. . Han . HyungSeok . Han . Choongwoo . Cha . Sang Kil . Egele . Manuel . Schwartz . Edward J. . Woo . Maverick . November 2021 . The Art, Science, and Engineering of Fuzzing: A Survey . IEEE Transactions on Software Engineering . 47 . 11 . 2312–2331 . 10.1109/TSE.2019.2946563 . 1812.00140 . 102351047 . 1939-3520.
  23. Web site: Technical "whitepaper" for afl-fuzz.
  24. Web site: More about AFL — AFL 2.53b documentation . February 27, 2023 . afl-1.readthedocs.io. "This approach allows for a very fine-grained and long-term exploration of program state while not having to perform any computationally intensive and fragile global comparisons of complex execution traces, and while avoiding the scourge of path explosion."
  25. Web site: More about AFL — AFL 2.53b documentation . February 27, 2023 . afl-1.readthedocs.io.
  26. Web site: More about AFL — AFL 2.53b documentation . February 27, 2023 . afl-1.readthedocs.io.
  27. Web site: More about AFL — AFL 2.53b documentation . February 27, 2023 . afl-1.readthedocs.io.
  28. Web site: Fuzzing random programs without execve. lcamtuf.blogspot.com. October 14, 2014 .
  29. Web site: New in AFL: persistent mode . lcamtuf's blog . June 11, 2015.
  30. Book: Lyu . Chenyang . Ji . Shouling . Zhang . Chao . Li . Yuwei . Lee . Wei-Han . Song . Yu . Beyah . Raheem . 2019 . : Optimized Mutation Scheduling for Fuzzers . en . 1949–1966 . 978-1-939133-06-9.
  31. Böhme . Marcel . Pham . Van-Thuan . Roychoudhury . Abhik . May 2019 . Coverage-Based Greybox Fuzzing as Markov Chain . IEEE Transactions on Software Engineering . 45 . 5 . 489–506 . 10.1109/TSE.2017.2785841 . 1939-3520.
  32. Pham . Van-Thuan . Böhme . Marcel . Santosa . Andrew E. . Căciulescu . Alexandru Răzvan . Roychoudhury . Abhik . September 2021 . Smart Greybox Fuzzing . IEEE Transactions on Software Engineering . 47 . 9 . 1980–1997 . 10.1109/TSE.2019.2941681 . 53721813 . 1939-3520.
  33. Book: Böhme . Marcel . Pham . Van-Thuan . Nguyen . Manh-Dung . Roychoudhury . Abhik . Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security . Directed Greybox Fuzzing . October 30, 2017 . https://doi.org/10.1145/3133956.3134020 . CCS '17 . New York, NY, USA . Association for Computing Machinery . 2329–2344 . 10.1145/3133956.3134020 . 978-1-4503-4946-8. 29430742 .
  34. Book: Poeplau . Sebastian . Francillon . Aurélien . 2020 . Symbolic execution with : Don't interpret, compile! . en . 181–198 . 978-1-939133-17-5.
  35. Web site: Releases - AFLplusplus/AFLplusplus. November 1, 2023. GitHub.
  36. Andrea . Fioraldi . Dominik . Maier . Heiko . Eißfeldt . Marc . Heuse . AFL++: Combining incremental steps of fuzzing research . 14th USENIX Workshop on Offensive Technologies (WOOT 20) . August 2020 .
  37. Web site: The AFL++ fuzzing framework . AFLplusplus . en.
  38. Web site: metzman . jonathan . [afl++] Use AFL++ instead of AFL for fuzzing. by jonathanmetzman · Pull Request #5046 · google/oss-fuzz ]. GitHub . en.

This article is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article "American Fuzzy Lop (software)".

Except where otherwise indicated, Everything.Explained.Today is © Copyright 2009-2024, A B Cryer, All Rights Reserved. Cookie policy.