approche Programmatique en Java pour la comparaison de fichiers

Question

Quelle serait la meilleure façon de comparer deux signatures de fichiers hexadécimal uns contre les autres pour des similitudes.

Plus précisément, ce que je voudrais faire est de prendre la représentation hexadécimale d'un fichier .exe et le comparer à une série de signatures de virus. Pour cette approche, je prévois de briser le fichier (exe) représentation hexagonale dans différents groupes de caractères N (ie. 10 caractères hexadécimaux) et faire la même chose avec la signature de virus. Je vise à réaliser une sorte de heuristiques et donc vérifier statistiquement si ce fichier exe a X% de similarité contre la signature de virus connu.

Le plus simple et probablement très mauvaise façon dont je pensais de le faire est, à comparer exe [n, n-1] contre le virus [n, n-1] où chaque élément du tableau est un tableau de sous, et donc exe1 [0,9] contre virus1 [0,9]. Chaque sous-ensemble sera statistiquement classé.

Comme vous pouvez le réaliser qu'il y aurait un très grand nombre de comparaisons et donc très lent. Donc, je pensais demander si vous les gars peuvent penser à une meilleure approche pour faire une telle comparaison, par exemple la mise en œuvre différentes structures de données ensemble.

Ceci est pour un projet je fais pour mon BSc où je tente de développer un algorithme pour détecter les logiciels malveillants polymorphes, ce ne représente qu'une partie du système, où l'autre est basé sur des algorithmes génétiques pour évoluer statique signature de virus. Des conseils, des commentaires ou des informations générales telles que les ressources sont les bienvenus.

---

Définition : les logiciels malveillants polymorphes (virus, ver, ...) maintient la même fonctionnalité et la charge utile que leur version "originale", tout en ayant des structures différentes en apparence (variantes). Ils atteignent que par obfuscation de code et modifiant ainsi leur signature hexagonale. Certaines des techniques utilisées pour le polymorphisme sont; modification de format (insérer remove des blancs), renommage, réorganisation de l'instruction, l'ajout de code indésirable, le remplacement de l'instruction (x = 1 change à x = y / 5 où y = 5), troquant des instructions de contrôle. Tant et si bien que le virus de la grippe mute et donc la vaccination ne sont pas efficaces, les logiciels malveillants mute polymorphes pour éviter la détection.

---

Mise à jour: Après les conseils les gars me ont donné en ce qui concerne ce que la lecture à faire; Je l'ai fait, mais il me un peu confus plus. J'ai trouvé plusieurs algorithmes de distance qui peuvent s'appliquer à mon problème, tels que:

• La plus longue séquence commune
• Levenshtein algorithme
• algorithme de Needleman-Wunsch
• algorithme Smith-Waterman
• algorithme Boyer Moore
• Aho algorithme Corasick

Mais maintenant, je ne sais pas qui à utiliser, ils semblent tous faire il même chose de différentes façons. Je continuerai à faire des recherches afin que je puisse comprendre chacun mieux; mais dans le même temps pourriez-vous me donner votre avis sur which might be more suitable afin que je puisse donner la priorité au cours de mes recherches et de l'étudier plus profondément.

---

Mise à jour 2: Je fini par utiliser une fusion de la LCSubsequence, LCSubstring et Levenshtein. Merci à tous pour les suggestions.

Il y a une copie du document final sur GitHub

Answer 1

Pour les algorithmes comme ceux-ci, je vous suggère de regarder dans la zone de bio-informatique. Il y a un problème similaire dans la mise il que vous avez de gros fichiers (séquences du génome) dans lequel vous êtes à la recherche de certaines signatures (gènes, des séquences de bases courtes bien connues spéciales, etc.).

De plus pour considérer les logiciels malveillants polymorphes, ce secteur devrait vous offrir beaucoup, parce que la biologie, il semble tout aussi difficile d'obtenir des correspondances exactes. (Malheureusement, je ne suis pas au courant d'algorithmes recherche appropriée approximative / correspondant à vous indiquer.)

Un exemple de cette direction serait d'adapter quelque chose comme le Aho Corasick algorithme afin de rechercher plusieurs signatures de malwares en même temps.

De même, les algorithmes comme le Boyer Moore algorithme vous donner la recherche fantastique runtimes en particulier pour des séquences plus longues ( cas moyenne de O (N / M) pour un texte de taille N dans laquelle vous recherchez un modèle de taille M, à savoir la recherche sublinéaire fois).

Answer 2

Plusieurs documents ont été publiés sur la recherche de documents en double près dans un grand corpus de documents dans le cadre de websearch. Je pense que vous les trouverez utiles. Par exemple, voir cette présentation .

Answer 3

Il y a eu une quantité sérieuse de recherche récemment dans l'automatisation de la détection des rapports de bogues en double dans les dépôts de bogues. Ceci est essentiellement le même problème que vous rencontrez. La différence est que vous utilisez des données binaires. Ce sont des problèmes similaires parce que vous serez à la recherche des chaînes qui ont le même modèle de base, même si les motifs peuvent avoir quelques légères différences. Un algorithme de distance en ligne droite-up ne sera probablement pas vous servir ici.

Ce document donne un bon résumé du problème, ainsi que certaines approches dans ses citations qui ont été essayées.

ftp://ftp.computer.org/ presse / sortie / procédure / Patrick / apsec10 / data / 4266a366.pdf

Answer 4

Comme quelqu'un l'a dit, similitude avec chaîne connue et bio-informatique problème pourrait aider. La plus longue chaîne commune est très fragile, ce qui signifie qu'une différence peut réduire de moitié la longueur de chaîne telle. Vous avez besoin d'une forme d'alignement de chaîne, mais plus efficace que Smith-Waterman. Je voudrais essayer et de regarder des programmes tels que BLAST, BLAT ou MUMMER3 pour voir si elles peuvent répondre à vos besoins. Rappelez-vous que les paramètres par défaut, pour ces programmes, sont basés sur une application de la biologie (combien pénalisent une insertion ou une substitution par exemple), de sorte que vous devriez probablement à des paramètres de réestimer en fonction de votre domaine d'application, peut-être basé sur un ensemble de la formation. Ce problème est connu parce que même en biologie différentes applications nécessitent des paramètres différents (en fonction, par exemple, sur la distance évolutive de deux génomes à comparer). Il est également possible, cependant, que même à un défaut de ces algorithmes pourraient produire des résultats utilisables. Le meilleur de tous serait d'avoir un modèle génératif de la façon dont les virus changent et qui pourraient vous guider dans un choix optimal pour une distance et un algorithme de comparaison.