Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

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




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

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

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

Определение 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; Просмотров: 380; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.009 сек.