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

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

Антонов Алексей Евгеньевич

СПОСОБЫ И ПРОГРАММНЫЕ СРЕДСТВА СРАВНЕНИЯ ИСПОЛНЯЕМЫХ ФАЙЛОВ ДЛЯ ИХ ОПЕРАТИВНОЙ КЛАССИФИКАЦИИ

Специальность 05.13.11 — Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

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

5 ДЕК 2013

Москва-2013

005542875

Работа выполнена на кафедре вычислительной техники в филиале федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Национальный исследовательский институт «МЭИ» в г. Смоленске.

Научный руководитель: Федулов Александр Сергеевич

доктор технических наук, профессор

Официальные оппоненты: Кутепов Виталий Павлович

доктор технических наук, профессор, профессор кафедры «Прикладная математика» ФГБОУ ВПО «Национальный исследовательский университет «МЭИ»

Морозов Андрей Владимирович

доктор технических наук, профессор, заместитель начальника кафедры «Автоматизированные системы боевого управления» ФГКВОУ ВПО «Военная академия войсковой ПВО ВС РФ имени Маршала Советского Союза А. М. Василевского» Министерства обороны РФ»

Ведущая организация: ФГАОУ ВПО «Северный (Арктический)

федеральный университет имени М. В. Ломоносова».

Защита состоится 20 декабря 2013 г. в 16:00 в ауд. М-704 на заседании диссертационного совета Д212.157.01 при ФГОУ ВПО «НИУ «МЭИ» по адресу: 111250, Москва, Красноказарменная ул., д. 13.

С диссертацией можно ознакомиться в библиотеке ФГОУ ВПО «Национальный исследовательский университет «МЭИ».

Автореферат разослан «_/£_» ноября 2013 года.

Ученый секретарь

диссертационного совета Д 212.157.01

к.т.н., доцент

Фомина Марина Владимировна

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность темы

Решение рада задач информатики требует анализа компьютерных

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

Реализация этих задач основана на процедуре сравнения программ (или их частей) по выделенным признакам, параметрам, свойствам, определении степени сходства программ с использованием заданной меры;

Способы сравнения программ и программные средства, реализующие эта способы, исследованы в работах ряда авторов: В. А. Захарова, С. С. Гайсаряна, А. В. Чернова, В. П. Иванникова, Е. Кирда, У. Байера, А. Валенштейна, X. Тамады, Я. Ксианга.

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

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

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

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

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

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

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

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

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

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

Цели и задачи работы

Целью диссертационной работы является улучшение качества сравнения

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

Для достижения поставленной цели в работе решены следующие основные задачи:

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

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

• разработан новый способ комбинирования результатов сравнения исполняемых файлов по нескольким признакам, повышающий качество сравнения;

• проведен анализ существующих показателей и подходов для оценки качества способов сравнения;

• исследованы признаки, позволяющие экспертно сравнивать некоторые типы исполняемых файлов и оценивать степень их сходства;

• разработан новый способ оценки качества сравнения, основанный на экспертной оценке степени сходства исполняемых файлов;

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

Методы исследования

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

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

Обоснованность научных результатов

Обоснованность теоретических разработок диссертации определяется

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

Достоверность основных результатов

Достоверность основных результатов диссертации подтверждается:

использованием достоверных исходных данных, результатами экспериментальных исследований, практическим применением разработанных способов и программных средств сравнения исполняемых файлов в ЗАО «Лаборатория Касперского», ООО «Софт-сервис», филиале ФГБОУ ВПО «Национальный исследовательский университет «МЭИ» в г. Смоленске.

Объект исследования

Объектом исследования в работе являются исполняемые файлы программ.

Предмет исследования

Предмет исследования — свойства и признаки исполняемых файлов,

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

Научная новизна

• Разработан новый способ сравнения исполняемых файлов, основанный на

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

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

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

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

Практическая значимость

• Предложенные способы сравнения исполняемых файлов и способ оценки

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

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

Положения, выносимые на защиту

• Способ сравнения файлов, основанный на анализе извлекаемых из них строк.

