Jak wykrywać plagiaty? Część trzecia!

Dzisiaj będzie kontynuacja dwóch poprzednich wpisów (1 i 2) dotyczących sposobów wykrywania plagiatów. Dzisiaj będzie ostatni wpis z tej serii. Opiszę w nim kolejne 3 sposoby wykrywania plagiatów.

Systemy bazujące na analizie drzewa wyprowadzeń

Systemy opierające się na analizie drzewa wyprowadzeń wyszukują podobieństwa między programami poprzez wyszukiwanie identycznych lub podobnych poddrzew w drzewie wyprowadzeń.

System CloneDR

System CloneDR jest komercyjnym systemem stworzonym przez firmę Semantic Designs. Działanie systemu opiera się na sprowadzeniu kodu źródłowego programu do drzewa wyprowadzeń, a następnie każda para drzew dwóch programów jest testowana w 3 fazach:

  1. wykrywanie identycznych i bardzo podobnych powtórzeń poddrzew w badanych drzewach
  2. wykrywanie powtórzeń deklaracji w kodzie
  3. wykrywanie podobnych poddrzew, które nie zostały znalezione w pierwszej fazie

Na podstawie danych zebranych podczas tych trzech faz algorytmu system decyduje o prawdopodobieństwie zajścia plagiatu.

Systemy bazujące na analizie grafu zależności

Systemy opierające się na analizie grafu zależności opierają się na budowie i badaniu grafu zależności programów.

System GPlag

Analizowane dane w system GPlag są reprezentowane przez grafy zależności i przepływu danego programu.

Szukanie podobieństw polega na szukaniu izomorficznych podgrafów pomiędzy dwoma drzewami programów.

Systemy bazujące na aproksymacji złożoności Kołmogorowa

Podejście do wykrywania plagiatów poprzez złożoność Kołmogorowa stawia na szukanie podobieństw w ilości informacji niesionych przez program.

Teraz będzie ciężko…

Niech {\mu = (M_1,M_2,\ldots)} będzie ciągiem wszystkich maszyn Turinga zakodowanych za pomocą słów nad alfabetem {\{0,1\}}. Dla każdego słowa {x\in\{0,1\}^{*}} możemy zdefiniować jego złożoność Kołmogorowa względem {\mu} jako
{K_{\mu}(x)=min\{|M_{j}|:M_{j}(\epsilon)=x\}}

A co to znaczy bardziej po ludzku?

Intuicyjnie można powiedzieć, że złożonością Kołmogorowa jest wielkość najmniejszego ciągu, z którego można odtworzyć ciąg x.

Ideą działania systemów opierających się na aproksymacji złożoności Kołmogorowa jest znalezienie właśnie tej aproksymacji dla każdego programu poprzez kompresje danego ciągu.

W przypadku systemów do wykrywania plagiatów przez {K(x)} określa się długość mierzoną w danej jednostce (np. bajty) najkrótszego programu, który dla pustego wejścia zwróci na wyjściu x. Przez {K(x|y)} rozumie się warunkową złożoność Kołmogorowa. Określa ona ile nowych informacji wnosi napis x, w przypadku kiedy mamy już dany napis y.

Odległość między dwiema złożonościami Kołmogorowa jest definiowana jako:

{d(x,y) = 1 - \frac{K(x)-K(x|y)}{K(xy)}}, gdzie:
{K(x)-K(x|y)} określa ile informacji o słowie x znajduje się w słowie y.

System SID

Ideą działania algorytmu SID jest tokenizacja ciągu wejściowego, jego kompresja oraz przybliżenie złożoności Kołmogorowa.

Pierwszym etapem systemu SID jest zamiana kodu programu źródłowego na ciąg Tokenów przy użyciu parsera.

W kolejnym etapie ciąg tokenów jest poddawany silnej kompresji bezstratnej algorytmem TokenCompress. Twórcy systemu oparli swój algorytm kompresji na algorytmie LZ z pewnymi modyfikacjami. Istotne było uzyskanie jak największego stopnia kompresji, kosztem czasu kompresji.

Aproksymacja {d(x,y)} jest liczone w następujący sposób:
{d(x,y) = 1 - \frac{Comp(x)-Comp(x|y)}{Comp(xy)}}, gdzie:
{Comp(x)} jest skompresowaną wielkością słowa x.

Im obliczona wartość jest bardziej zbliżona do 0 tym odległość w sensie informacyjnym jest między programami mniejsza i tym samym jest większe prawdopodobieństwo, że programy są do siebie podobne.

Podsumowanie

Tak jak wspomniałem we wstępie, wpisem tym kończę przegląd istniejących sposobów wykrywania plagiatów. Z wszystkich wymienionych sposobów wybiorę jeden i będę starał się go zaimplementować, a następnie przetestować w praktyce 🙂

Jedno przemyślenie nt. „Jak wykrywać plagiaty? Część trzecia!”

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *