Corpus Minimization (afl-cmin)

Relevant source files

The following files were used as context for generating this wiki page: - [afl-cmin.bash](https://github.com/lagraviereScience/AFLplusplus/blob/HEAD/afl-cmin.bash) - [src/afl-fuzz.c](https://github.com/lagraviereScience/AFLplusplus/blob/HEAD/src/afl-fuzz.c) - [src/afl-fuzz-init.c](https://github.com/lagraviereScience/AFLplusplus/blob/HEAD/src/afl-fuzz-init.c) - [custom_mutators/libfuzzer/FuzzerMerge.cpp](httpshttps://github.com/lagraviereScience/AFLplusplus/blob/HEAD/custom_mutators/libfuzzer/FuzzerMerge.cpp) - [utils/README.md](https://github.com/lagraviereScience/AFLplusplus/blob/HEAD/utils/README.md) - [config.h](https://github.com/lagraviereScience/AFLplusplus/blob/HEAD/config.h)

Corpus minimization is a process in AFL++ handled by the afl-cmin tool. Its purpose is to find the smallest subset of files from a larger input corpus that still preserves the full range of code coverage (instrumentation data points) observed in the original set. This is particularly useful for two main scenarios: screening a large, externally-sourced corpus before starting a fuzzing campaign to remove redundant files, and minimizing a corpus that was organically grown by afl-fuzz to make it more manageable for other tools or for archival.

The afl-cmin tool, which evolved from the earlier minimize_corpus.sh script, operates by analyzing the coverage traces of each file and selecting a minimal set that covers all unique execution paths. It does not alter the content of the files themselves; for that, the afl-tmin tool should be used. The process is essential for optimizing the fuzzing startup phase and improving overall efficiency by eliminating functionally redundant seed inputs.

Sources: afl-cmin.bash:13-33, utils/README.md:62-63

Core Logic and Workflow

The afl-cmin.bash script orchestrates a multi-step process to achieve corpus minimization. It relies heavily on afl-showmap to gather coverage information.

The overall workflow is as follows:

1. Setup and Sanity Checks: The script parses command-line arguments, validates the input/output directories, and checks for the afl-showmap binary. It also creates a temporary directory (.traces) inside the output directory to store coverage data for each input file.
2. Trace Collection: It iterates through every file in the input directory. For each file, it runs afl-showmap to execute the target binary and records the resulting coverage tuples into a corresponding file within the .traces directory. This step can be parallelized using the -T option.
3. Tuple Aggregation and Sorting: All unique tuples from all trace files are collected, counted, and sorted by their frequency (popularity) across the entire corpus. The least frequent tuples are placed first.
4. Candidate Selection: The script identifies the "best" candidate file for each unique tuple. The "best" is defined as the smallest input file that triggers that specific tuple. This is achieved by creating a list of (tuple, file) pairs and sorting it to find the smallest file for each unique tuple.
5. Greedy Corpus Construction: The script iterates through the unique tuples, from least popular to most popular. For each tuple not yet covered by the minimized set, it adds the "best" candidate file for that tuple to the output directory. It then adds all tuples from that newly added file to a master list of covered tuples. This greedy approach ensures that files covering rare paths are prioritized, and subsequent files are only added if they contribute new, previously unseen coverage.
6. Cleanup: The temporary .traces directory is removed unless AFL_KEEP_TRACES is set.

Sources: afl-cmin.bash:237-440

This diagram illustrates the high-level workflow of the afl-cmin.bash script.

Command-Line Interface

afl-cmin.bash is configured through a set of command-line options that control its execution, memory and time limits, and minimization strategy.

Option	Argument	Description
-i	dir	Required. Input directory containing the starting corpus.
-o	dir	Required. Output directory for the minimized corpus.
-f	file	Location read by the fuzzed program. Defaults to stdin or @@. Cannot be used with -T.
-m	megs	Memory limit for the child process in megabytes. Defaults to none.
-t	msec	Run time limit for the child process in milliseconds. Defaults to 5000.
-T	tasks	Number of parallel processes to create for trace collection. Use all for nproc.
-O		Use binary-only instrumentation (FRIDA mode).
-Q		Use binary-only instrumentation (QEMU mode).
-U		Use unicorn-based instrumentation (Unicorn mode).
-X / -Y		Use Nyx mode for VM-based fuzzing.
-A		Allow crashing and timeout-inducing inputs in the final corpus.
-C		Keep only crashing inputs and reject all others.
-e		Solve for edge coverage only, ignoring hit counts.

Sources: afl-cmin.bash:80-137

Environment Variables

The script's behavior can also be influenced by several environment variables.

Variable	Description
AFL_KEEP_TRACES	If set, the temporary <out_dir>/.traces directory is not deleted after the run.
AFL_NO_FORKSRV	Disables the forkserver, running the target via execve for each input.
AFL_PATH	Specifies a path to find the afl-showmap binary if it's not in the system's PATH.
AFL_SKIP_BIN_CHECK	Skips the check for whether the target binary is instrumented.
AFL_CMIN_CRASHES_ONLY	If set, only keeps inputs that cause the target to crash. Equivalent to the -C flag.
AFL_CMIN_ALLOW_ANY	If set, allows inputs that crash or time out to be included in the output corpus. Equivalent to the -A flag.

Sources: afl-cmin.bash:139-148

Minimization and Selection Strategy

The core of afl-cmin's effectiveness comes from its greedy algorithm for selecting the final set of files.

1. Prioritizing Rarity: By processing tuples from least-frequent to most-frequent, the algorithm ensures that files covering rare and unique code paths are included first.
2. Prioritizing Size: For any given tuple, the script pre-selects the smallest file that triggers it. This means that when a file is chosen to cover a rare tuple, it is the most compact representation of that path.
3. Coverage Tracking: A master list of covered tuples (.already_have) is maintained. A file is only added to the output set if it provides at least one tuple that is not in this master list. After a file is added, all of its tuples are merged into the master list.

This ensures that the final corpus is minimal because no file is included if its coverage is already completely provided by other, smaller, or rarer-path-covering files already in the set.

The following diagram shows the logic for deciding whether to include a candidate file in the output set.

Related Corpus Management Concepts

Corpus minimization is one of several corpus management techniques within AFL++. Other related concepts include corpus merging and dynamic queue culling.

Corpus Merging

Corpus merging, implemented in libfuzzer/FuzzerMerge.cpp, is the opposite of minimization. It aims to combine multiple corpora into one, eliminating duplicates. The CrashResistantMerge function implements a "greedy pass" that is conceptually similar to afl-cmin. It sorts new inputs and adds a file to the merged corpus if it introduces new features (coverage) not present in the existing set. This highlights a shared principle: managing corpora based on unique coverage contributions.

Sources: custom_mutators/libfuzzer/FuzzerMerge.cpp:188-235

Queue Culling

During a fuzzing run, afl-fuzz itself performs a form of online corpus minimization through a process called "culling". The cull_queue function periodically reviews the entire queue of test cases. It attempts to find a smaller subset of "favored" inputs that still cover the entire discovered bitmap. Entries that are found to be redundant (i.e., their coverage is a subset of other favored entries) are not removed but are less likely to be chosen for fuzzing in the future. This dynamic process keeps the active fuzzing queue efficient without requiring an offline tool like afl-cmin.

Sources: src/afl-fuzz.c:7093-7100

Conclusion

afl-cmin is an indispensable utility in the AFL++ suite for corpus hygiene. By employing a sophisticated yet efficient greedy algorithm, it reduces large collections of inputs to a minimal, coverage-equivalent set. This process is crucial for bootstrapping new fuzzing campaigns with clean, non-redundant seeds and for archiving the results of a fuzzing run in a compact format. Its reliance on afl-showmap for trace data and its parallel processing capabilities make it a powerful tool for any serious fuzzing effort.