Trouver des séquences correspondantes dans deux fichiers binaires
Question
Permettez-moi de commencer avec un peu de contexte.
Ce matin, l'un de nos utilisateurs a signalé que l'antivirus de CA avait signalé que le fichier d'installation de Testuff était infecté par un virus. Convaincu que c’était un faux positif, j’ai regardé sur le Web et découvert que les utilisateurs d’un autre programme (SpyBot) avaient signalé le même problème.
À présent, pour la question même.
En supposant que l'antivirus recherche une signature binaire spécifique dans le fichier, j'aimerais rechercher les séquences correspondantes dans les deux fichiers et, éventuellement, trouver un moyen de modifier le script de configuration pour empêcher cette séquence de s'afficher.
J’ai essayé ce qui suit en Python, mais cela fait longtemps que cela fonctionne et je me demandais s’il existait un moyen plus efficace ou plus rapide.
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))
Existe-t-il une meilleure bibliothèque pour Python ou un autre langage capable de le faire? Une façon complètement différente d'aborder le problème est également la bienvenue.
La solution
Voir le plus long problème de sous-chaîne commun . Je suppose que difflib utilise la solution DP, qui est certainement trop lente pour comparer les exécutables. Vous pouvez faire beaucoup mieux avec les arbres / tableaux de suffixes.
Utilisation de perl Tree :: Suffix pourrait être la solution la plus simple. Apparemment, il donne toutes les sous-chaînes communes dans une plage de longueur spécifiée:
@lcs = $tree->lcs;
@lcs = $tree->lcs($min_len, $max_len);
@lcs = $tree->longest_common_substrings;
Autres conseils
Notez que même si vous l’avez trouvé de cette façon, rien ne garantit que la correspondance la plus longue est en réalité celle recherchée. Au lieu de cela, vous pouvez trouver du code d’initialisation commun ou des tables de chaînes ajoutées par le même compilateur, par exemple.
Pourquoi ne pas contacter CA et leur demander de leur dire ce qu'ils recherchent, pour ce virus?
Vous pouvez également copier le fichier et modifier chaque octet jusqu'à ce que l'avertissement disparaisse (cela peut prendre un certain temps en fonction de la taille).
Il est possible que la détection du virus soit beaucoup plus compliquée que la recherche d’une chaîne fixe.
Mieux vaut ne pas s'interroger sur la complexité et le temps dont ont besoin ces types d'algorithmes.
Si cela vous intéresse, voici le document lié ici vous pouvez trouver une bonne introduction à cette thématique.
Si une bonne implémentation de ces algorithmes existe, je ne peux pas le dire.
Je soupçonne que la recherche de chaînes binaires ne vous aidera pas. Un programme d'installation est susceptible de faire des choses "suspectes".
Vous devez probablement parler à CA et à Spybot de la liste blanche de votre programme d'installation ou de ce qui déclenche l'alerte.