Přístupnostní navigace
E-application
Search Search Close
Bachelor's Thesis
Author of thesis: Ing. Lucie Svobodová
Acad. year: 2022/2023
Supervisor: prof. Ing. Tomáš Vojnar, Ph.D.
Reviewer: Ing. Jan Fiedor, Ph.D.
Modern software systems often use concurrent programs to improve performance and increase efficiency. However, ensuring the reliability and safety of such systems can be challenging due to the increased potential for bugs, including data races, to arise. In this thesis, we introduce a new static data race detector, DarC, designed for programs written in C using the Pthreads library. The proposed detector is implemented as an analyser plugin in Meta Infer, a static analysis framework with an emphasis on compositional, incremental, and consequently highly-scalable analysis. Our approach involves recording a set of accesses that occur in the analysed program along with information about the set of locks held during these accesses. The tool then identifies pairs of accesses that may lead to data races and reports them to the user. Our tool was successfully evaluated on a set of benchmarking programs as well as on real-life projects, showing its potential for effectively detecting data races in C programs.
static analysis, data race, Infer, program analysis, abstract interpretation, scalability, multi-threaded programs, concurrent programs, program verification, incremental analysis
Date of defence
15.06.2023
Result of the defence
Defended (thesis was successfully defended)
Grading
A
Process of defence
Studentka nejprve prezentovala výsledky, kterých dosáhla v rámci své práce. Komise se poté seznámila s hodnocením vedoucího a posudkem oponenta práce. Studentka následně odpověděla na otázky přítomných. Komise se na základě posudku oponenta, hodnocení vedoucího, přednesené prezentace a odpovědí studentky na položené otázky rozhodla práci hodnotit stupněm A.
Topics for thesis defence
Language of thesis
English
Faculty
Fakulta informačních technologií
Department
Department of Intelligent Systems
Study programme
Information Technology (BIT)
Composition of Committee
prof. Ing. Tomáš Vojnar, Ph.D. (předseda) doc. Ing. Petr Matoušek, Ph.D., M.A. (člen) Ing. František Grézl, Ph.D. (člen) doc. Ing. Tomáš Martínek, Ph.D. (člen) Ing. Matěj Grégr, Ph.D. (člen)
Supervisor’s reportprof. Ing. Tomáš Vojnar, Ph.D.
Studentka řešila nadprůměrně náročné zadání velmi zodpovědným a kreativním způsobem. Vytvořený nástroj byl úspěšně prezentován na studentské konferenci Excel@FIT a má po dopracování potenciál být publikován i na klasické vědecké konferenci. Práci bych rád doporučil i na některé z ocenění za bakalářské práce.
Práce je nadprůměrně náročná mj. s ohledem na to, že staví na metodách statické analýzy, které nejsou předmětem bakalářského studia na FIT VUT. Práce také vyžadovala pokročilé funkcionální programování v jazyce Ocaml, v němž je napsáno prostředí Meta Infer. Bylo rovněž zapotřebí seznámení se s prostředím Infer, které není příliš detailně zdokumentováno. Práce vyžadovala návrh originálního přístupu k analýze zaměřené na souběhy nad daty („data race“) způsobem kompatibilním s tím, že prostředí Meta Infer analyzuje programy zdola nahoru dle stromu volání, což vede na analýzu každé jednotlivé funkce bez znalosti kontextu jejího volání. Známé analýzy daného typu dostupné v literatuře přitom pracují dle stromu volání shora dolů.
Studentka začala v dané oblasti pracovat v rámci projektové praxe a její práce je významná pro několik výzkumných projektů řešených ve skupině VeriFIT (mj. GAČR AIDE či HE Chess). S dosaženými výsledky jsem velmi spokojen. Vytvořený nástroj poskytuje slibné výsledky a po dalším dopracování, o které studentka již projevila zájem, je zde potenciál k publikaci na kvalitní mezinárodní konferenci minimálně formou článku o nástroji.
Práce s literaturou byla zcela bezproblémová. Studentka byla schopna nastudovat i články výzkumného charakteru a aplikovat poznatky v nich obsažené.
Jak již bylo řečeno, studentka začala na tématu pracovat již v rámci projektové praxe. Po celou dobu řešení byla velmi aktivní, účastnila se pravidelných schůzek skupiny, prezentovala dosažené pokroky i možnosti dalšího pokračování práce a řešení různých problémů, které se při práci objevily.
Práce byla dokončována v přiměřeném předstihu. Text práce jsem byl schopen v rámci svých časových možností projít, komentovat a studentka reflektovala mé návrhy. Omezení v tomto směru byly vždy na mé straně a studentka byla schopna se s mými časovými omezeními vyrovnat, což rovněž hodnotím pozitivně.
Práce byla úspěšně prezentována na studentské konferenci Excel@FIT, kde získala Cenu firmy Honeywell, Cenu firmy NXP a ocenění odbornou veřejností – Cenu Jiřího Kunovského. Předpokládáme, že po dalším dopracování by měl být vytvořený nástroj publikován formou článku o nástroji na některé z uznávaných mezinárodních konferencí v dané oblasti. Vytvořený nástroj DARC je k dispozici jako open source.
Za zmínku stojí také to, že studentka v rámci studijní části své práce pomohla s přípravou publikace o dříve vytvořeném statickém analyzátoru L2D2, zaměřeném na vyhledávání uváznutí, na mezinárodní konferenci EUROCAST 2022 se sborníkem vydaným v edici LNCS nakladatelství Springer a je spoluautorkou této publikace.
Grade proposed by supervisor: A
Reviewer’s reportIng. Jan Fiedor, Ph.D.
Práce by svou obtížností a výborným vypracováním bez problémů obstála i jako práce diplomová. Je velmi kvalitní jak po jazykové, tak i typografické stránce. Navíc je psaná v anglickém jazyce a pro čtenáře dobře pochopitelná.
Navržená analýza je plně funkční, může konkurovat existujícím řešením, a na rozdíl od existujících řešení je navíc rychle a snadno nasaditelná.
Výsledky práce byly publikovány na studentské konferenci Excel@FIT, kde získala práce hned několik ocenění.
Celkově jde o vynikající práci a navrhuji hodnocení A. Navrhuji také zvážit možnost udělení některého z ocenění.
Evaluation level: značně obtížné zadání
Navržená analýza je založena na abstraktní interpretaci, jenž vyžaduje od studenta znalosti z oblastí matematiky, teoretické informatiky, a formální analýzy a verifikace. S předměty pokrývajícími tyto oblasti se studenti setkávají až v rámci magisterského studia, pro studenta bakalářského studia je tedy výrazně obtížnější tuto problematiku pochopit. Implementace analýzy ve formě zásuvného modulu pro nástroj Meta Infer navíc vyžaduje použití funkcionálního jazyka OCaml, se kterým se student během bakalářského studia také nesetká a klade to na něj další nároky.
Pro studenta bakalářského studia pokládám tedy toto téma za velmi náročné.
Evaluation level: zadání splněno
Všechny body zadání byly splněny.
Evaluation level: přesahuje obvyklé rozmezí
Práce mírně přesahuje obvyklé rozmezí. Důvodem je obtížnost tématu, jenž vyžaduje podrobné uvedení do problematiky a detailní popis návrhu řešení i implementace. Práce navíc vhodně doplňuje popis návrhu a implementace konkrétními ukázkami na příkladech, což velmi usnadňuje čtenáři pochopení dané problematiky i navrženého řešení.
Práce má výbornou prezentační úroveň a je dobře pochopitelná i pro čtenáře s minimem znalostí v oblasti abstraktní interpretace. Jednotlivé kapitoly obsahují všechny potřebné informace pro pochopení principů fungování navržené analýzy i její implementace.
Jednotlivé části navržené analýzy jsou navíc vhodně ilustrovány na řadě konkrétních příkladů umožňující čtenáři pochopit principy fungování celé analýzy bez nutnosti mít hluboké znalosti abstraktní intepretace.
Práce je psána v anglickém jazyce s minimem překlepů nebo chyb. Typograficky je práce na úrovni vědeckých článků a jiných odborných publikací.
Práce se odkazuje na velké množství věděckých článků, knih, a jiných odborných publikací a hlavně v teoretické části se na ně bohatě odkazuje, což svědčí o dobré teoretické přípravě. Všechny zdroje jsou řádně odcitovány.
Navržená analýza je implementována ve formě zásuvného modulu pro nástroj Meta Infer, je plně funkční, a výkonnostně srovnatelná s existujícími řešeními.
Funkčnost navržené analýzy byla otestována na třech testovacích sadách (vlastní vytvořené sadě ConcurrencyBenchmark, veřejné testovací sadě DataRacebenchmark a testovací sadě z mezinárodní soutěže analýzy software SV-COMP) a srovnána s několika existujícími nástroji pro odhalování chyb v souběžnosti (data race). Pro ověření škálovatelnosti byla následně analýza otestována na několika reálných aplikacích včetně eProsima/Fast-DDS čítající přes 100 000 řádků kódu.
Výsledná analýza má vysoký potenciál využití v praxi, hlavně díky jednoduchosti jejího nasazení i dobré škálovatelnosti. Tento závěr podporuje i zisk ceny partnera od firmy Honeywell na studenské konferenci Excel@FIT.
Grade proposed by reviewer: A
Responsibility: Mgr. et Mgr. Hana Odstrčilová