2015-06-10
431
Введение
Когда говорят о компьютерных вирусах, всегда подразумевают некий класс программ, обладающих определенными свойствами. Кроме того, для каждого нового вируса существует некая процедура согласно которой антивирусные эксперты решают - вирус это или нет, прежде чем вносить его сигнатуру в вирусную базу.
В связи с этим возникает вопрос о возможности формализовать эту процедуру выяснения относится ли программа к классу вирусов. Этой проблемой занимались многие исследователи еще с первой половины 80-х годов XX века. И самым первым из них был Фред Коэн.
Результат Фреда Коэна
В 1984 г. в своей работе "Computer Viruses - Theory and Experiments" Фред Коэн показал, что задача обнаружения компьютерных вирусов является неразрешимой. При этом он руководствовался следующими рассуждениями.
Отправной точкой был выбор определения вируса:
Определение 2.1. Компьютерным вирусом является программа, способная заражать другие программы изменяя их таким образом, чтобы они включали возможно измененную копию вируса.
|
|
|
Следовательно, чтобы определить, является ли программа P вирусом, необходимо выяснить заражает ли она другие программы. Предположим, существует процедура D, позволяющая по любой программе P сказать вирус это или нет. Но тогда можно составить программу V, которая будет включать процедуру D и будет заражать другие программы только в том случае, когда D не определит V как вирус и не будет заражать в противном случае.
Соответственно, если процедура D, будучи примененной к программе V, скажет, что это вирус, программа V на самом деле не будет заражать файлы и не будет вирусом согласно определению. И наоборот, если согласно процедуре D программа V не является вирусом, на самом деле она будет заражать другие программы, а значит будет вирусом.
Таким образом, гипотетическая процедура D оказывается противоречивой и, следовательно, не существует.
Результат Д. Чесса и С. Вайта
