22.12.25

денежная

Idea

Задачи ИКТ

Произвольный код

Information processing and transformation

Software/ IS

Рассмотрим произвольную программу P на одном из поддерживаемых языков. Определим семантическое свойство S(P): «существует исполнение P и входные данные x, при которых порождается уязвимый поток данных (например, неподготовленный SQL‑запрос с пользовательским вводом)». Требование заказчика к алгоритму Check(P): • если S(P) истинно, Check(P) обязан вернуть VULNERABLE; • если S(P) ложно, Check(P) обязан вернуть SAFE; • Check(P) всегда завершается за конечное время. Свойство S — нетривиальное семантическое свойство поведения программы, а не синтаксики исходника. Классические результаты теории вычислимости (в частности, теорема Риса) утверждают, что для любой нетривиальной семантической характеристики не существует универсального алгоритма, который корректно решает задачу для всех программ. Это напрямую бьёт в исходное требование: универсальный Check(P) в строгом смысле невозможен.

Фактически от нас ожидали решения класса задач, которые теоретически неразрешимы для произвольных программ. Мы можем: • жёстко ограничить поддерживаемые языки и паттерны кода; • допустить вероятностный характер выводов (эвристический режим); • опираться на комбинирование статического и динамического анализа. Но универсальный «оракул уязвимостей», который корректно отвечает SAFE/VULNERABLE для любой возможной программы, не может существовать. Именно это делает исходную задачу принципиально нерешаемой, а не просто «трудной в реализации».

Сергеев И.А.