Поиск пересечений в исходном коде

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

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

Впервые проблема плагиата и его особенностей в академической среде была поднята в статье Cheating Policy in a Computer Science Department (1980).

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

Пересечение — совпадение двух участков кода с точностью до незначительных модификаций.

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

К ним причисляют относительно простые модификации, которые не требуют глубокого понимания языка программирования:

К структурным можно отнести более сложные методы:

Часто встречаются классификации обходов по сложности обнаружения, вот пример одной из таких классификаций:

Выделяется четыре группы методов:

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

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

Один из самых распространённых методов обнаружения плагиата. В данном случае программный код превращается в поток неделимых (с точки зрения языка программирования) токенов. Для дальнейшего анализа можно также применять методы NLP, где в тексте вместо отдельных символов будут использоваться токены.

Главное отличие от методов первой группы в том, что при анализе большее значение придаётся структуре кода, а не наименованиям.

При таком подходе типичный алгоритм поиска плагиата строится следующем образом:

а) удаляются все названия переменных,

б) удаляются комментарии,

в) чистятся все строки и т. п.

а) Winnowing,

б) Rabin–Karp,

в) Suffix tree (array) и т. п.

В дополнение к обычным методам для сравнения последовательностей можно найти методы, основанные на нечёткой логике.

В данных методах уже используются полноценные парсеры языков и вместо последовательностей токенов строятся AST-деревья, которые каким-либо образом можно сравнивать между собой. Например, в статье Improved Plagiarism Detection Algorithm Based on Abstract Syntax Tree (2013, Guo Tao, Dong Guowei, Qin Hu and Cui Baojiang) вводится специальная хеш-функция для AST-деревьев, благодаря которой можно искать код с перестановками:

За счёт работы с AST появляется возможность искать более сложные обходы: перестановки блоков кода, инвертирование условий и т. п.

Идея метода — построить граф зависимостей между разными выражениями в программе. На рисунке ниже приведён пример PDG из статьи GPLAG: Detection of Software Plagiarism by Program Dependence Graph Analysis (2006, Chao Liu, Chen Chen, Jiawei Han):

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

В последнее время появилось несколько методов на основе ML, например:

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

Для начала рассмотрим более простую задачу — сравнение двух репозиториев.

Пусть дано два репозитория:

На выходе мы хотим получить список блоков-пересечений между участками проверяемого репозитория и участками репозитория-источника:

1. Проверяемый участок совпал с одним участком в источнике.

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

3. Два проверяемых участка пересекаются между собой.

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

А термин «репозиторий-источник» или просто «источник» используем для удобства.

Чтобы получить какую-то численную оценку совпадений с учётом подобных случаев, мы вводим понятие покрытия.

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

Для пояснения разберём расчёт покрытия на примере данной картинки, рассмотрим все файлы проверяемого репозитория.

Файл A имеет два участка с пересечениями — 40 символов и 60 символов:

Файл B также имеет два участка с пересечениями, но они накладываются друг на друга, в итоге получаем три кусочка:

В итоге покрытие для файла B будет равно 50 + 30 + 50 = 130 символов. А итоговое покрытие для репозитория будет равно 100 + 130 = 230 символов.

Задачу поиска блоков решаем в несколько этапов, основные из которых:

Рассмотрим первые два этапа на примере: допустим, есть какой-то код (пусть будет Python):

|# комментарий print (1+x)

После парсинга будет сформировано AST:

Здесь пунктирной линией отмечен порядок обхода узлов AST. Во время обхода к каждому узлу применяется набор правил, которые определяют, как узел добавляется в список токенов:

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

|# комментарий | print | ( | 1 | + | X | ) |

Так и упрощённую: например, удалив комментарии, заменив все числа на 42, а идентификаторы переменных — на val:

| print | ( | 42 | + | val | ) |

Тем самым можно пытаться нивелировать различия в коде, если применялись какие-то несложные модификации. В настоящий момент мы убираем:

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

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

Полученные последовательности токенов мы сравниваем между собой, используя алгоритм нечёткого поиска: https://habr.com/ru/companies/antiplagiat/articles/461903/.

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

Для работы с такими объёмами мы сначала выполняем индексацию, а сам поиск проводим в два этапа:

В качестве индекса мы используем имеющийся у нас индекс шинглов: https://habr.com/ru/companies/antiplagiat/articles/445952/.

Сами шинглы формируем традиционно — наборы токенов небольшой длины. Разве что дополнительно фильтруем их с помощью алгоритма Winnowing: https://theory.stanford.edu/~aiken/publications/papers/sigmod03.pdf, но это не обязательно.

Схематично архитектуру можно представить следующим образом:

Здесь в зависимостях:

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

В мире Open Source решения куда более интересные:

Ключевые их проблемы — отсутствие персистентного индекса и невозможность работы на больших объёмах (как по размеру проверяемого репозитория, так и по количеству источников).

