Testowania część druga!

Dzisiaj przetestujemy nasz algorytm po raz kolejny!

Zestaw testowy

Tym razem jako zestaw testowy posłużą nam kody źródłowe z kursu programowania z moich studiów. Podczas kursu trzeba było między innymi napisać programy, które rozłożą liczbę na czynniki pierwsze oraz wyliczą sito Eratostenesa. I właśnie kody źródłowe do tych dwóch zadań poddamy testom.

Udało mi się skolekcjonować po 5 różnych rozwiązań dla każdego z tych zadań. Wszystkie kody źródłowe są dostępne tutaj.

Testowanie

Przetestujmy kody źródłowe dla każdego zadania osobno.

Rozkład liczby na czynniki pierwsze

Zacznijmy najpierw od wczytania kodów źródłowych i wyliczenia prawdopodobieństw.

Po wywołaniu powyższego kodu otrzymaliśmy następujące wyniki:

Przeglądając wyniki możemy zauważyć, że kody źródłowe programów 4 i 5 zostały wskazane jako bardzo podobne do siebie. Zachęcam, aby przejrzeć te kody oraz porównać również z innymi. Łatwo możemy zauważyć, że te dwa kody źródłowe wykazują bardzo dużo cech wspólnych 😉

Podobnie sprawa wygląda w przypadku kodów 1 i 2, lecz podobieństwo jest już trochę mniej widoczne.

Sito Eratostenesa

Kolejnym zestawem będą programy, które implementują algorytm Sita Eratostenesa. Podobnie jak poprzednio zacznijmy od wczytania kodów źródłowych i wyliczenia podobieństw pomiędzy nimi.

I wyniki, które otrzymaliśmy po uruchomieniu powyższego kodu:

Tutaj możemy dostrzec, że największe prawdopodobieństwo plagiatu zachodzi pomiędzy programami 1 i 2. I ponownie gdy obejrzymy oba kody źródłowe znajdziemy widoczne podobieństwo.

Podsumowanie

Dzisiaj przetestowaliśmy nasz algorytm na zestawie kodów źródłowych z moich studiów. Analizując wyniki mogliśmy wskazać kody, które wykazywały nieprzeciętne podobieństwo 😉 Wydaje się, że algorytm działa dosyć dobrze i całkiem nieźle wskazuję podobne kody źródłowe.

Przetestujmy skuteczność algorytmu – część pierwsza!

Dzisiaj zajmiemy się przetestowaniem naszego algorytmu do wykrywania plagiatów w praktyce. Miejmy nadzieję, że to chociaż trochę zadziała 😉

Zestaw testowy

Musimy najpierw zacząć od przygotowania danych, na których będziemy testować naszą aplikacje.

Dzisiaj przygotujemy specjalnie spreparowane kody źródłowe i zobaczymy jak z nimi poradzi sobie nasza aplikacja.

Zacznijmy od stworzenia naszej wyjściowej klasy, która będzie zawierała kilka pól oraz metod.

Będzie to nasz wyjściowy kod, od którego będziemy robić wszystkie modyfikacje.

Wykonajmy następujące modyfikacje kodu:

  1. Zmieńmy nazwy metod i pól
  2. Przenieśmy operacje z metod do metody main, a same metody usuńmy
  3. Dodajmy kilka nieużywanych metod
  4. Czwartym kodem do porównania, będzie kopia oryginalnego kodu

Testujemy!

Stwórzmy prostą metodę, która wczyta nasze kody źródłowe oraz wywoła naszą aplikacje i wyliczy prawdopodobieństwo.

Omówmy wyniki!

