Студопедия

КАТЕГОРИИ:


Архитектура-(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.3.

Алгоритм A обнаруживает вирус V для любой программы p: A(p) завершает работу и печатает 1 .

Аналогично, алгоритм A обнаруживает множество вирусов S для любой программы p: A(p) завершает работу и печатает 1

По сути это то же определение обнаружения, что и использованное Ф. Коэном в его дебютной работе.

Полученный Ф. Коэном результат, о том, что не существует алгоритма 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 и только их.




Поделиться с друзьями:


Дата добавления: 2014-11-20; Просмотров: 339; Нарушение авторских прав?; Мы поможем в написании вашей работы!


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



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




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