Jak wykrywać plagiaty? Część pierwsza!

Jak wspomniałem w pierwszym wpisie w ramach Daj Się Poznać 2017, aplikacja, którą piszę będzie odpowiedzialna za wykrywanie plagiatów w kodach źródłowych programów.

W tym i w kilku (0, 1 lub 2 :P) kolejnych wpisach postaram się przedstawić kilka istniejących podejść do tego problemu.

Systemy bazujące na zliczaniu atrybutów

Pierwszymi automatycznymi systemami do wykrywania plagiatów w kodach źródłowych programów były systemy polegające za zliczaniu i porównywaniu atrybutów programów.

Miara złożoności Halstead’a

Pierwszym automatycznym systemem służącym do automatycznego porównywania stopnia podobieństwa między kodami źródłowymi programów był system zaproponowany przez Halsted’a w 1977 roku. System ten do mierzenia podobieństwa programów używał czterech statystyk programu:

  • {\eta_1} – liczba unikalnych operatorów
  • {\eta_2} – liczba unikalnych operandów
  • {N_1} – liczba wystąpień operatorów
  • {N_2} – liczba wystąpień operandów

Pary programów, u których powyższe wartości były identyczne były dalej przeglądane przez człowieka w celu stwierdzenia lub odrzucenie zajścia plagiatu (spora wada tego systemu ;)).

Powyższy system miał bardzo ograniczone możliwości. Statystyki takie jak liczba wystąpień operatorów czy ilość unikalnych operatorów są wartościami, które można w bardzo łatwy sposób zmienić, a co za tym idzie oszukać opisany wyżej system.

System Accuse Grier’a

System Accuse, stworzony przez Grier’a, powstał na bazie wcześniej opisanego systemu. Grier w swoim systemie do badania podobieństw między programami używa następujących statystyk:

  • liczba unikalnych operatorów
  • liczba unikalnych operandów
  • liczba wystąpień operatorów
  • liczba wystąpień operandów
  • liczba linii kodu
  • liczba zmiennych zadeklarowanych i użytych
  • liczba wszystkich instrukcji kontrolnych

W pierwszej fazie system Accuse zliczał dla każdego programu wyżej wymienione parametry. W drugiej fazie jest obliczania korelacja pomiędzy parami programów. Przy obliczaniu korelacji używane są dwa stałe parametry:

  • rozmiar okna (window) – określa maksymalną różnicę pomiędzy zliczonymi statystykami dwóch programów
  • wartość ważności (importance) – waga danego parametru przy obliczaniu korelacji

Następnie korelacja jest obliczana w następujący sposób:

  • wartość korelacji jest ustawiana na 0
  • dla każdej metryki wykonywane jest:
    • jeżeli {A_i} jest wartością i-tej metryki programu A i {B_i} jest korenspondującą metryką w programie B wtedy {diff_i=|A_i-B_i|}.
    • jeżeli {diff_i\le window_i} wtedy {correlation_{AB} += importance_i-diff_i}.

Przy parach programów z dużą wartością obliczonej korelacji zachodzi prawdopodobieństwo plagiatu i programy te powinny zostać przejrzane przez człowieka (tym razem jest o tyle lepiej, że nie wszystkie porównania muszą zostać przejrzane ;)).

System Faidhi-Robinson

Faidhi i Robinson stworzyli listę metryk służącą do wykrywania plagiatów. Metryki te według nich miały być lepsze od metryk opisanych w systemie Accuse. Metryki te, nie korelują ze sobą, a dodatkowo w tych metrykach są ukryte dodatkowe miary, które powinny być ciężkie do zmiany przynajmniej przez programistę (a przynajmniej początkującego ;).

Pierwsze dziesięć metryk Faidhi i Robinson zakwalifikowali do grupy metryk, które według nich może bez większego problemu zmienić nawet początkujący programista.

  1. średnia ilość znaków na linię
  2. liczba linii z komentarzami
  3. liczba linii z wcięciami
  4. liczba pustych linii
  5. średnia długość procedury lub funkcji
  6. liczba słów kluczowych
  7. średnia długość identyfikatora
  8. średnia ilość spacji na linię
  9. liczba etykiet i poleceń goto
  10. liczba unikalnych identyfikatorów

Kolejne 14 metryk zostało wybranych jako metryki mierzące strukturę programu, które są trudne do zmodyfikowania przez programistę.

  1. liczba etapów programów – przy pomocy algorytmu Cocke’a i Allen’a jest tworzony graf przepływu
  2. liczba kolorów wierzchołków o kolorach 1 i 2 w pokolorowanym grafie przepływu
  3. liczba wierzchołków mających kolor 3
  4. liczba wierzchołków mających kolor 4
  5. procentowa ilość wyrażeń w programie
  6. procentowa ilość prostych wyrażeń w programie
  7. procentowa ilość termów w programie
  8. procentowa ilość współczynników w programie
  9. liczba zbędnych rzeczy w programie – np. zbędne średniki lub pary BEGIN/END
  10. liczba linii wewnątrz funkcji i procedur
  11. liczba funkcji i procedur
  12. procentowa ilość wyrażeń warunkowych
  13. procentowa ilość powtarzających się wyrażeń
  14. liczba instrukcji w programie

W systemie Faidhi-Robinson, podobnie jak w poprzednim systemie, do obliczania podobieństwa użyto dwóch stałych parametrów:

  • rozmiar okna (window)
  • wartość ważności (importance)

Algorytm obliczania podobieństwa wygląda następująca:

  • dla każdej metryki:
    • {increment_i=\frac{window_i-diff_i}{window_i}\cdot importance_i}

Całkowita korelacja wynosi zatem:

{\sum_{i=1}^{24} increment_i}.

Im otrzymana korelacja miała większą wartość tym zachodziło większe prawdopodobieństwo plagiatu.

Krótkie podsumowanie

W tym wpisie przedstawiłem kilka pierwszych systemów do wykrywania plagiatów w kodach źródłowych. Niestety nie były one zbyt efektywne.

W kolejnych wpisach opiszę kilka innych podejść do wykrywania plagiatów, które charakteryzują się większą skutecznością.

2 przemyślenia nt. „Jak wykrywać plagiaty? Część pierwsza!”

  1. Ciekawy temat! Pamiętam, że przewijał się jakoś na studiach i nawet chcieli mi i paru kolegom coś podobnego zlecić w ramach jakiegoś projektu zespołowego. Ale w końcu temat nie poszedł do realizacji, więc nigdy nie miałem potrzeby go zgłębić. Chętnie przeczytam przyszłe posty o tym.

Dodaj komentarz

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