open-standards/wai/oer-conformance/fuzz_differential.py

#!/usr/bin/env python3
"""Differential fuzzing of the two OER verifiers.

Conformance is reason-set-equivalence, and the corpus pins it vector by vector. This
checks the rest of the input space: it mutates real corpus receipts, chains, records,
ledgers, published keys and signatures -- type swaps at any member, deletions, unknown
members, respelled decimals, repeated member names, literals no JSON library writes
(`-0`, `1e2`, lone surrogates) -- and requires the reference verifier here and wai-rs
(`wai_oer_diff`) to report the same thing for every document: the same reasons, the
same refusal, and no crash in either.

    python3 fuzz_differential.py [--seed N] [--cases N]

Exit status 0 when every document agrees. Deterministic for a given seed. Needs
`cryptography`; receipts hashed with blake3 are included only when the `blake3` module
is installed -- without it the reference rightly reports `missing_capability` for them
(extension section 5) where wai-rs, which has blake3, goes on to check the hash.
"""
import argparse, copy, hashlib, importlib.util, io, json, os, random, subprocess, sys, tempfile

HERE = os.path.dirname(os.path.abspath(__file__))
sys.path.insert(0, HERE)
import oer2_verify as V  # noqa: E402
from cryptography.hazmat.primitives.asymmetric import ed25519  # noqa: E402

HAVE_BLAKE3 = importlib.util.find_spec("blake3") is not None


class Lit:
    """Raw JSON text, written verbatim."""
    def __init__(self, text):
        self.text = text


class Pairs:
    """An object that may repeat a member name."""
    def __init__(self, pairs):
        self.pairs = pairs


def enc(v):
    if isinstance(v, Lit):
        return v.text
    if isinstance(v, Pairs):
        return "{" + ",".join(json.dumps(k) + ":" + enc(x) for k, x in v.pairs) + "}"
    if isinstance(v, dict):
        return "{" + ",".join(json.dumps(k, ensure_ascii=False) + ":" + enc(x) for k, x in v.items()) + "}"
    if isinstance(v, list):
        return "[" + ",".join(enc(x) for x in v) + "]"
    return json.dumps(v, ensure_ascii=False)


BASE = json.load(open(os.path.join(HERE, "vectors.json")))
KEYS = BASE["keys"]
V01 = BASE["vectors"][0]
R = V01["receipts"][0]
BUNDLE = next(r for v in BASE["vectors"] for r in v["receipts"] if r.get("kind") == "bundle")
PRIV = ed25519.Ed25519PrivateKey.from_private_bytes(
    hashlib.sha256(b"settlement world node ledger vector key").digest())

VALUES = [None, True, False, 0, 1, -1, 5, 2**53 - 1, 2**53, -(2**53), 2**64, "", "x", "0", "1.5", "+1",
          " 1", "1.", "01", "1e1000", "١", "NaN", "abstain", "escalate", "2.0", "3.0", "sha-256",
          "sha3-512", "ed25519", [], {}, [0.5], {"a": 1}, [1, [2, [3]]], 0.5, 1e300,
          Lit("-0"), Lit("1e2"), Lit("1.0"), Lit("-0.0"), Lit("2.99999999999999977"), Lit("9007199254740993"),
          Lit('"\\u0000"'), Lit('"\\ud83d\\ude00"'), Lit('"\\ud800"'), Lit("1.7976931348623157e308"),
          Lit("123456789012345678901234567890")]
if HAVE_BLAKE3:
    VALUES.append("blake3")


def reseal(r):
    """Re-seal after an edit where the body still canonicalises, so the checks past the
    seal are reached; otherwise leave the stale seal, which is itself a case."""
    try:
        body = V.canonical_bytes(r)
        r["receipt_id"] = V.h(r["hash_alg"], body)
        r["chain"]["receipt_hash"] = V.h(r["hash_alg"], r["chain"]["prev_hash"].encode() + body)
        r["chain"]["signature"] = PRIV.sign(r["chain"]["receipt_hash"].encode()).hex()
    except Exception:
        pass
    return r


def paths(v, p=()):
    yield p
    if isinstance(v, dict):
        for k, x in v.items():
            yield from paths(x, p + (k,))
    elif isinstance(v, list):
        for i, x in enumerate(v):
            yield from paths(x, p + (i,))


def at(v, p):
    for k in p:
        v = v[k]
    return v


def mutate(rng, r, n):
    for _ in range(n):
        choices = [p for p in paths(r) if p]
        if not choices:
            break
        p = rng.choice(choices)
        parent, k = at(r, p[:-1]), p[-1]
        op = rng.random()
        if op < 0.55:
            parent[k] = copy.deepcopy(rng.choice(VALUES))
        elif op < 0.7 and isinstance(parent, dict):
            del parent[k]
        elif op < 0.8 and isinstance(parent, dict):
            parent[rng.choice(["extra", "zz", str(k) + "_x"])] = copy.deepcopy(rng.choice(VALUES))
        elif op < 0.9 and isinstance(parent[k], str):
            s = parent[k]
            parent[k] = rng.choice([s + "0", "+" + s, s.upper(), s[:-1], s + " ", s.replace(".", ","), s * 2])
        elif isinstance(parent, dict):  # a repeated member name
            items = list(parent.items())
            items.insert(rng.randrange(len(items) + 1), (k, copy.deepcopy(rng.choice(VALUES))))
            if len(p) == 1:
                return Pairs(items)
            at(r, p[:-2])[p[-2]] = Pairs(items)
            break  # the tree below is no longer plain dicts
    return r


