💻 computer science

Verifying Exact Samplers for Continuous Distributions with a Discrete Program Logic

Questo articolo introduce Continuous-Eris, una logica di separazione di ordine superiore implementata nell'assistente alla dimostrazione Rocq, per verificare formalmente la correttezza degli algoritmi di campionamento esatto per distribuzioni continue come la Gaussiana e la Laplace, affrontando le limitazioni di sicurezza e accuratezza delle approssimazioni in virgola mobile.

Autori originali: Markus de Medeiros, Puming Liu, Kwing Hei Li, Alejandro Aguirre, Lars Birkedal, Joseph Tassarotti

Pubblicato 2026-05-14

📖 6 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Markus de Medeiros, Puming Liu, Kwing Hei Li, Alejandro Aguirre, Lars Birkedal, Joseph Tassarotti

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

Immagina di voler preparare una torta, ma invece di utilizzare un misurino standard, devi misurare ogni ingrediente versando acqua da un secchio in una tazza minuscola, una goccia alla volta. Se ti fermi dopo 100 gocce, hai un'approssimazione della quantità. Se ti fermi dopo 1.000, è più vicina. Ma se ti fermi in qualsiasi momento, hai tecnicamente commesso un piccolo errore perché non hai ottenuto la quantità esatta.

Nel mondo dell'informatica, è esattamente ciò che accade quando i computer gestiscono numeri reali (come 3,14159...). Utilizzano i "numeri in virgola mobile", che sono come quelle approssimazioni da 100 gocce. Per la maggior parte delle cose, questo va bene. Ma per compiti sensibili—come proteggere dati privati negli studi medici o nei registri finanziari—quei piccoli "errori di arrotondamento" possono sommarsi a grandi perdite di sicurezza.

Questo articolo introduce un nuovo modo per risolvere questo problema. Gli autori hanno costruito uno strumento chiamato Continuous-Eris che aiuta i programmatori a dimostrare che il loro codice esegue un campionamento esatto da distribuzioni continue (come scegliere un numero perfettamente casuale tra 0 e 1) senza mai commettere errori di arrotondamento.

Ecco come hanno fatto, utilizzando alcune analogie creative:

1. Il Problema: Lo Chef "Pigro"

Di solito, per ottenere un numero casuale tra 0 e 1, un computer potrebbe tentare di generare l'intera sequenza infinita di cifre (0,101101...) tutto in una volta. Ma è impossibile; non puoi scrivere un elenco infinito.

Invece, gli autori utilizzano un approccio "pigro". Immagina uno chef che sbuccia una cipolla strato per strato, ma solo quando glielo chiedi.

Il Codice: Il programma U (Uniforme) non genera l'intero numero immediatamente. Crea semplicemente un elenco vuoto.
La Richiesta: Quando chiedi le prime cifre (utilizzando una funzione chiamata GetBits), il programma sbuccia uno strato (genera un bit casuale, 0 o 1).
La Magia: Se chiedi più cifre in seguito, sbuccia un altro strato. Costruisce il numero bit per bit, solo alla velocità con cui ne hai bisogno. Questo garantisce che non devi mai gestire un elenco infinito, ma puoi ottenere una risposta precisa quanto desideri.

2. La Sfida: Dimostrare che lo Chef è Onesto

La parte difficile non è scrivere il codice; è dimostrare che lo chef pigro sta effettivamente scegliendo i numeri in modo equo.

Se lo chef sbuccia uno strato, è davvero casuale?
Se chiedi 10 strati, il numero risultante è davvero distribuito su tutto l'intervallo?
Come lo dimostri quando lo chef non ha nemmeno finito di sbucciare la cipolla?

I precedenti strumenti potevano dimostrare questo solo per cose semplici e discrete (come lanciare un dado). Non potevano gestire la "cipolla infinita" dei numeri continui, specialmente quando il codice era complesso, utilizzava memoria e cambiava valori al volo.

3. La Soluzione: Il "Nastro Infinito" e i "Ricevuti Temporali"

Per risolvere questo problema, gli autori hanno inventato un nuovo sistema logico (un insieme di regole per dimostrare la correttezza del codice) che combina tre trucchi intelligenti:

A. Il "Nastro Pre-disegnato" (Pre-campionamento)

Immagina di essere un mago. Per dimostrare che il tuo trucco funziona, scrivi segretamente l'intera sequenza di carte che prenderai dal mazzo prima ancora di iniziare lo spettacolo.
Nella loro logica, utilizzano un "nastro" che agisce come questo elenco pre-scritto. Anche se il computer genera bit uno alla volta, la prova assume che l'intera sequenza infinita di bit sia già scritta su un nastro magico. Questo permette al matematico di ragionare sull'"intero numero" anche se il programma vede solo "un bit alla volta".

B. Il "Ricevuto Temporale" (Il Budget)

Ecco la parte complicata: un nastro non può essere effettivamente infinito in una prova informatica.
Quindi, utilizzano un concetto chiamato Ricevuti Temporali. Pensa a questo come a un "budget di passi".

La logica dice: "Guarderemo l'esecuzione del programma solo per 100 passi."
Poiché il programma impiega un solo passo per generare un bit, se guardiamo solo per 100 passi, abbiamo bisogno di conoscere solo i primi 100 bit sul nostro nastro magico.
Il "Ricevuto Temporale" è un gettone che dice: "Mi restano 100 passi". Ogni volta che il programma compie un passo, spendi un ricevuto.
Questo permette loro di fingere che il nastro sia infinito, perché in qualsiasi momento specifico della prova, hanno bisogno solo di un numero finito di bit, e hanno un "ricevuto" per pagarli.

C. Il "Credito di Errore" (La Rete di Sicurezza)

Infine, utilizzano i Crediti di Errore. Immagina di avere un budget di "errori" che ti è permesso commettere.

Se vuoi dimostrare che il programma è corretto al 99,9%, spendi lo 0,1% del tuo credito.
Gli autori hanno sviluppato un modo per "spendere" questi crediti per dimostrare che la probabilità che il programma si comporti in modo errato è trascurabile.
Hanno capito come trasformare questi "budget di errori" discreti in uno strumento matematico continuo e fluido (utilizzando integrali) in modo da poter dimostrare che il codice funziona per l'intero intervallo dei numeri reali, non solo per punti specifici.

4. Cosa Hanno Effettivamente Dimostrato

Utilizzando questo nuovo sistema, gli autori non hanno solo parlato di teoria; hanno costruito e verificato codice reale per:

Distribuzione Uniforme: Scegliere un numero casuale tra 0 e 1.
Gaussiana (Curva a Campana): Scegliere un numero che si raggruppa attorno a una media (come le altezze umane).
Distribuzione di Laplace: Un tipo specifico di rumore utilizzato nella Privacy Differenziale (un metodo per condividere dati senza rivelare segreti individuali).

Hanno dimostrato che il loro codice per queste distribuzioni è matematicamente esatto. Se utilizzi il loro codice, non stai ottenendo un numero in virgola mobile "abbastanza vicino"; stai ottenendo un numero che è garantito seguire le regole matematiche perfette, bit per bit.

La Conclusione

L'articolo presenta un nuovo "regolamento" (Continuous-Eris) che permette ai programmatori di scrivere codice complesso, pigro e di campionamento esatto e dimostrare che è corretto al 100%. Lo hanno fatto combinando un "nastro magico pre-scritto" con un sistema di "budget di passi", permettendo loro di ragionare su possibilità infinite utilizzando passi finiti e gestibili. Questo è un grande passo avanti per garantire che gli algoritmi di protezione della privacy e altri sistemi critici non abbiano bug matematici nascosti causati da errori di arrotondamento.

Riepilogo Tecnico: Verifica di Campionatori Esatti per Distribuzioni Continue con una Logica di Programma Discreta

Enunciato del Problema

La maggior parte delle implementazioni di algoritmi di campionamento per distribuzioni di probabilità continue si basa sull'aritmetica in virgola mobile. Sebbene accettabile per molte applicazioni, le operazioni in virgola mobile introducono errori di arrotondamento difficili da analizzare e che possono portare a vulnerabilità critiche per la sicurezza, in particolare nella privacy differenziale, dove gli algoritmi sono spesso sviluppati formalmente sotto l'assunzione di un'aritmetica esatta.

Un'alternativa consiste nell'utilizzare algoritmi di campionamento esatto basati su numeri reali computabili, che possono generare pigramente cifre di un campione continuo con precisione arbitraria. Tuttavia, questi algoritmi sono complessi. Richiedono una combinazione di funzionalità linguistiche semanticamente impegnative, tra cui scelta probabilistica, funzioni di ordine superiore e stato mutabile allocato dinamicamente. Le logiche di programma esistenti per la verifica probabilistica sono insufficienti per questo compito: lavori precedenti o limitano il ragionamento alle distribuzioni discrete o assumono l'esistenza di primitive per il campionamento da distribuzioni continue (spesso basandosi su un'aritmetica reale non computabile). Di conseguenza, manca una tecnica formale per verificare la correttezza di campionatori esatti e computabili per distribuzioni continue che operano all'interno di un modello di programmazione discreto e con stato.

Metodologia

Gli autori presentano Continuous-Eris, una logica di separazione di ordine superiore progettata per verificare la correttezza degli algoritmi di campionamento esatto per distribuzioni computabili. Continuous-Eris estende Eris (una logica per verificare la correttezza approssimata di programmi probabilistici discreti) ed è costruita sul framework della logica di separazione Iris.

La metodologia centrale si basa sul colmare il divario tra il ragionamento discreto e quello continuo attraverso tre ingredienti logici chiave:

Crediti di Errore: Prelevati da Eris, sono risorse della logica di separazione $E(r)$ che rappresentano un limite superiore alla probabilità di fallimento di una specifica. Permettono un ragionamento modulare sui programmi probabilistici "spendendo" crediti per escludere eventi di errore a bassa probabilità.
Ricevuti Temporali: Adattati da Mével et al., sono utilizzati per internalizzare la correttezza parziale della logica. Tracciando il numero di passi di esecuzione rimanenti ($StepsLeft(k)$), la logica può ragionare su prefissi finiti di esecuzioni potenzialmente infinite. Questo è cruciale perché i campionatori esatti spesso coinvolgono una valutazione pigra in cui una sequenza infinita di bit non viene mai generata completamente.
Nastri di Pre-campionamento: Adattati da Clutch, permettono alla dimostrazione di pre-determinare gli esiti di futuri comandi di campionamento casuale. Mentre i nastri standard sono finiti, gli autori li combinano con i ricevuti temporali per simulare nastri di pre-campionamento infiniti. Questo meccanismo permette alla logica di condizionare i crediti di errore su un numero reale specifico $r$ (rappresentato da una stringa infinita di bit), anche se il programma genera solo un numero finito di bit durante qualsiasi esecuzione finita.

Fondamento Teorico

La logica generalizza la specifica di correttezza discreta di Marionneau et al. al contesto continuo. Invece di caratterizzare un campionatore tramite una funzione di massa di probabilità discreta, Continuous-Eris caratterizza un campionatore tramite un integrale di Riemann su una funzione di densità di probabilità.

Il pattern di specifica centrale per un campionatore $U$ che genera un reale uniforme in $[0, 1]$ è:
$\forall F \in PC([0, 1]), \quad \left\{ E\left(\int_0^1 F(x) dx\right) \right\} U() \{ v. \exists r. E(F(r)) * IsReal\ v\ r \}$
Qui, $F$ è una funzione limitata e a tratti continua. La logica permette di condizionare i crediti sul valore campionato $r$ come se fosse estratto uniformemente, a condizione che il valore atteso dei crediti sia preservato. La correttezza di questo approccio si basa sul fatto che una somma di Riemann (derivata dal pre-campionamento finito) può approssimare l'integrale arbitrariamente da vicino, con l'errore di discretizzazione pagato tramite crediti di errore "dal nulla".

Contributi Chiave

