Il ruolo del grafo di controllo di flusso nell'analisi statica

30 ottobre 2023 – 24 min – 5098 parole

Il grafo del controllo di flusso è un importante elemento da costruire nell’analisi statica dei programmi per applicare una serie di analisi che prendono in considerazione il flusso di un programma. Il “flusso”, informalmente, rappresenta l’evoluzione del programma durante il tempo d’esecuzione, ovvero a quali indirizzi la CPU salta per poter proseguire l’esecuzione del programma.

Il grafo (anche chiamato CFG per brevità) consente di ricavare in modo generale i primi elementi di alto livello del software partendo da una rappresentazione di livello basso/medio (citiamo il codice assembly o codice intermedio). Gli elementi di alto livello includono i loop di alto livello (cicli while o for), rami di esecuzione (switch, if, else) che possono essere fondamentali per individuare come l’esecuzione evolve nel tempo.

Ci concentreremo principalmente sul valore che il grafo del controllo di flusso ha per l’analisi statica di programmi di cui non abbiamo una visione chiara (quindi senza codice sorgente). Non dobbiamo però pensare che l’utilità del grafo del controllo di flusso sia limitato per l’analisi di un programma. I compilatori utilizzano il control flow graph per implementare una serie di ottimizzazioni che riguardano le espressioni e le variabili. Il CFG è il punto di partenza per applicare alcune analisi come individuare la liveness di una variabile o calcolare quando una espressione viene riutilizzata.

La costruzione del CFG non comporta sforzi particolari dall’analista dal momento che la maggior parte dei software di analisi già implementa il recupero del grafo a partire dai blocchi elementari. Però le soluzioni facili non fanno parte di questo blog: in questo articolo vedremo come è possibile costruirlo ed alcuni esempi per mostrare quanto è utile il control flow graph all’interno dell’analisi statica.

Il grafo del controllo di flusso

Formalmente, il Control Flow Graph è definito come un grafo <V, E> dove V rappresenta l’insieme dei blocchi elementari di una funzione ed E rappresenta l’insieme degli archi che collegano ogni blocco elementare in base alla rappresentazione semantica delle istruzioni. In alternativa, possiamo dire che il CFG è composto da una serie di archi <b1, b2> , dove b1 e b2 sono blocchi elementari, e quella coppia è inserita all’interno del CFG se e solo se il controllo di flusso dal blocco elementare b1 passa al blocco elementare b2.

Per chi volesse una definizione intuitiva delle strutture di base che stiamo utilizzando: un blocco elementare rappresenta una serie di istruzioni sequenziali che vengono raggruppate all’interno di un’unica struttura chiamata blocco. Ogni blocco elementare non può contenere più di una istruzione di cambiamento di flusso. Una sequenze di istruzioni genera un blocco elementare se: in ogni posizione, una istruzione “domina” (dominare = viene eseguita prima) sulle altre istruzioni sequenziali e nessun’altra istruzione viene eseguita tra due istruzioni in sequenza.

In altre parole, un blocco elementare è composto da una serie di istruzioni tale per cui solo la prima istruzione può essere un target di un blocco (single entry) e solamente l’ultima istruzione può portare ad un altro blocco (single exit). All’interno del grafo di controllo di flusso, possiamo identificare un nodo start che non ha archi entranti e un nodo exit che non ha archi uscenti.

Ogni software di analisi statica, inclusi decompilatori, una volta che le istruzioni del programma sono state disassemblate e tradotte in rappresentazione intermedia, procedono a suddividere le istruzioni in blocchi elementari. I blocchi elementari costituiscono i nodi del grafo, mentre gli archi sono i collegamenti tra ogni blocco elementare. Preso un blocco B, i blocchi a cui il controllo viene trasferito si chiamano successori del blocco B, mentre i blocchi da cui B ottiene il controllo si chiamano predecessori.

Ramo if else

Per calare meglio il CFG nel contesto dell’analisi, procediamo a dettagliare un esempio di costruzione del grafo di controllo di flusso. Supponiamo di avere il seguente codice:

fun1:
	push    rbp
	mov     rbp, rsp
	mov     DWORD PTR [rbp-4], 2
	mov     DWORD PTR [rbp-8], 5
	cmp     DWORD PTR [rbp-4], 1
	jle     .L2
	add     DWORD PTR [rbp-4], 3
	add     DWORD PTR [rbp-8], 2
	jmp     .L3
