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


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

Авторы

Захаров В.А., Захарьящев И.М., Подловченко Р.И., Русаков Д.М., Щербина В.Л.

Аннотация

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

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

Издание

Труды второй всероссийской конференции «Методы и средства обработки информации», 2005, Изд-во ф-та ВМК МГУ Москва, с. 414-421.

Научная группа

Теоретическая информатика

Все публикации за 2005 год Все публикации