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.

 

Kilka słów o ciągłej integracji…

Dzisiaj będzie raczej krótki wpis, w którym postaram się napisać kilka słów na temat Continous Integration.

Continous Integration == Jenkins ?

W swojej pracy mam przyjemność brać udział w rozmowach rekrutacyjnych. Czasami rozmowa schodzi na temat ciągłej integracji. Zauważyłem, że część osób utożsamia Continous Integration (CI) z Jenkinsem (lub czasem z innym toolem, którego akurat używają), ale czy to faktycznie to samo?

Ciągła integracja jest procesem…

Czym jest zatem ta ciągła integracja? W moim rozumieniu jest to proces jak najczęstszej integracji naszych zmian w kodzie z kodem, który znajduję się w repozytorium. Integracja obejmuje również kompilacje kodu, zbudowanie projektu oraz uruchomienie testów.

I w tym całym procesie z pomocą przychodzą nam narzędzia takie jak Jenkins czy TeamCity. Narzędzia te możemy skonfigurować, żeby przeprowadzały powyższe operacje automatycznie. Jenkins, czy inny tool, sprawdza regularnie repozytorium, a gdy wykryje zmiany buduje projekt, a następni uruchamia testy naszej aplikacji.

A może coś więcej?

CI jest według mnie podstawą, o którą powinno się zadbać w każdym projekcie. A co jeżeli chcemy pójść dalej z automatyzacją? Wtedy powinniśmy rozważyć Continous Delivery oraz Continous Deployment.

Czym się różnią te dwa podejścia? Wydaje mi się, że najprościej będzie to przedstawić za pomocą grafiki.

Jak widać oba podejścia są do siebie bardzo podobne. Różnią się właściwie ostatnim krokiem w dostarczaniu aplikacji. W Continous Delivery cały proces jest przeprowadzany automatycznie do momentu wybudowania wersji aplikacji, która będzie gotowa do deploya na serwer produkcyjny.

W Continous Deployment ostatni krok również jest zautomatyzowany i wybudowana wersja trafia automatycznie na produkcje.

Darmowe narzędzie

W ramach tego wpisu pozwolę sobie wpleść kilka słów na temat narzędzia do CI, którego użyłem w swojej aplikacji Plag-Detector. Część narzędzi do CI, tak jak np. Jenkins, jest darmowych, ale wymagają one serwera, na którym będą mogły być uruchomione. Jeżeli nie chcemy/nie możemy posiadać swojego serwera do CI to polecam użyć np. serwisu https://travis-ci.org, który jest darmowym narzędziem do CI. Ma on pewne ograniczenie, a mianowicie możemy go użyć tylko i wyłącznie do projektów, które mamy na naszym koncie GitHub (co w przypadku wymogów konkursów nie jest specjalnie problematyczne ;)).

Moje CI znajduje się tutaj: https://travis-ci.org/lukaszantkowiak/plag-detector.

Konfiguracja Travisa.

Aby Travis działał poprawnie musimy go skonfigurować. Robimy to za pomocą pliku .travis.yml, który wrzucamy do głównego katalogu naszego projektu. Poniżej przedstawię listing swojej konfiguracji dla projektu napisanego w Javie 8.

Jak widać najprostsza konfiguracja jest banalna i przyjemna 🙂

Kilka słów na koniec

W tym wpisie omówiliśmy pokrótce czym są Continous Integration, Continous Delivery i Continous Deployment oraz jakie są różnice między nimi.

Dodatkowo wspomniałem o Travis-CI, który jest darmowym toolem, i z którego zachęcam skorzystać jeżeli nie mamy możliwości postawienia toola do CI na swoim serwerze.

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.

Niezmienne obiekty – po co nam one?

O ile pojęcie niezmiennych obiektów nie brzmi zbyt znajomo, to o tyle na pewno słyszałeś o Immutable Object. I o tym właśnie będzie ten wpis.

Czym jest Immutable Object?

Tutaj nie ma żadnego haczyka i nazwa dokładnie wskazuje o czym mówimy. Immutable object jest to niezmienny obiekt, czyli taki, którego stan nie może zostać zmieniony cały okres życia obiektu. Czyli po prostu tworzymy nasz obiekt wraz ze wszystkimi wymaganymi atrybutami i żadnego z nich nie możemy zmienić. Przynajmniej w teorii :)… ale zmiany poprzez refleksje się nie liczą, więc uznajemy, że nie mamy możliwości zmiany wartości tych atrybutów 😉

Jakie są zalety i wady tego podejścia?

