Abordagem programada em Java para comparação de arquivos

Question

Qual seria a melhor abordagem para comparar duas assinaturas de arquivos hexadecimais entre si por semelhanças.

Mais especificamente, o que eu gostaria de fazer é pegar a representação hexadecimal de um arquivo .exe e compará -lo com uma série de assinaturas de vírus. Para essa abordagem, pretendo quebrar o arquivo (exe) representação hexadecimal em grupos individuais de n chars (ou seja, 10 chars hexadecimais) e fazer o mesmo com a assinatura do vírus. Pretendo o objetivo de executar algum tipo de heurística e, portanto, verifique estatisticamente se esse arquivo exe tem x% de similaridade em relação à assinatura conhecida do vírus.

A maneira mais simples e provavelmente muito errada que pensei em fazer isso é comparar exe [n, n-1] com o vírus [n, n-1], onde cada elemento na matriz é uma sub-matriz e, portanto, exe1 [0, 9] contra o vírus1 [0,9]. Cada subconjunto será classificado estatisticamente.

Como você pode perceber, haveria um grande número de comparações e, portanto, muito lento. Por isso, pensei em perguntar se vocês podem pensar em uma abordagem melhor para fazer essa comparação, por exemplo, implementando diferentes estruturas de dados.

Isso é para um projeto que estou fazendo para o meu BSC, onde estou tentando desenvolver um algoritmo para detectar malware polimórfico, esta é apenas uma parte de todo o sistema, onde o outro é baseado em algoritmos genéticos para evoluir a assinatura do vírus estático. Qualquer conselho, comentários ou informações gerais, como recursos, são muito bem -vindos.

---

Definição: Malware polimórfico (vírus, worm, ...) mantém a mesma funcionalidade e carga útil da versão "original", enquanto aparentemente têm estruturas (variantes) aparentemente diferentes. Eles conseguem isso por ofuscação de código e, assim, alterando sua assinatura hexadecimal. Algumas das técnicas usadas para o polimorfismo são; Alteração do formato (inserir remover em branco), renomeação variável, rearranjo de instrução, adição de código de lixo, substituição de declaração (x = 1 alterações para x = y/5 onde y = 5), trocando de instruções de controle. Muito parecido com o vírus da gripe mutações e, portanto, a vacinação não é eficaz, o malware polimórfico se afasta para evitar a detecção.

---

Atualizar: Depois do conselho, vocês me deram em relação ao que a leitura de fazer; Eu fiz isso, mas isso me confundiu mais. Encontrei vários algoritmos de distância que podem se aplicar ao meu problema, como;

• Subseqüência comum mais longa
• Algoritmo Levenshtein
• Algoritmo de Needleman -Wunsch
• Algoritmo de Smith -Aquático
• Algoritmo de Boyer Moore
• Algoritmo Aho Corasick

Mas agora não sei o que usar, todos parecem fazer a mesma coisa de maneiras diferentes. Continuarei a fazer pesquisas para que eu possa entender melhor cada um; Mas nesse meio tempo você poderia me dar sua opinião sobre which might be more suitable Para que eu possa dar prioridade durante minha pesquisa e estudá -la mais profunda.

---

Atualização 2: Acabei usando uma amálgama da LCSubsequence, LCSubstring e LEVENSHTEIN. Obrigado a todos pelas sugestões.

Há uma cópia do papel acabado em Github

Answer 1

Para algoritmos como esses, sugiro que você veja a área de bioinformática. Existe uma definição de problema semelhante, pois você possui arquivos grandes (sequências genômicas) nas quais está procurando certas assinaturas (genes, sequências de base curta bem conhecidas especiais etc.).

Também para considerar malware polimórfico, esse setor deve oferecer muito a você, porque na biologia parece igualmente difícil obter correspondências exatas. (Infelizmente, não estou ciente dos algoritmos apropriados de busca/correspondência apropriados para apontar você.)

Um exemplo dessa direção seria adaptar algo como o Aho Corasick Algoritmo para procurar várias assinaturas de malware ao mesmo tempo.

Da mesma forma, algoritmos como o Boyer Moore O algoritmo oferece horários fantásticos de pesquisa, especialmente para sequências mais longas (caso médio de O (n/m) para um texto de tamanho n, no qual você procura um padrão de tamanho M, ou seja, os tempos de pesquisa sublineares).

Answer 2

Vários artigos foram publicados sobre como encontrar documentos quase duplicados em um grande corpus de documentos no contexto da WebSearch. Eu acho que você os achará úteis. Por exemplo, veja isso apresentação.

Answer 3

Recentemente, houve uma quantidade séria de pesquisa na automação da detecção de relatórios duplicados de bugs em repositórios de bugs. Este é essencialmente o mesmo problema que você está enfrentando. A diferença é que você está usando dados binários. São problemas semelhantes, porque você estará procurando strings que tenham o mesmo padrão básico, mesmo que os padrões possam ter algumas pequenas diferenças. Um algoritmo de distância direto provavelmente não o serve bem aqui.

Este artigo fornece um bom resumo do problema, bem como algumas abordagens em suas citações que foram julgadas.

ftp://ftp.computer.org/press/outwer/proecedings/patrick/apsec10/data/4266a366.pdf

Answer 4

Como alguém apontou, a semelhança com o problema conhecido de string e bioinformática pode ajudar. A substring comum mais longa é muito quebradiça, o que significa que uma diferença pode reduzir pela metade o comprimento de tal string. Você precisa de uma forma de alinhamento de cordas, mas mais eficiente que Smith-Waterman. Eu tentaria procurar programas como BLAST, BLAT ou MUMMER3 para ver se eles podem atender às suas necessidades. Lembre-se de que os parâmetros padrão, para esses programas, são baseados em um aplicativo de biologia (quanto penalizar uma inserção ou substituição, por exemplo); portanto, você provavelmente deve observar os parâmetros de reestimação com base no domínio do seu aplicativo, possivelmente baseados em um Conjunto de treinamento. Esse é um problema conhecido, porque mesmo na biologia diferentes aplicações requerem parâmetros diferentes (com base, por exemplo, na distância evolutiva de dois genomas para comparar). Também é possível, porém, que, mesmo no padrão, um desses algoritmos possa produzir resultados utilizáveis. O melhor de tudo seria ter um modelo generativo de como a mudança de vírus e isso poderia guiá -lo em uma escolha ideal para um algoritmo de distância e comparação.