create a separate executable for each fuzz test; change std.testing fuzzing API to unify corpus with unit tests

[andrewrk]

Currently, all unit tests of a given compilation are compiled into the same binary, and the test runner iterates over all of them and runs them one by one. This saves time and disk space, eliminating the overhead of building an independent executable for each test.

The same is true for fuzz tests. When rebuilding a compilation in fuzz mode, all fuzz tests (and all other non-fuzzing unit tests) are compiled into the same executable. While this saves time and disk space at first, these benefits come at the cost of a larger points-of-interest array. This array is the set of virtual memory addresses for which the fuzzer is trying to reach. By keeping this array smaller, each individual fuzz run can be slightly faster. Multiplied by many fuzz runs, the tradeoff tilts in favor of separate executable for each fuzz test.

To further optimize fuzz run performance, we also want to minimize overhead of calling into the function. For instance ideally the hot fuzz loop will be a direct call into the code being tested, rather than dereferencing a function pointer. This is constrained by the std.testing API for how to declare something as a fuzz test.

This issue changes from the current API:

pub inline fn fuzz(context: anytype, comptime testOne: fn (context: @TypeOf(context), input: []const u8) anyerror!void, options: FuzzInputOptions) anyerror!void

Which is used like this:

test "example fuzz test" {
    try std.testing.fuzz({}, testOne, .{});
}

Into this signature:

pub fn fuzz(comptime testOne: *const fn (input: []const u8) anyerror!void, input: []const u8) anyerror!void

Note that the context is gone. Usage is now like this:

test "example unit test" {
    try std.testing.fuzz(myFuzzTest, "example input");
}

Importantly, "example unit test" is no longer itself a fuzz test. Instead, it has a side-effect of informing the build system about the existence of a fuzz test, as well as one input for the corpus. So, the following unit tests may also exist:

test "another unit test" {
    try std.testing.fuzz(myFuzzTest, "same fuzz test, different input");
    try std.testing.fuzz(myFuzzTest, "yet a third input to the same fuzz test");
}

test "third unit test" {
    try std.testing.fuzz(myFuzzTest, "this fourth input still does not declare a unique fuzz test");
    //try std.testing.fuzz(foobar, "ok now this one creates a new fuzz test"); // not allowed for reasons explained below
}

So this fundamentally changes the algorithm for build system discovering fuzz tests - they no longer correspond one-on-one to a unit test. This handles the common case that unit test coverage acts as a good initial corpus for fuzzing. For instance, consider this one-liner added to parser_test.zig:

