Calcolo dati binari somiglianza

StackOverflow https://stackoverflow.com/questions/579981

Domanda

Ho visto alcune domande qui relative alla determinazione della similarità dei file, ma sono tutti collegati a un particolare dominio (immagini, suoni, testo, ecc). Le tecniche offerti come soluzioni richiedono la conoscenza del formato file sottostante dei file a confronto. Quello che sto cercando è un metodo senza questo requisito, in cui i file binari arbitrari potrebbe essere paragonato, senza bisogno di capire che tipo di dati in essi contenuti. Cioè, sto cercando di determinare la la percentuale di somiglianza dei dati binari due file .

Per dare un po 'più in dettaglio per voi di lavorare con, anche se questo è potenzialmente applicabile a molte cose, ho un problema specifico che sto lavorando su. Ho anche Al momento ho una soluzione di lavoro, ma non credo che sia l'ideale. Ci sono probabilmente molte ottimizzazioni in termini di metodo di confronto, e memorizzare i risultati. Speriamo che alcune persone qui saranno in grado di darmi alcune nuove idee. Io probabilmente modificare alcune informazioni circa il mio metodo attuale, dopo un paio di giorni, ma io non voglio pensieri di polarizzazione delle persone circa il problema che ti dice come sto già facendo.

Il problema su cui sto lavorando è rilevazione di clonazione per le immagini del video gioco ROM . Per coloro che non hanno esperienza con l'emulazione, ROM sono discariche dei dati sulle cartucce di giochi. Una ROM "clone" è in genere una versione modificata del gioco stesso, il tipo più comune è una versione tradotta. Ad esempio, le versioni giapponese e inglese dell'originale Final Fantasy per il NES sono cloni. I giochi condividono quasi tutte le loro attività (sprites, musica, ecc), ma il testo è stato tradotto.

Al momento non ci sono diversi gruppi che lavorano sul mantenimento di liste di cloni per i vari sistemi, ma per quanto ne so, questo è tutto fatto manualmente. Quello che sto cercando di fare è trovare un metodo per rilevare immagini ROM simili automaticamente ed oggettivamente, in base alla somiglianza dei dati al posto di "questi sembrano come lo stesso gioco". Ci sono diverse ragioni per rilevare cloni, ma uno dei principali motivazioni deve essere utilizzato con compressione Solid . Questo consente la compressione di tutti i cloni di gioco insieme nella stessa archivio, con l'intero clone compressa impostare spesso prendendo solo un po 'più spazio di uno dei singoli ROM.

Alcune preoccupazioni da considerare quando venire con potenziali approcci:

  • ROM variano fortemente dimensioni, a seconda del sistema. Alcuni sono piccoli, ma i sistemi moderni possono avere quelli di grandi dimensioni, 256 MB o più. Alcuni (tutti?) I sistemi hanno solo potenze di 2 come possibili dimensioni, un gioco di 130MB su uno di questi sistemi avrebbe una ROM da 256 MB, in gran parte vuote. Si noti che a causa di questo, alcuni cloni possono avere selvaggiamente diverse dimensioni, se una versione del gioco attraversa la soglia e deve utilizzare una cartuccia che è il doppio.
  • Al momento non ci sono migliaia di ROM noti su molti sistemi, con la maggior parte dei sistemi continui ad avere nuovi rilasciati costantemente. Anche per i sistemi più vecchi, c'è una grande comunità di ROM-hacking che produce ROM modificate spesso.
  • La memorizzazione dei dati di somiglianza per ogni possibile coppia di rom si tradurrebbe in milioni di righe di dati per uno dei sistemi più popolari. Un sistema con 5000 ROM richiederebbe 25 milioni di righe di dati somiglianza, con un unico nuovo gioco aggiungendo altri 5000 righe.
  • Stato del trattamento deve essere recuperabili, in modo che se si è interrotto può riprendere da dove si era interrotto. Con qualsiasi metodo, sarà richiesto un sacco di elaborazione, e supponendo che il tutto verrà eseguito in un unico lotto non è sicuro.
  • Le nuove ROM potrebbe essere aggiunto in qualsiasi momento, in modo che il metodo non dovrebbero presumere che esso ha già un set "completo". Cioè, anche dopo aver già capito somiglianza per tutti i ROM esistenti, se si aggiunge uno nuovo (e questo potrebbe accadere anche prima della precedentetrattamento era completamente finito) deve esistere un metodo per confrontarlo con i precedenti, per determinare quale (se presente) è un clone di.
  • maggiore velocità di elaborazione dovrebbe essere data la priorità rispetto precisione (a un punto). Sapere se due ROM sono il 94% o il 96% simile non è particolarmente importante, ma se si prende un giorno di elaborazione per confrontare una nuova ROM per tutti i precedenti, il programma sarebbe probabilmente mai veramente completo.

