Fuzzing as Editor Feedback

Property-based testing frameworks generate random inputs. Your tests receive those inputs as arguments and can then test properties of your code that should be true for any input [16]. For example, to test a function that calculates the maximum of a list of numbers, you could write a test that receives a list of numbers as input, calls the maximum function, and verifies properties of the result. Properties of the maximum function could be that the original list has to contain the result, or that the result is larger than or equal to every list item.

Property-based testing frameworks exist for many languages, such as QuickCheck¹¹1https://hackage.haskell.org/package/QuickCheck for Haskell. They usually work in two phases:

1. 1.

   In the exploration phase, the framework runs the test with increasingly more complex inputs. If one of those inputs causes the test to fail, it enters the shrinking phase.

2. 2.

   In the shrinking phase, the framework tries smaller versions of the failing input. It repeatedly shrinks the input until any further reduction causes the test to succeed. Finally, it reports the smallest input that still fails the test.

To generate correctly-typed inputs, property-based testing frameworks usually require developers to implement code for generating inputs, although this can sometimes be automated.

Compared to unit tests (which only test a single input-output pair), property-based tests are more abstract and can test code more thoroughly without much more effort.

Fuzzing is the testing of programs with random inputs to find crashes. Historically, fuzzing evolved from an outside-in view, analyzing the robustness of other people’s programs [14]. Today, fuzzing makes security-critical software, such as firmware, operating systems, browsers, and applications, more robust²²2Some high-profile projects where fuzzing found bugs: Mozilla Firefox, Apple Safari, iOS kernel, sqlite, Linux ext4, Tor, PHP, OpenSSL, OpenSSH, LibreOffice, libpng, curl, GPG, OpenCV, zstd, MySQL, …
See also: https://github.com/google/oss-fuzz [26, 24, 27].

In this technique, a component called fuzzer generates bytes, runs the program with those inputs, and receives feedback about the program’s behavior. Because fuzzing works with unstructured bytes, it is usually more feedback-driven than property-based testing out of necessity. State-of-the-art fuzzers can be differentiated in the amount of feedback they receive from the running program [3, 22, 19]:

Blackbox fuzzing

The fuzzer only receives feedback about the program’s externally visible behavior, such as whether it crashed and how long it was executed. The limited amount of feedback makes it difficult to reach interesting code, especially if the program validates its input.

Whitebox fuzzing

The fuzzer accesses the program code (at the source or machine code level) and analyzes its structure. For example, it can use symbolic execution and a constraint solver to generate inputs that reach target locations. This produces high-quality inputs but introduces a considerable overhead for generating inputs, especially for code with complicated control flow.

Greybox fuzzing

The fuzzer uses simple coverage feedback to judge the quality of inputs. For example, inputs leading deep into the program’s logic are perhaps more interesting than ones only executing a few instructions. Greybox fuzzers mutate promising inputs – for example, by inserting or removing a few bytes from the input byte sequence – gradually exploring all code. Greybox fuzzing balances the quantity and quality of the input generation and is, therefore, more effective at finding bugs than the other two variants.

The most widely used open-source fuzzers are based on American Fuzzy Lop (AFL) [26], a Greybox fuzzer. Since its inception, several papers [2, 1, 3, 10, 25, 6, 4] have proposed additions to make fuzzing more effective, but most Greybox fuzzers follow AFL’s general architecture:

1. 1.

   The fuzzer maintains a pool of inputs. Initially, this pool is empty or filled with examples explicitly given by the developer.

2. 2.

   The fuzzer either generates a random byte sequence or picks and slightly mutates one from the pool.

3. 3.

   The fuzzer runs the program, sending the input bytes into its standard input (stdin). The fuzzer observes the coverage and whether the program crashed.

4. 4.

   If the input executes code that was not reached before, the input is added to the input pool. If the input crashes the program, it is reported.

5. 5.

   Go to step 2.

While fuzzing and property-based testing evolved from different origins, their use cases overlap: Fuzzing tests the property that the program doesn’t crash (although assertions in the code can reduce any property to a crash). A unique appeal of fuzzing among dynamic tools is that it requires no setup.

Fuzzing and property-based testing are usually used as after-the-fact analyses to find bugs. This distances them from the development workflow, both temporally and spatially.

