FrameShift : Learning to Resize Fuzzer Inputs Without Breaking Them
Harrison Green, Claire Le Goues, Fraser Brown · 2025
Read FrameShift : Learning to Resize Fuzzer Inputs Without Breaking Them by Harrison Green, Claire Le Goues, Fraser Brown (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-05421.txt.
Introduction
Harrison Green, Claire Le Goues, and Fraser Brown teach fuzzers to resize test files without wrecking them, in a 2025 paper. Fuzzers find bugs by mutating inputs and watching which paths a program takes. Many file formats carry length fields, and a naive mutation that changes data but not its declared length creates garbage the program rejects at the door. Their technique, FrameShift, detects those relation fields and keeps lengths consistent during mutation.
The method is light, needs no extra instrumentation, and was built into two leading fuzzers. Over twelve CPU-years of testing, it improved bug-finding performance. Fuzzing is a workhorse of software security, so removing a whole class of wasted mutations raises the yield of every campaign.
Catalog record
| CREATOR | Harrison Green, Claire Le Goues, Fraser Brown |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 63 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-05421
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
FrameShift : Learning to Resize Fuzzer Inputs Without Breaking Them Harrison Green, Claire Le Goues, Fraser Brown Abstract Coverage-guided fuzzers are powerful automated bug-finding tools. They mutate program inputs, observe coverage, and save any input that hits an unexplored path for future mutation. Unfortunately, without knowledge of input formats—for example, the relationship between formats’ data fields and sizes—fuzzers are prone to generate destructive frameshift mutations. These time-wasting mutations yield malformed inputs that are rejected by the target program. To avoid such breaking mutations, this paper proposes a novel, lightweight technique that preserves the structure of inputs during mutation by detecting and using relation fields . Our technique, FrameShift , is simple, fast, and does not require additional instrumentation beyond standard coverage feedback. We implement our technique in two state-of-the-art fuzzers, AFL++ and LibAFL , and perform a 12+ CPU-year fuzzer evaluation, finding that FrameShift improves the performance of the fuzzer in each configuration, sometimes increasing coverage by more than 50%. Furthermore, through a series of case studies, we show that our technique is versatile enough to find important structural relationships in a variety of formats, even generalizing beyond C/C++ targets to both Rust and Python. 1 Introduction Fuzzing is an effective tool for exploring the state space of programs and finding bugs. While the earliest fuzzer simply fed random data into UNIX programs [ 26 ] (and, again, found bugs!), coverage-guided fuzzers like AFL++ [ 11 ] , and LibAFL [ 12 ] use mutations and feedback to explore targets more efficiently. These coverage-guided fuzzers maintain a growing corpus of inputs. They pick inputs from this corpus, apply random mutations (bitflips, arithmetic operations, insertions from a dictionary, etc.), and then measure feedback like edge or block coverage. The fuzzers retain mutated inputs that reach new coverage, and discard mutated inputs that don’t. These fuzzers are versatile enough to find bugs in a wide variety of targets, and, as a result, they’ve been widely adopted in industry. For example, coverage-guided fuzzers have found more than 13,000 vulnerabilities across 1,000+ open-source projects as part of Google’s OSS-Fuzz . 1 1 1 https://github.com/google/oss-fuzz Unfortunately, even the best modern fuzzers struggle to successfully mutate certain types of input structures. Many common fuzz targets operate over serialized binary formats whose metadata —e.g., size and offset fields—describes the layout of associated data buffers. Security-critical applications process such structured inputs: Hardware security chips, for example, operate on TPM packets, and openssl (and others) use DER -encoded ASN.1 messages; both formats contain multiple nested size fields, which make them notoriously hard to mutate [ 3 ] . In general, these sorts of fields occur in almost every serialized binary format—in codecs ( PNG , JPEG , MP3 , OGG , etc.), document formats ( PDF , XLSX , DOCX , etc.), cryptographic protocols ( TLS , SSH ), object formats ( ELF , PE , Mach-O ), and many more. Fundamentally, any multi-part, variable-length binary data format requires metadata to describe its structure and delineate field boundaries. These metadata-rich formats pose a challenge to modern fuzzers. When a fuzzer mutates specific parts of an input—like a variable sized data buffer—without correspondingly updating related parts of the input—like the size or offset fields describing that buffer—it renders the input structurally invalid. We call such destructive mutations frameshifts . As a result of the frameshift, the target program will mishandle the input data or abort early with a validation error. Frameshifts cause fuzzers to get stuck exploring the space of invalid inputs and the space of inputs with the same sized structures as appear in the seed corpus; they are unable to discover new, interesting inputs that contain resized or shifted data. Existing approaches to this problem either (1) augment the fuzzer with an input specification, allowing it to understand and generate the expected structure [ 27 , 9 ] , or (2) learn important structures automatically during fuzzing using e.g., static analysis [ 19 , 8 ] , coverage-guided feedback [ 10 , 38 ] , or (recently) a combination of static analysis and machine learning [ 31 ] . Unfortunately, existing techniques in the first category require manual effort and, simultaneously, risk over-constraining the fuzzer. Techniques in the second category don’t solve the general frameshift problem either. Both AIFORE [ 31 ] and ProFuzzer [ 38 ] are closed source, which makes widespread adoption impossible. Further, all of TIFF [ 19 ] , WEIZZ [ 10 ] , ProFuzzer [ 38 ] , and AIFORE [ 31 ] try to discern whether bytes are e.g. an integer, or an enum, or a string, etc. They may identify relation fields, but do not attempt to identify the relationship between these fields and their target buffers—and thus cannot perform validity-preserving resizing mutations. Further, modern fuzzers include a (rough) generalization of the techniques prior work uses to e.g., discern valid enum options, byte ranges, etc. AFL++ and LibAFL , for example, use sophisticated strategies like compare-logging (an adaptation of RedQueen [ 2 ] ), which attempts to find special values and inject them into the input. This type of technique can, for example, identify alternative enum options (by instrumenting switch cases), or required magic bytes (by instrumenting e.g. memcmp ), thus subsuming less general analyses that do (some of) the same thing. Unfortunately, these features are not always enabled by default, rendering them absent from some academic evaluations [ 8 , 31 ] —and potentially underselling the actual performance of modern general-purpose fuzzers. In our work, we use industry-standard configurations (following FuzzBench [ 25 ] ) and focus on designing a system that confers an actual, significant benefit over state-of-the-art baseline fuzzers, even in their optimal configurations. This paper presents a new approach to fuzzing structured input formats by discovering relation fields and using them for structure-aware resizing mutations that preserve input validity. Our approach, FrameShift , is built on two key insights. First, coverage loss between a seed and a mutated input indicates that the fuzzer may have mutated an important relation field (e.g., size field) without mutating the corresponding data. This indicates a potential destructive frameshift that can be identified dynamically, over the course of a coverage campaign. There are, however, other reasons—reasons beyond frameshifts—that a mutation can lead to coverage loss. For example, mutations to enums may redirect execution to a different code path, or mutations to checksums may cause the target to abort early. Thus, our second insight is that, to identify true frameshifts, FrameShift can conduct experiments to find points where resizing a buffer restores coverage with respect to the original destructive mutation. We prune the search space of potential corrective mutations using domain-specific heuristics that let the analysis run in mere seconds per new input. Finally, FrameShift uses its newly-discovered relations to inform fuzzing with existing mutators—thus doing structure-aware fuzzing that avoids destructive frameshifts. We designed FrameShift to be fast, easy to integrate, and compatible with modern fuzzers. It can be applied to a wide range of existing fuzzers because, inspired by prior work [ 10 , 38 ] , it doesn’t require instrumentation beyond coverage feedback. It also does not require manual format specifications. Finally, FrameShift is performant: on unfriendly targets, the analysis almost