.L2:
    mov     eax, DWORD PTR [rbp-8]
    sub     eax, 4
    mov     DWORD PTR [rbp-4], eax
    add     DWORD PTR [rbp-8], 5
.L3:
    mov     eax, 0
    pop     rbp
    ret

fun1 è una funzione che chiamiamo per impostare alcuni valori all’interno di indirizzi di memoria (in particolare nello stack). Vogliamo cercare di recuperare il codice originale di alto livello, utilizzando alcune tecniche di analisi statica. Per farlo, dobbiamo cercare di recuperare il flusso di controllo, chiedendoci se il programma ha una esecuzione lineare oppure la CPU procede a valutare alcune condizioni.

Suddividiamo il seguente codice in blocchi elementari sapendo che ogni blocco elementare può contenere una sola istruzione di cambiamento di flusso: applichiamo un algoritmo che individua quelle istruzioni di inizio oppure di fine blocco. I passi da eseguire sono i seguenti:

Identifica le istruzioni “leader” nel codice, ovvero istruzioni che possono essere di queste 3 categorie:
1. La prima istruzione è un leader.
2. L’istruzione puntata da una istruzione di cambiamento di flusso (goto/jump) condizionale o incondizionale è un leader.
3. L’istruzione che segue immediatamente un’istruzione di cambiamento di flusso è leader.
Partendo da un leader, raggruppa la serie di istruzioni successive fino al leader successivo escluso: quel raggruppamento costituisce il blocco base corrispondente al leader iniziale.

Generalmente le istruzioni che fanno terminare un blocco base includono:

rami condizionati e incondizionati, sia diretti che indiretti;
istruzioni di ritorno
istruzioni che possono generare una eccezione
chiamate a funzioni che non effettuano un ritorno (come panic() o __stack_chk_fail).

Procediamo ad applicare l’algoritmo per l’insieme di istruzioni che abbiamo più sopra. Individuiamo i leader:

fun1:
	push    rbp 					# leader (prima istruzione)
	mov     rbp, rsp 				
	mov     DWORD PTR [rbp-4], 2 	
	mov     DWORD PTR [rbp-8], 5 	
	cmp     DWORD PTR [rbp-4], 1 	
	jle     .L2						
	add     DWORD PTR [rbp-4], 3 	# leader (l'istruzione segue una istruzione di salto)
	add     DWORD PTR [rbp-8], 2 	
	jmp     .L3 					
.L2:
    mov     eax, DWORD PTR [rbp-8]	# leader (l'istruzione è puntata da jle .L2)
    sub     eax, 4
    mov     DWORD PTR [rbp-4], eax
    add     DWORD PTR [rbp-8], 5
.L3:
    mov     eax, 0 					# leader (l'istruzione è puntata da jmp .L3)
    pop     rb
    ret

Possiamo individuare quindi i seguenti blocchi elementari:

Il primo:

push    rbp
mov     rbp, rsp 				
mov     DWORD PTR [rbp-4], 2 	
mov     DWORD PTR [rbp-8], 5 	
cmp     DWORD PTR [rbp-4], 1 	
jle     .L2

Il secondo:

add     DWORD PTR [rbp-4], 3 
add     DWORD PTR [rbp-8], 2 	
jmp     .L3

Il terzo:

mov     eax, DWORD PTR [rbp-8]	
sub     eax, 4
mov     DWORD PTR [rbp-4], eax
add     DWORD PTR [rbp-8], 5

e infine il quarto:

mov     eax, 0
pop     rb
ret

La suddivisione è stata sequenziale: il raggruppamento delle istruzioni è stato effettuato andando a valutare ogni singola istruzione presa singolarmente e andando ogni volta alla successiva. Possiamo quindi aggiungere le connessioni tra i blocchi elementari. Per semplicità, numeriamo i blocchi elementari partendo dall’indice zero. Dobbiamo chiederci: preso un blocco elementari, dove salterà a tempo d’esecuzione la CPU?

per il primo blocco elementare abbiamo due collegamenti: il primo va dal blocco elementare 0 al blocco elementare 1 (perché l’esecuzione è sequenziale, quindi il controllo di flusso va al blocco successivo), il secondo va dal blocco elementare 0 al blocco elementare 2 (c’è un salto condizionale all’etichetta L2).
per il secondo blocco elementare abbiamo un solo collegamento: notiamo infatti che l’esecuzione salta per forza all’etichetta L3 (blocco numero 3), quindi c’è un collegamento tra il blocco elementare 1 al blocco elementare 3 (salto incondizionale).
per il terzo blocco elementare abbiamo un solo collegamento: all’interno del blocco non ci sono istruzioni di salto, né tantomeno di chiamata di funzione. Possiamo quindi dire che il controllo passa dal blocco elementare 2 al blocco elementare 3.
il quarto blocco elementare è il blocco finale quindi non abbiamo collegamenti che partono da questo blocco.

