Что такое нечеткий хэш

Обновлено: 15.01.2025

Создатели вредоносных программ используют массу разных методов, чтобы скрыть свои творения от антивирусных средств и статических-динамических анализаторов. Однако и антивирусы не лыком шиты: для поиска «родственных» семплов они используют продвинутые алгоритмы хеширования. Сегодня мы расскажем, как работают эти алгоритмы, — с подробностями и наглядными примерами.

На практике в большинстве случаев существующая база или ядро вредоноса повторно используется для создания новой разновидности малвари. Вирусописатели особо не заморачиваются с затратной по времени разработкой новых «качественных» вирусов, а просто используют имеющиеся образцы.

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

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

Хеш «четкий»

Ханс Петер Лун из IBM еще в 1940-е разрабатывал системы для анализа информации, в том числе исследовал вопросы хранения, передачи и поиска текстовых данных. Это привело его к созданию алгоритмов преобразования, а затем и к хешированию информации в качестве способа поиска телефонных номеров и текста. Так индексация и концепция «разделяй и властвуй» сделали свои первые шаги в области вычислительной техники.

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

Мы привыкли ассоциировать хеш-функции с криптографическими хеш-функциями. Это распространенный инструмент, который используется для решения целого ряда задач, таких как:

аутентификация;
электронная подпись;
обнаружение вредоносного ПО (как файлов, так и их маркеров компрометации).

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

Что такое хеш

Криптографическая хеш-функция, чаще называемая просто хешем, — это математическое преобразование, переводящее произвольный входной массив данных в состоящую из букв и цифр строку фиксированной длины. Хеш считается криптостойким, если справедливо следующее:

по хешу нельзя восстановить исходные данные;
выполняется устойчивость к коллизиям, то есть невозможно получить из различных входных последовательностей одинаковые хеши.

MD5, SHA-1 и SHA-256 — наиболее популярные криптографические алгоритмы вычисления хеша, которые часто используются в детектировании вредоносного ПО. Еще совсем недавно вредонос опознавали только по сигнатуре (хешу) исполняемого файла.

Но в современных реалиях недостаточно знать просто хеш объекта, так как это слабый индикатор компрометации (IoC). IoC — это все артефакты, на основе которых может быть выявлен вредонос. Например, используемые им ветки реестра, подгружаемые библиотеки, IP-адреса, байтовые последовательности, версии ПО, триггеры даты и времени, задействованные порты, URL.

Рассмотрим «пирамиду боли» для атакующего, придуманную аналитиком в области информационной безопасности Дэвидом Бьянко. Она описывает уровни сложности индикаторов компрометации, которые злоумышленники используют при атаках. Например, если ты знаешь MD5-хеш вредоносного файла, его можно довольно легко и при этом точно обнаружить в системе. Однако это принесет очень мало боли атакующему — достаточно добавить один бит информации к файлу вредоноса, и хеш изменится. Таким образом вирус может переселяться бесконечно, и каждая новая его копия будет иметь отличный от других экземпляров хеш.

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

Как же определить схожесть между разными образцами малвари одного семейства?

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

«Нечеткий» хеш — SSDeep

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

Нечеткое хеширование — это метод, при котором программа, такая как, например, SSDeep, вычисляет кусочные хеши от входных данных, то есть использует так называемое контекстно вызываемое кусочное хеширование. В англоязычных источниках этот метод называется context triggered piecewise hashing (CTPH aka fuzzy hashing).

На самом деле классификаций нечетких хешей довольно много. Например, по механизму работы алгоритмы делятся на piecewise hashing, context triggered piecewise hashing, statistically improbable features, block-based rebuilding. По типу обрабатываемой информации их можно разделить на побайтовые, синтаксические и семантические. Но если речь заходит о нечетких хешах, то это, как правило, CTPH.

Алгоритм SSDeep разработан Джесси Корнблюмом для использования в компьютерной криминалистике и основан на алгоритме spamsum. SSDeep вычисляет несколько традиционных криптографических хешей фиксированного размера для отдельных сегментов файла и тем самым позволяет обнаруживать похожие объекты. В алгоритме SSDeep используется механизм скользящего окна rolling hash. Его еще можно назвать рекурсивным кусочным хешированием.