Pora na krótką analizę wyników.

  1. Zmienione nazwy metod i pól
    Program zwrócił następujący wynik:

    Tutaj możemy zauważyć, że program poradził sobie całkiem nieźle. Wskaźniki są bardzo bliskie 1, więc możemy z dużą dozą prawdopodobieństwa stwierdzić, że porównywane programy zawierają ten sam kod.
  2. Kod z metod przeniesiony do głównej metody
    Zwrócony wynik:

    Tutaj niestety algorytm poradził sobie dużo gorzej. Wystarczyła drobna zmiana w kodzie i stopień wykrywalności jest o wiele mniejszy. Może to byś spowodowane tym, że testowany kod jest krótki i nawet takie małe zmiany znacząco wpływają na wyniki. Warto na pewno się temu przyjrzeć w przyszłości.
  3. Kod z nieużywanymi metodami
    Wyliczone podobieństwo:

    Na tym przykładzie możemy zobaczyć w praktyce wykorzystanie wskaźników px oraz py. O ile główny wskaźnik wynosi tylko 0.63 i nie musi wydawać się podejrzany, o tyle wartość wskaźnika px (0.92) mocno wskazuje, że jeden z porównywanych kodów zawiera dużą część drugiego kodu, oraz że mógł zajść plagiat.
  4. Porównanie dwóch identycznych kodów źródłowych
    Wynik:

    Tutaj podobnie jak w pierwszym przypadku algorytm poradził sobie bardzo dobrze i wyliczył wskaźniki bliskie 1.

Podsumowanie

Dzisiaj wykonaliśmy pierwsze testy naszego algorytmu. Do testów użyliśmy kilka spreparowanych kodów źródłowych. Pierwsze wyniki wskazują, że algorytm jakieś prawdopodobieństwo wylicza 😉

W następnym wpisie odnośnie PlagDetectora przeprowadzimy testy na kodach źródłowych z28za czasów studenckich 😉

Wyliczmy podobieństwo!

W poprzednim wpisie dotyczącym PlagDetectora zajmowaliśmy się kompresją tokenów. Dzisiaj zajmiemy się trzecim i zarazem ostatnim krokiem naszego algorytmu, a mianowicie wyliczaniem podobieństwa pomiędzy kodami źródłowymi.

Mała powtórka

Na początku wróćmy do wpisu gdzie omawialiśmy cały algorytm i przypomnijmy sobie kilka wzorów.

Wartość aproksymacji Kołmogorowa będziemy przybliżać przy pomocy poniższego wzoru.
{d(x,y) = 1 - \frac{K(x)-K(x|y)}{K(xy)}}.

Przez {\emph{K(x)}} będziemy rozumieć wielkość (w bajtach) skompresowanego kodu źródłowego i będziemy oznaczać jako {\emph{Comp(x)}}. W związku z tym wzór na przybliżenie aproksymacji Kołmogorowa przyjmie postać:

{d(x,y) = 1 - \frac{Comp(x)-Comp(x|y)}{Comp(xy)}}.

Wartość {\emph{Comp(x|y)}} obliczymy w następujący sposób:
{Comp(x|y) = Comp(xy) - Comp(y)}.

Zatem ostatecznie wartość aproksymacji Kołmogorowa obliczymy z następującego wzoru:
{d(x,y) = 1 - \frac{Comp(x)+Comp(y)-Comp(x|y)}{Comp(xy)}}.

Tak obliczona wartość aproksymacji złożoności Kołmogorowa przeliczymy na współczynnik {\emph{D}} według wzoru:
{D = 1 - d(x,y)}.

I ten właśnie wskaźnik będzie naszym głównym wyznacznikiem, którego będziemy używać do oceny prawdopodobieństwa zajścia plagiatu.  Im wartość {\emph{D}} jest większa, tym prawdopodobieństwo plagiatu jest większe.

Dodatkowo dla każdej pary programów obliczymy wartości {\emph{px}} oraz {\emph{py}}. Wartości te będą przedstawiać procentową zawartość informacji z jednego kodu źródłowego zawartych w drugim. Wartości te obliczymy używając następujących wzorów:
{px=\frac{D(\alpha + 1)}{D+1}},
{py=\frac{D(\frac{1}{\alpha} + 1)}{D+1}}, gdzie:
{\alpha = \frac{Comp(y)}{Comp(x)}}.

Wskaźniki {\emph{px}} i {\emph{py}} posłużą nam jako dodatkowa informacja, wskazująca na zawartość jednego ciągu w drugim. Wartości te pomogą nam wskazać zajście plagiatu, w przypadku gdy jeden z programów zawiera w sobie kod drugiego, lecz sam program jest o wiele bardziej rozbudowany i wartość współczynnika {\emph{D}} może nie wskazać zajścia plagiatu.

I teraz kodowanie!

Zacznijmy od klasy, która przechowa nasze wyniki.

Podobnie jak przy tworzeniu klasy do przechowywania wyników kompresji – banał 😉

Teraz pora na obliczenia!

