Detail předmětu
Statická analýza a verifikace
FIT-SAVAk. rok: 2020/2021
Zavedení základních pojmů, jako jsou analýza a verifikace, formální analýza a verifikace, spolehlivost a úplnost, logický a fyzický čas, bezpečnost a živost apod. Přehled různých přístupů k statické analýze a verifikaci i dalších alternativních přístupů k verifikaci. Úvod do temporálních logik jako do jednoho z klasických mechanismů pro specifikaci ověřovaných vlastností systémů. Model checking pro logiku LTL s využitím Büchiho automatů. Využití automaticky zjemňované predikátové abstrakce jako jeden z nejúspěšnějších přístupů k model checkingu software. Abstraktní interpretace jako jedna z nejúspěšnějších metod statické analýzy: základní principy a algoritmy a přehled významných abstraktních domén. Analýza toku dat: základní pojmy a principy, klasické analýzy používané v optimalizujících překladačích, návrh vlastních analýz, ukazatelové analýzy. Řešení problémů SAT a SMT, které stojí za mnoha (nejen) verifikačními přístupy. Verifikace založená na symbolickém provádění, omezený model checking a k-indukce. Deduktivní verifikace anotovaných programů (vstupní a výstupní podmínky funkcí, invarianty cyklů). Binární rozhodovací diagramy pro efektivní ukládání (nejen) stavových prostorů. Úvod do automatizované verifikace konečnosti běhu programů (absence možného zacyklení) a automatizované analýzy složitosti.
Jazyk výuky
Počet kreditů
Garant předmětu
Zajišťuje ústav
Výsledky učení předmětu
Získané povědomí o významu a možnostech uplatnění metod a nástrojů statické analýzy a verifikace při vývoji různých typů systémů a o jejich rostoucím nasazení v praxi.
Prerekvizity
Způsob a kritéria hodnocení
Podmínky zápočtu:
Získání alespoň 50% možného bodového zisku z projektu.
Učební cíle
Doporučená literatura
Clarke, E.M., Henzinger, Th.A., Veith, H., Bloem, R. (Eds.): Handbook of Model Checking, Springer International Publishing, 2018.
Materials freely accessible on the Internet, especially papers and documentation related to the various computer-aided tools for static analysis and verification.
Materials presented within the lectures and made accessible via the Internet.
Moller, A., Schwartzbach, M.I.: Static Program Analysis, Department of Computer Science, Aarhus University, Denmark, 2018.
Rival, X., Yi, K. Introduction to Static Analysis: An Abstract Interpretation Perspective. MIT Press, 2020.
Valmari, A.: The State Explosion Problem. In Reisig, W., Rozenberg, G.: Lectures on Petri Nets I: Basic Models, volume 1491 of Lecture Notes in Computer Science, pages 429-528. Springer-Verlag, 1998.
Zařazení předmětu ve studijních plánech
- Program IT-MGR-2 magisterský navazující
obor MGM , 0 ročník, zimní semestr, volitelný
obor MBI , 0 ročník, zimní semestr, volitelný
obor MBS , 0 ročník, zimní semestr, povinně volitelný
obor MIN , 0 ročník, zimní semestr, povinně volitelný
obor MIS , 0 ročník, zimní semestr, povinně volitelný
obor MMI , 0 ročník, zimní semestr, volitelný
obor MMM , 0 ročník, zimní semestr, povinný
obor MPV , 0 ročník, zimní semestr, volitelný
obor MSK , 2 ročník, zimní semestr, povinně volitelný - Program MITAI magisterský navazující
specializace NISY , 0 ročník, zimní semestr, volitelný
specializace NADE , 0 ročník, zimní semestr, volitelný
specializace NBIO , 0 ročník, zimní semestr, volitelný
specializace NCPS , 0 ročník, zimní semestr, volitelný
specializace NEMB , 0 ročník, zimní semestr, volitelný
specializace NHPC , 0 ročník, zimní semestr, volitelný
specializace NGRI , 0 ročník, zimní semestr, volitelný
specializace NIDE , 0 ročník, zimní semestr, volitelný
specializace NISD , 0 ročník, zimní semestr, volitelný
specializace NMAL , 0 ročník, zimní semestr, volitelný
specializace NMAT , 0 ročník, zimní semestr, povinný
specializace NNET , 0 ročník, zimní semestr, volitelný
specializace NSEC , 0 ročník, zimní semestr, volitelný
specializace NSEN , 0 ročník, zimní semestr, volitelný
specializace NSPE , 0 ročník, zimní semestr, volitelný
specializace NVER , 0 ročník, zimní semestr, povinný
specializace NVIZ , 0 ročník, zimní semestr, volitelný
Typ (způsob) výuky
Přednáška
Vyučující / Lektor
Osnova
- Význam pojmů analýza a verifikace. Klasifikace ověřovaných vlastností a ověřovaných systémů. Přehled přístupů ke statické analýze a verifikaci.
- Temporální logiky CTL*, CTL a LTL.
- Model checking systémů s vlastnostmi specifikovanými v LTL s využitím Büchiho automatů.
- Model checking s využitím predikátové abstrakce postupně zjemňované na základě vylučování chybných protipříkladů.
- Abstraktní interpretace I: základní pojmy a principy.
- Abstraktní interpretace II: vybrané abstraktní domény úspěšné v praxi.
- Základní pojmy a principy analýzy toku dat, klasické analýzy toku dat.
- Pokročilejší analýzy toku dat, ukazatelové analýzy.
- Verifikace software s využitím symbolického provádění.
- Deduktivní verifikace anotovaných programů.
- Řešení problémů SAT a SMT jako základ mnoha přístupů k analýze a verifikaci.
- Binární rozhodovací diagramy.
- Verifikace konečnosti běhu programů, automatizovaná analýza výpočetní složitosti.
Projekt
Vyučující / Lektor
Osnova
Elektronické učební texty