Per sintetizzare, abbiamo i seguenti collegamenti:

[ (b0 -> b2), (b0 -> b1), (b1 -> b3), (b2 -> b3) ]

Questo array costituisce il nostro grafo di controllo di flusso e consente di individuare un primo costrutto di cambiamento di flusso ad alto livello. Utilizziamo la notazione DOT per avere un immagine visiva del grafo:

Control flow graph senza descrizione

In effetti questa rappresentazione non è molto utile però possiamo arricchirlo andando ad includere per ogni nodo (o blocco elementare) il codice assembly.

Control flow graph con descrizione

Con questo grafo, possiamo capire come l’esecuzione venga suddivisa in due percorsi, ci dovrà quindi essere una valutazione di una guardia (ovvero di una condizione che se valutata restituisce un valore vero oppure un valore falso) per capire dove il flusso salterà. Per identificare questa informazione, procediamo prendendo il primo blocco elementare. Con il primo blocco elementare possiamo vedere che c’è una istruzione di cmp: nell’instruction set architecture della famiglia x86, cmp è una istruzione che serve per fare la comparazione tra due elementi. Il risultato della comparazione viene impostato all’interno del registro rflags (contiene tutte le flag).

cmp DWORD PTR [rbp-4], 1 -- jle .L2 è equivalente all’espressione *(rbp-4) < 1? Questa valutazione consente di selezionare il prossimo blocco elementare che viene preso in considerazione dalla CPU (ricordiamo però che la CPU salta ad indirizzi della memoria, la rappresentazione a blocchi elementari è solo per facilitare l’analisi). Se il valore contenuto all’interno di (rbp-4) è uguale a 1, allora passeremo all’esecuzione del blocco elementare b2; se così non fosse, passeremo a b1. Questa condizione può essere anche scritta all’interno dell’arco che collega b0 a b1.

