🤖 machine learning

Verification Modulo Tested Library Contracts

Il paper propone un framework di apprendimento guidato da controesempi, implementato nello strumento VMTLC, per sintetizzare contratti modulari e contestuali adeguati che consentano di verificare programmi client che utilizzano librerie complesse, combinando la risoluzione di vincoli con un motore di testing.

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

Pubblicato 2026-04-20

📖 5 min di lettura🧠 Approfondimento

CC BY 4.0

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

Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

🛠️ Il Problema: Costruire una Casa senza Controllare i Mattoni

Immagina di voler costruire una casa complessa (il programma cliente). Per farlo, non vuoi mescolare il cemento o forgiare l'acciaio da zero; vuoi usare mattoni, finestre e porte già pronti prodotti da un'azienda specializzata (la libreria).

Il problema è che per essere sicuro che la tua casa non crollerà, dovresti teoricamente controllare ogni singolo mattone per vedere se è perfetto. Ma queste librerie sono enormi, piene di milioni di righe di codice. Controllarle tutte formalmente (come un ispettore matematico) richiederebbe anni e sarebbe impossibile da automatizzare.

D'altra parte, se non controlli i mattoni e metti solo un "speriamo bene", la casa potrebbe crollare.

💡 La Soluzione: "Verifica Modulo Contratti Testati"

Gli autori di questo paper propongono un approccio intelligente e pragmatico, che chiamano Verifica Modulo Contratti Testati di Libreria.

Ecco come funziona, passo dopo passo, con una metafora:

1. I Contratti (Le Promesse)

Invece di controllare come è fatto il mattone (il codice interno della libreria), chiediamo alla libreria di firmare un contratto (una promessa scritta).

Esempio: "Se mi dai un numero positivo, il mio mattone (metodo) ti restituirà sempre un numero positivo."
Il nostro obiettivo è trovare queste promesse giuste che permettano di dimostrare matematicamente che la tua casa (il programma cliente) è sicura.

2. Il Controllo Incrociato (Il Tester)

Qui sta la magia. Non ci fidiamo ciecamente della promessa scritta. Invece di controllare il codice della libreria, usiamo un robot tester (un generatore di test) che prova a "rompere" la promessa.

Il robot prova a dare numeri negativi al mattone per vedere se esce un numero negativo (violando il contratto).
Se il robot non riesce a trovare un errore dopo milioni di tentativi, diamo per buona la promessa.

3. L'Intelligenza Artificiale (Il Sintetizzatore)

C'è un problema: scrivere queste promesse a mano è difficile. Quindi, usiamo un'intelligenza artificiale (basata su algoritmi di apprendimento e, in alcuni casi, su LLM come i modelli linguistici) che fa un gioco di "indovina e correggi":

Indovina: L'AI propone un contratto per la libreria.
Verifica: Il sistema controlla se, con quel contratto, la tua casa è sicura.
Testa: Il robot tester prova a trovare un errore in quel contratto.
Correggi: Se il robot trova un errore (es. "Ehi, con questo numero il contratto non vale!"), l'AI impara dall'errore e propone un contratto migliore.
Si ripete finché non si trova un contratto che rende la casa sicura e che il robot non riesce a rompere.

🌟 La Grande Innovazione: I "Contratti Contestuali"

Questa è la parte più geniale del paper.

Nella verifica tradizionale, un contratto deve essere vero sempre, in ogni universo possibile.

Contratto Modulare (Vecchio): "Il mio mattone restituisce sempre un numero positivo, anche se il mondo è capovolto, anche se l'utente è pazzo, anche se il sole esplode." (È molto difficile da scrivere e da dimostrare).

Gli autori introducono i Contratti Contestuali.

Contratto Contestuale (Nuovo): "Il mio mattone restituisce sempre un numero positivo, ma solo se l'utente che mi chiama (il tuo programma) si comporta in modo normale."

L'analogia del ristorante:

Contratto Modulare: "Il cuoco promette che ogni piatto che esce dalla cucina è commestibile, anche se il cliente ordina 'zuppa di sabbia' o 'insalata di pneumatici'." (Impossibile da garantire).
Contratto Contestuale: "Il cuoco promette che ogni piatto è commestibile, purché il cliente ordini solo ingredienti che esistono nel menu."

Poiché il tuo programma (il cliente) usa la libreria in un modo specifico (non ordina "zuppa di sabbia"), possiamo scrivere contratti molto più semplici e facili da trovare. Il sistema verifica che il cliente non ordini cose strane, e poi verifica che il cuoco rispetti il contratto solo per gli ordini normali.

🤖 Come funziona nella pratica (Il Tool "Dualis")