E 'stato un problema interessante su cui lavorare, non vedo l'ora di vedere quello che gli altri possono venire con. Fatemi sapere nei commenti se volete altri dettagli, e cercherò di fornire loro.

È stato utile?

Soluzione

Sembra che si desidera un delta binario o forse un indice derivato dall'applicazione di un delta binario (come la sua dimensione). Si potrebbe quindi confrontare questo indice per qualche linea di base che si determina sperimentalmente per decidere se si tratta di un "clone" oppure no.

Ci sono un sacco di somiglianze tra la compressione e la creazione di Delta, quindi direi che non sono lontani con l'implementazione corrente.

Detto questo, confronto a coppie di ogni file binario nel database è probabilmente proibitivo (O (n 2 ), credo). Vorrei provare a trovare una semplice hash per identificare possibili candidati per il confronto. Qualcosa di simile a ciò che concettualmente spdenne e Eduard stanno suggerendo. Cioè, trovare un hash che può essere applicato ad ogni elemento una volta, ordinare tale elenco e quindi utilizzare un confronto più sofistica su oggetti la cui hash sono vicini tra loro nella lista.

La costruzione di hash utili per il caso generale è stato un tema di ricerca perseguita attivamente CS per diversi anni. Il href="http://lshkit.sourceforge.net/" rel="noreferrer"> LSHKit libreria software la ricerca di file simile in un FILE SYSTEM GRANDE sembra che potrebbe essere mirata più a file di testo che confrontano, ma potrebbe essere utile a voi. Il documento più recente, Multi-risoluzione somiglianza hashing descrive un più potente algoritmo. Non sembra essere accessibili senza un abbonamento, però. Probabilmente si desidera mantenere l'articolo di Wikipedia su Località Sensitive Hashing a portata di mano durante la navigazione delle altre risorse. Tutti ottenere abbastanza tecnico e la voce di Wikipedia in sé è abbastanza pesante per la matematica. Come più user-friendly alternativa si potrebbe essere in grado di applicare alcune idee (o anche eseguibili) dal campo di Acoustic fingerprinting.

Se siete disposti ad abbandonare il caso generale è probabile che si può trovare un molto più semplice (e più veloce) dominio-specifica funzione di hash che funziona solo per i ROM. Forse qualcosa che coinvolge il collocamento di sequenze di byte standard, o comuni, e il valore dei bit di selezione vicino loro. Io in realtà non so molto di vostro formato binario, ma sto immaginando le cose che segnalano l'inizio di sezioni nel file come regioni di suoni, immagini o testo. I formati binari spesso memorizzare gli indirizzi di questi tipi di sezioni vicino all'inizio del file. Alcuni usare anche un meccanismo concatenamento che memorizza l'indirizzo della prima sezione in una posizione nota con essa di dimensione. Questo consente di spostare alla sezione successiva, che contiene anche una dimensione, ecc Un po 'di indagine sarà probabilmente permetterà di scoprire qualsiasi formattazione rilevante, se non siete già a conoscenza di esso, e dovrebbe mettere sulla buona strada per costruire un hash utile.

Se le funzioni di hash non ottengono tutto il percorso (o hanno bisogno di input di qualche tipo per definire una metrica / distanza) poi ci sono diversi algoritmi delta binario e implementazioni sul web. Quello di cui sono più familiarità con viene utilizzato dal sistema di controllo della versione Subversion. Esso utilizza un algoritmo di binario delta chiamato xdelta per memorizzare in modo efficiente revisioni dei file binari. Ecco un link diretto al file nella loro repository che lo implementa: xdelta .c. C'è probabilmente uno strumento sul web che rendequesto più accessibile pure.

Altri suggerimenti

Si potrebbe desiderare di guardare bsdiff , che è un diffing binario / sistema di patching. C'è anche una tesi con un sacco di teoria.

Con alcune idee da algoritmi Plagio Detection .

La mia idea:

