Обзорная статья о том, что лежит в основе работы статических анализаторов кода. В ней вы узнаете о таких технологиях, как сопоставление с шаблоном, анализ потока данных, символьное выполнение, taint-анализ и т.д.
С точки зрения пользователя, статический анализатор кода работает следующим образом: на вход программист подаёт исходный код проекта, а на выходе получает отчёт. Отчёт содержит предупреждения, указывающие на фрагменты кода, которые с большой вероятностью содержат ошибки или не удовлетворяют стандартам кодирования. Выглядит просто, но внутри анализаторы скрывают много и интересного, и хитрого. Давайте заглянем за кулисы.
Рассмотрим 8 основных технологий, лежащих в основе работы современных статических анализаторов кода:
Сбор информации об исходном коде и его разбор является важным предварительным шагом для полноценного анализа. Старые анализаторы, называемые ещё иногда "линтерами", могли обойтись без этого шага и работали по принципу, близкому к поиску фрагмента текста по регулярным выражениям. Это тупиковый подход, так как с его помощью можно обнаружить только очень узкий спектр ошибок. Подробнее недостатки этого подхода разобраны в статье "Статический анализ и регулярные выражения".
Современные анализаторы выполняют синтаксический анализ (парсинг) кода и строят дерево разбора или абстрактное синтаксическое дерево. Анализатор выводит (раскрывает) типы переменных, собирает информацию о классах и другую полезную информацию. После этого анализатор начинает обход синтаксического дерева с целью выявления ошибок. При этом он использует дополнительную собранную информацию, такую как типы переменных и размеры классов.
Не зная информации о типах, невозможно сказать, является следующая конструкция ошибочной или нет (здесь и далее примеры написаны на языке C):
while ((ch = getchar()) != EOF)Если переменная ch имеет тип int, то код корректен. Если переменная ch имеет тип char, то символ со значением 0xFF (255) превращается в -1 и интерпретируется точно так же, как и конец файла (EOF). Здесь можно ознакомиться подробнее с подобным паттерном ошибки.
Это обнаружение известных паттернов ошибок, которые укладываются в определённый шаблон. Простой пример — лишняя точка с запятой после оператора for:
for (int i = 0; i < n; i++);
{
foo();
}Сопоставление происходит на уровне синтаксического дерева, что имеет ряд преимуществ над регулярными выражениями. Работая с деревьями, достаточно просто понять, что A < B и B > A — это одно и тоже, и найти ошибку в следующем коде:
if (A < B) { .... }
else if (B > A) { .... }Второе условие всегда ложно, так как на самом деле дублирует первое. Это классический паттерн опечатки (примеры в реальных приложениях).
Если искать повторяющиеся условия регулярными выражениями, это станет крайне непростым делом, так как придётся рассматривать множество вариантов, как может проявить себя этот паттерн ошибки:
if (A < B) ....
else if (A < B) ....
if (A + 1 < B && C) ....
else if (1 + A < B && C) ....
if (A & B == 0) ....
else if (0 == B & A) ....На самом деле всё ещё сложнее. Статический анализатор должен учитывать дополнительную информацию. Например, что операторы не перегружены. Или что в условии происходит изменение переменных:
if ((A = get()) < B) ....
else if ((A = get()) < B) .... // предупреждение выдавать не надоТак что регулярные выражения здесь вообще не подходят.
Анализ потоков данных позволяет анализатору делать предположения о значениях переменных и выражений в различных частях исходного кода. Некоторые виды предполагаемых значений:
Бывают и более сложные виды данных, сопоставляемые с какой-то переменной. Например, анализатор может знать, что указатель находится в одном из следующих состояний:
Пример, где информация о возможных значениях переменной позволяет выявить выход за границу массива:
float A[10];
for (size_t i = 0; i < sizeof(A); i++)
{
// Известно, что значение переменной i лежит в пределах [0..39].
A[i] = 1.0; // Будет выдано сообщение о выходе за границу массива.
}Символьное выполнение схоже с анализом потоков данных, но анализатор ничего не знает о конкретных значениях переменных. Однако, решая уравнения, он может сделать некоторые выводы о результатах вычислений. Поясню это простейшим примером:
int A = foo();
int B = A;
int C = 100 / (A - B);Допустим, анализатор не может выяснить, какие значения возвращает функция foo. Однако поскольку переменные A и B равны, то выражение A - B равно 0. Зная это, анализатор предупредит о делении на 0.
Все рассматриваемые здесь технологии анализа кода позволяют выявлять потенциальные уязвимости, так как по сути это те же самые ошибки в коде. Однако отдельно стоит выделить Software Composition Analysis.
В программных проектах используются сторонние компоненты, которые могут содержать уязвимости. Соответственно, само приложение также может быть уязвимо к атакам злоумышленников.
Информация об уязвимостях в различных версиях компонентов агрегируется в открытых базах данных. Используя эти базы, статические анализаторы могут предупредить разработчиков, что они используют устаревшие компоненты, содержащие уязвимости.
Важно понимать, что данный подход позволяет выявить только известные уязвимости, но не уязвимости нулевого дня. Такой подход отчасти напоминает принцип работы антивирусов, использующих базы, где хранятся сигнатуры уже известных вирусов.
Аннотации предоставляют информацию, на основе которой анализатор обнаруживает некорректное использование функций. Примеры:
if (memcmp(A, A, size) == 0) // Нет смысла сравнивать буфер сам с собой.
{
malloc(N * sizeof(float)); // Странно не сохранить адрес выделенного буфера
}Аннотирование функций бывает трёх типов:
Если известно, как одна функцию вызывает другую, то можно выявить, например, такую ошибку:
void use(struct S *p)
{
p->a = 123;
}
struct S globalVar;
void foo(int x)
{
struct S *q = (x == 5) ? NULL : &globalVar;
use(q);
}Потенциальное разыменование нулевого указателя будет выявлено благодаря совместной работе алгоритма анализа потока данных и межпроцедурного анализа.
Анализ потока данных вычислит, что в функцию use может быть передан как нулевой, так и не нулевой указатель на глобальную переменную.
Благодаря межпроцедурному анализу эта информация будет использована для повторной проверки функции use. Здесь опять вступает в работу алгоритм анализа потока данных, который выявит, что может произойти разыменование нулевого указателя.
Что интересно, к выявлению этой ошибки можно подойти и другим путём: используя автоматическое аннотирование функций и межпроцедурный анализ.
Разбирая функцию use, анализатор сделает себе "пометку", что аргумент функции разыменовывается без предварительной проверки. Следовательно, далее он предупредит, что в функцию use нельзя передавать указатель, который может быть равен NULL.
Межмодульный анализ позволяет выявить ещё больше ошибок, так как позволяет анализировать совместную работу функций, расположенных в разных единицах трансляции.
Taint-анализ – это технология, позволяющая отслеживать распространение непроверенных внешних данных по программе во время её работы. Попадание таких данных в некоторые ключевые точки может приводить к возникновению различных уязвимостей, среди которых SQL injection, XSS, path traversal и другие.
Taint-анализ схож с анализом потоков данных. Однако здесь не ставится задача понять, какие собственно данные передаются. Предполагается, что если они поступили извне, то могут быть опасны. Задача анализатора — отследить, что эти данные попадут в приёмник без предварительной проверки и выдать предупреждение.
Если вам интересно, как описанные технологии применятся на практике, то предлагаем вашему вниманию статью "Технологии статического анализа кода PVS-Studio". Часть деталей реализации также раскрывается в следующих публикациях:
Все статические анализаторы кода имеют две недостатка:
Эти ограничения связаны со следующими причинами:
Более подробно всё это разбирается в статье "Что нельзя найти с помощью статического анализа".
Как уже было сказано, все статические анализаторы кода подвержены ложноположительным срабатываниям. Поэтому перед разработчиками анализаторов стоит не только задача выдать как можно больше полезных сообщений, но и сократить количество бесполезных.
Для этого в реализации диагностик, как правило, прописан целый ряд исключений. Рассмотрим пример присваивания переменной самой себе:
variable = variable;Это хорошая диагностика, с помощью которой можно найти много реальных ошибок: примеры из коллекции PVS-Studio.
Кажется, что искать такую ошибку очень просто, и даже регулярные выражения бы справились. Однако есть нюансы. Например, в том же PVS-Studio в этой диагностике около 10 исключений. Рассмотрим парочку из них.
if (foo())
x = x;
else
x = -x;Этот код избыточен, но в нём нет ошибки! Задумка программиста очевидна: если функция вернула false, то поменять знак переменной. Автор кода не будет рад, если увидит предупреждение. Он специально написал код именно так, чтобы он был максимально понятен. Соответственно, полезно распознать такой паттерн программирования и не выдавать предупреждение.
Другой пример:
#ifdef WORDS_BIGENDIAN
#define fci_endian_ulong(x) RtlUlongByteSwap(x)
#else
#define fci_endian_ulong(x) (x)
#endif
....
cffile.cbFile = fci_endian_ulong(cffile.cbFile);Если макрос WORDS_BIGENDIAN не объявлен, то последняя строчка будет раскрыта препроцессором в:
cffile.cbFile = cffile.cbFile;Переменная присваивается сама себе, но выдавать предупреждение не надо, так как макрос мог раскрыться в вызов функции.
Если вас заинтересовала эта глава, то предлагаем вашему вниманию статью "Как и почему статические анализаторы борются с ложными срабатываниями".