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

На правах рукописи

Стремоухов Всеволод Дмитриевич

МОДЕЛЬ И МЕТОД ОПРЕДЕЛЕНИЯ АВТОРСТВА ВРЕДОНОСНОГО КОДА

Специальность 05.13.19 Методы и системы зашиты информации, информационная безопасность

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

6 МАЙ 2013

005059793

Санкт-Петербург 2013

005059793

Работа выполнена на кафедре «Безопасные информационные технологии» Санкт-Петербургского национального исследовательского университета информационных технологий, механики и оптики (НИУ ИТМО).

Научный руководитель:

Официальные оппоненты:

Ведущая организация:

д.т.н., профессор Осовецкий Леонид Георгиевич

д.т.н., профессор кафедры ОПДС СПбГУТ им. проф. Бонч-Бруевича М.А.

Комашинский Владимир Ильич

к.т.н., доцент кафедры геоинформационных систем ф-та инфокоммуникационных технологий НИУ ИТМО

Карманов Андрей Геннадиевич ЗАО "Лаборатория Касперского"

Защита состоится 2013 г. в 0 часов /%Укин. на заседании

диссертационного совета Д 212.227.05 при Санкт-Петербургском национальном исследовательском университете информационных технологий, механики и оптики по адресу: 197101, Санкт-Петербург, Кронверкский пр. 49

С диссертацией можно ознакомиться в библиотеке НИУ ИТМО.

Автореферат разослан 2013 г.

Ученый секретарь диссертационного совета / - В.И.Поляков

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

АКТУАЛЬНОСТЬ ТЕМЫ ИССЛЕДОВАНИЯ

В настоящее время эпидемии компьютерных вирусов и других вредоносных программ наносят огромный ущерб различным организациям и отдельным пользователям компьютеров. За последние 15-20 лет распространение вредоносного кода, носившее локальный характер, превратилось в глобальные эпидемии сетевых червей, не требующих для распространения участия пользователей. Работа и функционирование многих структур и организаций тесно связана или полностью зависит от глобальных сетей. Сетевые черви, размножающиеся в неограниченном количестве, забивают каналы передачи информации, тем самым нанося огромные убытки, не говоря уже о том, что код современного червя как правило содержит деструктивную нагрузку, что приводит к потере или утечке важной и конфиденциальной информации.

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

Однако, без сомнения, одним из основных факторов, стимулирующих распространение вредоносного кода (ВК), является трудность поиска автора -в бинарном объекте трудно найти улики в классическом их понимании. В результате, у вирусописателей создаётся ощущение абсолютной безнаказанности. Новые вредоносные программы появляются каждый день, а случаи обнаружения их создателей единичны и связаны только с наиболее известными образцами вредоносного кода. Безнаказанность, возможность прославиться и применить свои навыки программирования привлекают многих в создании и распространении вредоносных программ. Для применения к ним соответствующих мер, предусмотренных законодательством необходимо доказать

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

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

рых заранее известно.

Эти методы, после соответствующей доработки, мож-

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

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

тов, поступающих на

вход вирусной лаборатории, по каждому из которых

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

ЦЕЛИ И ЗАДАЧИ ДИССЕРТАЦИИ

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

Поставленная цель обуславливает необходимость решения следующих

задач:

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

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

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

В соответствие с целями и задачами диссертационной работы определены ее предмет и объект.

ПРЕДМЕТОМ работы является комплекс вопросов, связанных с определением общего авторства бинарных объектов, в частности, вредоносных программ. В качестве ОБЪЕКТА исследования выступают вирусные коллекции, статистические данные о распространении вредоносных программ и их общем авторстве, существующие методы поиска схожих образцов ВК и результаты, полученные с их помощью.

МЕТОДЫ ИССЛЕДОВАНИЯ

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

НАУЧНАЯ НОВИЗНА

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

ПРАКТИЧЕСКАЯ ЦЕННОСТЬ РАБОТЫ

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

НАУЧНЫЕ ПОЛОЖЕНИЯ, ВЫНОСИМЫЕ НА ЗАЩИТУ

1. Бинарный исполняемый объект вредоносного кода может быть представлен однородной цепью Маркова. Дискретные ячейки памяти (байты)

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

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

3. Вероятность общего авторства объектов кода пропорциональна степени сходства образов, сформированных на основе данных объектов.

СТРУКТУРА И ОБЪЕМ ДИССЕРТАЦИИ

