A TAXONOMY OF OBFUSCATING TRASFORMATIONS Funes Daniel 809619 Salvador Carlo 803776 Corso di Analisi...

A TAXONOMY OF OBFUSCATING TRASFORMATIONS

Funes Daniel 809619

Salvador Carlo 803776

Corso di Analisi e Verifica dei Programmi 2006/2007

INTRODUZIONE

Il software contiene informazioni riservate ed è una proprietà intellettuale di chi lo produce:

Codice Algoritmi Chiavi segrete

Attraverso le tecniche di analisi dei programmi (DataFlow Analysis) è possibile analizzare il comportamento di un software e rubarne i segreti.

Con abbastanza risorse in tempo e sforzo, un programmatore è capace di fare il reverse engineering di una applicazione, soprattutto se sviluppata in un linguaggio come Java, distribuita in formato semplice da decompilare.

PROTEZIONE DEL SOFTWARE: Scenario

Una volta creata l’applicazione deve essere distribuita in qualche forma(codice nativo, bytecode).

Alice e Bob sono due sviluppatori software, Bob è malintenzionato (algoritmi, strutture dati).

La protezione avviene attraverso mezzi legali o tecnici.

Le strategie tecniche sono: vendere i servizi, cifrare il codice, compilatore just-in-time, offuscamento del codice.

ALICE E BOB: vendere i servizi

ALICE E BOB: cifratura e compilatori just-in -time

ALICE E BOB:offuscamento del codice

Alice da in input l’applicazione ad un offuscatore, con vantaggi e svantaggi.

Il livello di sicurezza aggiunto da un’offuscatore ad un’applicazione dipende da:

la potenza degli algoritmi di offuscamento, la quantità di risorse (tempo e spazio) disponibili al

deoffuscatore.

TRASFORMAZIONI OFFUSCANTI: classificazione

Le trasformazioni si classificano e si valutano rispetto alla loro:

potenza: grado di confusione causato nell’utente malizioso;

resilienza: quanto il codice offuscato è resistente ad un attacco deoffuscante;

costo: quanto overhead è aggiunto all’applicazione originale.

TRASFORMAZIONI OFFUSCANTI: definizione

Sia t:P P’ una trasformazione di un programma sorgente P in un altro programma P’.

t:P P’ è una trasformazione offuscante se P e P’ hanno lo stesso comportamento osservabile e più precisamente devono essere mantenute le seguenti condizioni:

se P fallisce nel terminare o termina con una condizione di errore allora P’ potrebbe terminare oppure no,

altrimenti, P’ deve terminare e produrre lo stesso output di P.

VALUTAZIONE DELLLE TRASFORMAZIONI OFFUSCANTI: metriche di complessità E(X) è la complessità di un componente software X. F è una funzione o metodo, C è una classe, e P è un programma.

μ1 Lunghezza del programma

E(P) aumenta col numero di operatori e di operandi in P

μ2 Cyclomatic Complexity

E(F) aumenta col numero di predicati in F

μ3 Complessità annidata

E(F) aumenta con il numero di livelli annidati di predicati condizionali in F

μ4 Complessità del flusso di dati

E(F) aumenta col numero di riferimenti a basic block in F

μ5 Complessità fan-in/out

E(F) aumenta col numero di parametri formali di F, e con il numero di strutture dati globali lette o aggiornate da F

VALUTAZIONE DELLLE TRASFORMAZIONI OFFUSCANTI: metriche di complessità

μ6 Complessità delle strutture dati

E(P) aumenta con la complessità delle strutture dati statiche dichiarate in P. La complessità di una variabile scalare è costante; La complessità di un array aumenta col numero di dimensioni e con la complessità del tipo degli elementi; La complessità un record aumenta con il numero e la complessità dei suoi campi.

VALUTAZIONE DELLLE TRASFORMAZIONI OFFUSCANTI: metriche di complessità

μ7 Metrica 00 E(C) aumenta con: μ7a , il numero di metodi in C, μ7b , la profondità (la distanza dalla radice) di C nell’albero di ereditarietà μ7c, il numero di sottoclassi dirette di C μ7d , il numero di altre classi alle quali C è associata μ7e, il numero di metodi che possono essere eseguiti in risposta all’invio di un messaggio ad un oggetto di C μ7f, il grado di quali metodi di C non fanno riferimenti allo stesso insieme di variabili d’istanza.

