Статический vs динамический анализ

16.04.2010Andrew PetukhovОставьте комментарийGo to comments

Так получилось, что в течение буквально двух недель я натолкнулся на несколько упоминаний статического анализа в контексте поиска уязвимостей веб-приложений. Некоторые из этих суждений я немедленно хотел уточнить/поправить. Это навело меня на мысль, что хорошо было бы рассказать «на пальцах», что есть статический и динамический анализ, и как это все можно применить к анализу безопасности веб-приложений.
Итак, эту серию постов я начну с рассказа о том, что же вообще из себя представляет статический и динамический анализ.

Начнем с того, что цель и статического и динамического анализа — выявление интересующих нас свойств программы. Примерами таких свойств могут быть:
— наихудшее время выполнения программы (для систем реального времени)
— наиболее часто исполняемые блоки (в т.ч. SQL-запросы, системные вызовы) программы
— наличие в программе ошибок работы с памятью (разыменование null-указателей, запись в освобожденную память и т.д.)
— наличие в программе уязвимостей (да-да, уязвимость — это свойство программы)
При статическом анализе мы проверяем свойства программы без её выполнения, а при динамическом — во время выполнения. Какой из этих анализов выбрать — тоже зависит от наших целей, и об этом в самом конце.

Отлично. Пусть мы решили, какое свойство мы хотели бы проверять. Следующий шаг — формализация интересующего нас свойства. Возникнет справедливый вопрос: а в каких терминах формализовывать-то? Очевидно же, что словесное определение не очень подходит:)
Для того, чтобы выбрать, в каких терминах мы можем выражать интересующие нас свойства, надо понять, какие вообще бывают представления у программы («огласите весь список, пжлста!» (с)).
Самые очевидные представления программ — это непосредственно исходный код, байт-код и бинарный код. В каких терминах мы сможем задавать и искать свойства? На ум приходят регулярные выражения и прочие механизмы для поиска шаблонов.
[Anti Virus Vendor Defensive Mode On] По сути, базовый антивирус — это ни что иное, как статический анализатор [Anti Virus Vendor Defensive Mode Off]
Ну и применение grep’а тоже можно называть статическим анализом:)
Еще одно возможное представление программы — это состояния программы после каждого её оператора. Состояние программы — это набор переменных, доступных в данном месте программы, плюс для каждой переменной множество её возможных значений (обычно значения переменных зависят от входных данных программы). Состояние программы меняется в результате выполнения операторов: меняется множество доступных переменных (при входе-выходе из функций), меняются возможные значения переменных¹.
Опять зададимся вопросом, в каких терминах мы можем задавать и искать свойства в таком представлении? Понятно, что выразительных возможностей у нас уже поболе: мы уже можем проверять логические предикаты над значениями тех или иных переменных в заданных точках программы. Например, а во всех ли вычислениях квадратного корня sqrt в качестве аргумента передается неотрицательное число? Или более полезное: а во всех ли вызовах echo был заэкранирован JavaScript²?

И последнее представление программы, о котором я бы хотел рассказать — это граф зависимостей программы, или System dependence graph. В этом графе отражается поток управления программы и зависимости по данным. Если «на пальцах», то поток управления показывает, какие операторы могут следовать за данным. Например, для оператора в линейном блока — это следующий за ним оператор, для ветвления if — это либо первый оператор в «положительной» ветви, либо первый оператор в else-ветви, для оператора цикла while — это либо первый оператор тела цикла, либо первый оператор сразу после цикла (условие входа в цикл может не сработать) и т.д. Зависимость же по данным между операторами возникает, когда один оператор при своем исполнении использует значение переменной, выработанное другим оператором.
Приведем пример графа зависимостей в программе. Рассмотрим в качестве примера программу (к слову, уязвимую) на PHP, которая реализует перелистывание страниц в архиве новостной ленты:
S1: $skip = $_GET["skip"];
S2: if ($skip < 0)
S3: $skip = 0;
S4: $QueryOffset = $skip. ", 10";
S5: mysql_connect();
S6: mysql_select_db("myDB");
S7: $request = "SELECT fld_Text FROM news LIMIT ".$QueryOffset;
S8: $result = mysql_query($request);

