Calculando dados binários Similaridade

https://stackoverflow.com/questions/579981

06-09-2019
|

Pergunta

Eu vi algumas perguntas aqui relacionadas com a determinação da semelhança de arquivos, mas eles estão todos ligados a um determinado domínio (imagens, sons, textos, etc). As técnicas oferecidas como soluções exigem o conhecimento do formato de arquivo subjacente dos arquivos que estão sendo comparados. O que eu estou procurando é um método sem este requisito, onde os arquivos binários arbitrários podem ser comparadas sem a necessidade de compreender que tipo de dados que eles contêm. Ou seja, eu estou olhando para determinar o percentual semelhança de dados binários dois arquivos .

Para dar um pouco mais detalhadamente para você trabalhar, mesmo que este é potencialmente aplicável a muitas coisas, eu tenho um problema específico que eu estou trabalhando. Eu também têm actualmente uma solução de trabalho, mas eu não acho que ele é ideal. Existem provavelmente muitas otimizações em termos de método de comparação, e armazenar os resultados. Esperemos que algumas pessoas aqui será capaz de me dar algumas idéias novas. Eu, provavelmente, editar algumas informações sobre o meu método atual depois de um par de dias, mas eu não quero pensamentos das pessoas viés sobre o problema, dizendo-lhe como eu já estou fazendo isso.

O problema que estou trabalhando é detecção de clone para imagens de vídeo game ROM . Para aqueles que não têm experiência com emulação, ROMs são depressão dos dados sobre cartuchos de jogos. A ROM "clone" é tipicamente uma versão modificada do mesmo jogo, o tipo mais comum é uma versão traduzida. Por exemplo, as versões em japonês e inglês do original Final Fantasy para o NES são clones. Os jogos compartilham quase todos os seus ativos (sprites, música, etc), mas o texto foi traduzido.

Existem atualmente vários grupos que trabalham na manutenção de listas de clones para os vários sistemas, mas tanto quanto eu posso dizer, tudo isso é feito manualmente. O que estou tentando fazer é encontrar um método para detectar imagens ROM semelhantes automaticamente e objetiva, com base na similaridade de dados em vez de "estes parecem ser o mesmo jogo". Existem várias razões para a detecção de clones, mas uma das principais motivações é para ser usado com compressão Sólido . Isto permite a compressão de todos os clones de jogo em conjunto para o mesmo arquivo, com toda comprimido o conjunto clone muitas vezes levando-se apenas um pouco mais espaço do que uma das ROMs individuais.

Algumas preocupações a considerar quando esbarra com potencial aproxima:

ROMs variam muito em tamanho, dependendo do sistema. Alguns são pequenos, mas os sistemas modernos podem ter grandes, 256 MB ou mais. Alguns (todos?) Os sistemas só têm potências de 2 como possíveis tamanhos um jogo de 130MB em um desses sistemas teriam um rom 256MB, em grande parte vazio. Note-se que por causa disso, alguns clones podem ter tamanhos muito diferentes, se uma versão do jogo cruza o limiar e tem de usar um cartucho que é o dobro do tamanho.
Atualmente milhares de ROMs conhecidas em muitos sistemas, com a maioria dos sistemas continua a ter novos lançados constantemente. Mesmo para sistemas mais antigos, há uma grande comunidade de hackers ROM que produz ROMs modificadas frequentemente.
dados de similaridade Armazenando para cada par possível de ROMs resultaria em milhões de linhas de dados para qualquer um dos sistemas mais populares. Um sistema com 5000 ROMs exigiria 25 milhões de linhas de dados de similaridade, com um único jogo novo acrescentando mais de 5000 linhas.
Estado do processamento deve ser recuperável, de modo que se for interrompido, pode pegar de onde parou. Com qualquer método, um monte de processamento será necessária, e assumindo que a coisa toda será executado em um lote não é seguro.
Novas ROMs podem ser adicionados a qualquer momento, de modo que o método não deve presumir que ele já tem um conjunto "completo". Ou seja, mesmo depois de já ter descoberto similaridade para todas as ROMs existentes, se um novo é adicionado (e isso também poderia ocorrer antes anteriorprocessamento foi totalmente terminado) deve haver um método para compará-lo com todas as anteriores, para determinar quais (se houver) é um clone.
Maior velocidade de processamento de prioridade sobre a precisão (a um ponto). Saber se dois ROMs são 94% ou 96% semelhante não é particularmente importante, mas se for preciso um dia de processamento para comparar uma nova ROM para todos os anteriores, o programa provavelmente nunca verdadeiramente completo.