Часто CTPH-подобные хеши лежат в основе алгоритмов локально чувствительных хешей — locality-sensitive hashing (LSH). В их задачи входит поиск ближайших соседей — approximate nearest neighbor (ANN), или, проще говоря, похожих объектов, но с чуть более высокоуровневой абстракцией. Алгоритмы LSH используются не только в борьбе с вредоносным ПО, но и в мультимедиа, при поиске дубликатов, поиске схожих генов в биологии и много где еще.

Алгоритм SSDeep

Как работает SSDeep? На первый взгляд, все довольно просто:

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

Virus Total использует SSDeep, который выполняет нечеткое хеширование на загружаемых пользователями файлах. Пример — по ссылке.

Продолжение доступно только участникам

Членство в сообществе в течение указанного срока откроет тебе доступ ко ВСЕМ материалам «Хакера», позволит скачивать выпуски в PDF, отключит рекламу на сайте и увеличит личную накопительную скидку! Подробнее

Следует отметить, что rspamd использует нечеткие хеши не только для сравнения текстовых данных, но и изображений и других вложений в письмах. Однако в этом случае отсутсвует элемент нечеткой логики, и rspamd ищет точные соответствия для одинаковых объектов.

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

Шаг 1: выбор источников хешей

В первую очередь необходимо выбрать источники образцов спама для обучения. Основной принцип - использование для обучения спам-рассылок, которые приходят многим пользователям. Существует два основных подхода к решению подобной задачи:

использование жалоб пользователей;
создание ловушек для спама (honeypot).

Использование жалоб пользователей

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

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

В rspamd также есть две возможности, позволяющие отсеивать некоторые “ложные” срабатывания:

Первый метод довольно прост: давайте назначим каждой жалобе некоторый вес и при каждом обучении будем прибавлять его к сохраненному значению соответствующего хеша. При проверке мы не будем учитывать хеши, вес которых меньше заданного порога. Например, если вес жалобы w=1 , а порог срабатывания t=20 , то для начала срабатывания хеша необходимо как минимум 20 жалоб пользователей. Кроме этого, при проверке для хеша, превышающего пороговое значение, rspamd назначает не максимальные очки, а их величина плавно растет от нуля до максимума (до значения метрики) при изменении веса хеша от порогового до удвоенного порогового значения (t .. 2*t).

Настройка ловушек спама

Для данного метода необходимо иметь такие почтовые адреса, на которые не приходит легитимная почта, зато приходит много спама. Основная идея заключается в том, чтобы “засветить” адрес в базах спамеров, не показывая его легитимным пользователям. Для этого можно, например, разместить на достаточно популярном веб-сайте элемент iframe, который не отображается пользователям (имеет свойство hidden или нулевой видимый размер), но содержит доступные ботам email-адреса ловушек. В последнее время этот метод стал не очень эффективен, так как спамеры научились обходить такие приемы.

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

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

Шаг 2: Настройка хранилища

В данной главе я рассмотрю основные настройки хранилища и как оптимизировать его работу.

Важное замечание: хранилище работает не с письмами, а с готовыми хешами. То есть, чтобы преобразовать письмо в его хеш нужен отдельный процесс сканера или контроллера:

Хранение и проверка хешей
Транспортное шифрование протокола
Удаление устаревших хешей
Контроль доступа (как на запись, так и на чтение)
Репликация (с версии 1.3)

Архитектура хранилища

Для хранения данных используется sqlite3, и это накладывает некоторые ограничения на архитектуру хранилища.

Во-первых, sqlite крайне плохо работает при конкурентных запросах на запись: в этом случае производительность СУБД падает на несколько порядков. Во-вторых, довольно затруднительно обеспечивать репликацию и масштабирование базы данных, так как для этого нужны сторонние инструменты.

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

Устаревание хешей

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

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

Пример настройки

За хранение нечетких хешей отвечает процесс rspamd под названием fuzzy_storage . Для включения и настройки этого процесса можно использовать локальный файл конфигурации rspamd: etc/rspamd/rspamd.conf.local :

Настройки доступа