Tym razem nie zobaczymy żadnej magii w kodzie. Mamy tylko zwykłe przepisanie wzoru na Kotlina 😉

Podsumowanie

Dzisiaj zajęliśmy się ostatnim krokiem algorytmu, a mianowicie aproksymacją złożoności Kołmogorowa. Przypomnieliśmy sobie wzory potrzebne do obliczeń, a następnie zaadoptowaliśmy te wzory do naszego kodu. W następnym wpisie wykonamy w końcu nasze 3 kroki razem i przetestujemy działanie algorytmu 🙂

Czas na trochę kompresji!

W poprzednim wpisie na temat PlagDetectora opisaliśmy tokenizacje kodu źródłowego. Był to pierwszy z trzech etapów całego algorytmu. Dzisiaj zajmiemy się drugim krokiem, czyli kompresją tokenów.

Kilka słów o samej kompresji

Kompresja, jak sama nazwa wskazuje ;), jest to przetworzenie pewnej informacji w taki sposób, aby można było zapisać tą informacje w krótszy sposób. Przez słowo krótszy mam na myśli przy użyciu mniejszej ilości bajtów. Operacją odwrotną do kompresji jest dekompresja.

Rodzaje kompresji

Kompresje możemy podzielić na stratną oraz bezstratną. Jak sama nazwa wskazuje, w przypadku kompresji stratnej tracimy część informacji, dzięki czemu powinniśmy uzyskać większy współczynnik kompresji (przynajmniej w teorii ;)).

Oczywiście istnieje wiele algorytmów kompresji, które możemy przyporządkować do kompresji stratnej lub bezstratnej.

Spójrzmy na poniższy podział algorytmów.

  • Kompresja bezstratna
    • Kodowanie Huffmana
    • Kodowanie arytmetyczne
    • Kodowanie Shannona
    • Algorytmy słownikowe
      • LZ77
      • LZ78
      • LZW
    • PNG
  • Kompresja stratna
    • Kodowanie transformatowe
    • Kompresja falkowa
    • JPEG
    • MPEG

Oczywiście to nie są wszystkie istniejące algorytmy kompresji, ale wydaję mi się, że te najbardziej znane 🙂

Który algorytm wybrać?

Jak widzieliśmy, jest wiele algorytmów kompresji bezstratnej. Który zatem powinniśmy wybrać? Sugerując się tym co wybrali twórcy algorytmu SID (opisanym w jednym z poprzednich wpisów), również skupimy się na kodowaniu słownikowym, a konkretnie LZ77. Czemu własnie LZ77, a nie żaden z innych algorytmów kodowania słownikowego jak LZ78 czy LZW, które są rozwinięciem LZ77 (i często działają lepiej)? Zaraz wszystko powinno się wyjaśnić 🙂

Trochę teorii 🙂

Spójrzmy najpierw jak działa LZ77.

Jak wcześniej wspomnieliśmy, LZ77 jest algorytmem słownikowym? Znaczy to dokładnie tyle, że do zakodowania/odkodowania tekstu używamy słownika. W LZ77 słownik jest dynamiczny, czyli taki słownik, który jest tworzony w trakcie kodowania. Słownik tego typu ma również tę zaletę, że dostosowuje się do charakteru danych. W LZ77 słownikiem jest zakodowana/odkodowana część tekstu.

I teraz sam algorytm w teorii:

  • Dla zakodowanej części długości n i niezakodowanej długości m, czyli dla ciągu {x_1 \ldots x_nx_{n+1} \ldots x_{n+m}} szukamy najdłuższego podsłowa w ciągu ̇ {x_1 \ldots x_n} będącego prefiksem ciągu {x_{n+1} \ldots x_{n+m}} (dopasowanie).
  • Jako kod podajemy trzy liczby:
    • wielkość przesunięcia w lewo
    • ilość kopiowanych znaków
    • kod pierwszej niepasującej litery
  • Jeżeli pojawia się nowa litera, której nie można znaleźć w zakodowanej części to do słownika dodajemy {(0, 0, LITERA)}

Brzmi skomplikowanie, ale przykład powinien nam wszystko wyjaśnić 🙂