Диссертация состоит из четырех глав, изложена на 94 страницах, содержит 12 рисунков и список литературы из 42 наименований. Глава 1 содержит обзор различных работ и существующих методов в области определения общего авторства текстов и бинарных объектов, а также поиска схожих бинарных объектов по коллекции. Глава 2 описывает модель и метод определения авторства вредоносного кода на основе анализа матрицы переходных вероятностей Маркова, а также содержит результаты сравнения этой модели с существующими методами. Глава 3 описывает программную реализацию представленного метода, описаны основные алгоритмы формирования рельефных образов и поиска схожих объектов по коллекции. Глава 4 содержит анализ статистических данных об общем авторстве вредоносных программ, сравнивает эти данные с оценками авторства, полученным с помощью традиционных методов и метода на анализа матрицы переходных вероятностей Маркова.

По теме работы опубликовано 13 работ, в том числе 4 в изданиях рекомендованных ВАК РФ.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

Первая глава диссертации представляет собой обзор существующих методов в области определения общего авторства текстов и бинарных объектов, а также поиска схожих бинарных объектов по коллекции. Использованы наиболее известные работы, посвященные этому направлению, источники указаны в списке литературы. В частности описана модель определения авторства с использованием метода сжатия данных. Рассматривается задача классификации текста Т относительно текстов, S1,..., Sn, характеризующих п авторов. Для этого применяется подход, основанный на применении так называемой относительной энтропии. А именно, определяется характеристика H(T|S), которая характеризует энтропию текста Т по отношению к тексту S. Выбор источника текста Т при наличии текстов S1, ..., Sn, представляющих п источников, осуществляется согласно оценке

q(T)=argminiH(T|Si)

Чаще всего используется способ, называемый «шельфовым» (off-the-shelf) алгоритмом: сжимаем компрессором текст Si и измеряем длину в байтах C(Si) получившегося архива. Затем создаем текст SiT, склеив тексты Si и Т в один файл. Сжимаем SiT и измеряем длину полученного сжатого текста C(SiT) в байтах. Теперь полагаем

Hc(T|Si)= (C(SiT)-C(T)) /|Т|

где |Т| - длина текста Т в байтах. Полученное число Hc(T|Si) можно использовать совместно в оценке q(T) вместо H(T|Si). Таким образом, для определения источника Т мы вычисляем Hc(T|Si), а потом определяем истинный источник Т, выбирая то i, которое соответствует минимальному из чисел Hc(T|Si).

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

Описываются основные недостатки метода, прежде всего, невозможность определения абсолютной вероятности общего авторства образцов -данным методом можно выяснить только относительную вероятность при-

надлежности исследуемого образца тому или иному автору относительно ограниченного множества авторов.

Также описываются другие методы сигнатурного и частотного анализа бинарных исполняемых объектов на предмет авторства.

Далее в главе 1 представлена классификация фрагментов исполняемого объекта, на частотные характеристики которых может оказать влияние "почерк" вирусописателя на примере структуры исполняемых файлов подсистемы Win32 для операционных систем семейства Windows. Определены типы фрагментов, анализ которых для определения авторства не имеет смысла, представлен анализ методов отсечения данных фрагментов при исследовании.

Во второй главе описана новая математическая модель и метод определения авторства вредоносного кода на основе анализа матрицы переходных вероятностей Маркова. В § 1 главы 2 даны исходные предположения, на которых базируется модель. В §2 дана формулировка модели, описаны все ее параметры, дано базовое уравнение модели, позволяющее при заданных параметрах вычислить вероятность общего авторства двух объектов:

Рху = -—-х -, с частным решением

$>,»■ tpu(y) '

l-W-l 1-IJ.I

L, О) = vk,, х In J" , t(x) = arg min,,,.....„_, L, (x)

w Pi.,

Основное уравнение модели определения авторства ВК на основе анализа матрицы переходных вероятностей цепи Маркова. Р(х,у) - вероятность общего авторства двух объектов х и у; m - пространство словаря над байтовым алфавитом; k, 1 - байты, участвующие в переходе; S(d) - оценочный размер фрагмента, бесполезного для исследования, S - общий размер сэмпла.

В §3 главы 2 рассматриваются другие возможные методы анализа матрицы переходных вероятностей Маркова и даётся их сравнительная оценка.

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

• Предложенная модель лишена основного недостатка прочих рассмотренных моделей частотного анализа - а именно, зависимость получаемой вероятности от ограниченной коллекции "вероятных авторов"

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

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

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

