Хабрахабр

О статическом анализе начистоту

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

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

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

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

Рассмотрим, как обычно устроен статический анализатор. Существует множество платных и бесплатных инструментов, которые заявляют поиск уязвимостей в приложениях, написанных на разных языках программирования. Конечно, инструменты могут отличаться по дружелюбности интерфейса, по набору функциональности, по набору плагинов к разным системам и удобству использования API. Дальше речь пойдет именно о ядре анализатора, об алгоритмах. Наверное, это тема для отдельной статьи.

Промежуточное представление

В схеме работы статического анализатора можно выделить три основных шага.

  1. Построение промежуточного представления (промежуточное представление также называют внутренним представлением или моделью кода).
  2. Применение алгоритмов статического анализа, в результате работы которых модель кода дополняется новой информацией.
  3. Применение правил поиска уязвимостей к дополненной модели кода.

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

image

Лексический анализ разбивает текст программы на минимальные смысловые элементы, на выходе получая поток лексем. Аналогично компиляторам, лексический и синтаксический анализ применяются для построения внутреннего представления, чаще всего — дерева разбора (AST, Abstract Syntax Tree). В результате синтаксического анализа происходит построение дерева разбора – структуры, которая моделирует исходный текст программы. Синтаксический анализ проверяет, что поток лексем соответствует грамматике языка программирования, то есть полученный поток лексем является верным с точки зрения языка. Далее применяется семантический анализ, он проверяет выполнение более сложных условий, например, соответствие типов данных в инструкциях присваивания.

Также из дерева разбора можно получить другие модели. Дерево разбора можно использовать как внутреннее представление. Обычно CFG является основной моделью для алгоритмов статического анализа. Например, можно перевести его в трехадресный код, по которому, в свою очередь, строится граф потока управления (CFG).

image

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

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

Анализ потока данных

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

Если необходимо определить тип переменной, то можно говорить о задаче распространения типов (type propagation). Например, если необходимо определить, является ли выражение константой, а также значение этой константы, то решается задача распространения констант (constant propagation). Существует множество других задач анализа потока данных, которые могут использоваться в статическом анализаторе. Если необходимо понять, какие переменные могут указывать на определенную область памяти (хранить одни и те же данные), то речь идет о задаче анализа синонимов (alias analysis). Как и этапы построения модели кода, данные задачи также используются в компиляторах.

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

Для постановки конкретной задачи, помимо определения искомой информации, нужно определить правила изменения этой информации при прохождении данных по инструкциям в CFG. Расскажем подробнее про решение задачи внутрипроцедурного анализа потока данных. Напомним, что узлами в CFG являются базовые блоки – наборы инструкций, выполнение которых происходит всегда последовательно, а дугами обозначается возможная передача управления между базовыми блоками.

Для каждой инструкции $S$ определяются множества:

Целью анализа потока данных является определение множеств $in(S)$ и $out(S)$ для каждой инструкции $S$ программы. Основная система уравнений, с помощью которой решаются задачи анализа потока данных, определяется следующим соотношением (уравнения потока данных):

$out(S) = (in(S)−kill(S)) ∪ gen(S),$

$in(S) = ∪_i out(S_i).$

Может использоваться операция объединения, пересечения и некоторые другие. Второе соотношение формулирует правила, по которым информация «объединяется» в точках слияния дуг CFG ($S_i$ – предшественники $S$ в CFG).

Функции $gen$ и $kill$ рассматриваются как монотонные отображения на решётках (функции потока). Искомая информация (множество значений введенных выше функций) формализуется как алгебраическая решетка. Для уравнений потока данных решением является неподвижная точка этих отображений.

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

Межпроцедурный анализ

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

В точке вызова функции мы осуществляем встраивание вызываемой функции, тем самым сводим задачу межпроцедурного анализа к задаче внутрипроцедурного анализа. Встраивание (inline) функций. Такой метод легко реализуем, однако на практике при его применении быстро достигается комбинаторный взрыв.

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

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

Он основан на построении summary для каждой функции: правил, по которым преобразуется информация о данных при применении данной функции в зависимости от различных значений входных аргументов. Построение информации о функциях (function summary). Наиболее применимый алгоритм межпроцедурного анализа. Отдельной сложностью здесь является определение порядка обхода функций, так как при внутрипроцедурном анализе для всех вызываемых функций уже должны быть построены summary. Готовые summary используются при внутрипроцедурном анализе функций. Обычно создаются специальные итеративные алгоритмы обхода графа вызовов (call graph).

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

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

Taint-анализ

Отдельно стоит остановиться на одной из задач анализа потока данных — taint-анализе. Taint-анализ позволяет распространить по программе флаги. Данная задача является ключевой для информационной безопасности, так как именно с помощью нее обнаруживаются уязвимости, связанные с внедрением данных (внедрения в SQL, межсайтовый скриптинг, открытые перенаправления, подделка файлового пути и так далее), а также с утечкой конфиденциальных данных (запись пароля в журналы событий, небезопасная передача данных).

Пусть мы хотим отследить n флагов – <img src="https://habrastorage.org/getpro/habr/formulas/508/c04/793/508c047939e2c4cc62b2707775951625.svg" alt="$f_1, f_2, ... Попробуем смоделировать задачу. Множеством информации здесь будет множество подмножеств $\$, так как для каждой переменной в каждой точке программы мы хотим определить ее флаги. , f_n$" data-tex="inline"/>.

В данном случае функции потока могут определяться следующими соображениями. Далее мы должны определить функции потока.

  • Задано множество правил, в которых определены конструкции, приводящие к появлению или изменению набора флагов.
  • Операция присваивания перебрасывает флаги из правой части в левую.
  • Любая неизвестная для множеств правил операция объединяет флаги со всех операндов и итоговое множество флагов добавляется к результатам операции.

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

Такая уязвимость возникает, когда непроверенные данные от пользователя попадают в методы работы с базой данных. Например, необходимо обнаруживать уязвимости типа «Внедрение в SQL» (SQL Injection). Обычно в базе правил анализатора задаются правила постановки флага taint. Необходимо определить, что данные поступили от пользователя, и добавить таким данным флаг taint. Например, поставить флаг возвращаемому значению метода getParameter() класса Request.

В анализаторе задается множество функций, которые снимают флаги. Далее необходимо распространить флаг по всей анализируемой программе с помощью taint-анализа, учитывая, что данные могут быть валидированы и флаг может исчезнуть на одном из путей исполнения. Или функция привязки переменной к SQL-выражению снимает флаг о внедрении в SQL. Например, функция валидации данных от html-тегов может снимать флаг для уязвимости типа «Межсайтовый скриптинг» (XSS).

Правила поиска уязвимостей

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

Возвращаясь к примеру SQL-инъекции, мы проверим, что переменные с флагом taint не попадают в функции запроса к базе данных. Например, можно применить правило поиска уязвимости, которое будет определять вызов метода с параметром, у которого есть флаг taint.

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

Другие подходы

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

Выводы

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

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

Однако, эти минусы неизбежны, исходя из специфики алгоритмов. Минусами статического анализа является неизбежное наличие ложных срабатываний, потребление ресурсов и длительное время сканирований на больших объемах кода. Как мы увидели, быстрый анализатор никогда не найдет реальную уязвимость типа SQL-инъекции и подобных.

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

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть