Trova le sequenze corrispondenti in due file binari
Domanda
Vorrei iniziare con un po 'di background.
Questa mattina uno dei nostri utenti ha riferito che il file di installazione di Testuff è stato segnalato come infetto da un virus dall'antivirus CA. Fiducioso che si trattasse di un falso positivo, ho guardato sul web e ho scoperto che gli utenti di un altro programma (SpyBot) hanno segnalato lo stesso problema.
A ora, per la vera domanda.
Supponendo che l'antivirus stia cercando una firma binaria specifica nel file, mi piacerebbe trovare le sequenze corrispondenti in entrambi i file e spero di trovare un modo per modificare lo script di installazione per impedire che appaia quella sequenza.
Ho provato quanto segue in Python, ma è in esecuzione da molto tempo ormai e mi chiedevo se ci fosse un modo migliore o più veloce.
from difflib import SequenceMatcher
spybot = open("spybotsd160.exe", "rb").read()
testuff = open("TestuffSetup.exe", "rb").read()
s = SequenceMatcher(None, spybot, testuff)
print s.find_longest_match(0, len(spybot), 0, len(testuff))
Esiste una libreria migliore per Python o per un'altra lingua che può farlo? È ben accetto anche un modo completamente diverso di affrontare il problema.
Soluzione
Vedi il problema di sottostringa comune più lungo . Immagino che difflib usi la soluzione DP, che è certamente troppo lenta per confrontare i file eseguibili. Puoi fare molto meglio con suffisso alberi / array.
Utilizzo di perl Tree :: Suffix potrebbe essere la soluzione più semplice. Apparentemente fornisce tutte le sottostringhe comuni in un intervallo di lunghezza specificato:
@lcs = $tree->lcs;
@lcs = $tree->lcs($min_len, $max_len);
@lcs = $tree->longest_common_substrings;
Altri suggerimenti
Nota che anche se l'hai trovato in questo modo, non vi è alcuna garanzia che la partita più lunga sia effettivamente quella cercata. Al contrario, potresti trovare codice di inizializzazione comune o tabelle di stringhe aggiunte dallo stesso compilatore, ad esempio.
Perché non contatti CA e chiedi loro di dire loro cosa stanno cercando, per quel virus?
In alternativa, è possibile copiare il file e modificare ogni singolo byte fino alla scomparsa dell'avviso (potrebbe richiedere del tempo a seconda della dimensione).
È possibile che il rilevamento di virus possa essere molto più complicato della semplice ricerca di una stringa fissa.
Meglio non stupirsi della complessità e del tempo di cui hanno bisogno questi tipi di algoritmi.
Se sei interessato a questo - qui .ps documento collegato qui puoi trovare una buona introduzione a questa tematica.
Se esiste una buona implementazione per questi algoritmi, non posso dirlo.
Sospetto che la ricerca di stringhe binarie non ti aiuterà. È probabile che un programma di installazione stia facendo alcune cose "sospette".
Probabilmente devi parlare con CA e spybot della lista bianca del tuo programma di installazione o di ciò che sta attivando l'avviso.