Cтатический анализ исходного кода

Зубов Максим Валерьевич, Старцев Евгений Владимирович, Пустыгин Алексей Николаевич – ЧелГУ, Челябинск, Russia

LVEE 2012

This paper presents current existing approaches of using programs’s representations for static analysis. This analysis can help to understand and extend open-source software. The most common approaches were implemented in prototypes with open technologies. Also class-level detailed representation was developed and implemented in prototype to prove the assumption of more effective analysis on less detailed representation.

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

Форма промежуточного представления может определяться целью анализа. В свободном проекте BLAST ¹ исходный код программы представляется виде автомата потока управления (CFA), описывающего набор состояний процедур и переходы между ними. Алгоритм анализа называется “абстракция и уточнение по контрпримерам”: создаются абстрактные деревья достижимости (ART), которые описывают возможные пути распространения управления на уровне общности, которая используется на очередной итерации алгоритма.

Наиболее распространенное промежуточное предсталение — абстрактное дерево синтаксического разбора AST ². Известные инструменты генерации парсеров, такие как ANTLR³ (используется в Checkstyle⁴ для языка Java) или специфичные инструменты, например, API компилятора ROSE⁵, поддерживающего языки C, C++ и Fortran, могут быть использованы для генерации AST. Этот подход является простым и проверенным временем. Однако, имеют место и другие подходы. Например, в проекте Pylint⁶ для языка Python может быть использован отдельный свободно-распространяемый модуль logilab-astng⁷. Авторами были разработаны 2 прототипа генератора промежуточных представлений, основанных на AST: первый, для языка Python – на основе свободного модуля logilab-astng⁷, второй, для Java – на основе компилятора javac, входящего в состав открытой реализации средств разработки на Java – OpenJDK⁸.

Другой вариант использования промежуточного представления — реляционное представление исходного кода анализируемого ПО. По грамматике исходного языка подготавливается схема реляционной базы данных, далее созданная по этой схеме база данных заполняется в соответствии с конструкциями исходного кода. Анализ сводится к выполнению произвольных запросов к этой базе. В инструментах, использующих такой тип представления, применяются различные языки запросов, как самостоятельные, например, QUEL⁹ (в OMEGA¹⁰ для Ada, C и Pascal), так и специально созданные, например, .QL ¹¹ (SemmleCode¹² для Java). В настоящее время ведется создание прототипа построителя реляционного промежуточного представления для языка Java. Применение такого представления будет очень эффективно на больших объемах данных. Идея представления в виде реляционной БД дополняется использованием логических языков в качестве языков запросов (Prolog в ASTLOG¹³, Datalog в CodeQuest¹⁴), более подходящих для анализа структур исходного кода, например, транзитивных замыканий. Запросы к базе знаний транслируются в SQL и выполняются на конкретной базе данных, либо же база данных может быть представлена в виде базы знаний. На практике используется только первый способ.

Из идей реляционного представления, а именно проведения анализа в виде выполнения запросов к исходному коду, выделилось отдельное направление. Оно стоит обособленно, так как не диктует использование конкретного представления. Оно может быть как реляционным в системе CodeQuest¹⁴, так и AST в ASTLOG¹³. Некоторые заявляют о потенциально любом представлении (PQL¹⁵). В основном, в концепции запросов к исходному коду используют логические языки как наиболее удобные и нацеленные на извлечение знаний. Известны также анализаторы, выполняющие запросы на естественном языке (английском)¹⁶.

Промежуточные представления можно классификацировать по уровню детализации. Так в академическом проекте Bauhaus project¹⁷ для языков Ada, C, C++, C# и Java имеются 2 представления — низкоуровневое InterMediate Language, описывающее конструкции языка на синтаксическом и семантическом уровнях, и Resource flow graphs, описывающее архитектурные особенности программной системы. В анализаторе, использующем PQL¹⁵, выделяется 3 уровня анализа: модель глобального программного дизайна, модель структуры программы, модель детального программного дизайна. Для создания прототипа такого представления был выбран средний уровень детализации – уровень структуры и связи классов.

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

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

За счет универсальности категорий ООП, существующих во всех объектных языках¹⁸, полученное представление является полным для своего уровня анализа и, в то же время, универсальным для объектно-ориентированных языков. Полученное высокоуровневое представление позволяет производить анализ на уровне классов и архитектуры проекта, что позволяет снизить накладные расходы на выполнение анализа по сравнению с более детализированным представлением.

Независимо от форм представлений можно выделить модель анализа с помощью моделей отражения¹⁹. Она основана на сравнении высокоуровневой модели программы, которую программист мыслит себе в процессе разработки, и фактической, полученной в результате. Этот подход не требует конкретного представления кода, и иногда может быть выполнен с использованием текстовой обработки. Так, в частности, он был реализован в одном из первых опытов применения подхода для изучения подсистемы виртуальной памяти NetBSD¹⁹. На основе этого подхода с помощью собственного генератора промежуточного представления для Python, использующего logilab-astng⁷, была построена и проанализирована высокоуровневая модель нескольких проектов с открытым исходным кодом на Python.

Литература:

¹ BLAST / mtc.epfl.ch/software-tools/blast/index-epfl.php

² Ахо А.В., Ульман Д.Д. / Компиляторы. Принципы, технологии и инструментарии. / М.: Вильямс, 2008г.

³ ANTLR / www.antlr.org

⁴ Checkstyle / checkstyle.sourceforge.net

⁵ ROSE / rosecompiler.org

⁶ Pylint / www.logilab.org/857

⁷ logilab-astng / www.logilab.org/856

⁸ OpenJDK / openjdk.java.net

⁹ Ingres 10.0 QUEL Reference guide / Ingres corp. 2010, code.ingres.com/ingres/main/src/tools/ techpub/pdf/QUELRef.pdf

¹⁰ M. Linton / Queries and Views of Programs Using a Relational Database System / www.eecs.berkeley.edu/Pubs/TechRpts/1983/5296.html

¹¹ O. de Moor, E. Hajiyev, M. Verbaere / Object-oriented queries over software systems / ACM Press, 2007.

¹² SemmleCode / semmle.com/solutions/enabling-tools-for-your-projects

¹³ R. Crew / ASTLOG: A Language for Examining Abstract Syntax Trees / Microsoft Research, 1997.

¹⁴ E. Hajiyev / CodeQuest – Source Code Querying with Datalog / St. Anne’s College, Oxford University, 2005.

¹⁵ S. Jarzabek / Design of Flexible Static Program Analyzers with PQL / IEEE Transactions on software engineering, vol. 24, no. 3, march 1998.

¹⁶ M. Kinmming, M. Monperrus, M. Mezini / Quering Source Code with Natural Language / 26th IEEE/ACM International Conference On Automated Software Engineering (ASE’2011).

¹⁷ Bauhaus project / www.bauhaus-stuttgart.de/bauhaus/index-english.html

¹⁸ И. Грэхем / Объектно-ориентированные методы. Принципы и практика / М.: Вильямс, 2004 г.

¹⁹ G.C. Murphy, D. Notkin, K. Sullivan / Software Reflexion models: Bridging the gap between source and high-level models / Third ACM SIGSOFT Symposium on the Foundations of Software Engineering, pages 18–28, New York, ACM Press, 1995.

Текст тезисов доступен под лицензией Creative Commons Attribution-ShareAlike 3.0.