Обнаружение компьютерных вирусов

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

Теорема 2.12. Для всех геделевских нумераций частичных рекурсивных функций : - полное множество

Теорема приводится без доказательства.

Здесь - класс множеств в арифметической классификации. Известно, что классы множеств с индексом 1 и выше являются неразрешимыми. Следовательно и множество вирусов является неразрешимым.

Заключение

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

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