Tem sido um problema interessante para trabalhar, estou ansioso para ver o que outras pessoas podem vir acima com. Deixe-me saber nos comentários se você quiser mais detalhes, e eu vou tentar supri-las.

Solução

Parece que você quer um delta binário ou talvez um índice derivado da aplicação de um delta binário (como o seu tamanho). Você poderia, então, comparar este índice para alguns de base que você determinar experimentalmente para decidir se é um "clone" ou não.

Há uma série de semelhanças entre compressão e criação delta, então eu diria que você não estão muito longe com a sua implementação atual.

Dito isto, comparativos emparelhados de cada arquivo binário em seu banco de dados é provavelmente proibitivamente caro (O (n ²), eu acho). Gostaria de tentar encontrar um hash simples para identificar possíveis candidatos para comparação. Algo conceitualmente semelhante ao que spdenne e Eduard estão sugerindo. Isto é, encontrar um hash que podem ser aplicadas a cada item uma vez, classificar essa lista e, em seguida, usar uma comparação mais refinado em itens cujos hashes estão juntos na lista.

A construção de hashes úteis para o caso geral tem sido um tema de pesquisa prosseguir activamente no CS por vários anos. A LSHKit software biblioteca implementa alguns algoritmos deste tipo. O papel acessível internet achado semelhante arquivos em um sistema grande arquivo parece que pode ser alvo mais em arquivos de texto comparando mas pode ser útil. O papel mais recente multi-resolução hashing semelhança descreve um algoritmo mais poderoso. Ela não aparece para ser acessível sem uma assinatura, no entanto. Você provavelmente vai querer manter o artigo da Wikipedia sobre Localidade Hashing Sensitive acessível como você ver alguns dos outros recursos. Todos eles ficar bastante técnica e da própria entrada na Wikipedia é bastante pesado de matemática. Como uma alternativa mais user-friendly que você pode ser capaz de aplicar algumas ideias (ou mesmo executáveis) a partir do campo de Acústico fingerprinting .

Se você está disposto a abandonar o caso geral é provável que você pode encontrar muito mais simples (e mais rápido)-domínio específico função hash que funciona apenas para seus ROMs. Possivelmente algo que envolve a colocação de padrão, ou comum, seqüências de bytes e o valor de bits de seleção próximas a eles. Eu realmente não sei muito sobre o seu formato binário, mas eu estou imaginando coisas que sinalizam o início das seções no arquivo como regiões de som, imagens ou texto. formatos binários frequentemente armazenar os endereços desses tipos de seções perto do início do arquivo. Alguns também usam um mecanismo de encadeamento que armazena o endereço da primeira seção em um local conhecido, juntamente com o seu tamanho. Isso permite que você mover para a próxima seção, que também contém um tamanho, etc. Um pouco de investigação provavelmente irá permitir que você descubra qualquer formatação relevante, se você não estiver ciente disso, e deve colocá-lo bem no seu caminho para a construção de um hash útil.

Se as funções hash não levá-lo todo o caminho (ou eles exigem entrada de algum tipo para definir a / distância métrica), então existem vários algoritmos delta binários e implementações disponíveis na Web. O que eu estou mais familiarizado é usado pelo sistema de controle de versão Subversion. Ele usa um algoritmo delta binário chamado xdelta para armazenar de forma eficiente revisões de arquivos binários. Aqui está um link diretamente para o arquivo em seu repositório que implementa-lo: xdelta .c . Há provavelmente uma ferramenta na web que fazesta mais acessível também.

Outras dicas

Você pode querer olhar em bsdiff , que é um diffing sistema binário / remendar. Há também uma tese com muita teoria.

Use algumas idéias de algoritmos detecção de plágio .

