From LaTeX and OCaml to LEAN4 and Executables: Lean-Checked Theorems and Generating Proof-Carrying Rust

Nel mondo del software, esiste una tensione costante tra il modo in cui scriviamo il codice e il modo in cui sappiamo che sia sicuro. I programmatori usano linguaggi di alto livello per descrivere logiche complesse in un modo che sia leggibile e gestibile, ma le macchine che eseguono questo codice parlano un linguaggio molto più semplice e rigido. Per passare dall'uno all'altro, i compilatori agiscono come traduttori, ma è proprio in questo processo di traduzione che spesso si nascondono gli errori. Un errore nella traduzione può trasformare un'istruzione sicura in una pericolosa, causando il crash di un programma o un comportamento imprevedibile. Per decenni, il modo più affidabile per garantire la sicurezza è stato verificare il codice macchina finale, ma ciò è difficile perché il significato di alto livello del programma originale viene spesso perso nel processo. La domanda che i ricercatori si pongono è se sia possibile mantenere la chiarezza del linguaggio originale di alto livello pur riuscendo a dimostrare, con assoluta certezza, che le istruzioni macchina finali faranno esattamente ciò che intendiamo.

Brent Hartshorn ha costruito un sistema che risponde a questa domanda trattando un singolo pezzo di codice come due cose diverse contemporaneamente. Immaginate un documento che può essere letto simultaneamente come una prova matematica e come un insieme di istruzioni per una macchina. In questo nuovo lavoro, l'autore prende un sottoinsieme di un linguaggio di programmazione chiamato OCaml, noto per le sue regole rigide sulla gestione dei dati, e conferisce a ogni definizione due significati distinti. Primo, il codice viene letto come un argomento logico, dove la struttura stessa del programma funge da prova che certe condizioni saranno sempre soddisfatte. Secondo, lo stesso codice viene tradotto in un linguaggio diverso chiamato Rust, progettato per velocità e sicurezza, e poi compilato in un programma che un computer può effettivamente eseguire. La genialità dell'approccio risiede nella verifica: la prova logica è controllata da un piccolo motore matematico fidato, mentre il programma in esecuzione è controllato rispetto a un interprete di riferimento che simula il codice passo dopo passo. Se i due corrispondono, e se la prova logica regge, il risultato è un software che arriva con il proprio certificato di sicurezza.

I ricercatori hanno iniziato costruendo un traduttore che comprende una specifica porzione di OCaml. Questo traduttore, scritto in Python, è abbastanza piccolo da poter essere letto e compreso da una singola persona, il che è fondamentale perché se il traduttore stesso fosse troppo complesso, non potremmo fidarci del suo output. Esso prende il codice OCaml e lo divide in due percorsi. Sul percorso della prova, converte il codice in un formato che un kernel matematico possa controllare. Questo kernel è un piccolo programma che agisce come un giudice, verificando che la logica sia solida senza fare assunzioni. Sul percorso del programma, il traduttore converte il codice in Rust, un linguaggio che viene compilato in codice macchina nativo veloce. Per garantire che la traduzione fosse perfetta, il team ha costruito anche un interprete di riferimento che esegue direttamente il codice OCaml originale. Hanno poi eseguito tredici programmi di esempio diversi attraverso sia la versione Rust compilata che l'interprete. In ogni singolo caso, il codice compilato ha prodotto esattamente lo stesso output dell'interprete, provando che il processo di traduzione non ha alterato il comportamento dei programmi.

Una volta che il codice è stato tradotto con successo, il team ha applicato un rigoroso controllo di sicurezza alla versione Rust compilata. Hanno trattato il codice compilato come un contratto, dove regole specifiche su come il programma dovrebbe comportarsi sono state scritte come teoremi matematici. Ad esempio, hanno controllato che i calcoli interi non causassero mai un overflow accidentale e il passaggio a un numero negativo, una fonte comune di bug nel software. Hanno scoperto che, sebbene la maggior parte di queste regole di sicurezza fosse rispettata, esistevano casi limite specifici in cui le regole venivano violate. In undici scenari diversi, il codice compilato raggiungeva un punto in cui un calcolo intero poteva andare in overflow, come quando si sottrae il numero più piccolo possibile dallo zero. Il sistema ha identificato correttamente questi casi come obblighi aperti, il che significa che il codice era sicuro ovunque tranne che in questi limiti specifici e noti. Su novanta controlli di sicurezza totali eseguiti sui programmi di esempio, settantanove sono stati pienamente dimostrati, mentre gli undici rimanenti sono stati lasciati aperti perché rappresentavano limiti reali e raggiungibili nel modo in cui il computer gestisce i numeri.

Il progetto è andato oltre applicando questo metodo a un piccolo kernel di un sistema operativo, un componente centrale del software che gestisce le risorse del computer. I ricercatori hanno preso un kernel che era stato precedentemente scritto in Python e Rust e lo hanno riscritto nel loro sottoinsieme di OCaml. Successivamente, hanno tradotto questa nuova versione in Rust e l'hanno compilata. Il risultato è una terza implementazione dello stesso kernel. Testando la nuova versione derivata da OCaml contro la versione originale in Python, essa ha risposto correttamente in tutti i 236 casi di test. Il team ha poi tentato di dimostrare la sicurezza di questo nuovo kernel. Hanno dimostrato con successo 227 dei 236 obblighi di sicurezza. I pochi rimasti non dimostrati non erano errori nel codice, ma piuttosto lacune negli strumenti matematici utilizzati per controllarli, specificamente riguardo al modo in cui il sistema gestisce cicli complessi e contatori. Ciò ha dimostrato che il metodo poteva scalare da piccoli esempi a un componente funzionale di un sistema operativo.

Forse la parte più sorprendente del lavoro è stata la capacità di trasformare un'equazione matematica direttamente in un programma funzionante. I ricercatori hanno preso un'equazione formale che descriveva il comportamento di un kernel, scritta in una notazione matematica standard, e l'hanno inserita in uno strumento che la convertiva in codice OCaml. Questo codice è stato poi compilato ed eseguito. Il programma risultante si è comportato esattamente come descritto dall'equazione, corrispondendo all'output del modello originale in Python in ogni istanza. Questo processo ha dimostrato che una descrizione matematica di alto livello può essere trasformata in un binario eseguibile verificato senza perdere il proprio significato. Il team ha dimostrato che la versione compilata di questa equazione soddisfaceva la maggior parte dei suoi contratti di sicurezza, sebbene alcuni dei passaggi logici più complessi richiedessero un ulteriore perfezionamento degli strumenti di controllo.

I risultati di questo lavoro suggeriscono una nuova strada per costruire software affidabili. Mantenendo il codice sorgente di alto livello e verificando sia il suo significato logico che la sua forma compilata, i ricercatori hanno creato un sistema in cui la sicurezza del programma finale è supportata da una prova matematica. Il metodo ha identificato con successo i limiti del mondo reale nel modo in cui i computer gestiscono i numeri, come l'overflow intero, e ha distinto questi casi dai veri bug. Sebbene il sistema non abbia dimostrato ogni singola regola di sicurezza per le parti più complesse del kernel, ne ha dimostrata la stragrande maggioranza, e quelli che sono rimasti aperti sono stati chiaramente identificati come aree in cui gli strumenti di controllo, piuttosto che il codice stesso, necessitavano di miglioramenti. Il lavoro si pone come una dimostrazione del fatto che è possibile possedere il processo di traduzione dal codice di alto livello alle istruzioni macchina, garantendo che l'eseguibile finale porti con sé un certificato di sicurezza che è rigoroso quanto la logica che lo ha creato.