Важное замечание: Если в списке серверов в конфигурации плагина fuzzy_check (см. далее) присутствует имя localhost , необходимо разрешить доступ как с адреса 127.0.0.1, так и с адреса ::1, так как резолвер возвращает поочередно все известные для имени хоста адреса.

Также для разграничения доступа может использоваться транспортное шифрование, которое мы рассмотрим далее.

Транспортное шифрование

Чтобы настроить транспортное шифрование, в первую очередь нужно создать пару ключей для сервера хранилища с помощью команды rspamadm keypair -u :

Каждое хранилище может работать одновременно с произвольным числом ключей:

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

Для включения режима обязательного шифрования используется опция encrypted_only :

В этом режиме клиенты, у которых нет действительного открытого ключа, не смогут обращаться к хранилищу.

Проверка работы хранилища

Для проверки работы хранилища можно использовать команду rspamadm control fuzzystat :

Сначала отображается общая статистика хранилища: количество сохраненных и устаревших хешей, а также распределение запросов по версиям протокола клиента:

v0.6 - запросы от rspamd 0.6 - 0.8 (устаревшие версии, ограниченно совместимы)
v0.8 - запросы от rspamd 0.8 - 0.9 (частично совместимы)
v0.9 - незашифрованные запросы от rspamd 0.9+ (полностью совместимы)
v1.1 - зашифрованные запросы от rspamd 1.1+ (полностью совместимы)

Далее по каждому из ключей, сконфигурированных в хранилище, отображается подробная статистика по последним IP-адресам клиентов, от которых были получены запросы. И в заключение можно увидеть общую статистику по IP-адресам.

для изменения вывода этой команды можно использовать следующие опции (например, rspamadm control fuzzystat -n ):

-n : выводить “сырые” числа без сокращения
--short : не выводить подробную статистику по ключам и IP-адресам
--no-keys : не выводить статистику по ключам
--no-ips : не выводить статистику по IP-адресам
--sort : сортировать:
- checked : по числу проверенных хешей (по умолчанию)
- matched : по числу найденных хешей
- errors : по числу ошибочных запросов
- ip : по IP-адресу лексикографически
Шаг 3: Настройка плагина fuzzy_check

Плагин fuzzy_check используется процессами-сканерами для проверки писем и процессами-контроллерами для обучения хранилища.
1. Обработка писем и создание хешей их отдельных частей
2. Выполнение запросов к хранилищу
3. Транспортное шифрование
Обучение поизводится командой rspamc fuzzy_add :

Где параметр -w задает вес хеша, который мы обсуждали ранее, а -f указывает номер флага.

Флаги позволяют хранить хеши различного происхождения в хранилище. Например, хеши спам-ловушек, хеши жалоб пользователей и хеши писем из “белого” списка. Каждый флаг может быть ассоциирован с собственным символом и, соответственно, иметь свой вес при проверке письма:

Флаг можно указывать как по номеру:

так и по символу:

Соответсвие символов флагам нужно настроить в секции rule .

Рассмотрим некоторые полезные опции, которые можно настраивать в модуле.

Во-первых, max_score полезен для задания веса порога срабатывания данного хеша:

