ГИБРИДНЫЙ МЕТОД ПОИСКА УТЕЧЕК РЕСУРСОВ В ПРОГРАММАХ НА ЯЗЫКЕ C

HYBRID METHOD OF RESOURCE LEAK DETECTION FOR C PROGRAMS

Denis Isaev

master of engineering and technology, Bauman Moscow State Technical University, Department of “Computer software and information technology”,

Russia, Moscow

Igor Lomovskoy

senior Lecturer, Bauman Moscow State Technical University, Department of “Computer software and information technology”,

Russia, Moscow

АННОТАЦИЯ

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

ABSTRACT

A hybrid method of resource leak detection in C programs. The method consists of two steps. The first step is to perform static analysis to look for potential leaks. In the second step of the method a dynamic analysis is performed to check for potential leaks. If the leak is confirmed, it returns information about the conditions of its reproduction. Implementation has been researched on the works of students.

Ключевые слова: статический анализ, динамический анализ, гибридный анализ, поиск утечек, valgrind, gcc, gcov, python, gcc-python-plugin, clang, cppcheck.

Keywords: static analysis, dynamic analysis, hybrid analsysis, leaks search, valgrind, gcc, gcov, python, gcc-python-plugin, clang, cppcheck.

Введение

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

У статического анализа есть существенный недостаток: наличие ложноположительных срабатываний. В динамическом анализе тоже могут присутствовать ложноположительные срабатывания, но их количество значительно ниже [13]. Поэтому для решения проблемы ложноположительных срабатываний статического анализа в данной работе применяется динамический анализ.

Подобный гибридный подход с успехом используется во многих работах. Например, в работе [7] подобный метод используется для обнаружения утечек памяти во встраиваемых системах. При этом для динамического анализа используется собственная виртуальная платформа. В работе [11] используется схожий метод для обнаружения утечек динамической памяти. Основное отличие от работы [7] заключается в том, что статический анализ производится над дизассемблированным кодом. В работах [12; 16] используются схожие методы для решения других задач: поиска уязвимостей в коде и автоматического распараллеливания программ.

Адаптация гибридного метода для поиска утечек ресурсов

Предлагаемый гибридный метод изображен в виде диаграммы на рисунке 1.

Рисунок 1. Диаграмма для гибридного метода

Метод фактически состоит из двух шагов: статического анализа для поиска возможных утечек (блок A1) и динамического анализа для подтверждения каждой из возможных утечек (блоки A3 – A6).

Для выполнения статического анализа используется алгоритм с конструированием графа состояний из графа потока управления для поиска ошибочных состояний в нем [1]. Для уменьшения числа ложноположительных срабатываний используется реалистичная модель памяти [18]. При этом поддерживается поиск утечек следующих видов ресурсов:

• файловый поток (fopen/fclose);
• файловый дескриптор (open/close);
• динамическая память (malloc/free).

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

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

Как отмечалось выше, чтобы динамический анализ был эффективным, необходимы входные данные для воспроизведения всех возможных ситуаций, возникающих в программе. Задача генерации таких данных решается следующим образом (блоки A3, A4).

Выполняется компиляция программы с инструментацией для замера покрытия кода. Этот шаг необходим для того, чтобы дальше можно было измерять покрытие выполненного кода. В данной работе за основу меры покрытия взято покрытие операторов, то есть множество строк исходного кода, которые были выполнены [2]. Для ускорения работы с покрытием операторы, расположенные внутри одного базового блока [4] объединяются в один, таким образом, используется покрытие базовых блоков программы. Порядок прохождения через базовые блоки не учитывается.

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

Для генерации аргументов командной строки алгоритм использует набор ограничений на значения аргументов командной строки (argv) и их количество (argc). Для получения набора ограничений статический анализатор применяет SMT-решатель [15]. В процессе выполнения статического анализа, если встречается условный оператор, то условие из этого оператора добавляется в текущий набор ограничений SMT-решателя. Разработанный SMT-решатель проверяет возможность выполнимости данного условия и распространяет это условие на все связанные переменные. Поддерживаются только следующие виды ограничений: <, <=, ==, !=, >, >=. С помощью набора ограничений генерируется аргументы командной строки. Если часть ограничений неизвестна, например, известно только требуемое количество аргументов, но не их значения, то неизвестные аргументы генерируются случайным образом.

На рисунке 2 изображен пример работы SMT-решателя. В правой части рисунка построен граф состояний для листинга из левой части. В каждом узле графа состояний отображен текущий набор ограничений, и к каждому узлу добавлен узел, показывающий текущую строчку кода. Красным цветом в листинге выделены недостижимые строки кода, соответствующие им состояния отмечены в графе красным цветом. В выделенных вершинах графа состояний ограничения являются противоречивыми (например, argc < 4 и argc > 5), что является критерием недостижимости соответствующих строк кода. Если SMT-решатель не участвует в анализе, то выделенные строки кода будут считаться достижимыми, и из-за этого в них будут обнаружены ложные утечки.

