Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-gif

Source of release 0.3.0

0.3.0 / tools / fuzz.py

#!/usr/bin/env python3
"""Mutate GIFs and decode them: the decoder must never trap, hang or grow without bound,
whatever the bytes.

Each case is one of the corpus files (see conformance.py) changed by a few random
mutations: bytes flipped, inserted, deleted or repeated, chunks spliced in from another
file, and GIF's own structures (block introducers, extension labels, sub-block sizes,
code sizes, 16-bit fields set to 0 or 65535) dropped in at random places. Cases run in
batches through build/gifcheck (tools/gifcheck.lucb, with `qs`: every frame rendered,
nothing written, a 4-megapixel canvas limit), each batch under a time limit; a batch that
dies or times out is narrowed to the case responsible, which is saved under
build/fuzz-failures. The peak memory of the decoding processes is reported.

First, a stress phase decodes generated files that are large or adversarial: a frame of
65535 x 65535 pixels with little data, 20,000 frames, a 4096 x 1024 picture of long LZW
strings, a stream of clear codes, and frames disposed "previous" over a large canvas. Each
must finish in under two seconds.

  python3 tools/fuzz.py [--cases 20000] [--seed 1] [--guard-malloc]
"""
import argparse, os, random, resource, shutil, struct, subprocess, sys, tempfile, time
from pathlib import Path

ROOT = Path(__file__).resolve().parents[1]
sys.path.insert(0, str(ROOT / "tools"))
from conformance import CORPORA  # noqa: E402

TOOL = ROOT / "build/gifcheck"
FAILURES = ROOT / "build/fuzz-failures"
# With --guard-malloc, the tool runs under macOS's Guard Malloc (every allocation on its
# own page, freed pages unmapped), which turns an overrun or a use after free into a crash.
ENVIRONMENT = dict(os.environ)
TOKENS = [b"\x2c", b"\x21\xf9\x04", b"\x21\xff\x0bNETSCAPE2.0\x03\x01", b"\x21\xfe", b"\x21\x01\x0c", b"\x3b",
          b"\x00", b"\xff", b"\x02", b"\x08", b"\x0b", b"\x0c", b"\xff\xff", b"\x00\x00", b"\x80", b"\x87", b"\x40",
          b"\xff" * 64, b"\x00" * 64, b"GIF89a", b"\x21\xf9\x04\x0d\x00\x00\x00\x00"]


def lzw(indices, minimum):
    """`indices` LZW-encoded as GIF's sub-blocks, a clear code whenever the table fills."""
    clear = 1 << minimum
    out, bits, held = bytearray(), 0, 0
    table, prefix = {}, None
    size, decoded, first = minimum + 1, clear + 2, True  # the decoder's code width and table

    def emit(code):
        nonlocal bits, held, size, decoded, first
        bits |= code << held
        held += size
        while held >= 8:
            out.append(bits & 255)
            bits >>= 8
            held -= 8
        if code == clear:
            size, decoded, first = minimum + 1, clear + 2, True
        elif code != clear + 1:
            if not first and decoded < 4096:
                decoded += 1
                if decoded == 1 << size and size < 12:
                    size += 1
            first = False

    emit(clear)
    for index in indices:
        if prefix is None:
            prefix = index
        elif (prefix, index) in table:
            prefix = table[(prefix, index)]
        else:
            emit(prefix)
            table[(prefix, index)] = clear + 2 + len(table)
            prefix = index
            if len(table) + clear + 2 >= 4096:
                emit(prefix)
                emit(clear)
                table, prefix = {}, None
    if prefix is not None:
        emit(prefix)
    emit(clear + 1)
    if held:
        out.append(bits)
    return blocks(bytes(out))


def blocks(data):
    return b"".join(bytes([len(data[at:at + 255])]) + data[at:at + 255] for at in range(0, len(data), 255)) + b"\x00"


def gif(width, height, body, palette=b"\x00\x00\x00\xff\x00\x00\x00\xff\x00\x00\x00\xff"):
    bits = max(0, (len(palette) // 3 - 1).bit_length() - 1)
    return b"GIF89a" + struct.pack("<HHBBB", width, height, 0x80 | bits, 0, 0) + palette + body + b"\x3b"


def image(left, top, width, height, data, minimum=2):
    return b"\x2c" + struct.pack("<HHHHB", left, top, width, height, 0) + bytes([minimum]) + data


def stress_files():
    """Large and adversarial GIFs: (name, bytes)."""
    yield "huge frame", gif(64, 64, image(0, 0, 65535, 65535, lzw([1] * 100000, 2)))
    yield "many frames", gif(64, 64, (b"\x21\xf9\x04\x08\x00\x00\x00\x00" + image(0, 0, 64, 64, lzw([2] * 8, 2))) * 20000)
    palette = bytes(index for index in range(256) for _ in range(3))
    smooth = [(x // 64 + y // 16) % 256 for y in range(1024) for x in range(4096)]
    yield "string codes", gif(4096, 1024, image(0, 0, 4096, 1024, lzw(smooth, 8), 8), palette=palette)
    yield "clear codes", gif(16, 16, image(0, 0, 16, 16, blocks(bytes.fromhex("244992") * 300000)))
    previous = (b"\x21\xf9\x04\x0c\x00\x00\x00\x00" + image(0, 0, 2048, 2048, lzw([3] * 4, 2))) * 200
    yield "disposal previous", gif(2048, 2048, previous)


def stress():
    """Decode the stress files; answer the failures."""
    failures = []
    with tempfile.TemporaryDirectory() as directory:
        for name, data in stress_files():
            path = Path(directory) / "stress.gif"
            path.write_bytes(data)
            started = time.monotonic()
            done, crashed, trailer = run([("qs", str(path))], timeout=30)
            spent = time.monotonic() - started
            verdict = "trap" if crashed else ("slow" if spent > 2 else "ok")
            print(f"stress {name:<20} {len(data) / 1e6:6.2f} MB {spent:6.2f} s  {verdict}", flush=True)
            if verdict != "ok":
                failures.append(f"stress {name}: {verdict} {trailer.strip()[-200:]}")
    return failures


def mutate(data, rng, donors):
    data = bytearray(data)
    for _ in range(rng.randint(1, 6)):
        choice = rng.random()
        at = rng.randint(0, len(data))
        if choice < 0.25 and data:
            data[min(at, len(data) - 1)] ^= 1 << rng.randint(0, 7)
        elif choice < 0.4:
            data[at:at] = rng.choice(TOKENS)
        elif choice < 0.5 and data:
            del data[at:at + rng.randint(1, 16)]
        elif choice < 0.6 and data:
            del data[at:]
        elif choice < 0.7 and data:
            end = min(len(data), at + rng.randint(1, 64))
            data[at:at] = data[at:end] * rng.randint(1, 8)
        elif choice < 0.85:
            donor = rng.choice(donors)
            start = rng.randint(0, max(0, len(donor) - 1))
            data[at:at] = donor[start:start + rng.randint(1, 200)]
        elif data:
            data[min(at, len(data) - 1)] = rng.choice([0, 1, 2, 7, 8, 11, 12, 0x80, 0xff])
    return bytes(data)


def run(jobs, timeout):
    """Run `jobs` [(flags, path)] in one tool process: (finished count, crashed?, stderr)."""
    with tempfile.TemporaryDirectory() as directory:
        listing = Path(directory) / "list.txt"
        listing.write_text("".join(f"{flags} {path}\n" for flags, path in jobs))
        try:
            result = subprocess.run([str(TOOL), str(listing), directory], capture_output=True, timeout=timeout, env=ENVIRONMENT)
        except subprocess.TimeoutExpired as expired:
            return len((expired.stdout or b"").splitlines()), True, "timeout"
        return len(result.stdout.splitlines()), result.returncode != 0, result.stderr.decode("utf-8", "replace")


def main():
    parser = argparse.ArgumentParser()
    parser.add_argument("--cases", type=int, default=20000)
    parser.add_argument("--seed", type=int, default=1)
    parser.add_argument("--batch", type=int, default=500)
    parser.add_argument("--no-stress", action="store_true")
    parser.add_argument("--guard-malloc", action="store_true")
    options = parser.parse_args()
    if options.guard_malloc:
        ENVIRONMENT["DYLD_INSERT_LIBRARIES"] = "/usr/lib/libgmalloc.dylib"
    stressed = [] if options.no_stress else stress()
    rng = random.Random(options.seed)
    seeds = sorted(p for corpus in CORPORA.values() for p in corpus.glob("*.gif") if p.stat().st_size < 200000)
    donors = [p.read_bytes() for p in seeds]
    failures = []
    done, crashed, trailer = run([("qs", str(seed)) for seed in seeds], timeout=600)
    print(f"corpus: {len(seeds)} files, {'crashed: ' + trailer.strip()[-300:] if crashed else 'no traps'}", flush=True)
    if crashed:
        failures.append(f"corpus file {seeds[done]}: {trailer.strip()[-300:]}")
    with tempfile.TemporaryDirectory() as work:
        made = 0
        while made < options.cases:
            count = min(options.batch, options.cases - made)
            jobs = []
            for index in range(count):
                path = Path(work) / f"{made + index}.gif"
                path.write_bytes(mutate(rng.choice(donors), rng, donors))
                jobs.append(("qs", str(path)))
            start = 0
            while start < len(jobs):
                done, crashed, trailer = run(jobs[start:], timeout=120)
                if not crashed:
                    break
                bad = start + done
                FAILURES.mkdir(parents=True, exist_ok=True)
                saved = FAILURES / f"case-{made + bad}.gif"
                shutil.copy(jobs[bad][1], saved)
                failures.append(f"{saved}: {trailer.strip()[-300:]}")
                print(f"FAIL {failures[-1]}", flush=True)
                start = bad + 1
            made += count
            for path in Path(work).iterdir():
                path.unlink()
            print(f"{made} cases, {len(failures)} failing", flush=True)
    peak = resource.getrusage(resource.RUSAGE_CHILDREN).ru_maxrss
    peak_mb = peak / (1024 * 1024) if sys.platform == "darwin" else peak / 1024
    print(f"{options.cases} cases: {len(failures)} traps or hangs; peak memory of a decoding process {peak_mb:.1f} MB")
    for line in stressed:
        print(f"FAIL {line}")
    return 1 if failures or stressed else 0


if __name__ == "__main__":
    sys.exit(main())