Backend

Tokenizacja kodu źródłowego. Jak wykrywać plagiaty w Plag-Detectorze?

10 czerwca 2018 Łukasz Antkowiak

Tokenizacja jest terminem występującym często w tematyce związanej z bezpieczeństwem, czy też szyfrowaniem. Jej ideą jest zmiana kodu źródłowego na ciąg tokenów. W tym artykule opiszę pierwszy etap tokenizacji kodu źródłowego, czyli wykrywania plagiatów w Plag-Detectorze.

Łukasz Antkowiak. Java Senior Developer w Sii Poland. Od 2011 roku Java Developer w Volvo IT, później pracował jako Software engineer w Nokii. Przez lata był Consultantem w firmie Infusion. Od 2017 roku Java Software Developer w Siili Solutions Poland, od kwietnia 2018 roku Java Senior Developer w Sii Poland. Łukasz od ponad dwóch lat prowadzi bloga blog.lantkowiak.pl.

Pierwszym etapem algorytmu jest poddanie kodu źródłowego tokenizacji. Bardzo ważną rzeczą, jest dobranie odpowiedniego zestawu tokenów. Ztokenizowany kod powinien dobrze oddawać strukturę i logikę programu, ale 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ć do fałszywych wskazań. Zestaw tokenów oraz sama tokenizacja jest przeprowadzona pod kątem danego języka programowania. 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.

String var;                             VARIABLE_DECLARATION
int i;                                  VARIABLE_DECLARATION
i = 3;                                  IDENTIFIER
                                        ASSIGN
                                        IDENTIFIER
if (i > 2) {                            IF_SWITCH_STATEMENT_BEGIN
                                        OPEN_PARENTHESIS
                                        IDENTIFIER
                                        CONDITION
                                        IDENTIFIER
                                        CLOSE_PARENTHESIS
var = "more than 2";                    IDENTIFIER
                                        ASSIGN
                                        STRING
}                                       IF_SWITCH_STATEMENT_END
else {                                  IF_SWITCH_STATEMENT_BEGIN
var = "less than 2";                    IDENTIFIER
                                        ASSIGN
                                        STRING
}                                       IF_SWITCH_STATEMENT_END

Spis treści

Jak to zrobić w praktyce?

Można by samemu napisać tokenizer, ale byłaby to dość skomplikowana i długa robota — 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ęzyka 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.

Zobacz też

Backend EF Plus – aktualizacja wielu obiektów jednym zapytaniem

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.

<dependency>
    <groupId>org.antlr</groupId>
    <artifactId>antlr4</artifactId>
    <version>4.7</version>
</dependency>

Gramatyka

Następnie musimy znaleźć interesującą nas gramatykę i wrzucić ją 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.

src 
|- main 
 |- antlr4 
  |- pl 
   |- lantkowiak 
    |- algorithm 
     |- grammar

Pluginy

Teraz potrzebujemy dodania do naszego poma kolejnych dwóch pluginów.

1. antlr4-maven-plugin

<plugin>
    <groupId>org.antlr</groupId>
    <artifactId>antlr4-maven-plugin</artifactId>
    <version>4.7</version>
    <executions>
        <execution>
            <id>antlr-generate</id>
            <phase>generate-sources</phase>
            <goals>
                <goal>antlr4</goal>
            </goals>
        </execution>
     </executions>
</plugin>

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

2. build-helper-maven-plugin

<plugin>
    <groupId>org.codehaus.mojo</groupId>
    <artifactId>build-helper-maven-plugin</artifactId>
    <version>3.0.0</version>
    <executions>
        <execution>
            <id>add-source</id>
            <phase>generate-sources</phase>
            <goals>
                <goal>add-source</goal>
            </goals>
            <configuration>
                <sources>
                    <source>${project.build.directory}/generated-sources/antlr/</source>
                </sources>
            </configuration>
        </execution>
     </executions>
</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 wykorzystywać 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. We 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:

Java8.tokens
Java8Lexer.tokens
Java8BaseListener.java
Java8Lexer.java
Java8Listener.java
Java8Parser.java

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.

enum class LexerType(val title: String) {
    JAVA_8("Java 8")
}

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

class LexerFactory {
    fun getLexer(type: LexerType, cs: CharStream): Lexer {
        when (type) {
            LexerType.JAVA_8 -> return Java8Lexer(cs)
        }
    }
}

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

Sama tokenizacja jest już bardzo prosta:

class TokenizerImpl : Tokenizer {
    override fun tokenize(lexerType: LexerType, input: String): List<Int> {
        val lexer = LexerFactory().getLexer(lexerType, CharStreams.fromString(input))

        return lexer.allTokens.map { t -> t.type }
    }
}

W pierwszej linii metody, tworzę instancję fabryki, a następnie pobieram lexer. Później 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. Taka lista 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.