АЛГОРИТМ СТАТИЧЕСКОГО ПОИСКА УТЕЧЕК ПАМЯТИ В С/C++ ПРОГРАММАХ

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

Ключевые слова: разработка программного обеспечения; C++; ошибки с указателями; утечки памяти; статический анализ.

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

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

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

Для того, чтобы улучшить потребление памяти и надежность системы в целом, необходимо выполнять поиск утечек памяти во время тестирование программного обеспечение. В настоящее время существует довольно много методов для поиска утечек памяти [1], но их все можно разделить на две группы: статический поиск и динамический поиск. Динамический поиск основан на анализе поведения программы во время ее работы [2]. Самый простой способ посчитать количество выделенной памяти и количество освобожденной памяти, это позволит узнать есть ли в программе утечки или нет. Но для того, чтобы найти место утечки нужно тщательно анализировать места выделение и освобождения памяти [3]. Способ, описанный в [4], использует технику подсчета ссылок на выделенную память, который используется в сборщике мусора в языке программирования Java.

В отличии от динамических анализаторов, статические анализаторы [5] не запускают непосредственно программу, а анализируют ее код. Основными характеристиками статических анализаторов являются точность, полнота и ресурсоемкость. Полнота вычисляется как доля обнаруженных истинных ошибок среди всех имеющихся ошибок в программе, а точность как доля правильно обнаруженных ошибок среди всех обнаруженных. Обычно эти три характеристики находятся в противоречии и нужно выбирать компромисс между ними. Например, промышленные статические анализаторы обычно ориентируются на большую точность и низкую ресурсоемкость. Распространенным алгоритмом статического анализа является абстрактная интерпретация [6]. Данный подход похож на обычную интерпретацию программы, но осуществляет анализ всех путей исполнения программы, стремясь увеличить этим полноту анализа. Для хранения переменных обычно используют так называемые абстрактные семантические домены - множество интервалов, множество указателей и т.д.

В данной работе предложен алгоритм анализа утечек памяти на основе статического анализа. Идея алгоритма состоит в том, что мы не пытаемся вычислить всю программу, а представляем программу в виде графа вызовов функций и анализируем каждую функции по отдельности. Некоторые функции выделяют память и возвращают ее наружу. Таким функциям мы припишем атрибут "new". Некоторые функции удаляют переданную в качестве параметра память. Таким функциям мы припишем атрибут "delete". Функции с атрибутом "new" мы будем обрабатывать, как оператор выделения памяти, а с атрибутом "delete" будем обрабатывать, как оператор освобождения памяти. Функции анализируется по построенному графу от листовых к их родителям, для того, чтобы в момент анализа была известна информация о вызываемых функциях.

В функциях анализируем только переменные, с которыми связано выделение или освобождение памяти. Для хранения используется метод SSA (Static Single Assigment) [7], который хранит все версии переменной, что позволяет обрабатывать такие случаи, как, например, когда в одну переменную было несколько раз выделена память, но освобождена только один раз. При анализе храним списки выделенной и освобожденной памяти. После выхода из функции сравниваем эти списки. Если в списке выделенной памяти есть переменная, которой нет в списке удаление, то это утечка памяти, кроме случая, когда функция возвращает указатель на эту память. В этом случае мы помечаем функцию атрибутом "new". Если в списке освобождаемой памяти есть переменная, которой нету ни в списке выделенной памяти, ни среди аргументов, то это лишнее удаление, что тоже является ошибкой. Если в списке освобождаемой памяти есть переменная, которая есть среди аргументов, то функция помечается атрибутом "delete".

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

Сравнение метода производилось с двумя популярными на сегодняшний день статическими анализаторам: PVS-Studio [8] и Clang Static Analyzer [9].

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

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

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

1. Müller, Rajeev Joshi Peter, and Andreas Podelski. "Verified Software: Theories, Tools, Experiments." (2012).
2. Jump, Maria, and Kathryn S. McKinley. "Cork: dynamic memory leak detection for garbage-collected languages." Acm Sigplan Notices. Vol. 42. No. 1. ACM, 2007.
3. Chen, Kung, and Ju-Bing Chen. "Aspect-based instrumentation for locating memory leaks in Java programs." Computer Software and Applications Conference, 2007. COMPSAC 2007. 31st Annual International. Vol. 2. IEEE, 2007.
4. Maebe, Jonas, Michiel Ronsse, and K. D. Bosschere. "Precise detection of memory leaks." International Workshop on Dynamic Analysis. 2004.
5. Heine, David L., and Monica S. Lam. "A practical flow-sensitive and context-sensitive C and C++ memory leak detector." ACM SIGPLAN Notices. Vol. 38. No. 5. ACM, 2003.
6. Cousot, Patrick. "Abstract interpretation." ACM Computing Surveys (CSUR) 28.2 (1996): 324-328.
7. Aho, Alfred V., Ravi Sethi, and Jeffrey D. Ullman. Compilers, Principles, Techniques. Boston: Addison wesley, 1986.
8. Статический анализатор PVS-Studio. — URL: https://www.viva64. com/ru/pvs-studio/.
9. Статический анализатор Clang Static Analyzer. — URL: https://clang-analyzer.llvm.org/.