"""Chapter 22: is a combination of checkers worth it? (constructed teaching numbers) Section 22.3: two different checkers under the rule "any alarm blocks", with independent errors and with fully correlated errors; then one checker run three times, merged by "block on any alarm" and by "release only if a majority passes". Section 22.4: an ablation table built from a constructed detection matrix (100 seeded bugs), and the same configurations' false alarms from a constructed flag matrix (100 clean versions). Exercise 22.2: miss and false-alarm rates of a test suite plus a critique model. Only the standard library. Run: python3 tools/exercises/ch22_combination.py """ from itertools import product def pct(x): return f"{x:.1%}" print("=== 22.3 (1) two different checkers, rule: any alarm blocks ===") miss_a, miss_b = 0.30, 0.40 # chance of missing a real bug fa_a, fa_b = 0.10, 0.05 # chance of raising an alarm on a correct program # A bug gets through only if both checkers miss it. miss_or_indep = miss_a * miss_b # Fully correlated: every bug A misses, B misses too (B's misses contain A's). miss_or_corr = min(miss_a, miss_b) # A correct program is blocked if either checker raises a false alarm. fa_or_indep = 1 - (1 - fa_a) * (1 - fa_b) fa_or_corr = max(fa_a, fa_b) # B's false alarms fall inside A's print(f"A alone: miss {pct(miss_a)}, false alarm {pct(fa_a)}") print(f"B alone: miss {pct(miss_b)}, false alarm {pct(fa_b)}") print(f"A or B, independent errors: miss {pct(miss_or_indep)}, false alarm {pct(fa_or_indep)}") print(f"A or B, fully correlated errors: miss {pct(miss_or_corr)}, false alarm {pct(fa_or_corr)}") print() print("=== 22.3 (2) the same checker run three times ===") p, q = 0.30, 0.10 # per-run miss rate and false-alarm rate def at_least(k, n, r): """Probability that at least k of n independent events with probability r happen.""" total = 0.0 for outcome in product([0, 1], repeat=n): if sum(outcome) >= k: prob = 1.0 for o in outcome: prob *= r if o else 1 - r total += prob return total # Rule "any alarm blocks": a bug gets through only if all three runs miss it; # a correct program is blocked if at least one run raises a false alarm. miss_any_indep = at_least(3, 3, p) fa_any_indep = at_least(1, 3, q) # Rule "release only if at least two of three pass": a bug gets through if at least two runs # miss it; a correct program is blocked if at least two runs raise a false alarm. miss_maj_indep = at_least(2, 3, p) fa_maj_indep = at_least(2, 3, q) print(f"single run: miss {pct(p)}, false alarm {pct(q)}") print(f"any alarm blocks, independent runs: miss {pct(miss_any_indep)}, false alarm {pct(fa_any_indep)}") print(f"majority must pass, independent runs: miss {pct(miss_maj_indep)}, false alarm {pct(fa_maj_indep)}") print(f"identical runs (fully correlated), either rule: miss {pct(p)}, false alarm {pct(q)}") print() print("=== 22.4 ablation on 100 seeded bugs (constructed detection matrix) ===") # Each row: (caught by tests T, by critic C1, by critic C2, number of bugs with this pattern). # C1 and C2 are two critique models from the same model series. patterns = [ (1, 0, 0, 26), # only the tests catch these (1, 1, 1, 30), # tests and both critics (1, 1, 0, 8), # tests and C1 (1, 0, 1, 6), # tests and C2 (0, 1, 1, 17), # both critics, not the tests (0, 1, 0, 2), # C1 only (0, 0, 1, 1), # C2 only (0, 0, 0, 10), # nobody ] hours = {"T": 6, "C1": 3, "C2": 3} # human hours: writing tests; verifying each critic's flags total = sum(n for *_, n in patterns) assert total == 100 def caught(use, rows=patterns): """Versions in `rows` that at least one part in `use` raises an alarm on (rule: any alarm).""" idx = {"T": 0, "C1": 1, "C2": 2} return sum(n for *flags, n in rows if any(flags[idx[c]] for c in use)) configs = [ ("full: T + C1 + C2", ["T", "C1", "C2"]), ("without T", ["C1", "C2"]), ("without C1", ["T", "C2"]), ("without C2", ["T", "C1"]), ("without C1 and C2", ["T"]), ] for name, use in configs: c = caught(use) print(f"{name:20s} caught {c:3d}/{total} missed {total - c:3d} human hours {sum(hours[u] for u in use)}") for c in ["T", "C1", "C2"]: print(f"{c} alone catches {caught([c])}/{total}") miss_c1 = (total - caught(["C1"])) / total miss_c2 = (total - caught(["C2"])) / total both_miss = sum(n for t, c1, c2, n in patterns if not c1 and not c2) print(f"C1 misses {pct(miss_c1)}, C2 misses {pct(miss_c2)}; both miss {both_miss}/{total} = {pct(both_miss / total)}; " f"independence would predict {pct(miss_c1 * miss_c2)}") print() print("=== 22.4 false alarms on 100 clean versions (constructed flag matrix) ===") # The same three parts run on versions known to have no bug. Each row: (flagged by tests T, # by critic C1, by critic C2, number of clean versions with this pattern). A configuration # raises a false alarm on a clean version if any of its parts flags it, the same rule by which # `caught` counts a bug as found. C1 and C2 come from the same series, so their false alarms # overlap as their misses do. clean_patterns = [ (1, 0, 0, 2), # only the tests flag these (a flaky or over-strict test) (0, 1, 1, 20), # both critics, not the tests (0, 1, 0, 4), # C1 only (0, 0, 1, 3), # C2 only (0, 0, 0, 71), # nobody ] clean_total = sum(n for *_, n in clean_patterns) assert clean_total == 100 for name, use in configs: f = caught(use, clean_patterns) print(f"{name:20s} flagged {f:3d}/{clean_total} false-alarm rate {pct(f / clean_total)}") for c in ["T", "C1", "C2"]: print(f"{c} alone flags {caught([c], clean_patterns)}/{clean_total}") fa_c1 = caught(["C1"], clean_patterns) / clean_total fa_c2 = caught(["C2"], clean_patterns) / clean_total both_flag = sum(n for t, c1, c2, n in clean_patterns if c1 and c2) print(f"C1 flags {pct(fa_c1)}, C2 flags {pct(fa_c2)}; both flag {both_flag}/{clean_total} = {pct(both_flag / clean_total)}; " f"independence would predict {pct(fa_c1 * fa_c2)}") print() print("=== exercise 22.2 ===") n_bugs = 50 miss_t, miss_c = 0.20, 0.50 both_missed = 8 print(f"tests miss {pct(miss_t)} = {miss_t * n_bugs:.0f} bugs; critique misses {pct(miss_c)} = {miss_c * n_bugs:.0f} bugs") print(f"independent prediction for 'any alarm blocks': {pct(miss_t * miss_c)} = {miss_t * miss_c * n_bugs:.0f} bugs") print(f"fully correlated prediction: {pct(min(miss_t, miss_c))} = {min(miss_t, miss_c) * n_bugs:.0f} bugs") print(f"measured: {both_missed}/{n_bugs} = {pct(both_missed / n_bugs)}") fa_t, fa_c = 0.02, 0.30 print(f"false alarms, independent, any alarm blocks: 1 - (1-{fa_t})(1-{fa_c}) = {pct(1 - (1 - fa_t) * (1 - fa_c))}")