Verificatore ipd e BCEL 3

Verificatore ipd e BCEL

La struttura dati più importante, anche in termini di spazio, per l’algoritmo di verifica della Sun è il dizionario, cioè l’insieme di tutti gli in-frames (dei targets delle istruzioni di salto) salvati per effettuare correttamente la data-flow analysis: è proprio questa struttura dati, a causa della sua estensione per i metodi più “complessi”, a rendere difficoltosa l’implementazione di un verificatore on-card per sistemi embedded.

Prima di affrontare nel capitolo successivo quali sono le problematiche e come sono state risolte relative alle subroutines in questo capitolo viene discussa la verifica proposta nel verificatore ipd.

L’algoritmo del verificatore ipd è basato sull’idea di una gestione dinamica del dizionario [dynamicJBV] [ipdJTRES], le entries del dizionario vengono cioè allocate/deallocate non tutte all’inizio ma durante il processo di verifica e su una politica di scelta della sequenza delle istruzioni da verificare in modo da rendere “ottimo” tale processo. La soluzione si basa su una tecnica di ottimizzazione utilizzata, in un ambito differente, nei compilatori ed è fondata sul concetto di

immediate post dominators (ipds) del control-flow graph (cfg, grafo di flusso delle

3.1 Il

Control-Flow Graph

Ogni metodo, ed ogni programma in generale, è caratterizzato da un control-flow

graph (cfg) cioè da un insieme di nodi ed archi (il grafo appunto) orientato: ogni

nodo è una istruzione, ogni arco è una transizione tra i nodi connessi. Nel nostro caso la transizione è la relazione di sequenzialità nell’esecuzione delle istruzioni: in definitiva se seguiamo un percorso sul grafo, la sequenza di nodi che attraversiamo risulta essere una possibile sequenza di esecuzione del programma (fig. 3.1).

5 6 15 9 12 16 19 grafo di flusso associato al bytecode .... 5: baload[51](1) 6: ifne[154](3) -> 15: aload_1 9: sipush[17](3) -28412 12: invokestatic[184](3) 39 15: aload_1[43](1) 16: invokevirtual[182](3) 34 19: astore_2[77](1) .... bytecode possibili sequenze di esecuzione .... 5: baload[51](1) 6: ifne[154](3) -> 15: aload_1 15: aload_1[43](1) 16: invokevirtual[182](3) 34 19: astore_2[77](1) .... .... 5: baload[51](1) 6: ifne[154](3) -> 15: aload_1 9: sipush[17](3) -28412 12: invokestatic[184](3) 39 15: aload_1[43](1) 16: invokevirtual[182](3) 34 19: astore_2[77](1) .... se q u en za 1 se q u en za 2

fig. 3.1: Grafo e possibili sequenze di esecuzione del bytecode1

La maggior parte delle istruzioni (nodi) hanno un solo arco entrante ed un solo arco uscente, ma in generale questo non è vero: le istruzioni di salto condizionato, ad esempio, possono avere 2 o più archi entranti/uscenti. Per ora prenderemo in considerazione solo grafi ben strutturati: non prenderemo in considerazione ad esempio grafi con istruzioni di salto che hanno come target se stesse o che non hanno targets. Per comodità nell’esposizione, inoltre, tutti i grafi li supporremo “delimitati” da due nodi virtuali: START e END, che caratterizzano rispettivamente l’inizio e la fine del metodo (fig.3.2).

1 _{Il bytecode disassemblato è presentato nella forma verbosa <label: opcode[cod](bytes) operands>:}

label è un intero che rappresenta (in modo univoco) la posizione di una determinata istruzione nel bytecode, opcode è l’istruzione in forma mnemonica, [cod] è la codifica dell’istruzione nel bytecode, (bytes) sono il numero di bytes utilizzati per codificare l’istruzione, operands sono gli eventuali operandi

START 0 2 END

5 6

9

12 14

fig. 3.2: Esempio di grafo con nodi virtuali START e END

Nel seguito riportiamo esempi di control-flow graphs di programmi. Per ogni istruzione, il numero di archi uscenti dipende solo dalla particolare istruzione in questione: in particolare i salti condizionati (if, switch) hanno sempre 2 o più archi uscenti, solo l’istruzione virtuale END non ha archi uscenti e tutte le altre hanno un solo arco uscente. Gli archi uscenti da una istruzione di salto condizionato li chiameremo rami del salto condizionato.

Il numero di archi entranti invece è legato a tutta la struttura del grafo e quindi del programma: ogni istruzione ha solitamente un solo arco entrante (fatta eccezione per il nodo virtuale START che non ha archi entranti), ma in generale questo non è vero: infatti tutte le istruzioni che sono target di qualche salto condizionato possono avere più archi entranti. La figura 3.3 riporta un control-flow graph con un nodo con 4 archi entranti. START 0 2 END 5 6 9 19 12 14 16 ( if ) ( switch ) ( target )

fig. 3.3: Esempio di grafo che ha un target con 4 archi entranti.

I grafi presi in considerazione, supponiamo che soddisfino la condizione che partendo da qualsiasi istruzione sia sempre possibile trovare un percorso che porti al nodo END. Il grafo in figura 3.4.1 non soddisfa la condizione precedente perché i nodi 14 e 12 non raggiungono il nodo END, invece il grafo in figura 3.4.2 soddisfa la condizione.

START 0 2 END

5 6

9 19

12 14

fig. 3.4.1 Esempio di grafo con nodi (12 e 14) che non raggiungono il nodo END

START 0 2 END

5 6

9 19

12 14

fig 3.4.2: Esempio di grafo in cui tutti i nodi raggiungono il nodo END

3.2 Verifica basata sull’ipd

A questo punto descriviamo a grandi linee come avviene la verifica utilizzando l’algoritmo ipd. Un post-dominator è una istruzione che si trova su tutti i possibili percorsi che partono dal nodo START ed arrivano al nodo END: prese quindi due istruzioni instr1, instr2 di un grafo diremo che instr2 post-domina instr1 se tutti i percorsi che partono dal nodo START, passanti per instr1 per arrivare al nodo END, passano anche per instr2. In particolare diremo che instr2 è

l’immediate-post-dominator di instr1 se instr2 è il primo post-l’immediate-post-dominator incontrato sul cammino da instr1 al nodo END.

L’algoritmo di verifica basato sull’ipd modifica la gestione del dizionario durante la

data-flow analysis (passo 3) dell’algoritmo della Sun ed i principi su cui si basa

sono:

1. ogni control-flow graph viene virtualmente diviso in blocchi ed ogni blocco “non banale” parte con una istruzione di salto e termina con il suo ipd: in questo modo è possibile associare una sorta di “tempo di vita” alle entries del dizionario per capire quando crearle e quando rimuoverle;

2. vengono lasciate in memoria solo le entries necessarie per la verifica di un blocco;

3. il dizionario viene gestito in modo da non contenere frames duplicati: questa caratteristica in realtà non è strettamente necessaria, è solo una ottimizzazione: chiariremo nel paragrafo 6 di questo stesso capitolo come e perché può essere molto vantaggiosa.

Per sfruttare al meglio il partizionamento in blocchi del control-flow graph le istruzioni vanno verificate seguendo l’ordine sequenziale dato dal programma ed ogni volta che si lascia un blocco tutte le istruzioni del blocco devono essere state verificate. I blocchi non banali partono sempre con una istruzione di salto condizionato e terminano con il relativo ipd, quindi verificare completamente un blocco vuol dire verificare tutte le istruzioni di tutti i rami del salto condizionato. La figura 3.5 riporta un esempio di grafo ripartito in blocchi.

START 0 2 END 5 6 9 12 14 17 19 20 23 blocco 1 blocco 2

fig. 3.5: Blocchi di un grafo di flusso

A differenza dell’algoritmo della Sun che alloca staticamente nel dizionario una

entry per ogni target all’inizio della verifica, la strategia del verificatore ipd alloca

memoria solo quando viene “aperto” un salto condizionato e dealloca quando viene “chiuso”. Un salto condizionato si dice “aperto” quando i suoi rami non sono stati ancora tutti verificati in modo completo, si dice “chiuso” in caso contrario (fig 3.6). In particolare, quando un salto condizionato viene aperto le informazioni da salvare del dizionario sono i frames di tutti i suoi targets e del suo ipd. Inoltre bisogna memorizzare, in un’altra struttura dati, la coppia [salto_aperto_i,m_rami] che specifica, per il salto condizionato aperto, il numero di rami ancora da verificare. Come sarà chiaro tra poco, queste informazioni sono necessarie per applicare correttamente le “regole dell’ipd”. Oltre al dizionario quindi esiste anche un’altra struttura dati, chiamata contesto, che contiene queste informazioni. Lo spazio

occupato dal contesto è minimo ed è quindi irrilevante ai fini dello studio della fattibilità della verifica on-card.

START 0 2 END 5 6 9 12 14 ( salto condizionato aperto ) START 0 2 END 5 6 9 12 14 ( salto condizionato chiuso ) istruzioni verificate istruzioni da verificare i i

fig. 3.6: Esempio di salto condizionato aperto / chiuso

Quando un salto condizionato (il j-esimo ad esempio) viene chiuso vengono deallocate tutte le entries del dizionario che non occorrono più, cioè tutte le entries create quando il salto condizionato è stato aperto, e tolta dal contesto la coppia

[salto_aperto_j,m_rami].

E’ possibile osservare inoltre che il contesto è una struttura dati organizzata a stack perché nei grafi l’ordine con cui vengono chiusi i salti condizionati è inverso rispetto all’ordine con cui vengono aperti.

3.3 Regole del verificatore ipd

Le regole del verificatore ipd sono riportate in Appendice.

Esaminiamo ora in dettaglio le regole del verificatore ipd che differenziano da quelle del verificatore standard della Sun: le “regole dei salti condizionati” e le “regole

dell’ipd” [dynamicJBV],[TPMasci].

Le regole dei salti condizionati vengono utilizzate quando viene aperto un salto condizionato: vengono create entries nel dizionario e nel contesto, e vengono effettuati controlli che garantiscono il buon funzionamento dell’algoritmo.

Regola b1: branch_∉ (branch non appartiene).

Quando viene incontrata una nuova istruzione di salto condizionato nel dizionario viene creata, se non era già presente, una entry per ogni target ed una entry per l’ipd; se le entries erano già presenti viene fatto il merge2_.

Inoltre, supponendo che l’istruzione abbia m targets, nel contesto viene salvata la coppia [salto_condizionato_j,m_rami].

Regola b2: branch= (branch uguale).

Se un salto condizionato già aperto viene incontrato nuovamente ed il merge per i suoi targets non provoca cambiamenti nel dizionario (queste entries erano sicuramente già presenti nel dizionario perché il salto condizionato era aperto) allora non accorre verificare di nuovo i suoi rami: possiamo assumere di averli già verificati ed andare direttamente all’ipd del salto condizionato aperto. Questa regola garantisce la terminazione dell’algoritmo di verifica.

Regola b3: branch≠ (branch diverso).

Questa regola gestisce il caso opposto al precedente: se un salto condizionato già aperto viene incontrato nuovamente ed il merge per i suoi

targets fa cambiare almeno un frame del dizionario, allora il salto

condizionato va verificato nuovamente, come se venisse incontrato per la prima volta. Si devono quindi rimuovere tutte le coppie

2 _{Il merge è l’operatore che permette di individuare il least upper bound di due tipi, cioè il primo}

[salto_condizionato_j,m_rami] dal contesto fino a quella (inclusa) del salto

condizionato che si deve ripetere e poi quindi si applica di nuovo la regola

. branch_∉

La figura 3.7 mostra delle strutture tipiche di grafi in cui si applicano le regole dei salti condizionati. START 0 END 9 11 5 6 14 branch₌ 12 START 0 2 9 11 5 6 14 12 END branch_≠ START 0 END 5 6 9 12 14 branch_∉ A B 9 2 A A 9 2 A out-frame dell'istruzione n A in-frame dell'istruzione n* *La lettera ne specifica il contenuto; se non

presente il frame è vuoto (null-frame) n n istruzioni verificate istruzioni da verificare istruzione corrente i i i 2 2

fig. 3.7: Regole dei salti condizionati

Le regole dell’ipd garantiscono invece che tutti i rami di un salto condizionato vengano verificati prima di procedere oltre: solo quando un salto condizionato viene chiuso è possibile deallocare entries dal dizionario.

Regola i1: ipd≠0 (ipd diverso da 0)

Se l’istruzione raggiunta è un ipd ed i rami del relativo salto condizionato non sono stati ancora tutti verificati (supponiamo che rimangano k rami da verificare), allora l’esecuzione simbolica dell’ipd viene rimandata: viene quindi aggiornato l’in-frame del dizionario relativo all’ipd facendo il merge con il frame attuale, viene caricato nel frame corrente l’entry del dizionario relativa alla prima istruzione del prossimo ramo da verificare, in modo da poter ricominciare correttamente l’esecuzione simbolica, e viene decrementato il contatore (k) della coppia [salto_condizionato_j, k] che si trova in testa al contesto.

Regola i2: ipd=0 (ipd uguale a 0)

Se il salto condizionato è pronto per esser chiuso, cioè l’istruzione raggiunta è un ipd e tutti i rami del relativo salto condizionato sono state verificate, allora è possibile rimuovere dal dizionario le entries che non sono più necessarie (cioè tutte le entries create quando il salto condizionato era stato aperto) e la coppia [salto_condizionato_j, 0] che si trova in testa al contesto (per indicare che il salto condizionato è chiuso).

In figura 3.8 è mostrato un esempio di applicazione delle regole dell’ipd.

START 0 2 END 5 6 9 12 14 ipd₌₀ START 0 2 END 5 6 9 12 14 ipd_≠0 istruzioni verificate istruzioni da verificare istruzione corrente i i i

3.4 Dizionario senza frames duplicati

Consideriamo un esempio di bytecode di cui nella figura è riportato il grafo.

284 234 242 180 164 192 204 216 225 251 260 269 278 239 248 189 177 201 213 222 231 257 266 275 281 97

fig. 3.9: switch a 12 vie

Siamo in presenza di uno switch a 12 vie (11 targets e un successore naturale): se il codice fosse solo quello riportato l’algoritmo standard memorizzerebbe nel dizionario 11 entries, una per ogni target, mentre l’algoritmo basato sull’ipd ne memorizzerebbe 12, una per ogni target ed una per l’ipd.

La cosa che più stupisce è che un metodo così semplice riesca a mettere in crisi entrambi gli algoritmi di verifica: gli switch fanno infatti crescere a dismisura il numero di entries del dizionario. Analizziamo più in dettaglio come si comporta l’algoritmo di verifica basato sull’ipd per comprendere dove è il problema e come risolverlo: quando si giunge all’istruzione 97 (tableswitch) si applica la regola , cioè di salva un frame per ogni target, un null-frame per l’ipd, si aggiunge

al contesto la coppia [97:tableswitch, 11] e si procede con la verifica del successore naturale. Questo passo è illustrato in figura 3.10.

234 242 180 164 192 204 216 225 251 260 269 278 97 Dizionario [ 97 , 11 ] Contesto 284 A 234 A 180 A 242 A 192 A 251 A 204 A 260 A 216 A 269 A 225 A 278 A 97 A out-frame dell'istruzione n A in-frame dell'istruzione n* *La lettera ne specifica il contenuto; se non

presente il frame è vuoto (null-frame) n n istruzioni verificate istruzioni da verificare istruzione corrente i i i

fig. 3.10: Regola branch_∉

Per 12 volte l’ipd (284) viene raggiunto: le prime 11 si applica la regola ipd≠0, come

mostrato in figura 3.11. 234 242 180 164 192 204 216 225 251 260 269 278 97 Dizionario [ 97 , 2 ] Contesto B 284 A 234 A 180 A 242 A 192 A 251 A 204 A 260 A 216 A 269 A 225 A 278 284 239 248 189 177 201 213 222 231 257 266 275 281

L’ultima volta invece la ipd=0 e si dealloca tutto il dizionario e la coppia

[97:tableswitch, 0] dal contesto (vedi figura 3.12).

234 242 180 164 192 204 216 225 251 260 269 278 97 Dizionario Contesto B 284 A 234 A 180 A 242 A 192 A 251 A 204 A 260 A 216 A 269 A 225 A 278 284 239 248 189 177 201 213 222 231 257 266 275 281 [ 97 , 0 ]

fig. 3.12: Regola ipd=0

Ciò che risulta evidente è che i frames salvati nel dizionario non sono mai stati modificati durante l’esecuzione simbolica delle istruzioni dei rami, a parte quello dell’ipd: le entries dei targets sono servite solo per salvare gli in-frames per poter ricominciare correttamente la verifica di ogni ramo. Il “reale” contenuto di tali

entries altro non è che l’out-frame del salto condizionato, salviamo cioè 11 volte la

stessa identica informazione nel dizionario. Salvare in-frames diversi per diversi

targets è una cosa che in generale occorre fare perché a-priori non è possibile

sapere se durante l’intero processo di verifica tali frames restano identici: ad esempio un target dello switch potrebbe essere anche target di una istruzione di salto, ad esempio di una istruzione if, di un altro ramo dello switch e questo potrebbe portare ad una modifica del frame (vedi figura 3.13).

22 4 6 { lub(A,C)=C } 9 Dizionario A 14 22 C 14 12 A 4 istruzioni verificate istruzioni da verificare istruzione corrente A out-frame dell'istruzione n A in-frame dell'istruzione n*

*La lettera ne specifica il contenuto; se non presente il frame è vuoto (null-frame) n n i i i 8 C 9

fig. 3.13: L’in-frame di un target può cambiare durante la data-flow analysis

Ciò che possiamo sicuramente affermare è però che subito dopo l’esecuzione dello

switch tutti gli in-frames dei targets sono identici; quindi è sufficiente memorizzare

un solo frame nel dizionario, e farlo “puntare” da più istruzioni: in questo modo se eventualmente durante la data-flow analysis il frame di uno o più targets dovesse cambiare siamo in grado di tenerne conto.

Gestire un dizionario con una politica del genere è leggermente più complesso ma porta grandi vantaggi per quanto riguarda l’occupazione in memoria: ad esempio verificando il metodo processCompleteUpdate(...) con tale strategia la dimensione massima del dizionario sarebbe stata pari ad 1 perché il frame dell’ipd, quando viene creato “realmente” applicando la regola ipd≠0, risulta essere identico

a quello dei targets (il null-frame iniziale dell’ipd non viene “realmente” allocato). Questa gestione del dizionario può essere ovviamente utilizzata con successo anche nella verifica standard: tenendo conto del fatto che il codice delle applets, in particolare quello della Java Cards, è “piccolo” si può osservare infatti che i frames sono molte volte identici. Il principio è simile a quello utilizzato nelle cache, cioè è possibile notare una sorta di località spaziale e temporale nella tipologia di operazioni effettuate in prossimità delle diramazioni e ricongiungimenti dei rami del

control-flow graph. Con l’algoritmo di verifica basato sull’ipd la località delle

operazioni viene accentuata perché la data-flow analysis procede “a blocchi” ed appena si esce da un blocco tutti i frames (non più necessari) vengono cancellati.

3.5 BCEL

Il BCEL (Byte Code Engineering Library) [BCEL98] è un insieme di APIs (Application Programming Interfaces) che consentono di leggere, creare e modificare il codice assemblato dei file class di Java. Utilizzando il BCEL abbiamo quindi a disposizione un toolkit per lavorare ad alto livello con il bytecode e non dobbiamo preoccuparci dei dettagli implementativi della compilazione o di implementare un parser. Come vedremo più in dettaglio in seguito, ad ogni file class viene associato un oggetto JavaClass che contiene tutte le strutture dati che caratterizzano un file class binario, come ad esempio la tabella dei simboli (nomi delle variabili, delle costanti, dei metodi,…), i diritti di accesso ad attributi e metodi, ed ovviamente le istruzioni dei metodi.

Scritto da Markus Dahm [MarkusDahm], il BCEL è realizzato interamente in Java ed il codice sorgente è liberamente utilizzabile rispettando le condizioni delle licenze LGPL (GNU Less General Public License) e Apache; è stato inoltre utilizzato con successo in molti progetti, tra i quali compilatori, ottimizzatori, verificatori e analizzatori del bytecode. Il BCEL è composto da quattro packages:

- classfile: è il package che contiene il parser e le strutture dati per descrivere i vincoli strutturali di un file class;

- generic: è il package che consente di generare e modificare gli oggetti JavaClass;

- util: contiene classi di utilità varia, come ad esempio un viewer dei file class ed un tool per convertire i file class in formato HTML

- verifier: è il top-level del verificatore polivariante implementato da Enver Haase [EnverHaase]; espande e completa le APIs del BCEL.

BCEL e JustIce costituiscono quindi uno strumento per analizzare, creare e modificare i file class binari di Java offrendone una visione object-oriented.

Il package org.apache.bcel.verifier costituisce il top level del JustIce. JustIce è un verificatore di file class implementato da Enver Haase nel 2001: effettua una verifica polivariante del bytecode seguendo le linee guida espresse nelle specifiche Java 2 della Sun [vmspecv2]. La verifica polivariante è un particolare tipo di analisi

che risulta “necessaria” quando il bytecode contiene delle subroutines: le

subroutines sono la traduzione degli statements finally del codice Java e vengono

in genere utilizzate verso la “fine del codice” per compiere operazioni di “chiusura”, ad esempio chiusura di file aperti o di connessioni TCP; come si vedrà la verifica delle subroutines rende complicata la verifica strutturale ed ha reso necessaria una implementazione particolare del dizionario.

Nel package sono state implementate 5 classi con un main(String[]): una è il

main del verificatore vero e proprio (Verifier), le altre sono esempi che

chiariscono il funzionamento del JustIce e che consentono di confrontarne i risultati con la versione del verificatore (Sun, Microsoft,...) installata sulla macchina host. Il JustIce associa ad ogni file class un oggetto Verifier. Per effettuare i vari passi della verifica il Verifier crea istanze di PassVerifier: ogni passo della verifica ha quindi un oggetto che lo identifica che è in grado eseguire una parte dell’algoritmo e di lanciare messaggi per segnalare successo o fallimento del processo. Le classi che effettuano i controlli statici sul file class si trovano nel package statics mentre quelle per fare i controlli strutturali si trovano nel package structurals. Il package exec contiene classi per la gestione dei messaggi di eccezione, cioè violazione di qualche vincolo da parte del bytecode esaminato, lanciati durante la verifica.

Tutte le classi necessarie per verificare i vincoli statici di un file class sono contenute nel package statics: sono quindi presenti le classi per i primi passi della verifica (Pass1Verifier, Pass2Verifier, Pass3aVerifier), le strutture dati per rappresentare le variabili locali (nome e tipo contenuto di ognuna di loro) ed alcune altre classi utili per la rappresentazione dei tipi di dati Long e Double, questi infatti hanno una occupazione di memoria doppia rispetto agli altri tipi di dati quindi devono essere gestiti in modo particolare (occuperanno 2 variabili locali: la “parte bassa” sarà memorizzata nella variabile ri e la “parte alta” in ri+1).

Viene proposta una rapida analisi dei controlli effettuati nei primi 3 passi del JustIce.

Pass1Verifier controlla i vincoli statici indicati nel primo passo delle specifiche Java 2, controlla cioè che il file class che sta per essere caricato dal loader della JVM non contenga evidenti problemi di integrità.

Pass2Verifier effettua il passo 2 delle specifiche della Sun: controlla l’integrità del contenuto della tabella dei simboli, la correttezza della gerarchia delle classi, la

validità dei nomi e dei descrittori utilizzati, effettua cioè tutti i controlli che è possibile fare senza guardare le istruzioni del bytecode.

Pass3aVerifier compie tutti gli ultimi controlli statici necessari prima di cominciare la data-flow analysis [vmpecv2 4.9.1, Pass 3] ed i controlli del passo 4 delle specifiche della Sun [vmpecv2 4.9.1, Pass 4]. Il passo 4 viene effettuato ora perché contiene controlli che vengono effettuati al run-time ed il JustIce, non facendo parte della JVM installata sul sistema, non potrebbe quindi effettuarli. Comunque il passo 4 è un passo “virtuale”, cioè ritarda semplicemente dei controlli (che potevano esser fatti nel passo 3) per ragioni di efficienza (i primi 3 passi della Sun infatti non richiedono il caricamento dell’intero file class) quindi “anticipare” questi controlli non va contro le specifiche e comunque non crea problemi.

3.6 Struttura del Verificatore ipd

L’algoritmo di verifica del bytecode basato sull’ipd è implementato sulla struttura di alcune classi del JustIce. Mentre il control-flow graph rimane piuttosto simile, la

data-flow analysis diventa più complessa a causa delle regole dell’algoritmo ipd da

dover rispettare durante la verifica.

3.6.1 Il Control-flow graph del verificatore ipd

Ogni metodo da verificare è caratterizzato da un control-flow graph e questo viene rappresentato da una istanza della classe CFGraph:

public class CFGraph{

private class InstrContext implements InstructionContext{...}

private class TheDictionary{...}

private HashMap dictionary;

private HashMap currentInFrame;

private final MethodGen method_gen;

private final Subroutines subroutines;

private final ExceptionHandlers exceptionhandlers;

private Hashtable instructionContexts;

...

public InstructionContext[] getSuccessors();

public InstructionContext getImmediateSuccessor(InstructionContext ic){

public InstructionContext contextOf(InstructionHandle inst);

public final InstructionHandle getIPD(InstructionHandle ih);

public final HashMap getCBIPDs();

public final void dominators(boolean reverse);

public InstructionContext[] getInstructionContextsSorted();

public final void viewInstructions();

... }

Analizziamone le principali caratteristiche:

• Il dizionario viene salvato in una struttura chiamata dictionary. È presente il

caching dei successori.

• il dizionario è implementato dalla classe TheDictionary

• è presente l’attributo currentInFrame, nel JustIce questo veniva creato solo nella data-flow analysis

• sono presenti i metodi per il calcolo dell’ipd; in particolare:

o getCBIPDs(): restituisce l’ipd di tutti i salti condizionati tali che l’ipd sia diverso dal nodo END;

o getIPD(InstructionHandle ih): restituisce l’ipd dell’istruzione passata come parametro

Entrambi i metodi saranno modificati in questo lavoro per permettere il calcolo dell’ipd in casi in cui sono presenti subroutines;

• il metodo execute(...) esegue simbolicamente una istruzione, questo è stato implementato in modo differente rispetto a quello del JustIce: dopo aver verificato i controlli strutturali esegue simbolicamente l’istruzione ed aggiorna il currentInFrame del CFGraph. Non viene effettuato nessun merge: l’in-frame buono da utilizzare per eseguire simbolicamente l’istruzione viene scelto tra quello passato come parametro ed il currentInFrame, ovvero se il frame passato come parametro vale null allora viene utilizzato il currentInFrame. Il metodo che si occupa di passare l’in-frame alla execute(...) è ovviamente la circulationPump(...) perché solo il data-flow analyzer ha una visione globale dello stato della verifica e quindi sa quando il frame deve essere preso dal dizionario (ad esempio quando viene eseguito un nuovo ramo di un salto condizionato) o quando è buono il currentInFrame (ad esempio nella esecuzione di codice senza salti condizionati).

• Il metodo getSuccessors() restituisce un vettore di InstructionContext(s), cioè di nodi del grafo: contiene il successore naturale e tutti gli eventuali targets dell’istruzione; può lanciare eccezioni, in particolare questo avviene se il metodo viene invocato su istruzioni ret: questa scelta è stata fatta perché i vincoli strutturali imposti sulle subroutines devono essere accuratamente valutati e, potendo cambiare da implementazione a implementazione, è bene farli con metodi ad-hoc; bisogna tener presente infatti che il successore di una ret è contenuto nel registro specificato come parametro, ad esempio r0 se l’istruzione

è ret_0, e quindi, a seconda dei vincoli che si vogliono imporre, è necessario ricostruire la catena di esecuzione (execution chain) per poter controllare se la coppia jsr-ret è valida. Questo è il metodo che verrà riscritto in questo lavoro in modo da gestire bytecode in cui sono presenti subroutines.

• Il nodo del grafo è implementato dalla classe InstrContext.

• La classe InstructionContextImpl viene implementata come classe privata del CFGraph quindi dall’esterno è possibile utilizzare solo i metodi forniti

dall’interfaccia InstrContext: questo va bene, perché solo i metodi del ControlFlowGraph devono gestire determinati aspetti della struttura dei nodi (ad esempio il caching dei successori o la lista delle jsr effettuate fino a quel momento). InstrContext InstructionHandle Instruction e xe cu ti on P re de ce sso rs instruction instruction prev next InstructionHandle InstructionHandle lenght opcode ( istruzione precedente nel bytecode ) ( istruzione successiva nel bytecode ) cachedSuccessors TAG cache_ipd TAG InstructionHandle InstrContext ( istruzioni successive nel grafo ) ( ipd dell'istruzione )

fig.3.14: Struttura dei nodi del grafo (InstrContext) e loro relazione con le istruzioni del bytecode

• Per la la gestione del caching dei nodi è presente anche un bit di validità per successori e ipd: cacheTAG e ipdcacheTAG.

• Il metodo contextOf serve a recuperare un nodo del grafo partendo dal parametro InstructionHandle dell’istruzione richiesta.

• Il metodo dominators(…) si occupa di calcolare i dominanti dell’istruzione corrente per il calcolo dell’ipd, sarà invocato da getCBIPDs(); priorità dell’algoritmo ipd non è il tempo di esecuzione, ma la minimizzazione dello spazio di memoria richiesto per le strutture dati durante il calcolo dell’ipd;

Le strutture dati del dizionario sono pensate per associare ad ogni istruzione (presente nel dizionario) un in-frame: per fare questo in linea di principio basterebbe una semplice tabella che ha come chiave l’istruzione e come valore

l’in-frame, ma in questo modo non si ha una memorizzazione efficiente a causa dei

potenziali frames duplicati. Per risolvere questo inconveniente la tabella è stata divisa in due: c’è un indice che contiene la lista delle istruzioni del dizionario (dictionaryIndex) ed una che memorizza gli in-frames (frameIndex).

private class TheDictionary{

private class Index{...}

private HashMap dictionaryIndex;

private HashMap frameIndex;

private void updateMaxDictionarySize();

private boolean dictionaryMerge(InstructionHandle ih, Frame inFrame);

public Frame dictionaryGetFrame(InstructionHandle ih);

public void dictionaryRemoveUnusedEntries(ArrayList rem); public boolean dictionaryContains(InstructionHandle ih); public boolean dictionaryAddIPD(InstructionHandle ih); public boolean dictionaryAdd(InstructionHandle ih);

...

}

I metodi dictionaryGetFrame(…) e dictionaryContains(…) servono ad accedere alle informazioni contenute nel dizionario, i restanti metodi servono per modificare,aggiungere e rimuovere le entries del dizionario, in particolare dictionaryMerge(…) si occupa di fare il merge nel dizionario tra il frame dell’istruzione corrente e il frame contenuto nel dizionario (se presente).

3.6.2

La data-flow analysis del verificatore ipd

I controlli strutturali e la data-flow analysis vengono implementate dalla classe Pass3bIPDVerifierOpt. Esaminiamone la struttura:

public class Pass3bIPDVerifierOpt extends PassVerifier {

private class WKList{...}

private ArrayList workList;

private int method_no;

private void circulationPump(...);

public VerificationResult do_verify();

public int getMethodNo();

...

}

Pass3bIPDVerifierOpt offre solo due metodi pubblici, do_verify() e getMethodNo(), che hanno il compito di lanciare il passo della verifica e di restituire il numero del metodo che si sta processando, rispettivamente.

La gestione della coda istruzioni è implementata dalla classe WKList: compito di questa classe non è solo mantenere la lista delle istruzioni, ma anche memorizzare le informazioni del contesto, cioè le coppie [salto_condizionato_j, m_branch] come indicato nell’algoritmo di verifica basato sull’ipd. In particolare questa informazione è integrata nella struttura della worklist attraverso una implementazione di questa come uno stack di code. Ogni coda viene quindi associata ad un salto condizionato: ogni volta che un salto condizionato viene aperto viene creata una nuova coda nella

worklist. Ogni coda della worklist rappresenta un salto condizionato aperto ed il

numero di istruzioni contenute nella coda è proprio il numero di branch che restano da verificare per il salto condizionato. Un esempio è mostrato in figura 3.15.

404 385 388 401 417 414 376 411 373 worklist START END 414 385 404 388 istruzione corrente

prima istruzione del prossimo ramo da

verificare

questa coda è vuota perché si sta esaminado

l'ultimo ramo della 414 owner della coda

istruzioni verificate istruzioni da verificare istruzione corrente i i i

fig. 3.15: Worklist durante una esecuzione simbolica delle istruzioni

Esaminiamone in dettaglio la struttura:

private class WKList{

private int qe;

private final class InstructionQueue{...}

private ArrayList workList;

public void addQueue(); public void removeQueue();

public boolean currentQueueIsEmpty(); public boolean isEmpty();

...

public InstructionHandle nextInstruction();

public InstructionContext popInstruction();

public void pushInstruction(InstructionContext instr);

public void setQueueOwner(InstructionHandle ih); public void restartFromQueueOwner(...);

public boolean cbNotClosed(...);

... }

L’attributo intero privato qe (queue elements) è utilizzato per mantenere il conto di quante istruzioni restano in totale da verificare. Lo stack di code è implementato come un ArrayList di oggetti InstructionQueue: ogni InstructionQueue è caratterizzato da una coda di nodi, da un owner della coda, cioè il salto condizionato che ha “generato” la coda, e da un vettore che individua quali sono le

entries del dizionario create quando è stata generata la coda.

La classe offre tutti i metodi necessari per la gestione della coda e delle informazioni del contesto integrate; analizziamone i principali metodi:

• addQueue() e removeQueue() aggiungono e rimuovono una coda; in particolare removeQueue() manda anche un messaggio di errore se si tenta di rimuovere una coda non vuota: una coda viene rimossa solo se il salto condizionato è chiuso, cioè se tutti i rami sono stati verificati, ovvero solo se la coda corrente (dello stack di code) è vuota;

• currentQueueIsEmpty() e queueIsEmpty() restituiscono un booleano e verificano rispettivamente se la coda in cima allo stack (di code) della workList è vuota e se la worklist è vuota (qe==0);

• nextInstruction() restituisce la prossima istruzione da eseguire: è un metodo comodo da utilizzare nella circulationPump(...) per caricare dal dizionario il

frame della prima istruzione del prossimo ramo di un salto condizionato aperto

da verificare; questo metodo non modifica la workList.

• popInstruction() e pushInstruction() modificano la workList effettuando, rispettivamente, il pop ed il push di una istruzione nella coda in testa alla workList.

• setQueueOwner(...) permette di assegnare un owner ad una coda; le code vengono create solo in seguito all’apertura di un salto condizionato. E’ necessario sapere esattamente quali sono i salti condizionati aperti per applicare correttamente le regole specificate nell’algoritmo di verifica basato sull’ipd.

•

condizionato da rieseguire) ed elimina dal dizionario tutte le entries create all’apertura dei salti condizionati che vengono estratti dal contesto.

•

Analizziamo ora la struttura della classe InstructionQueue:

private final class InstructionQueue{

private ArrayList queue;

private ArrayList CDEntries;

private ArrayList ec;

private InstructionHandle owner;

public int size(); public boolean isEmpty();

public ArrayList getEC();

public void addCDEntry(InstructionHandle ih); public void removeCDEntry(InstructionHandle r); public ArrayList viewCDEntries();

public void pushInstruction(...);

public InstructionContext popInstruction();

public InstructionHandle nextInstruction();

public void setQueueOwner(InstructionHandle ih) public InstructionHandle getQueueOwner();

...

}

Alcuni metodi hanno nomi identici a quelli della WKList: sono in particolare i metodi per la gestione della singola coda. Alcuni metodi della WKList infatti non fanno altro che fare sanity checks (ad esempio prima di fare il pop di una istruzione controllano che esistano istruzioni) per poi invocare il metodo omologo della InstructionQueue. I campi privati sono:

• CDEntries: (created dictionary entries) serve a memorizzare quali sono le

entries del dizionario create quando il salto condizionato (owner della coda

InstructionQueue) è stato aperto;

• ec: memorizza le execution chains delle istruzioni presenti nella coda; è molto utile per il debugging dell’algoritmo e per tracciare le istruzioni che hanno prodotto il fallimento nella verifica;

• owner: memorizza il salto condizionato che ha “generato” la coda. Fa eccezione la coda numero 0, che appartiene sempre al top-level, che viene individuato con un puntatore null.

L’ultimo metodo che resta da esaminare è il “cuore” della classe Pass3bIPDVerifierOpt: la circulationPump(...). Come per il JustIce, questo metodo implementa la data-flow analysis: questa volta naturalmente viene implementata secondo le regole specificare nell’algoritmo di verifica basato sull’ipd. I parametri non sono cambiati: viene passato il grafo (CFGraph) del metodo da verificare, il suo nodo iniziale (start) ed il relativo in-frame (vanillaFrame) e due oggetti derivati dalla classe Visitor per fare i controlli strutturali (icv, instruction

constraint visitor) e l’esecuzione simbolica (ev, execution visitor).

La prima cosa da fare questa volta è inizializzare opportunamente il currentInFrame del grafo con la CFGinit(): prima veniva infatti inizializzato

l’in-frame della prima istruzione da eseguire perché il dizionario era integrato nei nodi.

La prima istruzione viene quindi aggiunta alla worklist e comincia il loop caratteristico della data-flow analysis: le istruzioni presenti nella worklist sono solo quelle che hanno il changed-bit che vale true.

Ad ogni ciclo viene prelevata una istruzione nell’ultima coda della worklist, oggetto di tipo WKList: la condizione di stop del ciclo è che non ci siano più istruzioni nella worklist. Ogni coda, come del resto anche la worklist, viene gestita con politica LIFO, ovvero come uno stack. Prima di poter eseguire l’istruzione è necessario controllare se siamo in presenza di un ipd o di un salto condizionato per poter applicare correttamente le regole dell’algoritmo proposto. Se non siamo in presenza di ipd o di salti condizionati si procede con un loop standard:

• vengono controllati i vincoli strutturali;

• viene eseguita simbolicamente l’istruzione (se la verifica dei vincoli ha successo);

• viene trovato il successore e messo nella coda in testa alla worklist;

Bisogna notare che, a differenza delle regole della Sun, nel verificatore ipd quando non si è in presenza di salti condizionati non viene mai effettuato il merge: un verificatore “standard” controllerebbe sempre se esiste un in-frame per il successore dell’istruzione (perché ad esempio potrebbe essere il target di una istruzione di salto), effettuerebbe il merge ed in base al risultato del merge deciderebbe se il changed-bit del successore deve esser messo a true. Fare il

merge anche per i targets dei salti incondizionati porta a due vantaggi

nell’algoritmo della Sun:

• funziona su qualsiasi grafo, anche quelli con nodi che non raggiungono il nodo END;

• ottimizza il tempo di verifica: viene evitata l’esecuzione di pezzi di codice che cominciano con istruzioni il cui frame è memorizzato nel dizionario (capita spesso nei salti all’indietro).

Memorizzare un frame per ogni target porta però a grossi inconvenienti nella verifica delle subroutines: infatti a causa del frame della istruzione che segue la jsr si ha una propagazione corretta dei tipi all’interno della subroutine, ma una propagazione inesatta alla sua fine (ma questa problematica si affronterà nel capitolo 4).

Nell’algoritmo proposto il merge viene solo effettuato per l’ipd e per i targets dei salti condizionati. Le condizioni di stop sono espresse nella regola branch≠.

Se si è in presenza di una istruzione di salto condizionato bisogna controllare se il salto condizionato viene incontrato per la prima volta: questo viene fatto con il metodo seenQueueOwner(...) della WKList, basta infatti controllare gli owner(s) delle altre code presenti nella worklist. Quando il salto condizionato viene incontrato per la prima volta, in seguito al controllo dei vincoli strutturali ed all’esecuzione simbolica dell’istruzione, viene creata una nuova coda nella worklist

(questa operazione corrisponde alla immissione di una coppia nel contesto) e vi vengono immessi i successori.

Se il salto condizionato era già stato incontrato si procede al test sui targets con il metodo testSuccessorsFrame(...) della classe CFGraph: se i frames del dizionario cambiano allora bisogna ripetere l’esecuzione del salto condizionato (e di tutti i salti condizionati annidati al suo interno), bisogna cioè eliminare dalla worklist tutte le code fino a quella del salto condizionato incontrato (il che corrisponde ad eliminare tutte le coppie dal contesto, fino a quella del salto condizionato da ripetere) ed eliminare dal dizionario tutte le entries create all’apertura dei salti condizionati. Tutte queste operazioni vengono effettuate dalla restartFromQueueOwner(...) della classe WKList. Se invece i frames (salvati nel dizionario) dei targets del salto condizionato non cambiano si salta direttamente all’ipd dell’ultimo, in ordine di esecuzione, salto condizionato aperto (regola

branch=): l’ultimo salto condizionato aperto è proprio l’owner della coda corrente.

Se si è in presenza dell’ipd del salto condizionato aperto è necessario controllare se è possibile eseguirlo o se si deve rimandare l’esecuzione perché restano rami da eseguire. Se tutti i rami del salto condizionato non sono stati eseguiti allora la coda “creata” dal salto condizionato contiene ancora istruzioni: si rimanda quindi l’esecuzione dell’ipd e si carica nel currentInFrame il frame salvato nel dizionario relativo alla prima istruzione del prossimo ramo da eseguire (regola ipd≠0). Se

invece la coda è vuota possiamo eliminarla, cancellare dal dizionario tutti i frame dei targets che non occorrono più (questo corrisponde a togliere dal contesto la coppia [j,0] relativa al salto condizionato che stiamo chiudendo, ed all’operazione

D espressa nelle regole riportate nell’appendice) e “potenzialmente” eseguire l’ipd: per capire se l’ipd può essere eseguito bisogna controllare che nessun altro salto condizionato del contesto abbia lo stesso ipd; basta quindi controllare, come al solito, gli owner(s) delle code nella worklist: il controllo viene svolto dal metodo cbNotClosed(...) della classe WKList. Questo controllo è espresso implicitamente nella regola ipd

'

↓_c

=0 perché l’istruzione non viene prelevata (cosa che invece viene

fatta nell’implementazione) e quindi viene fatto più volte il controllo i=ipd(top(c)). Ogni volta che si giunge all’ipd si deve comunque fare il merge tra il currentInFrame ed il frame dell’ipd salvato nel dizionario.

I controlli sull’ipd e sui salti condizionati possono essere omessi se nessun salto condizionato è aperto, cioè se siamo al top-level del metodo (owner==null).

In definitiva una versione semplificata della circulationPump(...) è la seguente:

private void circulationPump( CFGraph cfg, InstructionContext start,

Frame vanillaFrame, InstConstraintVisitor icv, ExecutionVisitor ev){

HashMap ipds = cfg.getCBIPDs(); WKList workList = new WKList(); cfg.CFGInit(vanillaFrame); workList.pushInstruction(start); ArrayList ec = new ArrayList(); while(!workList.isEmpty()){

InstructionContext currentInstruction = workList.popInstruction();

boolean execInstruction = true;

InstructionHandle qh = workList.getQueueOwner(); if((InstructionHandle)ipds.get(qh)==currentInstruction.getInstruction()){ while( ((InstructionHandle)ipds.get(qh)==currentInstruction.getInstruction()) && ((workList.currentQueueIsEmpty()))

{_{< regola ipd}=0 >; qh = workList.getQueueOwner();}

if(!(workList.currentQueueIsEmpty()){execInstruction = false;}

else if(workList.cbNotClosed(currentIPD, cfg)){execInstruction = false;} }

if(execInstruction == false){_{< regola ipd}≠0 >}

else{

currentInstruction.execute(null, ec, icv, ev);

InstructionContext[] successors = currentInstruction.getSuccessors();

if(successors.length>1){

if(workList.seenQueueOwner(currentInstruction.getInstruction())){

if(cfg.testSuccessorFrame(successors[i].getInstruction())==true){ < regola branch= >

}

else{_{< regola branch≠ >}} } else{ branch∉ < regola > } } else if(successors.length==1){workList.pushInstruction(successors[0]);} } }

Nella implementazione “completa” vengono inoltre effettuati vari sanity checks e controlli aggiuntivi per gestire il caso di ipd uguale a END: il nodo END infatti è un nodo virtuale e vale null e per questo non può esser messo nella coda di esecuzione: bisogna quindi prestare attenzione all’applicazione delle regole.