Fuzz-driven slow path detection

Fuzz testing consists into executing a given piece of code against randomized inputs. It is a known tool when you want to detect bugs in your algorithms, but we rarely talk of it for performance related topics. Let's see how we can turn fuzzers into tools able to help us into detecting slow code paths.

Performance is not an option

At Pigment, performance is not an option: we build pivoted grids able to render millions of cells on the screen with real-time updates. It consists into ingesting an array of all the rows to spread them into the relevant buckets.

You may imagine something starting from:

And resulting into something like:

The algorithm responsible to pivot the data is a synchronous piece of code executed in the main thread on user side. Having it too slow would ruin the overall user experience by freezing or even crashing the browser. So we first of all defined strict limits to avoid running the algorithm against unsupported sets of data: too many rows, too many cells and others.

But there was always a lucky configuration that passed and made the algorithm crazy, leading to rare complaints related to browser freezing when a grid is rendered. Each time, a new reason and a new slow code path detected and fixed. So we wanted to be proactive and anticipate these issues.

Towards fuzzing

Fuzzing consists into executing a given piece of code against randomly generated inputs. The approach is often used to detect bugs leading to crashes or to subtile unexpected values.

In our case, we wanted to push it further by leveraging it to help us into detecting slow code paths. Instead of asserting for crashes, we decided to ask a fuzzer to run our algorithm and to mark the test as failed anytime whenever it reaches an abnormal timing.

Our algorithm being executed in the main thread, we consider that it should never take more than 50ms to run. As written in the previous section, we do have some kill switches in the algorithm to quit whenever we encounter inputs being unsupported because of their size, so any valid inputs even too large should fulfill that requirement. As we only want to leverage our fuzzer to detect highly critical issues, our time limit is much higher than 50ms. It's rather 500ms and 10s.

The theoretical fuzzing approach is the following:

1. Generate a valid input for the algorithm
2. Start a timer
3. Run the algorithm against the generated input
4. Check if the timer breached the time limit
5. If not, go back to 1.

Fuzzing in TypeScript

Now that we have the concepts, let's see how we achieved that in TypeScript.

We decided to rely on fast-check for the fuzzer. But fast-check alone was not enough. Indeed, as we planned to detect huge performance issues implying main thread to be blocked for several seconds or even worse infinitely, we needed a way to stop a synchronous task. So we coupled it with @fast-check/worker. @fast-check/worker is able to spawn the code under test within workers so that it can be interrupted by the runner.

Our fuzzing snippet is:

import fc from "fast-check";
import { assert, propertyFor } from "@fast-check/worker";
import { isMainThread } from "worker_threads";
import { pathToFileURL } from "url";

const property = propertyFor(pathToFileURL(__filename));

const maxAllowedTimeMs = 10_000;
const maxAllowedTimeMsSpawningWorkerIncluded = 60_000;
const inputArb = todo; // an arbitrary responsible to generate our inputs

const fuzzTarget = property(inputArb(), (input) => {
  // Arrange
  const startTime = performance.now();

  // Act
  functionUnderTest();

  // Assert
  const endTime = performance.now();
  const waitingTimeMs = endTime - startTime;
  if (waitingTimeMs > maxAllowedTimeMs) {
    throw new Error(`Took ${waitingTimeMs}ms to run`);
  }
});

if (isMainThread) {
  fc.configureGlobal({
    timeout: maxAllowedTimeMsSpawningWorkerIncluded,
    endOnFailure: true, // we don't want to shrink: we will do that on case by case basis
    numRuns: 1_000_000, // we want more runs than the default 100
    interruptAfterTimeLimit: 30 * 3_600 * 1_000, // but don't want to run the fuzzer more than 30 min
    baseSize: "xlarge", // we want to run against possibly extra large entries
  });
  await assert(fuzzTarget);
}

Our snippet is leveraging two time limits:

• maxAllowedTimeMs: Capture executions leading to unacceptable timings but not able to catch infinite loops.
• maxAllowedTimeMsSpawningWorkerIncluded: Explicitely higher, it mostly addresses the infinite loop case or any execution running out-of-control for too long. The timing is way higher than the previous one as it also takes into account the time it takes to spawn a worker.

Our code being in TypeScript, it has to be transpiled. So we defined the following scripts:

"build": "esbuild ./fuzz.ts --bundle --platform=node --outfile=fuzz.cjs",
"fuzz": "node --max_old_space_size=16384 fuzz.cjs",

The build script will transform the code starting at ./fuzz.ts into a fuzz.cjs able to run by itself in node. The run script will run the test itself.

Takeaways

At first glance, the approach looked too naive to work. But we quickly detected issues as we incrementally plugged new parts of the input in our generator.

A common concern we often heard when we introduced the approach was: inputs might not be realistic and having them realistic enough might be too costly to make the tests useful. Actually, the point is highly challengeable. The aim of this technique is to find bugs that we never thought about so they might seem crazy at first glance. But as the events proved us, there are some unforecasted configurations that would lead us into the red. Instead of waiting for them to come, anticipating them will help us into detecting and patching slow code paths before anything gets reported.

Finally, the fuzzer is the last layer we added in our performance toolbox. We already had many layers to help us in that direction. Contrary to some others it has the benefit to make us able to anticipate issues we never thought about as it will always suggest us with new entries and one day it might detect a performance issue.

For the moment, the execution of the fuzzer has to be manually triggered in the CI. But we plan to run a limited version of it with all our tests: lower number of executions and smaller inputs.