Implementazione
5.1 Il
nuovo
control-flow graph
Per la gestione delle subroutines si è modificata la struttura del Control-flow Graph e della data-flow analysis con l’aggiunta di alcuni metodi (il più importante getSuccessors_ipd) e di vari controlli per la correttezza delle operazioni rispetto alle regole specificate riguardanti le subroutines. Alcuni controlli relativi ai vincoli strutturali imposti, sono stati implementati in questi metodi, altri sono stati importati direttamente dal JustIce.
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;
private ArrayList retPoint;
private HashMap realIPD;
private InstructionHandle lastJSR;
private ArrayList visited = new ArrayList();
private boolean mergeFrames(Frame f1, Frame f2){ ...
public InstructionHandle[] getSuccessors();
public InstructionHandle[] getSuccessors_ipd();
public InstructionContext getImmediateSuccessor(InstructionContext ic){
public InstructionContext contextOf(InstructionHandle inst);
public void lastJsr(InstructionContextImpl current);
private void CBrealIPD (InstructionContextImpl curr);
private void searchCB(InstructionHandlecurrent, InstructionHandle target,
InstructionHandle jsrP, ArrayList visitedCB);
public final InstructionHandle getIPD(InstructionHandle ih);
public final HashMap getCBIPDs();
public InstructionContext[] getInstructionContextsSorted();
public final void viewInstructions(); ...
}
Analizziamo i campi privati di CFGraph inseriti per la gestione delle subroutines:
• realRetPoint di tipo InstructionHandle[] e retPoint una lista di
elementi di tipo InstructionHandle, entrambi saranno utilizzati per memorizzare i successori dell’istruzione ret, nel calcolo dell’ipd retPoint conterrà tutti i possibili successori dell’istruzione ret, nella data-flow
analysis realRetPoint conterrà il reale (ed unico) successore della ret.
• realIPD di tipo HashMap è una tabella Hash che sarà utilizzata per memorizzare gli ipd reali dei salti condizionati appartenenti ad una
subroutine e che inizialmente hanno ipd uguale a END.
• lastJSR di tipo InstructionHandle servirà per i controlli relativi all’annidamento tra subroutines.
• visited è un ArrayList che servirà per evitare loop nella ricerca tra i predecessori dell’istruzione jsr, tale lista conterrà i nodi già visitati all’interno dell’albero corrente.
I metodi principali della classe CFGraph aggiunti o modificati sono:
• getSuccessors() è stata modificata in modo tale da calcolare i successori anche nel caso di istruzioni ret e jsr, questa verrà invocata durante la
data-flow analysis.
• getSuccessors_idp() è una variante della getSuccessors, come suggerisce il nome questa verrà invocata durante il calcolo dell’ipd, restituirà i tutti i possibili successori dell’istruzione ret in più controlla alcuni vincoli di tipo strutturale.
• lastJsr(…) è un metodo che ritorna l’ultima istruzione jsr incontrata, se successivamente alla jsr non ci sono istruzioni di ret o return significa che l’istruzione corrente è interna ad una subroutine.
• CBrealIPD(…) e searchCB(…) sono i metodi che si occupano di rintracciare nel bytecode i salti condizionati appartenenti ad una subroutine e di riempirne la relativa HashMap realIPD, aggiungendo la coppia <jsrPoint , next>, jsrPoint è la chiave e next rappresenta il successore dell’istruzione ret che diverrà il nuovo ipd dei salti ottenuti.
• getIPD(…) è il metodo già presente nella versione precedente del verificatore e che è stato modificato aggiungendo la possibità di cercare all’interno di realIPD il vero ipd del salto condizionato appartenente ad una
subroutine.
• getCBIPDs(…) anch’esso presente nella versione precedente, nella nuova versione oltre a riempire l’HashMap degli ipd generale (ipds) si preoccupa di fare la chiamata a CBrealIPDs(…) ( che a sua volta invocherà searchCB ) che riempirà la realIPD.
Nei prossimi due paragrafi si analizza in dettaglio le caratteristiche dei metodi sopra elencati.
5.2 I metodi getSuccessors_ipd() e getSuccessors()
Come accennato la necessità di avere due funzioni che ricavano i successori della istruzione corrente è dovuta alla natura dell’istruzione ret, durante il calcolo dell’ipd i successori di una ret dovranno essere tutti i possibili successori ( perchè non si ha la possibilità in questa fase di conoscere il successore reale della ret), nella data-flow analysis invece il successore della ret è unico, tali calcoli saranno effettuati rispettivamente da getSuccessors_ipd() e getSuccessors().
Vediamo la parte di codice aggiunta per poter gestire le subroutines del metodo getSuccessors_ipd():
// _getSuccesssors_ipd
....
Instruction inst = getInstruction().getInstruction();
// nel caso di jsr semplicemente restituisce il suo target
// e aggiunge alla lista retPoint il successore fisico dell’ istruzione jsr
if (inst instanceof JsrInstruction){
/**
* setta a false le condizione di stop e di ricerca compiuta con successo * ripristina la lista visited e chiama il metodo lastJsr che andrà a cercare se * l’istruzione corrente (jsr) appartiene ad una subroutine in tal caso
* solleverà un eccezione */ bit = false; stop = false; visited.clear(); lastJsr(this); if(bit){
throw new StructuralCodeConstraintException("Tentato annidamento L'istruzione ["+inst+" ] è presente all'interno di una
subroutine.");
}
//single conterrà il target della jsr
single[0] = ((JsrInstruction) inst).getTarget();
if(single[0].getInstruction() instanceof ASTORE){
// se la prima istruzione della subroutine è una ASTORE // continua altrimenti solleva l’eccezione
InstructionHandle[] succ = new InstructionHandle[1]; succ[0] = this.getInstruction().getNext();
// Se la lista retPoint è null (perchè è la prima volta che si // incontra un istruzione jsr la si inizializza
if(retPoint == null){
retPoint = new ArrayList(); }
// Si aggiunge alla lista il successore della ret
retPoint.add(this.getInstruction().getNext());
//aggiorno cache
cachedSuccessors = single; cacheTAG = true;
// ritorna il target della jsr
return single; }
else{
throw new StructuralCodeConstraintException("La prima istruzione della Subroutine non è una ASTORE");
} }
...
if (inst instanceof RET){
// L’istruzione corrente è una ret
if(retPoint == null){
// Si è incontrato una istruzione ret e la lista retPoint vale null? // Eccezione
throw new StructuralCodeConstraintException("Punto di ritorno della RET
nullo?!");
}
/**
* In ret si copiano tutti gli InstructionHandle contenuti nella lista * retPoint (riempita ogni qualvolta s’incontrava una jsr relativa a la * stessa subroutine), infine la funzione ritorna ret.
*/
InstructionHandle [] ret = new InstructionHandle [retPoint.size()]
for (int i=0; i<retPoint.size(); i++){
ret[i] = (InstructionHandle) retPoint.get(i); }
// aggiorno cache
cacheTAG = true; cachedSuccessors = ret;
return (InstructionHandle []) ret; }
Il metodo getSuccessors_ipd() restituisce un vettore di InstructionHandle(s), cioè di nodi del grafo: contiene il successore naturale e tutti gli eventuali targets dell’istruzione, quando l’istruzione corrente è una jsr fa un controllo strutturale per
verificare che non ci sia un tentativo di annidamento e se la prima istruzione della
subroutine sia effettivamente una astore, successivamente aggiunge alla lista il
successore fisico della istruzione jsr e ritorna il suo target.
Se l’istruzione corrente è una ret il metodo controlla che la lista non sia nulla e successivamente ritorna tutti gli elementi lista riempita dal metodo stesso ad ogni jsr incontrata.
Quindi il metodo può lanciare eccezioni (di tipo StructuralCodeConstraintException) solo nei casi in cui l’istruzione corrente è una jsr o una ret e se si verifica uno dei seguenti casi:
− La prima istruzione della subroutine non è una astore
− È presente una istruzione jsr all’interno di una subroutine (tentato annidamento)
− È presente un’istruzione ret senza aver incontrato nel flusso una istruzione jsr
Il metodo getSuccessors() anch’esso ritorna un vettore di InstructionHandle(s) e può sollevare le eccezioni viste sopra, tale metodo viene invocato al momento della data-flow analysis ed essendo la verifica polivariante ottiene qual è il vero successore dell’istruzione ret.
// getSuccesssors
…..
Instruction inst = getInstruction().getInstruction();
if (inst instanceof JsrInstruction){
// Si salva il target nella variabile single
single[0] = ((JsrInstruction) inst).getTarget();
// Controllo che la prima istruzione della subroutine sia una ASTORE
if(single[0].getInstruction() instanceof ASTORE){
InstructionHandle [] succ = new InstructionHandle[1]; succ[0] = this.getInstruction().getNext();
// reale della jsr realRetPoint = succ; //aggiorno cache cachedSuccessors = single; cacheTAG = true; return single; } else{
throw new StructuralCodeConstraintException("La prima istruzione della Subroutine non è una ASTORE"); }
}
else if (inst instanceof RET){
// Aggiorna cache successori e ritorna realRetPoint
cachedSuccessors = realRetPoint; cacheTAG = true;
return realRetPoint; }
Nel caso in cui l’istruzione corrente è una jsr si salva nell’attributo realRetPoint il successore fisico della jsr , tale attributo sarà poi ritornato dal metodo come successore quando nel flusso l’istruzione corrente sarà una ret.
5.3 I metodi CBrealIPD(…), searchCB(…) e lastJsr(…)
Si riporta la parte del codice sorgente relativo ai metodi CBrealIDP(…) e searchCB(…):
private void CBrealIPD (InstructionContextImpl curr){
if(curr.getInstruction().getInstruction() instanceof JsrInstruction){
// inst contiene instruction jsr
Instruction inst = curr.getInstruction().getInstruction(); InstructionHandle jsrPoint = curr.getInstruction();
// next contiene il successore fisico della jsr
InstructionHandle next = curr.getInstruction().getNext(); // target è il target della jsr
InstructionHandle target = ((JsrInstruction) inst).getTarget();
// creo la lista per evitare di entrare in loop nella // visita dei predecessori
ArrayList visitedCB = new ArrayList();
// chiamo searchCB che cerchera all'interno della subroutine // se ci sono dei branch e ne salva la coppia <jsrPoint,target> // nella HashMap realIPD
searchCB(target,next,jsrPoint, visitedCB); }
}
private void searchCB(InstructionHandle current, InstructionHandle target, InstructionHandle jsrP, ArrayList visitedCB){
// sono all'interno di una subroutine
InstructionContextImpl currentIC = _contextOf(current);
if( current.getInstruction() instanceof ReturnInstruction || current.getInstruction() instanceof ATHROW){
//zero successori, nulla da fare.
return; }
//else
// successors conterra i successori
InstructionContext[] successors = currentIC.getSuccessors_ipd(); for(int i=0;i<successors.length;i++){
if(visitedCB.contains(successors[i])){
// nodo visitato esco dal for
break; }
visitedCB.add(successors[i]);
if(current.getInstruction() instanceof RET || current.getInstruction()
instanceof ReturnInstruction ){
// esco dal for perchè ho raggiunto la fine di un ramo ( se ci sono dei // dei salti condizionati) oppure alla fine della subroutine
break; }else { if(successors[i].getInstruction().getInstruction() instanceof BranchInstruction){ // branch!
InstructionHandle branch = successors[i].getInstruction();
InstructionContextImpl b = _contextOf(branch);
if(b.realIPD == null){ b.realIPD = new HashMap(); }
/**
* aggiungo a realIPD la coppia <jsrP,target>
* in modo da settare il giusto successore della ret * durante la data-flow- analysis
*/
b.realIPD.put(jsrP,contextOf(target)); }
// chiamata ricorsiva sui successori
searchCB(successors[i].getInstruction(),target,jsrP, visitedCB); }
} }
Il metodo CBrealIPD(…) viene invocato dalla funzione getCBIPDs(…), come accennato questo insieme al metodo searchCB(…) si preoccupa di cercare dei salti condizionati interni ad una subroutine e memorizzare il target della jsr che ha invocato la subroutine in una HashMap (realIPD), la stessa istruzione jsr sarà chiave di realIDP.
Precisamente CBrealIPD(…) entra in gioco solo se l’istruzione attuale che gli viene passato come parametro (di tipo InstructionContextImpl) è una jsr, quindi memorizza InstructionHandle della istruzione corrente (jsrPoint) del target della jsr (target) e del successore fisico della jsr (next), invoca la searchCB passando questi tre valori come parametri più la ArrayList (visitedCB) che servirà per evitare loop nella ricerca dei branch tra le istruzioni della subroutine. Il metodo searchCB(…) è ricorsivo e una volta ottenuto i successori e verificato che questi non siano già stati visitati controlla se ci sono istruzioni ret o return (fine della subroutine o di un ramo del salto appartenente alla subroutine) in tal caso termina la ricerca (a meno che ci siano dei nodi superiori che non sono ancora stati visitati e sono “pendenti”) o se ci sono salti condizionati in questo caso salva in realIDP la coppia <jsrPoint,target>.
Per ogni salto condizionato appartenente a subroutine in realIPD si avranno tante
entries quante sono le chiamate alla subroutine che contiene il salto. Durante la data-flow analysis ogni volta che si incontrerà il salto in questione e se questo avrà ipd END si andrà a recuperare il vero ipd da realIPD riempito precedentemente e
gli si assocerà il nuovo ipd (il valore target).
public void lastJsr(InstructionContextImpl current){
// in pred copio i predecessori di current
InstructionHandle[] pred = current._getPredecessors();
// size contiene il numero di predecessori
int size = pred.length; for (int i=size-1; i>=0; i--){ if(stop){
// si è incontrata la jsr il metodo deve terminare
return; }
InstructionContextImpl currentl = (InstructionContextImpl) _contextOf(pred[i]);
if(visited.contains(currentl)){
// il nodo è stato già visitato, si esce dal for
return; }
Instruction currentlast = currentl.getInstruction().getInstruction();
// Aggiungo a visited il nodo che si sta visitando
visited.add(currentl);
if (currentlast instanceof JsrInstruction){
// jsr trovata, setto a true bit e stop // non devo visitare altri nodi
bit = true; stop = true; lastJSR = pred[i]; return; } if(currentl._getPredecessors().length != 0){
// chiamata ricorsiva sul predecesssore
lastJsr(currentl); } } }
Il metodo lastJsr(…) è anch’esso ricorsivo ma a differenza di searchCB(…) non compie la ricerca sui successori ma sui predecessori. Come struttura è molto simile al metodo searchCB(…), ottiene i predecessori e va a controllare per ognuno di questi se è stato già visitato e nel caso che tra questi ci sia l’istruzione jsr termina la ricerca altrimenti compie la chiamata ricorsiva sul predecessore. Se la ricerca ha dato esito positivo la jsr ottenuta verrà memorizzata nell’attributo lastJSR.
5.4 Controlli sulle subroutines importati dal JustIce
Nel capitolo dedicato alle problematiche delle subroutines si è visto dell’importanza che assumono i controlli strutturali nella verifica, più bachi si hanno nel codice del verificatore più aumentano le possibilità che bytecode maliziosi possano essere considerati corretti.
Si è anche visto che il metodo getSuccessors_ipd() durante il calcolo dei successori si occupa dei controlli riguardanti tre vincoli strutturali:
− La prima istruzione della subroutine deve essere una astore
− Non deve essere presente una istruzione jsr all’interno di una subroutine (tentato annidamento)
− L’istruzione ret deve essere preceduta nel grafo da una istruzione jsr
Gli altri controlli sui vincoli strutturali relativi alle subroutines non sono stati modificati rispetto all’implementazione del JustIce. Nel JustIce una subroutine è un istanza della classe Subroutines costituita da diversi metodi utili per la gestione delle subroutines.
Andiamo ad analizzare i metodi della classe Subroutines che operano i vari controlli:
• setLeavingRET(…) è il metodo che opera i seguenti controlli:
o All’interno della subroutine deve essere presente una sola istruzione ret
o L’istruzione ret deve prelevare l’indirizzo di ritorno dalla corretta variabile di controllo (ovvero se la prima istruzione della subroutine è astore 2 l’istruzione che termina la subroutine deve essere ret 2).
In caso che i vincoli di sopra non siano rispettati il metodo solleverà un eccezione del tipo StructuralCodeConstraintException.
• noRecursiveCalls(…) è il metodo che controlla che non ci siano chiamate ricorsive tra subroutines, in caso contrario solleva un eccezione di tipo StructuralCodeConstraintException.
• Subroutines() è il costruttore, controlla tra le varie operazioni che la
subroutine non sia protetta da gestori di eccezione anche questo in caso che
il vincolo non è rispettato solleva un eccezione di tipo StructuralCodeConstraintException.
5.5 La nuova data-flow analysis
Si è visto nel capitolo dedicato alla descrizione del verificatore ipd che il cuore della verifica, della data-flow analysis è il metodo circulationPump(…), il metodo è anche presente nel verificatore JustIce ma all’interno del verificatore ipd è chiaramente più complesso a causa delle varie regole imposte dall’algoritmo ipd. Le modifiche apportate al metodo in questo lavoro sono relative alla gestione dei salti condizionati interni ed esterni alla subroutine, consideriamo la parte di codice relativa all’ottimizzazione per i salti condizionati interni ad una subroutine1:
private void circulationPump(ControlFlowGraph cfg, InstructionContext start, Frame vanillaFrame, InstConstraintVisitor icv, ExecutionVisitor ev){
// In ipds memorizzo tutti gli ipd delle istruzioni ( che sono diversi da END)
HashMap ipds = cfg.getCBIPDs();
/**
* se l'istruzione attuale è una JSR devo settare il campo statico currentJSR. * curretnJSR serve alla getIPD per restituire il punto di ritorno corretto. *
*/
if(currentInstruction.getInstruction().getInstruction() instanceof JsrInstruction){ currentJSR = currentInstruction.getInstruction(); } if(currentInstruction.getInstruction().getInstruction() instanceof BranchInstruction){ /**
* se l'ipd di un salto condizionato è END e currentJSR != null allora * sono dentro una subroutine (currentJSR non viene resettato quando si esce dalla * subroutine.
* Questo non crea problemi alla getIPD perché se un salto condizionato è al di * fuori della
* subroutine l'hashmap realIPD vale null, quindi restituirà l'ipd corretto). * Se sono dentro la subroutine provo a migliorare l'ipd invocando la getIPD * (invece
* di prendere l'ipd direttamente dalla tabella ipds riempita all'inizio della * circulationPump da getCPIPDs.
*/
/**
* controllo se l'ipd vale END, cioè il salto condizionato non è presente nella * tabella ipds */ if(! ipds.containsKey(currentInstruction.getInstruction()) ){ /** * nuovo ipd
* Il metodo getIPD mi restituisce l’ipd reale, controlla se realIPD è != * da null e in tal caso ritorna il valore memorizzato nella realIPD
*/
InstructionContext newIPD = currentInstruction.getIPD();
//sanity check if(newIPD==null){ //errore System.exit(1); }
if(newIPD.getInstruction().getInstruction() instanceof EndInstruction){ //Il nuovo ipd è END. Do nothing!
else{
/**
* modifico l'ipd solo se sto verificando l'ultimo ramo del salto * condizionato
* aggiungo l'ipd alla tabella Hash ipds */
ipds.put(currentInstruction.getInstruction(), newIPD.getInstruction()); }
} }
boolean execInstruction = true; ….
}
Quindi la circulationPump(…):
1. invoca il metodo getCBipds(…) il quale:
a. Riempie la tabella ipds con le coppie <istruzione i, ipd dell’istruzione i> (solo se l’ipd dell’istruzione i è diverso da null). b. Invoca il metodo CBrealIPD(…) che riempie la tabella realIPD
con gli ipd reali dei salti condizionati appartenenti ad una
subroutine.
2. Ottenute le due tabelle per gli ipd, procede con il controllo dell’istruzione corrente:
a. In caso l’istruzione sia una jsr ne salva l’IstructionHandle nell’attributo currentJSR, questo servirà a capire da quale jsr si è entrati nella subroutine e di conseguenza ricavarne il corretto successore della ret
b. In caso l’istruzione sia un salto condizionato e se l’ipd è END, se l’attributo currentJSR è diverso da null e se anche realIPD è diverso da null, allora l’istruzione attuale è un salto condizionato
interno ad una subroutine. Con il metodo getIPD(…) si ricava dalla realIPD il nuovo ipd.
3. Se si è ricavato che l’istruzione attuale è un salto condizionato appartenente ad una subroutine allora modifica la tabella ipds aggiungendo una nuova
entry con la coppia <istruzione attuale, nuovo ipd dell’istruzione attuale>
altrimenti procede con la verifiche utilizzando le regole tradizionali dell’algoritmo ipd.
Si prende ora in considerazione la modifica del metodo relativo alla gestione del salto condizionato esterno ad una subroutine.
if(ec.size()>0){
if( ((InstructionContext)ec.get(ec.size()-1)).getInstruction().getInstruction()
instanceof JsrInstruction ){
/**
* se il predecessore è una JSR vuol dire che sono sulla prima istruzione della * subroutine devo eseguire anche se è ipd per avere la polivarianza
*/
if(execInstruction==false){
//prendo la lista dei salti condizionati aperti
InstructionHandle[] open_conditionals = workList.getQueueOwners(); InstructionHandle new_ipd = ((InstructionContext)ec.get(ec.size()-
1)).getInstruction().getNext();
InstructionHandle next_ipd = null;
//cerco il primo salto condizionato che ha un ipd diverso dal corrente
for(int i=0; i<open_conditionals.length; i++){
next_ipd = (InstructionHandle) ipds.get(open_conditionals[i]); if(next_ipd!=currentInstruction.getInstruction()){ //trovato break; } }
// l'istruzione attuale
for(int i=0; i<open_conditionals.length; i++){
InstructionHandle temp_ipd = (InstructionHandle)
ipds.get(open_conditionals[i]); if(temp_ipd==currentInstruction.getInstruction()){
//se next_ipd == null vuol dire che l'ipd è END, quindi devo togliere il // salto condizionato corrente dalla tabella ipds
if(next_ipd==null){ ipds.remove(open_conditionals[i]); } else{ ipds.put(open_conditionals[i], new_ipd); } } } } execInstruction = true; } }
Ottenuta l’istruzione attuale la circulationPump(…):
1. Controlla se il predecessore della istruzione è una jsr, in tal caso l’istruzione attuale è la prima istruzione di una subroutine.
2. Controlla se execInstruction vale false, in tal caso significa che non è possibile eseguire l’istruzione attuale in quanto è ipd di uno o più salti condizionati aperti.
3. Se l’istruzione è la prima di una subroutine ed è ipd allora dal contesto ricava i salti condizionati in questione e di questi ne modifica l’ipd (modificando la tabella ipds) secondo le regole viste.
4. A questo punto “setta” il valore di execInstruction a true e esegue il codice del corpo della subroutine.
In questo modo con il metodo circulationPump(…) si ottiene una verifica polivariante, ogni qualvolta che si trova all’ entry point di una subroutine non
rimanda mai l’esecuzione ma va ad eseguire simbolicamente il codice della stessa, come già accennato la polivarianza ottenuta si può anche pensare come una espansione in linea della subroutine.
