Lesson 4.1's directed suite missed BUG_13 because its one bad-CRC packet was low priority, and BUG_21 because it woke the router from input 0. No reviewer would call either choice wrong; they were simply the choices the writer made. A generator that picks priority and port at random does not make the writer's choices. Over a few hundred packets it tries both priorities and all four ports without anyone deciding to.
Why does random stimulus find bugs that directed tests miss, and what does it cost?
One obvious view is that random testing is unprincipled: it wastes cycles on cases that do not matter and repeats cases already seen. The opposite view is that random, run long enough, covers everything. Both miss the shape of the curve. Random is very efficient at first, because almost every packet is a case not yet seen. It becomes very inefficient at the end, because the last unseen cases are found only by luck. Knowing where on that curve a regression sits is what makes random a strategy rather than a hope.
Independence from the writer: random choices do not share the blind spots of the person who wrote the tests (the other priority, the other port).
Combinations for free: every random packet also has a random length, destination, timing and neighbour activity, so interactions are exercised without being designed.
The cost: drawing uniformly from n kinds, the expected number of draws to see all of them is n·H_n (fact M2).
A DCRouter header has 4 destinations, 2 priorities and 16 lengths: 128 kinds. The model computes how many kinds uniform random packets see after t packets, checks it by simulation, and splits the time to see all 128 into the first half and the last ten.
"""Why random works, and why it slows down: the coupon collector on DCRouter headers.
A DCRouter header has 4 destinations x 2 priorities x 16 lengths = 128 kinds. Directed tests
can hit all 128 with 128 packets, if someone writes all 128. Uniform random packets hit a
new kind quickly at first and ever more slowly at the end: the expected number of packets to
see every kind is n * H_n (the coupon collector, fact M2). Part 1 prints the expected number
of kinds seen after t random packets, n * (1 - (1 - 1/n)^t), and the expected time to see
them all. Part 2 checks both by simulation. Part 3 splits the wait: how many packets go to
the first half of the kinds, and how many to the last ten.
"""
import random
n = 4 * 2 * 16
H = sum(1 / k for k in range(1, n + 1))
ts = [64, 128, 256, 512, 1024, 2048]
print(f"header kinds n = {n}; expected packets to see all of them n*H_n = {n * H:.0f}")
print("random packets: " + " ".join(f"{t:>6d}" for t in ts))
expect = [n * (1 - (1 - 1 / n) ** t) for t in ts]
print("kinds seen (formula) " + " ".join(f"{e:6.1f}" for e in expect))
rng = random.Random(7)
runs = 2000
seen_at = [0.0] * len(ts)
all_at = []
for _ in range(runs):
seen, t, firsts = set(), 0, []
while len(seen) < n:
t += 1
k = rng.randrange(n)
if k not in seen:
seen.add(k)
firsts.append(t)
if t in ts:
seen_at[ts.index(t)] += len(seen) / runs
for j, tt in enumerate(ts): # runs that finished early saw all n from then on
if t < tt:
seen_at[j] += n / runs
all_at.append(firsts)
print("kinds seen (sim) " + " ".join(f"{s:6.1f}" for s in seen_at))
mean_all = sum(f[-1] for f in all_at) / runs
half = sum(f[n // 2 - 1] for f in all_at) / runs
last10 = mean_all - sum(f[n - 11] for f in all_at) / runs
print(f"simulated packets to see all {n}: {mean_all:.0f} (formula {n * H:.0f})")
print(f"first {n // 2} kinds: {half:.0f} packets; last 10 kinds: {last10:.0f} packets")
assert all(abs(a - b) < 1.0 for a, b in zip(expect, seen_at))
assert abs(mean_all - n * H) / (n * H) < 0.03
assert last10 > 4 * half
print(f"PASS: random needs about {n * H / n:.1f} times as many packets as kinds; the last 10 kinds cost more than four times the first {n // 2}")It prints:
header kinds n = 128; expected packets to see all of them n*H_n = 695
random packets: 64 128 256 512 1024 2048
kinds seen (formula) 50.5 81.1 110.8 125.7 128.0 128.0
kinds seen (sim) 50.5 81.1 110.8 125.7 128.0 128.0
simulated packets to see all 128: 703 (formula 695)
first 64 kinds: 88 packets; last 10 kinds: 382 packets
PASS: random needs about 5.4 times as many packets as kinds; the last 10 kinds cost more than four times the first 64How to read it: 128 random packets see only 81 kinds, because some kinds repeat while others are missed; it takes about 695 packets (5.4 per kind) to see all 128. The first 64 kinds cost 88 packets; the last 10 cost 382. The simulation agrees with the formula at every point.
Directed | Uniform random | |
|---|---|---|
Packets to cover 128 header kinds | 128, if someone writes all 128 | About 695 on average |
Cases nobody listed | Never | Yes, in proportion to their probability |
Timing and combinations | Only those designed | Exercised as a side effect |
Rare corners (probability p) | If someone writes them | About 1/p packets (lesson 4.5) |
Cost to add a case | Engineering time per case | Simulation time, which is cheap |
Random trades simulation time for engineering time and imagination. That trade is excellent for the many common cases and poor for rare ones, which is why lessons 4.3 to 4.5 shape the randomness and Part 6 measures what it reached.
Practice | Purpose |
|---|---|
Random by default, directed for known corners | Breadth from random, precision where it is needed |
Functional coverage on every random regression | Shows which kinds were reached and which are still missing (Part 6) |
Watch the closure curve flatten | The slow finish is when to bias or direct stimulus, not to run longer |
A team (illustrative) planned "one random packet per header kind" for a block with 128 kinds and ran 128 packets per test. Their coverage report showed about 81 of 128 kinds per test, as the model predicts, and the remaining kinds varied from seed to seed. Running each test for 1,024 packets, or tracking coverage across many seeds, closed the gap.
About 81: random draws repeat some kinds and miss others; the expected count is 128·(1 − (1 − 1/128)^128).
When only a few kinds are unseen, each packet has a small chance of hitting one, so the expected wait for each new kind grows as the number left shrinks.
Random stimulus does not share the test writer's blind spots and exercises combinations for free.
Covering n equally likely cases takes about n·H_n random draws: fast at first, slow at the end.
Pair random with coverage, and bias or direct stimulus when the curve flattens.