Over-Approximation

What Over-Approximation Means in Verification

Over-approximation is a modelling strategy that intentionally includes every real behaviour, plus some extra ones, so analysis can stay sound. It is common in verification because missing a real unsafe state is usually worse than temporarily admitting a few impossible ones.

The core trade-off is precision versus coverage. A narrower model may be easier to understand, but it can miss edge cases; a broader model can prove stronger safety claims, but often creates results that must be interpreted with care because some counterexamples may be artefacts of the abstraction.

Why Verification Tools Use It

In formal analysis, over-approximation helps answer the question “could something unsafe happen?” without having to explore every concrete execution exactly. That makes it useful for proving absence of certain classes of failure, especially when the state space is too large for exhaustive modelling.

It is also a practical way to keep models tractable. Instead of tracking every low-level detail, a verifier may collapse multiple states into one abstract state or widen a transition relation. The result is less computational cost, but also less certainty about whether every reported issue corresponds to a real defect.

False Positives, Soundness, and Follow-Up Checking

The main consequence of over-approximation is that it can produce false positives. A reported unsafe path may exist only in the model, not in the real system, so the output is often best treated as a candidate problem rather than a final verdict.

That does not make the method weak. It means the analysis is sound in a particular direction, it is designed to avoid missing real problems, even when that requires tolerating extra possibilities. In practice, teams often pair it with refinement, simulation, symbolic execution, or manual review to confirm whether a flagged state is actually reachable.

How It Relates to Security Analysis

Over-approximation is especially useful when security reviewers want to avoid blind spots. A model that includes all plausible attacker paths, configuration states, or privilege transitions can expose weaknesses that a more exact but incomplete model might overlook.

At the same time, broad models can make security analysis noisy. If the abstraction is too coarse, the team may spend time chasing impossible exposures, so the quality of the abstraction matters as much as the checking method itself.

Risk and Threat Considerations

Over-approximation creates a useful safety margin, but it can also obscure operational reality when teams mistake a model artefact for a real exposure or, worse, dismiss a genuine issue because the model already produced too many false alarms.

Failure mechanism: A coarse abstraction merges distinct states or transitions, so the verifier reports behaviours that are not actually reachable, or hides the concrete conditions needed to reproduce a real unsafe state.

Impact: Security teams may waste effort on false positives, under-triage real risk, or carry a model that looks reassuring while still missing important implementation details in review.

Practitioner Guidance

Why practitioners should care: The value of over-approximation depends on the question you are asking. Use it when soundness matters more than precision, and make sure reviewers know whether a result is a proof obligation, a suspected issue, or a modelling artefact.

What to watch for: If a model generates repeated alarms that cannot be reproduced in the real system, the abstraction is probably too broad for the decision you are trying to support. Tighten the model or add a validation step before treating outputs as actionable.

Related resources from NHI Mgmt Group

• Why is visibility over NHIs critical for security?
• What are the implications of using over-privileged browser extensions?
• When should teams prioritise CI/CD hardening over broader secret scanning?
• When does over-privileged NHI access become a material risk?