Gli autori hanno costruito un tool chiamato Dualis. Immaginalo come un team di lavoro:

L'Architetto (Solver CHC): Cerca di dimostrare matematicamente che la casa è sicura.
Il Distruttore (Tester/Fuzzer): Cerca di trovare buchi nei contratti della libreria.
L'AI (HornICE o LLM): È il mediatore che scrive le promesse, impara dagli errori del Distruttore e aiuta l'Architetto a trovare la soluzione.

Hanno testato questo sistema su 43 programmi reali che usano librerie complesse (come quelle di Facebook e Google). Risultato?

I vecchi metodi automatici fallivano su quasi tutti i casi.
Il loro sistema (Dualis) è riuscito a verificare la maggior parte dei programmi, trovando contratti che funzionano e che il robot tester non riesce a rompere.

📝 In Sintesi

Questo paper ci dice che per verificare software complessi oggi, non dobbiamo essere perfetti su tutto. Possiamo:

Verificare formalmente la parte piccola che scriviamo noi (il cliente).
Testare massicciamente la parte grande che usiamo (la libreria).
Usare l'AI per trovare la "ponte" perfetto (i contratti) che collega le due parti.

È come dire: "Non devo sapere come è costruito il motore della mia auto per sapere che è sicura; basta che il costruttore mi garantisca (con un contratto testato) che se metto benzina, l'auto parte, e che io guidi solo su strade asfaltate."

È un passo enorme verso l'automazione della sicurezza software, rendendo possibile verificare programmi che prima sembravano troppo grandi e complessi da controllare.

Titolo: Verifica Modulo Contratti di Libreria Testati (Verification Modulo Tested Library Contracts)

Autori: Abhishek Uppar, Omar Muhammad, Sumanth Prabhu S, Deepak D'Souza, P. Madhusudan, Adithya Murali.
Istituzioni: Indian Institute of Science, Relyance AI, University of Illinois, University of Wisconsin.

1. Il Problema

La verifica formale automatizzata di programmi complessi che utilizzano grandi librerie è attualmente un compito proibitivo. I metodi tradizionali richiedono annotazioni umane (contratti e invarianti) sia per il codice client che per le librerie, e la verifica completa di entrambe le parti è spesso intrattabile a causa della complessità della ricerca di invarianti induttivi.

Gli autori propongono un approccio pragmatico per scalare la verifica: rilassare i garanzie di verifica formale per le librerie, sostituendole con un rigoroso processo di test, mentre si mantiene la verifica formale per il codice client.

Il problema centrale, definito come VMTLC (Verification Modulo Tested Library Contracts), è il seguente:
Dato un programma client $C$ che utilizza una libreria $L$ , trovare un insieme di contratti formali $\Pi$ per i metodi di $L$ tali che:

Il client $C$ sia formalmente provato corretto assumendo i contratti $\Pi$ .
Un generatore di test deterministico, con risorse limitate, non riesca a trovare alcun caso di test che violi i contratti $\Pi$ rispetto all'implementazione della libreria.

In sostanza, si sintetizzano contratti per la libreria che sono sufficienti a provare il client e che "passano lo scrutinio" di un motore di test, senza necessariamente essere formalmente verificati sulla libreria stessa.

2. Metodologia

Il framework proposto utilizza un ciclo di apprendimento guidato da controesempi (Counterexample-Guided Inductive Synthesis - CEGIS) che combina tre componenti principali:

A. Sintesi Simultanea di Contratti e Invarianti

Il sistema sintetizza contemporaneamente:

Contratti per la libreria: Specifiche formali per i metodi della libreria.
Invarianti per il client: Invarianti di ciclo e annotazioni per il codice client.
L'obiettivo è soddisfare un insieme di Clausi di Horn Vincolati (CHC) derivati dal client, dove le relazioni non interpretate rappresentano sia gli invarianti del client che i contratti della libreria.

B. Contratti Contestuali (Contextual Contracts)

Una delle innovazioni chiave è l'introduzione dei contratti contestuali.

I contratti modulari classici devono valere in tutti gli stati possibili e per tutti gli input.
I contratti contestuali valgono solo nel contesto specifico in cui il client chiama la libreria. Poiché il client impone precondizioni implicite (es. "inserisco solo numeri positivi"), i contratti della libreria possono essere più forti e più semplici da sintetizzare in questo contesto ristretto.
La verifica di questi contratti avviene eseguendo l'intero programma (client + libreria) con input generati, invece di testare i metodi della libreria in isolamento.

C. Framework di Apprendimento (ICE Learning)

Il cuore del sistema è un solver CHC generalizzante basato su algoritmi ICE (Implication CounterExample).