TRASFORMAZIONI OFFUSCANTI:potenza della trasformazione

Sia T una trasformazione che conserva il comportamento | t: P P’ cioè che trasforma un P sorgente in un P’. Sia E(P) la complessità di P.

Tpot(P), la potenza di T rispetto al P, è la misura di quanto T cambia la complessità di P.

Tpot(P)=E(P’)/E(P)-1.

T è una trasformazione offuscante potente se: Tpot(P)>0.

Si misura in (low, medium, high).

TRASFORMAZIONI OFFUSCANTI:resilienza della trasformazione

Data T locale se ha effetto su un singolo basic block di un grafo

del flusso di controllo (CFG),

globale se ha effetto sull’intero CFG, interprocedurale se ha effetto sul flusso di informazioni

tra le procedure, interprocesso se ha effetto sulle interazioni tra thread di

controllo in esecuzione indipendente . Si misura su una scala che va da “trivial” a “one-way”.

TRASFORMAZIONI OFFUSCANTI:resilienza della trasformazione

Sia T una trasformazione che conserva il comportamento | t : PP’ .

Tres(P) è la resilienza di T rispetto al programma P.

Tres(P) è one-way se l’informazione è rimossa da P in modo che P non possa più essere ricostruito da P’.

Altrimenti Tres=resilienza(Tsforzo D, Tsforzo P).

La resilienza è la f definita dalla matrice seguente:

TRASFORMAZIONI OFFUSCANTI:costo della trasformazione

E’ l’overhead di tempo/spazio che una trasformazione aggiunge ad un’applicazione. E’ classificato su una scala a 4 punti (free, cheap, costly,

dear).

Tcost(P) è l’overhead in termini di tempo/spazio in P’ rispetto a P e può essere:

dear, se P’ richiede una quantità esponenziale di risorse rispetto a P.

costly, se P’ richiede più di O(n^p ), p>1, risorse rispetto a P. cheap, se P’ richiede più di O( n ) risorse rispetto a P. free, se P’ richiede più di O(1) risorse rispetto a P.

Tqual(P), la qualità di una trasformazione T è definita come: Tqual(P)=(Tpot(P),Tres(P),Tcost(P)).

TRASFORMAZIONI DEL CONTROLLO

Le TRASFORMAZIONI DEL CONTROLLO tentano di oscurare il flusso di controllo dell’applicazione sorgente:

Aggregazione : spezzano le computazioni logicamente affini oppure fonde computazioni non logicamente affini;

Ordine di controllo : randomizza l’ordine con cui le computazioni sono eseguite;

Computazioni del flusso di controllo : inseriscono nuovo codice (creano molto overhead).

TRASFORMAZIONI DEL CONTROLLO:predicati opachi

Una variabile V è opaca nel punto p di un programma, se V ha una proprietà q in p che è conosciuta al momento dell’offuscamento. Indicheremo ciò con Vp^q o con V^q se p è libero dal contesto.

Un predicato P è opaco nel punto p di un programma, se il suo esito è conosciuto al momento dell’offuscamento. Indicheremo con Pp^F o con Pp^T.

Misura del costo aggiunto di un costrutto opaco : free, …, dear.

TRASFORMAZIONI DEL CONTROLLO: costrutti opachi

trivial rotto solo attraverso un’analisi locale statica. un’analisi locale è ristretta ad un singolo basic block del CFG.

weak rotto solo attraverso un’analisi globale statica. Un’analisi globale è ristretta ad un singolo CFG.

TRASFORMAZIONI DEL CONTROLLO: trasformazioni computazionali

Inseriamo codice morto o irrilevante; Aumentando le metriche μ2 e μ3; Inseriamo codice morto o irrilevante;


Estendere le condizioni dei cicli: il predicato usato x^2(x+1)^2=0(mod 4) è sempre

valutato true.


Convertire un grafo di flusso riducibile ad uno non riducibile.

Trasformazioni language-breaking:


Rimuovere le chiamate a libreria e gli idiomi della programmazione;

Molti programmi scritti in Java si basano sulle chiamate alle librerie standard e sui clichè (o pattern).

