Многие (особенно в постсоветских странах) относятся к списыванию довольно беззаботно. Ученики в школах, студенты в университетах, а затем и специалисты в своей работе заимствуют чужие идеи и решения, не чувствуя вины за обман. Между тем плагиат — это не безобидное «подумаешь, списал», а серьезная проблема, которая ведет к мошенничеству и коррупции [1, 2]. 

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

Привет, Хабр! Меня зовут Карина Анисимова, я третьекурсница бакалаврской программы «Прикладная математика и информатика» петербургского кампуса НИУ ВШЭ. 

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

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

Чем особенна задача поиска плагиата в контестах?

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

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

При попытках выявления плагиата в коде как правило выделяют пять видов основных модификаций:

1. добавление или удаление комментариев;

2. добавление незначимых строк кода;

3. переименование переменных;

4. перемещение выражений без изменения семантики;

5. замена и видоизменение конструкций управления. Например, замена цикла for на цикл while или изменение условия внутри конструкции if else.

Покажу на примерах. Исходный код:

#include <iostream>
using namespace std;

int main()
{
	int a = 5, b = 2, c = 0;
	for (int i = 0; i < a; i++) {
		c += i;
		cout << i;
	}
	cout << c + a + b;
	return 0;
}

#include <iostream>
using namespace std;

int main()
/* comment */ {
	int a = 5, b = 2, c = 0;
	for (int i = 0; i < a; i++) {
		// comment
		c += i;
		cout << i;
	}
	cout << c + a + b;
	return 0;
}

#include <iostream>
using namespace std;

int main()
/* comment */ {
	int a, b, c, d;
	a = 5;
	b = 2;
	c = 0;
	d = 42;
	for (int i = 0; i < a; i++) {
		// comment
		c += i;
		cout << i;
	}
	int ans = c + a + b;
	cout << ans;
	return 0;
}

#include <iostream>
using namespace std;

int main()
/* comment */ {
	int x, y, z, t;
	x = 5;
	y = 2;
	z = 0;
	t = 42;
	for (int j = 0; j < x; j++) {
		// comment
		z += j;
		cout << j;
	}
	int out = z + x + y;
	cout << out;
	return 0;
}

#include <iostream>
using namespace std;

int main()
/* comment */ {
	int x = 5, y, z, t;
	z = 0;
	y = 2;
	for (int j = 0; j < x; j++) {
		// comment
		cout << j;
		z += j;
	}
	int out = z + x + y;
	cout << out;
	t = 42;
	return 0;
}

#include <iostream>
using namespace std;

int main()
/* comment */ {
	int x = 5, y, z, t, j = 0;
	z = 0;
	y = 2;
	while (j < x) {
		// comment
		cout << j;
		z += j;
		j++;
	}
	int out = z + x + y;
	cout << out;
	t = 42;
	return 0;
}

Существующие аналоги

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

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

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

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

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

Граф зависимостей программ

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

Существует два вида ребер:

• Ребра зависимости по данным соединяют вершины, в которых используются одинаковые данные. 

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

Например, для короткой программы:

program
	x := 5
	y := 5
	a := 1
	while a < 5 do
		x := x + y
		y := x - y
		a := a + 1
	end
end(x, y, a)

Граф зависимостей будет выглядеть так:

Цель работы

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

Целью моего исследования была оценка применимость алгоритма GPLAG к решению задачи поиска контестного плагиата.

Было выделено три основные задачи: 

• Реализация алгоритма из статьи GPLAG;

• Сбор датасета для проверки применимости к решению задачи выявления контестного плагиата;

• Проведение тестирования и анализ работы полученного решения.

Описание алгоритма

Алгоритм состоит из трех основных этапов. 

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

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

Построение графа

Для реализации первого этапа алгоритма нужно было научиться строить граф зависимостей программ. Для этого существует довольно много готовых инструментов, например Progex и TinyPDG. Однако оба этих инструмента работают только с  Java, и добавить другой язык программирования оказалось либо проблематично, либо вовсе невозможно. Поэтому я выбрала инструмент Joern. Он предоставляет возможность работы с C/C++ и Java, что сразу добавляет гибкости моей реализации, потому что охватывает наиболее популярные для решения контестных задач языки.

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

Сравнение графов

Следующий этап – это сравнение графов. Он оказался наиболее сложным для реализации. Задача поиска изоморфизмов на подграфах np-полная, но есть известные решения, которые выдают неплохую скорость работы. Наиболее распространенным сейчас является алгоритм VF2, он реализован в большинстве библиотек для работы с графами. Однако выяснилось, что он решает задачу поиска изоморфизмов вида граф-подграф, то есть во втором графе ищется подграф, изоморфный первому. А для моей задачи требуется алгоритм вида подграф-подграф, то есть поиск всех изоморфных пар подграфов. 

Я пробовала изучать другие алгоритмы, например алгоритм Ульмана, но сталкивалась с такой же проблемой. Тогда я решила свести задачу к поиску изоморфизмов вида граф-подграф. Для этого нужно у одного из графов построить все подграфы, а затем для каждой пары «подграф первого графа» и «второй граф» можно искать изоморфизмы вида граф-подграф известными алгоритмами. 

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

Решение этой проблемы нашлось в статье GPLAG. Авторы предложили зафиксировать наименьший размер подграфа, а именно 9 вершин, так как изоморфизм для более мелких подграфов можно считать совпадением, а не списыванием. Я решила пойти дальше и искать подграфы размера только 9, так как любой больший подграф с высокой вероятностью покроется несколькими подграфами размера 9. Эта эвристика помогла значительно повысить скорость нахождения подграфов, но время поиска для каждого запуска все равно оставалось довольно большим.