Al fine di creare una "firma" comparabile per ogni ROM, che varia leggermente da piccole porzioni cambiano, producono qualcosa di simile a un grafico di frequenza parola, ma invece di registrare le frequenze di parole, si potrebbe hash molto brevi tratti della ROM , e registrare le frequenze dei valori hash.

Non solo hash una sezione, poi la sezione successiva a partire dalla fine della prima sezione, ma invece utilizzare una finestra scorrevole, hashing la sezione a partire dal byte 1, quindi hash stessa sezione dimensioni a partire dal byte 2, quindi dal byte 3, ecc Questo annullerà l'effetto di porzioni diverse dimensioni variabili entro la ROM.

Se si utilizza una semplice funzione hash come xor di ciascun byte di 8 bit, in modo che si può facilmente calcolare l'hash della posizione successiva finestra xor l'hash corrente con gli 8 bit in uscita, e XOR 8 bit in ingresso. Un'altra funzione di hash alternativa può essere semplicemente per utilizzare la lunghezza di istruzioni parola in codice. Che può essere sufficiente a creare schemi statici per i codici che rappresentano istruzioni macchina. La cosa importante è che si vorrà una funzione di hash che si traduce in brevi sequenze comuni nel codice di istruzione con conseguente gli stessi valori di hash.

Si sarebbe probabilmente vuole un minor numero di valori hash con frequenze più elevate di ciascuno, ma non andare troppo lontano o il grafico sarà troppo piatta, con conseguente difficoltà confrontandoli. Allo stesso modo non andare troppo ampia, o avrete un sacco di piccole frequenze, rendendo di nuovo duro confronto.

Conservare questo grafico per ROM. Confrontare i grafici di frequenza per due differenti ROM calcolando la somma dei quadrati delle differenze di frequenze per ogni valore di hash. Se che riassume a zero, allora le ROM sono suscettibili di essere identici. Più lontano da zero è, i meno simili le ROM saranno.

Anche se è stato molto di più di "un paio di giorni", ho pensato, probabilmente dovrei aggiungere la mia soluzione attuale qui.

Nils Pipenbrinck stava andando nella stessa direzione come il mio metodo attuale. Dal momento che uno dei principali risultati della ricerca di cloni è un enorme risparmio di archiviazione solida, ho pensato che ho potuto solo provare a comprimere ogni due ROM insieme e vedere quanto spazio è stato salvato. Sto usando l'algoritmo LZMA in 7zip per questo.

Il primo passaggio è quello di comprimere ogni ROM individualmente e notare la dimensione compressa, quindi provare archiviazione due qualsiasi ROMs insieme e vedere quanto la dimensione risultante differisce dalle loro dimensioni individuali compressi. Se la dimensione combinata è uguale alla somma delle singole dimensioni, sono simili 0%, e se la dimensione è uguale a uno di essi (la più grande), sono identici.

Ora, questo è un enorme numero di tentativi di compressione necessaria, quindi ho un paio di ottimizzazioni finora (e vorrei capire di più):

  1. Dare priorità confronti in base a come simili le dimensioni compressi sono. Se ROM A ha una dimensione compressa di 10 MB e ROM B ha una dimensione compressa di 2 MB, è impossibile per loro di essere simile più del 20%, quindi confrontando loro per ottenere il risultato reale può essere lasciato solo successivamente. Esegue lo stesso algoritmo di compressione per i file altamente simili tende a portare a risultati simili a grandezza naturale, in modo da questo trova un sacco di cloni molto rapidamente.

  2. In combinazione con quanto sopra, mantenere entrambe "limite" superiore e inferiore sulla possibile somiglianza tra qualsiasi coppia di ROM. Ciò consente inoltre di priorità. Se ROM A e B sono simili al 95%, e la ROM B e C sono simili solo il 2%, allora sapete già che A e C sono compresi tra 0% e il 7%. Questo è troppo bassa per essere un clone, quindi questo confronto può essere posticipata in modo sicuro o addirittura ignorato del tutto, a meno che non ho molta voglia di conoscere le somiglianze esatte di tutto.

Credo che alcune tecniche prese in prestito dalla compressione dei dati potrebbe essere interessante:

Si supponga di avere due file, A e B.

Comprimere ogni singolo file e aggiungere i formati compressi insieme. Poi concatenare i due file in un unico file di grandi dimensioni, e comprimere esso pure.

La differenza nelle dimensioni vi darà una stima approssimativa quanto simili i file sono.

