Разработка шумового фильтра для двигателя обнаружения плагиата в Ruby

Question

Я работал над внедрением механизма обнаружения плагиата, основанного на академической статье за ​​MOSS(мера сходства программного обеспечения)

Ссылка на MOSS

Для разработки шумового фильтра для такого языка, как C/C++/Java, я должен принять несколько решений.

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

Как бороться с идентификаторами? Замена всех ключевых слов одним символом 'V' делает сопоставление независимым от имени переменной, имеет смысл.

Что делать с импортом пакетов и библиотекой?

Пробелы, комментарии и знаки препинания должны быть обязательно удалены.

Мне интересно, после выполнения всех операций, исходный файл будет просто буквой "V" и некоторым другим искаженным текстом.

Какие операции должен выполнять шумовой фильтр?

Выводы и мнения о лучшем способе борьбы с шумом?

Answer 1

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

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

Некоторые фрагменты более характерны, чем другие, фрагмент

for (i=0; i < 12345; i++) {
  array[i] = 54321;
  }

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

j=0;
while ( j < 12345) {
  foobar[j++] = 54321;
  }

и компилятор, вероятно, будет производить идентичный код.

Могут быть различия в именах переменных, числовых константах, адресных константах, чем угодно. Но "скелет" ключевых слов (-> {сравнения, циклы, выражения, присваивания, вызовы функций}) будет таким же. Итак: не отбрасывайте ключевые слова, они являются основой программы.

Answer 2

В Google можно найти много интересного, если вы ищете "текстовый отпечаток пальца". Черепица - это х-слово (х =7 во многих исследовательских проектах). Вы строите набор всех черепиц слово за словом.

Вы строите хэш над галькой и затем сравниваете 1000-ю гонт в тексте. Это довольно просто. Есть несколько вещей, таких как специальные хеш-функции, которые вы наверняка не слышали вне этого контекста и т. Д.

Начните с чтения, например, это не совсем ракетостроение, но и не тривиальное.

"Эффективное определение происхождения текста" Бесник Фетаху, Андреас Фрише http://resources.mpi-inf.mpg.de/d5/teaching/ws10_11/hir/reports/BesnikFetahu.pdf

"Алгоритмы дублирования документов", Андрей Бродер http://www.cs.princeton.edu/courses/archive/spr05/cos598E/bib/Princeton.pdf