🤖 machine learning

A-IC3: Learning-Guided Adaptive Inductive Generalization for Hardware Model Checking

Deze paper introduceert A-IC3, een lichtgewicht machine learning-framework dat met behulp van een multi-armed bandit-algoritme dynamisch de meest effectieve inductieve generalisatiestrategieën selecteert om de prestaties en schaalbaarheid van de IC3 hardware-modelchecker significant te verbeteren.

Oorspronkelijke auteurs: Xiaofeng Zhou, Guangyu Hu, Hongce Zhang, Wei Zhang

Gepubliceerd 2026-04-24

📖 4 min leestijd☕ Koffiepauze-leesvoer

CC BY 4.0

Oorspronkelijke auteurs: Xiaofeng Zhou, Guangyu Hu, Hongce Zhang, Wei Zhang

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een enorme, ingewikkelde labyrint hebt gebouwd. Je doel is om te bewijzen dat er geen enkele weg uit dit labyrint leidt naar een "gevaarlijke val" (een fout in je ontwerp). Dit is wat hardware-ontwerpers doen: ze proberen te bewijzen dat hun chips nooit vastlopen of fouten maken.

Deze paper introduceert A-IC3, een slimme nieuwe manier om dit labyrint te doorzoeken. Hier is de uitleg in gewone taal, met een paar creatieve vergelijkingen.

1. Het Probleem: De Stijve Verkenner

Stel je voor dat je een verkenner bent in dit labyrint. Je loopt een pad op en komt een muur tegen die je niet mag passeren. Je moet nu een nieuwe regel bedenken die zegt: "Alle paden die op dit lijken, zijn ook verboden."

In de wereld van chipontwerp heet dit inductieve generalisatie.

Het oude probleem: De beste verkenner tot nu toe (de IC3-algoritme) gebruikt een stijve, vooraf ingestelde strategie. Het is alsof de verkenner altijd zegt: "Als ik een muur zie, schrijf ik altijd een heel lange, gedetailleerde regel op."
De nadelen: Soms is die lange regel te lang en kan hij hem niet gebruiken (te agressief). Soms is de regel te kort en blokkeert hij niet genoeg (te voorzichtig). Omdat de verkenner niet kan zien hoe het labyrint er op dat moment uitziet, maakt hij veel fouten en loopt hij vast.

2. De Oplossing: De Slimme Gokker (A-IC3)

De auteurs van dit paper zeggen: "Waarom gebruiken we één stijve strategie voor alles? Laten we de verkenner een slimme gokker maken die zich aanpast."

Ze noemen hun systeem A-IC3. Het werkt als een Multi-Armed Bandit (een gokautomaat met meerdere hendels).

De Hendels (Strategieën): In plaats van één manier van werken, heeft de verkenner nu vier verschillende "hendels" (strategieën):
1. De Voorzichtige: Schrijft korte, veilige regels.
2. De Balans: Schrijft gemiddelde regels.
3. De Agressieve: Schrijft heel krachtige, uitgebreide regels.
4. De Basis: Doet het minimum.
De Gok: Elke keer als de verkenner een nieuwe muur tegenkomt, kijkt hij naar de situatie (is het labyrint groot? zijn er veel muren? is het complex?). Vervolgens kiest hij welke hendel hij moet trekken.

3. Hoe leert het systeem? (De Feedback)

Dit is het meest interessante deel. De verkenner heeft geen "handboek" om uit te lezen. Hij leert terwijl hij werkt.

De Beloning: Als de verkenner een hendel trekt en de regel werkt perfect (hij blokkeert de verkeerde weg en kan makkelijk worden gebruikt), krijgt hij een beloning (een puntje).
De Straf: Als de regel te lang is en vastloopt, of te kort is en niets doet, krijgt hij geen punten of zelfs een straf.
De Leercurve: Naarmate de verkenner meer muren tegenkomt, begint hij te merken: "Oh, als het labyrint heel complex is, werkt de 'Agressieve' hendel het beste. Maar als het simpel is, is de 'Voorzichtige' hendel sneller."

Het systeem past zich dus live aan, zonder dat iemand het handmatig hoeft in te stellen.

4. Het Resultaat: Sneller en Slimmer

De auteurs hebben dit getest op 914 verschillende "labyrinten" (echte chipontwerpen).

