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

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

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

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

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

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

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

Правда, тогда резко повышается значимость плагиата при написании программ-решений. Для начала мы решили строго ограничить время решения каждой задачи, но потом ввели градацию: за решение в первые две недели участник получает 4 балла, в третью неделю — 2, а после — 1. Таким образом, люди, которые не сумели решить её вовремя, имеют возможность посмотреть беглый разбор решения (как раз через две недели) и оперативно заработать половину своих бонусов, и даже те, кто махнул было на домашние задания рукой, могут немножко прибавить себе баллов. К экзамену допускались лишь набравшие более 2/3 из возможных баллов, причём оценки-автоматы «дошедших до финиша» делились строго: до 7/9 — «удовл», до 8/9 — «хор», остальное — «отл». Заметим, что человек, желающий сдать все решения незадолго перед экзаменом (вряд ли самостоятельные), сделать это не мог, т. к. не наберёт «проходного балла».

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

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

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

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

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

1. PEP8-фикация (autopep8) и сравнение (difflib) исходный текстов

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

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

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

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

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

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

Получившийся инструмент (версия 2019 года) (написан в течение недели, поэтому за программный продукт не считается, условия распространения — public domain) делает следующее:

1. Открывает и разбирает полученный из EJudge архив решений (время сдачи, автор и идентификатор задачи в архиве присутствуют в имени файла в программой)
2. Строит вспомогательные таблицы с препаратами программ и отформатированными версиями
3. Для каждого решения составляет список близких к нему, после чего разбивает решения на кластеры
4. Выставляет оценку каждому решению исходя из времени сдачи и участию в кластере копипаст
5. Запускает интерпретатор командной строки, позволяющий
   • Посмотреть оценки для всех пользователей и индивидуально
   • Посмотреть список решённых пользователем задач
   • Посмотреть списки пользователей и задач
   • Посмотреть список задач и кластеров копипасты по ним
   • Посмотреть участие пользователя в кластерах копипаст
   • Посмотреть исходный код решения
   • Сравнить два отформатированных решения

Последний пункт — уже чистое развлечение: дело в том, что командная строка в Python (с историей, редактированием и даже достраиванием) организуется слишком просто, грешно было её не сделать.

• UPD: Версия 2020 года, полностью переписанная

  • В ней пришлось отказаться от принципа «лидер кластера копипасты получает полный балл»: при должной организации он уязвим

  UDP: Версия 2022 года, ещё раз полностью переписанная

Как и следовало ожидать, pep8-фикация и вычисление расстояний оказались довольно медленными операциями, поэтому дополнительно между стадиями обработки сохранятся сериализованные промежуточные данные (и восстанавливаются вместо того, чтобы заново считать их при повторном запуске).

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

Таблица результатов

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

False positives. Кластеров предполагаемой копипасты оказалось подозрительно много. Причины:

1. Задача подразумевала решение настолько короткое, что его сложно было записать 60 различными способами
2. Задача предполагала или содержала очевидный алгоритм (например, в пояснениях), реализации которого вполне могли сами совпасть
3. Решение было переписано с доски после разбора 2 недели спустя.
4. Люди и в самом деле решали задачу сообща, после чего сдавали одно и то же или слегка переписанное решение

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

Выводы

1. Числовые оценки, равно как и оценки сложности, при описанном подходе не могут быть предсказаны заранее, метод требует постоянной адаптации со стороны эксперта.
2. Относительно возможных ложно выявленных копипаст пришлось проводить разъяснительную работу
3. Некоторые коллективные авторы явно получили свои тройки или даже четвёрки
4. Защита от рерайта помогает только от неизобретательного рерайта

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

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

И главное. Получившийся инструмент настолько «хорош», что выявляет даже не плагиат, а факт реализации одного и того же алгоритма. Я почти уверен, что разрешённый приём — «clean room reimplementation», при котором решение показывают, объясняют принципы его работы, после чего участник пишет своё решение с нуля, — выдал бы значимое количество ложных срабатываний.

Так что определение плагиата (за исключением прямой копипасты) остаётся процессом отнюдь не автоматическим, хотя, с применением инструментов, подобным представленному, несколько автоматизируемым.

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

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

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

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

Наверное, это будущие эффективные менеджеры.

Вопрос в том, зачем им учиться на факультете вычислительной математики и кибернетики, и где учиться тем ребятам, которые не так эффективно, но самостоятельно, справляются с решениями задач?

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

За прошедшие два десятилетия возник и доказал свою эффективность огромный пласт технологии, заключающийся в оперативном поиске и применении результатов интеллектуальной деятельности. В отличие от отраслевой науки предыдущих двух-трёх столетий, такое занятие на начальном этапе практически не требует каких-то определённых знаний, принося удовлетворительные результаты. Не требует настолько, что долгое время было объектом насмешек и осуждения. «Скрипт кидди», «индус триальный программист», «stackoverflow программирование» — в одной только в нашей области таких явлений полно.