I suggerisco di provare la trasformazione Tana Wheeler (bzip2) per fare la compressione. La maggior parte degli altri algoritmi di compressione hanno solo una storia limitata. L'algoritmo BWT OTOH può lavorare su grandi blocchi di dati. L'algoritmo "vede" entrambi i file nello stesso momento e qualsiasi somiglianza si tradurrà in un rapporto di compressione più elevato.

xdelta è piuttosto utile per ottenere diff binari decenti: http://xdelta.org

Si può iniziare con la memorizzazione di qualcosa di simile a alberi hash . È necessario solo per memorizzare un tale insieme di hash per ogni ROM, e lo spazio di memorizzazione richiesto è proporzionale solo (ma molto inferiore) la dimensione della ROM, assumendo dimensione del blocco costante. La dimensione del blocco scelto deve dare granularità sufficiente per assicurare la precisione, ad esempio: una dimensione minima di 128MiB, vincolo precisione dell'1% e Tiger-128 hash (simile a quello che usano per controllare i file trasferiti tramite DirectConnect), una dimensione di blocco di 1MiB fa bene ed è possibile memorizzare tutti gli hash di 128 * 128/8 = 2048 byte! Così facendo per 10.000 ROM richiederebbe solo circa 20MiB di spazio. Inoltre, è possibile scegliere un hash meno sicuro, ma più veloce e / o più piccolo. Aggiunta / verifica di similitudine una nuova ROM comporterebbe qualcosa come:

  1. Dividi la nuova ROM in blocchi e hash ciascuno di essi.
  2. Per ogni ROM già nel database, confrontare (vedi sotto) le sue hash con hash della nuova ROM.

La funzione di confronto deve verificare la presenza di similitudine. Ma dovrebbe trattare ogni hash come un valore indivisibile, vale a dire non preoccupatevi cercando di trovare una funzione logica significativa differenza tra due hash. Fino a quando la dimensione del blocco è abbastanza basso e le collisioni hash sono abbastanza rari, la precisione è garantita da un semplice è uguale-confronto.

Come si vede, il problema si riduce a uno più semplice di performance-saggio:. Insiemi di dati molto più piccoli il controllo per somiglianza

Due pensieri:

  • Consideriamo l'organizzazione del file come un grafico di flusso di dati e fare un po 'canonica su quel represention. Dal momento che si conosce il set di istruzioni, questo può essere fattibile, forse solo reggette un disassembler e facendo qualche elaborazione del testo.
  • Un classificatore addestrabile come CRM114 potrebbe rivelarsi utile per dare una rappresentazione compatta che ti dà un po ' idea se i binari hanno molto in comune.

Come ha detto Waylon Flinn, potrebbe essere necessario un algoritmo delta binario. Il rsync algoritmo è un buon compromesso. E 'veloce e affidabile. Si veda anche la .

La difficoltà è che, poiché si tratta di codice eseguibile, semplici cambiamenti possono propagarsi attraverso l'intera ROM. Gli indirizzi e gli offset per tutti i valori possono cambiare con l'aggiunta di una singola variabile o no-op istruzioni. Ciò renderà ancora basata su blocchi hashing inutile.

Una soluzione rapida-and-dirty potrebbe essere quella di incidere su una soluzione con difflib (o l'equivalente w / la vostra lingua preferita), dal momento che si ottiene un confronto scorrevole che può trattare con l'aggiunta o la rimozione dei dati. Dividere la ROM in sezioni eseguibili e dati (se possibile). La sezione di dati possono essere confrontati direttamente e href="http://docs.python.org/library/difflib.html#id1" rel="nofollow noreferrer"> rapporto di somiglianza calcolato, anche se si' ll ancora problemi w / indirizzi o offset.

La sezione eseguibile è più interessante. Leggi su formato asm della macchina, prendere l'eseguibile e dividerlo in una sequenza di codici operativi. Lasciare il codice operativo e registrare le parti, ma mascherare il "payload" / parti "immediate" (dove viene caricato gli indirizzi delle variabili). Consegnare le informazioni risultante alla calcolatrice rapporto di similitudine troppo.

La parte spiacevole è che questo è ancora un O (n ^ 2) il funzionamento del numero di ROM di tenere traccia, ma che può essere alleviata con il clustering (incrementale) o di un ordine di confronto di frequenza-based per ridurre la quantità di confronti necessario.

Non affiliato a StackOverflow
scroll top