Najpierw ustalmy nasze n (bufor słownika) i (bufor kodowania). Przyjmijmy odpowiednio 7 i 8. Spróbujmy teraz zakodować następujący ciąg: abccba-abba.

  • abccba-abba    (0, 0, a)
  • abccba-abba    (0, 0, b)
  • abccba-abba    (0, 0, c)
  • abccba-abba    (1, 1, b)
  • abccba-abba    (5, 1, -)
  • abccba-abba    (7, 2, b)
  • abccba-abba    (0, 0, a)

Zatem ostatecznie nasz zakodowany ciąg ma postać powyższych siedmiu ‚trójek’, czyli: (0, 0, a), (0, 0, b), (0, 0, c), (1, 1, b), (5, 1, -), (7, 2, b), (0, 0, a).

Czemu właśnie LZ77?

I teraz wracamy do kwestii wyboru algorytmu. Dlaczego właśnie LZ77? Tak jak pisaliśmy w jednym z poprzednich wpisów, musimy ustawić nieskończony bufor słownika i bufor kodowania. Wiążę się to oczywiście z wydłużeniem czasu kompresji, ale dzięki temu możemy uzyskać większy stopień kompresji.

W tym samum wpisie, w kolejnej sekcji, jest opisana część z aproksymacją złożoności Kołmogorowa. W jednym ze wzorów możemy dopatrzeć się, że kompresji będzie również poddana lista składająca się z tokenów z dwóch porównywanych kodów źródłowych. Jakie to ma znaczenie przy wyborze algorytmu kompresji?

Wróćmy do naszego przykładu i zastanówmy się co by się stało jakbyśmy przyjęli, że n i m są nieskończone oraz mieli do zakodowania ciąg: abccba-abbaabccba-abba (podwojony ciąg z naszego przykładu).

Pierwsze sześć kroków kodowania wygląda identycznie, więc możemy zacząć ten przykład od własnie szóstego kroku.

  • abccba-abbaabccba-abba    (7, 2, b)
  • abccba-abbaabccba-abba    (3, 1, a)
  • abccba-abbaabccba-abba    (11, 9, a)

Zauważmy, że do zakodowaniu podwojonego ciągu potrzebowaliśmy tylko jednej ‚trójki’ więcej. I to jest własnie właściwość, na której nam zależy, a której nie mają LZ78 i LZW. Chcemy wykrywać plagiaty, więc powinniśmy założyć, że tokeny porównywanych kodów źródłowych mogą być takie same lub bardzo podobne ;).

I trochę praktyki!

I w końcu trochę kodu! 🙂

Zacznijmy od stworzenia klasy, która będzie nam reprezentować zakodowaną ‚trójkę’.

Banał 😉

Teraz niestety trochę magii…

Powyżej zaimplementowaliśmy algorytm LZ77 z nieograniczonym buforem słownika i kodowania. Użyty algorytm jest napisany dosyć ‚prostacko’, ale działa 🙂 Przy najbliższej okazji wrócimy do niego i go zrefaktorujemy 😉

Podsumowanie

Dzisiaj zajęliśmy się drugim etapem w naszym algorytmie do wykrywania plagiatów., a mianowicie kompresją tokenów. Zobaczyliśmy jak wygląda LZ77 i zobaczyliśmy jak działa. Na koniec w trochę prostacki sposób zaimplementowaliśmy LZ77 z nieograniczonym buforem słownikowym i kodowania w Kotlinie ;). W następnym wpisie związanym z PlagDetectorem zajmiemy się trzecim etapem czyli aproksymacją złożoności Kołmogorowa 🙂

Tokenizacja kodu źródłowego

W tym wpisie opiszę pierwszy etap w wykrywaniu plagiatów w Plag-Detectorze.

O co właściwie chodzi?

Tokenizacja jest terminem występującym często w tematyce związanej z bezpieczeństwem czy też szyfrowaniem. W tym przypadku chodzi o coś trochę innego. Wspomniałem o tym w jednym z poprzednich wpisów.

Poniżej użyję tego samego przykładu, którego użyłem w tamtym wpisie.

Ideą tokenizacji jest zamiana kodu źródłowego na ciąg tokenów. W listingu powyżej można zobaczyć jak może wyglądać przykładowa tokenizacja kawałka kodu.

Jak to zrobić w praktyce?