Iterazione: Il solver propone candidati per contratti e invarianti.
Verifica: Un solver di vincoli verifica se i candidati soddisfano i CHC del client.
Testing: Un generatore di test (basato su fuzzing) verifica se i contratti proposti violano l'implementazione della libreria.
Feedback: Se il test fallisce, i casi di test che causano la violazione vengono aggiunti come esempi positivi al set di apprendimento. Il solver deve quindi generalizzare i contratti per includere questi nuovi esempi, evitando l'overfitting (cioè evitare contratti che funzionano solo per gli esempi specifici ma non generalizzano).

D. Motori di Sintesi

Il framework è agnostico rispetto all'algoritmo di apprendimento utilizzato. Gli autori hanno implementato e confrontato:

HornICE: Un apprenditore basato su alberi decisionali che cerca soluzioni semplici (piccoli alberi).
LLM (Large Language Models): Utilizzo di modelli linguistici (es. Gemini) per proporre contratti e invarianti basati su prompt testuali.
Ibrido (HornICE + LLM): L'LLM suggerisce i predicati atomici (la grammatica di base) e HornICE costruisce la soluzione logica combinandoli.

3. Contributi Chiave

Definizione del Problema VMTLC: Formalizzazione della verifica modulo contratti testati, un nuovo paradigma che bilancia verifica formale e testing.
Contratti Contestuali: Introduzione e formalizzazione di contratti che valgono solo nel contesto del client, dimostrando che sono spesso più semplici da sintetizzare e più potenti per la verifica del client rispetto ai contratti modulari.
Framework di Apprendimento Unificato: Un ciclo CEGIS che integra solver CHC generalizzanti, generatori di test e apprenditori (inclusi LLM) per sintetizzare simultaneamente contratti e invarianti.
Strumento Dualis: Implementazione del framework in uno strumento Python che orchestra solvers (Z3), fuzzing (AFL++) e apprenditori.

4. Risultati Sperimentali

Gli autori hanno valutato il framework su 43 benchmark C++ derivati da librerie open-source reali (Folly, Abseil, Android) e da SV-COMP. Questi benchmark sono stati scelti perché falliscono la verifica automatizzata completa con strumenti dello stato dell'arte (es. SeaHorn).

Efficacia:
- L'approccio basato su LLM puro ha risolto 38/43 benchmark per contratti modulari e 41/43 per contratti contestuali.
- L'approccio HornICE (alberi decisionali) ha risolto circa la metà dei casi, mostrando limiti nella capacità di generalizzare espressioni complesse non presenti nel suo template predefinito.
- L'approccio Ibrido ha migliorato le prestazioni rispetto a HornICE puro, ma è stato superato dall'LLM puro in termini di numero di benchmark risolti.
Semplicità dei Contratti: I contratti contestuali sintetizzati sono risultati sistematicamente più piccoli e meno complessi di quelli modulari, confermando l'ipotesi teorica.
Validità: Tutti i contratti sintetizzati sono stati verificati manualmente e tramite solver di vincoli per garantire che non fossero "spuri" (falsi positivi).
Robustezza: Un piccolo studio sui "mutanti" (programmi errati) ha mostrato che mentre i contratti contestuali possono talvolta validare programmi errati (se il bug è in un percorso raro non raggiunto dai test), il framework è comunque efficace nel rifiutare la maggior parte dei programmi errati, offrendo un livello di garanzia superiore al semplice testing.

5. Significato e Implicazioni

Il lavoro rappresenta un passo significativo verso l'automazione della verifica di software su larga scala.

Scalabilità: Permette di verificare client complessi che utilizzano librerie enormi, dove la verifica completa della libreria è impossibile.
Nuovo Paradigma: Sposta il punto di equilibrio nel design space della verifica: si sacrifica la garanzia formale assoluta sulla libreria (sostituendola con test estensivi) per ottenere la scalabilità necessaria a gestire codice reale.
Ruolo degli LLM: Dimostra che gli LLM, se integrati in un ciclo di validazione formale e test (non usati come "oracoli" ciechi), possono essere strumenti potenti per la sintesi di specifiche, superando i limiti dei metodi simbolici puri in termini di copertura del linguaggio e generalizzazione.
Futuro: Apre la strada all'uso di contratti contestuali anche in contesti semi-automatizzati, dove gli ingegneri scrivono annotazioni ma si affidano al testing contestuale per validare le librerie.

In conclusione, Dualis dimostra che è possibile ottenere un alto grado di fiducia nella correttezza del codice client attraverso una combinazione intelligente di sintesi di contratti, verifica formale parziale e testing intensivo, superando i colli di bottiglia attuali della verifica automatica completa.