approccio programmatico in Java per il confronto di file

Question

Quale sarebbe l'approccio migliore per confrontare due firme di file esadecimale uno contro l'altro per affinità.

In particolare, ciò che vorrei fare è quello di prendere la rappresentazione esadecimale di un file exe e confrontarlo contro una serie di firme dei virus. Per questo approccio ho intenzione di rompere il file (exe) rappresentazione esadecimale in singoli gruppi di n caratteri (es. Caratteri esadecimali 10) e fare lo stesso con la firma dei virus. Io sto puntando a svolgere una sorta di euristiche e quindi statisticamente verificare se questo file exe ha X% di somiglianza con la firma virus noto.

Il modo più semplice e probabilmente molto male ho pensato di fare questo è, per confrontare exe [n, n-1] contro il virus [n, n-1] in cui ogni elemento della matrice è una matrice sub, e quindi exe1 [0,9] contro virus1 [0,9]. Ogni sottoinsieme verrà classificato statisticamente.

Come si può realizzare ci sarebbe un massiccio numero di confronti e quindi molto molto lento. Così ho pensato di chiedere se voi potete pensare ad un approccio migliore per fare tale confronto, ad esempio implementare diverse strutture di dati insieme.

Questo è per un progetto sto facendo per la mia laurea in cui sto cercando di sviluppare un algoritmo per rilevare malware polimorfico, questa è solo una parte di tutto il sistema, dove l'altro si basa su algoritmi genetici per evolvere la statica firme dei virus. Qualche consiglio, commenti o informazioni di carattere generale quali le risorse sono i benvenuti.

---

Definizione : il malware polimorfico (virus, worm, ...) mantiene la stessa funzionalità e payload come la loro versione "originale", pur avendo strutture apparentemente diversi (varianti). Raggiungono che per codice offuscamento e alterando in tal modo la loro firma esadecimale. Alcune delle tecniche utilizzate per il polimorfismo sono; formato alterazione (sbozzati inserto rimuovere), rinomina variabile, dichiarazione riarrangiamento, inoltre codice spazzatura, una sostituzione di istruzione (x = 1 cambiamenti a x = y / 5 dove y = 5), scambiando di istruzioni di controllo. Tanto come il virus muta l'influenza e quindi la vaccinazione non è efficace, polimorfici muta di malware per il rilevamento evitare.

---

Aggiornamento: Dopo che il consiglio voi ragazzi mi ha dato per quanto riguarda quello che la lettura di fare; L'ho fatto, ma in qualche modo mi ha confuso più. Ho trovato diversi algoritmi di distanza che si possono applicare al mio problema, come ad esempio:

• Longest sottosequenza comune
• Levenshtein algoritmo
• algoritmo di Needleman-Wunsch
• algoritmo di Smith-Waterman
• algoritmo di Boyer Moore
• algoritmo Aho Corasick

Ma ora non so quale usare, tutti sembrano fare lo stessa cosa in modi diversi. Io continuerò a fare ricerca in modo che posso capire ognuno migliore; ma nel frattempo mi può dare la vostra opinione su which might be more suitable modo che io possa dare la priorità durante la mia ricerca e di studiare più profondo.

---

Aggiornamento 2: Ho finito per usare un amalgama del LCSubsequence, LCSubstring e Levenshtein Distanza. Grazie a tutti per i suggerimenti.

C'è una copia della carta finita sulla GitHub

Answer 1

Per gli algoritmi come questi vi suggerisco guardare in zona bioinformatica. V'è una impostazione di lì, in quella di avere file di grandi dimensioni (sequenze del genoma), in cui si sta cercando alcune firme (geni, sequenze speciali breve base ben noti, etc.) problema simile.

Anche per considerare il malware polimorfico, questo settore dovrebbe offrire molto, perché in biologia sembra altrettanto difficile ottenere corrispondenze esatte. (Purtroppo, non sono a conoscenza di adeguata ricerca approximative / corrispondenza algoritmi per puntare a.)

Un esempio da questa direzione sarebbe quello di adattare qualcosa come il Aho Corasick algoritmo per la ricerca per diverse firme di malware, allo stesso tempo.

Allo stesso modo, algoritmi come il Boyer Moore algoritmo darà fantastici tempi di esecuzione della ricerca soprattutto per le sequenze più lunghe ( caso medio di O (N / M) per un testo di dimensione N, in cui si guarda per un modello di taglia M, ovvero sublineare tempi di ricerca).

Answer 2

Un certo numero di documenti sono stati pubblicati sulla ricerca di documenti presso duplicati in un ampio corpus di documenti nel contesto di websearch. Credo che li troverete utili. Ad esempio, vedere questo presentazione .

Answer 3

C'è stata una gran quantità di ricerca recentemente nella automatizzare la rilevazione delle segnalazioni di bug duplicati in repository di bug. Questo è essenzialmente lo stesso problema si sta affrontando. La differenza è che si sta utilizzando dati binari. Sono problemi simili perché sarete alla ricerca di stringhe che hanno lo stesso modello di base, anche se i modelli possono avere alcune leggere differenze. Un algoritmo di distanza straight-up probabilmente non servirà bene qui.

Questo documento fornisce una sintesi bene del problema, così come alcuni approcci nelle sue citazioni che sono stati provati.

ftp://ftp.computer.org/ premere / uscita / procedimenti / Patrick / apsec10 / dati / 4266a366.pdf

Answer 4

Come qualcuno ha fuori a punta, la somiglianza con il noto stringa e bioinformatica aiuto problema potrebbe. Più lunga sottostringa comune è molto fragile, il che significa che una differenza può dimezzare la lunghezza di tale stringa a. Hai bisogno di una forma di allineamento stringa, ma più efficiente di Smith-Waterman. Vorrei provare e guardare programmi come BLAST, BLAT o MUMMER3 per vedere se possono soddisfare le vostre esigenze. Ricordate che i parametri di default, per questi programmi, sono basate su una domanda di biologia (quanto a penalizzare un inserimento o di una sostituzione, per esempio), quindi probabilmente si dovrebbe guardare a parametri di ri-stimare, sulla base di dominio di applicazione, possibilmente basate su una training set. Questo è un problema noto perché anche in biologia diverse applicazioni richiedono diversi parametri (sulla base, per esempio, sulla distanza evolutiva di due genomi da confrontare). E 'anche possibile, tuttavia, che anche a un predefinito di questi algoritmi potrebbero produrre risultati utilizzabili. Meglio di tutti sarebbe quello di avere un modello generativo di come i virus cambiano e che potrebbe guidare l'utente in una scelta ottimale per un algoritmo di distanza e di confronto.