Теоретические сведения о компьютерных вирусах

RASPM с присоединенным вспомогательным хранилищем

Дальнейшее приближение модели к реальным компьютерам и операционным системам основывается на идее присоединенных внешних хранилищ (данных и программ).

Описанные в предыдущем пункте модели ограничены тем, что в чистом виде пригодны только для анализа отдельного алгоритма или программы. Для анализа взаимодействия алгоритмов потребовались бы значительные усилия. Чтобы упростить анализ таких ситуаций имеет смысл ввести в модель вычислительной машины специальную область или ленту, на которой будут храниться данные других программ. Назовем эту область присоединенным вспомогательным хранилищем (Attached Background Storage, ABS). Кроме этого имеет смысл потребовать, чтобы любая выполняющаяся программа имела полный доступ (чтение и запись) к этому хранилищу.

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

Обозначим значение i -й ячейки памяти как c(i), где i - целое число. Допустимые коды операндов в таком случае представлены в таблице.

Полный код команды в этом случае будет складываться (в буквальном смысле) из кода инструкции и кода операнда. Например, команда ADD [i] будет иметь код 32, а команда GET [[i]] - код C3.

Поскольку программа в случае RASPM способна изменять себя в процессе выполнения, многие команды, в частности, команды с операндом [[i]] могут быть эмулированы через другие команды.

Также нужно понимать, что не любой операнд подходит к каждой инструкции. Например, инструкция READ может иметь только операнды типов [i] и [[i]], поскольку записывает значение из ленты в память.

При включении RASPM с ABS счетчик инструкций принимает начальное значение q и процессор немедленно выполняет команду, расположенную по адресу, указанному в q. Дальнейшее выполнение программы определяется командами, записанными в памяти и таким образом полностью определяется начальным содержанием памяти. Завершение работы машины происходит в следующих случаях:

Таким образом, в отличие от RAM специальная команда для завершения работы машины не используется.

При каждом включении машины содержимое памяти приводится к исходному значению M, а при каждом выключении обнуляется. Содержимое вспомогательного хранилища, напротив, сохраняется от выключения к включению. Можно также допустить, что вспомогательное хранилище разрешается отсоединять от одной машины и присоединять к другой. Естественным расширением RASPM с ABS выглядит возможность одновременного подключения нескольких вспомогательных хранилищ к одной машине. Следовательно можно определить RASPM с несколькими ABS следующим образом.

Доказательство. Достаточно показать, что RASPM с SABS может быть проэмулирована RASPM с ABS, поскольку симметричное утверждение доказывается тривиально.

Для эмуляции N вспомогательных хранилищ одним хранилищем воспользуемся следующим принципом: пронумеруем ленты вспомогательных хранилищ от 0 до N-1. Перенесем j -й символ i -й ленты в (Nj+i) -ю позицию новой ленты. Кроме этого изменим структуру памяти эмулирующей машины следующим образом:

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

STORE    [1]    ; сохранить значение аккумулятора в 1-м регистре 
LOAD    a    ; загрузить операнд
ADD    3    ; вычислить настоящий адрес
STORE    [2]    ; сохранить его, как адрес активной ленты
LOAD    [1]    ; восстановить значение аккумулятора

STORE    [1]    ; сохранить значение аккумулятора
SEEK    [[2]]    ; переместить головку в нужную позицию
PUT    a    ; записать операнд на ленту
LOAD    [[2]]    ; загрузить позицию на реальной ленте в аккумулятор
ADD    N    ; изменить позицию (соответствует сдвигу вправо)
STORE    [[2]]    ; сохранить позицию
LOAD    [1]    ; восстановить значение аккумулятора

STORE    [1]    ; сохранить значение аккумулятора
LOAD    a    ; загрузить операнд
MULT    N    ; вычислить по операнду
ADD    [2]    ; номер позиции
SUB    3    ; на реальной ленте
STORE    [[2]]    ; сохранить новую позицию
LOAD    [1]    ; восстановить значение аккумулятора

