Какое подмножество проблем не может охватить статический анализ?

Question

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

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

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

Может ли кто-нибудь дать простое объяснение с конкретными примерами того, где статический анализ дает сбой, и динамический анализ будет необходим?

Answer 1

Статический анализ никогда не может быть завершен для всех программ с заданным полным входным форматом Тьюринга (включая почти все языки программирования), так как в общем случае невозможно определить, выполняется ли когда-либо фрагмент кода или нет: вы не можете определить, останавливается ли код перед его остановкой. - т.е. завершает выполнение (если он входит в бесконечный цикл, то любая "проблема" за его пределами является фиктивной, поскольку она недостижима) - проблема, известная как проблема остановки.

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

Кроме того, стоит отметить, что некоторые системы исследования состояния по существу выполняют программу для каждого состояния (обычно останавливая новое исследование, если состояние стало эквивалентным) - однако, многие программы имеют нереально большие пространства входных состояний (рассмотрим любую программу, принимающую текстовые сообщения). вход!) что делает их практически невозможно полностью изучить все государства.