Рисунок 2. Пример работы SMT-решателя

Для генерации списка пустых файлов (как уже отмечалось, важен только факт наличия или отсутствия файла) выполняется поиск вызовов функции fopen в трассе утечки. При обнаружении состояния, в котором происходит выполнение данного вызова, рассматриваются ограничения на оба аргумента этого вызова: имя файла и режим открытия. С помощью ограничений на имя файла можно понять, что оно является константным, либо приходит из определенного аргумента командной строки. Более сложная логика на данный момент не поддерживается. Зная режим открытия файла, можно отбрасывать файлы, открываемые в режиме на запись, так как они будут созданы, даже если еще не существуют.

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

Утечка динамической памяти, присутствующая в этом примере, выделена красным цветом в листинге. Сначала алгоритм генерации входных данных обнаруживает ограничения на переменную argc, она не равна четырем, это означает, что для воспроизведения утечки необходимо передать программе три аргумента (не 4, так как первый аргумент это имя программы). Далее алгоритм обнаруживает, что на первый аргумент (argv [1]) наложено ограничение: он равен строке “password” из-за соответствующего сравнения (strcmp(argv [1], “password”)). Далее алгоритм обнаруживает вызовы fopen, которые открывают файлы с именами, пришедшими как второй и третий аргументы. При этом алгоритм генерирует имена файлов (f1.txt и f2.txt), запоминает их как второй и третий аргументы командной строки и отмечает, что файлы должны существовать.

Рисунок 3. Пример работы алгоритма генерации входных данных

Алгоритм генерации входных данных представлен в виде псевдокода в листинге 1.

Листинг 1. Псевдокод алгоритма генерации входных данных

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

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

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

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

Реализация гибридного метода

Для реализации статического анализа используется библиотека gcc-python [9]. На языке python [14] версии 3.4 разработан анализатор, который использует gcc [8] версии 4.9.3 для получения графа потока управления. Изначально использовалась версия gcc 4.8.2, но из-за ошибки в этой версии gcc было невозможно отключить ssa оптимизации.

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

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

1. Обертка для запуска анализатора из терминала – реализована, как и статический анализатор, на языке Python 3.4.
2. Модуль компиляции программы с инструментацией для замера покрытия кода – используются флаги “-fprofile-arcs -ftest-coverage” компилятора gcc. Если программу не удается скомпилировать, то динамический анализ не выполняется.
3. Блок генерации входных данных (А4) – реализован на языке Python 3.4. Используется паттерн «цепочка обязанностей» [3] для реализации независимых модулей генерации входных данных для каждого из типов входных данных.
4. Блок замера покрытия кода (А5) – используется программа gcov [10], которая запускается из динамического анализатора. Ее вывод разбирается с помощью регулярных выражений. Изначально был разработан модуль для valgrind [17] для замера покрытия кода без дополнительной компиляции, но от этого варианта пришлось отказаться из-за слишком медленной работы valgrind.
5. Блок подтверждения утечек (А6) – используется программа valgrind. Она запускается со следующими флагами: “--tool=memcheck --leak-check=full --track-fds=yes”. С помощью регулярных выражений анализатор обрабатывает ее вывод и понимает, что утечка воспроизвелась. Использовать код возврата valgrind без разбора вывода оказалось невозможным из-за того, что valgrind производит ложноположительные срабатывания об утечке файловых дескрипторов 0, 1 и 2. Данные файловые дескрипторы игнорируются при анализе вывода valgrind.

Исследование реализации метода на работах студентов

Все исследования проводились в операционной системе Ubuntu 14.04 с компилятором gcc 4.9.3. Операционная система была запущена в виртуальной машине, которой было выделено 3 Гбайт оперативной памяти и одно ядро процессора Inter Core i5 с частотой 2.4 ГГц.

Для исследования разработанного анализатора на работах студентов были автоматизированно загружены лабораторные работы 85 студентов по предмету «Программирование на Си». Загруженные работы содержали 2149 файлов исходного кода на языке C. Процесс выбора этих работ подробно описан в работе [1].

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

В данном разделе производится сравнение разработанного анализатора (далее он обозначается как gsa) с существующими статическими анализаторами кода clang sa [5] и cppcheck [6]. Разработанный анализатор используется в двух режимах: только статический анализа и гибридный анализ с показом только подтвержденных утечек.

Сравнение производится по следующим параметрам:

• p – точность поиска утечек (количество правильных срабатываний разделить на количество найденных утечек);
• r – полнота поиска утечек (количество правильных срабатываний разделить на количество существующих утечек);
• u – кол-во уникальных правильных утечек;
• t – среднее время выполнения анализа;
• m – максимальный объем резидентной памяти.

