Skip to content

Coverage Counterexample Search

Method — instantiates Target-Complete Mapping Design

Actively hunts for a single required target that no valid source covers — a counterexample to the completeness claim — instead of tallying how much is covered.

Coverage Counterexample Search tries to break the completeness claim rather than measure it: it adversarially hunts for one required target that no valid witness reaches — a counterexample that falsifies "everything is covered." Its defining move is the falsification stance. A coverage figure of 99% is treated as unproven until a genuine search fails to find the missing 1%, so the method's success is counted in counterexamples found (each a concrete, registered gap) and its confidence comes from a hard search coming up empty. It populates the uncovered-target register with reproducible misses instead of an aggregate score.

Example

A security operations center claims its detections cover "every MITRE ATT&CK technique relevant to our environment," and the dashboard reads 94%. Instead of trusting the number, the team runs a counterexample search: enumerate technique-by-asset-class combinations and, for each, try to exhibit a detection rule that would actually fire. The search surfaces a counterexample — credential-dumping on the CI/CD build agents has no rule at all, because that asset class was added after the detection library was last mapped. That single reproducible miss goes into the uncovered register and reframes the conversation from "94% covered" to "here is a specific blind spot on a high-value asset." (MITRE ATT&CK is a real framework, used here as context; the specific gap is illustrative.)

How it works

What distinguishes it is that it accumulates disproof, not coverage. It enumerates or samples the required target space and, for each target, attempts to produce a valid witness; the first target for which no candidate meets the validity rule is a counterexample and goes to the register. Confidence is inverted from the usual metric: it rises only when a strong, wide search fails to find a gap. A weak search that finds nothing proves little.

Tuning parameters

  • Search strategy — exhaustive enumeration versus adversarial sampling of the regions most likely to be weak. Targeting weak spots finds gaps fastest; exhaustion is what licenses a completeness claim.
  • Adversary strength — how hard it tries to disprove a candidate witness — accepting a nominal one versus demanding a real, traversed one. A harder adversary finds more gaps.
  • Target-space scope — the honest full space versus a convenient subset. Narrowing the space is the tempting cheat (see below).
  • Stop rule — halt at the first counterexample versus enumerate them all. First-found is cheap triage; full enumeration sizes the whole gap set.

When it helps, and when it misleads

Its strength is that it is the antidote to aggregate comfort: a single found counterexample outweighs any coverage percentage, and an honest search that comes up empty is real evidence of completeness rather than a self-report. Its weakness is that absence of a found counterexample proves completeness only if the search was genuinely hard and ran over the true target space — a weak search or a quietly narrowed space manufactures false confidence. The classic misuse is exactly that: scoping the target space to exclude the region where you would fail, or stopping the moment the tally looks acceptable, producing a reassuring empty result. The discipline that guards against it is to fix and freeze the true target space before searching — handing enumeration to Scenario Enumeration Workshop — and to record the search strength alongside the result, so an empty finding carries its own caveat. This is falsification applied to coverage: like a model checker, the method earns trust by trying to return a counterexample and failing.[1]

How it implements the components

Coverage Counterexample Search realizes the gap-detection side of the archetype — the components a falsification search produces or consumes:

  • required_target_space — the space it searches over, target by target, for a missing witness.
  • uncovered_target_register — its output: the found counterexamples, logged as concrete, reproducible gaps.
  • witness_validity_rule — the rule that defines "no valid witness": a target is a counterexample only when no candidate meets it.

It does not enumerate or define the target space in the first place — that is Scenario Enumeration Workshop — nor decide who fixes each found gap, which is Uncovered-Target Triage; the search finds the misses and logs them.

  • Instantiates: Target-Complete Mapping Design — the search is the adversarial check that a completeness claim can survive an attempt to break it.
  • Consumes: Scenario Enumeration Workshop supplies the frozen target space the search runs over.
  • Sibling mechanisms: Scenario Enumeration Workshop · Uncovered-Target Triage · Preimage Witness Generator · Bipartite Coverage Matrix · Graph Reachability Analysis

References

[1] In model checking, verifying a property means searching for a counterexample — an execution that violates it — and reporting the property as holding only when none can be found. Coverage counterexample search borrows that logic: it is the exhaustiveness of the failed hunt, not a headline percentage, that licenses "complete." ↩