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

Автор работы - Егорин А.П.

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

При разработке перспективных методов обнаружения полиморфных и метаморфных вирусов целесообразно воспользоваться следующим фактом: как бы ни изменялась структура программы-вируса в результате обфускации, ее функциональность остается неизменной. Функциональные характеристики вируса являются его подлинной «подписью», неизменно сохраняющейся при репликации. Таким образом, задача обнаружения вируса может быть представлена как задача поиска фрагмента кода S′, функционально эквивалентного заданному (эталонному шаблону) фрагменту S. Этот подход к разработке антивирусных программ уже был осуществлен. Показано, что существуют быстрые алгоритмы поиска функционально эквивалентных фрагментов кода, способные противостоять некоторым обфускирующим преобразованиям (изменение адресов, вставка несущественных команд, изменение графа потока управления). В то же время было отмечено, что для противодействия более сложной обфускации требуется разработка эффективных алгоритмов проверки эквивалентности программ.

Как известно, задача проверки эквивалентности программ в общем случае является алгоритмически неразрешимой. Однако, если принять во внимание некоторые характерные особенности преобразующихся вирусов, то эту задачу можно переформулировать в такой постановке, которая допускает возможность построения алгоритмов проверки эквивалентности программ. Прежде всего, необходимо иметь в виду, что компьютерный вирус должен иметь весьма компактный программный код. Именно из-за ограниченности размера кода вирус в процессе репликации не может применять сложные алгоритмы преобразования, предполагающие использование разнообразных алгебраических тождеств, а также специальных комбинаторных  или криптографических методов. Более простые приемы обфускации программ используют лишь узкий класс алгебраических свойств операционной семантики программ. Эти свойства можно моделировать в рамках теории алгебраических моделей программ[1,2]. В таком случае в зависимости от используемых алгебраических свойств семантики программ можно выбрать подходящую алгебраическую модель программ, полностью описывающую эти свойства, и рассматривать проблему эквивалентности программ в такой модели. Проведенные математические исследования[3,4] свидетельствуют о том, что во многих алгебраических моделях программ проблема эквивалентности разрешима и разрешающие алгоритмы при этом оказываются весьма эффективными. Аналогичный подход применялся в работах, в которых для обфускации и деобфускации программ используется аппарат абстрактных интерпретаций.

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

Література

[1] Подловченко Р.И. Иерархия моделей программ // Программирование,1981, с. 3-14.

[2] Подловченко Р.И. Полугрупповые модели программ // Программирование, с. 3-13.

[3] Подловченко Р.И.. Об одном массовом решении проблемы

эквивалентных преобразований схем программ // Программирование, 2000,

N 1, с. 66-77; 2000, N 2, с. 3-11.

[4] Подловченко Р.И., Захаров В.А., Захарьящев И.М., Русаков Д.М.,

Щербина В.С. О возможности применения быстрых алгоритмов

проверки эквивалентности программ для обнаружения вирусов // Труды

второй Всероссийской научной конференции «Методы и средства

обработки информации», 2005, с.414-421.