A minha ideia:

A fim de criar uma "assinatura" comparável para cada ROM, que varia um pouco como a mudança pequenas porções, produzir algo como um gráfico de frequência de palavras, mas em vez de gravar as frequências das palavras, você pode botar seções muito curtas da ROM e gravar as frequências dos valores de hash.

Do não apenas uma secção de mistura, em seguida, a secção seguinte a partir do final da primeira secção, mas em vez disso utilizar uma janela deslizante, a secção de hashing a partir de um byte, em seguida, hash a mesma secção de tamanho a partir de 2 bytes, em seguida, a partir de byte 3, etc. Isso vai anular o efeito da variável porte variando porções dentro de sua ROM.

Se você usou uma função hash simples como XOR de cada byte de 8 bits, de modo que você pode facilmente calcular o hash da próxima janela de posição por xor o hash atual com os de saída de 8 bits, e xor as recebidas 8 bits. Outra função hash alternativa pode ser simplesmente usar o comprimento de instrução palavra de código. Isso pode ser suficiente para criar padrões estáticos para os códigos que representam instruções de máquina. O importante é que você vai querer uma função hash que resulta em seqüências curtas comuns no código de instrução resultando nos valores mesmo hash.

Você provavelmente quer menos valores de hash com freqüências mais altas de cada um, mas não vá muito longe ou seu gráfico será muito plana, resultando em dificuldade compará-los. Da mesma forma, não vá muito grande, ou você vai ter um monte de muito pequenas freqüências, tornando comparação duro novamente.

Loja Este gráfico per ROM. Compare gráficos de frequência para duas ROMs diferentes, calculando a soma dos quadrados da diferença de frequências para cada valor hash. Se que resume a zero, em seguida, os ROMs são susceptíveis de ser idênticos. Quanto mais longe de zero é, os menos semelhantes as ROMs será.

Apesar de ter sido muito mais do que "um par de dias", eu percebi que eu provavelmente deveria acrescentar a minha solução atual aqui.

Nils Pipenbrinck estava indo na mesma direção que o meu método atual. Dado que um dos principais resultados da localização de clones é uma enorme economia de arquivamento sólida, eu percebi que eu poderia apenas tentar comprimir quaisquer duas ROMs juntos e ver quanto espaço foi salvo. Eu estou usando o LZMA algoritmo em 7zip para isso.

O primeiro passo é comprimir cada ROM individualmente e observe o tamanho compactado, em seguida, tentar arquivar quaisquer duas ROMs juntos e ver o quanto as difere de tamanho resultantes de seus tamanhos compactados individuais. Se o tamanho combinado é a mesma que a soma dos tamanhos individuais, eles são 0% semelhante, e, se o tamanho é o mesmo que um deles (o maior), eles são idênticos.

Agora, este é um enorme número de tentativas de compressão necessário, então eu tenho um par de otimizações até agora (e gostaria de descobrir mais):

comparações Priorizar com base em como semelhante os tamanhos compactados são. Se ROM A tem um tamanho compactado de 10MB e ROM B tem um tamanho comprimido de 2MB, é impossível para eles para ser mais do que 20% semelhante, por isso comparando-os para obter o resultado real pode ser deixado para mais tarde. Executando o mesmo algoritmo de compressão de arquivos altamente semelhantes tende a resultar em resultados de tamanho semelhante, de modo que este encontra um monte de clones muito rapidamente.
combinada com a acima, manter tanto superior e inferior "limites" sobre a possível semelhança entre qualquer par de ROMs. Isso permite que mais de priorização. Se ROMs A e B são 95% semelhantes, e ROMs B e C são apenas 2% semelhante, então já sabe que A e C estão entre 0% e 7%. Este é demasiado baixo para ser um clone, então essa comparação pode ser adiada com segurança ou mesmo ignorada por completo, a menos que eu realmente quero saber as semelhanças exatas de tudo.

Eu acho que algumas técnicas emprestadas de dados-compressão poderia ser interessante aqui:

Suponha que você tem dois arquivos, A e B.

Compress cada arquivo individualmente e adicionar os tamanhos compactados juntos. Em seguida, concatenar os dois arquivos em um único arquivo, grande e comprimi-lo também.