После изучения большого количества графов я заметила одну особенность. При построении появляется очень много подграфов, которые выглядят как несколько абсолютно не связанных частей программы и вершина, соответствующая точке входа в функцию, которая их объединяет. Мне показалось это не логичным, так как при построении хотелось получать подграфы, которые соответствуют полноценному участку программы. Тогда я решила попробовать удалить эту вершину. Результат меня удивил: количество подграфов сократилось в сотни раз. Возможно, это снизило качество сравнения программ, но позволило обрабатывать значительно бо́льшие программы.

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

Для поиска изоморфизмов я воспользовалась библиотекой networkX, в которой реализован алгоритм VF2. Однако на этом этапе возникла проблема. Очевидно, что структурный изоморфизм дает слишком грубое сравнение, и нужно обязательно учитывать типы вершин. Исходные типы вершин содержат детальную информацию о конкретной программе, например название переменных, поэтому две вершины, которые содержат один и тот же тип информацию, имеют разные типы. Поэтому было решено сузить типы вершин до 60 основных.

Примеры сужения типов:

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

Поддержка разных языков программирования

Обычно контесты пишут на C++, Java или Python. Я допускаю, что со временем этот список может расшириться, поэтому мне хотелось поддержать гибкость в работе с разными языками программирования. В итоге у меня получилось добиться возможности добавлять новый язык без особого труда. Для этого достаточно подобрать инструмент для построения графа по программе на нужном языке программирования, а также выделить основные типы вершин. 

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

Метрика

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

Похожесть принимает значения в промежутке от 0 до 1, где 0 соответствует полному отсутствию плагиата, а 1 – наличию значительного плагиата.

Датасет

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

Собранный датасет состоит из двух частей. Первая часть нужна для оценки способности алгоритма находить плагиат, а также чтобы оценить чувствительность к разным видам модификаций. Я написала скрипт, с помощью которого собрала 373 программы на языке C++ из 23 разных контестов с платформы Codeforces. Затем для каждой программы было нужно получить файлы с разными типами модификаций. Для этого я воспользовалась инструментом «Горшочек» и с его помощью получила файлы с тремя основными модификациями: добавление/удаление комментариев, переименование, замена взаимозаменяемых конструкций управления. К сожалению, другие модификации «Горшочек» не поддерживает, однако я смогла добавить в него возможность создать модификации вставки кода, поэтому файлы с такой модификацией тоже появились в датасете. Кроме того, я хотела получить файлы, приближенные к реальному плагиату. Для этого я построила файлы с комбинацией разных модификаций с помощью «Горшочка».

Вторая часть датасета нужна для оценки работы алгоритма в случаях отсутствия плагиата. Для него я выбрала две задачи: простую и сложную. Для простой задачи  собрала 23 решения (в каждом около 25 строк кода), а для сложной – 12 (в каждом около 60 строк кода). В дальнейшем планировалось попарное сравнение программ, решающих одну и туже задачу.

Пример решения простой задачи:

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        int a[n],max1=0,min1=1e9+1;;
        for(int i=0;i<n;i++) {
            cin>>a[i];
            max1=max(max1,a[i]);
            min1=min(min1,a[i]);
        }
        cout<<max1-min1<<"\n";
    }
    return 0;
}

Пример решения сложной задачи:

#include<bits/stdc++.h>
using namespace std;

int main()
{	int t;
	cin>>t;
	while(t--)
	{	int i,n,j,a=1,b,c;
		cin>>n;
		vector<int> v(n+1);
		unordered_map<int,int> m;
		v[0]=0;
		for(i=1;i<=n;i++)
		{	cin>>v[i];
			if(v[i]<=n)
				m[v[i]]++;
		}

		for(i=1;i<=n;i++)
		{	if(m[v[i]]!=1)
			{	int temp=v[i];
				while(temp>0)
				{	temp/=2;
					if(temp<=n)
					{	if(m[temp]==0)
						{	m[temp]=1;
							m[v[i]]--;
							v[i]=temp;
							break;
						}
					}
				}
				if(temp==0)
				{	cout<<"NO\n";
					a=0;
					break;
				}
			}
		}
		if(a)
			cout<<"YES\n";
	}
}

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

Ссылка на датасет: https://github.com/Karina5005/Plagiarism/tree/main/dataset/test 

Тестирование

Тестирование и анализ результатов заняли большую часть времени работы над проектом. Всего мы провели более 2500 сравнений.

Результаты тестирования представлены в таблице:

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

К сожалению, при сравнении решений простой задачи выявилась неточность. Нашелся набор программ, на которых значение похожести оказалось больше, чем хотелось бы. Это объясняется небольшим размером программ, а также простотой задачи – все решения действительно чем-то похожи. Из этого можно сделать вывод, что на маленьких программах алгоритм GPLAG может вести себя некорректно. 

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

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

Итоги

Мне удалось реализовать алгоритм из статьи GPLAG с поддержкой разных языков программирования и разными подходами к построению графа зависимостей программ. 

Для этого я построила датасет из 372 программ с 4 видами модификаций и собрала 673 пар программ для проверки случаев отсутствия плагиата. Этот датасет теперь позволяет проводить тестирования и других алгоритмов для поиска контестного плагиата.

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

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

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

Ссылка на репозиторий.