Oczywiście można by samemu napisać tokenizer, ale byłaby to dość skomplikowana i długa robota. Oczywiście zakładając, że tokenizer powinien uwzględniać gramatykę danego języka. Z pomocą przychodzi nam ANTLR, czyli ANother Tool for Language Recognition.

Dla ANTLRa możemy zdefiniować gramatykę, według której będzie przeprowadzona tokenizacja. Zdefiniowanie gramatyki dla każdego języki również byłoby dosyć karkołomnym zadaniem. Na szczęście większość gramatyk dla popularnych języków programowania została już zdefiniowana i jest dostępna tutaj: https://github.com/antlr/grammars-v4.

Konfiguracja i użycie ANTLRa

Ponieważ jesteśmy leniwi, chcemy żeby wszystko nam się robiło automatycznie. I tak jest w tym przypadku 🙂

Zależności

Konfiguracje musimy standardowo zacząć od dodania zależności do naszego pliku pom.xml.

Gramatyka

Następnie musimy znaleźć interesującą nas gramatykę i wrzucić ja do folderu antlr4, który umieszczamy w katalogu serc/main. Dodatkowo, jeżeli chcemy, żeby kod wygenerowany na podstawie naszej gramatyki był w konkretnym pakiecie to musimy gramatykę wrzucić właśnie pod taką ścieżką. Czyli np. jeżeli chcę, żeby klasy związane z gramatyką były w pakiecie pl.lantkowiak.plagdetector.algorithm.grammar, to powinienem mieć taką strukturę katalogów jak przedstawiona poniżej.

Pluginy

Teraz potrzebujemy dodać do naszego poma kolejne dwa pluginy.

antlr4-maven-plugin

Plugin ten będzie odpowiedzialny za wygenerowanie klas związanych z naszą gramatyką.

build-helper-maven-plugin

Ten plugin sprawia, że nasze wygenerowane źródła będą widoczne w Eclipsie jako klasy, których możemy użyć.

Mały hack

Jeżeli będziemy wykorzystać wygenerowane klasy w naszym kodzie Kotlinowym to nasz projekt niestety się nie zbuduje. Maven nie będzie widział wygenerowanych źródeł. Aby to naprawić musimy w naszym pomie zamienić kolejnością pluginy odpowiedzialne za kompilacje Javy i Kotlina. W wpisie Hello Kotlin pisałem, że plugin do kompilacji kodu Kotlina powinien być przed pluginem Javovym, żeby kod kotlina mógł być użyty w Javie. Niestety póki co musiałem z tego zrezygnować, aby móc zautomatyzować proces generacji kodów źródłowych dla gramatyk ANTLRowych.

Użycie w kodzie

Dla np. gramatyki dla Java 8 ANTLR wygeneruje następujące pliki:

Klasa, która będzie nas interesowała do przeprowadzenia tokenizacji to Java8Lexer.

Ponieważ Plag-Detector będzie wspierał wiele języków programowania stworzyłem enuma, który będzie zawierał wszystkie wspierane języki.

Następnie stworzyłem prostą fabrykę, która na podstawie przekazanego enuma zwróci mi instancje oczekiwanego leexera.

Klasa Lexer jest klasą abstrakcyjną, po której dziedziczą wszystkie lexery wygenerowane przez ANTLRa.

Sama tokenizacja jest już bardzo prosta:

W pierwszej linii metody tworze instancje fabryki, a następnie pobieram lexer. Następnie wywołuję metodę getallTokens(), która zwraca mi listę wszystkich tokenów z przetworzonego kodu źródłowego. Ponieważ do dalszych potrzeb istotne są dla mnie tylko typy tokenów, a nie całe obiekty z nadmiarowymi danymi, mapuję tokeny na ich typ, czyli int. Taką listę intów jest zwracana przez metodę i będzie dalej użyta w procesie wykrywania plagiatów.

Podsumowanie

W tym wpisie przedstawiłem ANTLRa oraz pokazałem jak go skonfigurować. Dodatkowo pokazałem w jaki sposób można użyć ANTLRa, aby dokonać tokenizacji ciągu znaków na wejściu – w naszym przypadku kodu źródłowego.

 

Hello Kotlin!

W końcu pora na kodowanie!

Po kilku wpisach teoretycznych na temat mojej aplikacji przyszła pora, żeby napisać pierwsze linijki w Kotlinie! Postaram się od razu przygotować projekt tak, aby mógł być dalej rozwijany i ostatecznie stać się gotową aplikacją.

