Создание плагина для Clang Static Analyzer для поиска целочисленных переполнений


    Автор статьи: 0x64rem


    Вступление


    Полтора года назад у меня появилась идея реализовать свой фазер в рамках дипломной работы в университете. Я начала изучать материалы про графы потока управления, графы потока данных, символьное исполнение и т.д. Далее шёл поиск тулз, проба разных библиотек (Angr, Triton, Pin, Z3). Ничего конкретного в итоге не получилось, пока этим летом я не отправилась на летнюю программу Summer of Hack 2019 от Digital Security, где в качестве темы проекта мне было предложено расширение возможностей Clang Static Analyzer. Мне показалось, что эта тема поможет мне расставить по полкам мои теоретические знания, приступить к реализации чего-то существенного и получить рекомендации от опытных менторов. Далее я расскажу вам, как проходил процесс написания плагина и опишу ход своих мыслей в течение месяца стажировки.


    Clang Static Analyzer


    Для разработки Clang предоставляет три варианта интерфейсов для взаимодействия:


    • LibClang — высокоуровневый C интерфейс, который позволяет взаимодействовать с AST, но не полноценно. Хороший вариант, если вам требуется взаимодействие с другим языком (например, реализация bindings) или стабильный интерфейс.
    • Clang Plugins — динамические библиотеки, вызываемые во время компиляции. Даёт полноценно манипулировать AST.
    • LibTooling — библиотека для создания отдельных инструментов на основе Clang. Также даёт полный доступ к взаимодействию с AST. Полученный код можно запускать вне среды сборки проверяемого проекта.

    Так как мы собираемся расширять возможности Clang Static Analyzer, то выбираем реализацию плагина. Писать код для плагина можно на C++ или Python.


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


    Для моей задачи требуется детальный анализ кода, поэтому для разработки был выбран C++. Далее идёт знакомство с инструментом.


    Clang Staic Analyzer (далее CSA) — инструмент для статического анализа C/C++/Objective-C кода, работающий на основе символьного исполнения. Анализатор можно вызвать через фронтенд Clang'а, добавив флаги -cc1 и -analyze к команде сборки, или через отдельный бинарь scan-build. Кроме самого анализа, CSA даёт возможность генерировать наглядные html-отчёты.


    # команда, чтобы посмотреть флаги для фронтенда clang'а
    clang -cc1 --help
    # запуск CSA способ №1
    clang++ -cc1 -x c++ -load path/to/Checker.so -analyze -analyzer-checker=test.Me -analyzer-config $BUILD_OPTIONS Checker.cpp  

     # запуск CSA способ №2
    scan-build -load-plugin path/to/Checker.so -enable-checker test.Me $BUILD_COMMAND

     # пример генерации отчёта для встроенного чекера DivideZero
    clang++ -cc1 -analyze -analyzer-checker=core.DivideZero -o reports div-by-zero-test.cpp

    пример отчёта


    CSA имеет отличную библиотеку для синтаксического анализа исходного кода при помощи обхода AST (Abstract Syntax Tree), CFG (Control Flow Graph). Из структур далее можно увидеть декларации переменных, их типы, использование бинарных и унарных операторов, можно получать символьные выражения и т.д. Мой плагин будет использовать функционал AST классов, такой выбор будет обоснован далее. Ниже перечислен список классов, который был использован в реализации плагина, список поможет получить первичное понимание о возможностях CSA:


    • Stmt — сюда относятся бинарные операции.


    • Decl — объявление переменных.


    • Expr — хранит левые, правые части выражений, их тип.


    • ASTContext — информация о дереве, текущей ноде.


    • Source manager — информация о фактическом коде, который соответствует части дерева.


    • RecursiveASTVisitor, ASTMatcher — классы для обхода дерева.


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



    Поиск целочисленных переполнений


    Чтобы начать реализовывать плагин, нужно выбрать задачу, которую он будет решать. Для этого случая сайт llvm предоставляет списки потенциальных чекеров, также можно доработать существующие стабильные или альфа чекеры. В ходе ознакомления с кодом имеющихся чекеров, стало понятно, что для более успешного освоения libclang лучше написать свой чекер с нуля, поэтому выбор делался из листа нереализованных идей. В итоге был выбран вариант создания чекера для детекта целочисленных переполнений (integer overflow). В Clang уже есть функционал для предупреждения этой уязвимости (для его применения указывают флаги -ftrapv, -fwrapv и подобные), он встроен в компилятор, и такой выхлоп сыпется в warnings, а туда смотрят нечасто. Ещё есть UBSan, но это санитайзеры, их используют не все, и этот метод — про выявление проблем во время исполнения, а плагин для CSA работает во время компиляции, анализируя исходники.


    Далее идёт сбор материала по выбранной уязвимости. Прежде integer overflow казалось чем-то простым и не серьёзным. На самом деле, уязвимость занятная и может иметь внушительные последствия.
    Целочисленные переполнения — это тип уязвимостей, в результате которых данные целочисленного типа в коде могут принимать неожиданные значения. Overflow — если переменная стала больше, чем это было задумано, Underflow — меньше, чем её первоначальный тип. Такие ошибки могут появляться как из-за программиста, так и из-за компилятора.


    В C++ во время операции сравнения арифметики целочисленные значения приводятся к одному типу, чаще к большему по разрядности. И такие приведения происходят везде и постоянно, они могут быть явными или неявными. Есть несколько правил, по которым происходят приведения [1]:


    • Преобразование со знаком в тип со знаком, но большей разрядности: просто добавляются старшие разряды.
    • Преобразование целого со знаком в целое без знака одной разрядности: отрицательное преобразуется в положительное и примет новое значение. Пример подобной ошибки в DirectFB — CVE-2014-2977.
    • Преобразование целого со знаком в целое без знака большей разрядности: сначала разрядность расширится, затем, если число отрицательное, то оно некорректно поменяет значение. Например: 0xff (-1) станет 0xffffffff.
    • Целое без знака в целое со знаком той же разрядности: число может поменять значение, в зависимости от значения старшего бита.
    • Целое без знака в целое со знаком большей разрядности: сначала повышается разрядность беззнакового числа, потом перевод в знаковое.
    • Понижающее преобразование: биты просто усекаются. Это может сделать беззнаковые значения отрицательными и прочее. Пример такой уязвимости в PHP.

    Т.е. триггером для уязвимости может послужить небезопасный пользовательский ввод, некорректная арифметика, неверное приведение типа, вызванное программистом или компилятором в ходе оптимизации. Также возможен вариант time bomb, когда фрагмент кода безобиден с одной версией компилятора, но с выходом нового алгоритма оптимизации "взрывается" и вызывает непредвиденное поведение. В истории уже был такой случай с классом SafeInt (очень иронично) [5, 6.5.2].


    Целочисленные переполнения открывают широкий вектор: возможно заставить выполнение пойти по другому пути (если переполнение затрагивает условные операторы), вызвать переполнение буфера. Для наглядности можно ознакомиться с конкретными CVE, посмотреть их причины, последствия. Естественно искать лучше integer overflow в опенсорных продуктах, чтобы не только описание читать, но и код посмотреть.


    • CVE-2019-3560 — Integer overflow в Fizz (проект, реализующий TLS для Facebook) можно было эксплуатировать уязвимость для DoS-атак, используя скрафченный сетевой пакет.
    • CVE-2018-14618 — Переполнение буфера в Curl'е вызывалось целочисленным переполнением из-за длины пароля.
    • CVE-2018-6092 — На 32-битных системах уязвимость в WebAssembly для Chrome позволяла осуществлять RCE через специальную HTML-страницу.

    Чтобы не изобретать велосипеды, был рассмотрен код для детектирования integer overflow в статическом анализаторе CppCheck. Его подход следующий:


    1. Определить, является ли выражение бинарным оператором.
    2. Если да, то проверить, оба ли аргумента имеют целочисленный тип.
    3. Определить размер типов.
    4. Проверить при помощи вычислений, может ли значение выйти за свои границы максимума или минимума.
      Но на этом этапе это не дало ясности. Получается много разных сюжетов, и от этого систематизация информации становится сложнее. На свои места всё поставил список CWE. Всего на сайте выделено 9 типов integer overflow:
      • 190 — integer oveflow
      • 191 — integer underflow
      • 192 — integer coertion error
      • 193 — off-by-one
      • 194 — Unexpected Sign Extension
      • 195 — Signed to Unsigned Conversion Error
      • 196 — Unsigned to Signed Conversion Error
      • 197 — Numeric Truncation Error
      • 198 — Use of Incorrect Byte Ordering

    Рассматриваем причину для каждого варианта и понимаем, что переполнения происходят при некорректном явном/неявном приведении. И т.к. в структуре абстрактного синтаксического дерева отображаются любые приведения, будем использовать AST для анализа. На рисунке ниже (рис. 3), видно, что любая операция, вызывающая приведение в дереве, является отдельным узлом, и, бродя по дереву, мы можем проверять все приведения типов, опираясь на таблицу с преобразованиями, которые могут вызвать ошибку.


    Sign G Sign L Sign E Unsign G Unsign L Unsign E
    Sign + - + - - -
    Unsign + - - - - +


    Конкретнее алгоритм звучит так: ходим по Cast'ам и смотрим IntegralCast (целочисленные преобразования). Если нашли подходящую ноду, смотрим на потомков в поисках бинарной операции или Decl (объявления переменной). В первом случае надо проверить знак и разрядность, которые использует бинарная операция. Во втором случае, сравнить только тип декларации.


    Реализация чекера


    Приступим к реализации. Нужен скелет для чекера, который может быть stand-alone библиотекой, а может быть собран как часть Сlang. В коде разница будет небольшой. Если вы уже собрались писать свой плагин, то рекомендую сразу прочитать небольшой pdf: "Clang Static Analyzer: A Checker Developer's Guide", там отлично описаны базовые вещи, правда, что-то может быть уже не актуально, библиотека обновляется регулярно, но базу вы схватите сразу.


    Если вы хотите добавить ваш чекер в вашу сборку clang, то необходимо:


    1. Написать сам чекер примерно с таким содержанием:


      namespace {
      class SuperChecker :  public Checker<check::PreStmt<BinaryOperator>> { // Наследовать вы 
      будете один из классов чекеров, которые имеют виртуальные функции. Задача реализовать их 
      под ваши нужды
      struct CheckerOpts { // структура для передачи входных аргументов чекера
              string FlagOne;
              int FlagTwo;
          };
          CheckerOpts Opts;
      
          //cool code
      };
      }
      
      void ento::registerSuperChecker(CheckerManager &mgr) {
      auto checker = mgr.registerChecker<SuperChecker>();
      
      // если чекеру нужны входные параметры от пользователя, то следующие 4 строчки 
      описывают это
      // этот вариант подходит только для встроенного чекера, для stand-alone пример кода 
      описан ниже.
       AnalyzerOptions &AnOpts = mgr.getAnalyzerOptions();
       SuperChecker::CheckerOpts &ChOpts = checker->Opts;
       ChOpts.FlagOne = AnOpts.getCheckerStringOption("Inp1", "", checker);
       ChOpts.FlagTwo = AnOpts.getCheckerIntegerOption("Inp2", 0, checker);
      //аргументы getCheckerIntegerOption: имя параметра, дефолтное значение, экземпляр чекера
      }

    2. Потом в исходниках Clang'а потребуется изменить файлы CMakeLists.txt и Checkers.td. Живут примерно тут ${llvm-source-path}/clang/lib/StaticAnalyzer/Checkers/CMakeLists.txt
      и тут ${llvm-source-path}/clang/include/clang/StaticAnalyzer/Checkers/Checkers.td.
      В первом нужно просто добавить имя файла с кодом, во втором нужно добавить структурное описание:


          #Checkers.td
          def SuperChecker : Checker<"SuperChecker">,
              HelpText<"test checker">,
              Documentation<HasDocumentation>;


    Если непонятно, то в файле Checkers.td достаточно примеров, как и что делать.


    Скорее всего вам не захочется пересобирать Clang, и вы прибегните к варианту со сборкой библиотеки (so/dll). Тогда в коде чекера должно быть примерно следующее:


    namespace {
        class SuperChecker :  public Checker<check::PreStmt<BinaryOperator>> { // Наследовать вы будете один из классов чекеров, которые имеют виртуальные функции. Задача реализовать их под ваши нужды
            struct CheckerOpts {
                string FlagOne;
                int FlagTwo;
            };
            CheckerOpts Opts;
            //cool code
        };
    }
    
    void initializationFunction(CheckerManager &mgr){
        SuperChecker *checker =  mgr.registerChecker<SuperChecker>();
    
      // если чекеру нужны входные параметры от пользователя, то следующие 4 строчки описывают это
        AnalyzerOptions &AnOpts = mgr.getAnalyzerOptions(); 
        TestChecker::CheckerOpts &ChOpts = checker->Opts;
        ChOpts.FlagOne = AnOpts.getCheckerStringOption("Inp1", "", checker); 
        ChOpts.FlagTwo = AnOpts.getCheckerIntegerOption("Inp2", 0, checker);
      //аргументы getCheckerIntegerOption: имя параметра, дефолтное значение, экземпляр чекера
    }
    
    extern "C" void clang_registerCheckers (CheckerRegistry &registry) {
        registry.addChecker(&initializationFunction, "test.Me", "SuperChecker description", "doc_link"); 
    }
    
    extern "C" const  char  clang_analyzerAPIVersionString [] = "8.0.1"; 

    Далее собираете свой код, можно написать свой скрипт для сборки, но если у вас возникают какие-то проблемы с этим (как это было у автора :) ), то можно по-странному использовать Makefile в исходниках clang'a и команду make clangStaticAnalyzerCheckers.


    Далее вызываем чекер:


    • для встроенных чекеров


      clang++ -cc1 -analyze -analyzer-checker=core.DivideZero test.cpp

    • для внешних


      clang++ -cc1 -load ${PATH_TO_CHECKER}/SuperChecker.so -analyze -analyzer-checker=test.Me -analyzer-config test.Me:UsrInp1="foo" test.Me:Inp1="bar" -analyzer-config test.Me:Inp2=123 test.cpp

      На этом этапе у нас есть уже какой-то результат (рис. 4), но написанный код умеет детектить только потенциальные переполнения. А это значит — большое количество false positive срабатываний.




    Чтобы это исправить мы можем:


    • Ходить по графу туда-сюда и проверять конкретные значения переменных для случаев, когда у нас есть потенциальное переполнение.
    • Во время обхода AST сразу сохранять конкретные значения для переменных и проверять их когда потребуется.
    • Использовать Taint анализ.

    Чтобы подкрепить дальнейшие аргументы, стоит упомянуть, что при анализе Clang парсит также и все файлы, указанные в директиве #include, в результате размер полученного AST увеличивается. В итоге из предложенных вариантов, только один является рациональным относительно конкретной задачи:


    • Первое, требует много времени на выполнение. Хождение по дереву, поиск и подсчёт всего необходимого будет длится долго, анализировать большой проект таким кодом может стать затруднительно. Для хождения по дереву в коде мы будем использовать класс clang::RecursiveASTVisitor, который выполняет рекурсивный поиск в глубину. Оценка времени такого подхода будет , где V — множество вершин, а E — множество рёбер графа.
    • Второе — можно конечно хранить, но мы не знаем, что нам будет нужно, а что нет. Кроме этого, сами древовидные структуры, которые мы используем при анализе, требуют много памяти, поэтому расходовать такие ресурсы на что-то ещё — плохая идея.
    • Третье — хорошая идея, для такого метода можно найти достаточно исследований и примеров. Но в CSA нет готового taint'а. Есть чекер, который позже был добавлен в список альфа чекеров (alpha.security.taint.TaintPropagation) в исходниках он описан в файле GenericTaintChecker.cpp. Чекер хороший, но подходит только для известных небезопасных функций ввода-вывода из C, "помечает" только переменные, которые были аргументами или результатами опасных функций. Кроме описанных вариантов, стоит учитывать глобальные переменные, поля классов и прочее, чтобы правильно восстановить модель "распространения".

    Оставшееся время на стажировке ушло на чтение GenericTaintChecker.cpp и попытки переделать его под свои нужды. Успешно сделать это к концу срока не вышло, но это осталось задачей для доработки уже за рамками обучения в DSec. Так же в ходе разработки стало ясно, что определять опасные функции — отдельная задача, не всегда опасные места в проекте идут из каких-то стандартных функций, поэтому чекеру был добавлен флаг для указания списка функций, которые будут считаться "отравленными"/"помеченными" во время taint анализа.
    Дополнительно была добавлена проверка, является ли переменная битовым полем. Стандартными средствами CSA размер определяется по типу, и если мы работаем с битовым полем, то его размер будет иметь значение разрядности типа всего поля, а не количеству бит, указанному в декларации переменной.


    Что в итоге?


    На данный момент реализован простой чекер, способный предупреждать только о потенциальных целочисленных переполнениях. Модифицированный класс для taint анализа, над которым предстоит ещё много работы. После, нужно использовать SMT для определения переполнений. Для этого подойдёт SMT-решатель Z3, который был добавлен в сборку Clang ещё в версии 5.0.0 (судя по release notes). Для использования солвера необходимо, чтобы Clang был собран с опцией CLANG_ANALYZER_BUILD_Z3=ON, а при непосредственном вызове плагина CSA передаются флаги -Xanalyzer -analyzer-constraints=z3.


    Репозиторий с результатами на GitHub


    Ссылки:


    1. Ховард М., Лебланк Д., Вьега Дж. "24 греха компьютерной безопасности"


    2. How to Write a Checker in 24 Hours


    3. Clang Static Analyzer: A Checker Developer's Guide


    4. CSA checker development manual


    5. Dietz W. et al. Understanding integer overflow in C/C++


    Digital Security
    Безопасность как искусство

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

      +3
      Хорошо бы теперь натравить чекер на пяток популярных библиотек и посмотреть не найдёт ли он потенциальную уязвимость.
        +1

        Вопрос, чуть отходит от темы, но я когда то хотел генерировать html отчёты из warning-ов clang. Потому что scan-build выдавал только несколько ошибок а ещё были интересные предупреждения при компиляции, как их тоже в html отчёт вывести? С этими опциями запуска clang так и не разобрался в чем отличия.

          +3
          Для плагина генерация отчётов добавляется вручную через специальные классы. По сути каждый чекер индивидуально решает, в каком случае и как багрепортер сгененрирует отчёт.
          Поэтому получение отчётов о всех варнингах, возникших во время билда, таким способом не сработает.
        +1
        Для последнего есть биндинги, которые разрешают парсить исходный код, перебирать ноды полученного абстрактного синтаксического дерева, также имеют доступ к свойствам нод и могут сопоставлять ноду строке исходного кода. Такой набор подойдёт для простого чекера. Подробнее ознакомиться с кодом можно в репозитории llvm.

        А можно узнать что конкретно Python не мог делать из того что требовалось для чекера?
          +1
          В своём коде я использую встроенные функции обхода по AST, и виртуальные классы для проверки состояния например перед заходом в функцию или после использования выражения. Из python биндингов, насколько я понимаю, этого не сделать.
          Ну и для меня приятным бонусом было, что на C++ много примеров работы с CSA.

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

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