Построенная таким образом симулирующая машина требует не более 7 операций на каждую операцию исходной программы, а значит сложность эмулирующей программы будет не больше 7T(n), где T(n) - сложность эмулируемой программы. Теорема доказана.

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

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

Прямым следствием из теоремы будет следующая теорема:

Доказательство. Этот результат получается из сопоставления результатов теорем 2.1, 2.2, 2.3 и 2.6.

Моделирование операционных систем

Естественным желанием является использовать RASPM с ABS и RASPM с SABS для запуска программ. Компоненты V, U, T и f машины $$G = \langle V, U, T, f, q, M \rangle$$ G= V, U, T, f, q, M были определены ранее. Теперь, задав определенным образом M и q можно получить программу, которая и будет определять характер функционирования машины. Разумно потребовать, чтобы файлы программ и данных хранились на вспомогательном(ых) хранилище(ах), порядок выполнения программ определялся входной лентой, и чтобы выполняемая программа могла модифицировать как данные, так и программы на вспомогательном хранилище. Соответственно необходима программа-оболочка, способная работать с файлами данных и программ и выполнять другие программы.

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

Это означает, что определив машину RASPM с ABS, мы определим также и операционную систему, т. к. M является частью определения машины.

В таком случае операционную систему можно будет поменять вместе с вспомогательным хранилищем.

На ту же ситуацию можно взглянуть и с обратной стороны.

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

Из определений непосредственно следуют следующие теоремы.

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

Вирусы в 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 способна для любой Машины Тьюринга и любого входа определить, завершит ли данная Машина Тьюринга работу на данном входе. Однако мы знаем, что это невозможно.

Полученное противоречие доказывает теорему.

Оценка сложности сигнатурного метода

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

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

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

В этом случае оценка количества ложных обнаружений будет примерно равна:

Можно также подсчитать вычислительную сложность алгоритма, выполняющего поиск вирусов по сигнатуре. Для выполнения поиска требуется последовательно сравнить все ячейки анализируемой строки данных с первыми ячейками сигнатур. В общем случае это LxM сравнений. Далее, при обнаружении совпадения потребуется провести сравнение со второй ячейкой сигнатуры. Учитывая вероятность совпадения значения первой ячейки, количество сравнений второй ячейки будет $$L \cdot M \cdot \frac{1}{n}$$. Аналогично, третьей - $$L \cdot M \cdot \frac{1}{n^2}$$ и т. д. Общее количество сравнений составит:

В худшем сценарии, когда все сигнатуры полностью различны, а n и N достаточно велики, количество сравнений составит s = LxMxN.

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

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

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

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

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

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

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

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

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

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

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

В этом определении уточняется введенное ранее отношение для состояний, получаемых в результате действия двух функций. Результатом действия функции f на состояние системы $$\langle s,t \rangle$$ является натуральное число, которое можно однозначно интерпретировать как новое состояние $$\langle s',t' \rangle$$. Точно так же $$g(s,t) = \langle s'',t'' \rangle$$. Соответственно, запись $$\begin{aligned} _h_~~~~~~~ \\ f(s,t) : g(s,t) \end{aligned} $$ обозначает, что обе программы завершают свою работу при запуске из состояния $$\langle s,t \rangle$$ и результат их выполнения будет отличаться фактом заражения некоторых программ: $$\begin{aligned} _h_~~~~~~~~~ \\ \langle s',t' \rangle : \langle s'',t'' \rangle \end{aligned} $$.

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

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

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

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

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

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

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

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

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

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

Обнаружение компьютерных вирусов

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

Теорема приводится без доказательства.

Здесь $$\Pi_2$$ - класс множеств в арифметической классификации. Известно, что классы множеств $$\Pi_n$$ с индексом 1 и выше являются неразрешимыми. Следовательно и множество вирусов является неразрешимым.

Заключение

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

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