Bachelor's Thesis

Incremental Parsing for YARA Language

Final Thesis 2.46 MB Appendix 17.55 MB

Author of thesis: Bc. Vojtěch Dvořák

Acad. year: 2022/2023

Supervisor: Ing. Dominika Regéciová

Reviewer: doc. Dr. Ing. Dušan Kolář

Abstract:

The main goal of this bachelor thesis is to design and implement a program library that enables incremental static analysis of the YARA language. One of the main purposes of this new library is to integrate with the open-source Yara Language Server project developed by Avast. Compared to the existing solution, which uses a non-incremental approach to analysis, the machine time requirements should be reduced. In addition to information
about the software solution, this thesis also includes a summary of the theory focusing on static analysis and its incremental variant, essential information about the YARA tool, and an introduction to the existing solution, the Yaramod-v3 library. The thesis also contains a comparison of the new library with the current solution, in which the achieved results
are presented. The experiments performed showed that the new library is able to perform incremental analysis of a modified rule set approximately 20× – 2000× faster depending on the particular set.

Keywords:

incremental static analysis, YARA, integrated development environment, IDE, YLS, LSP, Yaramod, LR parsing, semantic analysis, lexical analysis, text editor, tree-sitter, visitor, linting, Avast

Date of defence

16.06.2023

Result of the defence

Defended (thesis was successfully defended)

znamkaAznamka

Grading

A

Process of defence

Student nejprve prezentoval výsledky, kterých dosáhl v rámci své práce. Komise se poté seznámila s hodnocením vedoucího a posudkem oponenta práce. Student následně odpověděl na otázky oponenta a na další otázky přítomných. Komise se na základě posudku oponenta, hodnocení vedoucího, přednesené prezentace a odpovědí studenta na položené otázky rozhodla práci hodnotit stupněm A.

Topics for thesis defence

  1. Proč jste použil GLR?

Language of thesis

Czech

Faculty

Department

Study programme

Information Technology (BIT)

Composition of Committee

doc. Dr. Ing. Dušan Kolář (předseda)
doc. Dr. Ing. Otto Fučík (člen)
Ing. František Grézl, Ph.D. (člen)
Ing. Ivana Burgetová, Ph.D. (člen)
Ing. Martin Hrubý, Ph.D. (člen)

Supervisor’s report
Ing. Dominika Regéciová

Student se seznámil s problematikou inkrementálních parserů a jejich použití pro analýzu zdrojových kódů v textových editorech a integrovaných vývojových prostředích.


Navrhl a implementoval knihovnu, která umožnuje statickou analýzu jazyka YARA za využití algoritmu pro inkrementální parsování, a která je již nyní aktivně používaná ve společnosti Gen.


Výsledek student otestoval a porovnal s předchozí verzí řešení, u čehož bylo zjištěno výrazné zrychlení analýzy. Řešení bude rovněž zveřejněno jako open-source projekt.


K práci přistupoval aktivně a samostatně. Z těchto důvodů navrhuji hodnocení za A.

Evaluation criteria Verbal classification
Informace k zadání

Zadání považuji za náročnější. Student si musel nastudovat teorii inkrementálních parserů a jejich použití pro analýzu zdrojových kódů v textových editorech a integrovaných vývojových prostředích (IDE).

Student se rovněž musel seznámit s již existujícími systémy společnosti a stejně tak open-source nástroji, aby mohl navrhnout a implementovat řešení pro knihovnu za použití inkrementálního parsování.

Zadání pak bylo splněno ve všech bodech.

Práce s literaturou

Student si hledal zdroje informací aktivně sám. Čerpal především z technických dokumentací, ale i odborných publikací. Řádně citoval a odkazoval se na použité zdroje.

Aktivita během řešení, konzultace, komunikace

Student pracoval na zadání hned od začátku, dodržoval dohodnuté termíny. Práci pravidelně konzultoval, jak se mnou, tak odborným konzultantem. K práci přistupoval aktivně a přecházel s originálními řešeními problémů.

Aktivita při dokončování

Práce, především realizační část, byla dokončena v předstihu. Finální podoba byla dostatečně konzultována.

Publikační činnost, ocenění

Výsledky práce studenta budou zveřejněny jako součást open-source projektu Yaramod.

Points proposed by supervisor: 96
Display more

Grade proposed by supervisor: A

Reviewer’s report
doc. Dr. Ing. Dušan Kolář

Práce měla jistě velký potenciál, ale dle mého chyběly síly na posledních pár metrech před cílem. Například by mě zajímalo, proč je použita GLR, když gramatika určitě může být jednoznačná? Taky
to, proč je iniciační analýza tak pomalá? Kde je nějaké zdůvodnění kroků při řešení, experimenty, apod. Dojem hodně kazí, že kód odevzdaný v IS nelze podle návodu sestavit. Náročnější práci, pěkně zpracovanou tak nelze hodnotit jako vynikající.

Evaluation criteria Verbal classification Points
Náročnost zadání

Evaluation level: obtížnější zadání

Zadání hodnotím jako obtížnější, neboť bylo třeba nastudovat techniky částečného rozkladu programovacího jazyka a techniky a nástroje spojené s touto tehcnologií, což je nad rámec bakalářského studia.

Rozsah splnění požadavků zadání

Evaluation level: zadání splněno

Rozsah technické zprávy

Evaluation level: je v obvyklém rozmezí

Text je sice v obvyklém rozmezí, ale někde působí rozvláčně (úvodní partie), jinde zase informačně chudě (konec práce).

Prezentační úroveň technické zprávy

Kapitoly na sebe sice navazují, ale někde je text až populárně-naučný, jinde zase něco chybí, nebo jsme odkazováni na soubory v příloze (např. testování).

85
Formální úprava technické zprávy

Po formální stránce je práce úpravná, jen s drobnými překlepy a 2 systematickými chybami (např.  "ladící" místo "ladicí", nebo "řídící" místo "řídicí").

90
Práce s literaturou

Volba pramenů je vhodná pro daný typ práce.

90
Realizační výstup

Ač jsem postupoval podle návodu, v čerstvé instalaci aktuálního Kubuntu, tak tree-sitter se sice podařilo sestavit, základní testy proběhly, ale náročné testy dept_test.py selhaly. Hlavní program se nepodařilo sestavit vůbec (cmake v pohodě, make spadl na chybu). Komentované jsou jen halvičkové soubory, ostatní mají jen hlavičku s autorem.

50
Využitelnost výsledků

Dle vyjádření výsledků je programová sestava funkční, takže je na pracovišti běžně využívána.

Points proposed by reviewer: 80
Display more

Grade proposed by reviewer: B