Обзор подходов и инструментов

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

Проверка исходного кода на плагиат

Чтобы провести анализ подходов поиска плагиата в наборе документов, необходимо выделить ряд изменений исходного текста программы, к которым должен быть устойчив эффективный алгоритм [9]:

• 1. изменение комментариев кода;
• 2. изменение количества переносов строк, пробелов и отступов;
• 3. изменение типов переменных или возвращаемых значений функций на аналогичные (что может незначительно сказаться на выполнении программы. Например, снижение или повышение точности в переменных с плавающей запятой);
• 4. переименование переменных и функций;
• 5. замена строковых и символьных констант;
• 6. перестановка блоков кода;
• 7. добавление «ненужных» блоков кода (т.е. таких, которые практически не влияют на исполнение программы).

Среди наиболее распространенных подходов обнаружения плагиата можно выделить следующие [10]:

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

Существует довольно много инструментов для поиска плагиата в работах на естественном языке, многие из которых являются бесплатными и доступны в сети Интернет. Более того, многие из таких инструментов ищут плагиат с помощью нахождения точных копий участков кода, что не всегда эффективно. Намного меньше инструментов, которые учитывают специфику программных кодов и многих описанных выше типов изменений. Наиболее популярными и близкими к выделенным критериям инструментами являются MOSS (Stanford University) [11] и JPlag (Karlsruhe Institute of Technology) [12]. Но эти инструменты не чувствительны к некоторым из перечисленных ранее типов изменений исходных работ, а именно изменениям типов (3) и (5).

Одним из наиболее популярных алгоритмов для поиска плагиата в текстовых документах является алгоритм поиска и сравнения отпечатков [13,14]. Данный алгоритм относится к типу анализаторов строковых представлений программного кода и имеет ряд сильных сторон:

• 1) высокая скорость работы;
• 2) устойчивость к перестановкам частей документа [15];
• 3) относительно простая реализация;
• 4) устойчивость к шумам (т.е. вставке дополнительных участков текста в исходный документ) [15].

Использование данного алгоритма, однако, не решает задачу обнаружения плагиата полностью, а решает только проблемы, связанные с изменениями типов (6) и (7) [15]. Алгоритм находит совпадающие части в парах документов, но чувствителен к изменениям типов (1) — (5).

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

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