PVS-Studio — статический анализатор исходного кода для поиска ошибок и уязвимостей в программах на языке C, C++ и C#. В этой статье я хочу дать обзор технологий, которые мы используем в анализаторе PVS-Studio для выявления ошибок в коде программ. Помимо общей теоретической информации я буду на практических примерах показывать, как та или иная технология позволяет выявлять ошибки.

Введение

Поводом для написания статьи стало моё выступление с докладом на открытой конференции ИСП РАН 2016 (ISPRAS OPEN 2016), проходившей в первых числах декабря в Главном здании Российской академии наук. Тема доклада: «Принципы работы статического анализатора кода PVS-Studio» (презентация в формате pptx).

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

На данный момент PVS-Studio – это, фактически, два отдельных анализатора: один для C++, другой для C#. Более того, они написаны на разных языках. Ядро C++ анализатора мы разрабатываем на языке C++, а ядро C# анализатора на C#.

Однако, разрабатывая эти два ядра мы используем одинаковые подходы. Более того, ряд сотрудников одновременно принимают участие в разработке как C++, так и C# диагностик. Поэтому далее в статье я не стану разделять эти анализаторы. Описание механизмов будет общим для обоих анализаторов. Да, конечно есть какие-то отличия, но для обзорного знакомства они несущественны. Если же в процессе повествования возникнет необходимость, я явно укажу: идёт ли речь о С++ анализаторе, или C#.

Команда

Прежде чем приступить к описанию анализатора, скажу несколько слов о нашей компании и нашей команде.

Анализатор PVS-Studio разрабатывается в российской компании ООО «СиПроВер». Компания развивается на собственные средства, получаемые от продаж PVS-Studio. Офис компании находится в городе Тула, расположенном в 200 км. от Москвы.

Сайт: http://www.viva64.com

На момент написания статьи штат компании насчитывает 24 человека.

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

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

Наши достижения

Для популяризации PVS-Studio мы регулярно проверяем различные открытые проекты и описываем в статьях найденные в них ошибки. На данный момент мы проверили около 270 проектов.

В процессе написания этих статей мы выявили уже более 10000 ошибок, о которых сообщили авторам проектов. Мы очень гордимся этим и сейчас я поясню почему.

Если разделить количество найденных ошибок на количество проектов, то получается не очень внушительное число: около 40 ошибок на проект. Поэтому я хочу выделить важный момент. Эти 10000 ошибок являются побочным эффектом. Мы никогда не ставили целью выявить как можно больше ошибок. Часто мы останавливаемся, когда нашли достаточное количество дефектов в проекте, чтобы написать статью.

Это очень хорошо демонстрирует удобство и возможности анализатора. Мы гордимся тем, что можно просто брать незнакомые проекты и почти без всякой настройки анализатора сразу находить в них ошибки. Если бы это было не так, мы бы не выявили 10000 ошибок просто как побочный результат от написания статей в блог.

PVS-Studio

Если совсем кратко, то PVS-Studio это:

• Более 340 диагностик для C, C++;
• Более 120 диагностик для C#;
• Windows;
• Linux;
• Плагин для Visual Studio;
• Быстрый старт (мониторинг компиляции);
• Различные вспомогательные возможности, например, интеграция с SonarQube и IncrediBuild.

Почему C и C++

Языки C и C++ крайне эффективны и изящны. Но взамен требуют невероятного внимания к себе со стороны программиста и глубоких знаний предметной области. Поэтому статические анализаторы кода давно хорошо зарекомендовали себя среди C и С++ разработчиков. Причем, хотя языки, компиляторы и инструменты разработки развиваются, но, как говорится, ничего не меняется. Сейчас я поясню на примере, что имею в виду.

К 30-летию языка C++ мы выполнили проверку первого компилятора языка Cfront, написанного в 1985 году. Кому интересны подробности, предлагаю ознакомиться со статьёй "К тридцатилетию первого C++ компилятора: ищем ошибки в Cfront".

В нем мы нашли вот такую ошибку:

