💻 computer science

Misquoted No More: Securely Extracting F* Programs with IO

Questo articolo introduce SEIO*, un framework che combina la citazione relazionale con la generazione di sintassi verificata per estrarre in modo sicuro programmi F* con IO e tipi di raffinamento, debolmente incorporati in un calcolo profondamente incorporato, fornendo prove verificate da macchina di Robust Relational Hyperproperty Preservation (RrHP) per garantire la sicurezza contro l'arbitraria associazione avversaria.

Autori originali: Cezar-Constantin Andrici, Abigail Pribisova, Danel Ahman, Catalin Hritcu, Exequiel Rivas, Théo Winterhalter

Pubblicato 2026-07-20

📖 7 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Cezar-Constantin Andrici, Abigail Pribisova, Danel Ahman, Catalin Hritcu, Exequiel Rivas, Théo Winterhalter

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

La Rete di Sicurezza Invisibile

Immaginate di essere un maestro architetto che ha progettato un'automobile magnifica e a guida autonoma in un mondo immaginario perfetto, dove la fisica si comporta sempre esattamente come avete previsto. Avete scritto i progetti in un linguaggio speciale, super preciso, che vi permette di dimostrare matematicamente che l'auto non si scontrerà mai, non frenerà mai quando non dovrebbe e seguirà sempre le regole della strada. Questo è ciò che gli informatici chiamano "verifica formale". È come costruire un'auto in un sogno dove potete essere sicuri al 100% di ogni bullone e cavo.

Ma ecco il problema: quel mondo onirico non esiste sulla strada reale. Per guidare effettivamente l'auto, dovete tradurre i vostri progetti perfetti in un linguaggio che i motori e gli pneumatici reali possano comprendere, come il C o l'OCaml. Questo processo di traduzione è chiamato "estrazione". Il problema è che il traduttore (il programma per computer che esegue la conversione) non è perfetto. Potrebbe dimenticare un bullone, torcere un cavo o fraintendere una regola. Se l'auto del mondo reale viene costruita su un errore commesso durante la traduzione, la vostra prova perfetta di sicurezza diventa inutile. L'auto potrebbe sembrare sicura sulla carta, ma schiantarsi nella realtà.

Per anni, gli scienziati hanno cercato di risolvere questo problema controllando il lavoro del traduttore dopo il fatto, un po' come un meccanico che ispeziona un'auto dopo che è stata costruita per vedere se corrisponde ai piani. Ma questo articolo introduce un modo più intelligente: invece di controllare semplicemente l'auto finita, costruiscono un "certificato di sicurezza" durante la traduzione che dimostra, matematicamente, che l'auto reale è un gemello perfetto dell'auto del sogno, anche se il traduttore commette un errore. Chiamano questo un framework di "estrazione sicura" (secure extraction), ed è progettato per mantenere le vostre creazioni digitali al sicuro anche quando vengono mescolate con codice non verificato proveniente dal mondo esterno.

La Grande Idea dell'Articolo: Il Trucco Magico della "Citazione Relazionale"

Gli autori di questo articolo, un team di scienziati informatici, hanno costruito un nuovo framework chiamato SEIO★ (Secure Extraction of IO-star). Il loro obiettivo era risolvere il "probleto della traduzione" per i programmi scritti in F★, un linguaggio utilizzato per scrivere software altamente sicuri come gli strumenti crittografici. I programmi F★ sono spesso "profondamente incorporati" (shallowly embedded), un modo elegante per dire che sono scritti in uno stile astratto e di alto livello, ottimo per dimostrare le cose ma difficile da trasformare in codice reale per i computer.

Di solito, quando si trasformano questi programmi astratti in codice reale, si deve usare un "metaprogramma" (un programma che scrive altri programmi) per svolgere il lavoro pesante. Il vecchio metodo per farlo era rischioso: il metaprogramma scriveva il nuovo codice e poi cercava di scrivere una prova che il nuovo codice fosse corretto. Se la prova falliva, dovevi ricominciare da capo. Se la prova passava, dovevi comunque fidarti del fatto che il metaprogramma non avesse introdotto un bug durante la scrittura della prova. Era come chiedere a uno studente di correggere i propri compiti sperando che non imbrogliasse.

La scoperta degli autori è una tecnica che chiamano Citazione Relale (Relational Quotation). Invece di chiedere al metaprogramma di scrivere il codice finale e la prova, gli chiedono di fare qualcosa di molto più semplice: scrivere una derivazione di tipizzazione (typing derivation). Pensate a questo come a una scheda ricetta passo dopo passo che dice: "Passaggio 1: Prendi questo ingrediente. Passaggio 2: Mescolalo con quello". Questa scheda ricetta non cucina effettivamente il pasto; dimostra solo che gli ingredienti potrebbero essere cucinati in un piatto specifico.

Ecco la parte intelligente:

Il Metaprogramma (Lo Scrittore di Ricette): Il metaprogramma non verificato osserva l'originale programma astratto e genera questa "scheda ricetta" (la derivazione di tipizzazione). Poiché la scheda ricetta segue esattamente la struttura del programma originale, è molto facile da scrivere.
Il Controllo (L'Ispettore): Il linguaggio F★ stesso controlla questa scheda ricetta. Chiede: "Questa ricetta descrive effettivamente il programma originale?". Se il metaprogramma ha commesso un errore e ha scritto una ricetta per una torta quando l'originale era una zuppa, il controllo fallisce. Ma se la ricetta corrisponde, il linguaggio F★ è sicuro al 100% che la ricetta sia valida.
Il Passaggio Verificato (Il Maestro Chef): Una volta che la scheda ricetta è stata verificata, una diversa funzione, completamente verificata (un "Maestro Chef" che è stato matematicamente dimostrato essere perfetto), prende quella ricetta e cucina il piatto finale (il codice reale). Poiché la ricetta è stata provata corrispondente all'originale, e il chef è dimostrato capace di cucinare esattamente ciò che dice la ricetta, il piatto finale è garantito essere un gemello perfetto dell'originale.

Questo approccio minimizza la "fiducia" che dobbiamo riporre nel metaprogramma non verificato. Ci fidiamo solo che scriva la ricetta, non che cucini il cibo o corregga i compiti. La parte difficile — provare che il cibo sia sicuro — è affidata al Maestro Chef verificato.

Il Superpotere della "Compilazione Sicura"

L'articolo non si limita a garantire che il codice sia corretto; va oltre per assicurarsi che sia sicuro. Nel mondo reale, il vostro programma verificato potrebbe essere collegato con altro codice che non è verificato — magari codice scritto da un hacker, o semplicemente codice trascurato di un altro team. Questo codice "avversario" cerca di rompere le regole del vostro programma.

Gli autori dimostrano che il loro framework SEIO★ soddisfa una regola di sicurezza super forte chiamata Robust Relational Hyperproperty Preservation (RrHP). Per capire questo, immaginate che il vostro programma verificato sia una fortezza.

I vecchi metodi potrebbero dire: "Le mura della fortezza sono forti, quindi è sicura".
Questo articolo dice: "Anche se un hacker cerca di intrufolarsi dalla porta sul retro, o se cerca di ingannare le guardie, o se cerca di cambiare le regole del gioco, la vostra fortezza si comporterà ancora esattamente come avete progettato".

Dimostrano questo usando due "relazioni logiche", che sono come specchi bidirezionali. Uno specchio controlla se il codice reale fa tutto ciò che il codice astratto potrebbe fare. L'altro controlla che il codice reale non faccia nulla che il codice astratto non potrebbe fare. Dimostrando entrambi, mostrano che il codice reale è un'ombra perfetta e sicura dell'originale, indipendentemente dal codice disordinato con cui viene collegato.

Cosa Hanno Effettivamente Fatto (e Non Fatto)

Il team ha costruito questo framework interamente all'interno del linguaggio F★ e ha usato un computer per controllare ogni singolo passaggio della loro prova. Non hanno solo indovinato o simulato; hanno dimostrato matematicamente.

Cosa funziona: Hanno estratto con successo programmi che gestiscono l'Input/Output di file (leggere e scrivere file) e utilizzano "tipi di raffinamento" (tipi con regole extra, come "questo numero deve essere positivo"). Hanno dimostrato che anche con queste funzioni complesse, l'estrazione rimane sicura.
Cosa è ancora un lavoro in corso: L'articolo ammette che il loro sistema attuale non gestisce le funzioni ricorsive (funzioni che chiamano se stesse) o i "tipi dipendenti" completi (dove i tipi possono dipendere dai valori) nel modo più naturale. Hanno dovuto usare un workaround che coinvolge gli iteratori (cicli) per la ricorsione. Notano anche che il loro metaprogramma a volte deve indovinare dove inserire certi controlli di sicurezza, il che può essere un po' macchinoso.
Il succo della questione: Non hanno risolto ogni problema nell'universo della programmazione, ma hanno costruito un nuovo, molto più sicuro ponte tra il mondo delle prove perfette e il mondo del codice reale. Hanno dimostrato che, dividendo il lavoro in una fase di "scrittura della ricetta" e una fase di "cottura", si può ottenere una forte sicurezza senza dover fidarsi completamente dello scrittore della ricetta.

In breve, SEIO★ è un nuovo strumento che permette ai programmatori di prendere le loro idee perfette e verificate e trasformarle in software del mondo reale con una rete di sicurezza matematicamente garantita, assicurando che, anche se il processo di traduzione è imperfetto, il risultato finale sia comunque al sicuro dal caos del mondo esterno.

Sintesi Tecnica: Misquoted No More: Estrazione Sicura di Programmi F★ con IO

1. Enunciato del Problema

Il linguaggio orientato alle prove F★ è ampiamente utilizzato per scrivere e verificare programmi che sono debolmente incorporati (shallowly embedded) tramite monadi per rappresentare gli effetti (ad esempio, l'I/O). Una volta verificati, questi programmi vengono tipicamente estratti in linguaggi mainstream come OCaml o C per l'esecuzione. Tuttavia, questo processo di estrazione è attualmente non verificato e costituisce parte del Trusted Computing Base (TCB).

La sfida principale risiede nel passaggio di "quotation" (citazione) richiesto per estrarre i programmi debolmente incorporati. La quotazione comporta la traduzione di un programma debolmente incorporato (dove gli effetti sono rappresentati da tipi monadici) in un albero sintattico di sintassi profondamente incorporata (deeply embedded), ovvero una rappresentazione concreta del linguaggio di destinazione. Verificare il metaprogramma di quotazione è una sfida aperta significativa perché richiede una meta-teoria meccanizzata per il linguaggio sorgente e, anche per sistemi maturi come Rocq, la verifica della quotazione rimane irrisolta.

Gli approcci precedenti per certificare l'estrazione si affidano pesantemente alla validazione della traduzione (translation validation), dove un metaprogramma genera sia il codice estratto sia una prova di correttezza, la quale viene poi controllata dal tipo (type-checked). Sebbene ciò riduca il TCB rispetto alla verifica del metaprogramma, esso dipende comunque dal fatto che il metaprogramma generi prove valide, il che può fallire o risultare errato. Inoltre, il lavoro esistente si concentra principalmente sulla correttezza (preservazione del comportamento funzionale) piuttosto che sulla sicurezza. Quando il codice estratto viene collegato con codice avversario non verificato, le garanzie formali del programma originale verificato possono essere compromesse, portando a insicurezza o violazioni di sicurezza.

2. Metodologia

Gli autori introducono SEIO★, un framework per estrarre programmi F★ debolmente incorporati con I/O e tipi di raffinamento verso un lambda-calcolo tipizzato semplicemente ( $\lambda_{io}$ ) profondamente incorporato. La metodologia suddivide il processo di estrazione in due fasi distinte per minimizzare il ricorso alla validazione della traduzione:

Fase 1: Quotazione Relazionale (Validazione della Traduzione)
Invece di generare direttamente il codice di destinazione, il framework utilizza un metaprogramma per generare una derivazione di tipo per l'originale programma debolmente incorporato.

Relazione di Tipo Relazionale: Gli autori definiscono una relazione di tipo che caratterizza il sottoinsieme di F★ (chiamato IO★) oggetto dell'estrazione. Questa relazione opera su "valori F★ aperti" (funzioni da ambienti di valutazione a valori) piuttosto che su espressioni sintattiche, permettendole di gestire le variabili libere in un'incorporazione debole.
Metaprogramma: Un semplice metaprogramma attraversa la struttura del programma sorgente e costruisce una corrispondente derivazione di tipo.
Validazione: La derivazione generata viene controllata dal tipo tramite F★. Poiché la relazione di tipo utilizza tipi dipendenti, il controllo dei tipi verifica che la derivazione corrisponda sintatticamente e semanticamente al programma originale. Questo passaggio è l'unica parte che si affida alla validazione della traduzione.

Fase 2: Generazione della Sintassi Verificata
Una volta ottenuta una derivazione di tipo valida, una funzione F★ pura e verificata attraversa ricorsivamente la derivazione per generare la sintassi $\lambda_{io}$ di destinazione.

Poiché la derivazione di tipo è strutturalmente legata al programma sorgente tramite tipi dipendenti, la funzione di generazione della sintassi è garantita produrre codice semanticamente correlato all'originale.
Questo passaggio è interamente verificato all'interno di F★, eliminando la necessità di validazione della traduzione nella fase di generazione del codice.

Garanzie di Sicurezza tramite Relazioni Logiche
Per dimostrare la sicurezza, gli autori definiscono due relazioni logiche cross-linguaggio tra il linguaggio sorgente (IO★) e quello di destinazione ( $\lambda_{io}$ ):

Target-to-Source (Destinazione-a-Sorgente): Relaziona un programma di destinazione con un programma sorgente, garantendo che ogni comportamento di destinazione abbia un corrispondente comportamento sorgente.
Source-to-Target (Sorgente-a-Destinazione): Relaziona un programma sorgente con un programma di destinazione, garantendo che ogni comportamento sorgente abbia un corrispondente comportamento di destinazione.

Queste relazioni sono definite su semantiche che producono tracce (trace-producing semantics), dove le operazioni di I/O generano eventi (tracce). Gli autori dimostrano che SEIO★ soddisfa la Robust Relational Hyperproperty Preservation (RrHP), il più forte criterio di compilazione sicura definito da Abate et al. [1]. La RrHP implica l'astrazione totale (preservazione dell'equivalenza osservazionale) e la preservazione delle proprietà di traccia e delle iperproprietà (ad esempio, la non-interferenza) contro contesti avversari arbitrari.

Gestione dei Tipi di Raffinamento
Il framework è esteso per supportare i tipi di raffinamento (vincoli logici sui tipi). Poiché F★ scarica le prove di raffinamento utilizzando risolutori SMT senza produrre termini di prova espliciti, il metaprogramma di quotazione relazionale deve ricalcolare le precondizioni più deboli (weakest preconditions) da zero durante la quotazione e ri-dimostrarle per garantire che la derivazione di tipo rimanga valida.

3. Contributi Chiave

Quotazione Relazionale: Una nuova tecnica di validazione della traduzione che utilizza tipi dipendenti per definire una relazione di tipo per programmi debolmente incorporati. Permette a un metaprogramma di generare una derivazione di tipo che viene controllata dal tipo per garantire che corrisponda al programma sorgente, evitando la necessità di verificare il metaprogramma stesso.
Framework SEIO★: Un framework di estrazione completo per programmi F★ con I/O e tipi di raffinamento, che estrae verso un lambda-calcolo profondamente incorporato.
Compilazione Sicura Formale: Una prova verificata meccanicamente in F★ che dimostra come SEIO★ soddisfi la RrHP. È il primo framework di estrazione per un linguaggio orientato alle prove a fornire tali forti garanzie di sicurezza contro codice avversario arbitrario collegato.
Relazioni Logiche Cross-Linguaggio: La definizione e la prova di due relazioni logiche asimmetriche che colmano il divario tra un linguaggio debolmente incorporato con semantica che produce tracce e un linguaggio profondamente incorporato con semantica operativa standard.
Supporto ai Tipi di Raffinamento: Un'estensione del framework per gestire i tipi di raffinamento ricalcolando e ri-verificando le precondizioni durante la quotazione.

4. Risultati

Gli autori hanno implementato SEIO★ in F★, includendo oltre 900 definizioni di alto livello.
Hanno estratto con successo un esempio operativo: un wrapper di validazione per agenti IA non verificati che legge un file, chiama un agente e verifica il risultato.
Il framework è stato testato con vari agenti (sia corretti che malevoli) scritti direttamente nel linguaggio $\lambda_{io}$ di destinazione.
La prova verificata meccanicamente conferma che l'estrazione preserva le proprietà di sicurezza anche quando collegata con codice arbitrario non verificato, soddisfacendo la RrHP.
L'artefatto include una pipeline per compilare il codice $\lambda_{io}$ estratto in OCaml utilizzando il framework Peregrine e Malfunction, consentendo l'esecuzione pratica.

5. Significato e Rivendicazioni

Il documento sostiene di far avanzare lo stato dell'arte in due modi chiave:

Minimizzare la Validazione della Traduzione: Confinando la validazione della traduzione alla generazione di una derivazione di tipo (quotazione relazionale) e verificando il successivo passaggio di generazione della sintassi, il framework riduce il ricorso a metaprogrammi non verificati rispetto ai precedenti lavori di estrazione certificata.
Sicurezza sopra la Correttezza: A differenza del lavoro precedente che si concentrava sulla correttezza funzionale, SEIO★ fornisce garanzie di compilazione sicura formale. Assicura che i programmi F★ verificati mantengano le loro proprietà di sicurezza (come la non-interferenza e le proprietà di traccia) anche quando collegati con codice arbitrario, non verificato o avversario.

Gli autori osservano che questo lavoro va oltre lo stato dell'arte attuale, che non ha ancora fornito tali forti garanzie di compilazione sicura per l'estrazione da linguaggi orientati alle prove. Riconoscono limitazioni, come l'attuale mancanza di supporto per funzioni ricorsive generali e tipi dipendenti completi, che sono lasciati come lavoro futuro. Il documento sottolinea che, sebbene il metaprogramma di quotazione relazionale non sia verificato, la sua semplicità e la rigorosa verifica dei passaggi successivi rendono l'approccio complessivo robusto.