ИСПОЛЬЗОВАНИЕ МЕТОДОВ “РАССТОЯНИЕ ЛЕВЕНШТЕЙНА” И ВЫРАВНИВАНИЯ СТРОК ДЛЯ ПОИСКА ПЛАГИАТА В ПРОГРАММНОМ КОДЕ

PLAGIARISM SEARCH IN PROGRAM CODE USING LEVENSHTEIN DISTANCE AND ALIGNMENTS

Tatiana Ogneva

student, Faculty of Computer Science and Information Technologies, Saratov State University,

Russia, Saratov

Elena Lapsheva

Senior Lecturer, Faculty of Computer Science and Information Technologies, Saratov State University,

Russia, Saratov

АННОТАЦИЯ

В работе рассматривается проблема поиска плагиата в программном коде. Для ее решения используются расстояния Левенштейна и метод, основанный на выравнивании строк. Описана реализация предобработки (нормализация и токенизация) программного кода и приведены примеры, которые наглядно демонстрируют работу этих методов.

ABSTRACT

This article contains an overview of the problem of searching plagiarism in program code. The paper provides information on how to use such methods as Levenshtein distance and method, based on string alignments, to solve it. Also the article includes the description of preprocessing (normalization and tokenization) of source code and examples, which clearly demonstrate the work of these methods.

Ключевые слова: выявление плагиата в программном коде, алгоритмы поиска плагиата в программном коде, расстояние Левенштейна, выравнивание строк.

Keywords: source code plagiarism detection, algorithms of plagiarism search in program code, Levenstein distance, string alignment.

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

“Ручная” проверка возможна только в случае нескольких решений задач небольшого размера.  Если же речь идет о работе с группами и потоками студентов, то для решения проблемы списывания требуется специальное программное обеспечение (ПО).

Существуют различные методы поиска плагиата в программном коде. Наиболее известные - это алгоритм, основанный на выравнивании строк, алгоритм Хескела, алгоритм жадного строкового замощения и алгоритм нахождения расстояния Левенштейна.

В данной работе были реализованы следующие методы с использованием языка программирования Python и его библиотек:

1. Нахождение расстояния Левенштейна (реализован самостоятельно) [1]. На вход подается последовательность символов "K", "V", "T", "D", "S", "L", "I", "N" для Python и "K", "V", "C", "T", "D", "S", "L", "I", "N", "B", "P" для С++; на выходе получаем меру схожести.
2. Метод выравниваний (использовалось семейство методов Aligment из модуля BioPython [2]). На вход подается последовательность символов "K", "V", "T", "D", "S", "L", "I", "N" для Python и "K", "V", "C", "T", "D", "S", "L", "I", "N", "B", "P" для С++; на выходе получаем меру схожести.

Для этих методов была реализована предобработка, которая включает в себя два этапа:

1. Токенизация [3]. Каждому оператору выбранного языка программирования (в моей работе Python и C++) ставится в соответствие некоторая метка, назначенная заранее для каждого класса операторов, метки также могут приписываться блочным операторам и операторам подключения библиотек. По полученному набору меток строится строка, причем порядок этих меток сохраняется в соответствии с их порядком следования в исходном коде программы. Замена производится при помощи словаря токенов на основе регулярных выражений [4]. На вход подается исходный код программы; на выходе получаем токенизированное представление кода.
2. Нормализация - удаление пробельных символов (пробел, вертикальная табуляция, горизонтальная табуляция, перевод строки и возврат каретки), скобок, некоторых знаков пунктуации (запятая, точка, точка с запятой, двоеточие), комментариев и текстов внутри операторов вывода. На вход подается токенизированное представление кода; на выходе получаем нормализованную последовательность символов.

Программа была протестирована на программных кодах из системы автоматической проверки задач на сайте school.sgu.ru (всего 185 задач и 4900 решений к ним). Данный контестер используется для обучения программированию школьников и студентов и содержит более 800 задач начального и среднего уровней сложности.

Некоторые наиболее яркие примеры работы программы приведены в таблицах ниже.

Таблица 1.

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

Таблица 2.

Пример работы методов. Программы P1 и P2. Во втором решении добавлен комментарий и многострочная строка, пустая строка

Таблица 3.

Пример работы методов. Программы P1 и P2. Во втором решении переименованы некоторые переменные, добавлены пустые строки, остальное одинаково с точностью до пробельных символов

Таблица 4.

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

Таким образом, данные методы распознают такие виды плагиата, как изменение отступов, пробелов и комментариев; изменение имен идентификаторов, строковых литералов и типов переменных; вставка, удаление, изменение порядка следования фрагментов кода. При этом метод выравнивания оказался более чувствителен к такого рода изменениям.

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

1. И. А. Посов, В. Е. Допира, Методы поиска плагиата в кодах программ // Известия СПбГЭТУ «ЛЭТИ» № 6/2019 C. 61-66
2. Biopython Tutorial and Cookbook,  Jeff Chang, Brad Chapman, Iddo Friedberg, Thomas Hamelryck, Michiel de Hoon, Peter Cock, Tiago Antao, Eric Talevich, Bartek Wilczyński Last Update – June ‍2, 2021 (Biopython 1.79) [Электронный ресурс] URL: http://biopython.org/DIST/docs/tutorial/Tutorial.html (дата обращения 10.11.2021)
3. Э. М. Вихтенко, Д. А. Карманов, Д. З. Син, Информационная система “Плагиат в программах студентов” // ВЕСТНИКТОГУ. 2019.№3(54) С. 25-34
4. Perkins J. Python Text Processing with NTLK 2.0 Cookbook - 2010 C. 32-34.