A diferença nos tamanhos vai lhe dar uma estimativa aproximada quão semelhantes os arquivos são.

Eu sugiro que você experimente o Transformation Burrow Wheeler (bzip2) para fazer a compressão. A maioria dos outros algoritmos de compressão só tem uma história limitada. O algoritmo BWT otoh pode trabalhar em muito grandes blocos de dados. O algoritmo "vê" os dois arquivos ao mesmo tempo e qualquer semelhança irá resultar em uma maior taxa de compressão.

Xdelta é muito útil para obter diffs binários decentes: http://xdelta.org

Você pode começar por armazenar algo como hash árvores . Só é necessário para armazenar um tal conjunto de hashes para cada ROM, e o espaço de armazenamento necessário só é proporcional à (mas muito menor do que) o tamanho da ROM, assumindo tamanho do bloco constante. O tamanho do bloco escolhido deve dar granulosidade suficiente para garantir a precisão, por exemplo: para um tamanho mínimo de 128MiB, restrição precisão de 1% e Tiger-128 de hash (semelhante ao que eles usam para verificar os arquivos transferidos via DirectConnect), um bloco de tamanho 1MiB faz bem e você pode armazenar todos os hashes em 128 * 128/8 = 2048 bytes! Fazê-lo, para 10.000 ROMs única exigiria cerca 20MiB do espaço. Além disso, você pode escolher um menos segura, mas mais rápido e / ou de hash menor. Adicionando / verificação de similaridade uma nova ROM implicaria algo como:

Split a nova ROM em blocos e hash de cada um deles.
Para cada ROM já no banco de dados, comparar (veja abaixo) seus hashes com hashes da nova ROM.

A função de comparação deve verificar se há similaridade. Mas deve tratar cada hash como um valor indivisível, ou seja, não se incomode tentando encontrar uma função de diferença logicamente significativa entre dois hashes. Enquanto o tamanho do bloco é baixa o suficiente e hash colisões são suficientes rara, a precisão é garantida por um simples é-igual comparação.

Como você pode ver, o problema é reduzido a uma mais simples em termos de performance:. Verificar muito menores conjuntos de dados de similaridade

Dois pensamentos:

Considere organizar o arquivo como um fluxo de dados gráfico e fazer algumas canonização em que represention. Desde que você sabe o conjunto de instruções, isso pode ser viável, talvez apenas cintas-se um disassembler e fazer algum processamento de texto.
A treinável classificador, como crm114 pode vir a calhar para dar-lhe uma representação compacta que lhe dá alguns idéia se binários têm muito em comum.

Como disse Waylon Flinn, você pode precisar de um algoritmo delta binário. A rsync algoritmo é uma boa. Ele é rápido e confiável. Veja também a de utilidade documentação .

A dificuldade aqui é que desde que você está lidando com código executável, mudanças simples podem se propagar por toda a ROM. Os endereços e deslocamentos para valores ALL pode mudar com a adição de uma única variável ou não-op instrução. Isso fará com que até mesmo baseado em blocos sem valor hash.

Uma solução rápida e suja seria cortar-se uma solução com difflib (ou o equivalente w / o seu idioma favorito), uma vez que você recebe uma comparação deslizante que pode lidar com a adição de dados ou remoção. Dividir a ROM em seções executáveis ??e de dados (se possível). A seção de dados podem ser comparados directamente e uma relação de similaridade calculado , embora você' ll ainda tem problemas w / endereços ou compensações.

A seção executável é mais interessante. Leia-se sobre formato asm da máquina, tomar o executável e dividi-lo em uma seqüência de opcodes. Deixe o código de operação e registrar partes, mas mascarar a "carga" / peças "imediata" (onde ele carrega os endereços de variáveis). Distribua a informação resultante para a calculadora relação de semelhança também.

A parte infeliz é que esta ainda é um O (n ^ 2) operação do número de ROMs lhe acompanham, mas que podem ser aliviados com (incrementais) agrupamento ou uma ordem de comparação à base de frequência para reduzir a quantidade de comparações necessário.

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow