Differenza tra Function Call Graph e Control Flow Graph in informatica
Function Call Graph (FCG) e Control Flow Graph (CFG)
Il grafo delle chiamati a funzioni (detto anche Function Call Graph o FCG) è una rappresentazione, tramite diagramma di flusso, che permette di descrivere le relazioni di chiamante e chiamato tra le funzioni di un programma. In particolare, il FCG è basato su un grafo orientato etichettato i cui nodi rappresentano le funzioni del programma e gli archi le relazioni tra le funzioni.
Il FCG è il risultato dell’analisi di un programma al fine di capirne il funzionamento o come base per ulteriori analisi. Tale grafo può essere ricavato attraverso due tecniche: dinamica e statica. Un FCG dinamico viene ricavato dall’esecuzione del programma, ma permette di avere un grafo limitato al flusso seguito durante l’esecuzione. Per ottenere un grafo completo attraverso le tecniche dinamiche è necessario eseguire più volte il programma (tante volte quanto il numero dei possibili flussi). Un FCG statico è un grafo che rappresenta ogni possibile esecuzione del programma. Inoltre, con tale tecnica vengono rappresentate anche funzioni che durante l’esecuzione non verrebbero mai eseguite a causa di errori di programmazione.
Inoltre, i FCG possono essere suddivisi in context sensitive o context insensitive. I call graph di tipo context sensitive aggiungono un nodo aggiuntivo per ogni configurazione di parametri che viene utilizzata per chiamare tale funzione. I context insensitivi call graph utilizzano un unico nodo per rappresentare la funzione chiamata, senza distinguere i parametri passati alla funzione.
Tipicamente, i FCG estratti dai programmi presentano una struttura ad albero. In cui esiste un nodo radice che rappresenta l’entry point del programma. L’insieme dei nodi che rappresenta le funzioni utilizzate dal programma possono essere suddivise in tipologie diverse: funzioni locali (definite dall’utente) e funzioni non locali o esterne (definite all’interno di librerie terze). Tale differenza è essenziale perché il compilatore può modificare i nomi delle funzioni locali all’interno del binario, ma i nomi delle funzioni esterne rimangono gli stessi.
Poiché esiste una corrispondenza uno a uno tra le funzioni del programma e i nodi del FCG, tutti i nodi possono essere etichettati in modo univoco in base al nome della funzione che rappresenta.
In alcuni casi può essere utile effettuare anche una distinzione ulteriore all’interno delle funzioni non locali; evidenziando la differenza tra funzioni di libreria a caricamento dinamico (DLL) e funzioni collegate staticamente (Statically-linked). Il codice delle funzioni a caricamento dinamico viene aggiunto al programma durante la fase di caricamento in memoria e quindi a runtime. Mentre le funzioni statiche sono aggiunte durante la fase di compilazione del programma.
I FCG ottenuti attraverso l’analisi statica possono contenere anche altre informazioni rilevanti estratte dal binario. In generale, è possibile estrarre il codice operativo che costituisce ogni funzione locale del binario. Queste sequenze di codice possono essere utilizzate per creare diagrammi di flusso delle funzioni locali (Control Flow Graph o CFG).
Le sequenze di istruzioni assembly consecutive che non effettuano diramazioni nel normale flusso di esecuzione prendono il nome di basic block. Il diagramma di flusso di una funzione è costituito da una serie di basic block interconnessi tra di loro che evidenziano tutti i possibili percorsi di una funzione locale.
Inoltre, i FCG e i CFG sono generati ed estratti attraverso tool chiamati disassemblatori. In primo luogo, bisogna capire se al binario sono state applicate tecniche di binary obfuscation o binary packing.
Una volta individuata la tecnica di offuscamento utilizzata, è necessaria rimuoverla per poter analizzare il binario con il disassemblatore. Il disassemblatore viene utilizzato per identificare le funzioni ed assegna un nome simbolico univoco. Ciò è necessario perché i nomi delle funzioni scritte dal programmatore non sono conservati durante la compilazione del software. Quindi vengono assegnati dal decompilatore dei nomi casuali univoci.
Per le funzioni esterne, invece, vengono mantenuti i nomi contenuti all’interno delle librerie. Nel caso di funzioni esterne importate dinamicamente, si può ottenere il suo nome dall’ Import Address Table (IAT) presente nell’header PE dell’eseguibile. Mentre per le funzioni esterne collegate staticamente esistono dei software in grado di riconoscerle ed assegnare i nomi canonici corretti delle librerie standard.
Una volta che tutte le funzioni, cioè i nodi del function call graph, sono stati identificati, vengono inseriti all’interno di una struttura dati FIFO. Successivamente per ogni funzione presente, partendo dall’entry point, all’interno della struttura dati vengono analizzati tutte le relazioni chiamante-chiamato per identificare gli archi. Quando tutte le funzioni sono state processate l’algoritmo termina e il function call graph è creato.
Spesso creare un FCG completo da un binario non è banale. Infatti, l’utilizzo di tecniche di programmazione come la reflaction e i puntatori a funzione rendono l’estrazione delle funzioni più complessa. E soprattutto, non è possibile capire se tale funzione verrà richiamata (e da chi) durante la fase di esecuzione.
