🤖 machine learning

Verification Modulo Tested Library Contracts

Dit paper introduceert een raamwerk voor verificatie modulo geteste bibliotheekcontracten, waarbij een synthese-engine via een tegenbeeld-gestuurde leerbenadering adequate modulaire en contextuele contracten infereert om clientprogramma's die complexe bibliotheken gebruiken te verifiëren.

Oorspronkelijke auteurs: Abhishek Uppar, Omar Muhammad, Sumanth Prabhu, Deepak D'Souza, Madhusudan P, Adithya Murali

Gepubliceerd 2026-04-20

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Abhishek Uppar, Omar Muhammad, Sumanth Prabhu, Deepak D'Souza, Madhusudan P, Adithya Murali

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 machine bouwt, zoals een auto. Je hebt zelf de carrosserie, de stoelen en het stuur ontworpen (dit is je client-programma). Maar voor de motor, de versnellingsbak en de remmen maak je geen eigen ontwerp; je koopt deze onderdelen bij een gespecialiseerde fabriek (dit is je bibliotheek).

Het probleem is: hoe weet je of je auto veilig rijdt als je de motor niet zelf hebt gebouwd?

In de wereld van computerprogrammeren proberen wetenschappers al decennia om alles wiskundig te bewijzen. Ze willen elke schroef in de motor controleren om 100% zekerheid te hebben. Maar dat is als proberen elke zandkorrel in een woestijn te tellen: het kost te veel tijd en energie, en vaak lukt het gewoon niet.

De auteurs van dit paper, Abhishek Uppar en zijn team, hebben een slimme, pragmatische oplossing bedacht. Ze noemen het "Verificatie modulo geteste bibliotheekcontracten". Laten we dit uitleggen met een paar creatieve metaforen.

1. Het Probleem: De "Onmogelijke" Controle

Stel je voor dat je een auto bouwt en je wilt garanderen dat hij niet uit elkaar valt.

De oude manier: Je moet de motorfabriek dwingen om een wiskundig bewijs te leveren dat hun motor perfect is. Daarna moet jij bewijzen dat jouw auto perfect past op die motor.
- Nadeel: De motorfabriek (de bibliotheek) is zo groot en complex dat niemand het bewijs kan leveren. Het project stopt.

2. De Nieuwe Aanpak: De "Gevestigde" Test

De auteurs zeggen: "Laten we de motorfabriek niet dwingen om een wiskundig bewijs te leveren. In plaats daarvan laten we ze een contract tekenen."

Dit contract is een belofte. Bijvoorbeeld: "Als je de motor start met benzine, dan draait hij."

Stap 1: Jij (de programmeur) bouwt je auto en bewijst wiskundig dat hij veilig is, als die belofte waar is.
Stap 2: De motorfabriek moet die belofte niet bewijzen, maar ze moeten hem testen. Ze moeten duizenden keren proberen de motor te laten draaien met verschillende brandstoffen. Als de motor het contract breekt (bijv. hij stopt met draaien), dan is het contract slecht.

Als de motorfabriek duizenden keren slaagt in de test, gaan we ervan uit dat het contract klopt. Dan is jouw auto veilig, zelfs zonder dat we de motor van binnen hebben opengebroken.

3. De Twee Soorten Contracten: "Algemeen" vs. "Op Maat"

Het paper introduceert een heel nieuw idee: Contextuele Contracten.

Het Algemene Contract (Modulair):
Dit is als een handleiding voor een motor die voor iedereen geldt. De motorfabriek moet garanderen: "Deze motor werkt als je benzine, diesel of water toevoegt." Dat is heel moeilijk te testen en te bewijzen.
Het Contextuele Contract (Op Maat):
Dit is een contract dat alleen geldt voor jouw auto. Jij weet dat jij alleen benzine in je tank doet. Dus het contract kan simpel zijn: "Als je benzine toevoegt, draait de motor."
- Waarom is dit beter? Omdat je de motorfabriek niet hoeft te dwingen om te werken met water of diesel (wat ze misschien niet kunnen). Je test de motor alleen in de situatie waarin jij hem gebruikt. Dit maakt het contract veel simpeler en makkelijker te vinden.

De Metafoor:
Stel je voor dat je een sleutelbos hebt.

Een algemeen contract is een sleutel die voor elk slot ter wereld moet werken. Dat is onmogelijk.
Een contextueel contract is een sleutel die alleen werkt voor de deuren in jouw huis. Dat is veel makkelijker te maken en te testen.

4. Hoe werkt het? De "Leerkracht" en de "Testmeester"

De auteurs hebben een slimme computer-tool gemaakt (genaamd Dualis) die dit proces automatiseert. Het werkt als een spelletje van "Gok en Verbeter":