Struktura projektu

Aplikacja będzie się nazywać plag-detector. Będzie ona podzielona na kilka modułów. W tym wpisie zacznę od podstawowego modułu mojej aplikacji, czyli części programu, która będzie odpowiedzialna za wyliczanie prawdopodobieństwa plagiatu pomiędzy dwoma kodami źródłowymi.

Build tool

Przed napisaniem pierwszej linijki kodu warto wybrać narzędzie automatyzujące budowę aplikacji. Wybór padł na klasykę, czyli stary i lubiany Maven 😉

Konfiguracji parenta, czyli plag-detector, nie będę pokazywał. Nie ma tam nic odkrywczego 🙂

Poniżej przedstawię pom.xml modułu plag-algorithm.

W tej konfiguracje ważne są właściwie dwie rzeczy:

  1. Pluginy do kompilacji Kotlina i Javy. Wydaję mi się, że nie ma za bardzo co tutaj się rozpisywać 🙂
  2. Kolejność pluginów. Plugin Kotlina powinien być przed pluginem do kompilacji kodu Javy. Dzięki temu w kodzie Javowym będziemy mogli używać naszych klas Kotlinowych

Hello world!

I w końcu! Pierwszy kawałek kodu w Kotlinie!

Po uruchomieniu powyższego kodu, tak jak można się łatwo domyślić, otrzymujemy:

Kilka słów na koniec

Dzisiaj w wpisie pokazałem szkielet mojej aplikacji. Udało mi się skonfigurować mavena, tak aby kompilował kody napisane zarówno w języku Java, jak i w Kotlnie. Napisałem również pierwszy kod w Kotlinie, który się ładnie przywitał 😉

W następnych wpisach będę pokazywał swoje kolejne zmagania z Kotlinem, przy rozwijaniu plag-detectora 🙂

Wykrywanie plagiatów – wybór algorytmu

4W poprzednich wpisach zrobiłem przegląd istniejących algorytmów/systemów służących do wykrywania plagiatów w kodach źródłowych. W tym wpisie przedstawię ogólny zarys algorytmu, który wybrałem.

PlagDetector – algorytm

Głównym podejściem, wokół którego będzie koncentrował się mój system został opisany przeze mnie w tym wpisie. Chodzi o wykrywanie plagiatów przy użyciu aproksymacji złożoności Kołmogorowa.

Aplikacja będzie składała się z trzech głównych etapów.

Tokenizacja

Pierwszym etapem algorytmu jest poddanie kodu źródłowego tokenizacji.

Bardzo ważną rzeczą, jest dobranie odpowiedniego zestawu tokenów. Ztokenizowany kod programu powinien dobrze oddawać strukturę i logikę programu. Zbyt dokładne tokenizowanie może doprowadzić do pominięcia wykrycia plagiatu z powodu sprawdzania i porównywania nieistotnych informacji. Z drugiej strony, niewystarczająco dokładna tokenizacja może doprowadzić to fałszywych wskazań. Zestaw tokenów oraz sama tokenizacja jest przeprowadzona pod kątem danego języka programowa. Dzięki temu uzyskany ciąg tokenów powinien dobrze oddać strukturę programu. W Listingu poniżej znajduje się fragment przykładowego kodu i odpowiadający mu przykładowy ciąg tokenów.

Kompresja tokenów

Główną rzeczą przy wyborze algorytmu kompresji była konieczność wyboru takiego algorytmu, który będzie bezstratny, lecz jego stopień kompresji będzie możliwie duży. Na podstawie testów i doświadczeń autorów systemu SID (opisanego w poprzednim wpisie) wybór padł na algorytm LZ77.

Najważniejszą modyfikacją, którą wprowadzę do implementowanego algorytmu kompresji w stosunku do oryginalnego algorytmu LZ77 jest nieograniczony bufor słownika oraz nieograniczony bufor wejściowy. Dzięki takiemu podejściu stopień kompresji danych będzie większy niż w przypadku, gdy bufory słownika i wejściowy są ograniczone. Podejście to w oczywisty sposób powoduje wydłużenie działania algorytmu, lecz taki zabieg jest konieczny, aby uzyskać jak najbardziej dokładnie wyniki. Poniżej przedstawiłem pseudokod zmodyfikowanego algorytmu kodowania LZ77.

 

