Podejście programistyczne w Javie do porównywania plików

Question

Jakie byłoby najlepsze podejście do porównywania dwóch podpisów heksadecymalnych pod względem podobieństwa.

Dokładniej, chciałbym wykonać szesnastkową reprezentację pliku .exe i porównać ją z serią sygnatur wirusów. W tym podejściu planuję złamać reprezentację heksadecymalną pliku (exe) w poszczególne grupy N znaków (tj. 10 znaków szesnastkowych) i zrobić to samo z podpisem wirusa. Mam zamiar przeprowadzić heurystykę, a zatem statystycznie sprawdzić, czy plik exe ma X% podobieństwa w stosunku do znanego sygnatury wirusów.

Najprostszym i najprawdopodobniej błędnym sposobem, w jaki myślałem o zrobieniu tego, jest porównanie exe [n, n-1] z wirusem [n, n-1], gdzie każdy element w tablicy jest podtablicą, a zatem exe1 [0,9] przeciwko wirusowi1 [0,9]. Każdy podzbiór zostanie oceniony statystycznie.

Jak można sobie wyobrazić, byłaby ogromna liczba porównań, a co za tym idzie, bardzo powolna. Zastanawiałem się, czy zapytać, czy potraficie wymyślić lepsze podejście do takiego porównania, na przykład wspólnie wdrażając różne struktury danych.

To jest dla projektu robię dla mojego BSc, gdzie próbuję opracować algorytm do wykrywania polimorficznego szkodliwego oprogramowania, to tylko jedna część całego systemu, gdzie druga jest oparta na algorytmach genetycznych, aby rozwinąć statyczny wirus podpis. Wszelkie rady, uwagi lub ogólne informacje, takie jak zasoby, są bardzo mile widziane.

---

Definicja: polimorficzne złośliwego oprogramowania (wirusy, robaki, ...) utrzymuje taką samą funkcjonalność i ładowność jako ich „oryginalnej” wersji, mając najwyraźniej różne struktury (warianty). Osiągają to poprzez obfuskację kodu i tym samym zmieniają swój podpis heksagonalny. Niektóre z technik stosowanych do polimorfizmu są; zmiana formatu (wstaw usuń puste), zmienna zmiana nazwy, reorganizacja instrukcji, dodawanie nowego kodu, zastępowanie instrukcji (x = 1 zmiana na x = y/5 gdzie y = 5), zamiana instrukcji sterujących. Tak jak wirus grypy mutuje, a zatem szczepienie nie jest skuteczne, polimorficzne szkodliwe oprogramowanie mutuje, aby uniknąć wykrycia.

---

Aktualizacja: Po radzę chłopaki dali mi w odniesieniu do jakich czytanie zrobić; Zrobiłem to, ale nieco mnie to zdezorientowało. Znalazłem kilka algorytmów odległości, które można zastosować do mojego problemu, takie jak;

• Najdłuższy wspólny podciąg
• algorytm Levenshteina
• Needleman-Wunsch algorytm
• Smith-Waterman algorithm
• Boyer Moore algorytm
• Algorytm Aho-Corasick

Ale teraz don Wiedząc, z czego korzystać, wszystkie wydają się robić to samo na różne sposoby. Będę kontynuować badania, aby lepiej zrozumieć każdego; ale w międzyczasie mógłbyś dać mi swoją opinię na temat which might be more suitable, abym mógł nadać mu priorytet podczas moich badań i pogłębić to badanie.

---

Aktualizacja 2: skończyło się używając konglomerat z LCSubsequence, LCSubstring i Odległość Levenshteina. Dziękuję wszystkim za sugestie.

Istnieje egzemplarz gotowego papieru na GitHub

Answer 1

Dla algorytmów takich jak te sugeruję zajrzeć do obszaru bioinformatyki. Istnieje podobne ustawienie problemu, ponieważ masz duże pliki (sekwencje genomu), w których szukasz określonych sygnatur (geny, specjalne, dobrze znane krótkie sekwencje podstawowe itp.).

Również za uwzględnienie polimorficznego złośliwego oprogramowania, ten sektor powinien zaoferować wiele, ponieważ w biologii wydaje się równie trudne uzyskanie dokładnych dopasowań. (Niestety, nie jestem świadomy odpowiednich algorytmów wyszukiwania/dopasowywania, które by wskazywały.)

Jednym z przykładów z tego kierunku byłoby zaadaptowanie czegoś takiego jak algorytm Aho Corasick w celu wyszukania kilku sygnatur złośliwego oprogramowania w tym samym czasie .

Podobnie algorytmy, takie jak algorytm Boyer Moore, zapewniają fantastyczne środowisko wyszukiwania, szczególnie w przypadku dłuższych sekwencji (średni przypadek O (N/M) dla tekstu o rozmiarze N, w którym szukany jest wzorzec o rozmiarze M, tj. Sublinearne wyszukiwanie czasy).

Answer 2

Szereg referatów zostały opublikowane na znalezieniu w pobliżu duplikatów dokumentów w dużym zbiorze dokumentów w kontekście WebSearch. Myślę, że znajdziesz je przydatne. Na przykład zobacz ten presentation.

Answer 3

Ostatnio przeprowadzono wiele badań dotyczących automatyzacji wykrywania powtarzających się raportów o błędach w repozytoriach błędów. Jest to zasadniczo ten sam problem, z którym stoisz. Różnica polega na tym, że używasz danych binarnych. Są podobne problemy, ponieważ będziesz szukał ciągów, które mają ten sam podstawowy wzór, nawet jeśli wzory mogą mieć pewne drobne różnice. Prosty algorytm odległości prawdopodobnie nie będzie ci dobrze służył.

W tym artykule przedstawiono dobre podsumowanie problemu, a także kilka podejść w cytowanych próbach.

ftp://ftp.computer.org/press/outgoing/proceedings/Patrick/apsec10/data/4266a366.pdf

Answer 4

Jak ktoś zauważył, podobieństwo ze znanym ciągiem i bioinformatyka problemu może pomóc. Najdłuższy wspólny podciąg jest bardzo kruchy, co oznacza, że ​​jedna różnica może zmniejszyć o połowę długość takiego sznurka. Potrzebujesz formy wyrównania łańcucha, ale bardziej wydajnej niż Smith-Waterman. Spróbowałbym spojrzeć na programy takie jak BLAST, BLAT lub MUMMER3, aby sprawdzić, czy mogą one pasować do twoich potrzeb. Pamiętaj, że domyślne parametry dla tych programów są oparte na aplikacji biologii (ile można karać wstawienia lub podstawienia dla instancji), więc prawdopodobnie powinieneś spojrzeć na ponownej oceny parametrów w oparciu o domenę aplikacji, prawdopodobnie w oparciu o zestaw treningowy. Jest to znany problem, ponieważ nawet w biologii różne aplikacje wymagają różnych parametrów (na przykład na podstawie ewolucyjnej odległości dwóch genomów do porównania). Możliwe jest jednak również, że nawet przy domyślnym ustawieniu jeden z tych algorytmów może dać użyteczne wyniki. Najlepszy ze wszystkich byłoby posiadanie generatywnego modelu zmiany wirusów, który mógłby pomóc w wyborze optymalnego algorytmu odległości i porównania.