De Leerkracht (De Synthesizer): Deze probeert een contract te verzinnen. Hij zegt: "Ik denk dat de motor werkt als je benzine toevoegt."
De Testmeester (De Tester): Deze probeert de motor te laten draaien met allerlei rare dingen (water, zand, geen brandstof).
- Als de motor het contract breekt (bijv. hij stopt met draaien op benzine), zegt de Testmeester: "Fout! Probeer het opnieuw."
- De Leerkracht krijgt deze foutmelding als een voorbeeld en past het contract aan: "Ah, oké, misschien moet ik zeggen: 'Als je benzine toevoegt, en de tank niet leeg is'."
De Leerling (LLM's): Ze gebruiken zelfs kunstmatige intelligentie (zoals ChatGPT) als de Leerkracht. De AI leest de code en probeert slimme contracten te raden. Als de Testmeester een fout vindt, zegt de AI: "Oeps, ik had dat niet gezien," en probeert het opnieuw.

Dit gaat door tot de Leerkracht een contract heeft dat:

Wiskundig klopt voor jouw auto.
Door de Testmeester nooit kan worden "gepakt" (geen fouten gevonden).

5. Waarom is dit belangrijk?

Vroeger moesten we kiezen tussen:

Veiligheid: Alles wiskundig bewijzen (maar dan werken we alleen met heel kleine programma's).
Schaalbaarheid: Alles testen (maar dan weten we niet zeker of het veilig is).

Deze nieuwe methode combineert het beste van beide werelden:

We bewijzen wiskundig dat jouw specifieke programma veilig is.
We vertrouwen op uitgebreide tests voor de grote, complexe onderdelen die we niet zelf hebben geschreven.

Het is alsof je een brug bouwt. Je berekent wiskundig dat de brug veilig is, als de stalen balken sterk genoeg zijn. Je vraagt de staalfabriek niet om een wiskundig bewijs van de sterkte van elke balk, maar je laat ze de balken duizenden keren belasten met zware vrachtwagens. Als ze dat overleven, bouwen we de brug.

Kortom: Dit paper biedt een nieuwe manier om grote, complexe software te controleren door slimme "gokken" te doen die worden getoetst door strenge tests, in plaats van te proberen alles perfect te bewijzen. Het maakt het mogelijk om veilige software te maken voor de grote, ingewikkelde systemen van vandaag.

Titel: Verificatie Modulo Geteste Library Contracts (VMTLC)

Auteurs: Abhishek Uppar, Omar Muhammad, Sumanth Prabhu S, Deepak D'Souza, P. Madhusudan, en Adithiya Murali.

1. Het Probleem

Formele verificatie van grote softwaresystemen stuit vaak op schaalproblemen. Volledige automatisering is voor complexe specificaties en grote codebases vaak niet haalbaar zonder menselijke annotaties (zoals invariante en contracts). Het annoteren en formeel verifiëren van grote bibliotheken (libraries) is een enorme taak.

De auteurs stellen een pragmatische oplossing voor: Verificatie Modulo Geteste Library Contracts (VMTLC).
Het doel is om kleine client-programma's die gebruikmaken van grote bibliotheken te verifiëren, zonder de bibliotheek zelf formeel te verifiëren. In plaats daarvan worden er contracten gesynthetiseerd voor de bibliotheekmethoden die:

Voldoende sterk zijn om de correctheid van de client formeel te bewijzen.
Bestaan uit een set contracten die door een geautomatiseerde test-engine (tester) niet kunnen worden gefalsificeerd.

Het probleem wordt gedefinieerd als het synthetiseren van een set formele contracten $\Pi$ voor de methoden in een bibliotheek $L$ , zodat:

De client $C$ correct wordt bewezen onder de aanname van deze contracten.
Een deterministische test-generator (met een beperkte resource-begroting) geen tests kan vinden die de contracten schenden.

2. Methodologie

De auteurs presenteren een tegenstrijdigheid-gestuurde leerframework (counterexample-guided learning framework) om dit probleem op te lossen. Het proces verloopt in iteratieve rondes tussen drie componenten:

Synthesizer (Generalizing CHC Solver):
- Deze component probeert invariante voor de client en contracten voor de bibliotheek te vinden die voldoen aan een set van Constraint Horn Clauses (CHC).
- Cruciaal is dat de solver niet alleen de CHC's moet oplossen, maar de contracten moet generaliseren. Een solver die alleen de huidige positieve voorbeelden "overfit" (te specifiek is), zal niet werken.
- De auteurs gebruiken ICE-learning algoritmen (Implication Counterexample learning) als basis voor deze generaliserende solvers.
Test Engine:
- Deze component test de gesynthetiseerde contracten tegen de daadwerkelijke implementatie van de bibliotheek.
- Er zijn twee modi:
  - Modulair: De bibliotheekmethoden worden los getest.
  - Contextueel: De contracten worden getest binnen de context van de client (zie hieronder).
- Als de tester een schending vindt, worden deze testgevallen omgezet in positieve voorbeelden (voorbeelden die het contract moet dekken) en teruggevoerd naar de synthesizer.
Iteratief Proces:
- De synthesizer probeert een oplossing te vinden die de CHC's waar maakt én alle positieve voorbeelden dekt.
- Als de tester faalt, worden nieuwe voorbeelden toegevoegd en herhaalt het proces.
- Het proces stopt wanneer de client is geverifieerd én de contracten de test doorstaan.

Nieuwe Concepten:

Contextuele Contracten: In tegenstelling tot traditionele modulair contracten (die gelden in alle mogelijke contexten), gelden contextuele contracten alleen in de specifieke context waarin de client de bibliotheek aanroept. Dit maakt de contracten vaak eenvoudiger en makkelijker te synthetiseren, omdat ze geen algemene precondities hoeven te dekken die de client nooit genereert.
Observer Methods: De contracten en invariante worden uitgedrukt in termen van "observer methods" (zuivere functies die de staat van objecten beschrijven zonder deze te veranderen), wat de koppeling tussen client en bibliotheek vereenvoudigt.

Gebruikte Leeralgoritmen:

De framework ondersteunt verschillende ICE-learners:

HornICE: Een beslissingsboom-gebaseerde leerder die symbolische methoden gebruikt.
LLM (Large Language Models): Gebruik van modellen (zoals Gemini) om contracten en invariante te suggereren op basis van prompts, die vervolgens worden gevalideerd en verfijnd door de ICE-loop.
Hybride: Een combinatie waarbij de LLM basispredicaten genereert die door HornICE worden gebruikt om beslissingsbomen te bouwen.

3. Belangrijkste Bijdragen

Het VMTLC Probleem: Een formele definitie van verificatie waarbij bibliotheken alleen worden getest en niet formeel geverifieerd, met als doel de schaalbaarheid van verificatie te vergroten.
Contextuele Contracten: De introductie en analyse van een nieuw type contract dat specifiek geldt voor de context van de client, wat leidt tot eenvoudigere specificaties.
Generaliserend Leerframework: Een framework dat ICE-learning combineert met testgeneratie om zowel client-invariante als bibliotheekcontracten gelijktijdig te synthetiseren.
Tool Implementatie (Dualis): Een tool die het framework implementeert en verschillende solvers (HornICE, LLM, hybride) ondersteunt.
Evaluatie: Een uitgebreide evaluatie op 43 benchmarks (C++ en Java) met grote datastructuur-bibliotheken (o.a. Folly, Abseil), waar state-of-the-art tools (zoals SeaHorn) faalden.

4. Resultaten

De tool Dualis werd geëvalueerd op een benchmark-suite van open-source datastructuur-bibliotheken.

Effectiviteit:
- Voor modulaire contracten slaagde de pure LLM-approach in het oplossen van 38 van de 43 benchmarks, vergeleken met 19 voor HornICE en 25 voor de hybride aanpak.
- Voor contextuele contracten was het succes nog groter: LLM loste 41 van de 43 benchmarks op.
- Contextuele contracten bleken over het algemeen sneller te synthetiseren en minder complex dan modulaire contracten.
Validatie: Alle gesynthetiseerde contracten werden handmatig en automatisch gecontroleerd en bleken correct (logisch consistent met de gesynthetiseerde invariante).
Robuustheid: De test-engine (AFL++) testte de contracten gemiddeld met 34 unieke testgevallen per contract, met een bitmap-coverage van 50%, wat aangeeft dat er een grondige exploratie van het programma-gedrag plaatsvond.
Mutatie-analyse: Bij het testen van "mutanten" (incorrecte programma's die testen ontlopen) bleek dat VMTLC met contextuele contracten soms "spurious" (vals-positieve) contracten kan genereren die de fout niet opvangen. Echter, VMTLC met modulaire contracten slaagde erin om alle 30 geteste mutanten af te wijzen. Dit bevestigt dat modulaire contracten veiliger zijn, maar contextuele contracten meer kracht bieden voor complexe scenario's.

5. Betekenis en Conclusie

Dit paper biedt een nieuwe richting in geautomatiseerde softwareverificatie. Het erkent dat volledige verificatie van grote bibliotheken vaak onhaalbaar is, en stelt een pragmatische tussenweg voor: verificatie van de client onder de aanname van geteste bibliotheken.

Schaalbaarheid: De methode maakt het mogelijk om grote codebases te verifiëren door de complexiteit van het verifiëren van de bibliotheek te vervangen door uitgebreid testen.
Rol van AI: Het paper demonstreert succesvol hoe Large Language Models (LLMs) kunnen worden geïntegreerd in formele verificatiepipelines als "hypothesis generators" binnen een ICE-learning framework, waarbij de formaliteit van de solver de onbetrouwbaarheid van de LLM compenseert.
Toekomstperspectief: Hoewel er een risico bestaat op het synthetiseren van vals-positieve contracten (vooral bij contextuele contracten), suggereert de evaluatie dat dit risico klein is in de praktijk, mits er sterke testgenerators worden gebruikt. De methode opent de deur voor verificatie van systemen die vandaag de dag buiten bereik liggen van geautomatiseerde tools.

Kortom, Dualis toont aan dat het combineren van formele logica, testgeneratie en machine learning een krachtige strategie is om de kloof tussen theoretische verificatie en praktische, schaalbare softwarekwaliteit te overbruggen.