• Способ сравнения исполняемых файлов на основе анализа их структуры с ее представлением в виде блоков данных переменной длины.

• Способ комбинирования результатов сравнения исполняемых файлов, полученных по различным признакам файлов.

• Способ оценки качества сравнения файлов.

Внедрение результатов работы

Разработанные способы сравнения исполняемых файлов внедрены в

производственный процесс на ЗАО «Лаборатория Каотерского» и применяются для кластеризации и классификации новых вредоносных объектов в отделе «Исследования и разработки».

Разработанная программная система используется в отделе системного проектирования и обеспечения качества ООО «Софт-Сервис» для выявления дублирующихся программных модулей.

Результаты диссертационной работы используются в учебном процессе на кафедре вычислительной техники филиала ФБГОУ ВПО «Национальный исследовательский университет «МЭИ» в г. Смоленске.

Получено свидетельство о государственной регистрации программы для ЭВМ №2013612928 от 18.03.2013.

Апробация работы

Основные результаты работы докладывались и обсуждались на следующих

конференциях и семинарах:

• 6-ая межрегиональная научно-техническая конференция студентов и аспирантов «Информационные технологии, энергетика и экономика», Смоленск, 2009.

• 3-я международная студенческая конференция по проблемам компьютерной безопасности, Москва 2010.

• 7-ая межрегиональная научно-техническая конференция студентов и аспирантов «Информационные технологии, энергетика и экономика», Смоленск, 2010.

• 8-ая межрегиональная научно-техническая конференция студентов и аспирантов «Информационные технологии, энергетика и экономика», Смоленск, 2011.

• 2-ая международная научно-практическая конференция «Информатика, математическое моделирование, экономика», Смоленск, 2012.

• 9-ая межрегиональная научно-техническая конференция студентов и аспирантов «Информационные технологии, энергетика и экономика», Смоленск, 2012.

Публикации

Основные результаты диссертации опубликованы в 10 печатных работах, из них 3 статьи опубликованы в журналах, рекомендованных ВАК РФ для публикации основных результатов диссертаций.

Структура и объём работы

Работа состоит из введения, четырех глав, заключения, списка литературы

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

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

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

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

Для сравнения исполняемых файлов используется понятие степени сходства 5. Обычно в качестве степени сходства используется некоторая функция расстояния, принимающая значения в диапазоне действительных чисел [0, 1]. Чем более схожими являются файлы, тем меньше значение расстояния (степени сходства).

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

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

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

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

выявления функций и истории их вычисления.

Второй подход включает в себя анализ содержания исполняемых файлов. Файлы сравниваются посредством анализа некоторых признаков, извлекаемых из них. Например, можно анализировать набор строк - последовательность печатных символов в некоторой кодировке. Строки выделяются из исполняемого файла с помощью соответствующих утилит. Строками, представленными в файле, в том числе, являются и интерфейсные функции операционной системы (Application Program Interface —API).

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

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

• при сравнении файлов не учитывается информативность строк;

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

Устранение указанных недостатков позволит улучшить качество сравнения и оперативной классификации.

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

• согласование шкал, в которых представлены результаты работы различных способов;

• учет степени достоверности результатов работы различных способов.

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

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

Рассмотрим бикубическую меру качества кластеризации. Расчет бикубической меры основывается на величинах точности Р и полноты Е кластера для каждого объекта /) из множества всех кластеризуемых объектов Р = {/ь /¿, ..., /к}. Иллюстрация расчета точности и полноты представлена на рисунке 1.

Рисунок 1 — Расчет точности Р, и полноты К, бикубической меры объекта /¿.

На рисунке 1 сплошной линией обведен кластер объектов, полученный с помощью какой-либо процедуры кластеризации. Однотипные объекты представлены одинаковыми геометрическими фигурами. Для объекта /у точность Р,- = 4/5 говорит о наличии в кластере четырех однотипных объектов из пяти. Полнота Л, = 4/6 говорит о том, что в кластер включено четыре однотипных объекта из шести во множестве всех объектов.

Величины точности и полноты комбинируются в Р-меру следующим образом:

Р/ =4/5