Четвертая глава содержит анализ статистических данных об общем авторстве вредоносных программ и их соответствие теоретическим вероятностям общего авторства, полученным с помощью предложенной модели на основе анализа матрицы переходных вероятностей цепи Маркова. Анализ производился на вирусных коллекциях ЗАО «Лаборатория Касперского» и кафедры БИТ. Статистические данные были заранее сформированы методом анализа в ручном и полуавтоматическом режиме вирусными аналитиками кафедры БИТ и ЗАО «Лаборатория Касперского». Коллекции были подобраны так, чтобы была возможность анализа поведения модели при обработке различных типов ВК от широкого круга авторов. Анализ произведён в три этапа.

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

Маркова Сигнатурная Частотная

фактов общего авторства обнаружено при пороговом значении 0.7 3245 2976 1610

- \Zirus.win32 476 367 215

- Тго]ап.и/1п32 1486 1798 897

- 1А/огт.м/1п32 1283 811 498

Количество верно обнаруженных фактов общего авторства 3151 2959 1209

- \Лгиз.\«1п32 446 363 163

- Тго]ап.ш!п32 1464 1791 648

- МГогт.\л/1п32 1241 805 398

Корректность обнаружения при пороговом значении 0.7, % 97,10 99,43 75,09

Пороговое значение со 100% корректностью обнаружения 0,87 0,74 0,98

Фактов общего авторства обнаружено при использовании данного порогового значения 3109 2950 1209

На втором этапе эмулировался "входной поток" и производился анализ скорости детектирования подозрительных объектов. Для этого нескольким аналитикам на рассмотрение поступали образцы вредоносного кода в порядке их реального хронологического поступления на вход "Лаборатории Кас-перского". При этом каждый аналитик располагал только той частью коллекции, объекты которой уже находились в антивирусной базе на момент реального детектирования образца. Хронологические данные предоставлены службой KL mail server, принадлежащей компании ЗАО «Лаборатория Кас-перского».

На третьем этапе аналогичным образом эмулировался "входной поток" и производился анализ коэффициента автоматизации детектирования подозрительных объектов. Для этого были выбраны пороговые значения вероятности общего авторства для исследуемой модели и прочих сравнительных ме-

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

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

V Маркое

м-ь— - 1 ■ ■■- ■ . — —V Сигнатурн

--V Частотн