Niezmienne obiekty, jak wszystko ;), mają zalety i wady. Do najważniejszych zalet według mnie należą:

  • Są łatwiejsze w użyciu i testowaniu
  • Można je bezpiecznie używać w Setach lub jako klucz w Mapach
  • Mogą być łatwo cachowane
  • Immutable object mogą być bezpiecznie używane w programowaniu wielowątkowym. Stan tych obiektów nie może ulec zmianie, więc mamy pewność, że każdy wątek widzi aktualny stan obiektu 😉

Wady Immutable Object:

  • Nadmiarowy kod – musimy dopisać kilka finali, ale za to pozbywamy się setterów 😉
  • Inicjalizacja wszystkich pól przez konstruktory. Ponieważ wszystkie nasze pola są oznaczone jako final, muszą więc zostać zainicjalizowane w konstruktorze. A co jak nie chcemy zawsze podawać wartości wszystkich parametrów, tylko użyć domyślnych wartości dla niektórych pól? Wtedy musimy stworzyć osobny konstruktor dla każdej kombinacji pól, którą chcemy użyć.
  • Problem z wydajnością – za każdym razem, gdy chcemy wprowadzić zmianę w naszym obiekcie to sprowadza się to do utworzenia nowego obiektu. Może to być odczuwalne zarówno w czasie działania aplikacji, jak i zużyciu pamięci.

Kiedy ich używać?

Jest na pewno kilka podstawowych use-caseów, kiedy powinniśmy rozważyć użycie niezmiennych obiektów:

  • programowanie wielowątkowe – jeżeli mamy obiekt, który ma być współdzielony pomiędzy wątkami to zdecydowanie warto rozważyć użycie immutable object
  • obiekt używany jako klucz (np. w mapach) – mamy wtedy pewność, że klucz nie zostanie zmieniony kiedy jest już w użyciu i nie będzie kolizji
  • obiekt ma być typowym ‚value object’ – wydaje się oczywiste 😉

Z drugiej strony powinniśmy skłaniać się ku ‚standardowym obiektom’, kiedy mamy do czynienia:

  • z dużymi obiektami, których tworzenie zajmie dużo czasu i/lub pamięci
  • obiektami, które posiadają ‚tożsaność’, tzn. reprezentują osoby/rzeczy, dla których zmiana pewnych parametrów jest naturalna np. samochód, dla którego naturalnymi jest zmiana takich parametrów jak prędkość czy poziom paliwa.

Implementacja Immutable Object w Javie

Stworzenie Immutable Object w Javie jest dosyć proste. Wystarczy przestrzegać kilku wskazówek 🙂

  1. Wszystkie pola powinny posiadać modyfikatory private i final.
  2. Nie tworzymy setterów (wynika to zresztą z użycia modyfikatora final przy polach).
  3. Musimy zabezpieczyć naszą klasę, żeby nie można było po niej dziedziczyć.
  4. Jeżeli pola naszej klasy zawierają mutable object, wtedy musimy zabezpieczyć te obiekty przed zmianą.

Pora na przykład, który zobrazuje nam powyższe zasady.

Trochę optymalizacji

Jeżeli nasz niezmienny object będzie na prawdę często używany w naszej aplikacji możemy rozważyć pewne optymalizacje.

Jedną z technik, którą możemy użyć jest Pooling. Jest on np. użyty w JVM w przypadku Stringów. Poniżej przedstawię bardzo prymitywną implementacje tego podejścia.

Na początku stwórzmy jeszcze nasz immutable object, którego użycie będizemy chcieli zoptymalizować.

I teraz prosty mechanizm poolingu:

Ogólnie mówiąc ideą jest powtórne użycie wcześniej utworzonego obiektu, jeżeli jest taki sam jak byśmy chcieli stworzyć.

Przy używaniu poolingu powinniśmy mieć na uwadze, że o ile w środowisku jednowątkowym powinien sprawdzić się całkiem nieźle, o tyle przy wielu wątkach narzut na synchronizacje może być znaczący.

Podsumowanie

We wpisie postarałem przedstawić się ideę niezmiennych obiektów, ich wady oraz zalety. Pokazałem również jak zaimplementować taki obiekt w Javie oraz zaproponowałem pewną optymalizacje, którą możemy użyć, aby zwiększyć wydajność naszej aplikacji w przypadku częstego korzystania z naszego immutable object.

UPDATE 14.05.2017

Kolega zwrócił mi uwagę na błąd, który był w listingu z implementacją niezmiennej klasy w Javie – teraz wszystko powinno być ok 🙂

Zwrócił również uwagę, że warto dodać wzmiankę o poolingu w środowisku wielowątkowym – dodane 🙂

Dzięki 🙂