Logica Continuous-Eris: Una nuova logica di programma che combina crediti di errore, ricevuti temporali e nastri di pre-campionamento per verificare algoritmi di campionamento continuo computabili. Supporta funzioni di ordine superiore, stato mutabile e allocazione dinamica.
Verifica Formale di Campionatori Esatti: Gli autori forniscono implementazioni formalmente verificate di campionatori esatti per:
- La distribuzione Uniforme su $[0, 1]$ .
- La distribuzione Gaussiana (Normale).
- La distribuzione Laplace.
  Queste implementazioni si basano sugli algoritmi di Karney e utilizzano rappresentazioni pigre di liste di bit.
Aritmetica Costruttiva dei Reali Verificata: Una libreria per l'aritmetica reale esatta (un adattamento di CReal) verificata all'interno di Continuous-Eris. Questa libreria supporta operazioni (addizione, negazione, scalatura, confronto) su numeri reali pigri, permettendo la costruzione di distribuzioni complesse a partire da quelle più semplici.
Limite di Accuratezza per la Privacy Differenziale: Una dimostrazione formale che il campionatore Laplace verificato soddisfa un limite di accuratezza specifico utilizzato nella letteratura sulla privacy differenziale. Ciò dimostra che l'output del campionatore aderisce alle garanzie teoriche richieste per i meccanismi di preservazione della privacy senza fare affidamento su approssimazioni in virgola mobile.
Meccanizzazione: Tutti i risultati sono meccanizzati nell'assistente di dimostrazione Rocq (precedentemente Coq), basandosi sul framework Iris e sulla libreria di analisi reale Coquelicot.

Risultati

Il documento dimostra l'utilità di Continuous-Eris attraverso la verifica del programma MaxU2 (che calcola il massimo di due campioni uniformi) e del completo campionatore Gaussiano di Karney.

MaxU2: Gli autori dimostrano che il programma restituisce un valore distribuito con densità di probabilità $\mu_{max}(x) = 2x$ . La dimostrazione coinvolge integrali iterati e induzione di Löb per gestire i confronti ricorsivi di bit.
Campionatore Gaussiano: La verifica segue una struttura modulare, verificando sottoprogrammi per prove di Bernoulli, parti intere e cicli di campionamento per rifiuto. La dimostrazione stabilisce che il campionatore genera valori con la corretta densità gaussiana.
Campionatore Laplace: Gli autori verificano un campionatore per la distribuzione Laplace e derivano il limite della coda $P[|L_{\epsilon, \mu} - \mu| > \frac{\log(1/\beta)}{\epsilon}] \leq \beta$ direttamente dalla logica, senza aggiungerlo come un assioma primitivo.

Significato e Affermazioni

Il documento afferma di colmare una lacuna critica nella verifica formale fornendo la prima tecnica capace di verificare campionatori esatti e computabili per distribuzioni continue che utilizzano stato mutabile e funzioni di ordine superiore.

Correttezza senza Approssimazione: A differenza di lavori precedenti che assumono primitive continue o utilizzano aritmetica in virgola mobile, Continuous-Eris verifica algoritmi che generano campioni esatti (con precisione arbitraria) utilizzando esclusivamente primitive discrete (prove di Bernoulli).
Gestione della Complessità: La logica gestisce con successo le sfide semantiche della combinazione di casualità, stato mutabile e funzioni di ordine superiore, che sono tipicamente difficili da ragionare denotazionalmente.
Rilevanza Pratica: Verificando il campionatore Laplace e i suoi limiti di accuratezza, il lavoro fornisce una base per costruire sistemi con privacy differenziale con garanzie rigorose contro gli errori in virgola mobile.
Modestia: Gli autori riconoscono i limiti. L'approccio attuale si basa sull'integrazione di Riemann, richiedendo che le funzioni di distribuzione dei crediti siano a tratti continue. Ciò impedisce il ragionamento su distribuzioni con discontinuità non numerabili (ad esempio, evitando tutti i punti razionali). Inoltre, il documento si concentra sulla correttezza parziale; dimostrare la terminazione quasi certa per questi campionatori è lasciato a lavori futuri o ad altre logiche come Total Eris.

In sintesi, Continuous-Eris offre un framework rigoroso e meccanizzato per verificare che programmi complessi e con stato implementino correttamente il campionamento esatto da distribuzioni continue, colmando il divario tra l'analisi computabile teorica e la verifica pratica dei programmi.