Программный подход в Java для сравнения файлов

Question

Какой был бы лучшим подходом для сравнения двух шестнадцатеричных подписей файлов друг к другу для сходства.

Более конкретно, что я хотел бы сделать, это принять шестнадцатеричное представление файла .exe и сравнить его против ряд вирусной подписи. Для этого подхода я планирую разбить файл (EXE) шестнадцатеричное представление в отдельные группы N Chars (т.е. 10 шестнадцатеричных символов) и сделать то же самое с вирусной подписью. Я стремлюсь выполнить какую-то эвристику и, следовательно, статистически проверять, имеет ли этот файл EXE X% сходства с известной вирусной подписью.

Самым простым и вероятно, очень неправильным образом, подумав об этом, является, сравнить EXE [N, N-1] против вируса [n, N-1], где каждый элемент в массиве представляет собой подраздел, а следовательно, EXE1 [0, 9] против Virus1 [0,9]. Каждое подмножество будет оценено статистически.

Как вы можете понять, что было бы огромное количество сравнений и, следовательно, очень очень медленно. Поэтому я считал, что ребята, можете ли вы думать о лучшем подходе, чтобы сделать такое сравнение, например, реализацию различных структур данных вместе.

Это для того, чтобы проект делаю для моего BSC, где пытаюсь разработать алгоритм для обнаружения полиморфных вредоносных программ, это только одна часть всей системы, где другая основана на генетических алгоритмах для развития статической вирусной подписи. Любые советы, комментарии или общая информация, такая как ресурсы, очень приветствуются.

---

Определение: Полиморфные вредоносные программы (вирус, червя, ...) поддерживают ту же функциональность и полезную нагрузку, как их «оригинальная» версия, при этом, видимо, разные структуры (варианты). Они достигают этого по изменению кода и, таким образом, изменяя их шестнадцатеричную подпись. Некоторые из методик, используемых для полиморфизма; Изменение формата (вставьте удалить пробелы), переименование переменной, перемен на перестановку оператора, добавление нежелательного кода, замена оператора (x = 1 изменения в x = y / 5 где y = 5), замена операторов управления. Так много как вирус гриппа мутаты и, следовательно, вакцинация не эффективна, полиморфные вредоносные программы, чтобы избежать обнаружения.

---

Обновлять: После совета вы, ребята, дали мне, что чтение; Я сделал это, но это несколько путает меня больше. Я нашел несколько алгоритмов расстояния, которые могут подать заявку на мою проблему, например;

• Самая длинная общая подпоследовательность
• Алгоритм Левенштейна
• Алгоритм нуждаемости
• Алгоритм смитамана
• Boyer Moore Algorithm
• Ахо Корасик алгоритм

Но теперь я не знаю, который использовать, все, кажется, делают то же самое по-разному. Я буду продолжать делать исследования, чтобы я мог понять каждого лучше; но в то же время вы могли бы вы дать мне свое мнение на which might be more suitable Так что я могу дать ему приоритет во время моих исследований и изучить его глубже.

---

Обновление 2: Я закончил использовать амальгамацию LCSububequeSeque, LCSUBSTRING и LEVENSHTEIN расстояния. Спасибо всем за предложения.

Есть копия готовой бумаги на Гадость

Answer 1

Для алгоритмов, как эти, я предлагаю смотреть в зону биоинформатики. Существует аналогичная задача, установленная там, что у вас есть большие файлы (последовательности генома), в которых вы ищете определенные подписи (гены, специальные известные короткие базовые последовательности и т. Д.).

Также для рассмотрения полиморфных вредоносных программ этот сектор должен вам многое предложить вам, потому что в биологии, кажется, так же трудно получить точные совпадения. (К сожалению, я не знаю о соответствующих алгоритмах поиска / сопоставления / сопоставления, чтобы указать вам.)

Одним из примеров этого направления было бы адаптировать что-то вроде АхО Корасик алгоритм для поиска нескольких вредоносных подписей одновременно.

Точно так же алгоритмы, как Бойер Мур Алгоритм дают вам фантастические поисковые рубрики, особенно для более длительных последовательностей (средний случай O (N / M) для текста размера n, в котором вы ищете рисунок размера M, то есть сублинеарных времен поиска).

Answer 2

Ряд документов были опубликованы на выявлении ближних дублированных документов в большом корпусе документов в контексте WebSearch. Я думаю, что вы найдете их полезными. Например, увидеть это презентация.

Answer 3

Недавно было серьезное количество исследований в автоматизации отчетов об обнаружении дублирующихся ошибок в репозиториях ошибок. Это по сути та же проблема, которую вы сталкиваетесь. Разница в том, что вы используете двоичные данные. Это похожие проблемы, потому что вы будете искать строки, которые имеют одинаковый базовый шаблон, даже если узоры могут иметь несколько небольших различий. Прямой алгоритм расстояния, вероятно, не будет вам хорошо служить вам.

Эта статья дает хорошее резюме проблемы, а также некоторые подходы в его цитатах, которые были опробованы.

ftp://ftp.computer.org/press/Outgoing/prouche/patrick/apsec10/data/4266a366.pdf.

Answer 4

Как указывало кто-то, сходство с известной строкой и биоинформатической проблемой может помочь. Самая длинная общая подстрока очень хрупкая, что означает, что одно значение может вдвое вдвое длину такой строки. Вам нужна форма строкового выравнивания, но более эффективна, чем Smith-Waterman. Я бы постарался посмотреть на такие программы, как Blast, Blat или Mummer3, чтобы увидеть, могут ли они соответствовать вашим потребностям. Помните, что параметры по умолчанию, для этих программ основаны на приложении биологии (сколько наказывать наказание в размере или замене), поэтому вы, вероятно, должны посмотреть на переоценку параметров на основе вашего домена приложения, возможно, на основе Обучающий набор. Это известная проблема, потому что даже в биологии различные приложения требуют различных параметров (на основе, например, на эволюционном расстоянии двух геномов для сравнения). Также возможно, что даже по умолчанию один из этих алгоритмов может производить полезные результаты. Лучше всего будет иметь генеративную модель того, как изменяется вирусы, и это может помочь вам в оптимальном выборе для алгоритма расстояния и сравнения.