Zoom Icon

Information Entropy

From UIC Archive

Entropia dell'informazione

Contents


Information Entropy
Author: Pn
Email: Email
Website: No Site
Date: 03/06/2007 (dd/mm/yyyy)
Level: Working brain required
Language: Italian Flag Italian.gif
Comments:



Riferimenti

http://en.wikipedia.org/wiki/Information_entropy
http://it.wikipedia.org/wiki/Entropia_%28teoria_dell%27informazione%29
Mathematical Theory of Communication (Parte 1 - Capitolo 6 e 7)



Introduzione Matematica

Cito dal doc di Shannon:
Nella teoria dell'informazione l'entropia misura la quantità di informazione, scelta ed incertezza di un messaggio.


Il calcolo dell'entropia di un messaggio (o file) è utilizzato per verificare se è possibile comprimere quest'ultimo, poiché, in parole spicce, si può effettuare la compressione, se l'input non contiene variabiliPer variabile si intende l'entità più piccola del messaggio.Ad esempio in un file .txt, per variabile s' intende il singolo carattere del tutto casuali.

La formula dell'entropia (detta anche entropia di Shannon) che noi utilizzeremo è quella in cui si considera la sorgente discreta d'informazione formata da una successione di simboli indipendenti: cioè data una string ij, il simbolo j non è dipendente da i.

Formula entropia.png

Dove:

  • p(xi) è la probabilità con cui una variabile sia presente più volte nella stesso messaggio;
  • Alcune proprietà di H.
    • H=0 quando tutte le p(i) tranne una, sono zero.
    • Dato n il numero di possibili variabili, "H è massimo ed uguale a log(n) quando tutti i p(i) sono uguali, ad esempio p(i)=1/n".

Per vedere da dove derivi la formula, consiglio di leggere l' appendice 2 del doc. di Shannon.


Il codice della formula

Calcolare l'entropia di un file è abbastanza facile: sapendo che la nostra variabile è il BYTE, e che di byte differenti ce n'è possono essere al massimo 256 (2^8): il nostro n. In base a ciò possiamo dire che il massimo valore di H è log2(n), cioè max H = 8
In C++ possiamo scrivere la formula di Shannon nel seguente modo: //#define N 256 BYTE *Messaggio; //è il buffer che contiene il messaggio unsigned int lunghezza_messaggio; float Variabile[256]; //contiene tutte le possibili variabili float entropia = 0;

//azzero la matrice for (int i = 0; i < 256; i++) {

    Variabile[i] = 0.0;

}

//Vedo quante volte è presente una variabile nel messaggio for(int i = 0; i < lunghezza_messaggio; i++) {

    Variabile[Messaggio[i]] += 1.0;

}

//Calcolo l'entropia for (int i = 0; i < 256; i++) {

    if(Variabile[i] != 0.0) {
       Variabile[i] /= lunghezza_messaggio;  //per il calcolo della probabilità
       entropia += ( - (Variabile[i] * log2(Variabile[i]) );  //calcolo l'entropia 
    }

}

Ora che sabbiamo come calcolare l'entropia di un messaggio, in generale, possiamo utilizzare questo codice, per verificare se un file è packato, anche quando i vari tool basati su signature, non lo rilevano.

Spero che vi sia sorta una domanda del genere: "Su che base possiamo fare ciò???", niente di più semplice:

Chi pratica l'unpacking o ha sperimentato tecniche di compressione dati, conosce, più o meno, la morfologia che può avere un file compresso: blocchi di codice all'apparenza random.
Al contrario: in una sezione (ad esempio) .CODE non compressa, si ripetono delle seguenze di byte innumerevoli volte, cosa che non avviene nei file packati.
Ed usando questa semplice osservazione come base, possiamo affermare che: quanto più, l'entropia di un file si avvicina al valore massimo, allora il file in questione, si può dire che è packato.

Ultima osservazione: i file packati sono pieni zeppi di cavecode, es fsg le ha sparse nella sezione, mentre altri packer, tipo aspack, l'hanno verso la fine della sezione.

Ecco il source di un programma che controlla se un seguibile è packato, in base all'entropia della prima sezione (Source per Win32/64 bit).

Pn =)


Disclaimer

I documenti qui pubblicati sono da considerarsi pubblici e liberamente distribuibili, a patto che se ne citi la fonte di provenienza. Tutti i documenti presenti su queste pagine sono stati scritti esclusivamente a scopo di ricerca, nessuna di queste analisi è stata fatta per fini commerciali, o dietro alcun tipo di compenso. I documenti pubblicati presentano delle analisi puramente teoriche della struttura di un programma, in nessun caso il software è stato realmente disassemblato o modificato; ogni corrispondenza presente tra i documenti pubblicati e le istruzioni del software oggetto dell'analisi, è da ritenersi puramente casuale. Tutti i documenti vengono inviati in forma anonima ed automaticamente pubblicati, i diritti di tali opere appartengono esclusivamente al firmatario del documento (se presente), in nessun caso il gestore di questo sito, o del server su cui risiede, può essere ritenuto responsabile dei contenuti qui presenti, oltretutto il gestore del sito non è in grado di risalire all'identità del mittente dei documenti. Tutti i documenti ed i file di questo sito non presentano alcun tipo di garanzia, pertanto ne è sconsigliata a tutti la lettura o l'esecuzione, lo staff non si assume alcuna responsabilità per quanto riguarda l'uso improprio di tali documenti e/o file, è doveroso aggiungere che ogni riferimento a fatti cose o persone è da considerarsi PURAMENTE casuale. Tutti coloro che potrebbero ritenersi moralmente offesi dai contenuti di queste pagine, sono tenuti ad uscire immediatamente da questo sito.

Vogliamo inoltre ricordare che il Reverse Engineering è uno strumento tecnologico di grande potenza ed importanza, senza di esso non sarebbe possibile creare antivirus, scoprire funzioni malevole e non dichiarate all'interno di un programma di pubblico utilizzo. Non sarebbe possibile scoprire, in assenza di un sistema sicuro per il controllo dell'integrità, se il "tal" programma è realmente quello che l'utente ha scelto di installare ed eseguire, né sarebbe possibile continuare lo sviluppo di quei programmi (o l'utilizzo di quelle periferiche) ritenuti obsoleti e non più supportati dalle fonti ufficiali.