9. Blocchi elementari da riconoscere
Ora che stiamo iniziando a dare un senso alla sequenza di byte non strutturata nel file binario, il prossimo problema che dobbiamo risolvere prima di poter iniziare a decompilare il codice è essere sicuri che una sequenza di istruzioni sia effettivamente eseguita nella sequenza che vediamo nell’archivio.
Considera la seguente sequenza:
L1: MOV EAX, $2
L2: MUL EAX, ECX
L3: MOV DWORD [0x402000], EAX
Poiché sappiamo dal manuale utente del processore che l’istruzione MUL richiede che uno degli operandi e il risultato siano in EAX, potremmo essere tentati di tradurre la sequenza precedente nella seguente istruzione:
var_402000 = ecx * 2;
Sarebbe sbagliato per due ragioni:
- potrebbe esserci un salto da qualche altra parte del programma a L2. Se ciò accade, non possiamo essere sicuri che EAX conterrà il valore 2!
- Il registro EAX può essere riutilizzato dopo aver salvato in memoria il valore dell’istruzione MUL.
Ad esempio, una sequenza più grande potrebbe essere la seguente:
L0: MOV EAX, $3
CMP EBX, $0
JNE L2
L1: MOV EAX, $2
L2: MUL EAX, ECX
L3: MOV DWORD [0x402000], EAX
MOV DWORD [0x402010], EAX
...
Il modo corretto per tradurre la sequenza di cui sopra sarebbe:
eax = (ebx == 0) ? 2 : 3;
var_402010 = var_402000 = eax * ecx;
Ma come sappiamo che l’esecuzione potrebbe saltare L1 e passare direttamente a L2? E, cosa più importante, come facciamo a sapere che non ci sono altri modi in cui l’esecuzione può andare a L2, magari da qualche altra parte del codice?
Questi problemi possono essere risolti utilizzando una ben nota struttura dati chiamata basic block . Questa struttura dati è una delle più importanti dell’intero decompilatore, poiché gran parte del codice si baserà sulle informazioni memorizzate in essa per molte analisi.
Esistono molte informazioni in letteratura su cosa siano i blocchi di base. Abbiamo già dato una definizione informale. Eccone una più precisa: “un blocco di base è una sequenza di istruzioni; la prima istruzione è l’unico modo per l’esecuzione di entrare in un blocco di base; l’ultima istruzione è l’unico modo per l’esecuzione di uscire dal blocco di base.”
Una conseguenza di questa definizione è che ogni destinazione di salto avvia un nuovo blocco base e ogni istruzione di salto (comprese le istruzioni di ritorno) termina un blocco base.
Per un decompilatore non è chiaro se un’istruzione di chiamata debba terminare un blocco di base. A seconda della sofisticatezza degli algoritmi, si può considerare un’istruzione di chiamata per terminare un blocco di base, oppure si possono semplicemente ignorare le istruzioni di chiamata per il momento.
È comunque chiaro che la destinazione, ovvero un’istruzione di richiamo avvia sempre un blocco base.
Dato che abbiamo già calcolato l’elenco di etichette e salti durante la scansione del codice e dei dati e che abbiamo il punto di ingresso della maggior parte delle funzioni nella nostra tabella delle procedure, possiamo costruire i blocchi di base per una procedura utilizzando il seguente algoritmo:
current_address = current_procedure->entry_address
workList.push = current_address
while workList not empty
current_address = workList.pop
next:
block = new Block at current_address
blockList += block
label = find label at address higher than current_address
branch = find branch at address higher than current_address
if label->address < branch->address_after_branch
block->length = label->address - block->address
current_address = label->address
goto next
end if
block->length = branch->address_after_branch - block->address
if branch is return // returns have no known destination
continue
workList.push = branch->destination
if branch is conditional
current_address = branch->address_after_branch
goto next
end if
// else will resume from branch destination
end while
Questo algoritmo registrerà nel set blockList quali sequenze di istruzioni vengono eseguite in sequenza. Ma visto che ci siamo, perché non registriamo anche dove l’esecuzione va da un blocco all’altro? Dopo tutto, può essere utile sapere che nel nostro esempio, dopo aver impostato EAX a 3, lo useremo nell’istruzione MUL, invece che in qualche altra istruzione. Per fare ciò, registriamo 2 informazioni aggiuntive per ogni blocco:
L’elenco dei blocchi che saltano all’istruzione di ingresso del blocco corrente: ovvero l’elenco dei blocchi predecessori (pred in breve); e l’elenco dei blocchi a cui saltiamo quando abbiamo finito di eseguire questo blocco: questo è l’elenco dei blocchi successori (succ in breve). Ecco una versione modificata dell’algoritmo di costruzione del blocco di base che registra queste informazioni aggiuntive:
Block *get_block_at(Address start_address)
{
Block *block = find in BlockList a block for start_address
if block == not found
block = new Block at start_address
blockList += block
return block
}
CreateBasicBlocks(current_procedure)
{
current_address = current_procedure->entry_address
block = get_block_at(current_address)
current_procedure->entry_block = block
workList.push = current_address
while workList not empty
current_address = workList.pop
block = get_block_at(current_address)
next:
label = find label at address higher than current_address
branch = find branch at address higher than current_address
if label->address < branch->address_after_branch
block->length = label->address - block->address
current_address = label->address
next_block = get_block_at(current_address)
next_block->preds += block
block->succs += next_block
block = next_block
goto next
end if
block->length = branch->address_after_branch - block->address
if branch is return // returns have no known destination
continue
end if
next_block = get_block_at(branch->destination)
next_block->preds += block
block->succs += next_block
workList.push = branch->destination
if branch is not conditional
continue // will resume from branch destination
end if
next_block = get_block_at(branch->address_after_branch)
next_block->preds += block
block->succs += next_block
block = next_block
current_address = block->address
goto next
end while
sort blockList by block's start address
}
Note :
questo algoritmo è ancora incompleto: non tiene conto dei salti indiretti, in quanto presuppone solo che un salto possa avere 2 destinazioni: il caso vero e il caso falso. I salti indiretti, invece, possono avere molte destinazioni. Estenderemo l’algoritmo nella sezione avanzata per aggiungere tutte le destinazioni note all’elenco dei successori per un blocco che termina con un salto indiretto.
l’algoritmo utilizza solo salti e ritorni. Dovrebbe ignorare le chiamate di funzione (ovvero, se le istruzioni di chiamata sono state registrate nell’elenco dei rami, devono essere saltate quando si cerca il ramo successivo).
Sebbene questo algoritmo sia più complicato, vedremo nella prossima sezione che le informazioni sui successori e sui predecessori diventeranno molto utili per saperne di più sulla nostra procedura.