т-н гЧ гч гч гч ГО СП СП (П -в* чЭ" ^п ьЛ и! Ф Ю Г- Г- Г^ Г*. 0000 СО СП СП СТ>

Рис. 2: зависимость скорости детектирования сэмплов входного потока с использованием рассматриваемых методов относительно объёма сэмпла.

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

Рис. 3: зависимость коэффициента автоматизации процесса детектирования сэмплов входного потока относительно оценки авторства, вырабатываемой различными методами анализа.

Рис. 4: зависимость коэффициента автоматизации процесса детектирования сэмплов входного потока с использованием рассматриваемых методов относительно объёма сэмпла.

В конце главы приведены результаты изучения статистических данных и их сравнения с теоретическими вероятностями, предсказанными математическими моделями:

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

• Метод на основе анализа матрицы переходных вероятностей цепи Маркова позволяет серьёзно увеличить скорость детектирования подозрительных исполняемых объектов.

• Метод на основе анализа матрицы переходных вероятностей цепи Маркова позволяет серьёзно коэффициент автоматизации детектирования подозрительных исполняемых объектов, особенно для больших объектов, требующих трудоёмких операций при ручном анализе.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

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

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

5. Метод на основе анализа матрицы переходных вероятностей цепи Маркова позволяет серьёзно увеличить скорость детектирования подозрительных исполняемых объектов.

6. Метод на основе анализа матрицы переходных вероятностей цепи Маркова позволяет серьёзно коэффициент автоматизации детектирования подозрительных исполняемых объектов, особенно для больших объектов, требующих трудоёмких операций при ручном анализе.

СПИСОК РАБОТ. ОПУБЛИКОВАННЫХ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Стремоухов В.Д.," Анализ вредоносного кода: некоторые примеры ", Сборник трудов 10 Международной Конференции "Теория и Технология Программирования и Защиты Информации", СПбГУИТМО, СПб, 18 мая 2006

2. Стремоухов В.Д., Клеймёнов А. В. "Анализ вредоносного кода: некоторые проблемы", конференция "Технологии Майкрософт в проектировании и разработке программного обеспечения", СПбГПУ, СПб, 14 марта 2007

3. Стремоухов В.Д., Клеймёнов А. В. "Методы детектирования авторства вредоносного кода", 11 Международная Конференция "Теория и Технология Программирования и Защиты Информации", СПбГУИТМО, СПб, 18 мая 2007

4. Стремоухов В.Д., Клеймёнов А. В. "Проблемы распространения вредоносного кода", Сборник трудов Научно-технической конференции "День Антивирусной безопасности", Санкт-Петербург, 22 октября 2007

5. Стремоухов В.Д., "Разработка нейросетевого классификатора для детектирования потенциально-опасного функционала программного обеспечения", Сборник трудов Научно-технической конференции "День Антивирусной безопасности", Санкт-Петербург, 22 октября 2007

6. V. Stremouhov "Detecting malicious functionality: an introduction", 7th Kaspersky Virus Analyst Summit, Kaspersky Lab, Moscow, Jan. 30th, 2008

7. Стремоухов В.Д. "Программные методы детектирования авторства вредоносного кода", конференция "Технологии Майкрософт в проектировании и разработке программного обеспечения", СПбГПУ, СПб, 12 марта 2008

8. Стремоухов В.Д. "Прогнозирование вирусных эпидемий", конференция "Технологии Майкрософт в проектировании и разработке программного обеспечения", СПбГПУ, СПб, 12 марта 2008

9. Стремоухов В.Д., " "Методология обучения анализу вредоносного кода", Сборник трудов 12 Международной Конференции "Теория и Технология Программирования и Защиты Информации", СПбГУИТМО, СПб, 16 мая 2008

Ю.Стремоухов В.Д., Клеймёнов А. В. "Оценка эффективности модели на основе цепей Маркова для поиска сходных объектов вредоносного кода", 5 Всероссийская Конференция Молодых Учёных, СПбГУИТМО, СПб, 17 апреля 2008

11.Стремоухов В.Д. ""Обход систем защиты от исполнения данных в ОС семейства Windows", Сборник трудов 10 международной конференции HTFI, СПб, 10 декабря 2010

12.Стремоухов В.Д. "Методы обхода защиты от исполнения данных", Спи-сок-2011: Материалы межвуз. науч. конф. по проблемам информатики. 2729 апр. 2011г., Санкт-Петербург. - Издательство СПбГУ, СПб.:ВВМ, 2011.- ISBN 978-5-9651-0577-9

13.Стремоухов В.Д. "Определение авторства вредоносного кода с использованием метода сжатия данных", "Программные продукты и системы" №3/2013, Тверь, ЦПС

Санкт-Петербургский Национальный Исследовательский Университет Информационных Технологий, Механики и Оптики

На правах рукописи

0420135^283

Стремоухое Всеволод Дмитриевич

МОДЕЛЬ И МЕТОД ОПРЕДЕЛЕНИЯ АВТОРСТВА

ВРЕДОНОСНОГО КОДА

Специальность 05.13.19 Методы и системы защиты информации, информационная безопасность

Диссертация на соискание ученой степени кандидата наук

Научный руководитель (консультант) Доктор технических наук, профессор Осовецкий Леонид Георгиевич

Санкт-Петербург 2013

Оглавление

Введение.............................................................................................................................3

Глава 1: Постановка задачи и анализ существующих методов решения....................6

1.1 Постановка задачи...................................................................................................6

1.2 Существующие методы решения задачи..............................................................6

1.2.1 Метод на основе энтропийной классификации с помощью сжатия...........6

1.2.2 Частотный анализ...........................................................................................23

Глава 2: Модель...............................................................................................................26

2.1 Исходные положения............................................................................................26

2.2 Формулировка модели..........................................................................................30

Глава 3: Расчетно-вычислительный комплекс.............................................................35

Глава 4: Анализ модели на основе статистических данных.......................................51

4.1 Проверка однородности матриц переходных вероятностей.............................51

4.2 Проверка эффективности представления матрицы переходных вероятностей в виде двумерного образа..............................................................................................54

4.3 Проверка эффективности обнаружения авторства............................................58

4.4 Анализ увеличения скорости детектирования...................................................64

4.5 Анализ увеличения коэффициента автоматизации...........................................75

Список использованной литературы.............................................................................92

Введение

В настоящее время эпидемии компьютерных вирусов и других вредоносных программ наносят огромный ущерб различным организациям и отдельным пользователям компьютеров. За последние 15-20 лет распространение вредоносного кода, носившее локальный характер, превратилось в глобальные эпидемии сетевых червей, не требующих для распространения участия пользователей. Работа и функционирование многих структур и организаций тесно связана или полностью зависит от глобальных сетей. Сетевые черви, размножающиеся в неограниченном количестве, забивают каналы передачи информации, тем самым нанося огромные убытки, не говоря уже о том, что код современного червя как правило содержит деструктивную нагрузку, что приводит к потере или утечке важной и конфиденциальной информации.

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

Однако, без сомнения, одним из основных факторов, стимулирующих распространение вредоносного кода (ВК), является трудность поиска автора - в бинарном объекте трудно найти улики в классическом их понимании. В результате, у вирусописателей создаётся ощущение абсолютной безнаказанности. Новые вредоносные программы появляются каждый день, а случаи обнаружения их создателей единичны и связаны только с наиболее известными образцами вредоносного кода. Безнаказанность, возможность прославиться и применить свои

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

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

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

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

Глава 1: Постановка задачи и анализ существующих методов решения

1.1 Постановка задачи

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

В рассматриваемой работе будем оперировать понятиями частной и конечной задачи.

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

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

Для начала, рассмотрим существующие методы.

1.2 Существующие методы решения задачи

1.2.1 Метод на основе энтропийной классификации с помощью сжатия

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

на применении так называемой относительной энтропии. Именно, мы определяем характеристику Н(Т|8), которая характеризует энтропию текста Т по отношению к тексту Б. Выбор источника текста Т при наличии текстов 81, ..., Бп, представляющих п источников, осуществляется согласно оценке

<K7-) = argmintfi) (1.1)

