Выявление признаков плагиата в исходных кодах программных систем
|
1 Введение 4
1.1 Актуальность задачи 4
1.2 Обзор литературы 5
1.3 Определения 6
1.4 Постановка задачи 7
2 Наивный алгоритм 8
3 SourcererCC 9
3.1 Обзор подхода 9
3.2 Фильтрация по пересечениям под-блоков 10
3.3 Фильтрация по позициям токенов 11
3.4 Алгоритм поиска клонов 12
3.5 Особенности данного подхода 14
4 Использование адаптивных префиксов в алгоритме SourcererCC 16
4.1 Фильтрация по адаптивным префиксам под-блоков 16
4.2 Использование фильтрации по адаптивным префиксам на практике 17
5 Практические результаты 18
5.1 Возможности программного средства potator 18
5.2 Отличия от вышеописанных алгоритмов 20
5.3 Описание моделей и абстракций используемых в пакете potator 22
5.4 Результаты работы программного средства potator 25
5.5 Описания алгоритмов используемых в программном средстве potator 26
5.5.1 Описание алгоритма субтокенизации 26
5.5.2 Описание алгоритма используемого в NaiveDetector 26
5.5.3 Описание алгоритма используемого для работы с дельта инвертированными индексами 27
5.5.4 Описание алгоритма используемого в FilteringDetector 27
6 Заключение 28
Список литературы 29
A Приложение 1. Листинг алгоритма субтокенизации 32
B Приложение 2. Листинг алгоритма используемого в NaiveDetector 33
C Приложение 3. Листинг алгоритма для работы с дельта инвертированными индексами 34
D Приложение 4. Листинг алгоритма используемого в FilteringDetector 36
1.1 Актуальность задачи 4
1.2 Обзор литературы 5
1.3 Определения 6
1.4 Постановка задачи 7
2 Наивный алгоритм 8
3 SourcererCC 9
3.1 Обзор подхода 9
3.2 Фильтрация по пересечениям под-блоков 10
3.3 Фильтрация по позициям токенов 11
3.4 Алгоритм поиска клонов 12
3.5 Особенности данного подхода 14
4 Использование адаптивных префиксов в алгоритме SourcererCC 16
4.1 Фильтрация по адаптивным префиксам под-блоков 16
4.2 Использование фильтрации по адаптивным префиксам на практике 17
5 Практические результаты 18
5.1 Возможности программного средства potator 18
5.2 Отличия от вышеописанных алгоритмов 20
5.3 Описание моделей и абстракций используемых в пакете potator 22
5.4 Результаты работы программного средства potator 25
5.5 Описания алгоритмов используемых в программном средстве potator 26
5.5.1 Описание алгоритма субтокенизации 26
5.5.2 Описание алгоритма используемого в NaiveDetector 26
5.5.3 Описание алгоритма используемого для работы с дельта инвертированными индексами 27
5.5.4 Описание алгоритма используемого в FilteringDetector 27
6 Заключение 28
Список литературы 29
A Приложение 1. Листинг алгоритма субтокенизации 32
B Приложение 2. Листинг алгоритма используемого в NaiveDetector 33
C Приложение 3. Листинг алгоритма для работы с дельта инвертированными индексами 34
D Приложение 4. Листинг алгоритма используемого в FilteringDetector 36
1.1 Актуальность задачи
Дублирование исходного кода часто возникает в процессе разработки программного обеспечения. Этот дублированный код часто называют клонами кода, а процесс - клонированием кода. Исследования показали что 20-50% современного программного обеспечения состоит из склонированого кода [1]. Считается, что клоны кода имеют отрицательное влияние на качество кода, потому что они делают поддержку кода сложнее, а так же из-за них сложнее находить и устранять программные ошибки [4][11]. Также когда клонированный код появляется в кодовой базе, он так же может быть признаком нелегального переиспользования кода. Такое нелегальное переиспользование кода в программном обеспечении с открытым исходным кодом, как правило, принимает форму нарушения лицензии. Исследования выделяют две основные причины по которым разработчики клонируют код. Первая причина состоит в том, что разработчики программного обеспечения с открытым исходным кодом переиспользуют код с целью не фокусироваться на некоторых тривиальных задачах и потому что часто ограничены во времени и ресурсах [16]. Второй причиной выделяют тот факт что существует множество заблуждений о природе лицензий программного обеспечения с открытым исходным кодом, и это проблема только усугубляется большим количеством существующих лицензий для программного обеспечения с открытым исходным, что ведет к тому, что разработчики не до конца понимают условия лицензий и разницу между ними [3]. Нарушение лицензии программного кода может быть причиной судебных разбирательств, поэтому в наличии инструментов поиска склонированного кода заинтересованы не только разработчики программного обеспечения, но и их работодатели поскольку именно они будут нести ответственность за нарушенные лицензии.
1.2 Обзор литературы
Ранние работы, затрагивающие поиск похожих фрагментов кода, использовали прямолинейные подходы для поиска возможных дубликатов кода в больших кодовых базах. В этих работах анализировались названия директорий и файлов и находились директории в которых дословно совпадает большое количество файлов с исходным кодом [7][8]. Такие подходы позволяют корректно идентифицировать точные копии проектов и хорошо расширяется на очень большие объемы данных, но такие методы невозможно применять для выявления плагиата в коде, потому что уровень похожести должен быть определен непосредственно для кода.
Одним из первых программных инструментов, позволяющим производить поиск клонированного кода на уровне функций, при этом расширяющийся на большие объемы данных является SourcererCC [14]. Этот инструмент позволял производить эффективный поиск клонов, используя анализ токенов, использующихся в исходном коде. Данное решение будет подробно рассмотрено далее в тексте, вместе с дальнейшими модификациями данного подхода. Несмотря на эффективность, подходы основанные на анализе токенов не позволяют надежно находить некоторые типы клонов, в частности они не позволяют находить структурные и семантические клоны.
Подходы для поиска дубликатов в коде с использованием структурных признаков, как правило, используют информацию, которую можно получить из синтаксического дерева и используют методы для поиска похожих поддеревьев [5], из-за чего они обладают как минимум квадратичной асимптотикой и плохо масштабируются на большие объемы кода.
Так же существуют подходы которые ищут дубликаты кода, используя семантическую информацию. Зачастую такие подходы используют алгоритмы машинного обучения. Для подходов основанных на машинном обучении крайне важным является способ извлечения признаков из кода. В качестве признаков может быть использован код в виде текста, синтаксические деревья и даже байткод [13].
1.3 Определения
Далее приведены общепринятые определения[2][12][14], используемые в рамках данной работы
Фрагмент кода: Непрерывный сегмент исходного кода, определяемый как триплет (l, s, e), где l - файл с исходным кодом, s - номер строки на котором начинается данный фрагмент, e - номер строки на котором он заканчивается.
Пара клонов: Пара похожих фрагментов кода, определяемая как триплет (fi, f2, Ф), где fi, f2 - фрагменты кода, а ф - тип клона.
Класс клонов: Множество похожих фрагментов кода, определяемая как кортеж (fi, f2,..., фп,ф). Каждая пара различных фрагментов является парой клонов: (fi,fj,ф),г,д Е !..п^ = j.
Блок кода: Последовательность операций, объявлений классов и переменных внутри фигурных скобок или иных ограничителей зон видимости.
Проект: Проект P является некоторым набором фрагментов кода, предположим что он представлен в виде коллекции блоков кода P = {Bi,..., Bn}.
Клоны первого типа: Идентичные фрагменты кода, за исключением расположение пробелов и комментариев.
Клоны второго типа: Идентичные фрагменты кода, за исключением разницы в названиях переменных и литералов, в дополнение к разнице первого типа.
Клоны третьего типа: Синтаксически похожие фрагменты кода, которые отличаются на уровне операций. В фрагментах присутствуют операции которые добавлены, изменены и/или убраны по отношению друг к другу в дополнение к разнице первого и второго типа
Клоны четвертого типа: Синтаксически не похожие фрагменты кода, реализующие одинаковый функционал.
1.4 Постановка задачи
Обобщенно задача формулируется следующим образом.
1. Ввести метрику похожести f принимающую на вход два блока кода, и возвращающую неотрицательное вещественное число, отражающее степень похожести двух блоков кода.
2. Разработать инструмент, который используя данную метрику находит все пары блоков кода Bi, Bj в некотором проекте P такие, что f (B-^Bj) > О, где О заранее заданный порог.
Уточним постановку задачи, введя дополнительные определения. Предположим, что проект P представлен как набор блоков кода P : B1,..., Bn. В свою очередь блок кода B представлен как мешок токенов B : T1,... ,Tk.
Под токеном мы понимаем ключевое слово языка программирования, литерал или идентификатор. Строковые литералы разделены по пробелам.
Чтобы численно показать, что два блока кода являются клонами мы будем пользоваться метрикой похожести, которая будет измерять похожесть двух блоков кода друг на друга и возвращать неотрицательное число. Чем больше значение метрики, тем более похожи два фрагмента друг на друга. В результате блоки кода с метрикой похожести, большей чем некоторый заранее заданный порог, будут считаться клонами.
Формально: имея проект P, метрику похожести f, пороговое значение значение О, цель найти все пары блоков кода P.Bx и P.By, такие что: f (P.Bx, P.By) > |О * max(P.Bx, P.By|)"|
Дублирование исходного кода часто возникает в процессе разработки программного обеспечения. Этот дублированный код часто называют клонами кода, а процесс - клонированием кода. Исследования показали что 20-50% современного программного обеспечения состоит из склонированого кода [1]. Считается, что клоны кода имеют отрицательное влияние на качество кода, потому что они делают поддержку кода сложнее, а так же из-за них сложнее находить и устранять программные ошибки [4][11]. Также когда клонированный код появляется в кодовой базе, он так же может быть признаком нелегального переиспользования кода. Такое нелегальное переиспользование кода в программном обеспечении с открытым исходным кодом, как правило, принимает форму нарушения лицензии. Исследования выделяют две основные причины по которым разработчики клонируют код. Первая причина состоит в том, что разработчики программного обеспечения с открытым исходным кодом переиспользуют код с целью не фокусироваться на некоторых тривиальных задачах и потому что часто ограничены во времени и ресурсах [16]. Второй причиной выделяют тот факт что существует множество заблуждений о природе лицензий программного обеспечения с открытым исходным кодом, и это проблема только усугубляется большим количеством существующих лицензий для программного обеспечения с открытым исходным, что ведет к тому, что разработчики не до конца понимают условия лицензий и разницу между ними [3]. Нарушение лицензии программного кода может быть причиной судебных разбирательств, поэтому в наличии инструментов поиска склонированного кода заинтересованы не только разработчики программного обеспечения, но и их работодатели поскольку именно они будут нести ответственность за нарушенные лицензии.
1.2 Обзор литературы
Ранние работы, затрагивающие поиск похожих фрагментов кода, использовали прямолинейные подходы для поиска возможных дубликатов кода в больших кодовых базах. В этих работах анализировались названия директорий и файлов и находились директории в которых дословно совпадает большое количество файлов с исходным кодом [7][8]. Такие подходы позволяют корректно идентифицировать точные копии проектов и хорошо расширяется на очень большие объемы данных, но такие методы невозможно применять для выявления плагиата в коде, потому что уровень похожести должен быть определен непосредственно для кода.
Одним из первых программных инструментов, позволяющим производить поиск клонированного кода на уровне функций, при этом расширяющийся на большие объемы данных является SourcererCC [14]. Этот инструмент позволял производить эффективный поиск клонов, используя анализ токенов, использующихся в исходном коде. Данное решение будет подробно рассмотрено далее в тексте, вместе с дальнейшими модификациями данного подхода. Несмотря на эффективность, подходы основанные на анализе токенов не позволяют надежно находить некоторые типы клонов, в частности они не позволяют находить структурные и семантические клоны.
Подходы для поиска дубликатов в коде с использованием структурных признаков, как правило, используют информацию, которую можно получить из синтаксического дерева и используют методы для поиска похожих поддеревьев [5], из-за чего они обладают как минимум квадратичной асимптотикой и плохо масштабируются на большие объемы кода.
Так же существуют подходы которые ищут дубликаты кода, используя семантическую информацию. Зачастую такие подходы используют алгоритмы машинного обучения. Для подходов основанных на машинном обучении крайне важным является способ извлечения признаков из кода. В качестве признаков может быть использован код в виде текста, синтаксические деревья и даже байткод [13].
1.3 Определения
Далее приведены общепринятые определения[2][12][14], используемые в рамках данной работы
Фрагмент кода: Непрерывный сегмент исходного кода, определяемый как триплет (l, s, e), где l - файл с исходным кодом, s - номер строки на котором начинается данный фрагмент, e - номер строки на котором он заканчивается.
Пара клонов: Пара похожих фрагментов кода, определяемая как триплет (fi, f2, Ф), где fi, f2 - фрагменты кода, а ф - тип клона.
Класс клонов: Множество похожих фрагментов кода, определяемая как кортеж (fi, f2,..., фп,ф). Каждая пара различных фрагментов является парой клонов: (fi,fj,ф),г,д Е !..п^ = j.
Блок кода: Последовательность операций, объявлений классов и переменных внутри фигурных скобок или иных ограничителей зон видимости.
Проект: Проект P является некоторым набором фрагментов кода, предположим что он представлен в виде коллекции блоков кода P = {Bi,..., Bn}.
Клоны первого типа: Идентичные фрагменты кода, за исключением расположение пробелов и комментариев.
Клоны второго типа: Идентичные фрагменты кода, за исключением разницы в названиях переменных и литералов, в дополнение к разнице первого типа.
Клоны третьего типа: Синтаксически похожие фрагменты кода, которые отличаются на уровне операций. В фрагментах присутствуют операции которые добавлены, изменены и/или убраны по отношению друг к другу в дополнение к разнице первого и второго типа
Клоны четвертого типа: Синтаксически не похожие фрагменты кода, реализующие одинаковый функционал.
1.4 Постановка задачи
Обобщенно задача формулируется следующим образом.
1. Ввести метрику похожести f принимающую на вход два блока кода, и возвращающую неотрицательное вещественное число, отражающее степень похожести двух блоков кода.
2. Разработать инструмент, который используя данную метрику находит все пары блоков кода Bi, Bj в некотором проекте P такие, что f (B-^Bj) > О, где О заранее заданный порог.
Уточним постановку задачи, введя дополнительные определения. Предположим, что проект P представлен как набор блоков кода P : B1,..., Bn. В свою очередь блок кода B представлен как мешок токенов B : T1,... ,Tk.
Под токеном мы понимаем ключевое слово языка программирования, литерал или идентификатор. Строковые литералы разделены по пробелам.
Чтобы численно показать, что два блока кода являются клонами мы будем пользоваться метрикой похожести, которая будет измерять похожесть двух блоков кода друг на друга и возвращать неотрицательное число. Чем больше значение метрики, тем более похожи два фрагмента друг на друга. В результате блоки кода с метрикой похожести, большей чем некоторый заранее заданный порог, будут считаться клонами.
Формально: имея проект P, метрику похожести f, пороговое значение значение О, цель найти все пары блоков кода P.Bx и P.By, такие что: f (P.Bx, P.By) > |О * max(P.Bx, P.By|)"|
В рамках данной работы было проведено исследование существующих методов поиска дубликатов кода, а также реализовано программное средство способное находить дубликаты кода в наборах файлов с исходным кодом potator. Данное программное средство находится в открытом доступе и имеет открытый исходный код. Исходный код может быть найден по ссылке https://github.com/otzhora/potator вместе с инструкциями по установке. Также было проведено сравнение результатов поиска и скорости работы со стандартным средством поиска дубликатов SourcererCC. Реализованное программное средство potator пригодно для использовании в реальной практике разработки программного обеспечения.
