Алгоритм нечеткого сравнения исходных кодов программ

П.А. Хаустов, Ю.Я. Кацман
Томский политехнический университет,
г. Томск


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

В конце 2010 года на проблему плагиата обратило внимание руководство Московского государственного университета. Спустя несколько месяцев на сайте Томского политехнического университета появилась новость о том, что ТПУ поддерживает эту идею. Предполагается, что университет закупит специальное программное обеспечение, которое позволит отслеживать случаи плагиата среди студентов.

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

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

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

Задачей проекта «NoCrib» является создание и реализация алгоритма, позволяющего сравнить два исходных кода написанных на одном и том же языке программирования и релевантная оценка степени схожести этих кодов.

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

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

· алгоритм должен распознавать хотя бы основные ключевые слова языка;

· переменные не должны считаться разными, если они отличаются только именем;

· при обмене местами двух функций код не должен распознаваться, как совершенно другой;

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

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

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

Для анализа использован алгоритм, основанный на построении trie-деревьев исходного кода (http://en.wikipedia.org/wiki/Trie). Такие деревья используются в программировании для хранения словаря, в вершинах этих деревьев находятся символы используемого алфавита. В данном случае хранить код как набор слов нерационально, так как многие слова являются лишь именами переменных или функций, и, в случае замены имен функций и переменных, полученный исходный код будет рассматриваться, как код абсолютно непохожий на изначальный.

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

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


Рассмотрим для примера следующий исходный код на языке C++:

int f(int x)

{

return x & 1 + 1;

}

int main()

{

int x = 100, k = 0;

while (x)

{

x -= f(x);

++k;

}

return 0;

}

Упрощенное trie-дерево лексем, построенное по этому коду, представлено на рисунке:

Упрощенное дерево лексем

На рисунке некоторые вершины (блоки) содержат несколько лексем. В действительности каждая из этих лексем соответствует единственной вершине, которые, в свою очередь, образуют цепочку. Здесь приняты обозначения: VAR – имя переменной, NUM – арифметическая константа, FNAME – имя функции.

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

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

Стоит отметить, что для сравнения второго кода с первым не требуется создавать trie-дерево лексем для второго кода, так как в любой момент времени требуется хранить в памяти не более одной ветки оператора второго кода (то есть самого оператора и всех предшествующих ему уровней вложенности представленных в виде последовательности лексем). Для ветки каждого оператора второго кода можно идти по дереву лексем первого кода обходом в глубину от корня и смотреть есть ли точно такая же ветка в этом дереве. Очевидно, что если вся ветка не присутствует в дереве, то при обходе из корня возникнет ситуация, когда у текущей вершины среди детей нет вершины с нужным идентификатором лексемы. Количество вершин, посещенных до этого момента, обозначим за X. Количество вершин в самой ветке обозначим за Y. Очевидно, что если в дереве присутствует искомая ветка, то X = Y, в остальных случаях X < Y.

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

Для подсчета общей схожести исходных кодов используется значение x = C / Z, где C – сумма X2 для всех веток, Z – сумма Y2 для всех веток. Функция оценки похожести кодов имеет вид:

и принимает значения от 0 (абсолютная различимость) до 100 (абсолютная идентичность).

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

Рассмотрим работу системы сравнения двух кодов (C++):

Сумма двух чисел

Сумма двух чисел (имена переменных изменены)

#include <iostream>

#include <cstdio>

#include <cmath>

using namespace std;

int main()

{

int a, b;

cin >> a >> b;

int c;

cout << (c = a + b) << endl;

return 0;

}

#include <iostream>

#include <cstdio>

#include <cmath>

using namespace std;

int main()

{

int oper1, oper2;

cin >> oper1 >> oper2;

int res;

cout << (res = oper1 + oper2) << endl;

return 0;

}

Результат сравнения (схожесть в процентах) равен 100.000000.

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

Сравним код суммы двух чисел с кодом поиска максимума в линейном массиве.

#include <iostream>

#include <cstdio>

#include <cmath>

using namespace std;

int main()

{

int n, mx;

cin >> n;

for (int i = 0; i < n; ++i)

cin >> a[i];

mx = a[0];

for (int i = 1; i < n; ++i)

mx = max(a[i], mx);

cout << mx << endl;

return 0;

}

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


Назад к списку