def document(receipts, extra=None, keys=None):
    vec = {"name": "c", "receipts": receipts, "expected": []}
    vec.update(extra or {})
    return enc({"keys": KEYS if keys is None else keys, "vectors": [vec]})


def case(rng):
    kind = rng.random()
    if kind < 0.6:  # one receipt or bundle, mutated, re-sealed half the time
        r = mutate(rng, copy.deepcopy(rng.choice([R, BUNDLE])), rng.randint(1, 3))
        if rng.random() < 0.5 and not isinstance(r, Pairs):
            r = reseal(r)
        return document([r])
    if kind < 0.7:  # a two-receipt chain with a mutated link
        a, b = copy.deepcopy(R), copy.deepcopy(R)
        b["chain"]["prev_hash"] = a["chain"]["receipt_hash"]
        reseal(b)
        mutate(rng, rng.choice([a, b])["chain"], 1)
        return document([a, b])
    if kind < 0.8:  # records
        recs = copy.deepcopy(V01["records"])
        rid = R["settlement"]["record_id"]
        if rng.random() < 0.5:
            recs = rng.choice([[], None, "x", {rid: copy.deepcopy(rng.choice(VALUES))}])
        else:
            mutate(rng, recs[rid], 1)
        return document([copy.deepcopy(R)], {"records": recs})
    if kind < 0.85:  # ledgers
        ledger = copy.deepcopy(V01["ledger"])
        mutate(rng, ledger, rng.randint(1, 2))
        return document(copy.deepcopy(V01["receipts"][:20]), {"ledger": ledger})
    if kind < 0.93:  # published keys
        keys = copy.deepcopy(KEYS)
        name = next(iter(keys))
        keys[name] = rng.choice([None, 5, "", "zz", keys[name][:-2], keys[name] + "00", keys[name].upper(),
                                 " " + keys[name], "01" + "00" * 31, "00" * 32, "ec" + "ff" * 30 + "7f"])
        return document([copy.deepcopy(R)], keys=keys)
    r = copy.deepcopy(R)  # signature bytes
    sig = bytearray(bytes.fromhex(r["chain"]["signature"]))
    sig[rng.randrange(64)] ^= 1 << rng.randrange(8)
    r["chain"]["signature"] = rng.choice([sig.hex(), sig.hex().upper(), sig.hex()[:-2], "", " " + sig.hex()])
    return document([r])


def reference(text):
    try:
        doc = V.load(io.StringIO(text))
    except ValueError:
        return "REFUSED"
    except Exception as e:  # any other exception is a crash the fuzzer must report
        return "CRASH:load:" + type(e).__name__
    try:
        results = V.run(doc)
    except ValueError:
        return "NOFILE"
    except Exception as e:
        return "CRASH:run:" + type(e).__name__
    return " | ".join("%s=%s" % (x["vector"], ",".join(x["got"])) for x in results)


def main():
    ap = argparse.ArgumentParser(description=__doc__.split("\n\n")[0])
    ap.add_argument("--seed", type=int, default=1)
    ap.add_argument("--cases", type=int, default=20000)
    args = ap.parse_args()
    rng = random.Random(args.seed)
    texts = [case(rng) for _ in range(args.cases)]
    ours = [reference(t) for t in texts]
    with tempfile.NamedTemporaryFile("w", suffix=".jsonl", delete=False) as f:
        for t in texts:
            f.write(json.dumps(t) + "\n")
    rust = subprocess.run(
        ["cargo", "run", "-q", "--release", "--no-default-features", "--features", "oer",
         "--bin", "wai_oer_diff", "--", f.name],
        cwd=os.path.join(HERE, "..", "wai-rs"), capture_output=True, text=True, check=True).stdout.splitlines()
    os.unlink(f.name)
    assert len(rust) == len(ours), (len(rust), len(ours))
    diverged = [i for i in range(len(ours)) if ours[i] != rust[i]]
    crashes = sum(o.startswith("CRASH") for o in ours) + rust.count("CRASH")
    shape = {k: sum(1 for o in ours if f(o)) for k, f in [
        ("refused", lambda o: o == "REFUSED"), ("valid", lambda o: o.endswith("=")),
        ("with reasons", lambda o: o not in ("REFUSED", "NOFILE") and not o.endswith("=") and "CRASH" not in o)]}
    print("seed %d: %d documents (%s)%s" % (args.seed, len(ours), ", ".join("%d %s" % (n, k) for k, n in shape.items()),
                                           "" if HAVE_BLAKE3 else "; blake3 receipts left out (no blake3 module)"))
    for i in diverged[:20]:
        print("DIVERGED %d\n  reference: %s\n  wai-rs:    %s\n  document:  %s" % (i, ours[i], rust[i], texts[i][:400]))
    print("%d diverged, %d crashed" % (len(diverged), crashes))
    sys.exit(1 if diverged or crashes else 0)


if __name__ == "__main__":
    main()