Wielkością skompresowanego ciągu jest ilość wpisów w słowniku pomnożona przez (shift_size + length_size + token_size), gdzie:

  • shift_size – wielkość w bajtach potrzebna do zakodowania przesunięcia w lewo;
  • length_size – wielkość w bajtach potrzebna do zakodowania długości;
  • token_size – wielkość w bajtach potrzebna do zakodowania jednego tokena.

Aproksymacja złożoności Kołmogorowa

Wartość aproksymacji Kołmogorowa jest przybliżana przy pomocy wzoru:
{d(x,y) = 1 - \frac{K(x)-K(x|y)}{K(xy)}}.

Przez {\emph{K(x)}} w przypadku konstruowanego algorytmu będzie rozumiana wielkość (w bajtach) skompresowanego programu i będzie oznaczana jako {\emph{Comp(x)}}. W związku z tym wzór na przybliżenie aproksymacji Kołmogorowa przyjmie postać:

{d(x,y) = 1 - \frac{Comp(x)-Comp(x|y)}{Comp(xy)}}.

Wartość {\emph{Comp(x|y)}} zostanie przybliżona w następujący sposób:
{Comp(x|y) = Comp(xy) - Comp(y)}.

Zatem ostatecznie wartość aproksymacji Kołmogorowa zostanie obliczone ze wzoru:
{d(x,y) = 1 - \frac{Comp(x)+Comp(y)-Comp(x|y)}{Comp(xy)}}.

Tak obliczona wartość aproksymacji złożoności Kołmogorowa jest przeliczana na współczynnik R według wzoru:
{R = 1 - d(x,y)}.

Wskaźnik ten służy za wskaźnik prawdopodobieństwa zajścia plagiatu. Im wartość {\emph{R}} jest większa, tym prawdopodobieństwo plagiatu jest większe.

Dodatkowo dla każdej pary programów obliczane są wartości {\emph{px}} oraz {\emph{py}}. Wartości te przedstawiają procentową zawartość informacji z jednego ciągu zawartych w drugim. Wartości te obliczane są w sposób następujący:
{px=\frac{R(\alpha + 1)}{R+1}},
{py=\frac{R(\frac{1}{\alpha} + 1)}{R+1}}, gdzie:
{\alpha = \frac{Comp(y)}{Comp(x)}}.

Wskaźniki {\emph{px}} i {\emph{py}} służą jako dodatkowa informacja, wskazująca na zawartość jednego ciągu w drugim. Wartości te mogą wykazać zajście plagiatu, w przypadku gdy jeden z programów zawiera w sobie kod drugiego, lecz sam program jest o wiele bardziej rozbudowany i wartość współczynnika R może nie wskazać zajścia plagiatu.

Podsumowanie

W tym wpisie omówiłem algorytm, który planuję zaimplementować. Składa się  on z 3 głównych kroków – tokenizacji, kompresji i aproksymacji złożoności Kołmogorowa. W kolejnych wpisach postaram się bardziej przybliżyć każdy z tych etapów.

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 🙂

Jak wykrywać plagiaty? Część druga!

W jednej z poprzednich notek opisałem metody służące do wykrywania plagiatów, które bazują na zliczaniu atrybutów. Dzisiaj postaram się opisać i przedstawić systemy bazujące na metrykach strukturalnych.

Systemy bazujące na metrykach strukturalnych

Techniki wykrywania plagiatów opierające się na metrykach strukturalnych polegają na badaniu podobieństwa na podstawie podobnych lub identycznych fragmentów w badanych plikach. Poniżej opiszę kilka najpopularniejszych systemów służących do wykrywania plagiatów w kodach źródłowych programów, które bazują na metryce strukturalnej.

Dotplot

Metoda Dotplot jest wizualną metodą znajdującą pasujące do siebie fragmenty tekstu (w szczególnym przypadku kodu źródłowego). Decyzja o plagiacie jest podejmowana przez użytkownika analizującego otrzymane wizualne wyniki. Autor systemu uważa, że właśnie dzięki powierzeniu decyzji o plagiacie człowiekowi można zdecydowanie podwyższyć próg skuteczności znajdowania plagiatów. System działa w następujący sposób:

  • tokenizacja wejścia
  • konkatenacja tokenów z programu A i programu B
  • przedstawienie wyników w postaci graficznej