А между тем, огромная (никем не измеренная) часть работающих решений повседневных задач создаётся в наши дни именно таким способом! Победное шествие миллионов PHP-непрограммистов, Java-непрограммистов, Python-непрограммистов, последняя мода — JavaScript-непрограммистов и их блистательных поделий только ширится.

Особенно если вспомнить, что для них изготовлены (когда — такими же непрограммистами, а когда и вполне профессионалами) сотни тысяч удобных инструментов. Это часть совсем другого разговора, но напомню, чему мы учим современных wannabe-разработчиков: не пишите с нуля! не изобретайте все велосипеды! на свете полно уже решённых подзадач, оценивайте качество решений и комбинируйте их. И собственное решение оформляйте как такой модуль, решающий вашу подзадачу — этим вы поможете всем вашим коллегам.

А возвращаясь к разговору нашему — все эти люди не знают, где и чему учиться, вот и идут в академические (точнее — исследовательские) ВУЗы, где их заставляют разбираться в чём-то довольно неинтересном, типа линейной алгебры для того, чтобы впоследствии заниматься чем-то массово невостребованным, типа составления алгоритма к доказательству математической проблемы или постановкой и решением неочевидной научно-технической задачи, не говоря уже о собственно науке — области, в которой нет вообще никаких гарантий успеха.

Если мыслить масштабно, действующая модель образовательной площадки, до сих пор воспроизводящая средневековые каноны — аудитория, доска, что-то бубнящий профессор, студиозусы, записывающие с доски и со слуха, редкие, дорогие и бестолковые учебники — требует изрядной реорганизации. На самом деле совершенно непонятно — с какой стороны, потому что практика замены живых лекторов говорящими головами, бумажных учебников — PDF-ами, а экзамена — электронным тестированием достаточно явно показывает, что так делать не надо. Но это, опять-таки, тема большого и сложного разговора, требующего нескольких точек зрения, опыта в современных образовательных технологиях и т. д.

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

1. Узаконить.
   • Единственное, что не вызывает сомнений: усилия по копипасте/рерайтингу не могут быть полностью подпольными. Должна существовать какая-то дисциплина или какой-то вид контроля, в котором применялись бы поиск и адаптация готового решения — явно или как альтернатива полностью самостоятельной разработки. К сожалению, далеко не все существующие учебные задания допускают такое применение.
2. Пресечь.

   • Если за плагиатом строго приглядывать, риск станет невыгодным. Строго приглядывать — значит, тратить больше времени/внимания на каждом уровне контроля: увеличивать долю заданий, которые выполняются и проверяются в присутствии преподавателя, постоянно наблюдать за выполнением, в оффлайн-заданиях добиваться обратной связи (опять-таки очно), жёстко отслеживать наличие плагиата, и т. д., и т. п. Причём на всякую строгость имеются технические средства её преодоления — от мобильного интернета до микронаушников.

3. Параметризовать задания.

   • Если выданная одному студенту задача будет в достаточной мере отличатся от задачи, выданной другому, сам процесс превращения решения одной в решение другой, буде на то возникнет желание, окажется не мене обучающим, чем самостоятельное решение. Некоторые наши шаги в эту сторону мы уже предприняли: так, в разработках 2015/2016 и 2016/2017 учебных годов для первого курса условия контрольных генерировались программами (разумеется, написанными на Python3), которые надо было скачать, запустить, получить точную формулировку задачи и в качестве ответа продемонстрировать

     • «номер варианта» (начальное значение датчика случайных чисел, на основании которого генерировалось условие)
     • Формулировку условия
     • Программу-решение

     К сожалению, проверка таких заданий практически ручная: всё, что можно сделать за проверяющего — это определить, что номер варианта соответствует формулировке (т. е., что она действительно сгенерирована случайно, а не списана у товарища или придумана для удобства решения). Необходим особый фреймворк, позволяющий одновременно с условием генерировать эталонные тесты/ответы, а ещё лучше — эталонную программу-решение. Это не выглядит делом невозможным (в конце концов, при изучении не определённых алгоритмов, а самого языка программирования мы вольны в выборе класса задач), но, кажется, на практике этим никто особо не занимался.

4. Сменить мотивацию.

   • Голубая мечта, конечно, сделать как-нибудь так, чтобы заниматься плагиатом было невыгодно, а лучше — вообще неинтересно. При некоторых входных условиях это неплохо получается: включение учащихся в процесс постановки/проверки/оценки заданий, совместная разработка, введение элемента соревновательности и вообще геймификация и т. п. Однако все такие подходы либо ориентированы на изначально мотивированных участников, либо подразумевают какие-то особые, чудесные подачу и контроль материала, которые сделают весь учебный процесс интересным большинству участников, независимо от предметного содержания.

Если коротко, то мы пока держимся — комбинируя все эти методы понемногу. Но всё чётче ощущение, что воюем мы не с копиастой, а с главным достижением нашей эпохи — информационной связностью. И если продолжать в том же духе, не меняя вектор, копипаста победит.