Я; =4/6

Оо О ##

' v^i.-vii, т

где коэффициент у определяет, насколько важна точность в сравнении с полнотой.

Бикубическая мера Q рассчитывается как среднее значение F-меры для всех объектов:

Z ф,

v I F\

где |F| - мощность множества объектов F.

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

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

Способ основан на новом алгоритме выбора значимых строк. Для работы алгоритма необходимо иметь: словарь W некоторого языка (языков), представляющий собой набор слов Wj, W2, ..., Wk, ..., WK; файл ft из которого извлекаются строки; порог значимости th. Алгоритм выбора значимых строк

1. Выделить из представленного файла ft строки (для этого считать файл посимвольно, и найти последовательности печатных символов в некоторой кодировке).

2. Для всех выделенных на шаге 1 строк повторить пункты 3-6.

3. Найти в строке все вхождения слов из словаря W. Они образуют некоторое множество слов J. В процессе выделения слов из строки, какая-то часть строки (подстрока) может войти более чем в одно слово из множества J. Например, на рисунке 2 подстрока «те» входит в два слова из словаря «пате» и «measure».

КпйГОвдяШЩ!

Рисунок 2—Пересечение слов из словаря в строке

4. Разделить полученное множество J на подмножества Jg(g- 12,..., G) таким образом, чтобы в каждом из подмножеств не было слов, включающих в себя одну и ту же подстроку. Для рисунка 2 получим два подмножества Ji={«name»}, Ji={ «measure» }.

5. Для каждого из полученных подмножеств Jg оценить вероятность совместного случайного появления всех слов подмножества, по формуле полной вероятности Байеса. Чем выше полученная вероятность, тем больше оснований считать, что строка получена случайно и не является текстом, написанном на языке со словарем W.

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

Для вычисления степени сходства Sf^ файлов /; и fj при помощи полученных наборов строк используется индекс Жаккарда.

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

Пусть N — мощность множества API-функций, АР1„ — п-ая API-функция из множества всех рассматриваемых API-функций, п=1, 2, .... N. Имеется разбиение множества F на подмножества А, в которых имеется вызов функции АР1„.

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

Многие АИ-функции обычно применяются совместно (например, функции «открыть файл» и «закрыть файл»). В работе предлагается учитывать частоту совместного появления некоторой АР1-функции с множеством других АР1-функций следующим образом:

,п = 1,2,...,Ч (3)

п+т

где Эер„ — коэффициент, учитывающий частоту совместного появления выбранной функции АР1„ с остальными функциями множества АРЬфункций.

Коэффициент Оер„ лежит в диапазоне действительных чисел [О, N1. Чем меньше значение коэффициента, тем меньше зависимость вызова функции АР/„ от других функций множества АР1-функций.

Объединим коэффициенты информативности и совместного появления АР1-функций в единый весовой коэффициент значимости у„:

Чем больше значение коэффициента у„, тем более значимой является функция АР1„ для сравнения.

Степень сходства пары файлов /¡и /у в работе предложено определять следующим образом:

C^'-i __/гч

1 II • (5)

И=1_

N

l>g(l+max(a,„,a1„)}-v„

n=1

где aifl, djj, — количество вызовов API-функции API„ при выполнении файлов fi и fi в среде эмулятора, соответственно; операция «log» используется для уменьшения влияния API-функций с большим числом вызовов.

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

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

Для сравнения файлов, на основе полученных таким образом блоков, разработан следующий алгоритм вычисления степени сходства по структуре. Для работы алгоритма требуются: порог разницы между значениями энтропии блоков Ест,«, порог разницы в размерах выделенных блоков Гн™. Алгоритм вычисления степени сходства по структуре файла

1. Выполнить процедуру выравнивания похожих блоков для пары файлов ^ и аналогично известной процедуре выравнивания строк для подсчета редакционного расстояния. Блоки считаются похожими, если их статистические описания отличаются незначительно: разница между значениями энтропии блоков меньше порога Е{и отношение размеров блоков лежит в пределах допустимого интервала [Тц„''; Тц„]. Множество пар выровненных похожих блоков обозначим в виде {Ь], ..., Ьц,..., Ьв}.

2. Для каждой пары Ы выровненных блоков вычислим степень их различия ВЛД:

им н|Мг,.,.г,Л)\|в^-а,.,|