Вторым полезным параметром является mime_types , который определяет, какие типы вложений проверять (и обучать!) в данном хранилище. Этот параметр представляет собой список допустимых типов в формате ["type/subtype", "*/subtype", "type/*", "*"] , где * заменяет любой допустимый тип. Как правило, достаточно сохранять хеши всех вложений типа application/* . Текстовые части и вложенные изображения автоматически проверяются плагином fuzzy_check (то есть, нет нужды добавлять image/* в список проверяемых вложений). Стоит иметь в виду, что вложения и изображения проверяются на точное соответствие, в отличие от текстов, которые могут немного отличаться.

Очень важной является опция read_only , если вы хотите обучать ваше хранилище. По умолчанию read_only=true , что означает невозможность обучения хранилища:

Параметр encryption_key задает открытый ключ хранилища и включает шифрование запросов.

Параметр algorithm определяет алгоритм генерации хешей из текстовых частей писем (для вложений и изображений всегда используется blake2b). Исторически в rspamd использовался алгоритм siphash. Однако он имеет определенные проблемы с производительностью, особенно на устаревшем “железе” (CPU до Intel Haswell). Поэтому при создании собственного хранилища стоит рассмотреть другие, более быстрые алгоритмы:

Для большинства задач я рекомендую использовать mumhash или fasthash , которые демонстрируют отличную производительность на множестве платформ. Для оценки поризводительности вы можете скомпилировать набор тестов из исходного кода rspamd:

и запустить тест различных вариантов алгоритмов вычисления хешей на вашей платформе:

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

Написание скриптов-условий для обучения

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

В некоторых случаях полезно распределять обучение хешей по различным флагам в соответствии с их источником, который можно закодировать, например, в заголовке X-Source . Допустим, мы хотим иметь такое соответствие флагов и источников:
- honeypot - “черный” список: 1
- users_unfiltered - “серый” список: 2
- users_filtered - “черный” список: 1
- FP - “белый” список: 3
Тогда скрипт, осуществляющий такое распределение, может выглядеть следующим образом:

Шаг 4: Настройка репликации хешей

Зачастую бывает нужно собирать хеши из различных источников или иметь локальную копию удаленного хранилища. Начиная с версии 1.3 в rspamd для решения этой задачи реализована поддержка репликации на уровне хранилища хешей:

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

В таком случае рекомендуется заново клонировать базу данных путем “холодной” синхронизации.

Холодная синхронизация

Данная процедура служит для инициализации нового слейва или восстановления репликации после потери связи мастера со слейвом.

Для выполнения синхронизации на хосте мастера нужно остановить сервис rspamd и сделать дамп базы данных хешей (rspamd можно и не останавливать, но если за время клонирования базы данных версия мастера увеличится более чем на 1, процедуру придется повторить):

далее полученный файл fuzzy.sql копируется на все слейвы (rspamd на слейвах можно не останавливать):

После чего можно запускать rspamd сначала на слейвах, а затем на мастере.

Конфигурирование репликации

Репликация настраивается в конфигурационном файле хранилища хешей - worker-fuzzy.inc. Мастер репликации настраивается следующим образом:

Немного остановлюсь на настройке ключей для шифрования. Обычно для установления шифрованных соединений rspamd не требует конфигурирования ключа на обеих сторонах - ключ клиента генерируется автоматически. Однако в данном случае клиентом выступает мастер, поэтому на слейвах можно задать конкретный (открытый) ключ, по которому они будут проверять команды обновления. Также можно задать допустимые IP-адреса мастера, но защита по ключу является более надежной (кроме того, эти методы можно комбинировать).

Настройка слейва выглядит похоже:

Также на слейве можно настроить трансляцию флагов, получаемых с мастера, чтобы избежать коллизий с локальными хешами. Например, если мы хотим транслировать флаги 1 , 2 и 3 во флаги 10 , 20 и 30 соответственно, то можно написать такую конфигурацию:

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

Нечеткое хеширование — это метод, при котором программа, такая как, например, SSDeep, вычисляет кусочные хеши от входных данных, то есть использует так называемое контекстно вызываемое кусочное хеширование. В англоязычных источниках этот метод называется context triggered piecewise hashing (CTPH aka fuzzy hashing).

На самом деле классификаций нечетких хешей довольно много. Например, по механизму работы алгоритмы делятся на piecewise hashing, context triggered piecewise hashing, statistically improbable features, block-based rebuilding. По типу обрабатываемой информации их можно разделить на побайтовые, синтаксические и семантические. Но если речь заходит о нечетких хешах, то это, как правило, CTPH.

Алгоритм SSDeep разработан Джесси Корнблюмом для использования в компьютерной криминалистике и основан на алгоритме spamsum. SSDeep вычисляет несколько традиционных криптографических хешей фиксированного размера для отдельных сегментов файла и тем самым позволяет обнаруживать похожие объекты. В алгоритме SSDeep используется механизм скользящего окна rolling hash. Его еще можно назвать рекурсивным кусочным хешированием.

Часто CTPH-подобные хеши лежат в основе алгоритмов локально чувствительных хешей — locality-sensitive hashing (LSH). В их задачи входит поиск ближайших соседей — approximate nearest neighbor (ANN), или, проще говоря, похожих объектов, но с чуть более высокоуровневой абстракцией. Алгоритмы LSH используются не только в борьбе с вредоносным ПО, но и в мультимедиа, при поиске дубликатов, поиске схожих генов в биологии и много где еще.

Алгоритм SSDeep

Как работает SSDeep? На первый взгляд, все довольно просто:
- он разделяет файл на более мелкие части и изучает их, а не файл в целом;
- он может определить фрагменты файлов, которые имеют последовательности одинаковых байтов, расположенных в схожем порядке, либо байты между двумя последовательностями, где они могут различаться как по значению, так и по длине.
Virus Total использует SSDeep, который выполняет нечеткое хеширование на загружаемых пользователями файлах. Пример — по ссылке.

Virus Total использует SSDeep

Итак, рубрика э-э-эксперименты! Возьмем по 18 образцов исполняемых файлов нашумевших вирусяк: среди них — MassLogger (имена образцов будут начинаться с аббревиатуры ML), Agent Tesla (AT) и Emotet (EMO). Только вот где мы найдем такое количество малвари? Да на базаре.

Мы будем работать с .EXE-семплами, у каждого из испытуемых объектов уникальная криптографическая хеш-сумма SHA-1. Перечислим их все (команда для любителей Linux: shasum ML ):

С использованием SSDeep рассчитаем кусочный хеш каждого из файлов и сохраним результат в файле командой ssdeep MassLogger/* > ML.ssd . На выходе получим следующее:

Выглядит пугающе, правда? Давай сравним объекты между собой (в выводе мы предварительно удалили дубли, оставив уникальные совпадения между семплами). Для этого используем следующую команду:

В выводе команды правый столбец — процент совпадения между семплами.

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

Связи исследуемых семплов

Сразу изобразим граф связности для образцов Agent Tesla. Не будем перечислять хеш-суммы образцов, а сразу приступим к сравнению: сначала файлов между собой, затем с семплами MassLogger.

Граф связности для образцов Agent Tesla

Для Agent Tesla также обнаружено два семейства взаимосвязанных семплов и десять воинов-одиночек. Что дальше? Сравним SSDeep-хеши MassLogger с объектами Emotet. Пусто, нет совпадений. А если с Agent Tesla? Строим граф.

Сравнение MassLogger с Agent Tesla

Бинго! Совпадения есть, и взаимопроникновение фрагментов кода семейств Agent Tesla и MassLogger доказано.

Однако не всегда у исследователя достаточно семплов и образцов вредоносов других семейств — например, для семейства Emotet. На графе видно, что из всех 18 объектов 13 так или иначе связаны между собой, а семплы EMO3, EMO9, EMO11, EMO15 и EMO18 не нашли «друзей», и их мы отражать на рисунке не станем.

Взаимосвязи объектов на графе

Итак, что же в итоге у нас получилось? У групп MassLogger есть пять объектов, связанных с объектами Agent Tesla. Почему так вышло? Во-первых, это два кейлоггера, у них есть пересечения в функциональности. Во-вторых, они оба используют один и тот же загрузчик. В каждом из тестов находились связи (то есть сходства) между объектами более чем на 50%. Иными словами, из 18 образцов так или иначе были связаны между собой как минимум девять. Среди семплов нашлись по меньшей мере две группы связанных объектов, а у Emotet — сразу три группы. Теперь давай рассмотрим другой тип хеш-функций, и, возможно, мы найдем новые взаимосвязи.

Цель данной работы заключается в разработке оптимального алгоритма нечеткого поиска по словарю для базы данных.

В ходе выполнения работы был реализован алгоритм поиска на основе хэширования. Основная метрика, которая применялась для сравнения строк — расстояние Левенштейна. Данный алгоритм должен быть достаточно эффективным, чтобы сократить время поиска, так как метрика Левенштейна имеет квадратичную сложность.

Все алгоритмы были реализованы в Ruby 2.2.4, графики были выполнены в программе Matlab 2010.

Ключевые слова: нечеткий поиск, расстояние Левенштейна, хэширование

В данной работе будет предложен алгоритм поиска наиболее близких значений из словаря к входному запросу. Некоторые выводы, используемые в работе, были основаны на результатах работ Бойцова Л. М. [1], т. к. в своих статьях он уже проводил сравнения основных алгоритмов и повторение полученных им результатов является нецелесообразным.

Общая проблематика нечеткого поиска.

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

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

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

Выбор метрики сравнения слов.

Наиболее распространенной метрикой является метрика Левенштейна. Расстояние Левенштейна — это наименьшее расстояние редактирования такое, что одна строка переходит в другую. Данная метрика очень популярна и используется повсеместно, поэтому не будем останавливаться на ней подробно.

В случае сравнения строк, предпочтительней высчитывать расстояние для каждого слова отдельно, а не для строки целиком. Более того, необходимо выполнить нормировку, чтобы оценить коэффициент схожести слов. В нашем случае данный коэффициент будет вычисляться по следующей формуле:

,

где d(S1(i),S2(i)) расстояние Левенштейна, n — кол-во слов в строке (обычно для ФИО n=3); S1,S2 состоят из последовательности слов, поэтому вычисляем расстояние Левенштейна для каждой пары слов; k — показывает схожесть двух последовательностей слов (два ФИО).

Метод индексирования словаря.

Вычисление расстояния Левенштейна имеет квадратичную сложность, поэтому очень важно выбрать в исходном словаре множество, которое могло бы содержать исходный запрос. подобные методы основаны на сэмплировании, т. е. выделении характерных элементов строк. Наиболее подходящим методом для небольшой базы данных (до 500000 тыс. элементов словаря) является хэширование по сигнатуре [1]. Данный подход обеспечивает наилучшее соотношение качества поиска и скорости обработки запроса. Он имеет преимущество по сравнению с другими методами, такими как soundex (метафон), n-грамм, поиск по дереву, так как позволяет допускать ошибки в произвольных частях слова и при этом качество поиска не ухудшиться. Это имеет существенное значение при переводе русских имен на латиницу. Более того, такой метод ускорения поиска подходит для любого языка. Примером такой функции может быть . Такая функция была предложена в статье [5]. Данная функция хорошо подходит при считывании словаря с дискового пространства, но так как в нашем случае весь словарь будет загружен в оперативную память, то наиболее подходящим вариантом будет следующая формула: , u(i) — элемент словаря, k=length(u(i)). Мы просуммируем все уникальные значения кодов символов строки и получим некий образ. Таким образом, мы построим сюръективное отображение множества элементов словаря в некий набор образов и получили вектор столбец , где n — размер словаря

Описание используемого алгоритма исравнение результатов.

Поисковый алгоритм будет реализован следующим образом:
1. словарь сортируется по возрастанию значений h(i) — значений хэшей
2. û(1): , где y — образ входного запроса
3. k=koeff(u(i),a), — вычисляем коэффициенты схожести; если нашли элементы с k=1.0, то поиск завершаем.
4. û (2)= , t=max(bytes(char)) — максимальное значение кода символа
и так далее. Расширять выборку подмножества мы будем ограниченное число раз, равное максимально допустимому числу ошибок вставки или удаления. Переменная t на каждом шаге увеличивается, т. е. вначале мы ищем на точное совпадение образов (t=0*t), далее t=t*1 и ищем элемент в этом множестве (без элементов предыдущего) и так далее, расширяя максимально допустимое число раз.

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

Рис. 1 Сравнение временных затрат для обычного поиска и поиска с хэшированием

Мы видим, что с увеличением размера словаря, выигрыш становится существенен. Более того, в данном примере рассматривался случай, когда словарь не содержит искомый запрос и допустимо 3 ошибки. В реальной ситуации поиск, с предложенным алгоритмом, будет занимать значительно меньше времени.

Теперь сравним алгоритмы поиска с использованием функции хэширования из статьи Бойцова Л. М. [5] и используемой в работе (при сравнении рассматриваем ситуацию, что элемент в словаре отсутствует и допустимо 3 ошибки, входной набор состоит из 20 запросов).

Рис. 2 Сравнение временных затрат поиска с использованием функции Бойцова и предложенной в статье

Исходя из графика, видим, что наш метод показал лучшие результаты. Более того, алгоритм был внедрен в локальную базу данных и успешно используется. Он обеспечивает быстрый и качественный поиск.

Читайте также: