bakalářská práce

Static Analysis Using the Meta Infer Framework to Detect Data Races

Text práce 1.76 MB

Autor práce: Ing. Lucie Svobodová

Ak. rok: 2022/2023

Vedoucí: prof. Ing. Tomáš Vojnar, Ph.D.

Oponent: Ing. Jan Fiedor, Ph.D.

Abstrakt:

Vícevláknové programy jsou v moderních softwarových systémech využívány ke zlepšení výkonu a zvýšení efektivity. Zajištění spolehlivosti a bezpečnosti takových programů však může být náročné kvůli zvýšenému množství chyb, které se v nich vyskytují, včetně souběhu nad daty. V této práci představujeme nový statický detektor souběhu nad daty, DarC, navržený k analýze programů napsaných v jazyce C využívajících knihovnu Pthreads. Navrhovaný nástroj byl implementován jako zásuvný modul prostředí Meta Infer, což je nástroj pro statickou analýzu programů, který klade důraz na kompoziční, inkrementální a díky tomu i vysoce škálující analýzu programů. Nový analyzátor zaznamenává množinu přístupů ke sdíleným proměnným, ke kterým v analyzovaném programu došlo, spolu s informací o množině zámků uzamknutých při jednotlivých přístupech. Množina přístupů je dále použita k identifikaci dvojic přístupů, mezi nimiž by k souběhu nad daty mohlo dojít. Nástroj byl úspěšně ověřen na sadě testovacích vícevláknových programů, stejně tak jako na několika programech běžně využívaných v praxi, čímž byl ukázán jeho potenciál pro efektivní detekci souběhu nad daty v programech napsaných v programovacím jazyce C.

Klíčová slova:

statická analýza, souběh nad daty, Infer, analýza programů, abstraktní interpretace, škálovatelnost, vícevláknové programy, paralelní programy, verifikace programů, inkrementální analýza

Termín obhajoby

15.06.2023

Výsledek obhajoby

obhájeno (práce byla úspěšně obhájena)

znamkaAznamka

Klasifikace

A

Průběh obhajoby

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.

Otázky k obhajobě

  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.

Jazyk práce

angličtina

Fakulta

Ústav

Studijní program

Informační technologie (BIT)

Složení komise

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)

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.

Kritérium hodnocení Slovní hodnocení
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.

Výsledný počet bodů navržený vedoucím: 97

Známka navržená vedoucím: A

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

Kritérium hodnocení Slovní hodnocení Body
Náročnost zadání

Stupeň hodnocení: 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í

Stupeň hodnocení: zadání splněno

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

Rozsah technické zprávy

Stupeň hodnocení: 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.

Otázky k obhajobě:
  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.
Výsledný počet bodů navržený oponentem: 95

Známka navržená oponentem: A

Odpovědnost: Mgr. et Mgr. Hana Odstrčilová