Почему автоматическая проверка кода на уязвимости невозможна в принципе

Обещания проверить код на уязвимости часто превращаются в вычисления, которые займут больше времени, чем возраст вселенной. Понять, почему это так — значит понять границы автоматизированной безопасности. https://seberd.ru/4852

Вычислительная сложность задач верификации безопасности программного обеспечения

Программисты и специалисты по безопасности часто говорят о проверке кода. В идеальном мире инструмент просканировал бы программу и дал однозначный ответ: «Уязвимостей нет» или «Вот все проблемы». На практике любой серьёзный статический или динамический анализатор выдаёт сотни предупреждений, большинство из которых — ложные срабатывания. Это не недостаток конкретного инструмента, а фундаментальное следствие вычислительной сложности задач, которые мы пытаемся решить.

Что такое верификация и почему она «задача»

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

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

Проблема в том, что для нетривиальных программ количество возможных путей выполнения растёт экспоненциально с увеличением числа условных ветвлений, циклов и входных данных. Даже простая программа с десятком вложенных `if` может породить тысячи теоретических путей. Проверить каждый из них методом прямого перебора физически невозможно для реальных проектов.

Классы сложности: от P до неразрешимого

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

Задачи класса P (Polynomial) решаются за время, ограниченное полиномом от размера входа. Пример: проверить, есть ли в коде конкретная строка. Для таких задач существуют эффективные алгоритмы.
Задачи класса NP (Nondeterministic Polynomial) допускают быструю проверку предложенного решения, но поиск решения может потребовать перебора. Классический пример — задача выполнимости булевых формул (SAT). Многие задачи анализа потока данных, например, поиск возможности достичь определённой точки кода, сводятся к NP-полным задачам.
Задачи с ещё более высокой сложностью (PSPACE, EXPTIME) требуют ресурсов, растущих экспоненциально или использующих полиномиальную память. Проверка некоторых свойств программ с неограниченными циклами или параллельными процессами попадает сюда.
Неразрешимые задачи — для них не существует универсального алгоритма, дающего ответ всегда. Самый известный пример — проблема остановки: нельзя создать анализатор, который для произвольной программы и входа определит, завершится ли её выполнение. Многие глубокие вопросы о поведении программы (например, «никогда ли не произойдёт деление на ноль при любых входах?») неразрешимы в общем случае.

Большинство нетривиальных задач верификации безопасности принадлежат к классам NP, PSPACE или являются неразрешимыми. Это не просто теория, это прямой барьер на пути создания «идеального» сканера уязвимостей.

Как сложность проявляется в реальных инструментах

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

Статический анализ (SAST)

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

Абстрактная интерпретация работает не с конкретными значениями переменных, а с их абстрактными областями (например, «положительное число», «нуль», «отрицательное число»). Это позволяет анализировать множество путей одновременно, но теряет точность, порождая ложные срабатывания, когда анализатор не может доказать безопасность.
Поток данных часто реализуется как анализ над конечной решёткой значений, что гарантирует завершение, но опять же за счёт потери информации. Точный анализ потока данных для всех возможных путей — NP-Cложная задача.
Символическое выполнение представляет значения переменных как символьные выражения и строит логические формулы для путей выполнения. Проверка выполнимости этих формул (задача SAT) — NP-полная. Поэтому инструменты ограничивают глубину анализа или длину формул.

Динамический анализ (DAST, IAST, фаззинг)

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

Фаззинг, это подача случайных или сгенерированных по правилам входных данных. Покрытие всех возможных комбинаций входных параметров даже для одной функции экспоненциально зависит от их количества и размеров. Умный фаззинг использует обратную связь от программы для направления генерации, но и он не может гарантировать полный перебор.
Анализ покрытия кода (Code Coverage) — метрика, показывающая, какая часть кода была выполнена при тестировании. Достижение 100% покрытия ветвей (branch coverage) для сложной программы также часто является NP-трудной задачей из-за необходимости подбора входных данных, которые проходят по каждому условному переходу.

Практические следствия для регуляторики и стандартов

Требования стандартов безопасности, таких как те, что связаны с 152-ФЗ и документами ФСТЭК, часто включают необходимость проведения анализа защищённости кода. Понимание лежащей в основе вычислительной сложности критически важно для:

Реалистичной постановки задач. Требование «исключить все уязвимости» или «провести полную верификацию» для сложной системы с формальной точки зрения может быть невыполнимым. Правильнее ставить задачи на основе управления рисками: «применить методы статического и динамического анализа для выявления наиболее критичных классов уязвимостей с доведением уровня ложных срабатываний ниже установленного порога».
Выбора и оценки инструментов. Не существует «самого лучшего» анализатора. Инструменты делают различные приближения и жертвуют либо полнотой (не находят все уязвимости), либо точностью (выдают много ложных срабатываний). Оценка инструмента должна включать понимание, какие классы задач он решает и на каких компромиссах основан его алгоритм.
Интерпретации результатов. Отчёт инструмента, это не истина в последней инстанции, а гипотеза, сгенерированная в рамках его вычислительных возможностей. Специалист по безопасности должен уметь верифицировать эти гипотезы вручную. Большое количество предупреждений — не всегда признак плохого кода, это может быть признаком того, что код сложен для формального анализа.
Проектирования безопасных систем. Знание о том, что проверка некоторых свойств чрезвычайно сложна, должно влиять на архитектуру. Можно сознательно проектировать компоненты так, чтобы критические утверждения о безопасности были доказуемы более простыми средствами. Например, выносить сложную логику в изолированные модули с чёткими и проверяемыми интерфейсами.

Что делать с непреодолимой сложностью?

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

Ограничение области анализа. Вместо всей программы анализируют критическое ядро или отдельные модули. Вместо полной верификации доказывают отдельные инварианты (например, «после вызова этой функции указатель всегда инициализирован»).
Использование спецификаций и аннотаций. Программист помогает анализатору, явно указывая пред- и постусловия функций, инварианты циклов, диапазоны значений. Это сужает пространство поиска для инструмента. Языки, такие как Rust, со своей системой владения, формально исключают целые классы ошибок (гонки данных, использование после освобождения) на уровне конструкции языка, что снижает сложность последующего анализа.
Комбинация методов. Статический анализ находит потенциальные точки, динамический анализ (фаззинг) пытается их эксплуатировать, ручной аудит фокусируется на наиболее подозрительных местах. Ни один метод не даёт гарантии, но их комбинация значительно снижает риск.
Принятие неполноты. Это осознанный выбор. Цель — не найти все уязвимости, а сделать атаку настолько дорогой и сложной, чтобы она перестала быть практичной. Повышение сложности для атакующего часто является более достижимой целью, чем достижение полной гарантии для защищающегося.

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