Работая при университете, недавно столкнулся с интересной задачей, связанной с поиском академического плагиата во внутренней системе контестов по программированию, ставшей основой для преподавания основ алгоритмики студентам первого курса. Позже, начав поиск русскоязычных материалов, я был очень расстроен отсутствием каких-либо обобщающих статей на эту тему, поэтому незамедлительно решил восполнить этот пробел и рассказать о своем опыте создания модуля антиплагиата.
Введение
Академический плагиат — это очень распространенное явление, особенно если дать студентам много свободы в создании своих программ. По некоторым источникам, больше половины студентов технических специальностей хотя бы раз нечестно сдавали задания по программированию. Разумеется, с такой проблемой столкнулся и мой институт. Преподаватели и их ассистенты для большей части решений, прошедших проверку в системе автоматического тестирования, вынуждены открывать последние сданные исходники других студентов в рамках этой же задачи с целью выявить потенциальное наличие в них плагиата. Когда на потоке мало студентов и преподаватель условно знает "кто с кем дружит", то эта проверка не занимает длительного времени, но если на первый курс приходит более сотни студентов, то данную проблему быстро решить уже не получится. К счастью, этот процесс можно автоматизировать.
Начнём с того, что уже существует великое множество открытых и проприетарных решений, так или иначе решающих данную задачу: из опенсурсных популярны, например, MOSS и JPlag. Однако ни одно из них не удовлетворяет нашим требованиям: одни из них работают с лимитированным количеством языков программирования, другие сканируют половину интернета на наличие похожестей частей кода и прочее. Вот же краткий список требований к модулю, составленный нашей командой разработки:
Поддержка языков программирования платформы для контестов (C++, Python, Java, C# и Pascal);
Скоринг решений учеников, прошедших автоматическую проверку, в рамках одной задачи (то есть должна быть реализована push- или pull-модель взаимодействия с платформой);
Выдача преподавателю списка решений, наиболее похожих на целевое, для дальнейшего вынесения собственного вердикта о наличии списывания.
Как можно заметить, система просто должна автоматически выполнять ту работу, которую на данный момент вручную проделывает преподаватель. Остаётся лишь главный вопрос: как будет проходить непосредственно сам скоринг решений? И это уже детали реализации, которые мы сейчас разберем.
Типы заимствований исходного кода
Для начала стоит определиться, а что вообще считается академическим плагиатом? Существует прекрасная монография под названием A Survey on Software Clone Detection Research*, написанная ещё в 2007 году, и в дальнейшем повествовании я буду практически полностью опираться на неё, потому что она покрывает все необходимые нам темы. В ней описывается 4 основных типа заимствования исходного кода:
Программный код скопирован без каких-либо изменений (иными словами, идентичен оригиналу с точностью до комментариев);
Код скопирован с "косметическими" заменами идентификаторов (имен функций и переменных, типов данных, строковых литералов);
Код может включать заимствования второго типа, а также модификации скопированного оригинала путем добавления, редактирования или удаления его фрагментов или изменение порядка их исполнения, не влияющие на логику самой программы;
Программа некоторым образом переписана с общим сохранением логики работы и функциональности, однако синтаксически она может абсолютно отличаться от оригинала.
Качественная система антиплагиата должна хорошо определять первые три типа плагиата из классификации выше. Заимствования четвертого типа крайне затруднительны для выявления (см. статью) и часто представляют собой копирование самого алгоритма, а не частей кода оригинальной программы, что не является плагиатом как таковым.
Другой проблемой является то, что любой алгоритм антиплагиата будет давать ложноположительный результат на коротких и простых задачах (например, алгоритм Евклида или сортировка пузырьком), ведь если студент в здравом уме, то он явно не напишет что-то оригинальное и отличное от других решений. С этим недоразумением можно справиться несколькими способами: либо не запускать алгоритм на коротких задачах в принципе, либо использовать какой-то алгоритм "с пенальти" на короткие программы, либо вообще не решать данную проблему: преподаватель сам понимает, что задача простая, поэтому, вероятнее всего, сразу проставит ей нужную оценку.
Методы сравнения исходных кодов
В литературе встречается множество способов сравнения программ. Вот пять наиболее универсальных и распространенных подходов, которые в дальнейшем были успешно применены в нашей системе:
Text-based метод заключается в сравнении текстовых представлений программ на основе некоторой метрики, например, расстояния Левенштейна или Джаро-Виклера. Данный способ отличается своей скоростью и простотой, но результативность быстро снижается даже на простейших "косметических" модификациях.
Token-based метод основан на преобразовании ключевых слов программы в последовательность лексем языка программирования (далее просто токенов). Полученные токены сравниваются любым доступным способом. Этот алгоритм гораздо точнее предыдущего, так как игнорирует все изменения второго типа, однако он всё ещё не справляется со структурными изменениями.
Metric-based метод определяет на полученных в предыдущем методе токенах некоторые метрики (например, кол-во используемых циклов и условных конструкций), а далее считает схожесть программ на основе количества совпадающих метрик. В целом, алгоритм отлично дополняет другие методы антиплагиата, однако он часто даёт ошибочный результат (в частности, метод успешно отрабатывает на программах с переименованием переменных и изменением условий и циклов, но моментально деградирует при добавлении в код NO-OPов по типу объявления пустого цикла или инициализации неиспользуемых значений).
Tree-based подход требует представления кода в виде абстрактного синтаксического дерева (далее просто AST, Abstract Syntax Tree). В таком формате программы сравниваются любым доступным способом: от "наивного" подсчёта совпадающих узлов до продвинутых методов на основе расстояния Zhang-Shasha. Часто данный способ считается наиболее эффективным, но в то же время его сложнее внедрить: помимо построения самих AST, нужна реализация алгоритма для их сравнения.
Binary-based метод требует прохождения кодом этапа компиляции (или интерпретации). Полученное бинарное представление (ассемблерный листинг или байткод) служит основой для дальнейшего сравнения программ. Помимо высокой точности на заимствованиях 1-2 типа (мелкие структурные изменения часто оптимизируются компилятором, а разные реализации одного функционала, дают одинаковый ассемблерный листинг), алгоритм может дать неплохой результат на модификациях третьего типа, но в то же время может и легко ломаться. Было выявлено, что банальное изменение типов данные может уронить коэф. схожести на несколько десятков процентов.
Конечно же, это не все существующие алгоритмы. Есть множественные модификации каждого из методов, так или иначе повышающие эффективность скоринга (в этом плане может быть интересен метод Шинглов), а также совершенно другие подходы, которые могут основываться, например, на поведении программы во время исполнения (behavior-based метод) ини на графе её зависимостей (PDG-based метод). Кстати, упомянутая выше монография наполнена сравнительными таблицами как самих методов, так и их модификаций, что очень интересно для изучения.
В дополнении приведу ещё один интересный подход: если вы знаете специфику действий своего пользователя (например, с каким среднем промежутком времени сдаются задачи на платформе или сколько попыток нужно потратить для успешной сдачи), то сможете выделить ряд метрик, на основе которых можно будет определять подозрительность поведения конкретного пользователя. Например, если студент сдаёт к ряду несколько задач и они проходят все тесты, то это отличный триггер на жульничество с его стороны. К сожалению, такой подход не является универсальным, а результат зависит от выделенных для использования метрик.
Очевидно, что каждый из рассмотренных выше методов имеет свои преимущества и недостатки и некоторые из них могут быть эффективнее на определенных модификациях условного кода. Так что же мешает нам использовать лучшие стороны каждого из них? Алгоритм антиплагиата на основе нескольких подходов называется гибридным, и данный подход действительно значительнее устойчивее каждого из методов по отдельности. Для вынесения итогового вердикта можно использовать либо максимальный, либо средний скоринг для каждого из примененных алгоритмов. Второй вариант как раз таки и был применен в нашей дальнейшей реализации модуля антиплагиата.
Разработка алгоритма антиплагиата
Гибридный алгоритм антиплагита может быть реализован следующими простыми шагами:
Форматирование и нормализация (в т.ч. удаление комментариев) исходного кода для повышения точности текстовых сравнений;
Получение промежуточных представлений программы, а именно её токенов, AST и ассемблерного листинга;
Непосредственно сравнение полученных форматов вышеперечисленными методами;
Вынесение вердикта на основе полученных коэффициентов схожести;
(Опционально) Вычисление дополнительных полезных статистик, например, дисперсии и квантилей распределения этих коэффициентов для всей выборки решений.
С первым шагом особых проблем не возникает: нормализация может быть выполнена средствами языка программирования (в т.ч. регулярными выражениями), а для форматирования можно использовать сторонний инструмент (обратите внимание на clang-format), однако данный шаг опционален. Но вот с получением промежуточных представлений программы, а именно списка лексем и AST, могут возникнуть проблемы. Конечно, никто не мешает вам написать собственный лексер и парсер для каждой необходимой вам грамматики (так, например, сделали разработчики JPlag), но если у вас сжатые сроки и ленивые руки, то есть одно менее элегантное, но эффективное решение: использование парсера с открытым исходным кодом ANTLR.
ANTLR отлично зарекомендовал себя среди разработчиков различных грамматик и утилит для работы с ними, а сообщество уже добавило поддержку более двух сотен популярных языков программирования. Данный парсер сможет без проблем превратить вашу программу в список токенов, а также построить (и визуализировать!) абстрактное синтаксическое дерево на их основе. Небольшой платой за готовый синтаксический разбор будет долгое обращение к самой утилите (занимает порядка секунды для небольшой программы).
Итак, мы имеем все промежуточные представления на руках: ассемблерный листинг (или байткод) нам выдал компилятор/интерператор, токены и AST мы получили из ANTLR, а текстовое представление мы имеем по умолчанию. Исходники мы даже немного улучшили посредством нормализации, нечто подобное желательно сделать и с бинарным представлением, а именно удалить offsetы пямяти, оставив только исполняемые инструкции (тут достаточно задействовать утилиту grep).
Дальше нас ждет третий шаг, а именно скоринг полученных представлений. Со сравнением текстов и бинарного формата проблем не выходит: мы берем любую доступную метрику и сравниваем два набора символов. По моим наблюдениям, лучше всего показала себя комбинация расстояния Дамерау-Левенштейша и LCS. Со скорингом AST возникают некоторые трудности: если нужно это сделать эффективно, то в любом случае придётся считать редакторское расстояние для деревьев (кстати, есть одна каноническая реализация алгоритма на питоне), а если мы хотим сделать это быстро, то сойдёт и наивная стратегия, основывающаяся либо на прохождении по ветвям дерева до первого несовпадения элементов, либо на подсчете отношения количества совпавших узлов ко всем узлам (данная стратегия и легла в основу нашей реализации).
Полученный результат скоринга со всех методов, лежащий в промежутке от 0 до 1, фактически показывает, насколько два решения похожи друг на друга по некоторой метрике. Это можно усреднить и делать предположение по полученному значению: если коэффициент схожести программ выше 95%, то они практически идентичны. Дополнительные статистики, подсчитанные по выборке сданных на задачу решений, могут быть тоже очень полезны. К примеру, медианное значение схожести близкое к максимальному и низкая дисперсия говорят о простоте задачи — в этом случае можно уверенно давать отрицательный вердикт на наличие в решении заимствований.
Полученные результаты
Для тестирования полученного гибридного алгоритма была использована небольшая синтетическая выборка, включающая некоторые модификации программ на языках Java и C++ (~750 символов) для всех четырех типов заимствований. И вот как показали себя примененные методы по отдельности (коэф. схожести усреднен и округлен):
Модификация / процент схожести программ | Text-based | Token-based | Metric-based | Tree-based | Binary-based |
Изменение комментариев (тип 1) | 100% | 100% | 100% | 100% | 99% |
Реформатирование кода (тип 2) | 97% | 97% | 92% | 93% | 100% |
Добавление неиспользуемых зависимостей (тип 2) | 89% | 92% | 85% | 91% | 99% |
Переименование идентификаторов (тип 2) | 85% | 100% | 100% | 96% | 98% |
Изменение типов данных (тип 2-3) | 97% | 99% | 100% | 98% | 85% |
Изменение порядка исполнения кода (тип 3) | 78% | 86% | 95% | 91% | 81% |
Выделение частей кода в функции (тип 3-4) | 65% | 74% | 72% | 51% | 67% |
В прошлой таблице важны не цифры, а сама динамика поведения различных методов. По результатам итогового тестирования, алгоритм в среднем выдавал следующие проценты схожести программ с заимствованиями различных типов (в зависимости от силы изменений):
Заимствования типа 1: 99-100%
Заимствования типа 2: 94-98%
Заимствования типа 3: 87-96%
Заимствования типа 4: 65-82%
Кэширование промежуточных представлений
Основным узким местом стало получение промежуточных форматов данных: обращение к ANTLR для каждой программы занимало примерно секунду, в то время как алгоритмическая часть работала почти моментально. Решением проблемы стало использование кэширования представлений посредством общеизвестного Redis, позволившее получать результат антиплагиата примерно за 1-2 секунды для выборки из 50 решений с "прогретым" кэшем. Это примерно соответствует среднему количеству решений для задачи на нашей платформе в пределах одной группы студентов.
Существующая проблема "холодного старта" решается использованием очередей и брокера сообщений, например, RabbitMQ: в рамках контестов можно спокойно дать алгоритму возможность поработать пару минут на первых решениях, чтобы затем доставать нужные представления из кэша на последующих программах. Скорость в нашем случае не имеет значение, ведь сданная задача может быть проверена как через пару минут, так и к концу месяца: всё зависит от загрузки преподавателя.
Заключение
Гибридная методика поиска академического плагиата показывает неплохие результаты для детектирования многочисленных кодовых модификаций и довольно устойчива ко многим маскирующим преобразованиям.
Стоит отметить огромный потенциал использования ANTLR: он предоставляет все необходимые промежуточные представления программ, для сравнения которых можно внедрить любую желаемую стратегию, а также позволяет без труда можно добавить поддержку многих языков программирования (спасибо за то большому комьюнити). Важно заметить, что использование кэширования обращений к ANTLR может ускорить процессинг исходников в десятки раз!
Цель данной статьи: дать небольшой обзор популярных методик, а также поделиться своим опытом внедрения модуля антиплагиата. Искренне надеюсь, что я этого достиг. Не вижу смысла оставлять здесь большой список литературы: всем заинтересованным в данном направлении я настоятельно советую обратиться к упомянутой выше монографии, а прочие источники я добавил в местах использования.
На текущий момент система антиплагиата на стадии интеграции с университетской платформой. Если после успешного внедрения появятся интересные результаты, то я обязательно ими поделюсь, а пока предлагаю вам поделиться в комментариях своими мыслями и наработками в данной области, если таковые имеются, а также задать интересующие вопросы. Мне очень интересно узнать ваше мнение и помочь вам в создании проектов смежной тематики.
