Формализм Ф. Лейтольда
В 2000-м году венгерский исследователь Ференц Лейтольд попытался дать новый импульс развитию математической теории компьютерных вирусов путем более точного моделирования вычислительной среды - компьютеров и операционных систем. Попутно он вывел некую общую классификацию вирусов и также, как Д. Чесс и С. Вайт, рассмотрел в рамках предложенного формализма феномен полиморфных вирусов.
Классификация вирусов
Определение 2.31. Для всех геделевских нумераций частичных рекурсивных функций
i вредоносна по отношению к v и j тттк
i = v(j)
Существует состояние системы, при котором зараженная вирусом v программа j выполняет вредоносную функцию, т.е. результат действия зараженной программы не ограничивается заражением (появлением новых зараженных программ).
i заразна по отношению к v и j тттк i = v(j)
Существует состояние системы, при котором зараженная вирусом v программа j выполняет функцию размножения - в результате ее действия в системе появляются новые зараженные программы.
i безобидна по отношению к v и j тттк i = v(j)i не вредоносна по отношению к ji не заразна по отношению к j
i является трояном по отношению к v и j тттк i = v(j)вредоносна по отношению к ji не заразна по отношению к j
Троян способен только к выполнению вредоносных функций и не может размножаться.
i является переносчиком по отношению к v и j тттк i = v(j)не вредоносна по отношению к ji заразна по отношению к j
Переносчик является антиподом трояна: он только размножается и не содержит вредоносных функций.
i является вирусом по отношению к v и j тттк i = v(j)i вредоносна по отношению к ji заразна по отношению к j
Вирус - наиболее универсальный тип вредоносных программ, способный как к размножению, так и к выполнению вредоносных действий.
В тех случаях когда существует единственная j такая, что (т.е. когда v инъективна) и i является вредоносной (заразной, безобидной, трояном, переносчиком, вирусом) по отношению к v и j, ссылка на j будет опускаться и i будет называться вредоносной (заразной, безобидной, трояном, переносчиком, вирусом) по отношению к v.
Таким образом, если по отношению к какому-либо вирусу инфицированная программа является безобидной, это значит что она выполняет в точности те же действия, что и исходная неинфицированная программа и никаких других. Если она является трояном, значит она не может заражать другие программы, а может только имитировать их действия или наносить вред.
Если программа является переносчиком, значит она не способна наносить вред, но при определенных обстоятельствах может заражать другие программы.
Определение 2.32. Для всех геделевских нумераций частичных рекурсивных функций
вирус v - троянский конь тттк одновременно справедливо: (
вирус v только распространяется тттк одновременно справедливо: (
вирус v вредоносен тттк одновременно справедливо: (
Следующая теорема отмечает ряд простых свойств, присущих различным типам вирусов.
Теорема 2.11. Для всех геделевских нумераций частичных рекурсивных функций
Доказательство. Первое свойство непосредственно следует из первой теоремы о рекурсии (теоремы о неподвижной точке).
Остальные свойства следует непосредственно из определений.
Машина Тьюринга
Большинство теоретических результатов относительно вычислительной способности различных автоматов (к которым относятся RAM и RASPM) получено для Машины Тьюринга. Следовательно, для применения к RASPM уже известных результатов, необходимо установить отношение между этими формальными системами.
Определение 2.5. Машина Тьюринга с одной лентой может быть определена как совокупность семи элементов:
где Q - множество состояний Машины Тьюринга, S - множество символов, которые могут быть записаны на ленте, I - множество символов входящей последовательности, I
Машина начинает свою работу в состоянии q0 и в дальнейшем меняет состояния согласно функциям перехода в зависимости от текущего состояния и значения ячейки ленты. Попутно ячейки ленты перезаписываются новыми значениями согласно тем же функциям перехода.
Машина Тьюринга может содержать и большее количество лент, но вычислительная способность такой машины будет находиться в полиномиальной зависимости от вычислительной способности Машины Тьюринга с одной лентой. Помимо этого имеют место следующая теорема:
Теорема 2.3. Вычислительные способности Машины Тьюринга и RASPM эквивалентны, а их затраты на вычисление полиноминально сравнимы, если стоимость выполнения инструкции является величиной постоянной или находится в логарифмической зависимости от длины операнда
Кроме того доказан фундаментальный результат.
Теорема 2.4. Не существует такой Машины Тьюринга, которая сможет определить остановится ли произвольная Машина Тьюринга на произвольном входе (проблема остановки)
Моделирование операционных систем
Естественным желанием является использовать RASPM с ABS и RASPM с SABS для запуска программ. Компоненты V, U, T и f машины
G= V, U, T, f, q, M были определены ранее. Теперь, задав определенным образом M и q можно получить программу, которая и будет определять характер функционирования машины. Разумно потребовать, чтобы файлы программ и данных хранились на вспомогательном(ых) хранилище(ах), порядок выполнения программ определялся входной лентой, и чтобы выполняемая программа могла модифицировать как данные, так и программы на вспомогательном хранилище. Соответственно необходима программа-оболочка, способная работать с файлами данных и программ и выполнять другие программы.
Определение 2.8. Под операционной системой (ОС) понимается система программ, способная работать с файлами данных и программ и выполнять другие программы.
Операционная система может быть частью начального состояния памяти M или же может быть расположена на вспомогательном хранилище. Во втором случае, начальное состояние памяти должно содержать специальную программу, которая будет загружать операционную систему и запускать ее. Такая служебная программа не будет считаться частью операционной системы.
Определение 2.9. Если операционная система входит в состав начального состояния памяти M машины, то такая операционная система будет называться машинозависимой.
Это означает, что определив машину RASPM с ABS, мы определим также и операционную систему, т. к. M является частью определения машины.
Определение 2.10. Если операционная система расположена на вспомогательном хранилище, такая операционная система будет называться машиннонезависимой.
В таком случае операционную систему можно будет поменять вместе с вспомогательным хранилищем.
На ту же ситуацию можно взглянуть и с обратной стороны.
Определение 2.11. Если начальное состояние памяти M машины RASPM с ABS включает операционную систему, то такая машина будет называться ОС-зависимой машиной.
Т. е. машина может использовать только свою собственную операционную систему, хотя возможно создание программы, которая будет эмулировать какую-нибудь другую операционную систему.
Определение 2.12. Если операционная система машины RASPM с ABS расположена на вспомогательном хранилище, то такая машина будет называться ОС-независимой машиной.
Из определений непосредственно следуют следующие теоремы.
Теорема 2.8. Если O - машинозависимая операционная система машины G, то G - ОС зависимая машина.Теорема 2.9. Если O - машиннонезависимая операционная система машины G, то G - ОС независимая машина.
Для исследования общей задачи модификации одними программами других программ годится операционная система любого типа. Если же поставить задачу исследования также и программ, способных изменять код операционной системы, необходимо использовать модель с машиннонезависимыми операционными системами.
Обнаружение компьютерных вирусов
После определения компьютерного вируса естественным образом возникает вопрос об обнаружении такого рода программ, или о разрешимости множества компьютерных вирусов. Л. Адельман доказал следующую теорему.
Теорема 2.12. Для всех геделевских нумераций частичных рекурсивных функций
Теорема приводится без доказательства.
Здесь
Обнаружение вирусов
Определение 2.3.
Алгоритм A обнаруживает вирус V тттк для любой программы p: A(p) завершает работу и печатает 1 тттк p
Аналогично, алгоритм A обнаруживает множество вирусов S тттк для любой программы p: A(p) завершает работу и печатает 1 тттк p
По сути это то же определение обнаружения, что и использованное Ф. Коэном в его дебютной работе.
Полученный Ф. Коэном результат, о том, что не существует алгоритма A, способного обнаруживать множество всех возможных компьютерных вирусов, можно расширить и вывести, что даже имея один из экземпляров вируса V, нельзя создать алгоритм, способный обнаруживать все экземпляры вируса V.
Доказательство этого факта строится по той же схеме, что и доказательство Ф. Коэна. Рассмотрим такой полиморфный вирус, что для любого реализуемого алгоритма X программа p:
если X(p), то прекратить работу, иначе размножатьсябудет являться экземпляром этого вируса (при условии, конечно, что такая программа вообще способна размножаться)
Очевидно, не существует алгоритма B, который был бы способен обнаруживать все экземпляры такого вируса, поскольку для любого алгоритма B, претендующего на роль детектора, существует программа q:
если B(q), то прекратить работу, иначе размножатьсядля которой алгоритм B будет возвращать неверный результат. Действительно, если B(q) возвращает 1, значит q никогда не размножается и не является экземпляром описанного или любого другого вируса. Если же B(q) возвращает 0, тогда q в действительности размножается и является экземпляром вируса.
Возникает вопрос о существовании подобного полиморфного вируса и ответ на этот вопрос положительный. Рассмотрим следующий вирус W одним из экземпляров которого является r:
если Sub1(r), то завершить работу, иначе { заменить текст подпрограммы Sub1 текстом произвольной программы; размножаться; завершить работу; } Sub1: Вернуть 0;
Для любого алгоритма C, претендующего на обнаружение всех экземпляров вируса W, найдется программа s:
если Sub1(s), то завершить работу, иначе { заменить текст подпрограммы Sub1 текстом произвольной программы; размножаться; завершить работу; } Sub1: Вернуть С(аргумент);
для которой алгоритм С возвращает ошибочный результат. Если С(s) возвращает 1, значит s всегда просто завершает свою работу и не является экземпляром вируса W или любого другого вируса. Если же C(s) возвращает 0, значит s является экземпляром W. Соответственно, не существует алгоритма C, способного безошибочно определять все экземпляры вируса W и только их.
Общая проблема обнаружения вирусов
Согласно тезису Тьюринга-Черча, если бы существовал алгоритм обнаружения вирусов, можно было бы создать Машину Тьюринга, которая бы выполняла этот алгоритм. Покажем, что такой Машины Тьюринга не существует.
Теорема 2.10. Не существует Машины Тьюринга, которая могла бы определять наличие вируса в произвольной программе для машины RASPM с ABS.
Доказательство. Согласно теореме 2.7 вместо Машины Тьюринга можно использовать эквивалентную ей RASPM или RASPM с ABS. Рассмотрим программу P, которая эмулирует работу Машины Тьюринга (произвольной). Программа P печатает на выходе 1, если эмулируемая Машина Тьюринга завершает свою работу.
Построим простой вирус, который сперва запускает программу P на случайном, но фиксированном (для данного вируса) входе B, после чего начинает выполнять собственно вирусную часть. При заражении вирус копирует целиком программу P, последовательность B и вирусную часть.
Используя эту конструкцию можно создать программу V в RASPM с ABS для любой Машины Тьюринга, и эта программа будет вирусом в том случае, если она сможет размножаться, т. е. в том случае, когда Машина Тьюринга завершает свою работу на фиксированном для программы V входе или, что тоже самое, если программа P печатает единицу для данной Машины Тьюринга и данного входа.
Предположим, что существует Машина Тьюринга, способная обнаруживать все вирусы, т. е. такая Машина Тьюринга T, которая читает код программы RASPM с ABS и печатает 1, если в коде этой программы содержится вирус, и печатает 0, если вируса нет. Применим машину T к программе V. Если T печатает 1, значит программа P и соответствующая ей Машина Тьюринга завершают свою работу на некотором входе B. Если T печатает 0, значит программа P и соответствующая ей Машина Тьюринга никогда не завершит свою работу на некотором входе B. Учитывая, что вход B и эмулируемая программой P Машина Тьюринга могут быть любыми, получаем, что Машина Тьюринга T способна для любой Машины Тьюринга и любого входа определить, завершит ли данная Машина Тьюринга работу на данном входе. Однако мы знаем, что это невозможно.
Полученное противоречие доказывает теорему.
Оценка сложности сигнатурного метода
Далее в своей работе Ф. Лейтольд обращается к проблеме обнаружения не всех возможных вирусов, а некоторого подмножества "известных" вирусов.
Для этого предлагается сигнатурный метод - обнаружение вируса по строке или подстроке его кода. Естественно, таким образом невозможно обнаружить полиморфные вирусы. Но для обнаружения обычных или олигоморфных вирусов такой способ годится: олигоморфные вирусы могут обнаруживаться по строке или подстроке кода расшифровщика.
В случаях, когда обнаружение осуществляется по подстроке вирусного кода (либо даже по полному коду распаковщика для олигоморфных вирусов) возможны ложные срабатывания. Ф. Лейтольд приводит оценку вероятности ложных обнаружений при следующих допущениях:
Длина сигнатуры - NОбщая длина анализируемых данных - L >> NКоличество символов в алфавите - n, и встречаются они в анализируемых данных с равной вероятностьюКоличество известных вирусов M
В этом случае оценка количества ложных обнаружений будет примерно равна:
Можно также подсчитать вычислительную сложность алгоритма, выполняющего поиск вирусов по сигнатуре. Для выполнения поиска требуется последовательно сравнить все ячейки анализируемой строки данных с первыми ячейками сигнатур. В общем случае это L·M сравнений. Далее, при обнаружении совпадения потребуется провести сравнение со второй ячейкой сигнатуры. Учитывая вероятность совпадения значения первой ячейки, количество сравнений второй ячейки будет
В худшем сценарии, когда все сигнатуры полностью различны, а n и N достаточно велики, количество сравнений составит s = L·M·N.
Следовательно, сигнатурный поиск может быть выполнен за полиномиальное время.
Необходимо понимать, что полученные оценки приблизительны и соответствуют худшему варианту поиска случайной подпоследовательности в случайной последовательности. На практике код программы и код вируса не являются случайными последовательностями и с учетом знания их структуры алгоритм поиска может быть существенно оптимизирован, оценка времени - уменьшена.
Олигоморфные и полиморфные вирусы
Везде ранее подразумевалось, что вирус никак не меняется при размножении, т. е. присоединенная вирусная часть одинакова при каждом заражении. Тем не менее, многие вирусы не обладают таким свойством и способны меняться при размножении.
Определение 2.19. Способ распространения называется полиморфным если можно найти две программы зараженные с использованием одного способа распространения одного вируса, такие что последовательности инструкций зараженных частей этих программ будут отличаться.
Определение 2.20. Вирус называется полиморфным, если он обладает полиморфным способом распространения.
Определение 2.21. Способ распространения называется олигоморфным, если можно найти две программы зараженные с использованием одного способа распространения одного вируса, такие что последовательности инструкций зараженных частей этих программ будут одинаковы (для любой пары), но хотя бы одна часть вирусного кода будет зашифрована с разными ключами.
Определение 2.22. Вирус называется олигоморфным, если он обладает олигоморфным способом распространения.
На практике выделяют также подвиды полиморфных и олигоморфных вирусов.
Определение 2.23. Вирус называется медленным полиморфным, если он обладает полиморфным способом распространения, но применяет этот способ очень редко.
Определение 2.24. Вирус называется медленным олигоморфным, если он обладает олигоморфным способом распространения, но ключ шифрования меняет очень редко.
Основные положения
В работе "An Undetectable Computer Virus" Дэвид Чесс и Стив Вайт попытались развить идеи Коэна и показать, что задача обнаружения вирусов остается неразрешимой и при более слабых допущениях. Этой работой они попытались охватить класс полиморфных вирусов.
Рассмотрим множество программ. Множеством значений каждой из программ является одна или несколько других программ. При каждом выполнении программа производит одну программу из своего множества значений (в зависимости от входных данных). Пусть при этом выполнялась программа p, а результатом ее работы стала программа q. В этом случае будем говорить, что p производит q. Будем также говорить, что p со временем производит q, если p производит q либо непосредственно, либо после конечного числа итераций, когда сперва выполняется программа p, затем ее результат и т. д. Отношение "со временем производит" является транзитивным замыканием отношения "производит".
Определение 2.2. Множество V называется вирусным, если это максимальное множество удовлетворяющее условию:
Максимальность понимается в том смысле, что не существует такой программы r
Далее в рамках изложения условимся отождествлять множество V с компьютерным вирусом. Программа p будет называться экземпляром вируса V или же будет говориться, что она заражена вирусом V, тттк p
Программа p будет называться просто зараженной, если: (V - вирус) [p
Будем говорить, что программа p размножается, если она производит новый экземпляр вируса (новый в смысле еще один, а не в смысле отличный от предыдущих).
Простейший вирус представляет собой множество из одного элемента и всегда производит сам себя. Более сложные множества соответствуют полиморфным вирусам, которые могут иметь несколько отличающихся форм, каждая из которых в процессе эволюции способна со временем произвести все остальные.
Предложенный формализм соответствует перезаписывающим вирусам, которые заменяют собой другие программы, принимая их имена, либо некоторым видам сетевых червей, которые распространяются создавая свои копии и рассылая их по сетевым каналам. Для описания вирусов в классическом определении Коэна необходимо усложнять модель. Однако основные результаты, которые будут получены ниже, могут быть распространены и на классические "паразитирующие" вирусы.
Практические следствия
На практике вирус W не представляет такой уж большой опасности и это связано с тем, что, как правило, не расценивается проблемой ложное срабатывание на программах вида:
если D(t), то завершить работу, иначе размножаться
или
если Sub1(u), то завершить работу, иначе { заменить текст подпрограммы Sub1 текстом произвольной программы; размножаться; завершить работу; } Sub1: вернуть D(аргумент);
Несмотря на то, что такие программы никогда не размножаются, их существование тесно связано с существованием определенных вирусов.
Здесь важно понимать значение полученного результата. Вывод Ф. Коэна важен в первую очередь тем, что можно без особых разбирательств отметать любые заявления о создании алгоритма точно детектирующего вирусы и только их. Точно так же на основании результата Д. Чесса и С. Вайта можно отметать заявления о создании алгоритма, способного обнаруживать без ложных срабатываний все экземпляры полиморфного вируса по одному его экземпляру.
В реальной жизни антивирусная программа считается качественной, если она обнаруживает все жизнеспособные экземпляры вируса, желательно также его нежизнеспособные ответвления, и при этом характеризуется сравнительно небольшим числом ложных срабатываний. Следует избегать лишь тех ложных срабатываний, которые затрагивают существующие программы, используемые в повседневной работе различными пользователями. Ложные срабатывания на искусственных примерах, появление которых на компьютерах пользователей близко к нулю, вполне допустимы.
Принятые обозначения
В дальнейшем изложении будет считаться, что данные и программы, во-первых, различимы, как это обычно и бывает в компьютерных системах, а во-вторых, могут быть закодированы натуральными числами. Поскольку и данные и программы всегда имеют ограниченный размер и ограниченный алфавит для их представления, принципиальная возможность взаимно однозначного кодирования натуральными числами сомнений не вызывает.
Исходя из сказанного, состояние некой вычислительной системы с точки зрения выполняющейся программы, может быть описано как набор доступных программе данных и других программ, что может быть выражено как наборы или последовательности натуральных чисел. Действие любой программы заключается в том, чтобы из одного набора данных и программ получить другой набор данных и программ.
Ниже везде неявно подразумевается описанная интерпретация вычислительной системы.
- Обозначим S - множество всех конечных последовательностей натуральных чисел,
Нотация
- f(s,t)
Определение служит для уточнения понятия тождественности программ, представленных в виде частичных функций.
Определение 2.27.
- z=z', иp=p', и
Если раньше для обозначения действия программы на систему использовались коды состояний, то в этом определении используется детализированное описание состояния и по сути вводится отношение между чистым и зараженным состоянием системы. Зараженное состояние характеризуется тем, что при прочих равных в нем некоторые программы изменены вирусом (функция h).
Определение 2.28. Для всех частичных функций
В этом определении уточняется введенное ранее отношение для состояний, получаемых в результате действия двух функций. Результатом действия функции f на состояние системы
Определение 2.29. Для всех частичных функций
Введенное обозначение призвано отразить тот факт, что зараженная программа не всегда выполняет заражение - в некоторых состояниях зараженная программа может выполнять ровно те же действия, что и незараженная, т. е. результат ее действия при некоторых состояниях системы будут точно таким же как и у незараженной программы.
Определение 2.30. Для всех геделевских нумераций частичных рекурсивных функций
- Повреждение:
В данном определении выбор переменных d и p в явном виде указывает на их природу - данные (информация не подверженная заражению) и программы (информация подверженная заражению).
Здесь необходимы комментарии:
Повреждение. Из определения следует, что результат действия зараженной программы при определенном состоянии системы определяется только типом вируса и состоянием системы, независимо от того, какая программа была заражена.На самом деле, выполняемое вирусом действие может и не быть деструктивным, важно то, что оригинальная программа не выполняется вовсе, т. е. выполняется функция прописанная в самом вирусе.Заражение или имитация. Здесь, согласно определению, ситуация прямо противоположная. Результат действия зараженной программы либо вовсе не отличается от результата действия исходной, либо отличается появлением в системе новых зараженных программ. Различное поведение определяется различиями в исходном состоянии системы.
Проблема обнаружения вирусов
Вместе с выделением класса вирусов возникает и проблема обнаружения вирусов.
Определение 2.25. Проблема обнаружения вирусов является задачей теории алгоритмов: существует ли алгоритм, с помощью которого для любой программы можно было бы определить содержит она вирус, способный к распространению, или нет.
Предполагается, что все данные о структуре программы и машины, на которой она выполняется доступны. Неизвестными являются только данные о вирусе.
RASPM с присоединенным вспомогательным хранилищем
Дальнейшее приближение модели к реальным компьютерам и операционным системам основывается на идее присоединенных внешних хранилищ (данных и программ).
Описанные в предыдущем пункте модели ограничены тем, что в чистом виде пригодны только для анализа отдельного алгоритма или программы. Для анализа взаимодействия алгоритмов потребовались бы значительные усилия. Чтобы упростить анализ таких ситуаций имеет смысл ввести в модель вычислительной машины специальную область или ленту, на которой будут храниться данные других программ. Назовем эту область присоединенным вспомогательным хранилищем (Attached Background Storage, ABS). Кроме этого имеет смысл потребовать, чтобы любая выполняющаяся программа имела полный доступ (чтение и запись) к этому хранилищу.
Определение 2.6. Вычислительная машина G с хранением программ в памяти с произвольной выборкой и с присоединенным вспомогательным хранилищем (RASPM с ABS) определяется шестью элементами:
где V - алфавит, состоящий из входных символов, выходных символов, а также символов, которые могут быть записаны на присоединенном вспомогательном устройстве и в ячейках памяти (регистрах), U - непустое конечное подмножество кодов инструкций, U V, T- непустое множество возможных действий процессора, f - однозначная функция f: U
Без потери общности можно допустить, что существует взаимно однозначное кодирование символов алфавита V целыми числами. При этом каждая инструкция должна сопровождаться значением операнда, таким образом каждая команда задается двумя ячейками: код инструкции в одной ячейке и значение операнда в следующей ячейке. Один из вариантов кодирования инструкций представлен в таблице:
| LOAD | Операнд | 10 | Загружает в аккумулятор значение, определяемое операндом |
| STORE | Операнд | 20 | Копирует значение аккумулятора в ячейку, определяемую операндом |
| ADD | Операнд | 30 | Прибавляет к аккумулятору значение, определяемое операндом |
| SUB | Операнд | 40 | Вычитает из аккумулятора значение, определяемое операндом |
| MULT | Операнд | 50 | Умножает аккумулятор на значение, определяемое операндом |
| DIV | Операнд | 60 | Делит аккумулятор на значение, определяемое операндом |
| AND | Операнд | 70 | Выполняет побитовую операцию "И" между аккумулятором и значением, определяемым операндом |
| OR | Операнд | 80 | Выполняет побитовую операцию "ИЛИ" между аккумулятором и значением, определяемым операндом |
| XOR | Операнд | 90 | Выполняет побитовую операцию "исключающее ИЛИ" между аккумулятором и значением, определяемым операндом |
| READ | Операнд | A0 | Считывает значение с входной ленты в ячейку, определяемую операндом |
| WRITE | Операнд | B0 | Записывает на выходную ленту значение ячейки, определяемой операндом |
| GET | Операнд | C0 | Считывает значение с вспомогательного хранилища в ячейку, определяемую операндом |
| PUT | Операнд | D0 | Записывает на вспомогательное хранилище значение ячейки, определяемой операндом |
| SEEK | Операнд | E0 | Перемещает считывающую/записывающую головку вспомогательного хранилища в позицию, определяемую операндом |
| JUMP | Метка | FC | Присваивает счетчику инструкций значение метки |
| JGTZ | Метка | FD | Присваивает счетчику инструкций значение метки, если аккумулятор содержит положительное число |
| JZERO | Метка | FE | Присваивает счетчику инструкций значение метки, если аккумулятор равен нулю |
Обозначим значение i-й ячейки памяти как c(i), где i - целое число. Допустимые коды операндов в таком случае представлены в таблице.
| i | 1 | i |
| [i] | 2 | c(i) |
| [[i]] | 3 | c(c(i)) |
Поскольку программа в случае RASPM способна изменять себя в процессе выполнения, многие команды, в частности, команды с операндом [[i]] могут быть эмулированы через другие команды.
Также нужно понимать, что не любой операнд подходит к каждой инструкции. Например, инструкция READ может иметь только операнды типов [i] и [[i]], поскольку записывает значение из ленты в память.
При включении RASPM с ABS счетчик инструкций принимает начальное значение q и процессор немедленно выполняет команду, расположенную по адресу, указанному в q. Дальнейшее выполнение программы определяется командами, записанными в памяти и таким образом полностью определяется начальным содержанием памяти. Завершение работы машины происходит в следующих случаях:
когда машина выключается пользователемкогда счетчик указывает на ячейку памяти, содержимое которой не является кодом команды (x
Таким образом, в отличие от RAM специальная команда для завершения работы машины не используется.
При каждом включении машины содержимое памяти приводится к исходному значению M, а при каждом выключении обнуляется. Содержимое вспомогательного хранилища, напротив, сохраняется от выключения к включению. Можно также допустить, что вспомогательное хранилище разрешается отсоединять от одной машины и присоединять к другой. Естественным расширением RASPM с ABS выглядит возможность одновременного подключения нескольких вспомогательных хранилищ к одной машине. Следовательно можно определить RASPM с несколькими ABS следующим образом.
Определение 2.7. Вычислительная машина с хранением программ в памяти с произвольной выборкой и с несколькими присоединенными вспомогательными хранилищами (Random Access Stored Program Machine with Several Attached Background Storages, RASPM с SABS) определяется так же как и RASPM с ABS, но с некоторыми допущениями: к RASPM с SABS может быть одновременно присоединено несколько вспомогательных хранилищвсе символы на всех вспомогательных хранилищах входят в алфавит Vмножество возможных действий процессора включает дополнительное действия выбора активного вспомогательного хранилища (см.
нижеследующую таблицу) после выполнения соответствующей команды все инструкции, так или иначе связанные с использованием вспомогательного хранилища, будут относиться к активному хранилищуесли инструкция, связанная с использованием вспомогательного хранилища, выполняется до команды выбора активного хранилища, она будет использовать первое хранилищемашина останавливается в тех же случаях, что и RASPM с ABS, а также в случае выполнения команды смены хранилища, если операнд указывает на несуществующее хранилище
| SETDRIVE | операнд | FO | Устанавливает активным вспомогательным хранилищем ленту, определяемую операндом |
Доказательство. Достаточно показать, что RASPM с SABS может быть проэмулирована RASPM с ABS, поскольку симметричное утверждение доказывается тривиально.
Для эмуляции N вспомогательных хранилищ одним хранилищем воспользуемся следующим принципом: пронумеруем ленты вспомогательных хранилищ от 0 до N-1. Перенесем j-й символ i-й ленты в (Nj+i)-ю позицию новой ленты. Кроме этого изменим структуру памяти эмулирующей машины следующим образом:
- Нулевая ячейка по-прежнему аккумулятор1-ю ячейку оставим для будущих целей2-я ячейка содержит адрес ячейки с номером от 3 до N+2, которая хранит номер позиции головки чтения/записи на ленте вспомогательного хранилищаi-я ячейка в диапазоне от 3 до N+2 содержит позицию головки чтения/записи (i-3)-й виртуальной ленты вспомогательного хранилищаi-я ячейка при i>N+2 содержит то же значение, что и (i-N-2)-я ячейка эмулируемой машины, если при трансляции программа эмулируемой машины не подверглась изменениям (см. ниже), в противном случае сдвиг происходит на большее количество позиций
Команды эмулируемой машины переносятся в память эмулирующей машины без изменений за исключением следующих случаев:
если исходная программа должна изменить текущее активное хранилище, вместо команды SETDRIVE a выполняется последовательность команд, меняющая номер виртуальной ленты во 2-м регистре:
STORE [1] ; сохранить значение аккумулятора в 1-м регистре LOAD a ; загрузить операнд ADD 3 ; вычислить настоящий адрес STORE [2] ; сохранить его, как адрес активной ленты LOAD [1] ; восстановить значение аккумулятора
если оригинальная программа должна произвести чтение или запись на вспомогательном хранилище (например, PUT a), эмулирующей программе потребуется вычислить соответствующий номер ячейки на реальной ленте и произвести запись в нее путем выполнения следующей последовательности команд:
STORE [1] ; сохранить значение аккумулятора SEEK [[2]] ; переместить головку в нужную позицию PUT a ; записать операнд на ленту LOAD [[2]] ; загрузить позицию на реальной ленте в аккумулятор ADD N ; изменить позицию (соответствует сдвигу вправо) STORE [[2]] ; сохранить позицию LOAD [1] ; восстановить значение аккумулятора
если оригинальная программа перемещает головку чтения/записи при помощи команды SEEK a, эмулирующая программа выполняет такую последовательность команд:
STORE [1] ; сохранить значение аккумулятора LOAD a ; загрузить операнд MULT N ; вычислить по операнду ADD [2] ; номер позиции SUB 3 ; на реальной ленте STORE [[2]] ; сохранить новую позицию LOAD [1] ; восстановить значение аккумулятора
в процессе копирования программы из памяти эмулируемой машины в память эмулирующей, при замене описанных команд на последовательности команд, остальные команды сдвигаются на необходимое число позиций и все ссылки на ячейки памяти пересчитываются соответственно сдвигу
Построенная таким образом симулирующая машина требует не более 7 операций на каждую операцию исходной программы, а значит сложность эмулирующей программы будет не больше 7T(n), где T(n) - сложность эмулируемой программы. Теорема доказана.
Следовательно увеличение количества вспомогательных хранилищ не увеличивает вычислительной способности машины RASPM с ABS. Осознавая этот факт, несложно понять, что вычислительная способность RASPM с ABS не превышает вычислительной способности RASPM, что и утверждается соответствующей теоремой.
Теорема 2.6. Любая машина RASPM с ABS может быть проэмулирована машиной RASPM, и затраты на операции будут отличаться не более чем на постоянный множитель
Доказательство. По аналогии с доказательством предыдущей теоремы можно скомбинировать содержимое памяти и вспомогательного хранилища эмулируемой машины в памяти эмулирующей машины и получить RASPM - машину без вспомогательного хранилища. Основная разница при комбинировании будет заключаться в том, что смешиваться будут не отдельные ячейки, а их блоки, поскольку отрывать значение операнда от кода инструкции нельзя. Также следует учитывать, что для сохранения связности программы потребуется добавить после каждой команды оригинальной программы команду JUMP, чтобы пропустить ячейки памяти относящиеся к виртуальной вспомогательной ленте. В остальном принципы комбинирования остаются теми же, за тем исключением, что нет необходимости использовать несколько регистров для нескольких лент и отдельный регистр для номера ленты - достаточно будет ограничиться только регистром для хранения номера позиции на ленте. На этом неформальное доказательство можно считать законченным. Приводить формальное доказательство смысла нет из-за его относительной громоздкости.
Прямым следствием из теоремы будет следующая теорема:
Теорема 2.7. Вычислительная способность Машины Тьюринга и RASPM с ABS эквивалентны, а их затраты на вычисления находятся в полиномиальной зависимости
Доказательство. Этот результат получается из сопоставления результатов теорем 2.1, 2.2, 2.3 и 2.6.
Результат Фреда Коэна
В 1984 г. в своей работе "Computer Viruses - Theory and Experiments" Фред Коэн показал, что задача обнаружения компьютерных вирусов является неразрешимой. При этом он руководствовался следующими рассуждениями.
Отправной точкой был выбор определения вируса:
Определение 2.1. Компьютерным вирусом является программа, способная заражать другие программы изменяя их таким образом, чтобы они включали возможно измененную копию вируса.
Следовательно, чтобы определить, является ли программа P вирусом, необходимо выяснить заражает ли она другие программы. Предположим, существует процедура D, позволяющая по любой программе P сказать вирус это или нет. Но тогда можно составить программу V, которая будет включать процедуру D и будет заражать другие программы только в том случае, когда D не определит V как вирус и не будет заражать в противном случае.
Соответственно, если процедура D, будучи примененной к программе V, скажет, что это вирус, программа V на самом деле не будет заражать файлы и не будет вирусом согласно определению. И наоборот, если согласно процедуре D программа V не является вирусом, на самом деле она будет заражать другие программы, а значит будет вирусом.
Таким образом, гипотетическая процедура D оказывается противоречивой и, следовательно, не существует.
Результат Леонарда Адельмана
Леонард Адельман, известный математик, обладатель премии Тьюринга, участвовавший в свое время разработке криптосистемы RSA (буква A в аббревиатуре) для исследования феномена вирусов решил использовать другой формализм теории алгоритмов - не формализм машин Тьюринга, а формализм рекурсивных функций.
Теория машин Тьюринга и теория рекурсивных функций в некотором смысле эквиваленты - алгоритмы, вычислимые в одной теории будут вычислимыми в другой, и наоборот. Этот факт в совокупности с тезисом Тьюринга-Черча, означает, что полученные Л. Адельманом результаты в той же степени применимы к современным реалиям, что и результаты Ф. Коэна, Д. Чесса, С. Вайта, Ф. Лейтольда и других исследователей опиравшихся в своих работах на теорию машин Тьюринга.
Слабое определение обнаружения
Можно в некотором роде ослабить определение обнаружения, сохранив полученный выше результат в силе. В частности можно допустить, чтобы алгоритм, претендующий на обнаружение вируса V, возвращал 1 не только на экземплярах этого вируса, но и на некоторых других программах, при условии, что они тоже являются экземплярами (других) вирусов.
Определение 2.4. Будем говорить, что алгоритм A слабо обнаруживает вирус V тттк для любой программы p, A(p) завершает работу и возвращает 1, если p
Вполне очевидно, что для сконструированного вируса W не существует алгоритма, который мог бы слабо обнаруживать этот вирус, поскольку такой алгоритм будет либо возвращать 1 на программе, которая просто завершает свою работу, либо будет возвращать не 1 для программы, являющейся экземпляром W.
Способы размножения вирусов
Как известно из практики, вирус может присоединяться к программе используя различные технологии. Формы присоединения вирусов к различным программным областям будут называться способами размножения. Один и тот же вирус может обладать несколькими способами размножения.
Определение 2.14. Способ размножения вируса называется машинозависимым, если для использования этого способа вирусу требуется машина, обладающая определенными характеристиками или свойствами. В противном случае, когда характеристики и свойства машины не влияют на размножение вируса определенным способом, способ размножения называется машиннонезависимым.
Аналогичным образом можно рассмотреть и зависимость способов размножения от операционных систем.
Определение 2.15. Способ размножения вируса называется ОС зависимым, если для использования этого способа вирусу требуется операционная система, обладающая определенными характеристиками или свойствами. В противном случае, когда характеристики и свойства операционной системы не влияют на размножение вируса определенным способом, способ размножения называется ОС независимым.
Рассматривая совокупность способов размножения, можно распространить понятия машинозависимости и ОС зависимости на вирусы.
Определение 2.16. Вирус называется машинозависимым, если все его способы размножения машинозависимы. Аналогично, вирус называется машиннонезависимым, если все его способы размножения машиннонезависимы.
Определение 2.17. Вирус называется ОС зависимым, если все его способы размножения ОС зависимы. Аналогично, вирус называется ОС независимым, если все его способы размножения ОС независимы.
В некоторых случаях вирусы могут присоединять себя не к программной области а к файлу данных. Например, к исходному коду какой-либо программы. В этом случае для запуска вируса требуется, чтобы файл данных был преобразован третьей программой (компилятором) в файл программы. Дадим определение и такого способа размножения.
Определение 2.18. Способ размножения называется непосредственным, если вирус присоединяет себя непосредственно к программной области. Способ размножения называется косвенным, если вирус присоединяет себя к файлу данных.
Сравнение с результатом Ф. Коэна
Полученный результат является дополнением результата Ф. Коэна. Действительно, результат Ф. Коэна можно кратко записать в виде:
для любого обнаруживающего алгоритма найдется вирус, который не будет обнаруживаться данным алгоритмом.
Результат Д. Чесса и С. Вайта может быть по аналогии представлен как:
существует полиморфный вирус, такой что для любого обнаруживающего алгоритма, алгоритм не будет обнаруживать этот вируссуществует полиморфный вирус, такой что для любого обнаруживающего алгоритма, алгоритм не будет слабо обнаруживать этот вирус
Вирусы в RASPM с ABS
С учетом данного ранее определения операционной системы можно сформулировать определение вируса.
Определение 2.13. Компьютерный вирус определяется как часть программы, присоединенная к области программы и способная присоединять себя к областям других программ. Компьютерный вирус выполняется при выполнении программы к области которой он присоединен.
В общем случае присоединение вируса к области программы не должно оставлять неизменным результат выполнения программы (без учета действий вируса), однако такой способ присоединения часто используется вирусами для маскировки своего присутствия в системе (в области программы).
о компьютерных вирусах, всегда подразумевают
Когда говорят о компьютерных вирусах, всегда подразумевают некий класс программ, обладающих определенными свойствами. Кроме того, для каждого нового вируса существует некая процедура согласно которой антивирусные эксперты решают - вирус это или нет, прежде чем вносить его сигнатуру в вирусную базу.
В связи с этим возникает вопрос о возможности формализовать эту процедуру выяснения относится ли программа к классу вирусов. Этой проблемой занимались многие исследователи еще с первой половины 80-х годов XX века. И самым первым из них был Фред Коэн.
Вычислительная машина с хранением программ в памяти с произвольной выборкой
Развитием формализма вычислительной машины с произвольной выборкой является вычислительная машина с хранением программ в памяти с произвольной выборкой (Random Access Stored Program Machine, RASPM), отличие которой состоит только в том, что программа сохраняется в памяти, а значит может изменять сама себя в процессе выполнения.
Набор инструкций для RASPM в общем случае может не отличаться от набора инструкций RAM. Впрочем, некоторые инструкции могут быть упрощены. Так, вместо непрямой адресации можно использовать возможность модификации инструкций программы для получения того же эффекта.
Известно, что имеют место две теоремы:
Теорема 2.1. Если стоимость инструкции является величиной постоянной или находится в логарифмической зависимости от длины операнда, то для любой программы RAM, имеющей сложность T(n), найдется константа k и эквивалентная программа RASPM, сложность которой будет не больше kT(n).
Теорема 2.2. Если стоимость инструкции является величиной постоянной или находится в логарифмической зависимости от длины операнда, то для любой программы RASPM, имеющей сложность T(n), найдется константа k и эквивалентная программа RAM, сложность которой будет не больше kT(n).
Вычислительная машина с произвольной выборкой
Для моделирования компьютерной среды Ф. Лейтольд отталкивался от вычислительной машины с произвольной выборкой (Random Access Machine, RAM), определение которой представлено ниже.
Вычислительная машина с произвольной выборкой состоит из следующих компонентов:
Входная лента, представляющая собой последовательность ячеек, содержащих целые числа и доступных только для последовательного чтения - после чтения ячейки считывающая головка автоматически перемещается вправоВыходная лента, представляющая собой последовательность ячеек, доступных только для последовательной записи, по умолчанию эти ячейки пустыПрограмма - последовательность (возможно индексированная, т.е. с возможностью указать адрес некоторых или любых инструкций) инструкций, не находящаяся в памяти и, соответственно, неизменяемая, по умолчанию выполнение программы начинается с первой инструкции (можно ввести счетчик инструкций, указывающий на следующую к выполнению инструкцию, в этом случае по умолчанию счетчик указывает на первую инструкцию)Память - неограниченная последовательность регистров r0, r1, …, ri, …, способных хранить целые числа, по умолчанию значения регистров пусты, нулевой регистр r0 используется для вычислений и часто называется аккумулятором, доступ к регистрам производится непосредственно по их индексам, откуда и происходит название машины.
Как следует из определения, после того как ячейка была прочитана или записана, она не может быть прочитана или записана еще раз. Неизменяемость программы означает в том числе и то, что программа не может менять себя в процессе выполнения. Фактический набор используемых в программе инструкций большого значения не имеет, поскольку вычислительная сложность алгоритма реализованного в разных (разумных) наборах инструкций асимптотически будет совпадать. Один из возможных вариантов инструкций для вычислительной машины с произвольной выборкой представлен в таблице:
| LOAD | Операнд | Загружает в память значение, определяемое операндом |
| STORE | Операнд | Копирует значение аккумулятора в ячейку памяти (регистр) определяемый операндом |
| ADD | Операнд | Добавляет к аккумулятору значение, определяемое операндом |
| SUB | Операнд | Вычитает из аккумулятора значение, определяемое операндом |
| MULT | Операнд | Умножает аккумулятор на значение, определяемое операндом |
| DIV | Операнд | Делит аккумулятор на значение, определяемое операндом |
| READ | Операнд | Считывает значение с входящей ленты в регистр, определяемый операндом |
| WRITE | Операнд | Записывает на выходную ленту значение, определяемое операндом |
| JUMP | Метка | Присваивает счетчику инструкций значение метки |
| JGTZ | Метка | Присваивает счетчику инструкций значение метки, если аккумулятор содержит положительное число |
| JZERO | Метка | Присваивает счетчику инструкций значение метки, если аккумулятор равен нулю |
| HALT | Завершает работу машины |
Допускается три вида операндов:
i - обозначает собственно значение целого числа i[i] - для неотрицательных i обозначает значение регистра ri[[i]] - косвенная адресация, обозначает значение регистра rj, где j - значение регистра ri. Если j<0, машина завершает работу
По умолчанию (см. также определение) значение всех регистров равно нулю, счетчик инструкций указывает на первую инструкцию программы и выходная лента пуста. После выполнения k-й инструкции счетчик либо автоматически увеличивается на единицу и указывает на (k+1)-ю инструкцию, либо, если была выполнена инструкция JUMP или выполнены условия инструкций JGTZ или JZERO, принимает значение метки, либо, если была выполнена инструкция HALT, машина прекращает свою работу.
Из вышеизложенного видно, что разные
Из вышеизложенного видно, что разные исследователи в разное время используя различный математический аппарат получили эквивалентный вывод. Класс вирусов является неразрешимым, т.е. не существует алгоритма, который бы позволил однозначно определить является программа зараженной (вирусом) или нет. Речь идет даже не о нехватке ресурсов, а о принципиальной невозможности создать подобный алгоритм.
В связи с этим проблема естественным образом переходит из теоретической области в практическую, где применяются частные решения для решения частных задач обнаружения вирусов. В частности решаются задачи определения вирусов по сигнатурам, или вероятностного определения вирусов. О подклассах вредоносных программ и практических методах борьбы с ними и пойдет речь в последующих главах.
