Мы используем куки, чтобы пользоваться сайтом было удобно.
Хорошо
to the top
close form

Заполните форму в два простых шага ниже:

Ваши контактные данные:

Шаг 1
Поздравляем! У вас есть промокод!

Тип желаемой лицензии:

Шаг 2
Team license
Enterprise license
** Нажимая на кнопку, вы даете согласие на обработку
своих персональных данных. См. Политику конфиденциальности
close form
Запросите информацию о ценах
Новая лицензия
Продление лицензии
--Выберите валюту--
USD
EUR
RUB
* Нажимая на кнопку, вы даете согласие на обработку
своих персональных данных. См. Политику конфиденциальности

close form
Бесплатная лицензия PVS‑Studio для специалистов Microsoft MVP
* Нажимая на кнопку, вы даете согласие на обработку
своих персональных данных. См. Политику конфиденциальности

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

close form
Мне интересно попробовать плагин на:
* Нажимая на кнопку, вы даете согласие на обработку
своих персональных данных. См. Политику конфиденциальности

close form
check circle
Ваше сообщение отправлено.

Мы ответим вам на


Если вы так и не получили ответ, пожалуйста, проверьте папку
Spam/Junk и нажмите на письме кнопку "Не спам".
Так Вы не пропустите ответы от нашей команды.

Вебинар: C++ ЛИНТЕРЫ — ХОРОШО, НО НЕДОСТАТОЧНО - 20.06

>
>
Как работает статический анализ?

Как работает статический анализ?

27 Апр 2023

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

1048_how_static_analysis_works_ru/image1.png

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

На чём основывается статический анализ кода

Рассмотрим 8 основных технологий, лежащих в основе работы современных статических анализаторов кода:

  • Синтаксический и семантический анализ кода;
  • Сопоставления с шаблоном (pattern-based analysis);
  • Анализ потоков данных (data-flow analysis);
  • Символьное выполнение (symbolic execution);
  • Выявление уязвимых компонентов (SCA, software composition analysis);
  • Аннотирование функций;
  • Межпроцедурный и межмодульный анализ;
  • Taint-анализ (taint checking).

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

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

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

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

while ((ch = getchar()) != EOF)

Если переменная ch имеет тип int, то код корректен. Если переменная ch имеет тип char, то символ со значением 0xFF (255) превращается в -1 и интерпретируется точно так же, как и конец файла (EOF). Здесь можно ознакомиться подробнее с подобным паттерном ошибки.

Сопоставления с шаблоном (pattern-based analysis)

Это обнаружение известных паттернов ошибок, которые укладываются в определённый шаблон. Простой пример — лишняя точка с запятой после оператора 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) .... // предупреждение выдавать не надо

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

Анализ потоков данных (data flow analysis)

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

  • конкретные значения (числа, строки);
  • диапазоны значений;
  • множество возможных значений.

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

  • Неинициализированный (нельзя разыменовывать и сравнивать с другим указателем);
  • Нулевой (нельзя разыменовывать);
  • Указывает на буфер памяти определённого размера (можно проверить выход за границу буфера);
  • Указывает на освобождённую память (нельзя разыменовывать, повторно освобождать);
  • Является копией другого указателя (впрочем, это уже скорее символьное выполнение, которое мы рассмотрим в следующем разделе);
  • И так далее.

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

float A[10];
for (size_t i = 0; i < sizeof(A); i++)
{
  // Известно, что значение переменной i лежит в пределах [0..39].
  A[i] = 1.0; // Будет выдано сообщение о выходе за границу массива.
}

Символьное выполнение (symbolic execution)

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

int A = foo();
int B = A;
int C = 100 / (A - B);

Допустим, анализатор не может выяснить, какие значения возвращает функция foo. Однако поскольку переменные A и B равны, то выражение A - B равно 0. Зная это, анализатор предупредит о делении на 0.

Выявление уязвимых компонентов (SCA, software composition analysis)

Все рассматриваемые здесь технологии анализа кода позволяют выявлять потенциальные уязвимости, так как по сути это те же самые ошибки в коде. Однако отдельно стоит выделить 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-анализ (taint checking)

Taint-анализ – это технология, позволяющая отслеживать распространение непроверенных внешних данных по программе во время её работы. Попадание таких данных в некоторые ключевые точки может приводить к возникновению различных уязвимостей, среди которых SQL injection, XSS, path traversal и другие.

Taint-анализ схож с анализом потоков данных. Однако здесь не ставится задача понять, какие собственно данные передаются. Предполагается, что если они поступили извне, то могут быть опасны. Задача анализатора — отследить, что эти данные попадут в приёмник без предварительной проверки и выдать предупреждение.

Устройство анализаторов кода на примере PVS-Studio

Если вам интересно, как описанные технологии применятся на практике, то предлагаем вашему вниманию статью "Технологии статического анализа кода 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;

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

Если вас заинтересовала эта глава, то предлагаем вашему вниманию статью "Как и почему статические анализаторы борются с ложными срабатываниями".

Дополнительные ссылки

Популярные статьи по теме


Комментарии (0)

Следующие комментарии next comments
close comment form