Using property-based testing requires conscious effort from the developer. They have to implement/derive code for generating typed values, and they have to manually write tests for properties.

Using fuzzing requires less setup. However, it is usually not integrated into the editor, but invoked from the command line. Fuzzing works on entire programs, generates inputs at the byte level, and can take a long time to find bugs deep within your code (far from the main function).

Both tools yield insights apart from a potential crash report: They create examples covering all the different parts of the program and showing edge cases. Making these examples readily available during programming sessions rather than as an after-the-fact analysis has not yet been explored. Perhaps the developer can see these examples directly while writing code?

Other works explore showing live examples next to the source code, a practice sometimes called Babylonian Programming [18, 17]. For example, in Inventing on Principle [21], Bret Victor presents an editor that lets you specify example values for function inputs in a pane next to the source code. The editor will then show the concrete values of all variables and how they evolve as the function executes. Other works of live examples in your code include Live Literals [20], the Babylonian Programming Editor [18], or projection boxes [8].

A major difference among these tools is how developers specify examples. Rauch et al. [18] distinguish between two methods:

Implicit examples

are provided in the source code, thus requiring code modification.

Explicit examples

are provided using a special syntax or separate UI.

Making the computer come up with examples adds a third method. Mattis et al. [12] explore using large language models (LLMs) to generate examples and tests automatically. However, the model sometimes hallucinates function arguments, especially if code is not sufficiently tested or used by other code – the exact cases where examples would be helpful. A fundamental limitation of LLMs is that they approximate the runtime behavior of code internally [15, 9]. On the other hand, examples found through fuzzing are grounded in the actual semantics of the code.

Fuzzing is a largely untapped source of examples. In this paper, we bring those examples to the editor. Our prototype shows annotations based on these examples.

We designed Martinaise³³3https://marcelgarus.dev/martinaise , a custom programming language that has some specific limitations that make it easy to fuzz:

• $\mathrm{■}$

  It has a simple, static type system and favors concrete types over abstract interfaces.

• $\mathrm{■}$

  It has no first-class functions capturing their lexical context, only top-level functions.

• $\mathrm{■}$

  It has a small compiler and virtual machine, which enable complete code instrumentation.

• $\mathrm{■}$

  It has basic tooling support for Visual Studio Code (VS Code), a popular code editor.

In section 6, we discuss how our approach can be adapted to real-world languages.

The fuzzer needs to be able to generate, mutate, and analyze the function arguments. Our prototype creates code that allows the fuzzer to work with the argument types, but the behavior can be overridden if necessary.

The fuzzer can generate random values of a desired type:

• $\mathrm{■}$

  For structs, it generates a random value for each field.

• $\mathrm{■}$

  For enums, it chooses a random variant and generates a random payload.

Like many property-based testing frameworks, the code for generating values accepts a desired complexity. This allows the fuzzer to test a function with increasingly larger inputs and prevents infinite recursion for recursive types.

Only being able to generate values is not enough. Greybox fuzzers use evolution to be effective at exploring code. They randomly mutate the input and keep those inputs that cover new ground as the new baseline.

• $\mathrm{■}$

  For structs, the fuzzer changes a random field.

• $\mathrm{■}$

  For enums, the fuzzer either chooses a new variant or changes the payload.

This mutation works with a temperature: The higher the temperature, the more the mutated value differs from the original one. This allows the fuzzer to widen or narrow the search space of new inputs.

Fuzzing requires feedback about the code coverage. Similar to existing fuzzers like AFL, our fuzzer instruments the generated byte code to track the coverage: It rewrites conditional jumps, the only form of data-dependent control flow, so that they update a global coverage bitset. After running some code, this bitset automatically indicates which branches were chosen.

Instructions with external side effects also get replaced during instrumentation. Instructions that output data (such as printing or writing a file) get omitted. If a function reads external data (from the standard input or a file), the function is not fuzzed.

Given the functionality for generating inputs, judging their complexity, tracking coverage, and mutating them, we can now implement Greybox fuzzing. We have demands that are somewhat different from those of existing Greybox fuzzers: We want to find crashes but also interesting inputs. The editor should show representative examples as soon as possible.

Our process is very similar to how AFL works [26]: The fuzzer maintains a pool of examples. Initially, these are randomly generated. The fuzzer picks an example, mutates it, runs it, and compares the coverage to the original one:

• $\mathrm{■}$

  If it covers less code, it is discarded.

• $\mathrm{■}$

  If it covers the same code but is smaller, the example replaces the current example.

• $\mathrm{■}$

  If it covers new code, it is added to the pool for further exploration.

This process results in a set of small examples that execute different parts of a function’s code.

We want to show examples in the editor based on fuzzing. As a proof of concept, we implemented that functionality for the Visual Studio Code IDE⁴⁴4https://code.visualstudio.com/ (VS Code). We created a VS Code extension that tracks the opened files and the scroll position, checks which functions are visible, and spawns fuzzers for these functions. As these fuzzers report their progress, the extension continuously updates the examples shown in the editor.

Currently, editing the code invalidates the fuzzed examples in that file. When writing code, the visible functions are continuously fuzzed.

Coverage feedback is enough to explore functions with a straightforward control flow. Here is a function where the fuzzer successfully gives one example for each way the function can return:

These are all examples:

However, achieving full coverage on any function is impossible. For example, this function only returns an integer if the SHA-256 hash of the input matches an expected value:

While, in theory, the fuzzer could generate and show an example input that reaches the conditional branch, doing so in a reasonable time frame requires breaking SHA-256.

In practice, our fuzzer already struggles with simpler code. For example, it does not reach the inner code in the following if clause:

State-of-the-art fuzzers can fuzz this code because they also track the number of loop iterations, so inputs with a different prefix of "https" (such as "hello" and "htttt") will have different coverage in the string comparison code.

Apart from finding inputs that crash functions, the examples discovered by our tool can also be used to understand how a function behaves without looking at its implementation. However, while code coverage and input complexity generally correlate with how helpful examples are, we recognize that it is not a perfect proxy. In everyday use, we identify two major limitations when using our tool to understand existing code.

First, minimizing examples can be counterproductive. Previously, we showed that our tool gives [0] as an example for the average function. While a list containing a single number achieves full code coverage, it does not give the developer confidence that the implementation is correct. [1, 2, 3] would be a better example.

Second, the examples our tool shows are often unnatural. Here, our tool greets someone with an empty name:

While this is the expected behavior of fuzzing, in our experience, such unnatural examples introduce some mental overhead. This problem is difficult to address in a general way because the perceived complexity of values depends on the context: Even if 0 is perceived as less complex than 3 in isolation, most humans perceive [1, 2, 3, 4] as less complex than [1, 2, 0, 4].

Fuzzing takes time. Compared to traditional fuzzing, an advantage of fuzzing on the granularity of functions as opposed to entire programs is that the fuzzer does not have to reach potentially crashing code indirectly through the main function. For example, if the entry part of the code is guarded with code that is difficult to pass such as the SHA-256 code from section 5.1, our tool can still fuzz internally used functions in isolation.

Unlike type-checking or linting, the output of fuzzing changes over time. Table 1 shows how examples for the email address check from section 5.1 change on a desktop computer⁵⁵5The computer has an AMD Ryzen™ 7 5800X × 16 and 32 GiB of RAM. It runs Ubuntu 24.04.1 LTS. . Every line shows a timestamp, the number of function executions that were performed, and a screenshot of the examples. In the beginning, there are no examples. After the function is compiled, our tool quickly discovers four random-looking examples that cover all the code. Then, it shrinks them. The table only shows a subset of all updates – in total, the fuzzer produces many more intermediate versions, most of which differ only by a single character from the previous version. In the end, you are left with four small, representative examples of the function behavior.

Because of this continuous refinement, the feedback feels reasonably fast in practice. Even for large functions, the initial examples appear quickly – it just takes longer for the examples to stabilize.

Apart from the quality of examples, we also want to look at how and where examples are displayed. Currently, our tool formats examples as text and shows them next to the function signature. For many values, there are more appropriate representations than formatted text, such as visualizations. It may make sense to expand our tool to other editors that do not have VS Code’s constraints like the ones discussed by Rauch et al. [18].

There are some practical limitations of our implementation: We currently don’t order examples. Also, for functions that mutate the input or produce a side effect, input-output pairs do not help understand their behavior.

We chose Martinaise because it allowed us to investigate using fuzzing in the editor without focusing on more advanced challenges posed by real-world languages. These are ways in which our prototype could be adapted to different languages: