💻 computer science

Octopus: Practical Equivalence Checking of P4 Packet Parsers

Questo articolo presenta Octopus, uno strumento che traduce i parser di pacchetti P4 in automi per verificarne efficientemente l'equivalenza su hardware consumer, fornendo una prova di bisimulazione o un bit-stream di controesempio.

Autori originali: Jort van Leenen, Tobias Kappé

Pubblicato 2026-08-04

📖 4 min di lettura☕ Lettura da pausa caffè

CC BY 4.0

Autori originali: Jort van Leenen, Tobias Kappé

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

Immaginate Internet come una città enorme e frenetica dove i dati viaggiano in minuscole buste sigillate chiamate "pacchetti". Ogni volta che inviate un messaggio o trasmettete un video, questi pacchetti sfrecciano attraverso router e switch, che agiscono come vigili urbani velocissimi. Il loro compito è leggere l'indirizzo sulla busta (l'intestazione o header) e decidere dove inviarla successivamente. Ma prima di poter leggere l'indirizzo, devono sapere come è costruita la busta. L'indirizzo è proprio in cima? C'è un codice segreto all'interno? Questo compito di prendere un flusso grezzo di 1 e 0 e capire che "Ok, questi primi 16 bit sono la porta, e i successivi 16 sono la destinazione" è svolto da un packet parser.

Pensate al parser come a uno chef robotico molto severo e che segue rigorosamente le regole. Prende una lunga pagnotta di pane non tagliata (i dati in entrata) e la affetta in ingredienti specifici (intestazioni e campi) basandosi su una ricetta. Se il robot commette un errore — ad esempio, taglia la crosta dalla parte sbagliata o legge male la ricetta — l'intero pasto viene rovinato. Nel mondo digitale, un bad parser può portare a falle di sicurezza dove gli hacker si intrufolano, o semplicemente far crashare la rete. Poiché questi robot sono così importanti, gli ingegneri vogliono assicurarsi che siano perfetti. Ma verificare se due diverse ricette (o due versioni del codice del robot) facciano esattamente la stessa cosa è incredibilmente difficile. È come cercare di dimostrare che due chef diversi taglieranno una pagnotta esattamente nello stesso modo per ogni possibile pagnotta dell'universo, senza doverli effettivamente cuocere tutti.

È qui che entra in gioco un nuovo strumento chiamato Octopus. Creato dai ricercatori dell'Università di Leiden, Octopus è un software intelligente progettato per controllare se due packet parser sono "gemelli", ovvero se si comportano esattamente allo stesso modo, anche se il loro codice appare diverso all'interno. Prima di Octopus, esisteva uno strumento chiamato Leapfrog che poteva farlo, ma era come cercare di risolvere un enorme puzzle usando un supercomputer che richiedeva più memoria della rete elettrica di una piccola città; spesso impiegava giorni e andava in crash. Octopus, invece, è il cugino agile. Utilizza una strategia diversa per risolvere lo stesso puzzle, riuscendo a completare controlli complessi in pochi minuti su un normale laptop.

Il documento presenta Octopus come una soluzione pratica a un problema che prima era troppo pesante per i computer di uso comune. I ricercatori hanno costruito Octopus per tradurre il codice P4 (il linguaggio usato per programmare questi parser di rete) in una mappa di stati possibili, trasformando essenzialmente il codice in un diagramma di flusso. Successivamente, utilizza un trucco matematico chiamato "bisimulazione simbolica" per percorrere i diagrammi di flusso di entrambi i parser contemporaneamente. Inveve di testare ogni singolo pezzo di dato possibile (il che è impossibile), testa gruppi di dati alla volta utilizzando formule logiche.

I risultati sono impressionanti. Quando il team ha testato Octopus rispetto al vecchio strumento, Leapfrog, Octopus è stato drasticamente più veloce e ha utilizzato una frazione minima della memoria. Per esempio, su un caso di test difficile che aveva fatto esaurire la memoria a Leapfrog facendolo fallire, Octopus lo ha risolto in meno di 12 minuti. Su una collezione di codice di rete reale trovata online, Octopus ha controllato centinaia di coppie di parser in pochi secondi, finendo spesso in meno di un secondo per coppia. Lo strumento non si limita a dire "corrispondono" o "non corrispondono"; fornisce una prova. Se corrispondono, fornisce un "certificato" (una mappa matematica che mostra perché sono gemelli). Se non corrispondono, produce un "controesempio": un dato specifico che un parser accetta ma l'altro rifiuta, agendo come una pistola fumante per permettere agli ingegneri di correggere l'errore.

I ricercatori sottolineano con cautela che, sebbene Octopus sia molto più veloce e pratico del suo predecessore, non offre la stessa garanzia matematica incrollabile che l'altro strumento offriva (che era costruito all'interno di un sistema di prova formale). Inveve, Octopus si affida a risolutori logici standard per svolgere il lavoro pesante. Tuttavia, il team ha verificato che i risultati di Octopus siano affidabili, facendolo generare certificati che possono essere controllati indipendentemente. Hanno anche testato lo strumento su parser sintetici e creati artificialmente che erano incredibilmente complessi, e Octopus li ha gestiti senza battere ciglio.

