Consideriamo due programmi che superano entrambi tutti i test che scriviamo. Uno è corretto. L'altro presenta un errore di divisione per zero che si verifica solo quando una specifica combinazione di input arriva simultaneamente, una combinazione che i nostri test non producono mai. I test tradizionali non possono dirci quale sia quale. L'interpretazione astratta, invece, sì.
L'interpretazione astratta è il quadro matematico che conferisce agli strumenti di analisi statica la capacità di ragionare su tutti i possibili comportamenti di un programma senza eseguirlo. È la tecnica alla base di Infer di Facebook, che individua bug di puntatore nullo su larga scala, dell'analizzatore Astrée, che verifica formalmente il software di controllo di volo di Airbus, e di ogni analizzatore statico che dichiara la correttezza del programma, ovvero la garanzia che se un programma supera l'analisi, è effettivamente privo della classe di errori verificata. Capire come funziona spiega perché alcuni strumenti individuano bug che altri non rilevano e perché tali garanzie comportano specifici compromessi.
Analizzare il codice senza eseguirlo
SMART TS XL Applica l'analisi statica strutturale a tutti i linguaggi del tuo portfolio simultaneamente.
Maggiori InformazioniChe cos'è l'interpretazione astratta?
L'interpretazione astratta è una teoria di approssimazione dei programmi, sviluppata da Patrick Cousot e Radhia Cousot nel 1977. L'idea centrale è la seguente: invece di calcolare l'insieme esatto di tutti i possibili stati del programma, operazione generalmente indecidibile, si calcola una sovra-approssimazione sicura utilizzando un dominio matematico semplificato e trattabile per l'analisi.
La parola "astratto" qui non significa vago o concettuale. Si riferisce a una specifica operazione matematica: astrarre un insieme di valori concreti in una rappresentazione più semplice che conserva le proprietà che ti interessano, scartando i dettagli non necessari. Un valore intero concreto come 42 In un'astrazione basata sull'analisi dei segni, diventa semplicemente "positivo". L'astrazione perde informazioni (non si conosce più il valore esatto) ma guadagna in gestibilità (il segno di qualsiasi numero intero è una di tre possibilità: positivo, negativo o zero).
Ciò che rende questo approccio utile per l'analisi dei programmi è la garanzia che ne deriva: se l'analisi non rileva errori nel dominio astratto, non esistono errori in nessuna esecuzione concreta. Se rileva un potenziale errore, questo potrebbe verificarsi o meno nella pratica, ma nessun errore reale può essere nascosto. Questa è la correttezza.
Interpretazione astratta vs. analisi AST vs. analisi dinamica
Questi termini vengono spesso confusi, "analisi del codice AST" compare nei risultati di ricerca per questo articolo, e descrivono cose diverse.
Un albero sintattico astratto (AST) è una struttura dati che rappresenta la struttura grammaticale del codice sorgente. Ogni compilatore e linter ne crea uno. È alla base degli strumenti di parsing, refactoring e analisi statica basata su pattern. L'analisi basata su AST individua i pattern: il codice che corrisponde a una regola (una funzione con troppi parametri, una stringa SQL costruita tramite concatenazione) viene segnalato. Non effettua analisi sui valori o sul comportamento a runtime.
L'interpretazione astratta ragiona sul comportamento a runtime senza eseguire il programma. Utilizza l'AST come input, ma va ben oltre: modella il flusso dei valori all'interno del programma, gli intervalli di valori che le variabili possono assumere, se un puntatore potrebbe essere nullo in un punto specifico della chiamata, se un ciclo termina. L'analisi dell'AST è un'analisi di pattern matching. L'interpretazione astratta è un ragionamento comportamentale.
La maggior parte dei linter (ESLint, Checkstyle, Pylint) si basa principalmente sull'AST (Abstract Syntax Tree). La maggior parte degli strumenti di verifica formale (Infer, Astrée, Polyspace) utilizza l'interpretazione astratta. L'analisi dinamica (esecuzione del programma e osservazione del comportamento effettivo) individua solo i bug attivati da input specifici. L'interpretazione astratta individua i bug per tutti i possibili input senza eseguire affatto il programma.
I principi matematici alla base dell'analisi statica
La domanda "quali sono i principi matematici alla base degli strumenti di analisi statica" compare direttamente nei risultati di ricerca. Ecco la risposta in poche parole.
L'interpretazione astratta si basa su tre strutture matematiche:
Reticoli. Un reticolo è un insieme parzialmente ordinato in cui ogni coppia di elementi ha un estremo superiore (unione) e un estremo inferiore (incontro). Nell'analisi statica, il reticolo rappresenta il dominio astratto, l'insieme dei possibili valori astratti, ordinati in base alla quantità di informazione che trasportano. Per l'analisi dei segni, il reticolo si presenta in questo modo:
⊤ (unknown -- could be anything)
/ \
pos neg
\ /
0
|
⊥ (unreachable -- no possible value)Spostandosi verso l'alto nel reticolo si perde precisione (si sa di meno). Spostandosi verso il basso si guadagna precisione (si sa di più). L'elemento superiore ⊤ significa "non sappiamo nulla di utile". L'elemento inferiore ⊥ significa "questo stato è irraggiungibile".
Connessioni di Galois. Una connessione di Galois è la relazione formale tra il dominio concreto (i valori effettivi del programma) e il dominio astratto (la rappresentazione semplificata). Essa è composta da due funzioni: una funzione di astrazione α che mappa i valori concreti alla loro rappresentazione astratta e una funzione di concretizzazione γ che mappa i valori astratti all'insieme dei valori concreti che rappresentano.
La proprietà critica: il dominio astratto deve essere una sovra-approssimazione sicura. γ(α(S)) ⊇ S per ogni insieme concreto S. L'astrazione può includere più valori di quelli che effettivamente si verificano, ed è questo che produce falsi positivi, ma non deve mai escludere valori che si verificano realmente. Escludere valori reali significherebbe non individuare bug reali.
Iterazione a punto fisso. Per i programmi con cicli, l'analisi deve iterare fino al raggiungimento di uno stato stabile. Per un ciclo come:
c
int x = 0;
while (condition) {
x = x + 1;
}Nella prima iterazione, x is {0}. Dopo un corpo del ciclo, x potrebbe essere {0, 1}. Dopo due, {0, 1, 2}Questo insieme continua a crescere, non si stabilizza mai da solo. La soluzione è allargamento: un operatore che forza la convergenza saltando a un'approssimazione più ampia (tipicamente [0, +∞) per l'analisi degli intervalli). L'analisi utilizza quindi strozzatura per recuperare una certa precisione.
Questo calcolo a virgola fissa è ciò che rende completa l'interpretazione astratta lungo tutti i percorsi di esecuzione, inclusi i cicli, e ciò che la rende computazionalmente più onerosa rispetto alla semplice corrispondenza di pattern.
Domini astratti: scegliere cosa approssimare
Il dominio astratto determina cosa l'analisi può e non può trovare. Domini diversi rispondono a domande diverse sul comportamento del programma.
| Dominio astratto | Cosa tiene traccia | Esempio di utilizzo | Cosa manca |
|---|---|---|---|
| Analisi dei segni | Sia che i valori siano positivi, negativi o nulli | Divisione per rilevamento dello zero | Valori esatti, condizioni di overflow |
| Analisi degli intervalli | Limiti superiori e inferiori dei valori numerici | Overflow del buffer, sicurezza di accesso agli array | Relazioni tra variabili |
| Dominio ottagonale | Relazioni lineari tra coppie di variabili | Rilevamento del sovraccarico più preciso | Relazioni non lineari |
| Analisi del puntatore | Se i puntatori possono essere nulli o aliasarsi a vicenda | Dereferenziazione nulla, use-after-free | Durata di vita dell'oggetto, forma dell'hedge |
| Analisi della contaminazione | Se i valori provengono da fonti inaffidabili | Iniezione SQL, rilevamento XSS | Flussi impliciti attraverso il controllo |
| Dominio poliedrico | Vincoli aritmetici lineari arbitrari | verifica limitata al ciclo | Il costo delle prestazioni aumenta esponenzialmente |
Il compromesso tra i diversi domini è sempre tra precisione e prestazioni. Il dominio degli intervalli è veloce e individua la maggior parte degli errori numerici. Il dominio poliedrico è molto più preciso, ma presenta una complessità esponenziale in termini di numero di variabili. Gli strumenti pratici di analisi statica scelgono domini che bilanciano il compromesso in base all'applicazione di destinazione: i sistemi embedded critici per la sicurezza possono permettersi analisi più lente ma più precise; i linter integrati nei processi CI/CD devono terminare in pochi secondi.
Come tre strumenti reali utilizzano l'interpretazione astratta
Anziché descrivere la teoria in modo isolato, gli strumenti concreti ne chiariscono l'applicazione.
Facebook Infer utilizza una forma di interpretazione astratta chiamata bi-abduzione per analizzare Java, C, C++ e Objective-C alla ricerca di dereferenziazioni di puntatori nulli, perdite di risorse e condizioni di gara. La bi-abduzione scopre automaticamente precondizioni e postcondizioni per le funzioni, consentendo l'analisi interprocedurale senza richiedere specifiche manuali. Infer viene eseguito nei sistemi di integrazione continua (CI) di Facebook, Spotify, Mozilla e decine di altre grandi organizzazioni perché è scalabile a codebase di milioni di righe, mantenendo al contempo la correttezza per le classi di errori che verifica.
Astrée utilizza l'interpretazione astratta con domini astratti numerici per dimostrare l'assenza di errori di runtime nei programmi C. È stato utilizzato da Airbus per verificare formalmente il software di controllo di volo primario dell'A380, dimostrando l'assenza di errori di runtime nell'intero sistema di controllo, una garanzia che nessun programma di test era in grado di fornire. Astrée non rileva falsi negativi per le classi di errori che controlla, sebbene possa produrre falsi positivi che richiedono una revisione manuale.
Polyspace (MathWorks) applica un'interpretazione astratta al codice C e C++ incorporato in applicazioni critiche per la sicurezza. Classifica ogni operazione come "verde" (nessun errore dimostrabile), "rossa" (sicuramente un errore) o "arancione" (potenziale errore che richiede una revisione). La classificazione verde è una prova formale: nessuna esecuzione può causare un errore di runtime in quell'operazione.
Il triangolo solidità-precisione-prestazioni
Gli strumenti di interpretazione astratta si muovono all'interno di un triangolo fondamentale di proprietà in competizione tra loro. Nessuno strumento è in grado di massimizzare simultaneamente tutte e tre.
La solidità di uno strumento significa assenza di falsi negativi: ogni bug reale presente nella classe analizzata viene rilevato. Gli strumenti affidabili offrono garanzie; quelli non affidabili possono non individuare i bug.
La precisione implica un numero ridotto di falsi positivi: i risultati corrispondono a problemi reali, non a problemi teorici impossibili. Un'elevata precisione richiede ambiti astratti più raffinati e un'analisi interprocedurale più accurata.
Per "prestazioni" si intende la velocità di esecuzione dell'analisi, che si completa in tempi utili. Un'analisi più precisa è più costosa. Dimostrare l'assenza di tutti gli errori di runtime in una codebase di un milione di righe richiede ore; una scansione con un linter richiede pochi secondi.
Applicazioni diverse richiedono punti diversi in questo triangolo:
- Linting IDE e CI/CD: prima le prestazioni, poi la precisione, poi la solidità
- Scansione di sicurezza: la precisione prima di tutto (ridurre l'affaticamento da avvisi degli sviluppatori), la solidità è importante per le classi ad alta gravità
- Certificazione di importanza critica per la sicurezza: la solidità prima di tutto (non si possono trascurare i bug reali), le prestazioni secondarie, i falsi positivi sono accettabili con un processo di revisione manuale
Interpretazione astratta nello sviluppo di sistemi embedded e critici per la sicurezza
La domanda "vantaggi dell'analisi statica nello sviluppo di sistemi embedded" mette in luce uno dei campi di applicazione più importanti dell'interpretazione astratta. I sistemi embedded, le centraline di controllo per autoveicoli, il firmware per dispositivi medici, il software di controllo del volo aerospaziale, presentano vincoli che rendono l'interpretazione astratta particolarmente preziosa:
Non esiste un sistema di test per tutti gli stati. Una centralina elettronica (ECU) automobilistica risponde a migliaia di combinazioni di sensori in tempo reale. Creare test per ogni singola combinazione è impossibile. L'interpretazione astratta copre tutti gli stati simultaneamente.
Requisiti di certificazione. Gli standard DO-178C (aerospaziale), ISO 26262 (automotive) e IEC 62443 (controllo industriale) richiedono la dimostrazione del corretto funzionamento del software in tutte le condizioni. La verifica formale tramite interpretazione astratta può soddisfare questo requisito in un modo che i report di copertura dei test non sono in grado di fare.
Vincoli di risorse. Il software embedded spesso non dispone di un allocatore di memoria, di una gestione delle eccezioni e di un meccanismo di fallback del sistema operativo. Un errore di runtime, un dereferenziamento di un puntatore nullo, un array fuori dai limiti, rappresentano un grave guasto di sistema. Il costo di non rilevare questi bug non si limita a una segnalazione di arresto anomalo e a una patch correttiva. Si tratta di un incidente di sicurezza.
Gli analizzatori Astrée e Polyspace sono stati creati appositamente per questo contesto. La loro progettazione accetta elevati tassi di falsi positivi e tempi di analisi lenti in cambio della garanzia che nessun falso negativo sfugga al controllo.
I falsi positivi e il problema dell'allargamento
La critica più comune agli strumenti di interpretazione astratta riguarda i falsi positivi, ovvero gli avvisi relativi a potenziali errori che in realtà non possono verificarsi durante l'esecuzione reale. Comprendere perché i falsi positivi sono una caratteristica intrinseca del sistema e non un difetto di qualità, ne facilita la gestione.
I falsi positivi derivano da due fonti:
Sovra-approssimazione nel dominio astratto. Se il dominio dell'intervallo traccia x ∈ [0, 100], non può distinguere tra i casi in cui x è sempre inferiore a 50 nella pratica. Una divisione per x potrebbe essere segnalato come potenzialmente divisore per zero anche quando la logica del programma garantisce x > 0. Un dominio più preciso (che tiene traccia del valore esatto o di un vincolo che collega x (ad un'altra variabile) eliminerebbe il falso positivo, ma a un costo computazionale maggiore.
Allargamento. L'operatore di convergenza che rende trattabile l'analisi dei cicli perde necessariamente informazioni. Dopo l'allargamento x da [0, 5] a [0, +∞), l'analizzatore non sa più che x rimane limitato. Se il codice controlla assert(x < 1000) dopo il ciclo, questa affermazione non può più essere dimostrata, anche se in pratica x rimane sempre ben al di sotto di 1000.
Strategie pratiche per la gestione dei falsi positivi: configurare l'analisi in modo da utilizzare domini più precisi per i moduli critici (accettando un'analisi più lenta), sopprimere i falsi positivi confermati con annotazioni mirate e trattare i risultati arancioni/sconosciuti dello strumento come una coda di revisione prioritaria piuttosto che come bug confermati.
Come SMART TS XL Applica l'analisi statica su scala aziendale
SMART TS XL Opera nello spazio in cui la teoria astratta dell'interpretazione incontra la realtà aziendale: codebase che abbracciano più linguaggi, decenni di sviluppo e confini organizzativi che rendono impraticabile la verifica formale per ogni programma.
Invece di applicare un unico dominio astratto a tutti i programmi, SMART TS XL'S analisi statica del codice Integra tecniche di analisi strutturale appropriate a ciascun linguaggio presente nell'ambiente (COBOL, JCL, Java, Python, RPG, PL/I, SQL e stack moderni), producendo simultaneamente metriche di qualità, dati sulle dipendenze e risultati di sicurezza per l'intero portfolio.
La funzionalità di mappatura delle dipendenze tra applicazioni applica l'analisi basata sulla teoria dei grafi al grafo delle chiamate tra linguaggi diversi, identificando come programmi, set di dati e flussi di lavoro si connettono al di là dei confini linguistici: un'analisi dell'intero sistema che gli strumenti per un singolo linguaggio non sono in grado di eseguire. Si tratta di un ragionamento strutturale a livello di sistema: non si tratta di dimostrare le proprietà dei singoli programmi, ma le proprietà di come questi si connettono.
La funzionalità di analisi d'impatto applica l'analisi di raggiungibilità al grafo delle dipendenze: data una modifica proposta in un nodo, calcola l'insieme di tutti i nodi raggiungibili da esso. Questa è la domanda di analisi statica "cosa verrà influenzato?" a cui si risponde a partire dalla struttura del codice piuttosto che dall'osservazione in fase di esecuzione o dalla stima umana.
Per i team che conducono modernizzazione dell'eredità programmi, SMART TS XLL'analisi strutturale di colma il divario tra gli strumenti formali di interpretazione astratta (che sono specifici per una determinata lingua e richiedono competenze di dominio per la configurazione) e la necessità pratica di comprendere cosa facciano effettivamente i grandi sistemi legacy multilingue non documentati, prerequisito fondamentale per qualsiasi programma di modernizzazione che non voglia scoprire le sue sorprese più costose a metà dell'esecuzione.
Domande frequenti
Qual è la differenza tra interpretazione astratta e model checking? Entrambi sono metodi formali per la verifica dei programmi. L'interpretazione astratta approssima in modo eccessivo l'insieme degli stati possibili (corretta ma potenzialmente imprecisa). Il model checking esplora in modo esaustivo lo spazio degli stati (completo ma fattibile solo per sistemi finiti e limitati). L'interpretazione astratta è scalabile a programmi di grandi dimensioni. Il model checking è scalabile a proprietà complesse su modelli più piccoli. Sono complementari, non in competizione.
L'interpretazione astratta è utile solo per i software critici per la sicurezza? No, anche se in questi ambiti mostra il suo valore più evidente. Infer viene utilizzato nelle pipeline CI/CD standard delle grandi aziende tecnologiche, individuando dereferenziazioni di puntatori nulli e perdite di risorse nel codice Java e C di uso quotidiano. Il grado di rigore applicato è a discrezione dell'utente: da un lato, una verifica completa con garanzie formali, dall'altro un'analisi euristica più leggera, con la maggior parte degli strumenti pratici che si collocano in una posizione intermedia.
L'interpretazione astratta può analizzare il COBOL? L'interpretazione astratta è una teoria indipendente dal linguaggio. La sua applicazione al COBOL richiede l'implementazione delle funzioni di trasferimento astratte per le operazioni COBOL, l'aritmetica dei campi PIC, le clausole REDEFINES, i nomi delle condizioni di livello 88 e così via. Gli strumenti di interpretazione astratta generici (Infer, Astrée) non supportano il COBOL. Le piattaforme di analisi strutturale aziendali che comprendono nativamente il COBOL applicano tecniche di analisi statica correlate per individuare problemi di qualità, codice morto e problemi architetturali nelle codebase COBOL.
