Как я делал проверку копипасты для спецкурса по Python3 и что из этого вышло

Часть первая: why?

В 2017 году (осень) мы решили перезапустить спецкурс 2014 года по Python. Причин было много — наработанная практика за предыдущие два учебных года (базовый курс в Севастопольском филиале МГУ), перевод на Python3, некоторая реструктуризация изложения. Впрочем, подход остался тем же: мы читаем авторское «Знакомство с Python3», дополняем его объяснениями и примерами и решаем множество практических домашних заданий (36 задач на написание программы или функции). Лекции записывались на видео — в основном, скринкаст с небольшой говорящей головой.

Условия домашних заданий (в среднем по 3 к лекции) и некоторые подсказки по решениям выкладывались на сайте, а вот проверку мы доверили факультетской системе проведения олимпиад EJudge. Мы использовали только одну функцию EJudge: программе участника скармливается на стандартный ввод некий текст из набора входных тестов, а результат сравнивается с эталонным.

К сожалению, в курс не входили практические занятия под чьим-либо руководством, так что требования «красоты» или «лаконичности» программ-решений пришлось опустить — не стоит оценивать то, чему не учил.

Видео к курсу регулярно выкладывались в сети, регистрация на «соревнование» в EJudge была свободной, так что на время подведения итогов у нас было 131 зарегистрированный участник соревнования (включая меня), из которых примерно половина (включая меня :) ) «дошла до финиша», т. е. решила более ⅔ задач. Всего было более 6000 попыток сдать задачу, из которых примерно половина была, с точки зрения EJudge, успешной.

Понятно, что в таких условиях полномасштабный экзамен, с учётом требований к проведению экзамена — дело очень ресурсоёмкое. С другой стороны, человек, который успешно решил порядка 30 временами не самых простых задач, вряд ли нуждается в строгой экзаменовке. Беглое чтение написанного им кода вкупе с данными о решённых задачах даёт достаточное основание для оценки.

Правда, тогда резко повышается значимость плагиата при написании программ-решений. Для начала мы решили строго ограничить время решения каждой задачи, но потом ввели градацию: за решение в первые две недели участник получает 4 балла, в третью неделю — 2, а после — 1. Таким образом, люди, которые не сумели решить её вовремя, имеют возможность посмотреть беглый разбор решения (как раз через две недели) и оперативно заработать половину своих бонусов.

Тем не менее даже поверхностный взгляд на содержимое EJudge показал, что идея плагиата (он же «копипаста») продолжает будоражить неокрепшие умы участников, как если бы они не хотели научиться ЯП Python3, а хотели… чего-то другого, ума не приложу, чего :( .

В решениях присутствовала как прямая и беззастенчивая копипаста (идентичные программы от разных участников), так и разнообразные приёмы, как сейчас говорят, «рерайтинга» — тривиальной модификации исходного кода (расстановка незначащих пробелов, комментариев и пустых строк, переименование идентификаторов, перестановка независимых блоков кода и т. п.). Причём зачастую даже это не спасало от внимательного взгляда проверяющего, потому что при копипасте сохраняются индивидуальные особенности стиля программирования; что важнее — огрехи стиля, не влияющие на правильность ответа.

Но откуда взяться внимательному взгляду проверяющего, когда таких программ чуть менее, чем 3000??

Часть вторая: how?

Признаюсь честно, трудно сказать, что больше двигало мной: стремление навести какую-то справедливость или возможность попрактиковаться в программировании (разумеется, на Python3). Сама задача оценки «похожести» оказалась привлекательной. Плюс эдакий вызов: сам учил питону, вот теперь сам проверялку пиши.

  1. PEP8-фикация (autopep8)

    • Первая мысль была простой: избавиться от незначимых изменений форматирования текстов, для чего причесать их «улучшателем» — например, оформляющим программу в соответствие с pep-0008. Построчное сравнение двух программ после «pep8-фикации» (например, с помощью vimdiff) делает похожие программы действительно похожими, а выделенные различия в именах идентификаторов только прибавляют таком сравнению пафоса. Так или иначе выявленные случаи копипасты/рерайтинга демонстрировать удобно именно в отформатированном виде.

  2. Расстояние Левенштейна (editdistance)

    • Для каждой задачи было прислано в среднем порядка 70 верных решений, так что о ручном сравнении нельзя было и думать. И, опять-таки, первая мысль — померить т. н. «редакторское расстояние» (расстояние Левенштейна) в группе решений одной задачи. Было очевидно с самого начала, что одним только расстоянием обойтись не удастся, т. к. переименования и комментарии могут приводить к довольно большому разбросу в оценках. Вот если бы у нас были препараты исходного кода, по возможности лишённые синтаксически незначащих различий, этот инструмент пригодился бы.

  3. Абстрактное синтаксическое дерево разбора Python3 кода (ast.html)

    • Преодолев искушение вручную преобразовывать что-то в препарируемом исходном коде, я вовремя вспомнил о том, что имею дело не просто с программой, а с синтаксически верной (мало того, работающей и выдающей правильный ответ) программой. Так что если заставить сам Python построить дерево синтаксического разбора этого кода, а сравнивать уже текстовое представление этих деревьев, в них не будет ни пустых строк, ни пробелов, ни комментариев, ни лексически различных, но синтаксически одинаковых элементов, вроде строковых констант, задаваемых кавычками или апострофами.

  4. Удаление имён
    • Осталось только заменить все идентификаторы на один и от же, и переименование так же не будет учитываться при сравнении. Можно было бы унифицировать и строки, но специфика EJudge — строгая проверка соответствия вывода эталону — исключает возможность выводить один текст вместо другого. Получившийся препарат представляет собой нечто вроде «топологии» программы — здесь завели и поименовали несколько объектов, здесь объявили функцию, здесь вызвали функцию и метод объекта, а потом связали именем и т. п.
  5. Компрессия
    • Вычисление расстояния Левенштейна — алгоритм высокой вычислительной сложности, если считать строкой весь исходный код программы (всё дерево разбора), но выхода нет (иначе придётся разбираться с перестановкой строк). К счастью, решения домашних заданий — небольшие программы, а вдобавок из текстового представления дерева разбора я поудалял всевозможные пустые/повторяющиеся атрибуты и заменил названия синтаксических конструкций на однобуквенные. После этого, конечно, в получившемся препарате ничего уже разобрать нельзя, но нам и не надо, зато при измерении расстояния меньше работы и — что важнее — различия «топологии» имеют большую значимость.
  6. Кластеризация
    • Теперь возникает неприятная задача: выяснить «кто у кого списал?». Для каждого решения выделяются «близкие» (расстояние до которых не превышает 1% общего объёма препарата), после чего все доступные по близости задания объединяются в единый кластер. Лидер кластера (человек, первым сдавший задание) считается автором решения, остальные — списавшими либо у него, либо друг у друга.
  7. Оценка
    • Как уже было сказано, задания, сданные вовремя оценивались в 4 балла, с опозданием в неделю — в 2, с опозданием более 2 недель — в 1. Если решение оказывалось в кластере копипасты, лидер кластера получал полную оценку (это, естественно, всегда было 4 балла), остальные члены кластера — 1 балл, что приравнивало их к списавшим с доски во время разбора с недельной задержкой.

Получившийся инструмент.

Часть третья: so what?

Часть четвёртая, заключительная: till when?

Как бороться с копипастой?

  1. Пресекать?
  2. Параметрические задачи?
  3. Смена мотивации?