Оглавление
Технологии, используемые в PVS-Studio
- Смотри, а не читай (YouTube)
- Абстрактное синтаксическое дерево (Abstract Syntax Tree) и методика сопоставления с шаблоном (сигнатурный анализ, pattern-based analysis)
- Семантическая модель (semantic model) кода и вывод типов (type inference)
- Препроцессирование C и C++ исходного кода
- Отслеживание компиляции C и C++ исходного кода
- Анализ потоков данных (data-flow анализ) и символьное выполнение (symbolic execution)
- Межпроцедурный анализ
- Межмодульный анализ и аннотирование функций
- Taint анализ (taint checking)
- Анализ компонентного состава ПО (software composition analysis, SCA)
- Дополнительные ссылки
PVS-Studio предоставляет статические анализаторы для языков C, C++, C# и Java на платформах Windows, Linux и macOS. Несмотря на некоторые различия, накладываемые особенностями отдельных языков, в целом все анализаторы PVS-Studio используют ряд общих технологий и подходов к реализации статического анализа.
PVS-Studio разрабатывается с учётом требований, предъявляемых к статическим анализаторам в ГОСТ Р 71207–2024. Выявляет критические ошибки (потенциальные уязвимости) и может использоваться при разработке безопасного программного обеспечения.
В составе PVS-Studio можно выделить 3 отдельных программных инструмента для статического анализа: анализатор C и C++, анализатор C# и анализатор Java.
Анализатор PVS-Studio для языков C и C++ написан на языке C++ и основан на библиотеке разбора кода с закрытым исходным кодом VivaCore, также разрабатываемой командой PVS-Studio.
Анализатор PVS-Studio для языка C# написан на языке C# и использует для разбора кода (построения абстрактного синтаксического дерева и семантической модели) и интеграции с проектной системой MSBuild \ .NET открытую платформу Roslyn.
Анализатор PVS-Studio для языка Java написан на языке Java. Он использует возможности внутренней C++ библиотеки VivaCore для анализа потока данных. Для разбора кода (построения абстрактного синтаксического дерева и семантической модели) анализатор использует открытую библиотеку Spoon.
Все анализаторы PVS-Studio реализуют алгоритмы и механизмы для проведения data-flow анализа (включая символьное выполнение, межпроцедурный контекстно-чувствительный анализ и межмодульный анализ), основанные на собственных разработках компании PVS-Studio.
Рассмотрим далее подходы и методики, на которых основана технология статического анализа кода PVS-Studio.
Смотри, а не читай (YouTube)
Абстрактное синтаксическое дерево (Abstract Syntax Tree) и методика сопоставления с шаблоном (сигнатурный анализ, pattern-based analysis)
Вначале рассмотрим два термина, применяющихся в теории разработки компиляторов и статических анализаторов кода.
Абстрактное синтаксическое дерево (AST). AST — это конечное ориентированное дерево, в котором внутренние вершины соответствуют операторам языка программирования, а листья — соответствующим операндам. Абстрактные деревья синтаксиса используются компиляторами и интерпретаторами как промежуточное представление между деревьями разбора и внутренним представлением кода. Преимущество AST — достаточная компактность (абстрактность) структуры, достигаемая за счёт отсутствия узлов для конструкций, не влияющих на семантику программы.
Основным преимуществом использования абстрактного синтаксического дерева, по сравнению с прямым анализом текста программ (исходного кода), является независимость построенных на его основе анализаторов от конкретного синтаксиса: имён, стиля написания кода, его форматирования и т.п.
Дерево разбора (DT). Результат грамматического анализа. Дерево разбора отличается от абстрактного синтаксического дерева наличием узлов для тех синтаксических правил, которые не влияют на семантику программы. Классическим примером таких узлов являются группирующие скобки, в то время как в AST группировка операндов явно задаётся структурой дерева.
Высокоуровнево можно говорить, что ядра всех анализаторов PVS-Studio для разных языков работают с абстрактным синтаксическим деревом (AST). Однако на практике всё немного сложнее. В некоторых случаях диагностики требуют информации о необязательных узлах или даже вообще о количестве пробелов в начале строки. В этом случае анализ спускается на уровень дерева разбора и извлекает дополнительную информацию. Все используемые библиотеки (Roslyn, Spoon, VivaCore) предоставляют возможность получать информацию на уровне дерева разбора, и анализатор в ряде случаев этим пользуется.
Анализаторы PVS-Studio используют AST представление программы для поиска потенциальных дефектов методом сигнатурного анализа (сопоставление с шаблоном, pattern-based analysis). Это класс достаточно простых диагностических правил, которым для принятия решения об опасности кода достаточно сопоставить конструкцию, встретившуюся в коде, с заранее заданным шаблоном потенциальной ошибки.
Следует отметить, что поиск по шаблону — более высокоуровневая и эффективная технология, чем использование регулярных выражений. Регулярные выражения вообще не подходят по множеству причин для построения эффективного статического анализатора. Поясним это на простом примере. Допустим, требуется найти опечатки, когда выражение сравнивается само с собой. Это можно сделать регулярными выражениями для простейших случаев:
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, выявление подобных ошибок не является проблемой.
Представление кода в виде абстрактного синтаксического дерева также является подготовкой к проведению следующего уровня анализа — построения семантической модели и вывода типов.
Семантическая модель (semantic model) кода и вывод типов (type inference)
Помимо синтаксического анализа кода, все анализаторы PVS-Studio на основе построенного на предыдущем этапе представления кода в виде абстрактного синтаксического дерева проводят также и семантический анализ — построение полной семантической модели проверяемого кода.
Обобщённая семантическая модель представляет собой словарь соответствий семантических (смысловых) символов и элементов синтаксического представления этого же кода (для которого PVS-Studio использует узлы упомянутого выше абстрактного синтаксического дерева).
Каждый такой символ определяет семантику (смысл) соответствующей синтаксической конструкции языка. Эта семантика может быть неочевидна и невыводима из самого локального синтаксиса. Для выведения такой семантики требуется обращаться к другим частям синтаксического представления кода. Поясним это на примере фрагмента кода на языке C:
A = B(C);Не зная, что собой представляет 'B', невозможно сказать, какая перед нами конструкция языка. Это может быть как вызов функции, так и явное приведение типа (functional cast expression).
Семантическая модель, таким образом, позволяет анализировать семантику кода без необходимости постоянно совершать обход синтаксического представления этого кода для разрешения не выводимых из локального контекста семантических фактов. Семантическая модель "запоминает" семантику по ходу разбора кода для дальнейшего её использования.
На основе семантической модели анализаторы PVS-Studio получают возможность проводить вывод типов (type inference) у любой встречаемой синтаксической конструкции (как, например, идентификаторы переменных, выражения и т.п.), для которой это может потребоваться при проведении анализа кода на потенциальные дефекты. Семантическая модель дополняет анализ на основе шаблонов в случаях, когда одного синтаксического представления недостаточно для принятия решения об опасности проверяемой конструкции.
Построение полной и корректной семантической модели требует непротиворечивости и, соответственно, собираемости (компилируемости) проверяемого кода. Компилируемость исходного кода является обязательным условием для полноценной и корректной работы всех анализаторов PVS-Studio. Анализаторы PVS-Studio имеют механизмы отказоустойчивости при работе с некомпилируемым кодом. Однако такой код может ухудшать точность работы диагностических правил.
Препроцессирование C и C++ исходного кода
Препроцессирование C и C++ кода — это процесс раскрытия в исходном коде директив компилятора и подстановка значений макросов. В частности, в результате работы препроцессора на месте директив #include происходит подстановка содержимого заголовочных файлов, пути до которых записаны в данной директиве. Директивы и макросы раскрываются в случае такой подстановки последовательно, так же, как и во всех раскрываемых директивой #include заголовочных файлах. Препроцессирование является первым этапом работы компилятора — подготовкой единицы компиляции и её зависимостей к непосредственной трансляции исходного кода во внутреннее представление компилятора.
Раскрытие директив #include приводит к объединению исходного файла и всех используемых в нём заголовочных файлов в единый файл, часто называемый промежуточным (intermediate). По аналогии с компилятором, С и C++ анализатор PVS-Studio использует препроцессирование перед началом анализа. PVS-Studio использует для препроцессирования проверяемого кода целевой компилятор (в режиме препроцессора), для сборки которым этот код был изначально предназначен. PVS-Studio поддерживает работу с большим количеством препроцессоров, которые перечислены на странице продукта. Так как выходной формат препроцессоров различных компиляторов отличается, для корректной работы анализатора требуется использовать правильный препроцессор, соответствующий используемому для сборки проверяемого кода компилятору.
Перед началом анализа C и C++ анализатор PVS-Studio осуществляет запуск препроцессора для каждой единицы трансляции проверяемого кода. Помимо содержимого исходных файлов, на работу препроцессора также влияют параметры компиляции. PVS-Studio использует для препроцессирования параметры сборки, применяемые при компиляции проверяемого кода. Информацию о списке единиц трансляции, а также параметры компиляции PVS-Studio получает из сборочной системы проверяемого проекта либо путём отслеживания (перехвата) вызовов компиляторов в процессе сборки проекта.
Работа анализатора C и С++ PVS-Studio основана на результате работы соответствующего препроцессора — анализатор не анализирует исходный код напрямую. Препроцессирование C и C++ кода за счёт раскрытия директив компилятора позволяет анализатору построить полную семантическую модель проверяемого кода.
Отслеживание компиляции C и C++ исходного кода
Технология отслеживания (мониторинга) PVS-Studio позволяет перехватывать запуск процессов на уровне API операционной системы. Перехват запуска позволяет извлекать у процесса полную информацию о его работе, параметрах его запуска и рабочем окружении. Отслеживание запуска процессов PVS-Studio поддерживается на платформах Windows (реализовано через прямую работу с WinAPI) и Linux (реализовано с помощью стандартной системной утилиты strace).
C и C++ анализаторы PVS-Studio могут использовать отслеживание процессов компиляции как один из вариантов проведения анализа С++ кода. Несмотря на то, что PVS-Studio имеет средства прямой интеграции с наиболее распространёнными сборочными системами для C и C++ проектов, экосистема данных языков очень многообразна, и в ней существует большое количество сборочных систем (например, в embedded сегменте), интеграцию с которыми PVS-Studio не поддерживает. Хотя прямая, низкоуровневая интеграция C++ анализатора PVS-Studio в такие системы возможна, она является достаточно трудоёмкой, т.к. требует передачи в анализатор параметров компиляции для каждой единицы трансляции — исходного C или C++ файла.
Использование системы отслеживания процессов компиляции PVS-Studio позволяет упростить и автоматизировать процесс передачи анализатору всей необходимой для проведения анализа информации. Система отслеживания собирает параметры компиляции у процессов, анализирует и модифицирует их (например, активируя режим препроцессирования у компилятора — анализатору нужно проведение только этого этапа) и передаёт непосредственно в C++ анализатор PVS-Studio.
Таким образом, система отслеживания запуска процессов позволяет реализовать в PVS-Studio универсальную систему проверки C и C++ проектов, не зависящую от используемой сборочной системы, легко настраиваемую и полностью учитывающую оригинальные параметры компиляции проверяемого кода.
Анализ потоков данных (data-flow анализ) и символьное выполнение (symbolic execution)
Анализ потоков данных — это методика, позволяющая статическому анализатору делать предположения о значениях переменных и выражений в различных частях исходного кода. Под предполагаемыми значениями понимаются какие-то конкретные значения, диапазоны значений или множество возможных значений. Дополнительно собирается и обрабатывается информация о том, освобождена память по указателю или нет, каковы размеры массивов и так далее.
Предположения о значениях строятся на основе анализа движения значений переменных по графу выполнения программы (control-flow graph). В большинстве случаев анализатор не может знать точного значения переменной или выражения. Но он может, используя прямые и косвенные ограничения, накладываемые на рассматриваемые выражения по ходу обхода графа выполнения, делать предположения о диапазонах или множествах значений, которые данные выражения могут принимать в различных точках этого графа.
Все анализаторы PVS-Studio используют data-flow анализ для уточнения работы своих диагностических правил в случаях, когда для принятия решения об опасности рассматриваемого кода недостаточно информации, доступной только из синтаксической (AST) или семантической структуры этого кода. Анализаторы PVS-Studio используют собственную внутреннюю реализацию методики анализа потоков данных. Анализ потоков данных PVS-Studio поддерживает чувствительность к потокам и путям управления (flow-sensitive и path-sensitive dataflow анализ). Все ветвления в проверяемом коде учитываются в построении модели потоков данных этого кода.
Анализатор PVS-Studio для С, C++ и анализатор PVS-Studio для Java используют общую внутреннюю C++ библиотеку для работы data-flow анализа. Анализатор PVS-Studio для C# имеет реализацию data-flow алгоритмов, написанную на языке C#.
В случаях когда у анализатора при разборе кода отсутствует возможность напрямую рассчитать диапазон значений выражения, применяется методика символьного выполнения (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 механизмов.
Благодаря использованию при анализе AST представления кода и наличию полной семантической модели анализаторы PVS-Studio, встречая вызов функции, могут получать аналогичное AST представление тела этой функции, в котором также будет доступна вся семантическая информация.
Межпроцедурный анализ в PVS-Studio позволяет учитывать при анализе потока данных, значения, которые возвращают вызываемые функции. Также отслеживается состояния передаваемых в функции переменных и выражений, позволяя для передаваемых значений детектировать потенциально опасные конструкции и операции внутри тел функций. Таким образом, возможно обнаружение потенциальных дефектов как внутри тел самих вызываемых функций, так и определение взаимосвязи ограничений, накладываемых на возвращаемые значения функций их входными значениями.
Работа межпроцедурного анализа ограничена доступностью исходного кода функций, которые анализатору требуется раскрыть. Для раскрытия функций, определённых в исходных файлах, отличных от текущего проверяемого, PVS-Studio поддерживает механизм межмодульного анализа. Прямой учёт при анализе функций, описанных в сторонних библиотеках, невозможен (из-за отсутствия при проверке их исходных кодов), однако анализаторы 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 также предоставляет возможность задавать аннотации в виде специального декларативного синтаксиса для пользовательских функций, специфичных для конкретного проверяемого проекта.
Taint анализ (taint checking)
Taint анализ (анализ помеченных данных) — это методика отслеживания распространения по программе внешних непроверенных, "загрязнённых" (отсюда и название taint) данных. Попадание в определённые уязвимые приёмники таких данных может привести к возникновению целого ряда уязвимостей безопасности, таких как 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 контролирует не только попадание опасных данных в программу, но и их использование без проверки — опасным анализатор посчитает именно использование данных, а не только их ввод.
Анализ компонентного состава ПО (software composition analysis, SCA)
Многие современные приложения используют сторонние компоненты: библиотеки, пакеты и т.п. Некоторые из этих компонентов содержат уязвимости. Если приложение использует такой компонент, оно тоже может быть уязвимо.
Для поиска "опасных" зависимостей используют инструменты, которые проводят анализ компонентного состава ПО (software composition analysis, SCA).
Анализатор PVS-Studio для C# поддерживает анализ компонентного состава ПО. Алгоритм работы данного механизма:
- На основе проектных файлов сборочной системы MSBuild анализатор составляет bill of materials (BOM) – список прямых и транзитивных зависимостей проекта с информацией об их версиях.
- Среди зависимостей отбираются те, которые прямо или опосредованно используются в коде. Анализатор ищет использование в коде типов данных, которые объявлены в зависимых пакетах.
- Для каждой из BOM-записей PVS-Studio ищет подходящую ей запись в базе уязвимостей GitHub Advisory. При этом учитывается название проверяемой зависимости и её версия.
- Если соответствие найдено, анализатор выдаёт предупреждение с информацией о зависимости и уязвимостях, которые она содержит.
Подробнее об SCA в C# анализаторе PVS-Studio можно прочитать в документации к диагностическому правилу V5625.
Дополнительные ссылки
- Доклад на YappiDays 2018. Андрей Карпов. Опыт разработки статического анализатора кода.
- Доклад на CoreHard 2018. Павел Беликов. Как работает анализ Data Flow в статическом анализаторе кода.
- Доклад на Italian Cpp Community 2021 (itCppCon21). Yuri Minaev. Inside a static analyzer: type system.
- Олег Лысый , Сергей Ларин. Межмодульный анализ C++ проектов в PVS-Studio.
- Андрей Карпов. Зачем PVS-Studio использует анализ потока данных.
- Сергей Васильев. OWASP, уязвимости и taint анализ в PVS-Studio C#.
Была ли полезна эта страница документации?
