Компоненты Svace

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

Используемые анализы можно разделить на следующие группы:

Схема анализа

Общая схема анализа изображена ниже.

На вход анализатор получает скрипт сборки и исходный код (для языка python). Для анализа компилируемых языков специальная утилита build-capture запускает процесс сборки и перехватывает вызовы компиляторов, ассемблеров, компоновщиков и других утилит. Для компилируемых файлов запускаются наши модифицированные версии компиляторов. Для анализа языка python используется исходный код.

Для C/C++ используется компилятор Clang, который имеет встроенный анализатор CSA (Clang Static Analyzer). Мы расширили этот анализатор своими детекторами: к примерно сотни детекторов мы добавили ещё около двухсот своих. Кроме поиска ошибок, Clang генерирует промежуточное представление в формате llvm, которое преобразовывается в промежуточное представление svace ir. Последнее подаётся на вход нашему основному анализатору SvEng (Svace Engine).

Для других языков каждый компилятор генерирует два представления:

Последнее представление УАСД унифицировано для всех языков и передаётся на вход анализатору UAST.

Для языка Go промежуточное представление генерируется утилитой ssadump – инструментом для построения SSA-представления Go программ.

Для программ на языке Java мы также запускаем популярный анализатор SpotBugs. Для него мы реализовали интеграцию предупреждений в наш формат.

Кроме этого Svace поддерживает анализ программ на языке C#. Этот анализ производится компонентом cscc (SharpChecker), выполненным на базе компилятора Roslyn. Для поиска ошибок SharpChecker использует все виды статического анализа, аналогичные SvEng: поиск шаблонов в АСТ-деревьях, анализ потоков данных, межпроцедурное символьное выполнение с объединением состояний и использованием резюме методов, статический анализ помеченных данных для ошибок безопасности.

Пять компонентов – SvEng, UAST, SpotBugs, CSA и cscc– выдают предупреждения о найденных ошибках как результат своей работы. Далее рассмотрим, какие анализы при этом используются, их основные достоинства и ограничения.

Анализаторы на основе абстрактного синтаксического дерева

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

Например, для выражения x > x будет построено следующее АСД:

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

АСД-анализаторы для C/C++ реализованы в CSA. Для остальных языков используется UAST. UAST-анализатор также получает на вход АСД. Но это дерево содержит унифицированные узлы сразу для множества языков.

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

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

Компонент SvEng реализует межпроцедурный анализ на основе резюме. Такой анализ строит граф вызовов программы, после чего проводит анализ по графу вызовов “снизу-вверх”. Т.е. вначале анализируются листья графа вызовов – функции, которые не вызывают другие функции. Затем анализируются функции, которые вызывают только проанализированные функции. Последними анализируются функции верхнего уровня, которые не вызываются нигде в программе.

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

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

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

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

Рассмотрим небольшой фрагмент кода:

void setOneIf(int*p, bool flag) {
  if (flag)
    *p = 1;
}

void foo() {
  int *q = 0;
  setOneIf (q, true);
}

void bar() {
  int *q = 0;
  setOneIf (q, false);
}

void baz() {
  int x;
  int *q = &x;
  setOneIf (q, true);
}

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

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

void nocontext(bool m) {
  int *q = 0;
  setOneIf (q, m);
}

Тогда анализ не будет иметь информацию о значениях параметра m функции nocontext. Поэтому здесь также будет выдано предупреждение о разыменовании указателя q. При этом может быть так, что параметр m имеет только ложное значение в анализируемом проекте. На первый взгляд, такое поведение кажется нелогичным. Но в данном случае функция написана недостаточно хорошо. Она имеет параметр булева типа и передаёт нулевой указатель в функцию, которая может его разыменовать. И если этот параметр окажется истинным, то произойдёт ошибка. На наш взгляд, правильным будет исправить эту функцию так, чтобы она проверяла свой аргумент либо не передавала нулевой указатель.

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

Важная особенность реализованного анализа – его межмодульность. Т.е. анализатор учитывает связи между функциями в разных модулях. Определение модуля зависит от языка, в C/C++ это исходные файлы, компилируемые в одну единицу трансляции. В Golang модулем является пакет. В Java и Kotlin – class-файлы. Благодаря межмодульности Svace может находить ошибки, путь возникновения которых проходит через несколько модулей. Но вместе с этим межмодульность имеет свои недостатки. И главные из них – это сложность реализации инкрементального анализа, а также требования значительных ресурсов (как процессора, так и памяти) для анализа.

Данный анализ реализован в компоненте SvEng.

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

Только лишь одного анализа на основе резюме недостаточно для поиска всех видов ошибок. Одним из видов анализа является статистический анализ. Его идея заключается в поиске нетипичных шаблонов в коде. Например, если результат некоторой функции в 98% случаев проверяется на ноль, и лишь в 2% не проверяется, то, возможно, в этих 2% просто забыли добавить такую проверку.

Статистический анализ встроен в анализ на основе резюме по следующей схеме:

Анализ специальных функций

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

Анализы на основе символьного выполнения

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

В Svace символьное выполнение используется сразу тремя компонентами: SvEng, cscc и CSA.

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

Анализ на основе символьного выполнения используется компонентом статического анализатора CSA (Clang Static Analyzer), модифицированная версия которого распространяется вместе со Svace.

Анализатор в движке SvEng использует другой подход. Вместо выбора путей для анализа в точках объединения путей объединяются свойства анализа для всех возможных путей. Для анализируемых свойств SvEng использует формулы, описывающие возможные пути. При возникновении подозрения на ошибку, SvEng комбинирует формулы доступных свойств в условие ошибки, и запускает smt-решатель, чтобы проверить, что формула имеет решение. Это означает, что в функции существует путь, по которому может произойти ошибка.

Например, для ошибки разыменования нулевого указателя, формулой ошибки будет конъюнкция условия, что указатель имеет нулевое значение, условие того, что указатель будет разыменован, условие, что данная точка достижима, дополнительные условия описывающие функцию (взаимосвязь переменных, известные значения переменных). В данном случае условие, что указатель имеет нулевое значение – true, т.к. разыменование непосредственное. Более сложные условия используются, если разыменование происходит внутри вызываемой функцией. Благодаря такому подходу устраняется проблема экспоненциального роста количества путей. В программах без циклов анализатор гарантированно обойдёт все возможные пути. Но при этом при слиянии путей возможна потеря точности.

Анализатор языка C# cscc имеет другую реализацию, но использует тот же подход к символьному выполнению, как и SvEng.

Анализатор помеченных данных

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

В SharpChecker реализован статический межпроцедурный анализ помеченных данных на основе решения задачи IFDS (Interprocedural Finite Distributive Subset), а также различные расширения, улучшающие его масштабируемость, точность и полноту. С его помощью возможно обнаружение таких типов ошибок, как SQL Injection, утечки и внедрение данных, и другие ошибки безопасности в программах на языке С#. Истоки и стоки помеченных данных задаются в текстовых файлах в формате JSON, что позволяет пользователям самостоятельно редактировать существующие или создавать свои детекторы.

Поддерживаемые языки

Описанная схема позволяет находить множество возможных типов ошибок в программах, написанных на множестве языков программирования. В настоящий момент поддерживаются языки C, C++, Java, Kotlin, Go, C#, Python.

Алексей Бородин