12 января в 14:31

Как PVS-Studio ищет ошибки: методики и технологии

Что внутри у PVS-StudioPVS-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



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

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

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


Для популяризации 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 и С++ разработчиков. Причем, хотя языки, компиляторы и инструменты разработки развиваются, но, как говорится, ничего не меняется. Сейчас я поясню на примере, что имею в виду.

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++. Однако, далеко уйти ему не удалось, и он также доставляет массу головной боли программистам. Я ограничусь только одним из примеров, а вообще это тема для отдельной статьи.

C#, Facepalm



Мы вновь встречаем старого друга – ошибку, описанную выше. Фрагмент из проекта 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


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

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) значений. В наших статьях мы иногда называем это механизмом вычисления виртуальных значений: см., например, статью "Поиск ошибок с помощью вычисления виртуальных значений".

Symbolic execution



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

  • утечки памяти;
  • переполнения;
  • выход за границу массива;
  • разыменование нулевых указателей в 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


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

memcmp()



Мы проделали большую работу по аннотированию функций:
  • 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


Разработка анализаторов кода невозможна без их постоянного тщательного тестирования. При разработке 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.

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




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

Прочитали статью и есть вопрос?
Часто к нашим статьям задают одни и те же вопросы. Ответы на них мы собрали здесь: Ответы на вопросы читателей статей про PVS-Studio, версия 2015. Пожалуйста, ознакомьтесь со списком.
Автор: @Andrey2008
PVS-Studio
рейтинг 491,71
Ищем ошибки в C, C++ и C# на Windows и Linux
Похожие публикации

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

  • +4
    REENTERABLE – повторный вызов с теми же аргументами даст тот же результат;

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


    А то что вы написали, называется идемпотентностью или более сильно — чистотой (pure).

    • +2
      Мы знаем. :) Как я и сказал в статье, это слово осталось с исторических времён и переименовать его в сотни мест просто не хочется. Думаю, в любом проекте есть сущности, названия которых уже не отражают действительность. В отличие от других программистов, я никогда не утверждаю, что вот наш то код идеален и без ошибок. :)
      • +2

        Массовые переименования не так уж и сложны, было бы желание. Условно говоря, что-то вроде такого однострочника:


        find src -name \*.cpp -or -name \*.h | while read f; do
          sed -i 's/REENTERABLE/IDEMPOTENT/g' $f
        done

        Программистов, только вот, к сожалению, не получится так же быстро переучить.

    • +3
      Так purity тоже не про это, а в первую очередь про то, что нет side-эффектов, что является достаточным, но не необходимым условием возврата одинакового результата при вызовах с одинаковыми наборами аргументов.
      • +2

        Потому я и написал, что чистота — более сильное свойство.

        • +1

          Кажется, вам указали на то, что чистоту и идемпотентность нельзя "вложить" друг в друга, то есть чистота — не более сильное свойство.

          • +3

            Почему нельзя-то? Любая чистая функция — идемпотентна. Если считаете иначе, приведите контрпример.

            • +2

              Согласен, я не прав.

  • 0
    Спасибо за продукт и статью! К сожалению, сейчас мало пишу на С++, но но пару раз использовал trial PVS-Studio, было очень полезно, особенно при переносе с 32 на 64bit.
    Еще в постах очень рисунки стильные. Кто автор, если не секрет?
    Что касается symbolic execution. У вас свой engine или сторонний? Какие ограничения? Как с path explosion боретесь?
    • +2
      Автор картинок найден на фрилансе, но часто мы сами что-то комбинируем, правим. Автор не стал выкладывать единорогов в резюме (возможно стесняется :), так что я, пожалуй, не буду давать ссылку.

      По поводу symbolic execution. У нас всё своё. Ограничений и недоработок много, но мы постоянно улучшаем эти механизмы. С path explosion боремся, представляя значения переменных как диапазон значений/множество значений. Т.е. в каждой точке мы знаем, какой диапазон значений может иметь та или иная переменная. На самом деле всё сложнее. И да, у такого подхода есть свои проблемы. Зато быстро, так как не надо вновь и вновь анализировать одни и те-же участки кода с разным набором значений переменных. Хотя это не помогает, например, при раскрытии шаблонов и бывает надо заново анализировать класс при инстанцировании его другой константой.
      • 0
        Добавьте в ЧАВО :)
        У меня почему-то тоже при чтении именно этой статьи (из многих ваших прочитанных) возник именно этот вопрос
  • 0
    В примере со строками вы говорите, что
    Программист хотел проверить, что все символы в строке являются заглавными. Код явно содержит какую-то логическую ошибку, так как ранее все символы этой строки были преобразованы в нижний регистр.

    А что если программист хотел именно проверить, что строка не изменяется при изменении регистра, например, состоит из небуквенных символов и цифр (на это намекает название переменной insensitiveOverride )? Тогда код вполне корректный.
    • +1
      Быть может, но это у него тоже не получится. Посмотрите код внимательнее. Одна строка всегда в нижнем регистре. Другая всегда в верхнем. Сравнивать их не имеет смысла.
      • +2
        Так ведь о том и речь. Например, так:
        string value = "*123*";
        string lowerValue = value.ToLower(); // lowerValue == "*123*"
        string upperValue = lowerValue.ToUpper(); // upperValue == "*123*"
        bool insensitive = lowerValue == upperValue; // true
        

        и так:
        string value = "aBc123";
        string lowerValue = value.ToLower(); // lowerValue == "abc123"
        string upperValue = lowerValue.ToUpper(); // upperValue == "ABC123"
        bool insensitive = lowerValue == upperValue; // false
        

        Если, конечно, я правильно понимаю, как работают функции такого типа.
        • +1
          Согласен. Поспешил. Тогда будем просто считать, что это код, который стоит лишний раз проверить. :) Надо было выбрать какой-то другой пример.
      • 0

        Ну почему же. Для строки "0123456789.,;!@#$%^&*()" условие будет выполняться.

  • 0
    Спасибо за статью!
    Кстати в ней упоминается FCEUX а была когда нибудь статья по его проверке, я что то не нашёл.
    • 0
      Не было. Быть может интересных ошибок мало или сам проект маленький, не помню уже.
  • +2
    Кстати, под новый год была опубликована статья "Как 10 лет назад начинался проект PVS-Studio". Возможно в суматохе предпраздничных дней кто-то из наших читателей её пропустил. Поэтому решил напомнить. Желаю приятного чтения.
  • –2
    Не использовать clang для разбора C++ — вот тупиковый путь
    • +3
      На самом деле это очень спорное утверждение. Переход на Clang повлечёт огромную работу объёмом в многие человеко-годы. Т.е. только через 2-3 года мы будем иметь тоже самое, что и сейчас (причём в лучшем случае). У нас нет этих лишних лет. Лучше за это время мы сделаем что-то полезное и новое. Причем, не известно, что в результате будет легче поддерживать: свой движок или накатывать тысячи патчей на каждую новую версию Clang. Про тысячи патчей я не придумываю. Я знаю из статей и личного общения, что этим обречены заниматься авторы анализаторов кода, которые решили строить своё решение на основе сторонних движков. Причин появления всех этих подпорок несколько. Например, надо поддерживать экзотические расширения, существующие в других компиляторов. В данном случае, ими будут Visual C++ и GCC. Правки нужны и для того, чтобы добраться до определённой информации или узнать что-то хитрое, о чем не думали разработчики Clang. Причем все эти патчи будет невозможно пропихнуть в основную ветку, так как никому кроме разработчиков анализатора они не нужны. А поддерживать в актуальном состоянии тысячи патчей — та ещё работёнка.
      • –1
        Я знаю из статей и личного общения, что этим обречены заниматься авторы анализаторов кода, которые решили строить своё решение на основе сторонних движков.

        Можете рассказать о таких решениях? Я не слышал.
        clang успешно поддерживает расширения microsoft. О поддержке gcc я вообще молчу.
        И не надо пугать сообщениями про тысячи патчей.
        На что конкретно вы завязываетесь при использовании clang?
        На дерево разбора, не так ли?
        Вместо того, чтобы работать непосредственно над анализом кода, будете вручную писать поддержку идущего в народ C++17, которая займет не меньше времени.
        Почему тогда заиспользовали Roslyn для C#?
        Да потому, что сэкономили кучу времени, запилив за месяц свой анализатор на готовом движке.
        Причем все эти патчи будет невозможно пропихнуть в основную ветку, так как никому кроме разработчиков анализатора они не нужны.

        Пробовали?
        • +2
          Можете рассказать о таких решениях? Я не слышал.
          Например, в статье Coverity от 2010 года говорится, что они вставляют #ifdef COVERITY в 406 мест. Думаю, со временем всё становится только хуже. Я слышал от разработчиках других анализаторов о тысячах вставок. Пруфов не будет, так как обычно про такие вещи разработчики в статьях не пишут.

          clang успешно поддерживает расширения microsoft. О поддержке gcc я вообще молчу.
          Ха! Это теоретически. А на практике даже работа препроцессоров бывает не совместима, и мы с этим мучаемся. Именно поэтому плагин PVS-Studio для Visual Studio, в начале мы пытаемся препроцессировать файлы с помощью Clang, а если не получается, то запускается cl (Visual C++). Про нестандартные расширения, которые даже бывают толком нигде не описаны, я вообще молчу. А поддерживать их надо, так как они могут использоваться в системных заголовочных файлах.

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

          По поводу на что завязываемся… Да просто надо всё заново переписать. А потом вечно патчить. И поверьте, писать поддержку новых конструкций языка не так сложно по сравнению с объемом прочих работ. Собственно, мы уже много лет это успешно делаем.

          Почему тогда заиспользовали Roslyn для C#?
          Потому, что это дало возможность быстро сделать анализатор. И за это решение мы уже платим большим количеством сложностей и неудобств, связанных с постоянным изменением самого Roslyn. Например, JB не стали брать Roslyn, осознавая какую головную боль он им даст и продолжают развивать собственный движок.

          Пробовали?
          Пробовали. Байтораздерающий процесс.
          • 0
            Можете написать или посоветовать статью про нюансы препроцессора в gcc/clang/VS? В стандарте препроцессор описан очень кратко, значит, простор для реализации большой. На форумах я видел жалобы, что программа собранная в gcc (без использования специфичных расширений) при сборке clang не проходит тесты, но там было совсем немного и без разбора.
            • +1
              Я не встречал статью, где бы рассматривался этот вопрос. Сам тоже не писал, так как не вижу практической пользы.
        • –2
          clang не может корректно переварить исходники для gcc. Я имею в виду встроенное построение дерева.
          Часть расширений он просто игнорирует, на пример некоторые атрибуты.
          • –1
            Я думаю, что автор под «поддержать нестандартные расширения» подразумевал именно — «надо сделать так, чтобы парсер не падал при встрече таких лексем в коде».
            Clang, даже если что-то не поддерживает, не падает и дает проанализировать дерево, которые смог построить. Для PVS-Studio кажется будет вполне достаточно
  • +1
    PVS-Studio не использует непосредственно математический аппарат грамматик для поиска ошибок. Анализатор работает на более высоком уровне. Анализ выполняется на основании дерева разбора.

    Не совсем понятно как с помощью грамматик искать ошибки. Я думал, что они используются для генерации парсеров, которые как раз и строят дерево разбора.

  • +2
    Сделал обзорную презентацию о том, что представляет PVS-Studio на начало 2017 года. Можно быстро узнать, какие возможности предоставляет анализатор.
  • 0
    Спасибо за статью,
    было бы интересно узнать сравнение с Facebook Infer, и в целом отношение к separation logic, на которой в последнее время строят статические анализаторы.
    • +1
      На Facebook Infer мы практически не смотрели. На первый взгляд, это достаточно ограниченный анализатор, заточенный для поиска небольшого количества паттернов ошибок. У нас же около 300 диагностик, которые подходят для C. Сравниваться с ним мы можем только на языке Си, что не очень интересно.

      По поводу «separation logic, на которой в последнее время строят статические анализаторы». Это последнее время, наверное лет 20 :). Сейчас уже никто не пишет анализаторы, на таких технологиях, как регулярные выражения и т.п. Вернее некоторые пишут, но говорить о их серьёзности смысла нет. Сейчас любой статический анализатор в том или ином виде пытается учитывать значения переменных, путаются понять на что указывает указатель и т.д. В любом случае я не силён в умных словах, так как мне не требуется писать статьи в научные журналы. :)

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

Самое читаемое Разработка