Результаты сравнения приведены в таблице 1.

Таблица 1.

Результаты сравнения

Анализатор gsa потребляет памяти больше, чем остальные анализаторы. Это вызвано большим потреблением памяти самим компилятором gcc и использованием языка Python, использующего сборщик мусора, который освобождает память лишь в определенные моменты времени. В то время как cppcheck и clang sa написаны на языке C++ и не используют сборщик мусора.

Для ускорения работы разработанного анализатора были проведены улучшения, позволившие уменьшить потребление памяти на 10 %, среднее время анализа в 29 раз, медианное время анализа в 19 раз по сравнению с предыдущей версий анализатора. Тем не менее, разработанный анализатор работает в среднем на 57 % медленнее, чем анализатор clang и на 99% медленнее, чем анализатор cppcheck.

Заключение

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

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

Список литературы:

1. Исаев Д.С., Ломовской И.В. Разработка алгоритма поиска утечек ресурсов в программах на языке C. – [Электронный ресурс]: Молодежный научно-технический вестник. URL: http://sntbul.bmstu.ru/doc/746265.html (Дата обращения: 9.05.2016).
2. Покрытие кода. – [Электронный ресурс]: Wikipedia. URL: https://ru.wikipedia.org (Дата обращения: 14.06.2016).
3. Цепочка обязанностей. – [Электронный ресурс]: Wikipedia. URL: https://ru.wikipedia.org (Дата обращения: 03.07.2016).
4. Basic Blocks and Flow Graphs. – [Электронный ресурс]: Arizona Computer Science. URL: http://www.cs.arizona.edu/~collberg/Teaching/453/2009/Handouts/Handout-15.pdf (Дата обращения: 26.06.2016).
5. Clang Static Analyzer. – [Электронный ресурс]: Clang Static Analyzer. URL: http://clang-analyzer.llvm.org/ (Дата обращения: 9.05.2016).
6. Cppcheck A tool for static C/C++ code analysis. – [Электронный ресурс]: Cppcheck. URL: http://cppcheck.sourceforge.net/(Дата обращения: 9.05.2016).
7. Early Phase Memory Leak Detection in Embedded Software Designs with Virtual Memory Management Model – [Электронный ресурс]. http://www.ep.liu.se/ecp/090/005/ecp13090005.pdf.
8. GCC. – [Электронный ресурс]: GCC. URL: https://gcc.gnu.org/ (Дата обращения: 03.07.2016).
9. Gcc-python-plugin. – [Электронный ресурс]: Github. URL: https://github.com/davidmalcolm/gcc-python-plugin (Дата обращения: 03.07.2016).
10. Gcov. – [Электронный ресурс]: Wikipedia. URL: https://en.wikipedia.org/wiki/Gcov (Дата обращения: 03.07.2016).
11. Hybrid Analysis of Executables to Detect Security Vulnerabilities – [Электронный ресурс]. http://www.security.iitk.ac.in/contents/events/workshops/iitkhack09/papers/anchal.pdf.
12. Kevin A. Roundy and Barton P. Miller. Hybrid analysis and control of malware. – [Электронный ресурс]: Computer Sciences Department University of Wisconsin. URL: http://ftp.cs.wisc.edu/paradyn/papers/Roundy10Malware.pdf (Дата обращения 14.06.2016).
13. Michael D. Ernst. Static and dynamic analysis: synergy and duality. – [Электронный ресурс]: University of Washington Computer Science & Engineering. URL: https://homes.cs.washington.edu/~mernst/pubs/staticdynamic-woda2003.pdf (Дата обращения 14.06.2016).
14. Python programming language. – [Электронный ресурс]: Python. URL: https://www.python.org/ (Дата обращения: 03.07.2016).
15. Satisfiability modulo theories. – [Электронный ресурс]: Wikipedia. URL: https://en.wikipedia.org/wiki/Satisfiability_modulo_theories (Дата обращения: 03.07.2016).
16. Silvius Rus, Lawrence Rauchwerger and Jay Hoeflinger. Hybrid Analysis: Static & Dynamic Memory Reference Analysis – [Электронный ресурс]: Texas A&M University. URL: https://parasol.tamu.edu/publications/download.php?file_id=340 (Дата обращения 14.06.2016).
17. Valgrind home. – [Электронный ресурс]: Valgrind. URL: http://valgrind.org/ (Дата обращения: 03.07.2016).
18. Zhongxing Xu. A Memory Model for Static Analysis of C Programs. – [Электронный ресурс]: Персональный веб-сайт. URL: http://lcs.ios.ac.cn/~xzx/memmodel.pdf (Дата обращения: 9.05.2016).