Обзор алгоритмов и детекторов обнаружения плагиата в исходных кодах программ Ю. Лифшиц Д. Антипов О. Евтифеева А. Котов А. Красс М. Лакунин Е. Лысенко А. Семенников Р. Счастливцев Санкт-Петербург, 2006

План обзора Постановка задачи Обзор алгоритмов Тестирование детекторов Направления для дальнейшей работы Project summary

Определение плагиата Для нас плагиат – это непосредственное использование чужого кода в своём. Часть одной программы является плагиатом части другой программы, если она была получена из нее копированием с последующим незначительным изменением кода: случайные вставки в код; перегруппировка методов; переименование переменных; рефакторинг кода.

Общая схема поиска плагиата Исходная программа Текст Представление Парсер Основной алгоритм Выходные данные Метрика Вывод Переходим из модели с большим количеством избыточной информации к более компактной

Представления исходного кода Исходный код программы Параметрическое представление Токенизированное представление В виде дерева или ориентированного графа while (i

Основные ветви развития Атрибутно-подсчётные методы Структурные методы Строковое выравнивание Жадное строковое замощение Применение суффиксных деревьев/массивов Использование приближения Колмогоровской сложности Сравнение AST-представлений программ Сигнатурные методы или методы отпечатков Гибридные методы

Сигнатурные методы (метод отпечатков) 1. Хэшируем все подстроки токенизированной программы P фиксированной длины. 2. Выделяем некоторое подмножество их хэш- значений, хорошо характеризующее P. 3. Проделываем те же шаги для токенизированных программ T 1, T 2 … T n и помещаем выбранные хэш- значения в базу. 4. С помощью хэш-таблицы (базы) получаем набор участков строки P, подозрительных на плагиат. 5. Анализируем результат и делаем выводы.

Детекторы плагиата ДетекторЯзыкиМодельАлгоритм AccuseFortrann-мерное пространство аттрибутно-подсчитывающий метод SIMC, Java, Pascal, Modula-2, Miranda токеныпоиск по матрице совпадений подстрок JPlagC/C++, Java, Schemeтокеныжадное строковое замощение MOSSC/C++, C#, Java, a8086 assembly и др. сигнатура кодаметод отпечатков PlaguePascal, Modula-2, Prolog токенынабор метрик, одна из них – вариация НОП SherlockPascal и др.текст, токеныаналог Plague, нейросеть Plan-XSMLXML форматиспользоване XMLStore SIDС++, Javaтокенывычисление метрики на основе Колмогоровской сложности

Тестирование бесплатных детекторов Доступность: SIM – работает всегда, так как это не online-сервис JPlag – никаких претензий MOSS – иногда сервер может быть недоступен SID – может не работать долгое время Скорость тестирования: MOSS, SIM – почти мгновенно JPlag – порядка 10 секунд на тест SID – среднее ожидание времени ответа - 10 минут

Сравнительная характеристика ДетекторРегистрацияПрог. требованияАвтома- тизация Представл. рез-тов Языки JPlagзапрос, разрешение администра- тора JRE, web-браузернетокно с фреймами средний диапазон MOSSписьмо с запросом Perl, web-браузердаокно с фреймами широкий диапазон SIDзаполнить форму zip-архиватор, web-браузер даокно с фреймами узкий диапазон SIM--даstdoutсредний диапазон

Принципы оценки результатов тестирования n проектов участвует в тесте n * (n – 1) / 2 пар проектов нужно проверить на наличие плагиата g пар проектов действительно содержат плагиат f пар проектов с плагиатом обнаружил детектор t из f обнаруженных пар действительно содержат плагиат

Тестовая коллекция КоллекцияЯзыкТипКоличество файлов TestSet_simple.zip (2 Kb) Javaестественный2 TestSet_spbolymp.zip (177 Kb) C++естественный196 TestSet_SID.zip (653 Kb) Javaискусственный86 TestSet_FTP.zip (637 Kb) C++естественный5(170)

Результаты тестирования TestSet_spbolymp.zip ТестФайловСр. размер SIDMOSSJPlagSIMКомментарии Summer2004- Set_day28- TestB 53 Kb4%-14.0 % 42%SIM неоправданно подозрителен SPB2005- TestC 71 Kb11%--60%false positive TeamSPB2003 -TestF 32 Kb80%99% и 96% 100% плагиат

Результаты тестирования TestSet_SID.zip ТестФайловСр. Разм.SID (%)MOSS, %JPlag, %SIM, % 1/10023 Kb8279 и /10023 Kb7979 и /10023 Kb6662 и /10023 Kb5340 и /10024 Kb316 и / Kb9898 и / Kb9898 и / Kb9797 и / Kb9296 и / Kb7984 и / Kb155 и / Kb4019 и / Kb6343 и

Качество обнаружения плагиата MOSS, JPlag, SID – хорошее; SID – лучше устойчив к вставкам одиночных операторов в код, но хуже реагирует на другие методы сокрытия плагиата; SIM – слишком подозрителен на коротких программах; SID, JPlag – парсер C-файлов не переваривает корректную строку while (c=='\xD').

Возможные направления для улучшения обзора Протестировать CloneDR, Palamida IP Amplifier и Black Duck protexIP, выяснить достоинства и недостатки CodeRank TM. Рассмотреть применение детекторов в индустрии создания ПО. Провести более глубокое тестирование с применением обфускаторов, нейросетей, более тонкой настройкой алгоритмов и т.д. Исследовать применение кластеризации для различных баз и алгоритмов.

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

Project summary Проект выполнен в рамках программы по сотрудничеству Intel с ВУЗами Санкт-Петербурга; 9 человек работали над проектом в период с по ; Сайт проекта – построен на базе технологии коллективной разработки WiKi. Основной результат проекта – обзор алгоритмов и детекторов.