В экспериментах мы хотели проверить репозитории из GitHub и было интересно посмотреть, встречается ли в репозиториях с permissive-лицензиями код из репозиториев с copyleft-лицензиями.

В OSS-мире присутствует два крупных семейства лицензий: copyleft и permissive.

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

Но только семейство copyleft налагает ограничения на конечный продукт или на форму поставки компонента в нём.

Прежде чем перейти непосредственно к проверкам, нам нужно было проиндексировать репозитории. Для индексации отбирались репозитории с максимальным числом звёзд в порядке убывания. Форки отбрасывались, учитывались данные только одной ветки, как правило master.

Изначально мы проиндексировали около 90 000 репозиториев из GitHub по одним из наиболее популярных языков: Python, Javа, JavaScript, С/C++, C#. Уникальных проектов оказалось не очень много — к моменту, когда мы перешли к индексации репозиториев со 100–200 звёздами (шли от наиболее популярных и вниз), получили такую статистику:

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

Среди проиндексированных репозиториев получили следующее распределение по лицензиям:

Подробнее:

В первом эксперименте мы проверили все репозитории с permissive-лицензиями по всем репозиториям с copyleft-лицензиями. Неизвестные лицензии из проверки исключили, т. к. их можно отнести к обоим семействам лицензий. В результате проверки получили 185 ГБ отчётов. Стоит отметить, что на каждый проверяемый репозиторий могло найтись до десяти источников, с которыми были пересечения (на самом деле их могло быть сильно больше, но мы специально ограничили поиск десятью, с которыми пересечений было больше всего). Чтобы хоть как-то уменьшить объём, решили дополнительно отфильтровать результаты по значимости. Значимость определили следующим образом.

Совпадения пары репозиториев считаются значимыми, если для проверяемого репозитория выполнилось хотя бы одно из условий:

После фильтрации осталось 7083 репозитория со значимыми совпадениями, а для них получилось 51 156 отчётов о парных сверках, из которых мы проанализировали вручную 200 пар (менее 0,4%).

Каких-либо интересных результатов обнаружить не удалось, все отчёты были заполнены «корректными» совпадениями:

· Куски сгенерированного кода — это могли быть клиенты для взаимодействия по gRPC; REST-клиенты, сформированные по спецификации OpenAPI; специфичные генерации для языка программирования (например, code-behind-файлы в C#: *.Designer.cs, *.csd.cs).

· Proto-контракты — дополнительные контракты от Google, контракты популярных Open Source продуктов из Apache Software Foundation и т. п.

Были и забавные моменты:

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

Но в целом, если какие-то недобросовестные заимствования кода и были, то найти их было невозможно за огромным массивом корректных.

Проанализировав проблемы, мы сделали несколько доработок, чтобы убрать «лишние» корректные совпадения.

Начали с простейших фильтров:

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

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

Из новых находок:

Следующим этапом мы добавили ещё пару фильтров, но использовали уже другие подходы.

Основная цель минификации — уменьшение размера файла. Для этого удаляются несущественные для выполнения кода детали: форматирование, комментарии, иногда сокращаются имена переменных и т. п.

А нужно ли вообще убирать минифицированный код из сравнений?

На самом деле — да, т. к. этот код является производным и генерируется из вполне корректного кода, т. е. он не является исходным кодом в обычном понимании этого термина.

Поэтому мы посчитали некоторые метрики для обычного кода и минифицированного:

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

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

Считаем, что такие высокочастотные шинглы принадлежат либо библиотечному, либо шаблонному коду.

В итоге удалось отбросить ещё несколько совпадений:

На самом деле всё равно какие-то библиотеки находятся — или редко используемые, или каких-то редких версий. Всё так же находятся обвязки ML/DL-моделей. Но большой пласт «корректных» совпадений удалось действительно отбросить.

Для второго эксперимента мы заново переиндексировали репозитории с использованием описанных выше фильтров. Кроме того, мы как увеличили количество проиндексированных репозиториев для старых языков (Python, Javа, JavaScript, С/C++, C#), так и реализовали поддержку ещё шести языков (Go, Kotlin, PHP, Rust, Swift, TypeScript), которые тоже добавили в индекс, доведя количество проиндексированных репозиториев до 165 000.

В итоге получили такое распределение по языкам:

И по лицензиям:

Как и в первом эксперименте, мы проверяли все репозитории с permissive-лицензиями по всем репозиториям с copyleft-лицензиями, исключив репозитории с неизвестными лицензиями. Несмотря на почти двукратный рост числа проверяемых репозиториев, суммарный объём отчётов о проверке уменьшился до ~50 ГБ, что объясняется работой фильтров на библиотечный, сгенерированный и минифицированный код.

Для определения значимых пар использовали те же критерии значимости, что и в первом эксперименте:

В результате осталось 3067 репозиториев, для которых имеется 5497 отчётов о парных сверках, содержащих значимые совпадения, что более чем в девять раз меньше по сравнению с 51 146 парами из первого эксперимента.

Как и раньше, дальнейший анализ был ручной: рассмотрели 57 пар (чуть больше 1% от общего числа). Кроме того, отдельно были рассмотрены межъязыковые совпадения (например, когда Java-код «совпадает» с C#-кодом), тут уже смотрели без учёта значимости. Результаты по большей части опять были представлены «корректными» совпадениями, хотя их состав изменился:

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

И наконец-то стали встречаться и интересные результаты:

URL: https://github.com/cguweb-com/Arduino-Projects

Лицензия: MIT License

Нашлись библиотеки с copyleft-лицензиями:

Библиотека в проверяемом репозитории: https://github.com/cguweb-com/Arduino-Projects/tree/cb5a4712f65acdd1623183609f027163f564fcbd/Nova-SM3/Remote%20Control/Code/Arduino%20Libraries/RF24

Источник https://github.com/nRF24/RF24/

Лицензия GPL-2.0

Библиотека в проверяемом репозитории: https://github.com/cguweb-com/Arduino-Projects/tree/cb5a4712f65acdd1623183609f027163f564fcbd/Nova-SM3/Code/Arduino%20Libraries/Adafruit_NeoPixel

Источник https://github.com/adafruit/Adafruit_NeoPixel

Лицензия LGPL-3.0

URL: https://github.com/nissl-lab/npoi

Есть совпадения в классе BigInteger, в том числе совпадения с классом MutableBigInteger из JDK на 40% (совпадения вплоть до комментариев).

Примеры совпадений:

URL: https://github.com/xiangyuecn/Recorder

Совпадает код некоторых функций с функциями из mp3 LAME encoder:

Примеры совпадений

Были найдены корректные, но любопытные пересечения. Например, между двумя репозиториями:

Оказалось, что во втором репозитории используется библиотека https://github.com/marek-stoj/NLangDetect, которая является портом под dotnet-библиотеку https://github.com/shuyo/language-detection, используемую в первом репозитории.

Ещё одна пара репозиториев:

В обоих используется портированный из Go код: https://github.com/moby/moby/blob/master/pkg/namesgenerator/names-generator.go.

Наверное, наиболее очевидным был выбор для попарной сверки репозиториев OpenOffice и LibreOffice. Из 1,7 ГБ файлов репозитория мы смогли распознать и проверить 245 МБ (13%) по поддерживаемым на текущий момент языкам. Множество файлов было отброшено, т. к. не представляют особого интереса, таковыми для нас были, например, *.xml, *.xslt, *.md, а также различные документы, файлы локализации и т. п. После обработки получилось около 221 млн символов, и в результате найдены пересечения по 27 млн символов (12%). В разбивке по языкам получились такие статистики:

Так, к примеру, для C# совпадают обвязки для работы с Uno Platform: https://github.com/apache/openoffice/tree/trunk/main/cli_ure/source/basetypes и https://github.com/LibreOffice/core/tree/master/cli_ure/source/basetypes/uno.

А ещё мы выборочно проверили открытые исходники известных компаний и проектов. Получили такие результаты.

Для справки

Мы намеренно не проверяли известные утёкшие исходники (Microsoft, Yandex и т. д.).

Яндекс https://opensource.yandex/projects/ или https://opensource.yandex/

Docker и Kubernetes

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

Apache Software Foundation

Отдельным пунктом было интересно сравнить между собой несколько IDE, для этого мы взяли NetBeans IDE, IntelliJ Community и Visual Studio Code. С VS Code пересечений не нашлось. При сравнении между собой NetBeans и IntelliJ обнаружили сильную схожесть используемых лексеров (e. g. TwigTopColoringLexer.java & _RegExLexer.java), но при разборе обнаружилось, что код автосгенерирован.

Проверяли библиотеку https://github.com/ricmoo/pyaes, нашли её же в исходниках другого репозитория https://github.com/Alessanddotnet swap variablesroZ/LaZagne/tree/master/Windows/lazagne/config/crypto/pyaes по очень неявному расположению.

Анализируя совпадения между репозиториями, мы обнаружили, что, несмотря на все наши усилия, большая часть совпадений совершенно неинтересна, т. к. туда попадают:

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

В тех репозиториях с GitHub, что удалось допроверить руками, в основном всё было хорошо, заимствование кода из copyleft-репозиториев встречалось относительно редко. Намного чаще имел место непорядок с лицензиями: в репозитории использовались библиотеки, для которых забыли указать лицензию, хотя и сам репозиторий, и библиотеки имеют permissive-лицензии. Впрочем, подобные нарушения достаточно легко исправляются.

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

Исходя из вышеуказанного, видятся следующие применения разработанного нами решения: