A team's random regression runs 100,000 packet groups through DCRouter every night, and has done so for a month. Every common case has been hit thousands of times. Then a reviewer asks: has all four inputs sending maximum-length packets to the same output at once ever happened? The answer, worked out on a whiteboard: in any one night, almost certainly not, and over the whole month, only about three chances in five. Random testing is very good at the middle of the distribution and very bad at its tail.

How long does random stimulus take to reach a rare corner, and what can be done about it?

The obvious answer, and why it breaks

The obvious belief is that random testing, run long enough, eventually covers everything, so a big enough regression catches every bug. "Eventually" hides the problem. A corner needs several independent conditions in the same cycle, and the probabilities of independent conditions multiply. Four conditions of 1 in 60 each give 1 in 13 million. The waiting time grows as fast as the corner shrinks, and real bugs live disproportionately in these corners, because the common cases were already exercised by designers' own tests.

The idea: rare events follow simple arithmetic

If a corner has probability p per trial, and trials are independent (fact M3):

• Expected wait 1/p: a corner of one in a million needs a million trials on average, and often several times more.

• Confidence needs more: to be 95% sure of at least one hit you need about 3/p trials, since (1 − p)^(3/p) ≈ e^(−3) ≈ 0.05.

• Conditions multiply: k independent conditions of probability q each give p = q^k, so each extra condition divides the chance again.

Build it: a DCRouter corner

Packets in this model are uniform random: each input picks one of 4 outputs and one of 15 lengths with equal probability, and the model treats a "packet group" as one header arriving on each input at once (illustrative). It computes three corners of increasing rarity, checks the formula by Monte Carlo, then repeats the hardest corner with the length biased so that 15 is chosen 20% of the time.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

"""The long tail: how long uniform random stimulus takes to hit a rare corner.

A corner is a combination of conditions that must hold in the same cycle. For DCRouter,
"all four inputs present a header for the same output, each with the maximum length 15"
needs four independent choices to line up. With uniform random packets each input picks
the same output with probability 1/4 and length 15 with probability 1/15, so (illustrative,
assuming all four headers arrive together) p = (1/4 * 1/15)^4 relative to output 0, times 4
outputs. Part 1 computes p for that corner and for two simpler ones, the expected number of
trials 1/p, and the chance of at least one hit in a regression of N trials, 1 - (1 - p)^N.
Part 2 checks the formula with a Monte Carlo run for the two-input corner. Part 3 shows what
biasing does: choosing length 15 with probability 0.2 instead of 1/15 multiplies p by 3^4 = 81.
"""
import random

corners = {
    "len 15 on one input":                 1 / 15,
    "two inputs, same output, both len 15": 4 * (1 / 4 * 1 / 15) ** 2,
    "four inputs, same output, all len 15": 4 * (1 / 4 * 1 / 15) ** 4,
}
trials = [1e3, 1e4, 1e5, 1e6, 1e7]
print("trials (packet groups):           " + " ".join(f"{int(t):>9d}" for t in trials))
probs = {}
for name, p in corners.items():
    probs[name] = [1 - (1 - p) ** t for t in trials]
    print(f"{name:34s}" + " ".join(f"{v:9.3f}" for v in probs[name]) + f"   (p = {p:.2e}, 1/p = {1 / p:,.0f})")

rng = random.Random(3)
p2 = corners["two inputs, same output, both len 15"]
runs, n = 4000, 1000
hits = sum(any(rng.random() < p2 for _ in range(n)) for _ in range(runs)) / runs
print(f"Monte Carlo, two-input corner, {n} trials, {runs} runs: hit rate {hits:.3f} (formula {1 - (1 - p2) ** n:.3f})")

biased = 4 * (1 / 4 * 0.2) ** 4
bprobs = [1 - (1 - biased) ** t for t in trials]
print(f"{'four-way corner, len 15 biased 20%':34s}" + " ".join(f"{v:9.3f}" for v in bprobs) + f"   (p = {biased:.2e}, 1/p = {1 / biased:,.0f})")
print(f"biasing the length alone makes the four-way corner {biased / corners['four inputs, same output, all len 15']:.0f} times more likely")

assert abs(hits - (1 - (1 - p2) ** n)) < 0.04
assert probs["four inputs, same output, all len 15"][2] < 0.05 and bprobs[2] > 0.9
print("PASS: in 100,000 trials uniform random has a 3% chance of the four-way corner; biasing the length raises it to 92%")

It prints:

trials (packet groups):                1000     10000    100000   1000000  10000000
len 15 on one input                   1.000     1.000     1.000     1.000     1.000   (p = 6.67e-02, 1/p = 15)
two inputs, same output, both len 15    0.671     1.000     1.000     1.000     1.000   (p = 1.11e-03, 1/p = 900)
four inputs, same output, all len 15    0.000     0.003     0.030     0.266     0.954   (p = 3.09e-07, 1/p = 3,240,000)
Monte Carlo, two-input corner, 1000 trials, 4000 runs: hit rate 0.663 (formula 0.671)
four-way corner, len 15 biased 20%    0.025     0.221     0.918     1.000     1.000   (p = 2.50e-05, 1/p = 40,000)
biasing the length alone makes the four-way corner 81 times more likely
PASS: in 100,000 trials uniform random has a 3% chance of the four-way corner; biasing the length raises it to 92%

How to read it: the two-input corner (1 in 900) is hit almost at once. The four-way corner (1 in 3.2 million) needs ten million trials for a 95% chance; the nightly 100,000 gives 3%, and even a month of nightly runs (about three million trials) gives only about three chances in five. Changing nothing but the length distribution, so that 15 is chosen 20% of the time instead of 1 in 15, multiplies the chance by 3^4 = 81 and turns the same nightly run into a 92% hit. The Monte Carlo line confirms the formula: 0.663 measured against 0.671 predicted.

What to do about the tail

In SystemVerilog, biasing is a constraint (fact V1). For DCRouter's length field:

1
2
3
4
5
6

// snippet: weighting the boundary lengths of a DCRouter packet
class dcr_packet;
  rand bit [3:0] len;
  rand bit [1:0] dst;
  constraint c_len { len dist { 1 := 20, 15 := 20, [2:14] :/ 60 }; }   // 1 and 15 each 20%; :/ shares 60 across the range
endclass

The dist weights make each boundary length appear 20% of the time while the 13 middle values share the remaining 60%.

How real teams do it

What breaks

A team (illustrative) shipped a switch whose arbiter mis-counted when all ports issued maximum bursts in the same cycle. Their random regression had run for months with uniform burst lengths and uniform port choice. Afterwards they computed the corner's probability under their stimulus: about one in two hundred million per cycle group. A coverage cross of "ports requesting × burst length at maximum" had never been written, so nobody saw the hole. Adding the cross and weighting maximum bursts made the corner appear in every nightly run.

Key takeaways

• A corner of probability p takes 1/p trials on average and about 3/p for 95% confidence.

• Independent conditions multiply, so multi-condition corners are far rarer than any single condition.

• Bias distributions, shrink configurations, add coverage crosses or prove formally, instead of running longer.

Related topics

• Part 4 overview: Stimulus

• SystemVerilog course: Constraint Operators