Traduciamo ogni blocco elementare con una rappresentazione più simil-C, ricordandoci che le istruzioni di add e sub sono delle operazioni di somma e sottrazione, push rbp -- mov rbp, rsp sono il prologo delle funzioni (per ora non ci interessano), mentre DWORD PTR [rbp-#X] sono delle posizioni della memoria dove rbp - #X è l’indirizzo.

Riscrittura delle variabili

Il grafo di controllo di flusso illustrato qui sopra è molto semplice da capire, con grafi più complessi però potrebbe essere utile effettuare un’azione di riscrittura per cercare di arrivare ad un codice più comprensibile possibile. Per prima cosa potremo riscrivere le variabili in gioco, eliminando DWORD PTR [rbp-#X] Procediamo in questo modo:

Iteriamo su ogni blocco elementare
Iteriamo sulle istruzioni di ogni blocco elementare
Se troviamo una istruzione e uno dei due parametri corrisponde a DWORD PTR [rbp-#X] dove #X è un numero intero: interroghiamo una tabella in cui memorizziamo che per l’indice #X c’è la variabile di nome var_#X e applichiamo la trasformazione DWORD PTR [rbp-#X] -> #X
In tutti gli altri casi: lasciamo invariato il codice.

Questa trasformazione semplifica il codice, ma assume che non interessi all’analista il valore del puntatore di [rbp-X]. Qualche volta eliminare questo tipo di informazione è molto pericoloso e potrebbe portare a trasformazioni non semanticamente equivalenti rispetto al codice di partenza.

Applichiamo la regola per il primo blocco elementare:

push    rbp 					# ignoro l'istruzione: prologo
mov     rbp, rsp 				# ignoro l'istruzione: prologo
mov     DWORD PTR [rbp-4], 2 	# diventa: mov var_4, 2
mov     DWORD PTR [rbp-8], 5 	# diventa: mov var_8, 2
cmp     DWORD PTR [rbp-4], 1 	# diventa: cmp var_8, 1
jle     .L2						# ignoro l'istruzione

Il codice finale risulta essere per il primo blocco elementare:

mov     var_4, 2 	
mov     var_8, 5 	
cmp     var_8, 1 	
jle     .L2

Per il secondo blocco elementare:

add     var_4, 3 
add     var_8, 2 	
jmp     .L3

Per il terzo blocco elementare:

mov     eax, var_4	
sub     eax, 4
mov     var_4, eax
add     var_8, 5

Il quarto non presenta alcuna modifica dal momento che non utilizza alcun accesso all’indirizzo referenziato da [rbp- #X]. Qualcuno potrebbe chiedersi se non avrebbe avuto più senso applicare direttamente la trasformazione sul codice lineare invece di costruire il control flow graph: vedremo successivamente che la costruzione del grafo consente di applicare queste trasformazioni molto facilmente e in contesti locali senza preoccuparci di effetti disastrosi sul resto delle istruzioni.

Riscrittura delle operazioni tramite SSA

La forma di Static Single Assignment è una rappresentazione intermedia molto potente che consente di recuperare alcune informazioni importanti sulla variazione dei valori delle variabili. La forma vine attualmente impiegata nell’analisi statica, nella decompilazione e all’interno dei compilatori ottimizzanti. Questa trasformazione prevede di riscrivere i termini mov primo_parametro, secondo_parametro come un singolo assegnamento primo_parametro = secondo_parametro.

Con abbastanza astuzia e intuizione, è possibile scrivere l’assembly precedente con la forma di Static Single Assignment. Per migliorare l’output della trasformazione possiamo considerare anche le operazioni logico algebriche che sono successive ad una mov e hanno il primo parametro in comune. Procediamo:

Iteriamo sui blocchi elementari:
1. Iteriamo sulle istruzioni
2. Quando troviamo una qualsiasi istruzione mov primo_parametro, secondo_parametro: riscriviamo facendo un assegnamento primo_parametro = secondo_parametro
3. Quando troviamo una qualsiasi istruzione che computa operazioni logico aritmetiche, riscriviamo l’istruzione facendo un assegnamento con l’operazione logico artimetica.

Il codice finale risulta essere per il primo blocco elementare:

var_4 = 2 	
var_8 = 5 	
cmp     var_8, 1 	
jle     .L2

Per il secondo blocco elementare:

var_4 = var_4 + 3
var_8 = var_8 + 2
jmp     .L3

Per il terzo blocco elementare:

eax = var_4
eax = eax - 4
var_4 = eax
var_8 = var_8 + 5

Per il quarto blocco elementare:

eax = 0
pop rb # ignoriamo questa istruzione: epilogo della funzione

Notiamo che in particolare per il terzo blocco elementare può essere applicata un’altra trasformazione per migliorare la leggibilità del codice. Quando troviamo una qualsiasi istruzione che computa operazioni logico aritmetiche che segue una istruzione di assegnamento e il primo_parametro è in comune, allora poniamo l’operazione logica all’interno del primo assegnamento.

Il terzo blocco elementare diventa così:

var_4 = var_4 - 4
var_8 = var_8 + 5

Recupero del controllo di flusso

Nell’ultima trasformazione cerchiamo di recuperare il flusso di controllo del codice per scrivere il codice con i costrutti che siamo abituati a vedere, in particolare per questo caso if ed else. Le istruzioni che rimangono da ispezionare sono la cmp e le jump condizionali o incondizionali.

L’istruzione compare (cmp) per x86 semanticamente è una istruzione di sottrazione tra i due operatori da comparare. Ad esempio cmp %eax, 1 è uguale ad effettuare una operazione di sottrazione tra %eax e 1. Come effetto collaterale, l’operazione di sottrazione imposta alcuni bit di flag all’interno del registro rflags: queste flag consentono alla cpu di saltare con jump condizionali (specificano la flag da considerare).

Soffermiamo la nostra attenzione sul primo blocco elementare in modo da capire come funziona bene il jump. Analizziamo il primo blocco elementare, composto da una serie di istruzioni di assegnamento e:

cmp     var_8, 1 	
jle     .L2

L’istruzione di compare effettua la sottrazione tra var_8 e 1, può sembrare una scelta che non ha alcun senso, perché è necessario effettuare la sottrazione? I creatori dell’ISA di Intel non potevano direttamente aggiungere istruzioni come cmpe o cmple? Rispetto al segno del risultato dell’operazione di sottrazione, identifichiamo tre diverse condizioni:

se il risultato è di segno negativo (flag SIGN a NG - negative), allora var_8 è minore di 1
se il risultato è di segno positivo (flag SIGN a PL - positive), allora var_8 è maggiore di 1
se il risultato è zero (flag ZERO a ZR, altrimenti NZ), allora var_8 è uguale a 1.

È possibile unire le condizioni della flag SIGN e della flag ZERO per capire se un numero è maggiore o uguale oppure minore o uguale. Il blocco di istruzioni che abbiamo mostrato precedentemente può essere riscritto come if (var_8 <= 1), l’argomento del jump condizionale rappresenta l’indirizzo a cui saltare quando la condizione dell’if è vera (ovvero il blocco elementare numero #2). Che cosa succede però se la condizione è falsa? Se la condizione è falsa, la CPU continuerà ad eseguire le istruzioni sequenzialmente: guardando il codice per interezza, la CPU salterà alle istruzioni contenute nel blocco elementare numero #1.

Ritornando alle istruzioni del primo blocco elementare, scriviamo in linguaggio naturale la trasformazione che vogliamo applicare.

Iteriamo sui blocchi elementari
Iteriamo sulle istruzioni
Se l’istruzione che stiamo valutando è una cmp e la successiva è una jump condizionale, scriviamo if (condizione){ etichetta } dove la condizione è composta dagli operandi dell’operazione cmp e l’operazione è data dal tipo di jump condizionale (le per Less Equal, g per Greater…). Aggiungiamo anche il numero di blocco elementare a cui saltare tra due parentesi graffe.

Le due istruzioni quindi diventano if(var_8 <= 1) { b2 }. Dal momento che l’altro blocco elementare (ovvero la condizione falsa) è raggiungibile solo se (var_8 > 1) possiamo utilizzare il costrutto else per rappresentare la condizione di falsità della guardia dell’istruzione if. Il codice finale è if(var_8 <= 1) { b2 } else { b1 }.

Un’ulteriore trasformazione è l’unione di tutti i blocchi elementari per cercare di ricomporre il codice iniziale da cui siamo partiti. Dobbiamo stare attenti a posizionare i blocchi elementari nelle corrette posizioni: seguendo ad esempio la trasformazione del ramo if-else possiamo posizionare il blocco numero #2 all’interno del ramo true dell’if e il blocco numero #1 all’interno del ramo false dell’if. Aggiungiamo un punto e virgola finale per rendere tutto più simile al C.

var_4 = 2; 	
var_8 = 5;
if (var_8 <= 1) {
	var_4 = var_4 - 4;
	var_8 = var_8 + 5;
} else {
	var_4 = var_4 + 3;
	var_8 = var_8 + 2;
}
eax = 0;

Sarebbe riduttivo però avere l’ultima istruzione con un registro: perché effettivamente viene utilizzato il registro eax per impostarlo a 0, se dopo non viene utilizzato? In effetti c’è un dettaglio che è stato omesso e riguarda la caratteristica principale di questo codice assembly. Il codice assembly è stato estrapolato da una funzione (puoi individuare se una serie di istruzioni assembly sono una funzione, identificando il prologo e l’epilogo!). All’interno dell’Instruction Set Architecture di Intel, è specificato come il risultato finale della funzione, ovvero il valore di ritorno, è contenuto sempre all’interno del registro eax. Se l’ultima istruzione è eax = valore, possiamo sostituire il codice con return valore. In definitiva, il codice risulta:

int fun_1(){
	var_4 = 2; 	
	var_8 = 5;
	if (var_8 <= 1) {
		var_4 = var_4 - 4;
		var_8 = var_8 + 5;
	} else {
		var_4 = var_4 + 3;
		var_8 = var_8 + 2;
	}
	return 0;
}

Questo esempio non ha un particolare significato a livello della semantica del codice. Possiamo notare una importante caratteristica che prima forse era più nascosta riguardante i valori delle variabili. Dal momento che conosciamo i valori delle variabili a priori e sapendo che i valori sono statici, possiamo applicare tutte le tecniche di ottimizzazione per andare a semplificare le istruzioni (la condizione dell’if sarà sempre falsa!). Questo particolare non era così scontato per noi perché è molto difficile comprendere codice a basso livello: il compilatore invece avrebbe potuto tramite la suddivisione in blocchi elementari accorgersi della condizione sempre falsa non includendo il blocco elementare numero 2 ed eliminando i due rami d’esecuzione.

L’esempio (banale) fa capire l’importanza della suddivisione in blocchi elementari e l’applicazione delle trasformazioni locali all’interno dei blocchi. Tutte le volte che andiamo ad eseguire la compilazione di un certo codice sorgente, il compilatore applica alcune tecniche di ottimizzazione proprio sulla base del grafo del controllo di flusso per andare ad eliminare codice morto (codice non utilizzato) o rimescolamento delle istruzioni. Per andare ad aggiungere ulteriore valore all’utilizzo del grafo del controllo di flusso, segue un esempio più complesso.

Il ciclo while e il ciclo for

Vediamo un esempio più complesso per analizzare il grafo del controllo di flusso e ottenere informazioni rispetto ai cicli. L’obiettivo è quello di ricostruire il codice originale e capire se possiamo ricavare anche che cosa fa questa particolare funzione rispetto ad uno o più parametri utilizzati localmente.

f2:
        push    rbp
        mov     rbp, rsp
        mov     DWORD PTR [rbp-12], 4
        mov     DWORD PTR [rbp-4], 0
        mov     DWORD PTR [rbp-8], 1
        jmp     .label_A
.label_B:
        mov     eax, DWORD PTR [rbp-8]
        imul    eax, DWORD PTR [rbp-4]
        mov     DWORD PTR [rbp-8], eax
        add     DWORD PTR [rbp-4], 1
.label_A:
        mov     eax, DWORD PTR [rbp-4]
        cmp     eax, DWORD PTR [rbp-12]
        jl      .label_B
        mov     eax, 0
        pop     rbp
        ret

Applichiamo la suddivisione in blocchi elementari e costruiamo il grafo del controllo di flusso. Il primo blocco elementare risulta essere:

push    rbp 					# prologo
mov     rbp, rsp 				# prologo
mov     DWORD PTR [rbp-12], 4
mov     DWORD PTR [rbp-4], 0
mov     DWORD PTR [rbp-8], 1
jmp     .label_A

Il secondo blocco elementare risulta essere (label_B):

mov     eax, DWORD PTR [rbp-8]
imul    eax, DWORD PTR [rbp-4]
mov     DWORD PTR [rbp-8], eax
add     DWORD PTR [rbp-4], 1

Il terzo blocco elementare (label_A):

mov     eax, DWORD PTR [rbp-4]
cmp     eax, DWORD PTR [rbp-12]
jl      .label_B

E il quarto:

mov     eax, 0
pop     rbp
ret

Esaminiamo blocco per blocco per capire i collegamenti tra i blocchi elementari:

per il blocco numero 0: abbiamo un solo jump incondizionato al blocco numero 2 (con label_A)
per il blocco numero 1 (label_B): non abbiamo istruzioni di jump, proseguiamo con l’esecuzione con il blocco numero 2 (label_A)
per il blocco numero 2 (label_A): abbiamo un’istruzione di jump condizionato al blocco numero 1 (label_B), altrimenti proseguiamo linearmente con il blocco numero 3.
per il blocco numero 3: l’esecuzione termina con la ret. Non abbiamo collegamenti con altri blocchi.

Per sintetizzare, abbiamo i seguenti collegamenti:

[ (b0 -> b2), (b1 -> b2), (b2 -> b1), (b2 -> b3) ]

Applicando la notazione DOT, possiamo rappresentare il grafo in questo modo:

Control flow graph ciclo while-for senza descrizione

Questa rappresentazione non è molto utile, possiamo arricchirla andando ad includere per ogni nodo (o blocco elementare) il codice assembly.

Control flow graph ciclo while-for con descrizione

In questo caso, non sappiamo bene come poter identificare il controllo di flusso, notiamo però rispetto all’esempio precedente che il grafo presente un ciclo (dato da b1 -> b2 e b2 -> b1). Questa caratteristica potrebbe indicare che il codice iniziale contiene un ciclo: una porzione di codice che viene eseguita più volte con la valutazione di una specifica guardia.

Il prossimo passo sarà quello di applicare le trasformazioni che abbiamo precedentemente applicato per l’esempio del ramo if-else. Applicheremo le trasformazioni per la riscrittura delle variabili, riscrittura delle operazioni e recupero del controllo di flusso.

Ignorando per ora il prologo, il primo blocco elementare diventa:

var_12 = 4
var_4 = 0
var_8 = 1
jmp     .label_A

Il secondo blocco elementare (label_B):

var_8 = var_8 * var_4
var_4 = var_4 + 1

Il terzo blocco elementare (label_A):

if (var_4 < var_12) { goto label_B } 
# posso scrivere 'goto' come un jump
# cmp     var_4, var_12
# jl      .label_B

Il quarto blocco elementare:

eax = 0

Notiamo che il terzo blocco elementare (ovvero il blocco elementare #2) è molto particolare in quanto è potenzialmente raggiungibile sia da b0 sia da b1. Possiamo immaginare che l’esecuzione della CPU continui a saltare tra il blocco elementare b1 e il blocco elementare b2. Non possiamo quindi pensare di unire i blocchi elementari senza tenere conto di questa informazione. Intuitivamente possiamo pensare che il terzo blocco elementare sia la condizione d’uscita del ciclo, mentre il secondo blocco elementare corrisponde al corpo del ciclo (ovvero cosa viene eseguito ad ogni iterazione).

Blocco dominatore

Questa intuizione però non può essere lasciata al caso. Gli analisi del software che per prima hanno descritto il grafo del controllo di flusso hanno indicato una nozione molto importante chiamata individuazione dei blocchi dominatori. Un blocco b_i si dice dominante su un blocco b_j se e solo se all’interno di tutti i percorsi che vanno dal nodo start al nodo b_j c’è anche il blocco b_i.

Formalmente i blocchi dominatori di un blocco B sono definiti come:

dom(B) = {B} unione ( intersezione ( per ogni Y in Predecessori(B) ) dom(Y) )

dove:

Un blocco B domina se stesso;
Un nodo che domina su tutti i predecessori di B domina anche su B;
Prendo l’intersezione tra ogni nodo dei predecessori e i loro dominatori;

Posso calcolare i blocchi dominatori tramite un semplice algoritmo che sfrutta uno stack come lista per mantenere le informazioni relative ai blocchi elementari ancora da computare.

dom(b0) = {b0} dove b0 è il nodo iniziale (questo insieme non cambia mai)
Per tutti i nodi tranne b0, imposta inizialmente dom(B) = {tutti i blocchi elementari}
Push ogni nodo tranne b0 su una lista.
Ora rimuovi qualsiasi nodo, B, dalla lista.
1. Calcola un nuovo valore per dom(B) utilizzando la formula precedente.
2. Se il nuovo valore di dom(B) differisce dal valore corrente, utilizzare il nuovo valore.
3. Aggiungi tutti i successori di B alla lista di lavoro (se non sono già presenti nell’elenco, ad eccezione di b0 il cui valore è noto).
Ripetere fino a quando la lista di lavoro è vuota.

Per questo caso:

dom(b0) = {b0}
dom(b1) = {b1, b2}
dom(b2) = {b0, b1, b2}
dom(b3) = {b0, b1, b2, b3}

Identifichiamo quindi i loop naturali: un loop si dice naturale quando in presenza di un arco all’indietro che va da m a n, n domina su m, è un insieme di nodi x tale per cui n domina su x ed esiste un percorso che va da x ad m e non contiene m. L’unico arco all’indietro per il nostro grafo è quello che va dal blocco elementare b1 al blocco elementare b2.

Riscrivendo la definizione, dobbiamo trovare un loop naturale con un arco all’indietro che va da b1 a b2 e dobbiamo comprendere all’intero del loop naturale un insieme di nodi x tale per cui b2 domina su x ed esiste un percorso che va dal nodo x al nodo b1 e non contiene b1. Scopriamo che l’unico nodo x che rispetta questa condizione è il nodo b2, intestazione del ciclo.

In definitiva, l’algoritmo che identifica i loop naturali è descritto come segue:

Identifica i dominatori.
Trova gli archi all’indietro: i target degli archi all’indietro sono potenzialmente le intestazioni dei loop.
Verifica che per ogni arco all’indietro esiste un percorso che va dal blocco elementare da cui l’arco parte al blocco intestazione del loop.

Ora che abbiamo riconosciuto il loop con b1 come corpo del ciclo e b2 blocco intestazione, possiamo procedere a riscrivere il codice unendo il blocco b2 e il blocco b1 tra un ciclo while.

while(var_4 < var_12){
	var_8 = var_8 * var_4;
	var_4 = var_4 + 1;
}

Vi ricorda qualcosa questo ciclo while? Finché var_4 è minore di var_12 moltiplico var_8 con var_4: questo potrebbe non essere così visibile con la prima occhiata però rappresenta la funzione fattoriale di un numero naturale. In particolare, il ciclo rappresenta var_8 = fatt(var_12). Unendo gli altri blocchi elementari con alcune trasformazioni, possiamo trovare la forma originale del codice:

var_12 = 4;
var_4 = 0;
var_8 = 1;
while(var_4 < var_12){
	var_8 = var_8 * var_4;
	var_4 = var_4 + 1;
}
return 0;

Per essere più precisi, qualcuno potrebbe accorgersi che l’assegnamento a var_4, possiamo riscrivere il ciclo while in un ciclo for. Per identificare il ciclo for, all’interno del blocco del ciclo deve esserci una istruzione che aumenta o diminuisce il valore di una variabile utilizzata all’interno della guardia e prima del loop deve esserci l’inizializzazione della variabile.

var_12 = 4;
var_8 = 1;
for(var_4 = 0; var_4 < var_12; var_4++){
	var_8 = var_8 * var_4;
}

Non sempre è così ovvio trasformare un loop while in un ciclo for, però i moderni software di analisi statica hanno alcune euristiche per controllare che all’interno del corpo vi siano le classiche operazioni di incremento o decremento di una variabile utilizzata per poter accedere, ad esempio, ad una struttura o ad un array.

Il valore finale della funzione fattoriale dipende da var_12 e anche per questo caso abbiamo provveduto a semplificare la trattazione inserendo un valore statico. Per esercizio potete verificare come ottimizzare il codice (semplicemente posizionando all’interno di var_8 il valore di fatt(4)).

Per questo esempio è stato abbastanza facile recuperare il ciclo while dal momento che il codice messo a disposizione coincideva con l’idea e la definizione di loop naturale (quindi abbiamo potuto contraddistingue senza problemi l’intestazione del loop e il corpo). Ricordiamo però che non è sempre così: i loop irriducibili sono loop che consentono di “rompere” gli algoritmi di loop detection. I loop irriducibili prevedono più punti di accesso per il corpo dei loop, l’algoritmo che abbiamo proposto non riuscirebbe a decidere quale blocco prendere in considerazione come corpo. Sono stati sviluppati diversi approcci per poter risolvere la situazione: bisogna tenere conto che in presenza di un normale codice assembly generato da un compilatore “classico” troviamo per la maggior parte dei casi loop naturali.

Il grafo di controllo di flusso è il punto di partenza dell’analisi

Abbiamo visto attraverso due esempi come il grafo di controllo di flusso e alcune proprietà di questo grafo (dominatori, loop interni, principio di località) possono essere molto potenti per poter applicare una serie di analisi sul codice. Il grafo può essere applicato in realtà sia al codice sorgente, sia alla rappresentazione intermedia ma anche al codice di più basso livello. Quello che in realtà importa è quanta informazione riguardante il controllo di flusso è disponibile chiaramente: nella rappresentazione intermedia, ad esempio, non è così lampante osservare un ciclo for o un ciclo while in quanto non si conoscono i salti. È possibile sviluppare delle euristiche per poter identificare efficaciemente la separazione di rami e associare un costrutto del controllo di flusso (if-else, while, switch).

La maggior parte degli algoritmi si sviluppano all’interno di un grafo: decompilatori e analizzatori come Angr, Binary Ninja, Ghidra, IDA fanno un utilizzo costante di algoritmi di analisi del software applicati al grafo di controllo di flusso. La scelta di utilizzare questa struttura dati è data dalla versatilità con cui si può costruire una qualsiasi trasformazione da poter applicare all’interno di un blocco locale senza preoccuparsi di “effetti collaterali” all’esterno del blocco preso in considerazione.

Il grafo del controllo di flusso può essere costruito all’interno di una singola funzione oppure su tutto il programma: per evitare di rendere troppo pesante la lettura, ci focalizzeremo sulla costruzione del grafo di controllo di flusso locale ad una funzione. Per costruire il grafo del controllo di flusso sull’intero programma è necessario costruire tutti i controlli di flusso localmente e poi attraversare i grafi dal punto iniziale, esplorando tutti i rami d’esecuzione. Questo è computazionalmente oneroso dal momento che l’utilizzo delle risorse cresce esponenzialmente al numero di percorsi da attraversare.

Il grafo del controllo di flusso costruito localmente ad una funzione, seppur semplice da manipolare, può talvolta generare risultati imprevedibili a seconda della complessità del grafo e della presenza o meno di loop irriducibili. Attaccanti che vogliono vanificare ogni sforzo per ottenere il codice sorgente originale possono costruire grafi di controllo di flusso con un numero di nodi abbastanza elevati per consumare tutte le risorse dell’analista. Esistono poi offuscamenti come il control flow flattening per rendere inutile ogni tentativo di recuperare il controllo di flusso originale.

Nel prossimo articolo, vedremo come costruire un grafo di controllo di flusso attraverso le API di Ghidra. Come sempre, se avete critiche, suggerimenti o qualsiasi altro commento, potete scrivere un’e-mail a seekbytes@protonmail.com.