Pexpr expr::typ(Ptable tbl)
{
  ....
  Pclass cl;
  ....
  cl = (Pclass) nn->tp;
  cl->permanent=1;                                    // <= use
  if (cl == 0) error('i',"%k %s'sT missing",CLASS,s); // <= test
  ....

Сначала указатель cl разыменовывается, а только потом проверяется на равенство NULL.

Прошло 30 лет.

Теперь перед нами код не компилятора Cfront, а современный Clang. И вот что в нём обнаруживает PVS-Studio:

....
Value *StrippedPtr = PtrOp->stripPointerCasts();
PointerType *StrippedPtrTy = 
  dyn_cast<PointerType>(StrippedPtr->getType());  // <= use
if (!StrippedPtr)                                 // <= test
  return 0;
....

Как говорится: «Баги. Баги C++ никогда не меняются». Указатель StrippedPtr сначала разыменовывается, а только потом проверяется на равенство NULL.

Анализаторы кода крайне полезны для языков C и C++. Поэтому мы развивали и будем развивать анализатор PVS-Studio для этих языков. Пока не предвидится, что у этих инструментов станет меньше работы, так как языки крайне популярны и при этом крайне опасны.

Почему C#

Конечно, в некоторых моментах язык C# более совершенный и безопасный, чем C++. Однако, далеко уйти ему не удалось, и он также доставляет массу головной боли программистам. Я ограничусь только одним из примеров, а вообще это тема для отдельной статьи.

Мы вновь встречаем старого друга – ошибку, описанную выше. Фрагмент из проекта PowerShell:

....
_parameters = new Dictionary<string, ParameterMetadata>(
  other.Parameters.Count,                          // <= use
  StringComparer.OrdinalIgnoreCase); 
if (other.Parameters != null)                      // <= test
....

Сначала ссылка other.Parameters используется для получения свойства Count, а только затем проверяется на равенство null.

Как видите, от того, что в C# указатели назвали ссылками, лучше не стало. Что касается различных опечаток, то они вообще не зависят от языка. В общем, для PVS-Studio есть работа и мы активно развиваем C#-направление.

Что дальше?

Пока что у нас нет четких планов, какой язык мы хотим поддержать следующим. У нас есть два кандидата: Objective-C и Java. Мы больше склоняемся к языку Java, но пока окончательно не определились.

Какие технологии мы не используем в PVS-Studio

Прежде чем рассказывать о внутреннем устройстве PVS-Studio кратко отмечу, чего в PVS-Studio нет.

PVS-Studio не имеет ничего общего с Prototype Verification System (PVS). Это просто совпадение. Аббревиатура PVS образована от названия нашей компании Program Verification Systems.

PVS-Studio не использует непосредственно математический аппарат грамматик для поиска ошибок. Анализатор работает на более высоком уровне. Анализ выполняется на основании дерева разбора.

PVS-Studio не использует компилятор Clang для анализа C/C++ кода. Clang используется для выполнения шага препроцессирования. Подробнее про это рассказано в статье "Немного о взаимодействии PVS-Studio и Clang". Для построения дерева разбора мы используем собственный парсер, который был основан на забытой сейчас библиотеке OpenC++. Впрочем, от кода той библиотеки почти ничего не осталось, и мы реализуем поддержку новых конструкция языка самостоятельно.

При работе с C# кодом мы опираемся на Roslyn. C# анализатор PVS-Studio проверяет непосредственно исходный код программы, что повышает точность анализа по сравнению с проверкой бинарного байт-кода (Common Intermediate Lanuage).

PVS-Studio не использует для поиска ошибок поиск подстрок (string matching) и регулярные выражения (regular expressions). Это тупиковый путь. У такого подхода так много недостатков, что на его основе невозможно сделать хоть сколько-нибудь качественный анализатор, а многие диагностики в принципе невозможно реализовать. Подробнее эта тема рассмотрена в моей статье "Статический анализ и регулярные выражения".

Какие технологии мы используем в PVS-Studio

Для обеспечения высокого качества результатов статического анализа мы используем передовые методы анализа исходного кода программы и её графа потока управления (control flow graph). Давайте ознакомимся с ними.

Примечание. Далее в качестве примеров будут рассмотрены некоторые диагностики и кратко описаны принципы их работы. Важно отметить, что я сознательно опускаю описание случаев, когда диагностика не должна срабатывать, чтобы не перегружать статью деталями. Это примечание я пишу для тех, кто не сталкивался с разработкой анализаторов: не думайте, что всё так просто, как будет написано ниже. Сделать диагностику — это только 5% работы. Ругаться на подозрительный код не сложно, намного сложнее не ругаться на корректный код. 95% времени при разработке диагностики уходит на обучение анализатора выделять различные приемы программирования, которые хотя и выглядят подозрительно для диагностики, на самом деле корректны.

Pattern-based analysis

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

Для начала давайте рассмотрим два самых простых случая, выявляемых с помощью паттерного анализа. Первый простой случай:

if ((*path)[0]->e->dest->loop_father != path->last()->e->....)
{
  delete_jump_thread_path (path);
  e->aux = NULL;
  ei_next (&ei;);
}
else
{
  delete_jump_thread_path (path);
  e->aux = NULL;
  ei_next (&ei;);
}

Предупреждение PVS-Studio: V523 The 'then' statement is equivalent to the 'else' statement. tree-ssa-threadupdate.c 2596

В независимости от условия, всегда выполняется один и тот же набор действий. Думаю, здесь всё настолько просто, что не требуются специальные пояснения. Кстати, этот фрагмент кода я встретил не в курсовой работе студента, а в коде компилятора GCC. С результатами проверки компилятора GCC можно ознакомиться в статье "Находим ошибки в коде компилятора GCC с помощью анализатора PVS-Studio".

Второй простой случай (код взят из проекта FCEUX):

if((t=(char *)realloc(next->name,strlen(name+1))))

Предупреждение PVS-Studio: V518 The 'realloc' function allocates strange amount of memory calculated by 'strlen(expr)'. Perhaps the correct variant is 'strlen(expr) + 1'. fceux cheat.cpp 609

Анализируется следующий ошибочный паттерн. Программисты знают, что когда они выделяют память для хранения строки, то должны дополнительно выделить память для одного символа, где будет храниться признак конца строки (терминальный ноль). Другими словами, программисты знают, что должны обязательно дописать +1 или +sizeof(TCHAR). Но делают это иногда небрежно. В результате они прибавляют 1 не к значению, которое возвращает функция strlen, а к указателю.

Именно так и произошло в нашем случае. Вместо strlen(name+1) должно быть написано strlen(name)+1.

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

Теперь рассмотрим анализ среднего уровня сложности.

Диагностика формулируется так: предупреждаем, если после использования оператора as на null проверяется исходный объект вместо результата оператора as.

Рассмотрим фрагмент кода из проекта CodeContracts:

public override Predicate JoinWith(Predicate other)
{
  var right = other as PredicateNullness;
  if (other != null)
  {
    if (this.value == right.value)
    {

Предупреждение PVS-Studio: V3019 Possibly an incorrect variable is compared to null after type conversion using 'as' keyword. Check variables 'other', 'right'. CallerInvariant.cs 189

Обратите внимание, что на равенство null проверяется переменная other, а вовсе не right. Это явная ошибка, ведь потом работают именно с переменной right.

И под конец — сложный паттерн, связанный с использование макросов.

Макрос разворачивается так, что приоритет операции внутри макроса выше приоритета операции вне макроса. Пример:

#define RShift(a) a >> 3
....
RShift(a & 0xFFF) // a & 0xFFF >> 3

Для разрешения проблемы нужно поместить в макросе аргумент a в скобки (а лучше и весь макрос тоже в скобки), то есть написать так:

#define RShift(a) ((a) >> 3),

Тогда макрос корректно развернётся в:

RShift(a & 0xFFF) // ((a & 0xFFF) >> 3)

Описание паттерна выглядит простым, но на практике реализация диагностики весьма сложна. Недостаточно анализировать только "#define RShift(a) a >> 3". Если выдавать предупреждения на все такие строки, будет слишком много срабатываний. Надо смотреть, как макрос раскрывается в конкретном случае, и пытаться отделить ситуации, когда это специальная задумка, а когда действительно не хватает скобок.

Рассмотрим эту ошибку на примере кода реального проекта FreeBSD:

#define  ICB2400_VPINFO_PORT_OFF(chan)   (ICB2400_VPINFO_OFF +                   sizeof (isp_icb_2400_vpinfo_t) +      (chan * ICB2400_VPOPT_WRITE_SIZE))
....
off += ICB2400_VPINFO_PORT_OFF(chan - 1);

Предупреждение PVS-Studio: V733 It is possible that macro expansion resulted in incorrect evaluation order. Check expression: chan — 1 * 20. isp.c 2301

Type inference

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

Другими словами, анализатор должен знать, является токен Foo именем переменной, названием класса или функцией. Анализатор во многом повторяет работу компилятора, которому также требуется точно знать тип того или иного объекта и всю сопутствующую информацию о типе: размер, знаковый/беззнаковый тип, если класс, то от кого он наследуется и так далее.

Именно по этой причине анализатор PVS-Studio требует препроцессировать *.c/*.cpp файлы. Только анализируя препроцессированный файл можно собрать всю информацию о типах. Без такой информации многие диагностики осуществлять невозможно, или они будут давать много ложных срабатываний.

Примечание. Если кто-то заявляет, что их анализатор умеет проверять *.c/*.cpp файлы как текстовый документ, без полноценного препроцессирования, то знайте, это просто баловство. Да, такой анализатор может что-то находить, но в целом — это несерьезная игрушка.

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

Давайте рассмотрим на примерах, как используется информация о типах.

Первый пример демонстрирует, что информация о типе нужна, чтобы выявить ошибку при работе с функцией fprintf (код взят из проекта Cocos2d-x):

WCHAR *gai_strerrorW(int ecode);
....
#define gai_strerror gai_strerrorW
....
fprintf(stderr, "net_listen error for %s: %s",
        serv, gai_strerror(n));

Предупреждение PVS-Studio: V576 Incorrect format. Consider checking the fourth actual argument of the 'fprintf' function. The pointer to string of char type symbols is expected. ccconsole.cpp 341

Функция frintf ожидает в качестве четвертого аргумента указатель типа char *. Случайно получилась так, что фактическим аргументом является строка типа wchar_t *.

Чтобы выявить эту ошибку надо знать тип, который возвращает функция gai_strerrorW. Если этой информации не будет, то и выявить ошибку не представляется возможным.

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

Код вида "*A = *A;" однозначно считается анализатором подозрительным. Однако, анализатор промолчит, если встретит следующую ситуацию:

volatile char *ptr;
....
*ptr = *ptr;  // <= Нет срабатывания V570

Спецификатор volatile подсказывает, что это не ошибка, а специальная задумка программиста. Разработчику зачем-то надо «потрогать» ячейку памяти. Зачем ему это нужно — мы не знаем, но раз он так делает, то в этом есть смысл и выдавать предупреждение не следует.

Теперь давайте рассмотрим пример, как можно выявлять ошибку, основываясь на знаниях о классе.

Пример кода взят из проекта CoreCLR:

struct GCStatistics : public StatisticsBase {
....
virtual void Initialize();
virtual void DisplayAndUpdate();
....  
GCStatistics g_LastGCStatistics;
....
memcpy(&g_LastGCStatistics, this, sizeof(g_LastGCStatistics));

Предупреждение PVS-Studio: V598 The 'memcpy' function is used to copy the fields of 'GCStatistics' class. Virtual table pointer will be damaged by this. cee_wks gc.cpp 287.

Копировать один объект в другой с помощью функции memcpy вполне допустимо, если объекты являются POD-структурами. Однако здесь в классе присутствуют виртуальные методы, а значит имеется и указатель на таблицу виртуальных методов. Копировать этот указатель из одного объекта в другой крайне опасно.

Итак, диагностика стала возможна благодаря тому, что мы знаем, что переменная g_LastGCStatistics — это экземпляр класса, и что этот класс не является POD-типом.

Symbolic execution

Символьное выполнение позволяет вычислять значения переменных, которые могут приводить к ошибкам, производить проверку диапазонов (range checking) значений. В наших статьях мы иногда называем это механизмом вычисления виртуальных значений: см., например, статью "Поиск ошибок с помощью вычисления виртуальных значений".

Зная предполагаемые значения переменных, можно выявлять такие ошибки как:

• утечки памяти;
• переполнения;
• выход за границу массива;
• разыменование нулевых указателей в C++ / доступ по нулевой ссылке в C#;
• бессмысленные условия;
• деление на 0;
• и так далее.

Рассмотрим, как используя знания о возможных значениях переменных можно находить различные ошибки. Начнём с фрагмента кода, взятого из проекта QuantLib:

Handle<YieldTermStructure> md0Yts() {
  double q6mh[] = {
    0.0001,0.0001,0.0001,0.0003,0.00055,0.0009,0.0014,0.0019,
    0.0025,0.0031,0.00325,0.00313,0.0031,0.00307,0.00309,
    ........................................................
    0.02336,0.02407,0.0245 };               // 60 элементов
  ....
  for(int i=0;i<10+18+37;i++) {             // i < 65   
    q6m.push_back(
      boost::shared_ptr<Quote>(new SimpleQuote(q6mh[i])));

Предупреждение PVS-Studio: V557 Array overrun is possible. The value of 'i' index could reach 64. markovfunctional.cpp 176

Здесь анализатор знает следующие данные:

• массив q6mh содержит 60 элементов;
• счетчик массива i будет принимать значения [0..64].

Зная эти данные, диагностика V557 обнаруживает выход за границу массива при выполнении операции q6mh[i].

Теперь рассмотрим ситуацию, где может возникнуть деление на 0. Код взят из проекта Thunderbird:

static inline size_t UnboxedTypeSize(JSValueType type)
{
  switch (type) {
  .......
  default: return 0;
  }
}
Minstruction *loadUnboxedProperty(size_t offset, ....)
{
  size_t index = offset / UnboxedTypeSize(unboxedType);

Предупреждение PVS-Studio: V609 Divide by zero. Denominator range [0..8]. ionbuilder.cpp 10922

Функция UnboxedTypeSize возвращает различные значения, в том числе и 0. Не проверяя, что результат работы функции может быть 0, её используют как знаменатель. Потенциально это может привести к делению переменной offset на 0.

Предыдущие примеры касались диапазона целочисленных значений. Однако, анализатор оперирует и со значениями других типов данных, например, со строками и указателями.

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

string lowerValue = value.ToLower();
....
bool insensitiveOverride = lowerValue == lowerValue.ToUpper();

Предупреждение PVS-Studio: V3122 The 'lowerValue' lowercase string is compared with the 'lowerValue.ToUpper()' uppercase string. ServerModeCore.cs 2208

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

Продолжать описывать диагностики, построенные на знаниях о значении переменных, можно долго. Я приведу только ещё один пример, связанный с указателями и утечкой памяти.

Код взят из проекта WinMerge:

CMainFrame* pMainFrame = new CMainFrame;
if (!pMainFrame->LoadFrame(IDR_MAINFRAME))
{
  if (hMutex)
  {
    ReleaseMutex(hMutex);
    CloseHandle(hMutex);
  }
  return FALSE;
}
m_pMainWnd = pMainFrame;

Предупреждение анализатора: V773 The function was exited without releasing the 'pMainFrame' pointer. A memory leak is possible. Merge merge.cpp 353

Если не удалось загрузить фрейм, то функция завершает свою работу. При этом не разрушается объект, указатель на который хранится в переменной pMainFrame.

Диагностика работает следующим образом. Анализатор запоминает, что указатель pMainFrame хранит адрес объекта, созданного с помощью оператора new. Анализируя граф потока управления, анализатор встречает оператор return. При этом объект не разрушался и указатель продолжает ссылаться на созданный объект. Это значит, что в этой точке возникает утечка памяти.

Method annotations

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

Мы проделали большую работу по аннотированию функций:

• C/C++. На данный момент проаннотировано 6570 функций (стандартные библиотеки C и C++, POSIX, MFC, Qt, ZLib и так далее).
• C#. На данный момент проаннотировано 920 функций.

Рассмотрим, как в ядре C++ анализатора проаннотирована функция memcmp:

C_"int memcmp(const void *buf1, const void *buf2, size_t count);"
ADD(REENTERABLE | RET_USE | F_MEMCMP | STRCMP | HARD_TEST |
    INT_STATUS, nullptr, nullptr, "memcmp",
    POINTER_1, POINTER_2, BYTE_COUNT);

Краткие пояснения по разметке:

• C_ — вспомогательный механизм контроля аннотаций (юнит-тесты);
• REENTERABLE – повторный вызов с теми же аргументами даст тот же результат;
• RET_USE – результат должен быть использован;
• F_MEMCMP – запуск определённых проверок выхода за границы буфера;
• STR_CMP – при равенстве функция возвращает 0;
• HARD_TEST – особая функция: некоторые библиотеки определяют собственные идентичные функции в своих namespace и поэтому следует игнорировать namespace;
• INT_STATUS – результат нельзя явно сравнивать с 1 или -1;
• POINTER_1, POINTER_2 – указатели должны быть не нулевыми и разными;
• BYTE_COUNT – параметр задает количество байт и должен быть больше 0.

Данные аннотации используются многими диагностиками. Рассмотрим некоторые ошибки, которые мы обнаружили в коде приложений благодаря приведенной выше разметке для функции memcmp.

Пример использования разметки INT_STATUS. Проект CoreCLR:

bool operator()(const GUID& _Key1, const GUID& _Key2) const
{
  return memcmp(&_Key1, &_Key2, sizeof(GUID)) == -1;
}

V698 Expression 'memcmp(....) == -1' is incorrect. This function can return not only the value '-1', but any negative value. Consider using 'memcmp(....) < 0' instead. sos util.cpp 142

Такой код может работать, но в целом он неверен. Функция memcmp возвращает значения 0, больше нуля и меньше нуля. Важно:

• «больше нуля», это не обязательно 1
• «меньше нуля», это не обязательно -1

Таким образом, нет никакой гарантии в работоспособности написанного кода. В любой момент сравнение может начать работать неправильно. Это может произойти при смене компилятора, изменении настроек оптимизации и так далее.

Флаг INT_STATUS помогает выявить ещё один вид ошибки. Код проекта Firebird:

SSHORT TextType::compare(ULONG len1, const UCHAR* str1,
                         ULONG len2, const UCHAR* str2)
{
  ....
  SSHORT cmp = memcmp(str1, str2, MIN(len1, len2));
  if (cmp == 0)
    cmp = (len1 < len2 ? -1 : (len1 > len2 ? 1 : 0));
  return cmp;
}

PVS-Studio. V642 Saving the 'memcmp' function result inside the 'short' type variable is inappropriate. The significant bits could be lost breaking the program's logic. texttype.cpp 3

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

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

Одна такая ошибка послужила причиной серьезной уязвимости в MySQL/MariaDB до версий 5.1.61, 5.2.11, 5.3.5, 5.5.22. Причиной стал следующий код в файле 'sql/password.c':

typedef char my_bool;
....
my_bool check(...) {
  return memcmp(...);
}

Суть в том, что при подключении пользователя MySQL /MariaDB вычисляется токен (SHA от пароля и хэша), который сравнивается с ожидаемым значением функцией memcmp. На некоторых платформах возвращаемое значение может выпадать из диапазона [-128..127]. В итоге, в 1 случае из 256, процедура сравнения хэша с ожидаемым значением всегда возвращает значение true, независимо от хэша. В результате простая команда на bash даёт злоумышленнику рутовый доступ к уязвимому серверу MySQL, даже если он не знает пароль. Более подробное описание этой проблемы можно прочитать здесь: Security vulnerability in MySQL/MariaDB.

Пример использования разметки BYTE_COUNT. Проект GLG3D:

bool Matrix4::operator==(const Matrix4& other) const {
  if (memcmp(this, &other, sizeof(Matrix4) == 0)) {
    return true;
  }
  ....
}

Предупреждение PVS-Studio: V575 The 'memcmp' function processes '0' elements. Inspect the 'third' argument. graphics3D matrix4.cpp 269

Третий аргумент функции memcmp помечен как BYTE_COUNT. Считается, что такой аргумент не должен быть равен 0. В приведённом фрагменте кода третий фактический параметр как раз равен 0.

Ошибка заключается в том, что не там поставлена скобка. В результате третьим аргументом является выражение sizeof(Matrix4) == 0. Результат этого выражения false, т.е. 0.

Пример использования разметки POINTER_1 и POINTER_2. Проект GDB:

static int
psymbol_compare (const void *addr1, const void *addr2,
                 int length)
{
  struct partial_symbol *sym1 = (struct partial_symbol *) addr1;
  struct partial_symbol *sym2 = (struct partial_symbol *) addr2;
  return (memcmp (&sym1->ginfo.value, &sym1->ginfo.value,
                  sizeof (sym1->ginfo.value)) == 0
          && .......

Предупреждение PVS-Studio: V549 The first argument of 'memcmp' function is equal to the second argument. psymtab.c 1580

Первый и второй аргументы размечены как PONTER_1 и POINTER_2. Во-первых, это означает, что они не должны быть равны NULL. Но в данном случае нам интересно второе свойство разметки: эти указатели не должны совпадать, о чем говорят суффиксы _1 и _2.

Из-за опечатки в коде буфер &sym1->ginfo.value сравнивается сам с собой. PVS-Studio, опираясь на разметку, легко обнаруживает эту ошибку.

Пример использования разметки F_MEMCMP.

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

dst_s_read_private_key_file(....)
{
  ....
  if (memcmp(in_buff, "Private-key-format: v", 20) != 0)
    goto fail;
  ....
}

Предупреждение PVS-Studio: V512 A call of the 'memcmp' function will lead to underflow of the buffer '«Private-key-format: v»'. dst_api.c 858

Строка «Private-key-format: v» состоит из 21 символа, а не из 20. Таким образом, сравнивается меньше байт чем требуется.

Пример использования разметки REENTERABLE. Если честно, слово «reenterable» не совсем верно отражает суть данного флага. Однако, все разработчики в нашей команде к нему привыкли и не хочется делать изменений в коде ради красоты.

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

if (fprintf(f, "1") == 1 && fprintf(f, "1") == 1)

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

if (fprintf(f, "1") == 1) // неправильно

А вот такой код избыточен и насторожит анализатор, так как функция cosf не имеет состояния и никуда ничего не записывает:

if (cosf(a) > 0.1f && cosf(a) > 0.1f)

Вернемся теперь к функции memcmp и посмотрим, какую ошибку удалось обнаружить с помощью рассмотренной разметки в проекте PHP:

if ((len == 4) /* sizeof (none|auto|pass) */ &&
    (!memcmp("pass", charset_hint, 4) ||
     !memcmp("auto", charset_hint, 4) ||
     !memcmp("auto", charset_hint, 4)))

Предупреждение PVS-Studio: V501 There are identical sub-expressions '!memcmp(«auto», charset_hint, 4)' to the left and to the right of the '||' operator. html.c 396

Два раза проверяется, что буфер содержит слово «auto». Этот код избыточен и анализатор предполагает в нем наличие ошибки. И действительно, комментарий подсказывает нам, что пропущено сравнение со строкой «none».

Как видите, с помощью разметки можно находить много интересных ошибок. Часто анализаторы предоставляют возможности пользователям самостоятельно аннотировать функции. В PVS-Studio эти возможности развиты слабо. В нем есть всего несколько диагностик, для которых можно что-то проаннотировать. Например, это диагностика V576 для поиска ошибок использования функций форматного вывода (printf, sprintf, wprintf и так далее).

Мы сознательно не развиваем механизм пользовательских аннотаций. На это есть две причины:

• В большом проекте никто не станет тратить время на разметку функций. Это просто нереально, когда у вас 10 миллионов строк кода, а ведь анализатор PVS-Studio как раз ориентирован на средние и большие проекты.
• Если не размечены функции из какой-то известной библиотеки, то лучше написать нам и мы сами проаннотируем их. Во-первых, мы сделаем это быстрее и лучше, а во-вторых, результаты разметки станут доступны всем нашим пользователям.

Ещё раз кратко о технологиях

Кратко резюмирую свой рассказ о используемых технологиях. PVS-Studio использует:

• Сопоставление с шаблоном (pattern-based analysis) на основе абстрактного синтаксического дерева: применяется для поиска мест в исходном коде, которые похожи на известные шаблоны кода с ошибкой.
• Вывод типов (type inference) на основе семантической модели программы: позволяет анализатору иметь полную информацию о всех переменных и выражениях, встречающихся в коде.
• Символьное выполнение (symbolic execution): позволяет вычислять значения переменных, которые могут приводить к ошибкам, производить проверку диапазонов (range checking) значений.
• Анализ потока данных (data-flow analysis): используется для вычисления ограничений, накладываемых на значения переменных при обработке различных конструкций языка. Например, какие значения может принимать переменная внутри блоков if/else.
• Аннотированние методов (method annotations): предоставляет больше информации об используемых методах, чем может быть получено путём анализа только их сигнатуры.

На основе этих технологий анализатор умеет выявлять следующие классы ошибок в программах на языках C, C++ и C#:

• 64-битные ошибки;
• адрес локальной переменной возвращается из функции по ссылке;
• арифметическое переполнение, потеря значимости;
• выход за границу массива;
• двойное освобождение ресурсов;
• мёртвый код;
• микрооптимизации;
• недостижимый код;
• неинициализированные переменные;
• неиспользуемые переменные;
• некорректные операции сдвига;
• неопределенное/неуточняемое поведение;
• неправильная работа с типами (HRESULT, BSTR, BOOL, VARIANT_BOOL);
• неправильное представление о работе функции/класса;
• опечатки;
• отсутствие виртуального деструктора;
• оформление кода не совпадает с логикой его работы;
• ошибки из-за Copy-Paste;
• ошибки работе с исключениями;
• переполнение буфера;
• проблемы безопасности;
• путаница с приоритетом операций;
• разыменование нулевого указателя / нулевой ссылки;
• разыменование параметров без предварительной проверки;
• ошибки синхронизации;
• ошибки при использовании WPF;
• утечки памяти;
• целочисленное деление на 0;
• диагностики, созданные по специальным просьбам пользователей.

Вывод. Анализатор PVS-Studio является мощным инструментом поиска ошибок, использующим для этого современный арсенал методов для их выявления.

Да, PVS-Studio это положительный супергерой мира программ.

Тестирование PVS-Studio

Разработка анализаторов кода невозможна без их постоянного тщательного тестирования. При разработке PVS-Studio мы используем 7 различных методик тестирования:

1. Статический анализ кода на машинах разработчиков. У всех разработчиков установлен PVS-Studio. Новый или изменённый код сразу проверяется с помощью механизма инкрементального анализа. Проверяется C++ и С# код.
2. Статический анализ кода при ночных сборках. Если предупреждение не было замечено, то оно выявится на этапе ночной сборки на сервере. PVS-Studio проверяет C# и C++ код. Помимо этого, мы дополнительно используем компилятор Clang для проверки C++ кода.
3. Юнит-тесты уровня классов, методов, функций. Не очень развитая система, так как многие моменты сложно тестировать из-за необходимости подготавливать для теста большой объем входных данных. Мы больше полагаемся на высокоуровневые тесты.
4. Функциональные тесты уровня специально подготовленных и размеченных файлов с ошибками. Это наша альтернатива классическому юнит-тестированию.
5. Функциональные тесты, подтверждающие, что мы корректно разбираем основные системные заголовочные файлы.
6. Регрессионные тесты уровня отдельных сторонних проектов и решений (projects and solutions). Самый важный и полезный для нас вид тестирования. Сравнивая старые и новые результаты анализа, мы контролируем, что что-то не сломали и оттачиваем новые диагностические сообщения. Для его осуществления мы регулярно проверяем открытые проекты. C++ анализатор тестируется на 120 проектах под Windows (Visual C++), плюс дополнительно на 24 проектах под Linux (GCC). Анализатор C# пока тестируется чуть слабее. Тестовая база состоит из 54 проектов.
7. Функциональные тесты пользовательского интерфейса расширения — надстройки, интегрируемой в среду Visual Studio.

Заключение

Эта статья написана для популяризации методологии статического анализа. Думаю, читателям интересно знать не только о результатах применения анализаторов кода, но и том, как они устроены внутри. Постараюсь время от времени писать статьи на эту тематику.

Дополнительно, мы планируем больше участвовать в различных мероприятиях, таких как конференции и семинары. Мы будем рады получить приглашения на различные мероприятия, особенно проходящие в Москве и Санкт-Петербурге. Например, в вашем институте или компании проходят встречи программистов, где люди делятся своим опытом. Мы можем приехать и сделать доклад на интересную тему. Например, про современный C++, о том, как мы разрабатываем анализаторы, про типовые ошибки программистов и как их предотвращать, доработав стандарт кодирования и так далее. Приглашения прошу присылать мне на почту karpov [@] viva64.com.

Напоследок несколько ссылок:

• Скачать PVS-Studio для Windows
• Скачать PVS-Studio для Linux
• Бесплатный вариант лицензии для PVS-Studio

Если хотите поделиться этой статьей с англоязычной аудиторией, то прошу использовать ссылку на перевод: Andrey Karpov. How PVS-Studio does the bug search: methods and technologies.