Un processus itératif de vérification qui alterne entre la vérification par modèle d'un système abstrait et des étapes d'affinement guidées par des contre‑exemples jusqu'à ce que la propriété soit prouvée sur le système concret ou qu'un contre‑exemple réel soit trouvé.

Principe

Exploiter les contre‑exemples produits au niveau abstrait pour distinguer les comportements spurious des erreurs réelles et affiner l'abstraction seulement quand c'est nécessaire, échangeant ainsi les fausses alertes dues à l'abstraction contre des augmentations ciblées de précision.

Démonstration

Vérifier une propriété de sécurité d'un composant logiciel via une abstraction par prédicats ; si le vérificateur renvoie un contre‑exemple, le simuler sur le programme concret. Si la simulation montre que la trace est spurious, ajouter des prédicats qui séparent le chemin spurious et relancer la vérification jusqu'à ce que la propriété tienne ou qu'une trace défaillante réelle soit produite.

Mauvaise application

Considérer chaque contre‑exemple comme réel sans tester sa spuriousité et accepter ainsi des négatifs faux, ou ajouter répétitivement des prédicats qui éliminent des traces spurious mais provoquent une explosion de l'espace d'états et une perte d'évolutivité.

Conséquence

Avec une abstraction sonore et des heuristiques d'affinement adéquates, la méthode produit souvent soit une preuve de correction sur un modèle abstrait compact, soit un contre‑exemple concret ; en pratique elle peut améliorer drastiquement l'évolutivité de la vérification par rapport à des méthodes sur états concrets.

Inversion

Une approche purement abstraite qui n'affine jamais en fonction des contre‑exemples (abstraction en une passe) ou une recherche exhaustive des états concrets sans abstraction — ces deux extrêmes génèrent soit des alarmes spurious persistantes, soit échouent à monter en échelle.

Limite

S'applique lorsqu'un modèle abstrait et une stratégie d'affinement peuvent être définis ; ne garantit pas la terminaison pour tous les systèmes (par ex. certains systèmes à états infinis ou des schémas d'affinement mal choisis) et son efficacité dépend de l'expressivité des prédicats ou des primitives d'affinement disponibles.

Tension sémantique

Entre précision et évolutivité : des abstractions plus fortes augmentent l'évolutivité mais génèrent plus de contre‑exemples spurious ; un affinement agressif réduit la spuriousité mais risque une explosion combinatoire.

Synthèse

Le CEGAR est une boucle fermée de vérification : abstraire, vérifier, analyser le contre‑exemple, affiner l'abstraction pour éliminer les comportements spurious, et répéter jusqu'à preuve ou contre‑exemple concret, en équilibrant sonorité, précision et ressources tout en reconnaissant la possibilité de non‑termination dans des cas pathologiques.