Общая проблема обнаружения вирусов

Проблема обнаружения вирусов

Олигоморфные и полиморфные вирусы

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

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

Определение 2.20. Вирус называется полиморфным, если он обладает полиморфным способом распространения.

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

Определение 2.22. Вирус называется олигоморфным, если он обладает олигоморфным способом распространения.

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

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

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

Вместе с выделением класса вирусов возникает и проблема обнаружения вирусов.

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

Предполагается, что все данные о структуре программы и машины, на которой она выполняется доступны. Неизвестными являются только данные о вирусе.

Согласно тезису Тьюринга-Черча, если бы существовал алгоритм обнаружения вирусов, можно было бы создать Машину Тьюринга, которая бы выполняла этот алгоритм. Покажем, что такой Машины Тьюринга не существует.

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

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

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