Основные положения. В работе "An Undetectable Computer Virus" Дэвид Чесс и Стив Вайт попытались развить идеи Коэна и показать

В работе "An Undetectable Computer Virus" Дэвид Чесс и Стив Вайт попытались развить идеи Коэна и показать, что задача обнаружения вирусов остается неразрешимой и при более слабых допущениях. Этой работой они попытались охватить класс полиморфных вирусов.

Рассмотрим множество программ. Множеством значений каждой из программ является одна или несколько других программ. При каждом выполнении программа производит одну программу из своего множества значений (в зависимости от входных данных). Пусть при этом выполнялась программа p, а результатом ее работы стала программа q. В этом случае будем говорить, что p производит q. Будем также говорить, что p со временем производит q, если p производит q либо непосредственно, либо после конечного числа итераций, когда сперва выполняется программа p, затем ее результат и т. д. Отношение "со временем производит" является транзитивным замыканием отношения "производит".

Определение 2.2. Множество V называется вирусным, если это максимальное множество удовлетворяющее условию:

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

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

Программа p будет называться просто зараженной, если: (V - вирус) [p V].

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

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

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