Проблема остановки: почему нельзя написать идеальный антивирус

Бывают задачи, которые невозможно решить программой — и это доказано так же строго, как теорема Пифагора.

Нельзя написать программу, которая по любой другой программе заранее скажет, зациклится та или нет. Это не вопрос мощности компьютера — это фундаментальный запрет.

Задача, которая выглядит безобидно

Представьте, что вас просят написать функцию halts(program, input). Она принимает на вход чужую программу и её входные данные, а возвращает true, если эта программа когда-нибудь завершится, и false, если она зациклится навсегда. Звучит полезно: такой анализатор спас бы нас от зависаний.

Кажется, что задача сложная, но решаемая — ну, надо просто проанализировать код повнимательнее. В 1936 году Алан Тьюринг доказал, что универсального решения не существует. И доказательство умещается в одну хитрую идею.

Хитрость с самоотрицанием

Допустим, такая функция halts всё-таки написана и работает безупречно. Тогда мы можем построить вредную программу — назовём её trouble:

def trouble(prog):
    if halts(prog, prog):   # завершится ли prog, поданная сама себе?
        while True:          # тогда мы нарочно зацикливаемся
            pass
    else:
        return              # иначе спокойно завершаемся

А теперь зададим главный вопрос: что произойдёт, если запустить trouble(trouble), то есть подать программе саму себя?

Если halts говорит, что trouble(trouble) завершится, то по коду мы попадаем в while True и зацикливаемся. Противоречие.
Если halts говорит, что она зациклится, то мы идём в else и завершаемся. Снова противоречие.

Получается, любой ответ halts оказывается ложным. А раз идеальная halts приводит к противоречию, значит, её просто не может существовать. Это рассуждение «от противного», тот же приём, что в школьном доказательстве иррациональности корня из двух.

Причём тут антивирус

Идеальный антивирус — это программа, которая по любому файлу безошибочно говорит: «вредит» или «безопасен». Но «вредит» в общем случае означает что-то вроде «выполнит запрещённое действие при каких-то условиях». А определить, дойдёт ли произвольная программа до конкретной строки кода, — это переформулировка проблемы остановки.

Формально это закрепляет теорема Райса: любое нетривиальное свойство поведения программы (а «является ли вирусом» — именно такое) неразрешимо алгоритмически. То есть универсального детектора вирусов, который никогда не ошибается, быть не может — это математический факт, а не недоработка инженеров.

Как же тогда живут реальные антивирусы

Невозможность идеала не означает беспомощность. Антивирусы работают на компромиссах:

Сигнатуры	Ищут известные куски кода вредоносов — быстро, но бессильны против нового.
Эвристики	Подозрительные паттерны поведения — ловят неизвестное, но дают ложные срабатывания.
Песочница	Запускают файл в изоляции и смотрят, что он делает — но программа может «затаиться».

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

Что отсюда забрать

Проблема остановки — это не курьёз, а граница познаваемого для машин. Она объясняет, почему компиляторы не могут поймать все ваши бесконечные циклы, почему статические анализаторы кода неизбежно либо что-то пропускают, либо ругаются зря, и почему «защита, которая ловит вообще всё» — это всегда маркетинг, а не правда. Понимать эту границу полезно: она экономит силы, которые иначе ушли бы на поиск несуществующего идеального решения.