Het resultaat: De verkenner met A-IC3 (de slimme gokker) kon veel meer labyrinten oplossen dan de oude, stijve verkenner.
De snelheid: Hij loste de moeilijkste labyrinten veel sneller op.
De analogie: Het is alsof je een auto hebt die niet alleen op de snelheid van de weg kijkt, maar ook op het weer, het verkeer en het wegdek. Als het regent, schakelt hij automatisch naar een veiligere modus. Als de weg leeg is, gaat hij harder. De oude auto had alleen maar een vaste versnelling.

Samenvatting in één zin

A-IC3 is een slimme, lerende assistent voor chipontwerpers die continu de beste manier kiest om fouten te blokkeren, net zoals een ervaren gids in een grot die weet wanneer hij voorzichtig moet zijn en wanneer hij snel kan rennen, afhankelijk van hoe donker en gevaarlijk de grot op dat moment is.

Dit maakt het proces van het controleren van chips veel sneller, goedkoper en betrouwbaarder.

Probleemstelling

Hardware model checking, en specifiek het IC3/PDR-algoritme (Inductive Construction of 3rd-order / Property Directed Reachability), is de state-of-the-art techniek voor het verifiëren van veiligheidseigenschappen in digitale ontwerpen. Een cruciale stap in IC3 is de inductieve generalisatie: het proces waarbij een tegenvoorbeeld voor inductiviteit (CTI - Counterexample to Inductiveness) wordt veralgemeend tot een bredere clausule die een groot aantal onbereikbare blokkeert.

De huidige uitdagingen zijn:

Statische Strategieën: Bestaande methoden (zoals CtgDown, EXCTG) gebruiken vaste of handmatig afgestelde strategieën voor generalisatie. Ze kiezen niet dynamisch tussen agressieve (sterke generalisatie, maar risico op niet-propagerende clausules) en conservatieve (zwakke generalisatie, maar hoge propageringskans) benaderingen.
Context-afhankelijkheid: De effectiviteit van een generalisatiestrategie hangt sterk af van de dynamische context van het bewijsproces (bijv. het frame-niveau, de dichtheid van clausules, de groei van de bewijsverplichtingen-queue). Een strategie die op het ene moment werkt, kan op het andere moment schadelijk zijn.
Beperkingen van bestaande ML-aanpakken: Eerdere machine learning-methoden (zoals NeuroPDR of DeepIC3) vereisen zware offline training en hebben hoge inferentie-kosten, waardoor ze ongeschikt zijn voor de miljoenen keren dat generalisatie binnen de innerlijke lus van IC3 wordt aangeroepen.

Methodologie: A-IC3

De auteurs stellen A-IC3 voor, een lichtgewicht framework dat inductieve generalisatie behandelt als een contextueel Multi-Armed Bandit (MAB) probleem. In plaats van een vaste strategie te gebruiken, leert het systeem online welke strategie het beste werkt voor een specifieke bewijssituatie.

1. Contextuele MAB Formulering

Het probleem wordt gemodelleerd als een agent die bij elke generalisatiestap een "arm" (een strategie) kiest op basis van een contextvector $x_t$ .

De Arms (Strategieën): Het framework definieert een spectrum van strategieën variërend van Basic tot Aggressive. Deze strategieën controleren parameters zoals het aantal CTG-pogingen (Counterexample to Generalization), recursiediepte en het aantal pogingen om literalen te verwijderen.
- Basic: Geen CTG-verkenning, alleen literal-dropping.
- Conservatief: Beperkte CTG-verkenning, geschikt voor vroege bewijsstadia.
- Balanced: Standaard verkenning.
- Aggressief: Diepe recursie en uitgebreide verkenning voor complexe CTI's.

2. Bewijs-bewuste Context Vector (Proof-Aware Context)

De agent ontvangt een contextvector $x_t \in \mathbb{R}^7$ die zowel lokale als globale kenmerken van het IC3-bewijs samenvat:

Lokale kenmerken: Diepte van de CTI, grootte van de kubus (aantal literalen), activiteitsscore (hoe vaak deze CTI voorkomt), en de lengte van de bewijsverplichtingen-queue (PO-queue).
Globale kenmerken: Huidig frame-niveau, grens-frame niveau (frontier), saturatie van het huidige frame (aantal clausules), en de groeisnelheid van de PO-queue.
Deze vector wordt genormaliseerd om schaalvariaties te compenseren.

