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

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

![1048_how_static_analysis_works_ru/image1.png](https://import.viva64.com/docx/blog/1048_how_static_analysis_works_ru/image1.png)

С точки зрения пользователя, [статический анализатор кода](https://pvs-studio.ru/ru/blog/terms/0074/) работает следующим образом: на вход программист подаёт исходный код проекта, а на выходе получает отчёт\. Отчёт содержит предупреждения, указывающие на фрагменты кода, которые с большой вероятностью содержат ошибки или не удовлетворяют стандартам кодирования\. Выглядит просто, но внутри анализаторы скрывают много и интересного, и хитрого\. Давайте заглянем за кулисы\.

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

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

1. Синтаксический и семантический анализ кода;
1. Сопоставления с шаблоном \(pattern\-based analysis\);
1. Анализ потоков данных \([data\-flow analysis](https://pvs-studio.ru/ru/blog/terms/7004/)\);
1. Символьное выполнение \(symbolic execution\);
1. Выявление уязвимых компонентов \(SCA, software composition analysis\);
1. Аннотирование функций;
1. Межпроцедурный и межмодульный анализ;
1. Taint\-анализ \(taint checking\)\.

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

Сбор информации об исходном коде и его разбор является важным предварительным шагом для полноценного анализа\. Старые анализаторы, называемые ещё иногда "линтерами", могли обойтись без этого шага и работали по принципу, близкому к поиску фрагмента текста по регулярным выражениям\. Это тупиковый подход, так как с его помощью можно обнаружить только очень узкий спектр ошибок\. Подробнее недостатки этого подхода разобраны в статье "[Статический анализ и регулярные выражения](https://pvs-studio.ru/ru/blog/posts/cpp/0087/)"\.

Современные анализаторы выполняют [синтаксический анализ](https://pvs-studio.ru/ru/blog/terms/0016/) \(парсинг\) кода и строят [дерево разбора](https://pvs-studio.ru/ru/blog/terms/0039/) или [абстрактное синтаксическое дерево](https://pvs-studio.ru/ru/blog/terms/0004/)\. Анализатор выводит \(раскрывает\) типы переменных, собирает информацию о классах и другую полезную информацию\. После этого анализатор начинает обход синтаксического дерева с целью выявления ошибок\. При этом он использует дополнительную собранную информацию, такую как типы переменных и размеры классов\.

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

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

Если переменная _ch_ имеет тип _int_, то код корректен\. Если переменная _ch_ имеет тип _char_, то символ со значением 0xFF \(255\) превращается в \-1 и интерпретируется точно так же, как и конец файла \(_EOF_\)\. [Здесь](https://pvs-studio.ru/ru/docs/warnings/v739/) можно ознакомиться подробнее с подобным паттерном ошибки\.

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

Это обнаружение известных паттернов ошибок, которые укладываются в определённый шаблон\. Простой пример — лишняя точка с запятой после оператора _for_:

```cpp
for (int i = 0; i < n; i++);
{
  foo();
}
```

Сопоставление происходит на уровне синтаксического дерева, что имеет ряд преимуществ над регулярными выражениями\. Работая с деревьями, достаточно просто понять, что _A < B_ и _B \> A_ — это одно и тоже, и найти ошибку в следующем коде:

```cpp
if (A < B) { .... }
else if (B > A) { .... }
```

Второе условие всегда ложно, так как на самом деле дублирует первое\. Это классический паттерн опечатки \([примеры](https://pvs-studio.ru/ru/blog/examples/v517/) в реальных приложениях\)\. 

Если искать повторяющиеся условия регулярными выражениями, это станет крайне непростым делом, так как придётся рассматривать множество вариантов, как может проявить себя этот паттерн ошибки:

```cpp
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) ....
```

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

```cpp
if ((A = get()) < B) ....
else if ((A = get()) < B) .... // предупреждение выдавать не надо
```

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

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

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

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

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

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

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

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

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

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

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

Допустим, анализатор не может выяснить, какие значения возвращает функция _foo_\. Однако поскольку переменные _A_ и _B_ равны, то выражение _A \- B_ равно 0\. Зная это, анализатор предупредит о делении на 0\.

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

Все рассматриваемые здесь технологии анализа кода позволяют [выявлять потенциальные уязвимости](https://pvs-studio.ru/ru/blog/terms/6441/), так как по сути это те же самые ошибки в коде\. Однако отдельно стоит выделить [Software Composition Analysis](https://pvs-studio.ru/ru/blog/posts/csharp/0876/)\.

В программных проектах используются сторонние компоненты, которые могут содержать уязвимости\. Соответственно, само приложение также может быть уязвимо к атакам злоумышленников\.

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

Важно понимать, что данный подход позволяет выявить только известные уязвимости, но не [уязвимости нулевого дня](https://pvs-studio.ru/ru/blog/terms/6478/)\. Такой подход отчасти напоминает принцип работы антивирусов, использующих базы, где хранятся сигнатуры уже известных вирусов\.

### Аннотирование функций

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

```cpp
if (memcmp(A, A, size) == 0) // Нет смысла сравнивать буфер сам с собой.
{
  malloc(N * sizeof(float)); // Странно не сохранить адрес выделенного буфера
}
```

Аннотирование функций бывает трёх типов:

1. Информация о функциях хранится в самих анализаторах кода и заложена их создателями; 
1. Информация о функциях, заданная пользователями;
1. Информация о функциях, собираемая самим анализатором на основании устройства этих функций\.

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

Если известно, как одна функцию вызывает другую, то можно выявить, например, такую ошибку:

```cpp
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\-анализ](https://pvs-studio.ru/ru/blog/terms/6496/) – это технология, позволяющая отслеживать распространение непроверенных внешних данных по программе во время её работы\. Попадание таких данных в некоторые ключевые точки может приводить к возникновению различных уязвимостей, среди которых [SQL injection](https://pvs-studio.ru/ru/blog/terms/6507/), [XSS](https://pvs-studio.ru/ru/blog/terms/6462/), [path traversal](https://pvs-studio.ru/ru/blog/terms/6470/) и другие\.

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

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

Если вам интересно, как описанные технологии применятся на практике, то предлагаем вашему вниманию статью "[Технологии статического анализа кода PVS\-Studio](https://pvs-studio.ru/ru/blog/posts/0908/)"\. Часть деталей реализации также раскрывается в следующих публикациях:

1. [Анализ потока данных PVS\-Studio распутывает всё больше связанных переменных](https://pvs-studio.ru/ru/blog/posts/csharp/0976/)\.
1. Межмодульный анализ C и C\+\+ проектов в деталях\. [Часть 1](https://pvs-studio.ru/ru/blog/posts/cpp/0963/)\. [Часть 2](https://pvs-studio.ru/ru/blog/posts/cpp/0965/)\.
1. [Эволюция PVS\-Studio: анализ потока данных для связанных переменных](https://pvs-studio.ru/ru/blog/posts/csharp/0942/)\.
1. [Под капотом PVS\-Studio для Java: разработка диагностик](https://pvs-studio.ru/ru/blog/posts/java/0752/)\.
1. [Как забраться на дерево](https://pvs-studio.ru/ru/blog/posts/cpp/0735/)\.
1. [Зачем PVS\-Studio использует анализ потока данных](https://pvs-studio.ru/ru/blog/posts/cpp/0803/)\.

## Ограничения статического анализа кода

Все статические анализаторы кода имеют две недостатка:

1. [Ложноположительные срабатывания статического анализатора кода](https://pvs-studio.ru/ru/blog/terms/6461/)\. Ошибки нет, но анализатор выдаёт предупреждение\.
1. [Отсутствие срабатываний статического анализатора кода](https://pvs-studio.ru/ru/blog/terms/6460/)\.

Эти ограничения связаны со следующими причинами:

1. У статических анализаторов отсутствует высокоуровневая информация о том, как на самом деле должна работать программа\.
1. Недостаточное количество вычислительных ресурсов\. Как следствие, необходимо идти на компромисс между точностью анализа и временам работы\.
1. "[Проблема остановки](https://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%BE%D0%B1%D0%BB%D0%B5%D0%BC%D0%B0_%D0%BE%D1%81%D1%82%D0%B0%D0%BD%D0%BE%D0%B2%D0%BA%D0%B8)", неразрешимая на машине Тьюринга\.

Более подробно всё это разбирается в статье "[Что нельзя найти с помощью статического анализа](https://pvs-studio.ru/ru/blog/posts/1037/)"\.

## Исключения для предотвращения ложных срабатываний

Как уже было сказано, все статические анализаторы кода подвержены [ложноположительным срабатываниям](https://pvs-studio.ru/ru/blog/terms/6461/)\. Поэтому перед разработчиками анализаторов стоит не только задача выдать как можно больше полезных сообщений, но и сократить количество бесполезных\. 

Для этого в реализации диагностик, как правило, прописан целый ряд исключений\. Рассмотрим пример присваивания переменной самой себе:

```cpp
variable = variable;
```

Это хорошая диагностика, с помощью которой можно найти много реальных ошибок: [примеры из коллекции PVS\-Studio](https://pvs-studio.ru/ru/blog/examples/v570/)\.

Кажется, что искать такую ошибку очень просто, и даже регулярные выражения бы справились\. Однако есть нюансы\. Например, в том же PVS\-Studio в этой диагностике около 10 исключений\. Рассмотрим парочку из них\.

```cpp
if (foo())
  x = x;
else
  x = -x;
```

Этот код избыточен, но в нём нет ошибки\! Задумка программиста очевидна: если функция вернула _false_, то поменять знак переменной\. Автор кода не будет рад, если увидит предупреждение\. Он специально написал код именно так, чтобы он был максимально понятен\. Соответственно, полезно распознать такой паттерн программирования и не выдавать предупреждение\.

Другой пример:

```cpp
#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_ не объявлен, то последняя строчка будет раскрыта препроцессором в:

```cpp
cffile.cbFile = cffile.cbFile;
```

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

Если вас заинтересовала эта глава, то предлагаем вашему вниманию статью "[Как и почему статические анализаторы борются с ложными срабатываниями](https://pvs-studio.ru/ru/blog/posts/cpp/0488/)"\.

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

1. [Использование машинного обучения в статическом анализе исходного кода программ](https://pvs-studio.ru/ru/blog/posts/0706/)\.
1. [Зачем нужен динамический анализ кода, если есть статический?](https://pvs-studio.ru/ru/blog/posts/0643/)
1. [Создание статического анализатора для C\# на основе Roslyn API](https://pvs-studio.ru/ru/blog/posts/csharp/0867/)\.
1. [Под капотом SAST: как инструменты анализа кода ищут дефекты безопасности](https://pvs-studio.ru/ru/blog/posts/cpp/1028/)\.