Принятые обозначения

Результат Леонарда Адельмана

Леонард Адельман, известный математик, обладатель премии Тьюринга, участвовавший в свое время разработке криптосистемы RSA (буква A в аббревиатуре) для исследования феномена вирусов решил использовать другой формализм теории алгоритмов - не формализм машин Тьюринга, а формализм рекурсивных функций.

Теория машин Тьюринга и теория рекурсивных функций в некотором смысле эквиваленты - алгоритмы, вычислимые в одной теории будут вычислимыми в другой, и наоборот. Этот факт в совокупности с тезисом Тьюринга-Черча, означает, что полученные Л. Адельманом результаты в той же степени применимы к современным реалиям, что и результаты Ф. Коэна, Д. Чесса, С. Вайта, Ф. Лейтольда и других исследователей опиравшихся в своих работах на теорию машин Тьюринга.

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

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

Ниже везде неявно подразумевается описанная интерпретация вычислительной системы.

1. Обозначим S - множество всех конечных последовательностей натуральных чисел, . Таким образом элемент S может обозначать либо набор файлов данных, либо набор файлов программ, закодированных при помощи натуральных чисел.
2. Обозначим e - вычислимую инъективную функцию из SxS на с вычислимой обратной функцией, . По тому же принципу, что и программы и данные, натуральными числами могут кодироваться и состояния системы. Функция e взаимно однозначно ставит в соответствие набору данных и программ натуральное число. Иными словами e - однозначная нумерация состояний системы.
3. 

Нотация предназначена для обозначения состояния системы и фактически является кодом этого состояния, представленным натуральным числом.

1. Для всех частичных функций Любая программа переводит систему из одного состояния в другое, учитывая, что состояния кодируются натуральными числами, можно считать любую программу функцией из в .
2. Для всех частичных функций примем обозначение f(n) определена
3. Для всех частичных функций примем обозначение f(n) не определена

Определение 2.26. Для всех частичных функций выполняется одно из условий:

1. и , либо
2. и и f(s,t) = g(s,t)

Определение служит для уточнения понятия тождественности программ, представленных в виде частичных функций.

Определение 2.27. для всех частичных функций::

1. z=z', и
2. p=p', и
3. , и
4. либо
• q=q', либо
• и h(q_i)=q'_i

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

Определение 2.28. Для всех частичных функций , , и

В этом определении уточняется введенное ранее отношение для состояний, получаемых в результате действия двух функций. Результатом действия функции f на состояние системы является натуральное число, которое можно однозначно интерпретировать как новое состояние . Точно так же . Соответственно, запись обозначает, что обе программы завершают свою работу при запуске из состояния и результат их выполнения будет отличаться фактом заражения некоторых программ: .

Определение 2.29. Для всех частичных функций , или

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

Определение 2.30. Для всех геделевских нумераций частичных рекурсивных функций , общерекурсивная функция v будет вирусом по отношению к выполняется либо:

1. Повреждение:
2. Заражение или имитация:

В данном определении выбор переменных d и p в явном виде указывает на их природу - данные (информация не подверженная заражению) и программы (информация подверженная заражению).

Здесь необходимы комментарии:

• Повреждение. Из определения следует, что результат действия зараженной программы при определенном состоянии системы определяется только типом вируса и состоянием системы, независимо от того, какая программа была заражена. На самом деле, выполняемое вирусом действие может и не быть деструктивным, важно то, что оригинальная программа не выполняется вовсе, т. е. выполняется функция прописанная в самом вирусе.
• Заражение или имитация. Здесь, согласно определению, ситуация прямо противоположная. Результат действия зараженной программы либо вовсе не отличается от результата действия исходной, либо отличается появлением в системе новых зараженных программ. Различное поведение определяется различиями в исходном состоянии системы.

Классификация вирусов

Определение 2.31. Для всех геделевских нумераций частичных рекурсивных функций , для всех вирусов v по отношению к :

• i вредоносна по отношению к v и j
• i = v(j)
• 

Существует состояние системы, при котором зараженная вирусом v программа j выполняет вредоносную функцию, т.е. результат действия зараженной программы не ограничивается заражением (появлением новых зараженных программ).

• i заразна по отношению к v и j
• i = v(j)
• 

Существует состояние системы, при котором зараженная вирусом v программа j выполняет функцию размножения - в результате ее действия в системе появляются новые зараженные программы.

• i безобидна по отношению к v и j
• i = v(j)
• i не вредоносна по отношению к j
• i не заразна по отношению к j
• i является трояном по отношению к v и j
• i = v(j)
• вредоносна по отношению к j
• i не заразна по отношению к j

Троян способен только к выполнению вредоносных функций и не может размножаться.

• i является переносчиком по отношению к v и j
• i = v(j)
• не вредоносна по отношению к j
• i заразна по отношению к j

Переносчик является антиподом трояна: он только размножается и не содержит вредоносных функций.

• i является вирусом по отношению к v и j
• i = v(j)
• i вредоносна по отношению к j
• i заразна по отношению к j

Вирус - наиболее универсальный тип вредоносных программ, способный как к размножению, так и к выполнению вредоносных действий.

В тех случаях когда существует единственная j такая, что (т.е. когда v инъективна) и i является вредоносной (заразной, безобидной, трояном, переносчиком, вирусом) по отношению к v и j, ссылка на j будет опускаться и i будет называться вредоносной (заразной, безобидной, трояном, переносчиком, вирусом) по отношению к v.

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

Определение 2.32. Для всех геделевских нумераций частичных рекурсивных функций , для всех вирусов v по отношению к :

• вирус v безобиден одновременно справедливо:
• 
• 
• вирус v - троянский конь одновременно справедливо:
• 
• 
• вирус v только распространяется одновременно справедливо:
• 
• 
• вирус v вредоносен одновременно справедливо:
• 
• 

Следующая теорема отмечает ряд простых свойств, присущих различным типам вирусов.

Теорема 2.11. Для всех геделевских нумераций частичных рекурсивных функций , для всех вирусов v по отношению к :

1. [v(j) безобидна по отношению к v и j]
2. вирус v безобиден [v(j) безобидна по отношению к v и j]
3. если v - троян, то [v(j) безобидна по отношению к v и j] или [v(j) является трояном по отношению к v и j]
4. если v способен только распространяться, то [v(j) безобидна по отношению к v и j] или [v(j) является переносчиком по отношению к v и j]

Доказательство. Первое свойство непосредственно следует из первой теоремы о рекурсии (теоремы о неподвижной точке).

Остальные свойства следует непосредственно из определений.

Дата добавления: 2014-11-20