Obliczanie Podobieństwa Danych Binarnych

Warto przyjrzeć się bsdiff , który jest binarnym systemem różnicowania/łatania. Istnieje również teza z dużą ilością teorii.

Użyj kilku pomysłów z algorytmów wykrywania Plagiatów .

Mój pomysł:

W celu stworzenia porównywalnej "sygnatury" dla każdego ROM, która zmienia się nieznacznie w miarę zmiany małych porcji, tworząc coś w rodzaju wykresu częstotliwości słów, ale zamiast rejestrować częstotliwości słów, możesz hashować bardzo krótkie sekcje ROM i rejestrować częstotliwości wartości skrótu.

Nie tylko hashować jedną sekcję, a następnie następną sekcję rozpoczynającą się od końca pierwszej sekcja, ale zamiast tego użyj przesuwanego okna, hashując sekcję począwszy od bajtu 1, następnie hashując sekcję tej samej wielkości począwszy od bajtu 2, potem od bajtu 3, itd. To zaneguje efekt zmiennych rozmiarów różnych części w Twoim ROM.

Jeśli użyłeś prostej funkcji skrótu, takiej jak xor każdego 8-bitowego bajtu, dzięki czemu możesz łatwo obliczyć hash następnej pozycji okna przez XOR bieżący hash z wychodzących 8 bitów i XOR przychodzących 8 bitów. Inna alternatywna funkcja hashowania może być po prostu użycie długości słowa kodu instrukcji. Może to wystarczyć do stworzenia statycznych wzorców dla kodów reprezentujących instrukcje maszynowe. Ważne jest to, że będziesz potrzebował funkcji skrótu, która powoduje wspólne krótkie sekwencje w kodzie instrukcji, co skutkuje tymi samymi wartościami skrótu.

Prawdopodobnie chcesz mniej wartości skrótu z wyższymi częstotliwościami każdego z nich, ale nie idź za daleko, bo twój wykres będzie zbyt płaski, co spowoduje trudności w porównaniu ich. Podobnie nie idź zbyt szeroko, bo będziesz miał wiele bardzo małych częstotliwości, co ponownie trudne porównanie.

Zapisz ten wykres na ROM. Porównaj wykresy częstotliwości dla dwóch różnych ROM, obliczając sumę kwadratów różnicy częstotliwości dla każdej wartości skrótu. Jeśli suma ta wynosi zero, to Rom prawdopodobnie będzie identyczny. Im dalej od zera, tym mniej podobne będą Romy.

Choć minęło dużo więcej niż "kilka dni", pomyślałem, że powinienem dodać moje obecne rozwiązanie tutaj.

Nils Pipenbrinck szedł w tym samym kierunku, co moja obecna metoda. Ponieważ jednym z głównych wyników znajdowania klonów jest ogromne oszczędności dzięki solidnej archiwizacji, pomyślałem, że mogę po prostu spróbować skompresować dowolne dwa Romy razem i zobaczyć, ile miejsca zostało zaoszczędzone. Używam do tego algorytmu LZMA w 7zip .

Pierwszym krokiem jest skompresowanie każdego Pojedynczo i zanotuj rozmiar skompresowany, a następnie spróbuj zarchiwizować dowolne dwa Romy razem i zobacz, jak bardzo wynikowy rozmiar różni się od ich indywidualnych skompresowanych rozmiarów. Jeśli łączna wielkość jest taka sama jak suma poszczególnych rozmiarów, są one o 0% podobne, a jeśli wielkość jest taka sama jak jedna z nich (największa), są identyczne.

Teraz, jest to ogromna liczba prób kompresji wymagane, więc mam kilka optymalizacji do tej pory (i chciałbym dowiedzieć się więcej):

1. Ustalanie priorytetów porównań na podstawie podobieństw skompresowanych rozmiarów. Jeśli ROM A ma skompresowany rozmiar 10MB, a ROM B ma skompresowany rozmiar 2MB, nie jest możliwe, aby były podobne o więcej niż 20%, więc porównanie ich w celu uzyskania rzeczywistego wyniku może zostać pozostawione na później. Uruchomienie tego samego algorytmu kompresji na bardzo podobnych plikach powoduje wyniki o podobnej wielkości, więc bardzo szybko znajduje to wiele klonów.

2. W połączeniu z powyżej, zachowaj zarówno górną, jak i dolną "granicę" na możliwym podobieństwie między dowolną parą Romów. Pozwala to na dalsze ustalanie priorytetów. Jeśli ROM A i B są podobne w 95%, A ROM B I C są tylko 2% podobne, to już wiesz, że A I C są między 0% a 7%. Jest to zbyt niskie, aby być klonem, więc porównanie to można bezpiecznie odłożyć lub nawet całkowicie zignorować, chyba że naprawdę chcę znać dokładne podobieństwa wszystkiego.

Myślę, że niektóre techniki zapożyczone z kompresji danych mogą być tutaj interesujące:

