Проверяем код динамического анализатора Valgrind с помощью статического анализатора

    Дружба статического и динамического анализаСразу скажу, что статья пишется вовсе не для того, чтобы показать, что статический анализ работает лучше, чем динамический. Такое утверждение будет неверным, так же, как и обратное. Инструменты статического и динамического анализа дополняют друг друга, а не конкурируют между собой. У тех, и у тех есть сильные и слабые стороны. Некоторые ошибки не могут обнаруживать динамические анализаторы, а некоторые — не могут найти статические. Поэтому, следует отнестись к этой заметке просто, как к очередной демонстрации возможностей PVS-Studio, а не как к сравнению двух методологий.

    Методологии динамического и статического анализа кода


    Исходный код программы содержит подсказки, которые помогают выявить ошибки. Рассмотрим простой пример:

    char *str = foo();
    if (str == '\0')

    Странно сравнивать указатель не с nullptr, NULL или хотя бы с 0, а именно с символьным литералом '\0'. Исходя из этой странности, статический анализатор кода может предположить, что на самом деле хотели проверить не то, что указатель равен 0, а то, что строка пустая. Т.е. хотели проверить, что в начале строки располагается терминальный ноль, но случайно забыли разыменовать указатель. Скорее всего окажется, что это действительно ошибка, и правильный код должен быть таким:

    char *str = foo();
    if (*str == '\0')

    При компиляции подобная информация теряется, и динамический анализатор не способен выявить эту ошибку. С точки зрения динамического анализатора, указатель проверяется на равенство NULL - беспокоиться здесь не о чем.

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

    ADOConnection* piTmpConnection = NULL;
    hr = CoCreateInstance(
                  CLSID_DataLinks,
                  NULL,
                  CLSCTX_INPROC_SERVER, 
                  IID_IDataSourceLocator,
                  (void**)&dlPrompt
                  );
    if( FAILED( hr ) )
    {
      piTmpConnection->Release();
      dlPrompt->Release( );
      return connstr;
    }

    Если функция CoCreateInstance отработала с ошибкой, то произойдёт разыменование нулевого указателя piTmpConnection. На самом деле, здесь строчка piTmpConnection->Release(); просто лишняя, так как ещё никакое соединение не создавалось.

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

    Чисто теоретически, статический анализатор обладает информацией о коде, а значит способен находить больше ошибок, чем динамический анализатор. На практике, возможности статических анализаторов ограничены объемом доступной памяти и приемлемым временем работы. Другими словами, статический анализатор может рассмотреть, как будет работать код при всех возможных вариантах входных данных. Но делать он это будет 150 лет на кластере, где вдобавок установлен невероятный объём памяти.

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

    Результаты проверки


    Мы регулярно проверяем различные проекты с целью популяризации методологии статического анализа кода, и я не мог пройти мимо такого проекта, как Valgrind. Найти в нем ошибки – это, своего рода, вызов. Это качественный, оттестированный проект, который вдобавок проверяется анализатором Coverity. Да и вообще, я уверен, что этот код проверялся энтузиастами разнообразнейшими инструментами. Так что, даже найти несколько ошибок — это большой успех.

    Давайте посмотрим, что нашел интересного анализатор PVS-Studio в коде проекта Valgrind.

    static void lk_fini(Int exitcode)
    {
      ....
      VG_(umsg)("  taken:         %'llu (%.0f%%)\n",
                taken_Jccs, taken_Jccs * 100.0 / total_Jccs ?: 1);
      ....
    }

    Предупреждение PVS-Studio: V502 Perhaps the '?:' operator works in a different way than it was expected. The '?:' operator has a lower priority than the '/' operator. lk_main.c 1014

    Оператор ?: крайне коварен, и его надо использовать очень аккуратно. Подробнее я рассуждал на эту тему в 4 главе своей небольшой книги, куда я рекомендую заглянуть. Рассмотрим, чем этот код подозрителен.

    Мне кажется, программист хотел защититься от деления на ноль. Поэтому, если переменная total_Jccs равна 0, то деление должно осуществляться на 1. Планировалось, что код будет работать так:

    taken_Jccs * 100.0 / (total_Jccs ?: 1)

    Однако, приоритет оператора ?: ниже, чем у операторов умножения и деления. Поэтому, выражение вычисляется так:

    (taken_Jccs * 100.0 / total_Jccs) ?: 1

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

    static Bool doHelperCall (....)
    {
      ....
      UInt nVECRETs = 0;
      ....
      vassert(nVECRETs ==
               (retTy == Ity_V128 || retTy == Ity_V256) ? 1 : 0);
      ....
    }

    Предупреждение PVS-Studio: V502 Perhaps the '?:' operator works in a different way than it was expected. The '?:' operator has a lower priority than the '==' operator. host_arm_isel.c 795

    Интересный случай. Оператор ?: используется неправильно, но код при этом корректен.

    Задумывалось, что проверка должна работать так:

    nVECRETs == ((retTy == Ity_V128 || retTy == Ity_V256) ? 1 : 0)

    Но работает это так:

    (nVECRETs == (retTy == Ity_V128 || retTy == Ity_V256)) ? 1 : 0

    Самое забавное, что если присмотреться, то видно, что эти проверки эквивалентны. Результат будет один и тот же.

    Аналогичные проверки находятся здесь:

    • V502 Perhaps the '?:' operator works in a different way than it was expected. The '?:' operator has a lower priority than the '==' operator. host_arm64_isel.c 737
    • V502 Perhaps the '?:' operator works in a different way than it was expected. The '?:' operator has a lower priority than the '==' operator. host_mips_isel.c 611

    typedef  ULong  DiOffT;
    typedef
       struct {
          Bool   fromC;
          DiOffT off;
          SizeT  size;
          SizeT  used;
          UChar  data[];
       }
       CEnt;
    static Bool is_sane_CEnt (....)
    {
      ....
      CEnt* ce = img->ces[i];
      ....
      if (!(ce->size == CACHE_ENTRY_SIZE)) goto fail;
      if (!(ce->off >= 0)) goto fail;                         // <=
      if (!(ce->off + ce->used <= img->real_size)) goto fail;
      ....
    }

    Предупреждение PVS-Studio: V547 Expression 'ce->off >= 0' is always true. Unsigned type value is always >= 0. image.c 147

    Член off является переменной беззнакового типа, а значит он всегда больше или равен нулю. Таким образом, условие (!(ce->off >= 0)) всегда ложно.

    static void sdel_Counts ( Counts* cts )
    {
       memset(cts, 0, sizeof(Counts));
       free(cts);
    }

    Предупреждение PVS-Studio: V597 The compiler could delete the 'memset' function call, which is used to flush 'cts' object. The memset_s() function should be used to erase the private data. cg_merge.c 324

    Видимо, для упрощения поиска ошибок в самом Valgrind, память перед освобождением заполняется нулями. Однако, в release-версии компилятор, скорее всего, удалит вызов функции memset, так как буфер больше никак не используется до вызова функции free.

    Аналогичные места, где память может не обнуляться:

    • V597 The compiler could delete the 'memset' function call, which is used to flush 'ffn' object. The memset_s() function should be used to erase the private data. cg_merge.c 263
    • V597 The compiler could delete the 'memset' function call, which is used to flush 'cts' object. The memset_s() function should be used to erase the private data. cg_merge.c 332
    • V597 The compiler could delete the 'memset' function call, which is used to flush 'cpf' object. The memset_s() function should be used to erase the private data. cg_merge.c 394

    static
    Bool dis_AdvSIMD_scalar_shift_by_imm(DisResult* dres, UInt insn)
    {
      ....
      ULong nmask = (ULong)(((Long)0x8000000000000000ULL) >> (sh-1));
      ....
    }

    Предупреждение PVS-Studio: V610 Unspecified behavior. Check the shift operator '>>'. The left operand '((Long) 0x8000000000000000ULL)' is negative. guest_arm64_toIR.c 9428

    Если сдвигаемый вправо операнд имеет отрицательное значение, результирующее значение зависит от реализации (implementation-defined). Таким образом, мы имеем дело с опасным кодом.

    Теперь рассмотрим ситуацию, когда разыменование указателя находится до его проверки на равенство NULL:

    PRE(xsm_op)
    {
       struct vki_xen_flask_op *op = (struct vki_xen_flask_op *)ARG1;
    
       PRINT("__HYPERVISOR_xsm_op ( %u )", op->cmd);            // <=
    
       PRE_MEM_READ("__HYPERVISOR_xsm_op", ARG1,
                    sizeof(vki_uint32_t) + sizeof(vki_uint32_t));
    
       if (!op)                                                 // <=
          return;
      ....
    }

    Предупреждение PVS-Studio: V595 The 'op' pointer was utilized before it was verified against nullptr. Check lines: 350, 360. syswrap-xen.c 350

    Аналогичные случаи:

    • V595 The 'sysctl' pointer was utilized before it was verified against nullptr. Check lines: 568, 578. syswrap-xen.c 568
    • V595 The 'domctl' pointer was utilized before it was verified against nullptr. Check lines: 710, 722. syswrap-xen.c 710

    Bool ML_(read_elf_debug_info) ( struct _DebugInfo* di )
    {
      ....
      if (inrw && sdynbss_present) {
        vg_assert(di->sbss_present);
        sdynbss_present = False;
        vg_assert(di->sbss_svma + di->sbss_size == svma);
        di->sbss_size += size;
        ....
      } else                                                // <=
      
      if (inrw && !di->sbss_present) {
        di->sbss_present = True;
        di->sbss_svma = svma;
        di->sbss_avma = svma + inrw->bias;
      ....
    }

    Предупреждение PVS-Studio: V705 It is possible that 'else' block was forgotten or commented out, thus altering the program's operation logics. readelf.c 2231

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

    static
    Bool doHelperCallWithArgsOnStack (....)
    {
      ....
       if (guard) {
          if (guard->tag == Iex_Const
              && guard->Iex.Const.con->tag == Ico_U1
              && guard->Iex.Const.con->Ico.U1 == True) {
             /* unconditional -- do nothing */
          } else {
             goto no_match; //ATC
             cc = iselCondCode( env, guard );
          }
       }
      ....
    }

    Предупреждение PVS-Studio: V779 Unreachable code detected. It is possible that an error is present. host_arm_isel.c 461

    Строчка кода:

    cc = iselCondCode( env, guard );

    никогда не выполняется:

    void reset_valgrind_sink(const char *info)
    {
       if (VG_(log_output_sink).fd != initial_valgrind_sink.fd
           && initial_valgrind_sink_saved) {
          VG_(log_output_sink).fd = initial_valgrind_sink.fd;
          VG_(umsg) ("Reset valgrind output to log (%s)\n",
                     (info = NULL ? "" : info));
       }
    }

    Предупреждение PVS-Studio: V547 Expression '((void *) 0)' is always false. server.c 110

    Предупреждение анализатора выглядит странно и требует пояснения.

    Нас интересует следующее выражение:

    (info = NULL ? "" : info))

    Макрос NULL разворачивается в ((void *) 0) и получается:

    (info = ((void *) 0) ? "" : info))

    Приоритет оператора ?: выше чем у оператора =, поэтому вычисления происходят следующим образом:

    (info = (((void *) 0) ? "" : info)))

    Согласитесь, что условие ((void *) 0) для оператора ?: смотрится странным, о чем и предупреждает анализатор PVS-Studio. По всей видимости, мы имеем дело с опечаткой, и код должен был быть таким:

    (info == NULL ? "" : info))

    И последний на сегодня фрагмент кода:

    void genReload_TILEGX ( /*OUT*/ HInstr ** i1,
                            /*OUT*/ HInstr ** i2, HReg rreg,
                            Int offsetB )
    {
      TILEGXAMode *am;
      vassert(!hregIsVirtual(rreg));
      am = TILEGXAMode_IR(offsetB, TILEGXGuestStatePointer());
    
      switch (hregClass(rreg)) {
      case HRcInt64:
        *i1 = TILEGXInstr_Load(8, rreg, am);
        break;
      case HRcInt32:
        *i1 = TILEGXInstr_Load(4, rreg, am);
        break;
      default:
        ppHRegClass(hregClass(rreg));
        vpanic("genReload_TILEGX: unimplemented regclass");
        break;
      }
    }

    Предупреждение PVS-Studio: V751 Parameter 'i2' is not used inside function body. host_tilegx_defs.c 1223

    Думаю, здесь забыли записать NULL по адресу i2, как это сделано в других аналогичных функциях:

    *i1 = *i2 = NULL;

    Аналогичная ошибка находится здесь:

    V751 Parameter 'i2' is not used inside function body. host_mips_defs.c 2000

    Заключение


    Спасибо всем за внимание. Попробуйте наш статический анализатор кода PVS-Studio для Linux.


    Windows разработчиков, я приглашаю сюда: PVS-Studio for Windows. Для них — всё чуть проще. Они просто могут поставить плагин для Visual Studio и проверять с помощью демонстрационной версии свои C, C++ и C# проекты.


    Если хотите поделиться этой статьей с англоязычной аудиторией, то прошу использовать ссылку на перевод: Andrey Karpov. Checking the code of Valgrind dynamic analyzer by a static analyzer

    Прочитали статью и есть вопрос?
    Часто к нашим статьям задают одни и те же вопросы. Ответы на них мы собрали здесь: Ответы на вопросы читателей статей про PVS-Studio, версия 2015. Пожалуйста, ознакомьтесь со списком.
    PVS-Studio
    372,00
    Static Code Analysis for C, C++, C# and Java
    Поделиться публикацией

    Комментарии 27

      +9
      … статический анализатор может рассмотреть, как будет работать код при всех возможных вариантах входных данных...

      На самом деле нет, потому что тогда он столкнётся с проблемой останова.
        +3
        Можно ввести ограничение: если анализатор уже год анализирует одну функцию, то предупредить, что возможен вечный цикл. Ведь я не говорил, что такой теоретический анализатор не может выдать ложное срабатывание. :)
          –3
          На самом деле нет, потому что тогда он столкнётся с проблемой останова.


          Это распространенное заблуждение. Проблема останова актуальна только для машины Тьюринга, поскольку она бесконечна. Для любой конечной системы возможно решение этой проблемы с использованием более «мощной» системы.
            0
            Если программа работает с сетью, вам потребуется более мощная система, чем весь Интернет.
              0
              Если под «анализируемой программой» подразумевается только та часть, которая исполняется непосредственно на устройстве, а не все что можно «выполнить удаленно» на другой машине в сети, то вовсе нет.
              Т.к. такая связь с сетью ничем по сути не отличается от обычного ввода/вывода и принципиально анализ программы не усложняет.

              Другое дело что сложность анализа может расти сильно нелинейно от сложности системы. Но чисто теоретически, к проблеме останова это отношения ни имеет.
          0
          Другими словами, статический анализатор может рассмотреть, как будет работать код при всех возможных вариантах входных данных. Но делать он это будет 150 лет на кластере, где вдобавок установлен невероятный объём памяти.

          А кто будет делить данные на фактор-группы? Скажем, если ошибка будет только в случае определенного совпадения байтов или чего-то еще, на что вы не будете расчитывать?

            0
            Я не обещал, что такой анализатор не будет давать ложно позитивных и ложно негативных срабатываний. :) Просто он будет работать чуть тщательнее, чем обычно.
            +6
            А вы проверяли PVS-Studio Valgrind'ом? Было ли найдено что-нибудь интересное?
              0
              Пока не пробовали. Там ожидаемо будет 100500 утечек памяти, так как узлы дерева не удаляется в процессе работы, так как построенное дерево используется до конца работы программы. А в конце просто завершить программу, без предварительного удаления дерева. Этакая оптимизация скорости работы.
                0
                Ну, такие структуры часто заворачиваются в какой нить shared_ptr, так что как такового мемори лика нет — указатель на память не теряется, просто живет всю жизнь процесса. При выходе из main счетчик станет равен 0 и память освободится. Если же там сырой указатель, то да valgrind скажет что течет.
                  +3
                  Освобождение памяти отсутствует сознательно. Удаление сотен тысяч отдельных объектов это медленно. Впрочем, их можно почистить быстрее, так как для их выделения используется свой собственный менеджер памяти. Но даже он отключен, так как всё равно это пустая потеря времени.

                  Механизм освобождения в менеджере памяти используется только при прогоне юнит-тестов, чтобы не сжирать слишком много памяти при проверке различных тестовых *.i файлов. В случае же работы в пользовательском режиме память освобождает операционная система, завершая процесс. Такой подход экономит порядка 0.1 секунду (значение приблизительное, давно не замерял время) на запуск. Проверили 1000 файлов и вот уже экономия в 100 секунд: приятно.
                  –5
                  А как же ваше предыдущее мнение, что качество кода важнее всего? :-) Теория — это хорошо, а в реальности на рекламу на хабре у вас ресурсы есть, а вот на повышение качества кода — ресурсов нет. Даже на бесплатный Valgrind ресурсов не нашлось.

                  Неужели вы поменяли своё мнение, и теперь считаете, что лишний тестировщик выгоднее автоматической проверки? Да ещё и бесплатной?

                  Видите насколько ваши слова расходятся с делом? :-) Хотя в реальности вы правы — реклама действительно важнее качества кода.
                0

                Увидев КПДВ, я подумал было, что вы проверили код статического анализатора PVS-Studio статическим анализатором PVS-Studio :)

                  +4
                  Они это при каждом коммите делают ))
                  +1
                  Член off является переменной беззнакового типа, а значит он всегда больше или равен нулю. Таким образом, условие (!(ce->off >= 0)) всегда ложно.

                  На это автор кода может возразить, что так задумано на случай, если тип поменяется в будущем на знаковый. Учитывая, что тип поля объявлен не напрямую, а через typedef, шансы на это вполне себе возрастают. Если дальше пойдёт какая-то магия с указателями, то лучше уж при потенциальной замене типа в будущем на goto fail пойти, чем на UB напороться.


                  Кстати, вопрос вам. Такой код:


                  int cmp = compare(a, b);
                  if(cmp < 0) { ... }
                  else if(cmp == 0) { ... }
                  else if(cmp > 0) { ... }

                  Будет ли PVS-Studio ругаться в последней строчке, что условие всегда истинно?

                    0
                    Дополнительный вопрос — а если там в конце ещё один else?
                      +1
                      Анализтор промолчал в обоих случаях. Во втором случае стоит что-то сказать, взял на карандашь. Спасибо.
                        +1

                        Тогда ещё вопрос:


                        int *x = ...
                        if(x == NULL) { ... }
                        else if(x != NULL) { ... }

                        Тут тоже молчите, что x != NULL всегда истинно?

                          0
                          И здесь молчит. Хочу сказать, что мне не нравится подобные рассуждения и эксперименты на основе подобных тестов. Прошу почитать: Почему я не люблю синтетические тесты.
                            +2

                            Нет-нет, я не с целью поддеть вас, у меня исключительно профессиональный интерес ;-)

                              0
                              Нам пришлось убрать подобный код из-за предупреждений какого-то из компиляторов.

                              Сложно сказать, стоит ли так писать. Иногда (из-за паранойи) хочется туда ещё и ветку else добавить

                              if(x == NULL) { ... }
                              else if(x != NULL) { ... }
                              else {assert(false);}


                              Если у нас операторы == и != переопределены, и в переопределении есть тонкая ошибка (ну или баг в компиляторе, или полуработающий процессор) срабатывание ветки else возможно.

                              Другой момент, что я бы, пожалуй, предпочел тут ложное срабатывание статанализатора и пометку такого места руками. Потому что ляп программиста — все таки вероятнее. Ну скажем вторая проверка должна использовать хх, а не х. То есть такой код — он немного пахнет.
                                +1

                                Альтернативный вариант:


                                if(x == NULL) { ... }
                                else {
                                  assert(x != NULL);
                                  ...
                                }

                                Так вы и документировали вторую ветку (на случай если первая разрастётся), и добавили отладочную проверку. Можно бы было ещё так:


                                if(x == NULL) { ... }
                                else {
                                  assert(x != NULL); // PVS-Studio: static assert
                                  ...
                                }

                                Комментарий специального вида после ассерта должен указывать, что PVS-Studio в состоянии статически вывести, что этот ассерт всегда истинный. Если со временем окажется, что это не так (например, условие в верхнем if поменяется, а про else все забудут), то PVS-Studio начнёт ругаться, что больше не может вывести истинность утверждения, помеченного комментарием.

                                  –1
                                  Хорошая идея, но первый вариант легче читается.

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

                                  Ну изменение х из прерывания или гонку тредов он вряд ли верно поймет. Думаю, что volatile просто отключит эту проверку.
                        0
                        На это автор кода может возразить

                        Может. Это его право. Задача статического анализтора указать на подозрительный код. Задача программиста оценить это сообщение и предпринять меры, если они нужны или подавить предупреждение.
                          –1
                          В отличие от статанализа динамический анализатор, как правило, указывает на реальные ошибки. Причем ещё и те, что встречаются у большинства пользователей.
                          –5
                          Кто-то из компиляторов ругается.
                          0
                          Скорее всего окажется, что это действительно ошибка, и правильный код должен быть таким:

                          char *str = foo();
                          if (*str == '\0')


                          Мне кажется в правильном коде должна быть еще проверка на NULL, потому что указатель мы получаем из вызова foo и он вполне может оказаться нулевым. Поэтому я бы предложил такой вариант:
                          char *str = foo();
                          if (str && *str == '\0')

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

                          Самое читаемое