Сравнение исходных текстов программ путем выравнивания…
1
УДК 004.02
Сравнение исходных текстов программ путем
выравнивания последовательностей токенов
© А.В. Дубанов
МГТУ им. Н.Э. Баумана, Москва, 105005, Россия
В настоящее время весьма актуальна проблема обнаружения заимствований в
текстах. В данной работе был модифицирован один из известных алгоритмов вы-
равнивания последовательностей биополимеров для того, чтобы сравнивать ис-
ходные тексты программ и выявлять в них похожие фрагменты. Входными дан-
ными этого алгоритма являются исходные тексты программ, которые
рассматриваются как последовательности символов. Лексические домены при
этом соответствуют алфавиту символов, составляющих эти последовательно-
сти. Алгоритм был реализован в виде программы, его работа продемонстрирована
на фрагментах кода, написанных на языке Scheme. В статье обсуждаются пер-
спективы и ограничения применения алгоритма.
Ключевые слова:
заимствование кода, выравнивание последовательностей,
наибольшая общая подпоследовательность, динамическое программирование, лек-
сический анализ, функциональное программирование.
Введение.
Проблема поиска некорректных заимствований (в том
числе в исходных кодах программ) является весьма злободневной за-
дачей [1]. В практике кафедры «Теоретическая информатика и ком-
пьютерные технологии» эта задача систематически возникает при
проверке домашних заданий, результаты которых должны быть пред-
ставлены в виде программ на языках программирования высокого
уровня, и имеет целью выявление случаев «списывания». Для решения
этой задачи требуется разработать средства для сравнения исходных
текстов, позволяющие находить похожие или идентичные фрагменты
в исходных кодах программ, оценивать степень обнаруженного сход-
ства и наглядно представлять результат сравнения.
Очевидно, что такая задача является обобщением задачи нахожде-
ния наибольшей общей подпоследовательности в двух последователь-
ностях символов. Различные методы нахождения наибольших общих
или идентичных подпоследовательностей в исходном коде реализова-
ны в ряде компьютерных программ «антиплагиата», наиболее извест-
ной из которых является MOSS [2]. Однако практическое применение
программ «антиплагиата» имеет ряд ограничений как технических, так
и лицензионных. Среди удачных приемов следует отметить сравнение
не отдельных литер, а
токенов
. Это позволяет сделать метод нечув-
ствительным к переименованию идентификаторов.