Aggiungere operatori ridondanti

P e Q possono assumere tutti i valori il cui quoziente sia 2 ogni volta che l’espressione (2') è raggiunta.


Parallelizzazione del codice Si possono creare due processi fantoccio che non

eseguono nessun compito utile. Possiamo spezzare una sezione sequenziale

dell’applicazione in sezioni multiple eseguite in parallelo.

TRASFORMAZIONI DEL CONTROLLO: trasformazioni per aggregazione

Chi programma usa l’astrazione procedurale per vincere alcune difficoltà.

Queste astrazioni vengono rimosse utilizzando: Inlining, Outlining, Interleaving, Clonazione.

Si procede nel modo seguente: Il codice che il programmatore ha allegato insieme in un

metodo deve essere sparpagliato nel programma. Il codice che sembra non essere logicamente connesso

deve essere aggregato in un metodo.


Metodi Inline e Outline Inline: si rimpiazza una chiamata a procedura con il

corpo della procedura chiamata e si rimuove la procedura:

altamente resiliente (generalmente one-way); non c’è più traccia dell’astrazione.

Outlining: si trasforma una sequenza di espressioni in una subroutine


Metodi Inline e Outline. Nei linguaggi object oriented come Java, l’inlining può non

sempre essere una trasformazione totalmente one-way.

L’attuale procedura chiamata dipenderà dal tipo di m determinato a run-time.

Occorre applicare l’inlining a tutti i possibili metodi e ramificare su m.


Metodi interleave. La scoperta del codice interfogliato è un difficile compito

di reverse engineering. L’idea:

fondere i corpi e la lista dei parametri dei due metodi; aggiungere un parametro extra (o parametro globale) per

discriminare tra le chiamate ai metodi individuali.


Metodi di clonazione. Per capire il comportamento di una subroutine sono

importanti anche i differenti ambienti in cui è stata chiamata. Idea : offuscare il punto di una chiamata ad un metodo

per far sembrare che differenti routine sono state chiamate.

TRASFORMAZIONI DEI DATI: Storage e Encoding

Trasformazioni che oscurano le strutture dati usate nell’applicazione sorgente.

Le trasformazioni storage tentano di scegliere una classe di immagazzinamento non naturale sia per i dati dinamici che per quelli statici

Es. storage int i; a[i]=3; le trasformazioni encoding tentano di scegliere

codifiche non naturali per i comuni tipi di dati Es. encoding 0000000000001100 sarà interpretato come

12.

TRASFORMAZIONI DI STORAGE E ENCODING:Cambiare la codifica

Viene sostituito i con i’=c1*i + c2.

c1 e c2 sono costanti. Introduce overhead in termini di tempo

d’esecuzione ma può essere deoffuscato usando le comuni tecniche di analisi dei compilatori.

TRASFORMAZIONI DI STORAGE E ENCODING:Promozione di variabili

Promuovere le variabili da una classe di memorizzazione ad una più generale.

Bassa potenza e resilienza, ma usate in modo congiunto con altre trasformazioni sono molto efficienti.

Promozione di una varibile da integer ad un oggetto integer

Promozione di una varibile da locale a globale, questa trasformazione incrementa la metrica μ5.

TRASFORMAZIONI DI STORAGE E ENCODING:Splitting delle varibili (1)

Variabili di tipo Boolean o con raggio d’azione ridotto posso essere spezzate in più variabili.

V=[p1,..,pk] ( V di tipo T, pi di tipo U). La potenza, la resilienza, e il costo di questa

trasformazione crescono con l’aumentare di k, ma di solito k<= 3 a causa del costo della trasformazione troppo elevato.

Per spezzare una variabile V in due variabili p e q è necessario fornire:

Una funzione f(p,q)=V, Una funzione g(V), Nuove operazioni che possano essere effettuate su p e q.

TRASFORMAZIONI DI STORAGE E ENCODING:Splitting delle varibili (2)

TRASFORMAZIONI PER AGGREGAZIONE:Fusione di variabili scalari

In un programma object oriented il controllo è organizzato attorno alle strutture dati, che un reverse engineering prova a ricostruire. Quindi è importante per un offuscatore provare a nasconderle.

Due o più variabili scalari V1,…, Vk posso essere fuse in un’unica variabile Vm:

L’aritmetica sulle variabili individuali deve essere trasformata in un’aritmetica su Vm,

Fusione di due variabili integer a 32 bit X e Y in una a 64 bit Z, usando la funzione Z(X,Y) =232 * Y + X .

TRASFORMAZIONI PER AGGREGAZIONE:Ristrutturare array

Operazioni su array : splitting(1-2), merging(3-5) ,folding(6-7) ,flatting(8-9)

TRASFORMAZIONI PER AGGREGAZIONE:Modificare le relazioni di ereditarietà

Si dice che la classe C2 eredita dalla classe C1 e

indichiamo ciò con ( ). la complessità di una classe cresce con la sua

ampiezza (gerarchia di ereditarietà). Idea : aumentiamo l’ampiezza della gerarchia (μ7)

Fattorizzazione, Inserimento di classi fantoccio

Variante : falsa rifattorizzazione. Problema : bassa resilienza. Soluzione : usate in modo combinato.

2 1 2C C C

VALORI E PREDICATI OPACHI:uso di alias

L’analisi statica interprocedurale è significativamente complicata ogni volta che c’è possibilità d’aliasing.

Infatti, differenti versioni di precise analisi statiche sugli alias hanno dimostrato che questo è un problema NP-hard.

L’idea di base è di costruire una struttura dinamica complessa e mantenere un insieme di puntatori in questa struttura.

VALORI E PREDICATI OPACHI:uso di thread

I programmi paralleli sono molto più difficili da analizzare rispetto alla loro controparte sequenziale.

La ragione di ciò è la loro semantica interfogliante: n espressioni in una regione parallela.

Idea base analoga a quella che usa gli alias struttura dati globale aggiornato da thread

Vantaggi i predicati opachi richiedano nel caso

peggiore tempo esponenziale per essere rotti

grado molto alto di resilienza Si combinano gli effetti di interfogliamento

e aliasing.

DEOFFUSCAMENTO E TRASFORMAZIONI PREVENTIVE

Architettura di un tool di deoffuscazione Java. L'input principale del tool è un'applicazione costituita da un insieme di file class Java offuscati.

L'output del tool è un insieme di file class deoffuscati che possono essere convertiti in sorgenti Java da un decompilatore.

DEOFFUSCAMENTO E TRASFORMAZIONI PREVENTIVE

Trasformazioni preventive innerenti: Rendono le tecniche di deoffuscamento più difficili, Poca potenze, molta resilienza.

Trasformazioni preventive mirate: esplorare i problemi conosciuti nei correnti deoffuscatori o

nei decompilatori,

Es. il decompilatore Mocha.

IDENTIFICARE E VALUTARE I COSTRUTTI OPACHI

La parte più difficile del deoffuscamento è identificare e valutare i costrutti opachi :

Locali, Globali, Interprocedurali.

( * (7* * 1) )...Fif x x y y

locale* ;

...

7* * 1;

...

( )....F

R x x

S y y

if R S

globale

IDENTIFICARE E VALUTARE I COSTRUTTI OPACHI:Pattern Matching

Un deoffuscatore può usare la conoscenza delle strategie impiegate dagli offuscatori conosciuti per identificare i predicati opachi.

regole di pattern-matching che possano identificare i predicati opachi comunemente usati.

L’offuscatore dovrebbe evitare di usare un numero limitato di predicati opachi;

Utilizzo di costrutti opachi sintatticamente simili ai costrutti usati nell’applicazione reale.

IDENTIFICARE E VALUTARE I COSTRUTTI OPACHI:slicing del programma

Uno slice di un programma P rispetto ad un punto p e ad una variabile v, consiste di tutte le espressioni di P che possono aver contribuito al valore di v nel punto p.

Il deoffuscatore creerà quindi degli slice per ogni variabile da esaminare, al fine di eliminare falso codice e unire pezzi di codice logicamente legati.

L’offuscatore deve rendere difficile lo slicing Aggiungendo parametri alias, Aggiungendo dipendenze alle variabili.

IDENTIFICARE E VALUTARE I COSTRUTTI OPACHI:Analisi Statistica(1)

Un deoffuscatore può sfruttare un programma offuscato per analizzare il risultato di tutti i predicati e avvisare il reverse engineer di qualunque predicato che restituisce sempre lo stesso valore di verità.

Predicati che si verificano in casi eccezzionali.

IDENTIFICARE E VALUTARE I COSTRUTTI OPACHI:Analisi Statistica(2)

L’offuscatore dovrebbe quindi favorire i predicati Predicati opachi con side-effect.

?p

ARCHITETTURA DI UN TIPICO OFFUSCATORE JAVA

Permette di inserire dei profili per evitare che trasformazioni troppo costose siano applicate a parti del codice usate molto frequentemente.

Contiene un grannumero di trasformazioni.

ALGORITMI D’OFFUSCAMENTO:ciclo principale

SelectCode restituisce il prossimo codice oggetto sorgente che deve essere offuscato.

SelectTransform restituisce la trasformazione che dovrebbe essere usata per offuscare il particolare codice oggetto sorgente.

Apply applica le trasformazioni al codice oggetto sorgente e di conseguenza aggiorna l’applicazione.

Done determina quando il livello d’offuscamento richiesto è stato ottenuto.

ALGORITMI D’OFFUSCAMENTO: strutture dati

Per ogni codice oggetto sorgente S e per ogni routine M:

Ps(S) l’insieme dei costrutti del linguaggio che il programmatore ha usato in S.

A(S) ={T1V1, … , TnVn} è un mapping tra le trasformazioni Ti e i valori Vi.

I(S) è la priorità d’offuscamento di S.

R per ogni routine M, R(M) è il rango del tempo d’esecuzione di M.

ALGORITMI D’OFFUSCAMENTO:funzioni di qualità

Restituiscono informazioni di tipo numerico riguardanti ogni trasformazione:

Tres(S) - restituisce una misura della resilienza della trasformazione T quando è applicata al codice oggetto sorgente S.

Tpot(S) - restituisce una misura della potenza della trasformazione T quando è applicata al codice oggetto sorgente S.

Tcost(S) - restituisce una misura del tempo d’esecuzione e dell’overhead di spazio aggiunto da T a S.

Pt - mappa ogni trasformazione T nell’insieme dei costrutti del linguaggi che T aggiungerà all’applicazione.

ALGORITMI D’OFFUSCAMENTO:ALGORITMO 1 (offuscamento del codice)

1. Caricare l’applicazione C1,C2,… da offuscare

a. Codice sorgente oppureb. Codice oggetto

2. Caricare il codice contenuto nei file delle librerie L1,L2,..

3. Costruire una rappresentazione interna dell’applicazione

a. Un grafo di controllo del flusso per ogni routine di Ab. Un call-graph per le routine in Ac. Un grafo di ereditarietà per le classi di A.

4. Costruire R(M) e Ps(S) usando l’algoritmo 5, I(S) usando l’algoritmo 6 e A(S) usando l’algoritmo 7.

ALGORITMI D’OFFUSCAMENTO:ALGORITMO 1 (offuscamento del codice)

5. Applicare le Trasformazioni offuscanti all’applicazioneREPEAT

S:=SelectCode(I);T:=SelectTrasformation(S,A);Applica T ad S ed aggiorna le strutture

dati rilevanti del punto 3UNTIL Done(ReqObf,AcceptCost,S,T,I)

6. Ricostruisci il codice oggetto sorgente offuscato in una nuova applicazione offuscata X.

ALGORITMI D’OFFUSCAMENTO:ALGORITMO 2(SelectCode)

Input Il mapping della priorità di offuscamento I come computato

dall’algoritmo 6 Output: un codice oggetto sorgente S. I mappa ogni codice oggetto sorgente S in I(S).

Trattiamo I come una coda a priorità Selezioniamo S in modo da massimizzare I(S)

ALGORITMI D’OFFUSCAMENTO:ALGORITMO 3 (Select Transform)

Input Un codice oggetto sorgente S. La mappa di appropriatezza computata dall’Algoritmo 7

Output: Una trasformazione T Due aspetti importanti da considerare

T deve essere inglobata in modo naturale con il resto del codice S

Alto livello di appropiatezza in A(S) T deve rendere alti livelli di offuscamento con bassi costi di

overhead

ALGORITMI D’OFFUSCAMENTO:ALGORITMO 3 (Select Transform)

Restituisci una trasformazione T tale che:

Dove ω1,ω2,ω3 sono costanti definite dall’implementazione

ALGORITMI D’OFFUSCAMENTO:ALGORITMO 4 (Done)

Svolge vari compiti Aggiorna la coda a priorità I

La riduzione è basata su una combinazione resilienza/potenza Aggiorna anche ReqObf e AcceptCost Determina se la condizione di terminazione è stata

raggiunta.

ALGORITMI D’OFFUSCAMENTO:ALGORITMO 5 (informazioni pragmatiche)

Input Un’applicazione A I = {I1,I2,..}

Output: R(M), Ps(S) Si computano le informazioni pragmatiche

Dinamiche Uso di profiler su I Calcolare R(M) per ogni routine/basic block

Statiche Calcolare Ps(S)

ALGORITMI D’OFFUSCAMENTO:ALGORITMO 5 (informazioni pragmatiche)

FOR S:=ogni codice oggetto sorgente in A DOO := l’insieme di operatori che S usa;C := l’insieme dei costrutti del linguaggio ad alto livello

(WHILE,eccezzioni,threads,etc.) che S usa;L := l’insieme di classi/routine di libreria che S referenzia;Ps(S) := O U C U L;

END FOR

ALGORITMI D’OFFUSCAMENTO:ALGORITMO 6 (priorità dell’offuscamento)

Input un’applicazione A R(M)

Output: I(S) Possibili euristiche per I(S) possono essere

Se molto tempo è speso ad eseguire una routine M, allora M è probabilmente una procedura importante che dovrebbe essere pesantemente offuscata

Il codice complesso è più probabile che contenga importanti segreti commerciali che semplice codice

ALGORITMI D’OFFUSCAMENTO:ALGORITMO 7(appropiatezza dell’offuscamento)

Input Un’applicazione A costituita dai file C1,C2,… Pt,Ps(S),A(S)

Output: A(S)

FOR S := ogni codice oggetto sorgente in A DOFOR T := ogni trasformazione DO

V := grado di somiglianza tra e Pt(T) e Ps(S);

A(S) := A(S) U {TV};END FOR

END FOR

CONCLUSIONI (1)

Metodo migliore di offuscamento è quello che ha il miglior rapporto costo,resilienza,potenza:

Gli offuscatori commerciali usano una combinazione di trasformazioni: Package/Class/Method/Field renaming , Control Flow Obfuscation , String Encryption.

In oltre attuano una ottimizzazione del codice per incrementare al massimo le performance.

Trade-off tra protezione e prestazione. Protegge solo parti del codice. Usare gli offuscatori come ottimizzatori di codice, per

ridurre le dimensioni delle applicazioni e renderle più performanti.

CONCLUSIONI (2)

Reverse Engeneering sempre possibile, si deve avere un costo elevato per effettuarla.

Offuscamento può introdurre bug nel codice. Difficoltà nel debug del codice

Lo sviluppatore a volte dovrà mantenere 2 versioni dell’applicazione.

Uno sguardo avanti: Obsfucation tool sempre più presenti nel processo di

creazione del software, inclusi in strumenti di sviluppo come visual studio 2005.

Interessi commerciali che portano a investimenti per la protezione del software.

BIBLIOGRAFIA

Software protection and Application Security: Understanding the Battleground (A. Main and P.C. van

Oorschot), LNCS 2003

A Taxonomy of Obfuscating Transformation (C. Collberg, C. Thomborson and D. Low), TR 1998

Wikipedia, the free encyclopedia. (2002), “Obfuscated code”, http://www.wikipedia.com/wiki/obfuscated+code

Metrics for Measuring The Effectiveness of Obfuscators (N.Naeem, M.Batchelder, L.Hendren), Sable, 2006.

A TAXONOMY OF OBFUSCATING TRASFORMATIONS Funes Daniel 809619 Salvador Carlo 803776 Corso di Analisi...

Documents

Transcript of A TAXONOMY OF OBFUSCATING TRASFORMATIONS Funes Daniel 809619 Salvador Carlo 803776 Corso di Analisi...