Redqueen: Input-to-State Correspondence
Relevant source files
The following files were used as context for generating this wiki page:
Redqueen is a powerful fuzzing strategy within AFL++ that automates the process of solving complex conditional checks in a target program. It implements a form of "Input-to-State Correspondence," where the fuzzer identifies relationships between the input data and the program's internal state (specifically, values used in comparisons). By leveraging this correspondence, Redqueen can intelligently modify inputs to satisfy "magic byte" checks, checksum validations, and other intricate path constraints, thereby unlocking new code paths for the fuzzer to explore.
This feature is built upon the CmpLog instrumentation, which logs the operands of comparison instructions during program execution. Redqueen analyzes these logs and attempts various strategies to manipulate the input file so that its contents match the logged runtime values. This process is handled by the input_to_state_stage function and is integrated as a deterministic fuzzing stage within the main fuzzing loop.
Sources: src/afl-fuzz-redqueen.c, include/afl-fuzz.h:1010-1013, qemu_mode/README.md:112-119
Architecture and Integration
The Redqueen functionality is not a standalone tool but a stage within the afl-fuzz main loop. It is enabled by using the -c command-line option, which activates CmpLog.
The primary entry point for this stage is the input_to_state_stage function, which is called from the main fuzzing function fuzz_one. To avoid redundant work, this expensive stage is typically run only once per queue entry, tracked by the colorized flag in the queue_entry struct.
Sources: src/afl-fuzz-redqueen.c:11-12, include/afl-fuzz.h:320, src/afl-fuzz.c:602-613
High-Level Flow
The following diagram illustrates the general workflow of the Redqueen stage.
This diagram shows how the Redqueen stage is triggered from the main fuzzing loop and processes a single queue entry to find new inputs.
Sources: src/afl-fuzz-redqueen.c, include/afl-fuzz.h:320
Sequence of Operations
The interaction between the main fuzzer, the Redqueen stage, and the target binary is crucial. The CmpLog forkserver plays a key role in efficiently gathering comparison data.
This sequence diagram details the interactions for gathering comparison data and testing potential solutions.
Sources: src/afl-fuzz-redqueen.c:832-840, src/afl-fuzz-cmplog.c, src/afl-fuzz-run.c:28-41
Core Data Structures
The Redqueen implementation relies on several key data structures to manage its state and findings.
| Structure | File | Description |
|---|---|---|
struct queue_entry | include/afl-fuzz.h | Represents an entry in the fuzzing queue. The colorized field is a flag to indicate if the Redqueen stage has already been performed. The taint field points to a linked list of tainted structs. |
struct tainted | include/afl-fuzz.h | A node in a linked list that marks a specific region (pos, len) of an input file as influencing a comparison. This is the "Input-to-State Correspondence" link. |
struct cmp_map | include/cmplog.h | A shared memory structure populated by CmpLog instrumentation. It contains a header and an array of logged comparison instructions and their runtime operand values. |
Sources: include/afl-fuzz.h:311-391, include/afl-fuzz.h:268-275, [src/afl-fuzz-cmplog.c]
Solving Strategies
Redqueen employs several strategies to solve the comparisons logged by CmpLog. These are controlled by the -l command-line option.
Sources: src/afl-fuzz-redqueen.c:36-101, src/afl-fuzz.c:687-731
Direct Replacement
The most basic strategy is to directly substitute a portion of the input file with a value observed at runtime. The taint analysis helps identify which part of the input corresponds to the memory operand of the cmp instruction. The fuzzer then replaces this part with the value from the other operand (often a constant or a register value).
Sources: src/afl-fuzz-redqueen.c:868-876
Arithmetic Solving (-lA)
The solve_arith function handles comparisons that involve simple arithmetic. It tries to solve for the input value by applying additions and subtractions to the logged operand. For example, if the comparison is input_val == runtime_val - 5, this strategy will find the correct input_val.
Sources: src/afl-fuzz-redqueen.c:103-241
Transformational Solving (-lT, -lX)
The solve_transform function applies a series of data transformations to find a match. This is useful for endianness issues, simple checksums, or character case changes. The transformations include:
- Byte swapping (e.g.,
bswap16,bswap32,bswap64) - Negation (
neg) - Case toggling (
lower,upper)
The -lX option enables "extreme" transformations, which are more computationally intensive variations.
Sources: src/afl-fuzz-redqueen.c:243-829
Configuration
The behavior of CmpLog and Redqueen can be fine-tuned through command-line flags and compile-time configuration.
Runtime Configuration (-c and -l flags)
The Redqueen stage is enabled by providing a target binary to the -c option, which activates CmpLog. The -l option configures the solving strategies.
-l Option | Description |
|---|---|
A | Enables Arithmetic solving. |
T | Enables Transformational solving. |
X | Enables eXtreme transformational solving. |
R | Enables Random colorization of bytes. |
1, 2, 3 | Sets the CmpLog level, controlling which files are selected for analysis (small, larger, or all). |
Sources: src/afl-fuzz.c:687-731
Compile-Time Configuration
Several macros in config.h control the tuning and behavior of the CmpLog/Redqueen system.
| Macro | Default | Description |
|---|---|---|
CMPLOG_COMBINE | Defined | If a Redqueen pass finds more than one solution, it attempts to combine them. |
CMPLOG_CORPUS_PERCENT | 5U | Minimum percentage of the corpus to perform CmpLog on. |
CMPLOG_POSITIONS_MAX | 12288 | Number of potential positions to track before CmpLog is considered less useful. |
CMPLOG_FAIL_MAX | 96 | Maximum allowed failures per CMP value before giving up on it. |
Sources: include/config.h:70-85
Conclusion
The Redqueen Input-to-State Correspondence feature is a sophisticated, automated strategy within AFL++ for overcoming complex path predicates. By instrumenting comparisons with CmpLog and applying intelligent solving techniques, it can bypass checks for magic values, checksums, and other guards that would otherwise halt a traditional fuzzer. This significantly improves the fuzzer's ability to explore deep and complex program states, leading to better code coverage and a higher probability of discovering vulnerabilities.