Вычислительная машина с произвольной выборкой

Вычислительные модели

Формализм Ф. Лейтольда

Практические следствия

На практике вирус W не представляет такой уж большой опасности и это связано с тем, что, как правило, не расценивается проблемой ложное срабатывание на программах вида:

если D(t), то завершить работу, иначе размножаться

или

если Sub1(u), то завершить работу, иначе {

заменить текст подпрограммы Sub1 текстом произвольной программы;

размножаться;

завершить работу;

}

Sub1:

вернуть D(аргумент);

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

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

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

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

Для моделирования компьютерной среды Ф. Лейтольд отталкивался от вычислительной машины с произвольной выборкой (Random Access Machine, RAM), определение которой представлено ниже.

Вычислительная машина с произвольной выборкой состоит из следующих компонентов:

• Входная лента, представляющая собой последовательность ячеек, содержащих целые числа и доступных только для последовательного чтения - после чтения ячейки считывающая головка автоматически перемещается вправо
• Выходная лента, представляющая собой последовательность ячеек, доступных только для последовательной записи, по умолчанию эти ячейки пусты
• Программа - последовательность (возможно индексированная, т.е. с возможностью указать адрес некоторых или любых инструкций) инструкций, не находящаяся в памяти и, соответственно, неизменяемая, по умолчанию выполнение программы начинается с первой инструкции (можно ввести счетчик инструкций, указывающий на следующую к выполнению инструкцию, в этом случае по умолчанию счетчик указывает на первую инструкцию)
• Память - неограниченная последовательность регистров r₀, r₁,..., r_i,..., способных хранить целые числа, по умолчанию значения регистров пусты, нулевой регистр r₀ используется для вычислений и часто называется аккумулятором, доступ к регистрам производится непосредственно по их индексам, откуда и происходит название машины.

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

Инструкция	Параметр	Описание
LOAD	Операнд	Загружает в память значение, определяемое операндом
STORE	Операнд	Копирует значение аккумулятора в ячейку памяти (регистр) определяемый операндом
ADD	Операнд	Добавляет к аккумулятору значение, определяемое операндом
SUB	Операнд	Вычитает из аккумулятора значение, определяемое операндом
MULT	Операнд	Умножает аккумулятор на значение, определяемое операндом
DIV	Операнд	Делит аккумулятор на значение, определяемое операндом
READ	Операнд	Считывает значение с входящей ленты в регистр, определяемый операндом
WRITE	Операнд	Записывает на выходную ленту значение, определяемое операндом
JUMP	Метка	Присваивает счетчику инструкций значение метки
JGTZ	Метка	Присваивает счетчику инструкций значение метки, если аккумулятор содержит положительное число
JZERO	Метка	Присваивает счетчику инструкций значение метки, если аккумулятор равен нулю
HALT		Завершает работу машины

Допускается три вида операндов:

• i - обозначает собственно значение целого числа i
• [i] - для неотрицательных i обозначает значение регистра r_i
• [[i]] - косвенная адресация, обозначает значение регистра r_j, где j - значение регистра r_i. Если j<0, машина завершает работу

По умолчанию (см. также определение) значение всех регистров равно нулю, счетчик инструкций указывает на первую инструкцию программы и выходная лента пуста. После выполнения k -й инструкции счетчик либо автоматически увеличивается на единицу и указывает на (k+1) -ю инструкцию, либо, если была выполнена инструкция JUMP или выполнены условия инструкций JGTZ или JZERO, принимает значение метки, либо, если была выполнена инструкция HALT, машина прекращает свою работу.

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