Aby lepiej pokazać działanie algorytmu, poniżej pokażę przykład działania algorytmu.

Ciągi wejściowe:

  • Ala ma kota
  • Kot ma na imie ala

Przebieg algorytmu:

  • tokenizacja: ala{\diamond}ma{\diamond}kota, kot{\diamond}ma{\diamond}na{\diamond}imie{\diamond}ala
  • konkatenacja: ala{\diamond}ma{\diamond}kota{\diamond}kot{\diamond}ma{\diamond}na{\diamond}imie{\diamond}ala
  • wyniki w graficznej formie:
    alamakotakotmanaimieala
    alaXXXXXX
    maXXXXXX
    kotaXXX
    kotXXX
    maXXXXXX
    naXXX
    imieXXX
    alaXXXXXX

Na podstawie tak przedstawionych wyników, osoba analizująca dane z pomocą wskazówek, stworzonych przez autora systemu, może stwierdzić zajście plagiatu.

JPlag

System JPlag jest darmowym systemem do wykrywania plagiatów dostępnym online. System analizując kody źródłowe programów działa w dwóch etapach:

  1. Parsowanie i tokenizacja kodu źródłowego.
    Przy pomocy parsera i tokenizera kod źródłowy programu jest zamieniany na ciąg tokenów.
  2. Porównanie par ciągów tokenów ze sobą.
    Każda para ciągu tokenów jest porównywana ze sobą przy użyciu algorytmu Greedy String Tiling
    Przy porównywaniu tokenów przestrzegane są następujące zasady:

    1. Każdy token z programu A może zostać dopasowany tylko do jednego tokena z programu B.
    2. Podciągi tokenów są znajdowane niezależnie od ich pozycji.
    3. Dłuższe podciągi są bardziej preferowane od krótszych

Uwzględniając powyższe zasady powstał algorytm, który przebiega w dwóch fazach:

  1. W pierwszej fazie algorytmu w dwóch ciągach tokenów znajdowany jest najdłuższy wspólny podciąg dla dwóch podanych ciągów wśród tokenów, które nie są oznaczone.
  2. W drugiej fazie wszystkie tokeny zawierające się w znalezionym w fazie pierwszej podciągu zostają oznaczone jako użyte i algorytm wraca do punktu pierwszego.

Algorytm jest wykonywany dopóki są znajdowane dopasowania tokenów o długości nie mniejszej niż ustalony próg.\par
W listingu poniżej przedstawiono pseudo-kod algorytmu Greedy String Tiling.

Na podstawie wyniku działania algorytmu jest wyliczane prawdopodobieństwo w następujący sposób:

{sim(A,B)=\frac{2\cdot coverage(tiles)}{|A|+|B|}}, gdzie:

{coverage(tiles) = \sum_{match(a,b,length)\in tiles}length}

Obliczone podobieństwo jest wyrażone w procentach, zatem im wyższa wartość tym większe prawdopodobieństwo na to, że mamy do czynienia z plagiatem.

MOSS

Ostatnim systemem opierającym się na metrykach strukturalnych, który opiszę jest MOSS. Głównym algorytmem systemu jest algorytm Winnowing. Jego zasada działania opiera się na k-gramach, czyli podciągach tokenów długości k. Algorytm przebiega następująco:

  1. podanie na wejście ciągu znaków
  2. usunięcie zbędnych znaków
  3. podzielenie ciągu wejściowego na k-gramy
  4. zamiana k-gramów na hashe
  5. wybranie części hashów, według odpowiedniego algorytmu – wybrane hashe tworzą tzw. odcisk palca programu.

Tak przygotowane zestawy odcisków palca są ze sobą porównywane w celu znalezienia jak największych wspólnych części odcisków palców.

Krótkie podsumowanie

Dzisiaj pokazałem bardziej zaawansowane systemy wykrywania plagiatów. według mnie na szczególną uwagę zasługuje system JPlag, który ma całkiem niezłą skuteczność.

W jednym z kolejnych wpisów opiszę jeszcze 2-3 podejścia do tego  problemu. Po tej dawce teorii będziemy mogli z czystym sumieniem przejść do praktyki i implementacji naszego algorytmu 🙂

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ą.