о

Для оценки энтропии текста используется способ, называемый «шельфовым» (off-the-shelf) алгоритмом: сжимаем компрессором текст Si и измеряем длину в байтах C(Si) получившегося архива. Затем создаем текст SiT, объединив тексты Si и Т в один объект. Сжимаем SiT и измеряем длину полученного сжатого текста C(SiT) в байтах. Теперь полагаем

Г С№Г)-С(Г)

S. \Т\

где (Т| - длина текста Т в байтах. Полученное число Нс(Т|8і) можно использовать совместно в оценке я(Т) в качестве Н(Т|8і). Таким образом, для определения источника Т мы вычисляем Нс(Т|8і), а потом определяем истинный источник Т, выбирая то і, которое соответствует минимальному из чисел Нс(Т|8і).

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

сжимаемого текста. Рассмотрим основные алгоритмы сжатия, пригодные для данной задачи:

Фронтальное сжатие - тип дельта-кодирования (delta encoding), где общие префиксы или суффиксы и их длины записываются таким образом, чтобы избегать дублирования данных. Дельта-кодирование применяется как предварительный этап для многих алгоритмов сжатия, к примеру RLE, и в инвертированных индексах поисковых программ. Природа данных, которые будут закодированы, значительно влияет на эффективность сжатия. Дельта-кодирование повышает коэффициент сжатия в том случае, когда данные имеют маленькую или постоянную вариацию (как, к примеру, градиент на изображении); для данных, сгенерированных генератором случайных чисел с равномерным распределением, коэффициент сжатия изменится не сильно. Пример:

Несжатый поток Сжатый поток

Е2 ЕО 4А 84 0 Е2 ЕО 4А 84

Е2 ЕО 4А FD IF ВА 3 FD IF ВА ЕО 7F

ЕО 7F 84 84

Е2 ЕО 4А FD IF FD 5 FD OD

0D 0 97 84 F8

97 84 F8 3 F8 OA OD

97 84 F8 F8 OA 0D 4 7D 97 FC

97 84 F8 F8 7D 97 3 7D 7F

FC 3 A8

97 84 F8 7D 7F 3 FDF8

97 84 F8 А8 2 FC 84 97 84 7F

97 84 F8 FD F8 3 OA АА AA OA

97 84 FC 84 97 84

7F

97 84 FC OA АА АА

OA

Алгоритм Лемпеля-Зива-Велча. Данный алгоритм при сжатии (кодировании) динамически создаёт таблицу преобразования строк: определённым последовательностям символов (словам) ставятся в соответствие группы бит фиксированной длины (обычно 12-битные). Таблица инициализируется всеми 1-символьными строками (в случае 8-битных символов — это 256 записей). По мере кодирования, алгоритм просматривает текст символ за символом, и сохраняет каждую новую, уникальную 2-символьную строку в таблицу в виде пары код/символ, где код ссылается на соответствующий первый символ. После того как новая 2-символьная строка сохранена в таблице, на выход передаётся код первого символа. Когда на входе читается очередной символ, для него по таблице находится уже встречавшаяся строка максимальной длины, после чего в таблице сохраняется код этой строки со следующим символом на входе; на выход выдаётся код этой строки, а следующий символ используется в качестве начала следующей строки. Пример:

Символ Битовый код Новая запись

Т 20= 10100

О 15= 01111 27: ТО

В 2= 00010 28:0В

Е 5= 00101 29: ВЕ

О 15= 01111 30: ЕО

R 18= 10010 31: OR

N 14 = 001110 32: RN

О 15 = 001111 33: NO

Т 20 = 010100 34: ОТ

ТО 27 = 011011 35: TT

ВЕ 29 = 011101 36: TOB

OR 31 =011111 37: BEO

TOB 36= 100100 38: ORT

ЕО 30 = 011110 39: ТОВЕ

1Ш 32 = 100000 40: ЕОЯ

ОТ 34= 100010 41: КМО

# 0 = 000000 42: ОТ#

Алгоритм Шеннона—Фано - использует коды переменной длины: часто встречающийся символ кодируется кодом меньшей длины, редко встречающийся — кодом большей длины. Коды Шеннона — Фано префиксные, то есть никакое кодовое слово не является префиксом любого другого. Код Шеннона — Фано строится с помощью дерева. Построение этого дерева начинается от корня. Всё множество кодируемых элементов соответствует корню дерева (вершине первого уровня). Оно разбивается на два подмножества с примерно одинаковыми суммарными вероятностями. Эти подмножества соответствуют двум вершинам второго уровня, которые соединяются с корнем. Далее каждое из этих подмножеств разбивается на два подмножества с примерно одинаковыми суммарными вероятностями. Им соответствуют вершины третьего уровня. Если подмножество содержит единственный элемент, то ему соответствует концевая вершина кодового дерева; такое подмножество разбиению не подлежит. Подобным образом поступаем до тех пор, пока не получим все концевые вершины. Ветви кодового дерева размечаем символами 1 и 0.

При построении кода Шеннона — Фано разбиение множества элементов может быть произведено, вообще говоря, несколькими способами. Выбор разбиения на уровне п может ухудшить варианты разбиения на следующем уровне (п + 1) и привести к неоптимальности кода в целом. Другими словами, оптимальное поведение на каждом шаге пути ещё не гарантирует оптимальности всей совокупности действий. Поэтому код Шеннона — Фано не является оптимальным в общем смысле, хотя и дает оптимальные результаты при некоторых распределениях вероятностей. Для одного и того же распределения вероятностей можно построить, вообще говоря, несколько кодов Шеннона — Фано, и все они

могут дать различные результаты. Если построить все возможные коды Шеннона — Фано для данного распределения вероятностей, то среди них будут находиться и все коды Хаффмана (см. ниже), то есть оптимальные коды. Пример:

Исходные символы:

А (частота встречаемости 50)

В (частота встречаемости 39)

С (частота встречаемости 18)

О (частота встречаемости 49)

Е (частота встречаемости 35)

Б (частота встречаемости 24)

Результирующее дерево:

Рис. 1.1: пример дерева для алгоритма Шеннона-Фано

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

Алгоритм Хаффмана на входе получает таблицу частот встречаемости символов в сообщении. Далее на основании этой таблицы строится дерево кодирования Хаффмана (Н-дерево).

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

2. Выбираются два свободных узла дерева с наименьшими весами.

3. Создается их родитель с весом, равным их суммарному весу.

4. Родитель добавляется в список свободных узлов, а два его потомка удаляются из этого списка.

5. Одной дуге, выходящей из родителя, ставится в соответствие бит 1, другой — бит 0.

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

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

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

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

Обновление дерева при считывании очередного символа сообщения состоит из двух операций.

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

Вторая операция — перестановка узлов дерева — требуется тогда, когда увеличение веса узла приводит к нарушению свойства упорядоченности, то есть тогда, когда увеличенный вес узла стал больше, чем вес следующего по порядку узла. Если и дальше пр