PVS-Studio предоставляет статические анализаторы для языков C, C++, C# и Java на платформах Windows, Linux и macOS. Несмотря на некоторые различия, накладываемые особенностями отдельных языков, в целом все перечисленные анализаторы используют общие технологии и подходы.
В составе PVS-Studio можно выделить 3 отдельных программных инструмента для статического анализа кода:
Перечисленные анализаторы реализуют алгоритмы и механизмы для проведения data-flow анализа (включая символьное выполнение, межпроцедурный анализ и межмодульный анализ), основанные на наших собственных разработках.
Рассмотрим подходы и технологии, на которых базируется работа статического анализатора кода PVS-Studio.
Вначале рассмотрим два термина, применяющихся в теории разработки компиляторов и статических анализаторов кода.
Абстрактное синтаксическое дерево (AST) — это конечное ориентированное дерево, в котором внутренние вершины соответствуют операторам языка программирования, а листья —операндам. Абстрактные деревья синтаксиса используются компиляторами и интерпретаторами как промежуточное представление между деревьями разбора и внутренним представлением кода. Преимущество AST — достаточная компактность (абстрактность) структуры, достигаемая за счёт отсутствия узлов для конструкций, не влияющих на семантику программы.
Основным преимуществом использования абстрактного синтаксического дерева, по сравнению с прямым анализом текста программ (исходного кода), является независимость построенных на его основе анализаторов от конкретного синтаксиса: имён, стиля написания кода, его форматирования и т.п.
Дерево разбора (Parse Tree, PT, DT). Результат грамматического анализа. Дерево разбора отличается от абстрактного синтаксического дерева наличием узлов для тех синтаксических правил, которые не влияют на семантику программы. Классическим примером таких узлов являются группирующие скобки, в то время как в AST группировка операндов явно задаётся структурой дерева.
Высокоуровнево можно говорить, что ядра всех анализаторов PVS-Studio для разных языков работают с абстрактным синтаксическим деревом (AST). Однако на практике всё немного сложнее. В некоторых случаях диагностики требуют информации о необязательных узлах или даже о количестве пробелов в начале строки. В этом случае анализ спускается на уровень дерева разбора и извлекает дополнительную информацию. Все используемые библиотеки (Roslyn, Spoon, VivaCore) предоставляют возможность получать информацию на уровне дерева разбора, и анализатор в ряде случаев этим пользуется.
Анализаторы PVS-Studio используют AST представление программы для поиска потенциальных дефектов методом сигнатурного анализа (сопоставление с шаблоном, pattern-based analysis). Это класс простых диагностических правил, которым для принятия решения об опасности кода достаточно сопоставить конструкцию, встретившуюся в коде, с заранее заданным шаблоном потенциальной ошибки. Данный подход к анализу достаточно точен, но позволяет находить только относительно простые дефекты - для более сложных диагностических правил PVS-Studio дополняет анализ AST другими методиками, которые мы рассмотрим чуть позже.
Следует отметить, что сигнатурный анализ — более высокоуровневая и эффективная технология, чем использование регулярных выражений. Регулярные выражения вообще не подходят для построения эффективного статического анализатора по множеству причин. Поясним это на простом примере. Допустим, требуется найти опечатки, когда выражение сравнивается само с собой. Это можно сделать регулярными выражениями для простейших случаев:
if (A + B == A + B)
if (V[i] == V[i])Однако, если ошибочные выражения записаны чуть по-другому, регулярные выражения бессильны. Вернее, их просто невозможно написать для всех случаев альтернативной записи:
if (A + B == B + A)
if (A + (B) == (B) + A)
if (V[i] == ((V[i])))
if (V[(i)] == (V[i]))В свою очередь, для сопоставления по шаблону, если используется AST, выявление подобных ошибок не является проблемой.
Примечание. В нашей коллекции ошибок вы можете посмотреть, как разнообразно могут выглядеть подобные дефекты, найденные с помощью диагностик V501 (C, C++), V3001 (C#), V6001 (Java).
Представление кода в виде абстрактного синтаксического дерева также является подготовкой к проведению следующего уровня анализа — построения семантической модели и вывода типов.
Все анализаторы PVS-Studio на основе построенного на предыдущем этапе представления кода в виде абстрактного синтаксического дерева проводят семантический анализ — построение полной семантической модели проверяемого кода.
Обобщённая семантическая модель представляет собой словарь соответствий семантических (смысловых) символов и элементов синтаксического представления этого же кода.
Каждый такой символ определяет семантику (смысл) соответствующей синтаксической конструкции языка. Эта семантика может быть неочевидна и невыводима из самого локального синтаксиса. В таком случае для выведения такой семантики требуется обращаться к другим частям синтаксического представления кода. Поясним это на примере фрагмента кода на языке C:
A = B(C);Не зная, что собой представляет B, невозможно сказать, какая перед нами конструкция языка. Это может быть как вызов функции, так и явное приведение типа (functional cast expression).
Семантическая модель, таким образом, позволяет анализировать семантику кода. Без неё пришлось бы постоянно совершать обход синтаксического представления этого кода, чтобы разрешить невыводимые из локального контекста семантические факты. Семантическая модель "запоминает" семантику по ходу разбора кода для дальнейшего её использования. Поясним на примере:
void B(int);
....
A = B(C);Встретив объявление функции B, анализатор запомнит, что символ B является именем функции с определёнными характеристиками. Встретив выражение A = B(C), анализатор сразу поймёт, что такое B, ему не нужно вновь обходить большой фрагмент AST.
На основе семантической модели анализаторы PVS-Studio получают возможность проводить вывод типов (type inference) у любой встречаемой синтаксической конструкции. Такими конструкциями могут быть идентификаторы переменных, выражения и так далее.
Информация о типах требуется большинству диагностик. На её основе делается предположение о потенциальных ошибках или наоборот — срабатывают исключения из правил.
Даже если мы говорим о диагностиках, основанных на шаблонах, многие из них учитывают типы. Например, в тех случаях, когда одного синтаксического представления недостаточно для принятия решения об опасности проверяемой конструкции.
Рассмотрим в качестве примера очень простую диагностику V772 для кода на языке C++:
void *ptr = new Example();
....
delete ptr;Вызов оператора delete для указателя типа (void *) приводит к неопределённому поведению. Сам по себе шаблон для поиска крайне прост: это любой вызов оператора delete. Можно сказать, это вырожденный случай шаблонной диагностики :). Однако, чтобы понять, найдена ошибка или нет, нужно знать тип операнда ptr.
Построение полной и корректной семантической модели требует непротиворечивости и, соответственно, собираемости (компилируемости) проверяемого кода. Компилируемость исходного кода является обязательным условием для полноценной и корректной работы всех анализаторов PVS-Studio. И хотя в них заложены механизмы отказоустойчивости при работе с некомпилируемым кодом, такой код может ухудшать точность работы диагностических правил.
Препроцессирование C и C++ кода — это процесс раскрытия в исходном коде директив компилятора и подстановка значений макросов. В частности, в результате работы препроцессора на месте директив #include происходит подстановка содержимого заголовочных файлов, пути до которых записаны в данной директиве. Директивы и макросы раскрываются в случае такой подстановки последовательно – так же, как и во всех раскрываемых директивой #include заголовочных файлах.
Препроцессирование является первым этапом работы компилятора — подготовкой единицы компиляции и её зависимостей к непосредственной трансляции исходного кода во внутреннее представление компилятора.
Раскрытие директив #include приводит к объединению исходного файла и всех используемых в нём заголовочных файлов в единый файл, часто называемый промежуточным (intermediate). По аналогии с компилятором, С и C++ анализатор PVS-Studio использует препроцессирование перед началом анализа.
Для препроцессирования проверяемого кода PVS-Studio пользуется тем же компилятором, который использовался для сборки (но в режиме препроцессора). PVS-Studio поддерживает работу с большим количеством препроцессоров, которые перечислены на странице продукта. Для корректной работы анализатора требуется использовать правильный препроцессор – такой же, который применяется при компиляции проверяемого кода. Это обусловлено тем, что выходной формат препроцессоров различных компиляторов отличается.
Перед началом анализа C и C++ кода PVS-Studio осуществляет запуск препроцессора для каждой единицы трансляции проверяемого кода. Помимо содержимого исходных файлов, на работу препроцессора также влияют параметры компиляции. PVS-Studio использует для препроцессирования параметры сборки, применяемые при компиляции проверяемого кода. Информацию о списке единиц трансляции, а также параметры компиляции PVS-Studio получает либо из сборочной системы проверяемого проекта, либо путём отслеживания (перехвата) вызовов компиляторов в процессе сборки проекта.
Работа анализатора PVS-Studio C и С++ основана на результате работы соответствующего препроцессора — исходный код не анализируется напрямую. Препроцессирование C и C++ кода за счёт раскрытия директив компилятора позволяет анализатору построить полную семантическую модель проверяемого кода.
Без тонкостей опять не обходится. Фразу "исходный код не анализируется напрямую" следует читать как "почти всегда исходный код не анализируется напрямую". Есть несколько диагностик, такие как V1040, которые обращаются напрямую к файлам с исходным кодом. Им нужна информация про директивы #include и макросы, которая теряется после препроцессирования.
Технология отслеживания (мониторинга) PVS-Studio позволяет перехватывать запуск процессов на уровне API операционной системы. Перехват запуска позволяет извлекать у процесса полную информацию о его работе, параметрах его запуска и рабочем окружении. Отслеживание запуска процессов PVS-Studio поддерживается на платформах Windows (реализовано через прямую работу с WinAPI) и Linux (реализовано с помощью стандартной системной утилиты strace).
C и C++ анализаторы PVS-Studio могут использовать отслеживание процессов компиляции как один из вариантов проведения анализа С++ кода. Как уже говорилось ранее, PVS-Studio имеет средства прямой интеграции с наиболее распространёнными сборочными системами для C и C++ проектов. Но экосистема данных языков весьма многообразна, и в ней существует большое количество сборочных систем (например, в embedded сегменте), интеграцию с которыми анализатор не поддерживает.
Хотя прямая низкоуровневая интеграция C++ анализатора PVS-Studio в такие системы возможна, она является достаточно трудоёмкой, так как требует передачи в анализатор параметров компиляции для каждой единицы трансляции — исходного C или C++ файла.
Использование системы отслеживания процессов компиляции PVS-Studio позволяет упростить и автоматизировать процесс передачи анализатору всей необходимой информации для проведения анализа. Система отслеживания собирает параметры компиляции у процессов, анализирует, модифицирует их (например, активируя режим препроцессирования у компилятора — анализатору нужно проведение только этого этапа) и передаёт непосредственно в C++ анализатор PVS-Studio.
Таким образом, система отслеживания запуска процессов позволяет реализовать в PVS-Studio универсальную систему проверки C и C++ проектов, не зависящую от используемой сборочной системы, легко настраиваемую и полностью учитывающую оригинальные параметры компиляции проверяемого кода.
См. также раздел документации "Система мониторинга компиляции в PVS-Studio".
Анализ потоков данных — это методика, позволяющая статическому анализатору делать предположения о значениях переменных и выражений в различных частях исходного кода. Под предполагаемыми значениями понимаются какие-то конкретные значения, диапазоны значений или множество возможных значений. Дополнительно собирается и обрабатывается информация о том, освобождена память по указателю или нет, каковы размеры массивов и так далее.
Предположения о значениях строятся на основе анализа движения значений переменных по графу выполнения программы (control-flow graph). В большинстве случаев анализатор не может знать точного значения переменной или выражения. Но он может делать предположения о диапазонах или множествах значений, которые данные выражения могут принимать в различных точках этого графа. Для этого учитываются прямые и косвенные ограничения, накладываемые на рассматриваемые выражения по ходу обхода графа выполнения.
Примечание. В некоторых наших статьях и докладах мы называем предполагаемые значения переменных "виртуальными".
Все анализаторы PVS-Studio используют data-flow анализ для уточнения работы своих диагностических правил. Это требуется в случаях, когда для принятия решения об опасности рассматриваемого кода недостаточно информации, доступной только из AST или семантической структуры этого кода.
Анализаторы PVS-Studio используют собственную внутреннюю реализацию методики анализа потоков данных. Анализаторы PVS-Studio для С, C++ и Java используют общую внутреннюю C++ библиотеку для работы data-flow анализа. Анализатор для C# имеет реализацию data-flow алгоритмов, написанную на языке C#.
Рассмотрим пример data-flow анализа на примере реального Java кода (источник):
private static byte char64(char x) {
if ((int)x < 0 || (int)x > index_64.length)
return -1;
return index_64[(int)x];
}После выполнения условного оператора становится известно, что значение переменной x лежит в диапазоне [0..128]. В противном случае функция досрочно закончит свою работу. Размер массива составляет 128 элементов, а значит, перед нами off-by-one error. Для правильной проверки следовало использовать оператор >=.
В случаях, когда у анализатора при разборе кода отсутствует возможность напрямую рассчитать диапазон значений выражения, применяется методика символьного выполнения (symbolic execution). Символьное выполнение представляет возможные значения переменных и выражений в символическом виде с помощью формул. В таком представлении анализатор оперирует не конкретными значениями переменных, а символами, абстрагирующими данные переменные.
Рассмотрим пример на языке C++:
int F(std::vector<int> &v, int x)
{
int denominator = v[x] - v[x];
return x / denominator;
}Даже если ничего неизвестно о том, с какими значениями вызывается функция, анализатор PVS-Studio обнаружит здесь деление на ноль.
При обходе графа выполнения анализатор строит формулы для встречаемых выражений. В дальнейшем он может вычислять ограничения значений для этих выражений. Это достигается за счёт того, что в упомянутые выше формулы подставляются известные ограничения для тех символов, от которых зависит формула. Благодаря решению созданных при обходе графа формул, алгоритмы символьного выполнения позволяют вычислять ограничения значений одних выражений или переменных в зависимости от значений других выражений или переменных.
Можно сказать, что вычисление конечного значения выражения откладывается до момента, когда оно понадобится. Например, при работе диагностического правила, где оно будет вычислено по заранее сформулированной формуле.
Анализатор PVS-Studio для C, C++ и анализатор Java используют в рамках работы своих data-flow алгоритмов методику символьного выполнения.
Межпроцедурным анализом называют способность статического анализатора раскрывать точки вызова функций и учитывать влияние таких вызовов на состояние программы и переменных в локальном проверяемом контексте. Анализаторы PVS-Studio используют межпроцедурный анализ для уточнения ограничений и диапазонов значений переменных и выражений, рассчитываемых с помощью data-flow механизмов.
Межпроцедурный анализ в PVS-Studio позволяет учитывать при анализе потока данных значения, которые возвращают вызываемые функции. Рассмотрим пример ошибки в коде на языке С++:
int *my_alloc() { return new int; }
void foo(bool x, bool y)
{
int *a = my_alloc();
std::free(a);
}Ошибка несовместимого способа выделения и освобождения памяти будет обнаружена как раз благодаря информации о том, что может вернуть вызываемая функция.
Также отслеживаются состояния передаваемых в функции переменных и выражений. Это позволяет определять их потенциально опасное использование внутри тел функций. Таким образом, возможно как обнаружение потенциальных дефектов внутри тел самих вызываемых функций, так и определение взаимосвязи ограничений, которые накладываются на возвращаемые значения функций их входными значениями.
Рассмотрим вариацию ошибки, которую мы уже приводили до этого:
void my_free(void *p) { free(p); }
void foo(bool x, bool y)
{
int *a = new int;
my_free(a);
}Как и в предыдущем случае, анализатор предупредит, что память выделена с помощью оператора new, а освобождается с помощью функции free.
Работа межпроцедурного анализа ограничена доступностью исходного кода функций, которые анализатору требуется раскрыть. Прямой учёт при анализе функций, описанных в сторонних библиотеках, невозможен (из-за отсутствия при проверке их исходного кода). Однако анализаторы PVS-Studio способны учитывать их возвращаемые значения с помощью механизма аннотаций.
Помимо межпроцедурного, анализаторы PVS-Studio также поддерживают межмодульный анализ. Под межмодульным анализом в PVS-Studio понимается расширение возможностей межпроцедурного анализа на функции, объявленные в программных модулях, отличных от того, к которому относится текущий проверяемый файл.
В различных языках программирования под модулями могут пониматься различные сущности. В данном контексте под модулем мы подразумеваем единицу компиляции. Для языков C и C++ — это отдельный файл с исходным кодом (файл с расширением .c или .cpp). Для языка C# — это проект. Для языка Java — это исходный файл (файл с расширением .java) с объявленным в нём классом.
Анализаторы PVS-Studio для Java и C# способны получать исходный код функций, находящихся как в том же исходном файле, так и в других исходных файлах, относящихся к проверяемому проекту. Анализатор PVS-Studio для C# может также получать и анализировать исходный код функций, объявленных в других проектах, если эти проекты также были переданы в анализатор для проверки.
Анализатор PVS-Studio для C++ может получать тела функций, объявленных в проверяемой единице компиляции (препроцессированном исходном файле с раскрытыми включениями заголовочных файлов). Межмодульный режим работы C++ анализатора позволяет также получать data-flow информацию из других единиц компиляции. Для этого анализатор использует двухпроходный режим анализа. Первый проход собирает межпроцедурную data-flow информацию для всех проверяемых исходных файлов. На втором проходе эта информация используется при непосредственном анализе исходных файлов.
Если при разборе кода анализатор встречает функцию, тело которой невозможно раскрыть для анализа, он может воспользоваться механизмом аннотирования функций. Аннотирование функций позволяет задавать в декларативном виде информацию как об ограничениях в возвращаемых функцией значениях, так и об ограничениях, накладываемых на её входные параметры.
Аннотирование в анализаторах PVS-Studio можно разделить на 2 категории: библиотечные функции и пользовательские функции. Все анализаторы PVS-Studio содержат в себе аннотации на множество функций стандартных и распространённых библиотек. C++ анализатор PVS-Studio также предоставляет возможность задавать аннотации в виде специального декларативного синтаксиса для пользовательских функций, специфичных для конкретного проверяемого проекта.
На данный момент, например, в анализаторе для C и C++ проаннотировано около 7400 функций. Ручной разметке подвергаются:
Это позволяет задавать информацию по поведению функций, тела которых недоступны анализатору, и он не может самостоятельно понять, правильно они используются или нет. Рассмотрим для примера, как проаннотирована функция fread:
C_"size_t fread"
"(void * _DstBuf, size_t _ElementSize, size_t _Count, FILE * _File);"
ADD(HAVE_STATE | RET_SKIP | F_MODIFY_PTR_1,
nullptr, nullptr, "fread", POINTER_1, BYTE_COUNT, COUNT, POINTER_2)
.Add_Read(from_2_3, to_return, buf_1)
.Add_DataSafetyStatusRelations(0, 3)
.Add_FileAccessMode(4, AccessModeTypes::Read)
.Out(Modification::BoxedValue, Arg1)
.Out(Modification::BoxedValue, Arg4)
.Returns(Arg3, [](const IntegerVirtualValue &v)
{ return IntegerVirtualValue { 0, v.Max(), true }; });Аннотация позволяет указать, что считается корректными аргументами. Но намного более интересно, что аннотация задаёт взаимосвязь между входными аргументами и возвращаемым значением. Это позволяет обнаружить ошибку следующего вида:
unsigned foo(FILE *f)
{
unsigned char buf[10];
size_t n = fread(buf, sizeof(unsigned char), 10, f);
unsigned sum = 0;
for (size_t i = 0; i <= n; ++i)
sum += buf[i];
return sum;
}Анализатор знает, что может быть прочитано 10 байт и следовательно переменная n может принять значение в диапазоне [0..10]. Поскольку условие цикла написано с ошибкой, то и значение переменной i также может принять значение в диапазоне [0..10].
Благодаря взаимодействию механизма аннотирования и data-flow анализа PVS-Studio выдаст сообщение о потенциальном выходе за границу массива, если функция fread прочитает 10 байт: "V557 Array overrun is possible. The value of 'i' index could reach 10".
Taint-анализ (анализ помеченных данных) — это методика, позволяющая отследить распространение по программе внешних непроверенных, "загрязнённых" (отсюда и название taint) данных. Попадание в определённые уязвимые приёмники (sinks) таких данных может привести к возникновению целого ряда дефектов безопасности, таких как SQL-инъекции, межсайтовый скриптинг (XSS, cross-site scripting) и многих других.
Потенциальные уязвимости ПО, связанные с распространением заражённых данных, описаны в стандартах безопасной разработки, таких как OWASP ASVS (Application Security Verification Standard).
Обычно программу невозможно полностью защитить от ввода в неё потенциально опасных данных. Поэтому основным способом борьбы с внешними taint-данными является их проверка перед использованием или попаданием в уязвимые приёмники — так называемая очистка (санитизация) данных.
Анализатор PVS-Studio для C и C++, а также анализатор PVS-Studio для C# могут с помощью технологий межпроцедурного data-flow анализа отслеживать распространение по программе taint-данных. На механизме отслеживания taint-данных основана целая группа диагностических правил PVS-Studio.
Анализаторы PVS-Studio контролируют всю трассу распространения заражённых данных с учётом их передачи между программными модулями, а также их проверки (очистки). PVS-Studio сгенерирует предупреждение о потенциальной угрозе безопасности кода только в случае, если анализатор отследит полный путь прохождения taint-данных от источника до приёмника без проверки. Таким образом, PVS-Studio контролирует не только попадание опасных данных в программу, но и их использование без проверки — опасным анализатор посчитает именно использование данных, а не только их ввод.
Рассмотрим пример на языке C#:
void ProcessUserInfo()
{
using (SqlConnection connection = new SqlConnection(_connectionString))
{
....
String userName = Request.Form["userName"];
using (var command = new SqlCommand()
{
Connection = connection,
CommandText = "SELECT * FROM Users WHERE UserName = '" + userName + "'",
CommandType = System.Data.CommandType.Text
})
{
using (var reader = command.ExecuteReader())
....
}
}
}При формировании SQL-команды используется значение переменной userName, полученное из внешнего источника – Request.Form. Если в качестве значения используется скомпрометированная строка (например, ' OR '1'='1), это исказит логику запроса.
В данном случае анализатор отследит распространение данных от внешнего источника (Request.Form) до приёмника (свойство CommandText SQL-команды) без надлежащей проверки и выдаст предупреждение.
В конце хочется отметить, что для инструментов статического анализа важно не только количество диагностик, но и то, на каких технологиях они основаны. Важно, как реализованы диагностики и как много внимания уделяется таким темам, как ложные срабатывания и интеграция в процесс разработки.
Ложноположительные срабатывания при статическом анализе неизбежны. Поэтому, во-первых, наша команда много работает над тем, чтобы сократить их количество. Редко диагностики PVS-Studio хочется отключить, в отличие от многих предупреждений компиляторов. Это сильная сторона нашего анализатора. Во-вторых, у нас продумано, что делать с оставшимися предупреждениями и как интегрировать анализатор в большой проект.
Вы можете попробовать статический анализатор PVS-Studio, запросив бесплатную пробную лицензию.