In breve, il documento dimostra che Octopus rende possibile verificare rigorosamente i parser di rete su hardware normale, trasformando un compito che prima richiedeva un supercomputer in qualcosa che può essere fatto nel tempo necessario per preparare una tazza di caffè. Non risolve ogni possibile problema (non può ancora gestire determinati tipi di stack di dati complessi e annidati), ma per la stragrande maggioranza del codice di rete reale, dimostra che il controllo dell'equivalenza è ora pratico, veloce e affidabile.

Riassunto Tecnico: Octopus – Verifica dell'Equivalenza Pratica dei Parser di Pacchetti P4

Definizione del Problema

I parser di pacchetti sono componenti critici nei commutatori (switch) e router di rete, responsabili della strutturazione di flussi di bit in entrata in intestazioni (header) e campi di protocollo. Gli errori nei parser possono portare a comportamenti di inoltro errati o a gravi vulnerabilità di sicurezza, come la famiglia di exploit Ripple20. Sebbene il P4 sia un linguaggio specifico per il dominio progettato per mitigare i problemi di gestione della memoria tipici dei linguaggi general-purpose come il C, i programmi P4 possono comunque contenere errori logici, specialmente durante le fasi di ottimizzazione o refactoring.

Gli strumenti esistenti per la verifica della correttezza dei parser affrontano spesso limiti di scalabilità. Nello specifico, Leapfrog, un precedente verificatore di equivalenza implementato nel sistema di prova Rocq, costruisce bisimulazioni simboliche per dimostrare l'equivalenza. Tuttavia, la dipendenza di Leapfrog da Ltac (il linguaggio di tattiche di Rocq) per costruire oggetti di prova nel Calculus of Inductive Constructions comporta un consumo di risorse proibitivo. Ad esempio, un singolo benchmark ha richiesto oltre 400 GiB di memoria e quasi un giorno di runtime, rendendolo impraticabile per molti scenari reali.

Metodologia

Gli autori presentano Octopus, uno strumento progettato per eseguire la verifica dell'equivalenza pratica dei parser di pacchetti P4. Octopus traduce i parser P4 in automi a stati finiti deterministici (DFA) e tenta di costruire una bisimulazione simbolica tra due parser.

Componenti Core

