A simple black-box fuzzer.

fuss.ts

import { assert } from "./utils.js";

type Awaitable = unknown;

export class Fusser {
  buffer: Uint32Array;
  init: () => Awaitable;
  action: (v: number) => Awaitable;

  private canceled: boolean;

  constructor(init: () => Awaitable, action: (v: number) => Awaitable) {
    this.buffer = new Uint32Array(128);
    this.init = init;
    this.action = action;

    this.canceled = false;
  }

  async fuss(): Promise<number[] | null> {
    this.canceled = false;

    let base: number[] = [];
    let err: Error;
    let stackTrimmed: string;
    finding:
    while (true) {
      if (await this.interrupted()) {
        return null;
      }

      crypto.getRandomValues(this.buffer);
      const [e, failedAt] = await this.runCase(this.buffer);
      if (e) {
        base = [...this.buffer.slice(0, failedAt)];
        err = e;
        stackTrimmed = trimStack(err.stack ?? "");
        break finding;
      }
    }

    let reduced = base;
    console.log(`Reducing while looking for the following error:\n${err.name}: ${err.message}\n${stackTrimmed}`);
    console.log(`Initial length ${reduced.length}`);

    while (true) {
      const lengthBefore = reduced.length;

      // Reduce by masking off parts of the array
      const BITS = 8;
      newmask:
      while (true) {
        if (reduced.length < BITS) {
          break;
        }

        const chunkSize = Math.floor(reduced.length / BITS);
        console.group(`Mask reduce: chunkSize=${chunkSize}`);
        for (let mask = 1; mask < 2 ** BITS; mask++) {
          if (await this.interrupted()) {
            return null;
          }

          const candidate = new Array(chunkSize * popcnt32(mask));
          let chunksFilled = 0;
          for (let i = 0; i < BITS; i++) {
            if ((mask >> i) & 1) {
              // Copy a chunk's worth of data from reduced to candidate
              for (let j = 0; j < chunkSize; j++) {
                candidate[chunksFilled * chunkSize + j] = reduced[i * chunkSize + j];
              }
              chunksFilled += 1;
            }
          }
          assert(chunksFilled === popcnt32(mask));

          const [e, failedAt] = await this.runCase(candidate);
          if (e && err.name === e.name && err.message === e.message && stackTrimmed === trimStack(e.stack ?? "")) {
            reduced = candidate.slice(0, failedAt);
            console.log(`Reduced to length ${reduced.length} with mask ${mask}`);
            console.groupEnd();
            continue newmask;
          }
        }
        console.groupEnd();

        break;
      }

      // Reduce by iteratively trying to remove smaller and smaller contiguous chunks
      let chunkSize = Math.floor(reduced.length / 2);
      bigchunks:
      while (true) {
        if (chunkSize === 0) {
          break;
        }

        console.group(`Linear reduce: chunkSize=${chunkSize}`);
        for (let i = 0; i < reduced.length - chunkSize; i += Math.ceil(chunkSize / 4)) {
          if (await this.interrupted()) {
            return null;
          }

          const candidate = [...reduced.slice(0, i), ...reduced.slice(i + chunkSize)];
          const [e, failedAt] = await this.runCase(candidate);
          if (e && err.name === e.name && err.message === e.message && stackTrimmed === trimStack(e.stack ?? "")) {
            reduced = candidate.slice(0, failedAt);
            chunkSize = Math.floor(reduced.length / 2);
            console.log(`Reduced to length ${reduced.length} at offset ${i}`);
            console.groupEnd();
            continue bigchunks;
          }
        }
        console.groupEnd();

        chunkSize = Math.floor(chunkSize / 2);
      }

      if (reduced.length === lengthBefore) {
        break;
      }
    }

    return reduced;
  }

  async runCase(buf: Iterable<number>): Promise<[Error | null, number]> {
    await this.init();

    let i = -1;
    for (const v of buf) {
      i += 1;
      try {
        await this.action(v);
      } catch (e) {
        if (!(e instanceof Error)) {
          throw new Error(`Fusser expected an Error, but got ${e}`);
        }
        return [e, i];
      }
    }

    return [null, 0];
  }

  cancel() {
    this.canceled = true;
  }

  private async interrupted(): Promise<boolean> {
    await new Promise(res => setTimeout(res, 0));
    return this.canceled;
  }
}

function popcnt32(n: number): number {
  n = n - ((n >> 1) & 0x55555555)
  n = (n & 0x33333333) + ((n >> 2) & 0x33333333)
  return ((n + (n >> 4) & 0xF0F0F0F) * 0x1010101) >> 24
}

function trimStack(stack: string) {
  return stack.slice(0, stack.indexOf("runCase@"));
}