™«(ГМ.Г|Д)] ' <®>

где Тц, и Гц — размеры, а ЕСц, и — значение энтропии к-ой пары схожих блоков для файлов /5 и й, соответственно. ВЛ'/1 лежит в диапазоне действительных чисел [0, 1], где большим значениям соответствует большее различие между блоками.

3. Вычислить степень сходства между парой файлов:

■А ,

Ь Шеагк+1 (7)

1,1 тах(Ьс1,Ьс1)

где Шеагк — редакционное расстояние пары блоков Ък до ближайшей из соседних пар фы и Ьы), Оно рассчитывается как количество действий (вставка, замена, удаление), которое нужно совершить, прежде чем произойдет

выравнивание следующей (или предыдущей) пары; bel и Ъс2 — количество блоков в первом и втором файле соответственно.

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

Z fjs^.qj

-- (8)

где — обобщенная степень сходства для пары файлов {, и fi; S"; _

значение степени сходства по признаку m из множества £2 = {String, API,

Struct}; q„ — количество элементов, участвующих в сравнении (например,

блоков, строк, API-функций); Ц>а — согласующая функция, принимающая значения в диапазоне [ОД].

Согласующая функция строится на основе использования экспертного опроса. Для каждой пары файлов эксперт делает заключение: схожи они или различны. Эти экспертные ответы усредняются по группе пар файлов, имеющих близкие значения степени сходства и числа элементов для сравнения. Полученную величину назовем вероятностью сходства файлов. В координатах «степень сходства» - «количество элементов» значения этой вероятности представляют собой некоторую поверхность. Пример такой поверхности для одного способа сравнения представлен на рисунке 3.

вероятность сходстве пары объектов

Рисунок 3 — Экспериментальная зависимость вероятности сходства пары файлов от значения степени сходства между ними и количества элементов сравнения для строк файла.

Согласующая функция аппроксимирует эту поверхность. Пример согласующей функции представлен на рисунке 4.

Рисунок 4 —Аппроксимированная зависимость вероятности сходства файлов от значения степени сходства между ними и количества элементов сравнения для строк файла.

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

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

вероятность сходства пары объектов

Пусть имеется некоторое разбиение множества исполняемых файлов р = {/ь /г, •••. /к} на кластеры. Предположительно в каждом кластере сосредоточены файлы одного вида. Предположим также, что имеется экспертная информация относительно схожести пар файлов. Эта информация может быть частичной, т. е. существовать не для всех пар файлов. Подобная ситуация характерна для разбиения вредоносного ПО на семейства с учетом вердиктов ряда антивирусных сканеров.

Для определения экспертной оценки степени схожести пар файлов введем следующий показатель:

О, если оба файла принадлежат к разным видам ПО

0.5, если файлы одного вида, но их сравнение не проводилось м

V" , иначе,

(9)

м

гДе '.7 =1, 2, ..., К, М — количество экспертов, оценивающих степень сходства этих файлов, V™ имеет значение 1, если, по мнению эксперта, файлы похожи, и О — в противном случае.

Модифицируем показатели точности Р и полноты Д бикубической меры качества сравнения. Для каждого файла /¡-е р будем рассчитывать эти величины следующим образом:

^.г»^; ,1-1,2,...,к, (Ю)

ЧГ^Р-.Б,^ 1,1

£

,1 = 1,2,..., К, (11)

0.5 1,1

где Рт и Ят - модифицированные показатели точности и полноты, Бц — степень сходства пары файлов /¡, £ полученная каким-либо способом сравнения, И — некоторый порог, К — мощность множества Р.

Далее расчет модифицированной Б-меры Фш,> производится по формуле (1), в которой вместо Р и Я. используются Рт и Ят. Для подсчета модифицированной бикубической меры От используется выражение (12), в которой максимизируется среднее значение модифицированной Р-меры по порогу И.

<3т=тах ь

Ъ фт>.ь

__

и

(12)

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

В третьей главе работы представлены результаты разработки и тестирования программных средств для сравнения и оперативной классификации исполняемых файлов. Программные средства состоят из следующих основных компонентов: АР1-монитор, распаковщик, обработчики (препроцессоры) различных признаков файла, программа сравнения файлов, анализатор качества сравнения. Диаграмма компонентов системы представлена на рисунке 5.

9

Набор файлов

ЗАР» монитор шыуофофАР1

Предварительная обработка файлов Журнал

1Р1 Препроцессор

□Распаковщик

у^—Р Препроцессор строк

Распакованный

Ф«йл

Прел

«нный I

\л М

Препроцессор структуры

3 Анализатор качества

Рисунок 5 —Диаграмма компонентов разработанной системы

АН-МОНИТОР — программа способная каким-либо образом перехватывать вызовы АР1-функций исследуемого файла и сохранять журнал вызова этих функций.

Распаковщик- Упакованные файлы крайне тяжело поддаются анализу, поскольку их структура и строки скрыты. Распаковщик представляет файл в незапакованном виде.

Препроцессор АРТ-функтрто формирует отчет, содержащий АР1-функции, количество вызовов и значения единого весового коэффициента значимости (4) для каждой из них.

Препроцессор_строк формирует отчет, содержащий все строки

обрабатываемого исполняемого файла с пометкой, является ли строка значимой.

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

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

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

Тестирование показало работоспособность разработанных программных средств.

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

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

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

Для оценки предложенных способов сравнения был использован разработанный во второй главе показатель качества - модифицированная бикубическая мера (12). Результаты расчета для существующих и разработанных способов сравнения исполняемых файлов приведены в таблице 1:

Таблица 1 - Значение модифицированной бикубической меры качества для различных способов сравнения исполняемых файлов

Способ сравнения Значение модифицированной бикубической меры качества

Существующие способы сравнения

Сравнение по строкам без учета их значимости 0,695

Сравнение по АР1-функциям без их взвешивания 0,813

Сравнение по структуре файла с использованием блоков постоянной длины 0,816

Разработанные способы сравнения

Сравнение с взвешиванием АРЬфункций 0,849

Сравнение по значимым строкам 0,883

Сравнение структуры файлов с использованием блоков переменной длины 0,887

Способ, комбинирующий результаты сравнения по нескольким признакам 0,915

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

ЗАКЛЮЧЕНИЕ

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

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

2. Разработан ряд способов сравнения исполняемых файлов, основанных на:

• выделении значимых строк;

• сравнении структуры файлов, представленной вектором описаний блоков переменной длины.

3. Разработан и реализован способ комбинирования результатов сравнения по различным признакам файлов.

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

5. Предложен способ оценки качества сравнения исполняемых файлов.

6. Реализованы программные средства для сравнения и классификации исполняемых файлов.

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

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Федулов А. С., Антонов А. Е. Алгоритм обнаружения и обхода антиотладочных и антиэмуляционных приемов / А. С. Федулов, А. Е. Антонов // Информационно-управляющие системы. — СПб.: ГУАП, РИЦ, 2011. — С. 50-54.

2. Федулов А. С., Антонов А. Е. Идентификация типа файла на основе структурного анализа / А. С. Федулов, А. Е. Антонов // Прикладная информатика № 2. — М.: Синергия ПРЕСС, 2013. — С. 68-77.

3. Антонов А. Е. Использование вердиктов антивирусных сканеров для кластеризации исполняемых файлов / А. Е. Антонов // Естественные и технические науки. № 2.—М.: «Спутник+», 2013. — С. 294-299.

4. Антонов А. Е. Анализ типологий вредоносных программ / А. Е. Антонов // Информационные технологии, энергетика и экономика. Сб. трудов 6 межрег. науч.-техн. конф. студентов и аспирантов. Т 1. — Смоленск: Универсум, 2009. — С. 6-9.

5. Антонов А. Е. Разработка типологизации вредоносных программ / А. Е. Антонов // Информационные технологии, энергетика и экономика. Сб. трудов 6 межрег. науч.-техн. конф. студентов и аспирантов. Т 1. — Смоленск: Универсум, 2009. — С. 9-13.

6. Антонов А. Е. Методы деобфускации на основании анализа частоты появления полезных и мусорных команд / А. Е. Антонов // Информационные технологии, энергетика и экономика. Сб. трудов 7 межрег. науч.-техн. конф. студентов и аспирантов. Т1. — Смоленск: Универсум, 2010. — С. 8-13.

7. Антонов А. Е. Сравнение исполняемых файлов по строкам / А. Е. Антонов // Информационные технологии, энергетика и экономика. Сб. трудов 8 межрег. науч.-техн. конф. студентов и аспирантов. Т 1. — Смоленск: Универсум, 2011,—С. 6-11.

8. Антонов А. Е. Оценка качества кластеризации вредоносного программного обеспечения / А. Е. Антонов // Информационные технологии,

энергетика и экономика. Сб. трудов 8 межрег. науч.-техн. конф. студентов и аспирантов. Т1. — Смоленск: Универсум, 2011. — С. 3-6.

Э.Антонов А.Е. Функциональное сравнение исполняемых файлов / А. Е. Антонов // Информационные технологии, энергетика и экономика. Сб. трудов 9 межрег. науч.-техн. конф. студентов и аспирантов. Т 1. — Смоленск: Универсум, 2012. — С. 3-7.

10. Федулов А. С., Антонов А. Е. Сравнение файлов по бинарной структуре / А. С. Федулов, А. Е. Антонов // Информатика, математическое моделирование, экономика. Том 2: сб. статей, 2 междунар. науч.-практ. конф. — Смоленск: Смоленский филиал АНО ВПО ЦС РФ «Российский университет кооперации», 2012. —С. 185-195.

Подписано в печать 12.11.2013 г. Формат 60x84'/,,. Тираж 100 экз: Печ. л. 1,5

Отпечатано в издательском секторе филиала МЭИ в г. Смоленске 214013 г. Смоленск, Энергетический проезд, 1

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Филиал федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Национальный исследовательский институт «МЭИ» в г. Смоленске

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

04201451618

Антонов Алексей Евгеньевич

СПОСОБЫ И ПРОГРАММНЫЕ СРЕДСТВА СРАВНЕНИЯ ИСПОЛНЯЕМЫХ ФАЙЛОВ ДЛЯ ИХ ОПЕРАТИВНОЙ КЛАССИФИКАЦИИ

05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

ДИССЕРТАЦИЯ

на соискание учёной степени кандидата технических наук

Научный руководитель: доктор технических наук, профессор Федулов А. С.

Москва - 2013

ОГЛАВЛЕНИЕ

ОГЛАВЛЕНИЕ.............................................................................................................2

ВВЕДЕНИЕ..................................................................................................................7

Актуальность темы..................................................................................................7

Цели и задачи работы..............................................................................................9

Методы исследования...........................................................................................10

Обоснованность научных результатов................................................................10

Достоверность основных результатов.................................................................10

Объект исследования............................................................................................10

Предмет исследования.........................................................................................10

Научная новизна....................................................................................................11

Практическая значимость.....................................................................................11

Положения, выносимые на защиту......................................................................12

Внедрение результатов работы.............................................................................12

Апробация работы................................................................................................12

Публикации............................................................................................................13

Структура и объём работы...................................................................................13

Краткое содержание работы................................................................................14

1 ОБЗОР СПОСОБОВ СРАВНЕНИЯ ИСПОЛНЯЕМЫХ

ФАЙЛОВ И ОЦЕНКИ ИХ КАЧЕСТВА...................................................................16

1.1 Сравнение программ и исполняемых файлов...............................................16

1.1.1 Сравнение строк файла............................................................................19

1.1.1.1 Получение и анализ строк................................................................20

1.1.1.2 Сравнение файлов по их АР1-функциям.........................................22

1.1.1.3 Использование п-грамм и последовательности АРЬфункций......24

1.1.1.4 Использование неупорядоченных высокоуровневых событий.....25

1.1.1.5 Использование упорядоченных высокоуровневых событий.........28

1.1.1.6 Сложности при сравнении файлов по АР1-функциям...................29

1.1.2 Сравнение структуры файла....................................................................30

1.1.2.1 Контекстно-зависимая кусочная хеш функция...............................31

1.1.2.2 Сравнение статистических профилей.............................................33

1.1.2.3 Анализ недостатков существующих способов сравнения файлов по их структуре.............................................................................................35

1.1.3 Другие способы сравнения исполняемых файлов.................................36

1.1.3.1 Анализ влияния выполнения файла на операционную систему...36

1.1.3.2 Сравнение статистических свойств кода.........................................38

1.1.3.3 Сравнение сетевого трафика............................................................39

1.2 Комбинация нескольких способов сравнения файлов.................................41

1.2.1 Голосование...............................................................................................41

1.2.2 Взвешенная комбинация..........................................................................41

1.2.3 Комбинирование при помощи методов машинного обучения.............42

1.2.4 Анализ недостатков существующих методов комбинирования результатов сравнения нескольких способов..................................................42

1.3 Показатели качества сравнения......................................................................43

1.3.1 Понятие показателя качества сравнения файлов...................................43

1.3.2 Оценка качества сравнения

с использованием эталонного разбиения на классы......................................44

1.3.2.1 Индекс Ранда......................................................................................44

1.3.2.2 Бикубическая мера............................................................................45

1.3.3 Оценка качества сравнения без использования разбиения на классы.46 1.3.3.1 Графовый подход к оценке качества способов сравнения.............47

1.3.4 Недостатки существующих показателей качества сравнения..............49

1.4 Выводы по главе..............................................................................................49

2 РАЗРАБОТКА СПОСОБОВ СРАВНЕНИЯ

ИСПОЛНЯЕМЫХ ФАЙЛОВ И ИХ КОМБИНАЦИИ...........................................51

2.1 Сравнение файлов с использованием строк..................................................51

2.1.1 Исключение частых не информативных строк......................................52

2.1.2 Типизация строк.......................................................................................53

2.1.3 Алгоритм выделения значимых строк....................................................53

2.1.4 Расчет степени сходства...........................................................................56

2.2 Сравнение исполняемых файлов по API-функциям.....................................56

2.2.1 Выявление используемых функций........................................................57

2.2.2 Сравнение файлов по API функциям

с учетом их информативности..........................................................................58

2.3 Сравнение структуры файлов.........................................................................61

2.3.1 Разработка алгоритма разбиения файла.................................................61

2.3.2 Разработка способа сравнения файла.....................................................63

2.4 Способ комбинации результатов сравнения по нескольким признакам... .67

2.4.1 Области компетенции различных способов сравнения файлов...........67

2.4.2 Разработка способа комбинирования нескольких степеней сходства. 69

2.4.3 Параметрическая настройка комбинации алгоритмов..........................71

2.5 Оценка способов сравнения файлов..............................................................72

2.5.1 Оценка качества с использованием многосортного множества...........72

2.5.2 Меры качества для сравнения файлов....................................................74

2.6 Выводы по главе..............................................................................................75

3 РЕАЛИЗАЦИЯ СИСТЕМЫ СРАВНЕНИЯ

И КЛАССИФИКАЦИИ ИСПОЛНЯЕМЫХ ФАЙЛОВ..........................................77

3.1 Выбор среды разработки.................................................................................77

3.2 Реализация системы........................................................................................77

3.2.1 API монитор..............................................................................................78

3.2.2 Распаковщик..............................................................................................79

3.2.3 Препроцессор API функций.....................................................................79

3.2.4 Препроцессор строк.................................................................................82

3.2.5 Препроцессор структуры файлов............................................................85

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

3.2.7 Анализатор качества.................................................................................90

3.3 Тестирование разработанных приложений...................................................91

ч 3.3.1 Объект испытаний....................................................................................91

ч 3.3.2 Цель испытаний.......................................................................................91

3.3.3 Требования к программе..........................................................................91

3.3.4 Средства испытаний.................................................................................92

3.3.5 Методы испытаний...................................................................................92

3.3.6 Состав и порядок испытаний..................................................................93

3.3.6.1 Тестирование программы АР1 препроцессор.................................93

^ 3.3.6.2 Тестирование программы препроцессор строк..............................96

3.3.6.3 Тестирование программы препроцессор структуры......................98

3.3.6.4 Тестирование программы, сравнивающей исполняемые файлы 100

3.3.7 Выводы по тестированию......................................................................102

3.4 Внедрение разработанной программной системы....................................102

3.5 Выводы по главе............................................................................................102

4 ЭКСПЕРИМЕНТАЛЬНАЯ ПРОВЕРКА РАЗРАБОТАННЫХ

СПОСОБОВ СРАВНЕНИЯ ИСПОЛНЯЕМЫХ ФАЙЛОВ..................................104

4.1 Выбор файлов для экспериментального анализа.......................................104

4.2 Анализ информативности и согласованности

вердиктов антивирусных сканеров....................................................................104

4.2.1 Обоснованность использования антивирусных

ч вердиктов для кластеризации вредоносных программ................................105

4.2.2 Оценка независимости антивирусных вердиктов...............................107

4.2.3 Оценка информативности антивирусных вердиктов..........................108

ч

4.2.4 Исключение не информативных вердиктов.........................................113

4.3 Настройка разработанных способов............................................................115

4.4 Экспериментальная оценка разработанных способов...............................115

4.4.1 Построение выборки файлов.................................................................115

4.4.2 Оцениваемые способы сравнения файлов...........................................116

4.4.3 Оценка качества сравнения....................................................................117

4.5 Экспериментальная оценка классификатора исполняемых файлов, основанного на комбинированном показателе степени сходства...................122

4.5.1 Методика проведения эксперимента....................................................122

4.5.2 Построение выборки файлов.................................................................124

4.5.3 Оценка качества детектирования вредоносного

программного обеспечения............................................................................125

4.5.4 Результаты эксперимента.......................................................................125

4.6 Выводы по главе............................................................................................127

ЗАКЛЮЧЕНИЕ........................................................................................................128

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ...............................................129

Приложение А..........................................................................................................140

Приложение Б..........................................................................................................143

ВВЕДЕНИЕ

Актуальность темы

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

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

Способы сравнения программ и программные средства, реализующие эти способы, исследованы в работах ряда авторов: В.А.Захарова [1, 2, 3, 4, 5], С. С. Гайсаряна [6, 7], А.В.Чернова [8, 9, 10, 11], В. П. Иванникова [6], Е. Кирда [12, 13, 14, 15, 16], У.Байера [17, 12], А. Валенштейна [18, 19, 20], X. Тамады [21, 22], Я. Ксианга [23].

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

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

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

Одной из важнейших предметных областей применения процедуры

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

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

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

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

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

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

Цели и задачи работы

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

Для достижения поставленной цели в работе решены следующие основные задачи:

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

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

• разработан новый способ комбинирования результатов сравнения исполняемых файлов по нескольким признакам, повышающий качество сравнения;

• проведен анализ существующих показателей и подходов для оценки качества способов сравнения;

• исследованы признаки, позволяющие экспертно сравнивать некоторые типы исполняемых файлов и оценивать степень их сходства;

• разработан новый способ оценки качества сравнения, основанный на экспертной оценке степени сходства исполняемых файлов;

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

Методы исследования

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

Обоснованность научных результатов

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

Достоверность основных результатов

Достоверность основных результатов диссертации подтверждается: использованием достоверных исходных данных, результатами экспериментальных исследований, практическим применением разработанных способов и программных средств сравнения исполняемых файлов в ЗАО «Лаборатория Касперского», ООО «Софт-сервис», филиале ФГБОУ ВПО «Национальный исследовательский университет «МЭИ» в г. Смоленске.

Объект исследования

Объектом исследования в работе являются исполняемые файлы программ.

Предмет исследования

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

Научная новизна

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

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

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

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

Практическая значимость

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

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

Положения, выносимые на защиту

• С