Modello di Automa:
- I parser P4 sono modellati come macchine a stati in cui gli stati corrispondono agli stati P4, e le transizioni dipendono dai bit di input e dallo "store" corrente (campi di intestazione e metadati).
- Una configurazione è definita come una terna $\langle q, s, w \rangle$ , che rappresenta lo stato corrente $q$ , lo store $s$ e un buffer $w$ di bit non letti.
- Il modello gestisce l'estrazione dei bit nelle intestazioni e l'esecuzione di assegnazioni (ad esempio, scambi di endianness) all'interno dei blocchi di operazione.
Bisimulazione Simbolica tramite TGF:
- Invece di esplorare configurazioni concrete (che sono esponenzialmente grandi), Octopus utilizza le Template-Guarded Formulas (TGF) per rappresentare simbolicamente insiemi di coppie di configurazioni.
- Una TGF $\gamma = \langle q_<, q_>, n_<, n_>, \phi_\gamma \rangle$ traccia gli stati di due parser, il numero di bit nei rispettivi buffer e una formula del primo ordine $\phi_\gamma$ che descrive i vincoli sui buffer e sugli store.
- L'algoritmo (Algoritmo 1) calcola iterativamente le TGF successive. Utilizza un risolutore SMT (predefinito Z3) per verificare se nuove coppie raggiungibili siano già coperte dalle TGF esistenti o se portino a una contraddizione (ad esempio, un parser accetta mentre l'altro rifiuta).
Costruzione Forward e Ottimizzazione:
- A differenza di Leapfrog, che lavora all'indietro utilizzando le condizioni di pre-condizione più deboli (weakest preconditions), Octopus costruisce la bisimulazione in avanti utilizzando le condizioni di post-condizione più forti (strongest postconditions - SP). Ciò elimina la necessità di alcuni passaggi di pre-elaborazione richiesti da Leapfrog.
- Lo strumento impiega una tecnica di "leaps" (salti) per far avanzare entrambi i parser simultaneamente fino all'esecuzione di un blocco di operazione, anziché elaborare bit per bit, riducendo significativamente il numero di passi.
Input e Output:
- Octopus si integra direttamente con P4C (il compilatore di riferimento P4), accettando codice sorgente P4 o la rappresentazione intermedia (IR) in formato JSON. Ciò elimina la necessità di una traduzione manuale in una rappresentazione interna profondamente incorporata.
- Equivalenza: Se i parser sono equivalenti, Octopus restituisce un certificato costituito da un insieme di TGF che formano una bisimulazione simbolica.
- Inequivalenza: Se i parser differiscono, genera un bit-stream di controesempio (un pacchetto accettato da uno ma rifiutato dall'altro) e i percorsi di esecuzione seguiti.

Contributi Chiave

Prestazioni Pratiche: Octopus raggiunge la verifica dell'equivalenza su hardware consumer in pochi minuti, mentre Leapfrog spesso fallisce a causa dell'esaurimento della memoria o di un tempo di esecuzione eccessivo.
Supporto Diretto P4: Collegandosi a P4C, Octopus accetta parser P4 standard senza richiedere la traduzione manuale in un formato interno specializzato.
Generazione di Certificati: Lo strumento produce prove verificabili per i propri verdetti. Per l'equivalenza, fornisce una bisimulazione simbolica; per l'inequivalenza, fornisce un controesempio concreto.
Scalabilità: Lo strumento gestisce con successo benchmark che hanno superato i limiti di memoria degli strumenti precedenti.

Risultati Sperimentali

Gli autori hanno valutato Octopus utilizzando la suite di benchmark di Leapfrog, benchmark sintetici generati da Whippersnapper e una collezione di codice P4 pubblico.

Confronto con Leapfrog:
- Sulla suite di benchmark di Leapfrog, Octopus ha superato Leapfrog di diversi ordini di grandezza sia in termini di runtime che di utilizzo della memoria.
- Per il benchmark "Variable-length format 3", Leapfrog non è riuscito a terminare (superando 1,4 TiB di memoria), mentre Octopus ha completato la verifica in circa 23 minuti (12,1 min di generazione + 10,9 min di validazione) utilizzando solo 0,252 GiB di memoria.
- In tutti i benchmark in cui Leapfrog è terminato, Octopus ha dimostrato un footprint di memoria significativamente inferiore (tipicamente < 0,1 GiB rispetto a centinaia di GiB).
Benchmark Sintetici:
- Utilizzando Whippersnapper, gli autori hanno testato la scalabilità rispetto al numero crescente di campi, intestazioni e profondità del parser.
- Il runtime è stato ampiamente insensibile al numero di campi (gestiti efficientemente dai "leaps"), ma è aumentato con il numero di intestazioni e la profondità dell'albero del parser a causa della crescita dei percorsi di esecuzione e della dimensione delle formule.
- Lo strumento ha verificato con successo equivalenze tra parser strutturalmente diversi (ad esempio, un parser con $n$ intestazioni a campo singolo rispetto a uno con un'unica intestazione di $n$ campi) in pochi secondi.
Codice Reale:
- Valutato su 34 programmi P4 pubblici (30 entro lo scope), Octopus ha eseguito 435 controlli di equivalenza a coppie su un laptop consumer (Intel Core i5, 24 GiB di RAM).
- Il tempo medio di esecuzione è stato di 0,659 secondi per controllo, con un picco di memoria media di 51,72 MiB.
- Lo strumento ha identificato con successo classi di equivalenza non banali tra parser che differivano sintatticamente ma si comportavano in modo identico riguardo a specifiche decodifiche di protocollo (ad esempio, IPv4 vs IPv4+TCP).

Significato e Assertions

Il documento afferma che Octopus abilita la verifica dell'equivalenza pratica dei parser di pacchetti P4, un compito precedentemente limitato dai vincoli di risorse degli strumenti di verifica formale come Leapfrog.

Fiducia vs Prestazioni: Sebbene Octopus non fornisca le garanzie fondamentali di un oggetto di prova nel Calculus of Inductive Constructions (come fa Leapfrog), genera certificati che possono essere validati indipendentemente. Gli autori sostengono che questo compromesso sia giustificato dalla capacità di eseguire controlli complessi su hardware standard in pochi minuti.
Verifica Relazionale: Lo strumento si concentra sulla verifica relazionale (confronto tra due parser) piuttosto che sulla verifica della correttezza funzionale di un singolo parser rispetto a una specifica.
Limitazioni: L'attuale ambito è limitato a parser in cui ogni stato consuma almeno un bit, non viene utilizzato il lookahead e non compaiono stack di intestazioni. Gli autori notano che gli stack di intestazioni illimitati rendono l'equivalenza indecidibile, ma gli stack di dimensione fissa potrebbero potenzialmente essere supportati.
Lavoro Futuro: Gli autori identificano la validazione dei certificati come un collo di bottiglia delle prestazioni (che raddoppia il tempo di esecuzione) e propongono l'incorporazione dei certificati per le query SMT per ridurre l'overhead. Mirano inoltre ad estendere il supporto per il lookahead e la rilevazione della terminazione.

In sintesi, Octopus rappresenta un passaggio dalla verifica formalmente rigorosa ma praticamente impraticabile a uno strumento che bilancia i metodi formali con i requisimenti di prestazione dell'ingegneria di rete moderna.