Анализ больших массивов исходных текстов программ

Аннотация

Ключевые слова

Mining software repositories (MSR), Source code repositories (SCR), code clones detection

Введение

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

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

Варианты использования

1. Поиск совпадающих или похожих фрагментов внутри одного проекта или между проектами.
   Результаты внутри проекта могут использоваться для рефакторинга. Результаты заимствований между проектами могут использоваться для проверки лицензионной чистоты кода.
2. Частота использования различных конструкций языка или библиотечных вызовов. Может использоваться для оценки необходимости поддержки устарвеших версий языковых и библиотечных возможностей. Может использоваться для оценки широты проникновения новых возможностей и востребованности языков и библиотек.
3. Динамика разработки программных проектов --- скорость увеличения кодовой базы, связь с количеством задач и ошибок. Сравнение скорости разработки проектов, использующих различные языки программирования.
4. Статистическая зависимость метрик исходного кода (например, размера функций) и количества дефектов.

Цели и задачи

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

Целью работы является исследование методов анализа больших массивов исходных текстов программ.

Задачи работы:

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

Работы

1. Разработка эскиза архитектуры платформы анализа больших массивов исходных текстов программ, включающего:
   * подсистему хранения информации об исходных текстах;
   * подключаемые модули сканирования хранилищ программных проектов и создания локальной копии репозиториев исходных текстов;
   * подключаемые модули индексирования исходных текстов и сохранения результатов;
   * подключаемые модули анализаторов и построения отчетов.
2. Определение программных интерфейсов необходимых подсистем.
3. Реализация подключаемого модуля сканирования хранилищ программных проектов --- например, для GitHub.
4. Реализация подсистемы хранения информации об исходных текстах.
5. Реализация одного подключаемого модуля индексирования исходных текстов --- например, дайджестов (хэшей) для фрагментов исходных текстов как описано в статье [1].
6. Реализация одного подключаемого модуля анализа --- например, для поиска совпадающих дайджестов/последовательностей дайджестов, то есть поиска совпадающих или похожих фрагментов исходных текстов, как описано в статье [1].
7. Реализация генератора веб-страниц, содержащих отчет о найденных совпадающих или похожих фрагментах исходных текстов.

Предполагаемый объем программной реализации --- 3000 строк на языке Java.

Компетенции

Для выполнения работы Исполнителю потребуются следующие основные компетенции:

1. Разработка архитектуры программных систем --- для разработки архитектуры платформы анализа больших массивов исходных текстов программ.
2. Использование сетевых API хранилищ программных проектов --- для получения списка репозиториев и дополнительной информации.
3. Использование систем контроля версий (SCM) таких как Git, Mercurial, Subversion --- для получения локальной копии репозитория исходных текстов.
4. Использование или разработка анализаторов исходных текстов на различных языках программирования --- для извлечения необходимой информации из исходных текстов. Например, для синтаксического анализа исходных текстов на языке Java может использоваться Eclipse JDT, содержащий возможность построения дерева абстрактного синтаксиса Java.
5. Использование хэш-функций и разработка алгоритмов построения дайджестов для фрагментов кода.
6. Разработка схем баз данных и запросов --- для хранения и последующего использования информации, извлеченной из исходных текстов.
7. Использование языка программирования общего назначения или специализированного языка программирования --- для разработки анализаторов информации, сохраненной в базе данных.
8. Использование параллельных вычислений --- для ускорения анализа.
9. Использование API (например, командной строки) существующих анализаторов исходных текстов для подключения их к анализу.
10. Использование средств построения отчетов или средств создания веб-страниц --- для построения отчетов о результатах анализа.

Литература

1. Michel Chilowicz, Etienne Duris and Gilles Roussel. Syntax tree fingerprinting: a foundation for source code similarity detection. DOI: 10.1109/ICPC.2009.5090050 Conference: The 17th IEEE International Conference on Program Comprehension, ICPC 2009, Vancouver, British Columbia, Canada, May 17-19, 2009.
   http://igm.univ-mlv.fr/~chilowi/research/syntax_tree_fingerprinting/syntax_tree_fingerprinting_ICPC09.pdf
   Весьма популярна задача поиска кода, заимствованного проектом, которую можно обобщить как задачу поиска похожих фрагментов кода. Один из достаточно эффективных методов её решения описан в этой статье.
   Метод заключается в сборе цифровых отпечатков для операторов программного кода и поиске совпадающих последовательносей отпечаков. Управлять степенью близости находимых результатов можно изменяя способ формирования отпечатков – делая их более или менее зависимыми от деталей.
   
2. Huzefa Kagd, Michael L. Collard and Jonathan I. Maletic. A survey and taxonomy of approaches for mining software repositories in the context of software evolution. JOURNAL OF SOFTWARE MAINTENANCE AND EVOLUTION: RESEARCH AND PRACTICE J. Softw. Maint. Evol.: Res. Pract. 2007; 19:77–131 Published online in Wiley InterScience (www.interscience.wiley.com). DOI: 10.1002/smr.344.
   http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.142.4190&rep=rep1&type=pdf
   Список литературы этого обзора насчитывает 106 пунктов. Он охватывает только исследования, изучающие вопросы развития программных проектов (то есть, множество ревизий программного кода и связанной с ним информации одного проекта для различных моментов времени).
3. R. Dyer, Hoan Anh Nguyen, H. Rajan, T.N. Nguyen. Boa: A language and infrastructure for analyzing ultra-large-scale software repositories. Software Engineering (ICSE), 2013 35th International Conference on; 01/2013.
   http://web.cs.iastate.edu/~design/papers/ICSE-13/icse13.pdf
   В статье описан языка запросов и необходимая инфраструктура для получения информации из больших репозиториев программных проектов. Это удобный инструмент для проверки различных гипотез, относящихся к анализу больших программных репозиториев. Реализация использует методы параллельной обработки запросов.
4. Scheidgen M., Fischer J. (2014) Model-Based Mining of Source Code Repositories. In: Amyot D., Fonseca i Casas P., Mussbacher G. (eds) System Analysis and Modeling: Models and Reusability. SAM 2014. Lecture Notes in Computer Science, vol 8769. Springer, Cham
   http://www.markus-scheidgen.de/wp-content/uploads/2014/09/ScheidgenFischer_cameraReady.pdf