Załóżmy, że masz dwa pliki, A I B.

Kompresuj każdy plik indywidualnie i dodaj skompresowane rozmiary razem. Następnie połącz oba pliki w jeden, duży plik i skompresuj go.

Różnica w rozmiarach da ci przybliżone oszacowanie, jak podobne są pliki.

Proponuję wypróbować transformację Burrowa Wheelera (bzip2), aby wykonać kompresję. Większość innych algorytmów kompresji ma tylko ograniczoną historię. Algorytm BWT otoh może pracować na bardzo dużych fragmentach danych. Algorytm "widzi" oba pliki w tym samym czasie, a każde podobieństwo spowoduje wyższy współczynnik kompresji.

XDelta jest całkiem przydatna do uzyskiwania porządnych binarnych diffów: http://xdelta.org

Możesz zacząć od przechowywania czegoś w rodzaju hash trees . Dla każdego ROM jest potrzebny tylko jeden taki zestaw skrótów, a wymagana przestrzeń dyskowa jest tylko proporcjonalna (ale znacznie mniejsza od) rozmiaru ROM, przy założeniu stałej wielkości bloku. Wybrany rozmiar bloku musi dawać wystarczającą ziarnistość, aby zapewnić dokładność, np.: dla minimalnego rozmiaru 128mib, ograniczenie dokładności 1% i Tiger-128 hash (podobny do tego, którego używają do sprawdzania plików przesyłanych przez DirectConnect), blok o rozmiarze 1mib działa dobrze i można przechowywać wszystkie hasze w 128 * 128 / 8 = 2048 bajtów! Tak więc robienie tego dla 10,000 ROM wymagałoby tylko około 20MB miejsca. Co więcej, możesz wybrać mniej bezpieczny, ale szybszy i/lub mniejszy hash. Dodawanie / sprawdzanie podobieństwa nowy ROM pociąga za sobą coś w stylu:

1. podziel nowy ROM na bloki i hashuj każdy z nich.
2. dla każdego ROM już w bazie danych, porównaj (patrz poniżej) jego skróty z nowymi ROM ' AMI hashes.

Funkcja porównywania powinna sprawdzać podobieństwo. Powinien jednak traktować każdy hash jako niepodzielną wartość, tzn. nie trudzić się szukaniem logicznie znaczącej funkcji różnicy między dwoma hashami. Tak długo, jak rozmiar bloku jest wystarczająco niski, a kolizje hashów są wystarczająco rzadkie, dokładność jest gwarantowana przez proste porównanie is-equal.

Jak widzisz, problem sprowadza się do prostszego pod względem wydajności: sprawdzania znacznie mniejszych zestawów danych pod kątem podobieństwa.

Dwie myśli:

• rozważ zorganizowanie pliku jako wykresu przepływu danych i dokonaj kanonicznej klasyfikacji tego represjonowania. Ponieważ znasz zestaw instrukcji, może to być wykonalne, może po prostu przywiązanie disassemblera i przetwarzanie tekstu.
• klasyfikator trainable, taki jak CRM114 może się przydać, aby dać ci zwartą reprezentację, która daje ci pewne pojęcie, czy binaria mają wiele wspólnego.

Jak powiedział Waylon Flinn, możesz potrzebować binarnego algorytmu delta. Algorytm rsync jest dobry. Jest szybki i niezawodny. Zobacz także dokumentację narzędzia .

Trudność polega na tym, że ponieważ masz do czynienia z kodem wykonywalnym, proste zmiany mogą rozprzestrzeniać się w całej pamięci ROM. Adresy i przesunięcia dla wszystkich wartości mogą się zmieniać po dodaniu pojedynczej zmiennej lub instrukcji no-op. To uczyni nawet blokowe hashowanie bezwartościowym.

Szybkim i brudnym rozwiązaniem byłoby zhakowanie rozwiązania za pomocą difflib (lub równoważnego w / ulubionym języku), ponieważ daje Ci przesuwne porównanie, które może radzić sobie z danymi dodawanie lub usuwanie. Podziel ROM na sekcje wykonywalne i dane (jeśli to możliwe). Sekcja danych może być porównana bezpośrednio i współczynnik podobieństwa obliczony , choć nadal będziesz miał problemy z / adresami lub przesunięciami.

Sekcja wykonywalna jest ciekawsza. Odczytaj format ASM maszyny, weź plik wykonywalny i podziel go na sekwencję kodów opcodes. Pozostaw kod opcode i zarejestruj części, ale zamaskuj części "payload" / " immediate "(gdzie ładuje zmienne adresy). Podaj wynikowe informacje do kalkulatora współczynnika podobieństwa.

Niefortunną częścią jest to, że jest to nadal operacja O(n^2) na liczbie pamięci ROM, które śledzisz, ale można to złagodzić za pomocą (przyrostowego) klastrowania lub kolejności porównywania opartej na częstotliwości, aby zmniejszyć ilość potrzebnych porównań.