3. PA-LinUCB Agent

Voor de besluitvorming wordt LinUCB (Linear Upper Confidence Bound) gebruikt, aangepast als PA-LinUCB (Proof-Aware LinUCB).

Werkingsprincipe: LinUCB schat de verwachte beloning voor elke strategie als een lineaire functie van de contextvector. Het balanceert exploratie (het testen van nieuwe strategieën) en exploitatie (het kiezen van de beste bekende strategie).
Integratie: De agent wordt opgeroepen binnen de recursieve Block-procedure van IC3. Na het genereren van een clausule en het proberen van propagatie, ontvangt de agent een beloning en update hij zijn parameters online.
Voordeel: LinUCB heeft een lage rekenkosten en vereist geen vooraf verzamelde datasets, wat het ideaal maakt voor de innerlijke lus van IC3.

4. Beloningsfunctie (Reward Function)

De beloning $r_t$ die de agent ontvangt, is een combinatie van:

Kwaliteit van groottereductie ( $R_s$ ): Hoeveel literalen zijn verwijderd? (Straf voor toename van grootte).
Kwaliteit van propagatie ( $R_p$ ): Hoe ver kan de clausule worden doorgestuurd naar hogere frames?
Bonusterm ( $R_b$ ): Extra beloningen of straffen voor specifieke gebeurtenissen, zoals het bereiken van de frontier (hoogte bonus) of over-generalisatie (straf).
De totale beloning is een gewogen som: $r_t = w_s R_s + w_p R_p + R_b$ .

Belangrijkste Bijdragen

Eerste adaptieve controller: A-IC3 is de eerste leer-gestuurde aanpak die inductieve generalisatie in IC3 behandelt als een contextueel beslissingsprobleem, zonder offline training.
Proof-aware context ontwerp: Een innovatieve representatie van de bewijstoestand die lokale moeilijkheidsgraden en globale vooruitgang combineert, waardoor een standaard LinUCB-agent effectief kan sturen.
Naadloze integratie: Het framework is geïntegreerd in rIC3 (de huidige state-of-the-art model checker) en werkt met minimale overhead, waardoor het direct toepasbaar is in industriële settings.

Resultaten

De methode werd geëvalueerd op een benchmarksuite van 914 instances (voornamelijk uit HWMCC'20, '24 en '25) met een time-out van 3600 seconden.

Oplossingspercentage: A-IC3 loste 653 gevallen op, wat 50 meer is dan de standaard rIC3-instelling (603) en significant meer dan rIC3-CtgDown (629) en rIC3-DynAMic (627).
PAR-2 Score: De PAR-2 score (een maatstaf voor prestaties waarbij time-outs dubbel worden geteld) verbeterde van 2541.05 (standaard) naar 2151.76 voor A-IC3. Dit is een verbetering van ongeveer 15-16% ten opzichte van de beste baseline.
Schaalbaarheid: De methode presteerde het beste op moeilijke gevallen (die >100 seconden nodig hebben), waarbij de verbetering het grootst was. Op makkelijke gevallen was de overhead verwaarloosbaar.
Convergentie: A-IC3 bereikte vaak een lager "termination level" (minder frames nodig voor een bewijs), wat aangeeft dat de gegenereerde clausules effectiever waren en sneller tot een inductief invariant leidden.

Significantie

Dit werk markeert een belangrijke stap in het integreren van machine learning in formele verificatie:

Van statisch naar adaptief: Het beweegt weg van handmatig ontworpen heuristieken naar een systeem dat dynamisch leert van de bewijscontext.
Efficiëntie: Het toont aan dat complexe AI-methoden (zoals Deep Learning) niet altijd nodig zijn; een lichtgewicht, online leermethode (MAB) kan al aanzienlijke prestatieverbeteringen leveren zonder de rekenkosten te verhogen.
Toekomstperspectief: Het opent de deur voor verdere integratie van leermechanismen in andere fasen van het model checking-proces, waarbij de interactie tussen lokale beslissingen en globale bewijsstrategieën wordt geoptimaliseerd.

Kortom, A-IC3 bewijst dat het adaptief kiezen van generalisatiestrategieën op basis van real-time feedback de efficiëntie van hardware model checking aanzienlijk kan verhogen, zelfs op de meest complexe industriële benchmarks.