Bachelor's Thesis

Statická analýza v nástroji Meta Infer zaměřená na detekci souběhu nad daty

Final Thesis 1.76 MB

Author of thesis: Ing. Lucie Svobodová

Acad. year: 2022/2023

Supervisor: prof. Ing. Tomáš Vojnar, Ph.D.

Reviewer: Ing. Jan Fiedor, Ph.D.

Abstract:

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.

Keywords:

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)

znamkaAznamka

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

  1. V sekci 4.2.8 popisujete implementaci operátorů join a widen nutných pro abstraktní interpretaci. Po popisu implementace operátoru join konstatujete, že operátor widen je implementován stejně jako operátor join. Proč jsou v případě vaší implementace dva rozdílené operátory implementovány identicky? Může tento fakt ovlivnit výsledky analýzy?
  2. Na konci sekce 5.1.2 diskutujete falešné poplachy způsobené tím, že analýza předpokládá nejhorší možnou situaci v případě, že zámek může, ale nemusí, být uzamčen nebo odemčen. Bylo by možné zakomponovat tyto informace do navržené analýzy, tedy rozlišovat mezi zámky, kde jsme si jistí, že byly zamknuty nebo odemknuty, a zámky, kde si tím jistí nejsme? Při filtrování nalezených chyb na konci analýzy bychom pak mohli zobrazit uživateli prioritně ty chyby, u kterých nemáme pochybnosti, že přístupy nejsou dostatečně chráněny.

Language of thesis

English

Faculty

Department

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 report
prof. 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.

Evaluation criteria Verbal classification
Informace k zadání

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

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

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

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.

Aktivita při dokončování

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

Publikační činnost, ocenění

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.

Points proposed by supervisor: 97

Grade proposed by supervisor: A

Reviewer’s report
Ing. 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 criteria Verbal classification Points
Náročnost zadá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é.

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

Evaluation level: zadání splněno

Všechny body zadání byly splněny.

Rozsah technické zprávy

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

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

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.

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

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

95
Práce s literaturou

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.

95
Realizační výstup

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.

95
Využitelnost výsledků

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.

Topics for thesis defence:
  1. V sekci 4.2.8 popisujete implementaci operátorů join a widen nutných pro abstraktní interpretaci. Po popisu implementace operátoru join konstatujete, že operátor widen je implementován stejně jako operátor join. Proč jsou v případě vaší implementace dva rozdílené operátory implementovány identicky? Může tento fakt ovlivnit výsledky analýzy?
  2. Na konci sekce 5.1.2 diskutujete falešné poplachy způsobené tím, že analýza předpokládá nejhorší možnou situaci v případě, že zámek může, ale nemusí, být uzamčen nebo odemčen. Bylo by možné zakomponovat tyto informace do navržené analýzy, tedy rozlišovat mezi zámky, kde jsme si jistí, že byly zamknuty nebo odemknuty, a zámky, kde si tím jistí nejsme? Při filtrování nalezených chyb na konci analýzy bychom pak mohli zobrazit uživateli prioritně ty chyby, u kterých nemáme pochybnosti, že přístupy nejsou dostatečně chráněny.
Points proposed by reviewer: 95

Grade proposed by reviewer: A

Responsibility: Mgr. et Mgr. Hana Odstrčilová