Граф зависимостей для этой программы представлен на рисунке ниже:
Снова зададимся вопросом, в каких терминах мы можем задавать и искать свойства в таком представлении? Ну конечно, в терминах путей в графах. Например, можно посмотреть, а на всех ли путях от получения пользовательских данных из HTTP-запроса до их использования в, например, функциях mysql_query, встречается заданная процедура фильтрации, например, addslashes?³
Тут надо заметить, что в динамическом анализе мы получим зависимости по данным только для конкретного пути исполнения программы (часто это называется динамическим срезом или слайсом).

Итак, мы определились с целью анализа, мы сформулировали наше свойство в терминах некоторого представления программы. Осталось выбрать тип анализа — статический или динамический.
Если программу нельзя запустить (программа находится на раннем этапе разработки; платформа, для которой написана программа, нам не доступна — например, дорогие контроллеры, авионика, ПО для новых мобильных телефонов, не поступивших в продажу, и т.д.) — у нас нет выбора, используем статический анализ.
Если нам надо проверить свойство программы на конкретных входных данных — не надо городить огород — используем динамический анализ.
Пусть теперь нам надо убедиться в наличии или отсутствии некоторого свойства для всех возможных входных данных. Перебирать все возможные входные данные и запускать на них программу для динамического анализа — не вариант. В статическом же анализе мы видим все возможные пути выполнения. Есть одно но — в статическом анализе есть алгоритмические неразрешимые проблемы (см. Теорему Райса), из-за которых представления, которые мы строим, не являются точными (например, мы не можем быть на 100% уверены, есть ли зависимость между некоторыми данными или нет). При этом справедливо утверждение, что чем больше в языке динамизма (см. языки с динамической типизацией типа PHP, Python) и функциональных возможностей (например, лямбда-функции в Питоне), тем менее точное представление программы у нас получится. Из-за анализа интересующих нас свойств на неточных представлениях программы мы получаем ложные срабатывания. Это плата за полноту — анализ всех путей программы для всех возможных входных данных.

Есть интуитивно понятный способ показать, почему статический анализ не может быть 100% точным. Представим на секунду, что это не так, и мы имеем способ проверять, например, свойство завершимости программы со 100% точностью.
Тогда у нас появляется бесплатный способ проверки математических гипотез, для которых пока не найдено доказательств.
Например, рассмотрим задачу поиска нечетных совершенных чисел. Нечётных совершенных чисел до сих пор не обнаружено, однако не доказано и то, что их не существует. Моментально пишем программу
if (find_perfect_odd_number())
return 1;
и запускаем наш статический анализатор. По предположению он у нас выдаст, остановится ли программа или нет. Мы автоматом получаем ответ, мучавший ученых веками:))

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

Краткое резюме. И статический и динамический анализ позволяют проверять наличие или отсутствие интересующих нас свойств в программе. Свойства эти обычно формулируются в терминах предикатов над значениями переменных в заданных точках программы или в терминах свойств путей в графе зависимостей программы. Если нам нужны гарантии присутствия/отсутствия свойств — без статического анализа не обойтись (можно туда же добавить методы верификации, model-checking’а). Если нас интересует наличие/отсутствие свойств на самых частых путях выполнения программы (intended workflow), при этом мы хотим иметь точный ответ, чтобы не тратить время оператора на проверку корректности/ложности получаемых результатов (false postitives) — выбираем динамический анализ. Кстати, эти типы анализа можно совместить, а как — расскажу как-нибудь потом…

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

Note 1. При динамическом анализе у каждой переменной, очевидно, будет только одно возможное значение. То, что показывают продвинутые отладчики в хороших IDE во время трассировки — это и есть состояния программы.
Note 2. На самом деле предикаты задаются посложнее, приведенные формулировки выбраны для иллюстрации.
Note 3. Примерно так работает метод обнаружения уязвимостей, известный как taint propagation (aka Tainted Mode).