--- a/lib/std/zig/parser_test.zig
+++ b/lib/std/zig/parser_test.zig
@@ -6415,6 +6415,7 @@ fn testParse(source: [:0]const u8, allocator: mem.Allocator, anything_changed: *
     return formatted;
 }
 fn testTransformImpl(allocator: mem.Allocator, fba: *std.heap.FixedBufferAllocator, source: [:0]const u8, expected_source: []const u8) !void {
+    std.testing.fuzz(fuzzTestOneParse, source);
     // reset the fixed buffer allocator each run so that it can be re-used for each
     // iteration of the failing index
     fba.reset();

This means that all the unit test cases from the rest of the file will be collected into the initial corpus.

Finally, circling back to optimizing the fuzz function - since this API declares a comptime-known function pointer as a fuzz test, it means that when recompiling a test binary in fuzz mode, specifically that one function that was referenced can be wrapped in the test runner like this:

export fn zig_fuzzer_one(input_ptr: [*]const u8, input_len: usize) void {
    theOneAndOnlyFuzzFunction(input_ptr[0..input_len]) catch |err| { ... };
}

And of course this will be inlined and optimized so that it has no overhead.

In order to accomplish this without complicated and brittle machinery inside the compiler, std.testing.fuzz will note the first unit test corresponding to any particular fuzz function pointer. A second, different fuzz function may not be declared in the same unit test. This means that fuzz functions can be identified by unit test index. When recompiling unit tests for purpose of exposing a single fuzz function, the unit test index can be used for conditional compilation to eliminate most dead code, and then the std.testing.fuzz function will simply @export the wrapper. This only works if unit tests are forbidden from declaring more than one fuzz test (not to be confused with more than one corpus input).

This restriction could be lifted by adding a more advanced fuzz test declaration function which includes a comptime string which makes the exported function unique. This id then becomes part of the tuple that identifies a fuzz test (unit test index, comptime string fuzz test id), and then is used as conditional compilation to avoid compiling multiple fuzz tests declared in the same unit test into one executable.

By doing things this way, unit tests and fuzz tests are unified so that the unit tests can test additional things such as expected result, while also declaring the initial corpus data for property-based testing.

[gooncreeper]

The second suggestion of unifying the corpus with test runs goes against a smith approach (#25281) as it requires tying the use of the fuzzed input to be the same as in the unit tests.

As for removing context, I have found it helpful for passing preallocated memory (example), and there are likely other uses.

And of course this will be inlined and optimized so that it has no overhead.

How? They are in separate compilation units.

[andrewrk]

The second suggestion of unifying the corpus with test runs goes against a smith approach (#25281) as it requires tying the use of the fuzzed input to be the same as in the unit tests.

I see your point, but consider:

• when there is no smith, it is invaluable as an initial corpus (as in the case of a tokenizer)
• those tests can still be used as a secondary campaign alongside the smithing campaign
• the connection can be used to determine the quality of the smith (i.e. if the smith cannot produce a unit test input, then either the smith or the unit test is flawed)
• the unit test cases can be used to lead a smith toward better starting corpus (comparing smith output with the pre-packaged unit tests has a better fitness signal than PC addresses reached)

How? They are in separate compilation units.

Before: cycle() has an indirect call machine code instruction to fuzz once
After: cycle() has a direct call machine code instruction to fuzz once

In any case, solving separate executable for each fuzz test will require a compiler enhancement to allow overriding the entry points. I'll file a proposal for that.

[andrewrk]

The more I looked into this today, the more I think this should be split into two proposals:

• create a separate executable for each fuzz test
• change std.testing fuzzing API to unify corpus with unit tests

I'm starting to question the value of separate executable for each fuzz test. Particularly when using limited mode, I think the limit would have to be extremely high for it to beat the amount of time saved by not compiling a lot of test executables. For instance, have a look at these numbers:

const std = @import("std");
const expect = std.testing.expect;

pub fn main() !void {
    var array: [16000]u8 = undefined;
    @memset(&array, 0);
    // escape the pointer to prevent the memsets below from being optimized away
    std.debug.print("pointer: {*}\n", .{&array});

    var timer = try std.time.Timer.start();
    @memset(array[0..8000], 1);
    const duration = timer.read();
    std.debug.print("memset 8000 took {D}\n", .{duration});
    timer.reset();
    @memset(&array, 2);
    const duration2 = timer.read();
    std.debug.print("memset 16000 took {D}\n", .{duration2});
}

Some data points on my computer:

memset 8000 bytes: 141ns, 160ns, 190ns, 201ns, 210ns
memset 16000 bytes: 171ns, 241ns, 250ns, 250ns, 260ns, 301ns

This overhead is really low. By comparison building hello world with -OReleaseSafe takes about 4s. So doing some back of the napkin math, for the median value above (difference of 60ns), in order for points-of-interest array reduction due to independent fuzz test from the executable to be a winning strategy, you'd need to pass at least --limit=66M. I suppose that could be within realistic range - although if the user fuzz test is even a little bit slow, for example taking 1ms, then it would take 19 hours to reach 66M iterations. If another commit lands before then, causing the fuzz executables to need to be regenerated, then it will not have been worth it under those conditions.

However, I don't think that's what's holding back zig's integrated fuzzer at this time. I think UX enhancements are still the more important aspect (getting it working on all platforms without things going wrong for various reasons), followed by the freshness detection should be based on the same strategy as outlined in detecting new behaviors in the AFL technical details document.

In any case, I've re-opened #13524 as a prerequisite of this one. A nice middle ground would be to at least rebuild fuzz executables without non-fuzz unit tests inside them.

[kristoff-it]

I'm starting to question the value of separate executable for each fuzz test. Particularly when using limited mode, I think the limit would have to be extremely high for it to beat the amount of time saved by not compiling a lot of test executables.

I think the main motivation for splitting fuzz tests is to have meaningful coverage numbers (both for users and for evaluating performance of the fuzzer itself).

My understanding is that without splitting tests it's not possible to (reasonably) differentiate between what's reachable from one test vs another. This means that the coverage information becomes hard to interpret because it's a function of how many tests you have in the executable. As an example it might be that maxing out coverage for a given test will amount to max 2% of the overall coverage (and we won't even be able to tell you that this is the case).

That alone IMO is motivation enough for separate executables but, on top of that, wouldn't the lost time building separate executables be regained by not having to rebuild most of them most of the time (assuming correct caching)?

For example if you have a fuzz test for the tokenizer, unless you touch it, the relative fuzz test will not have to be rebuilt.

It is correct to say that for more "integration testing"-style fuzz tests you will end up rebuilding them a lot more though, but you would still have the issue of bad coverage numbers in this case. My understanding is that this latter style of testing is in any case best suited for endless runs rather than limit fuzzing.

[andrewrk]

I think the main motivation for splitting fuzz tests is to have meaningful coverage numbers (both for users and for evaluating performance of the fuzzer itself).

Well, keep in mind that zig build would report aggregated coverage numbers, and by having all the fuzz tests in the same executable, you get that aggregation for free.

You're thinking in terms of % to evaluate how well-covered source code is, but I think you should be favoring the more information-rich data that we have which is source code decorated by points-of-interest along with reachability. That is not really compromised by having more data aggregated inside it, because the user knows which parts of code they care about being tested or not - and if anything the aggregation is handy for this purpose.

And keep in mind that when someone is working on a fuzz test directly, or the fuzzer directly, they will likely use --test-filter manually to isolate a single test. In this case, the feature is redundant.

That alone IMO is motivation enough for separate executables but, on top of that, wouldn't the lost time building separate executables be regained by not having to rebuild most of them most of the time (assuming correct caching)?

That's a good point to keep in mind for this issue - it's something I forgot about when typing this up. However... in the CI use case, this would not apply since it would be a fresh commit every time. In the use case where a developer is making multiple edits to a particular fuzz test, they will likely be using --test-filter manually to isolate the test, so the feature would be redundant.

It sounds like the core perspective difference here is about the cost of fully-covered source code reporting some number less than 100%. Personally, I don't really understand the weight you're putting on this cost. There's always going to be uncovered code, for example in dependencies. For example, a tokenizer fuzz test might indirectly depend on an array hash map but it is not designed to completely explore array hash map implementation details. Same deal with allocators.

In the end I'm not arguing against doing this issue, and I think I've carved out an implementation plan - but I do think it's a fairly low priority issue.

[gooncreeper]

when there is no smith, it is invaluable as an initial corpus (as in the case of a tokenizer)

Even in the case of the tokenizer, a smith would have some advantages. For example, it can weigh ascii values higher, output utf-8 code points, and optionally add a BOM.

those tests can still be used as a secondary campaign alongside the smithing campaign

In the future when we have multi-threaded fuzzing they will only serve to slow down more efficient campaigns (the effect would be reduced by #22901, but there will still be some overhead regardless). It additionally adds some friction to writing a smith-based fuzz test.

the connection can be used to determine the quality of the smith (i.e. if the smith cannot produce a unit test input, then either the smith or the unit test is flawed)

I am not quite seeing this (unless you are suggesting the fuzzer somehow does this, which has the same problems as below). The user is able to evaluate the pc coverage via the build system while using the smith (having the corpus inputs would actually impair that).

the unit test cases can be used to lead a smith toward better starting corpus (comparing smith output with the pre-packaged unit tests has a better fitness signal than PC addresses reached)

With the proposed API, this would not be possible since the format of the unit test cases and smith are completely different and require separate functions to test.

[kristoff-it]

Well, keep in mind that zig build would report aggregated coverage numbers, and by having all the fuzz tests in the same executable, you get that aggregation for free.

I always assumed we would show one entry in the report for each fuzz test that run, I guess we never hashed that out!

From my perspective per-fuzz-test % and detailed coverage are complementary and, while in theory you could derive the former from the latter, the experience that I've imagined is that I would use the source view mainly to spot check "did we cover this tricky condition at all", while the % would be what I look at to quickly gauge the level of "fuzzing completion" of a unit (unit as in unit test). Looking at the source code you can't trivially get that same number back in normal cases.

That alone IMO is motivation enough for separate executables but, on top of that, wouldn't the lost time building separate executables be regained by not having to rebuild most of them most of the time (assuming correct caching)?

That's a good point to keep in mind for this issue - it's something I forgot about when typing this up. However... in the CI use case, this would not apply since it would be a fresh commit every time. In the use case where a developer is making multiple edits to a particular fuzz test, they will likely be using --test-filter manually to isolate the test, so the feature would be redundant.

If I understand correctly your reply, you've assumed that I meant avoiding rebuilding fuzz tests in the case where you change (repeatedly) only one of them, thus saving the time it takes to rebuild other tests. What I was thinking is instead the case where you have a fuzz test for, say, the tokenizer that only tests it as a unit. With separate executables for each fuzz test you won't have to rebuild that test no matter what change you make in the rest of the codebase (not just other tests), which helps running the same test, untouched, for months or maybe years. Or am I missing something wrt caching?