Statická a dynamická verifikace programů s pokročilými rysy paralelismu a neomezenosti

Název anglicky

Static and Dynamic Verification of Programs with Advanced Features of Concurrency and Unboundedness

Typ

grant

Klíčová slova

automatická verifikace programů; statická a dynamická analýza; formální
verifikace; model checking; paralelismus; nekonečně stavové programy; dynamické
datové struktury

Abstrakt

Automatizovaná verifikace programů je v současnosti s ohledem na rostoucí dopad
počítačem řízených systémů na naše životy a výraznou potřebu minimalizovat počet
chyb v těchto systémech velmi aktuálním výzkumným tématem. Projekt se konkrétně
zaměřuje na verifikaci programů s pokročilými rysy paralelismu a neomezenosti,
které patří k obzvláště problematickým aspektům software, se kterými se musí
automatická verifikace vyrovnávat. V prvním případě se projekt soustřeďuje
zejména na metody verifikace programů určených pro moderní vícejádrové procesory.
V druhém případě se jedná o verifikaci programů pracujících s různými neomezenými
datovými strukturami, zejména pak poli (o parametrické velikosti) a složitými
dynamickými strukturami založenými na ukazatelích (jako jsou seznamy či stromy).
Projekt zahrnuje výzkum metod dynamické i statické verifikace, včetně model
checkingu, a také jejích vhodných kombinací. Pro práci s programy s nekonečnými
stavovými prostory se výzkum v projektu zaměřuje na metody efektivní symbolické
verifikace založené na použití automatů a logik.

Řešitelé

Vojnar Tomáš, prof. Ing., Ph.D. (UITS) – hlavní řešitel
Češka Milan, prof. RNDr., CSc.
Dudka Kamil, Ing.
Dudka Vendula, Ing.
Fiedor Jan, Ing., Ph.D. (UITS)
Gach Marek, Ing.
Holík Lukáš, doc. Mgr., Ph.D. (UITS)
Hýsek Jiří, Ing.
Charvát Lukáš, Ing., Ph.D.
Konečný Filip, Ing., Ph.D.
Křena Bohuslav, Ing., Ph.D. (UITS)
Letko Zdeněk, Ing., Ph.D. (CK-SZZ)
Peringer Petr, Dr. Ing. (UITS)
Rogalewicz Adam, doc. Mgr., Ph.D. (UITS)
Smrčka Aleš, Ing., Ph.D. (UITS)
Šimáček Jiří, Ing., Ph.D.

Publikace

2015

FIEDOR, J.; DUDKA, V.; KŘENA, B.; LETKO, Z.; UR, S.; VOJNAR, T. Advances in Noise-based Testing of Concurrent Programs. Software Testing Verification and Reliability, 2015, vol. 25, no. 3, p. 272-309. ISSN: 1099-1689. Detail

2013

CEDERBERG, J.; VOJNAR, T.; ABDULLA, P. Monotonic Abstraction for Programs with Multiply-Linked Structures. International Journal of Foundations of Computer Science, 2013, vol. 24, no. 2, p. 187-210. ISSN: 0129-0541. Detail
DUDKA, K.; MÜLLER, P.; PERINGER, P.; VOJNAR, T. Predator: A Tool for Verification of Low-Level List Manipulation (Competition Contribution). Tools and Algorithms for the Construction and Analysis of Systems. Lecture Notes in Computer Science. Lecture Notes in Computer Science Volume 7795. Berlin: Springer Verlag, 2013. p. 627-629. ISBN: 978-3-642-36742-7. ISSN: 0302-9743. Detail
DUDKA, K.; PERINGER, P.; VOJNAR, T. Byte-Precise Verification of Low-Level List Manipulation. 20th Static Analysis Symposium. Lecture Notes in Computer Science. Lecture Notes in Computer Science Volume 7935. Berlin: Springer Verlag, 2013. p. 215-237. ISBN: 978-3-642-38855-2. ISSN: 0302-9743. Detail
DUDKA, K.; PERINGER, P.; VOJNAR, T. Byte-Precise Verification of Low-Level List Manipulation. FIT-TR-2012-04, Brno: Faculty of Information Technology BUT, 2013. Detail
HOLÍK, L.; ABDULLA, P.; HAZIZA, F. All for the Price of Few (Parameterized Verification through View Abstraction). Proc. of VMCAI 2013. Lecture Notes in Computer Science. Berlin Heidelberg: Springer Verlag, 2013. p. 476-495. ISBN: 978-3-642-35872-2. ISSN: 0302-9743. Detail
HOLÍK, L.; ABDULLA, P.; HAZIZA, F.; JONSSON, B.; REZINE, A. An Integrated Specification and Verification Technique for Highly Concurrent Data Structures. 19th International Conference, TACAS 2013. Lecture Notes in Computer Science. Lecture Notes in Computer Science. Berlin Heidelberg: Springer Verlag, 2013. p. 324-338. ISBN: 978-3-642-36742-7. ISSN: 0302-9743. Detail
HOLÍK, L.; JONSSON, B.; LENGÁL, O.; VOJNAR, T.; TRINH, Q.; ABDULLA, P. Verification of Heap Manipulating Programs with Ordered Data by Extended Forest Automata. FIT-TR-2013-02, Brno: Faculty of Information Technology BUT, 2013. p. 1-35. Detail
HOLÍK, L.; JONSSON, B.; LENGÁL, O.; VOJNAR, T.; TRINH, Q.; ABDULLA, P. Verification of Heap Manipulating Programs with Ordered Data by Extended Forest Automata. Proceedings of ATVA'13. Heidelberg: Springer Verlag, 2013. p. 224-239. ISBN: 978-3-319-02443-1. Detail
HOLÍK, L.; LENGÁL, O.; ROGALEWICZ, A.; ŠIMÁČEK, J.; VOJNAR, T. Fully Automated Shape Analysis Based on Forest Automata. FIT-TR-2013-01, Brno: Faculty of Information Technology BUT, 2013. p. 1-25. Detail
HOLÍK, L.; LENGÁL, O.; ROGALEWICZ, A.; ŠIMÁČEK, J.; VOJNAR, T. Fully Automated Shape Analysis Based on Forest Automata. Proceedings of CAV'13. Lecture Notes in Computer Science. Heidelberg: Springer Verlag, 2013. p. 740-755. ISBN: 978-3-642-39798-1. ISSN: 0302-9743. Detail
CHARVÁT, L.; SMRČKA, A.; VOJNAR, T. An Abstraction of Multi-Port Memories with Arbitrary Addressable Units. Computer Aided Systems Theory - EUROCAST 2013. Lecture Notes in Computer Science. Berlin Heidelberg: Springer Verlag, 2013. p. 460-468. ISBN: 978-3-642-53855-1. Detail
LETKO, Z. Analysis and Testing of Concurrent Programs. Information Sciences and Technologies Bulletin of the ACM Slovakia, 2013, vol. 5, no. 3, p. 1-8. ISSN: 1338-1237. Detail
ROGALEWICZ, A.; IOSIF, R. Automata-Based Termination Proofs. Computing and Informatics, 2013, vol. 2013, no. 4, p. 739-775. ISSN: 1335-9150. Detail
ROGALEWICZ, A.; ŠIMÁČEK, J.; IOSIF, R. The Tree Width of Separation Logic with Recursive Definitions. arXiv:1301.5139: 2013. Detail
ROGALEWICZ, A.; ŠIMÁČEK, J.; IOSIF, R. The Tree Width of Separation Logic with Recursive Definitions. Automated Deduction - CADE-24. Lecture Notes in Computer Science. Lecture Notes in Artificial Intelligence. Berlin: Springer Verlag, 2013. p. 21-38. ISBN: 978-3-642-38573-5. ISSN: 0302-9743. Detail
VOJNAR, T.; KŘENA, B. Automated formal analysis and verification: an overview. INTERNATIONAL JOURNAL OF GENERAL SYSTEMS, 2013, vol. 2013, no. 42, p. 335-365. ISSN: 0308-1079. Detail

2012

ČEŠKA, M.; FIEDOR, J.; GACH, M. A Novel Approach to Modechart Verification of Real-Time systems. Lecture Notes in Computer Science, 2012, vol. 2012, no. 6927, p. 559-567. ISSN: 0302-9743. Detail
DUDKA, K.; MÜLLER, P.; PERINGER, P.; VOJNAR, T. Predator: A Verification Tool for Programs with Dynamic Linked Data Structures (Competition Contribution). Lecture Notes in Computer Science, 2012, vol. 2012, no. 7214, p. 544-547. ISSN: 0302-9743. Detail
DUDKA, K.; PERINGER, P.; VOJNAR, T. An Easy to Use Infrastructure for Building Static Analysis Tools. Lecture Notes in Computer Science, 2012, vol. 2012, no. 6927, p. 527-534. ISSN: 0302-9743. Detail
DUDKA, V.; FIEDOR, J.; KŘENA, B.; VOJNAR, T. DA-BMC: A Tool Chain Combining Dynamic Analysis and Bounded Model Checking. Lecture Notes in Computer Science, 2012, vol. 2012, no. 7186, p. 1-5. ISSN: 0302-9743. Detail
DUDKA, V.; KŘENA, B.; LETKO, Z.; UR, S.; VOJNAR, T. Testing of Concurrent Programs with Genetic Algorithms. Lecture Notes in Computer Science, 2012, roč. 2012, č. 7515, s. 152-167. ISSN: 0302-9743. Detail
DUDKA, V.; KŘENA, B.; LETKO, Z.; VOJNAR, T. Testing of Concurrent Programs Using Genetic Algorithms. FIT-TR-2012-01, Brno: 2012. Detail
FIEDOR, J.; KŘENA, B.; LETKO, Z.; VOJNAR, T. A Uniform Classification of Common Concurrency Errors. Lecture Notes in Computer Science, 2012, vol. 2012, no. 6927, p. 519-526. ISSN: 0302-9743. Detail
FIEDOR, J.; VOJNAR, T. Noise-Based Testing and Analysis of Multi-threaded C/C++ Programs on the Binary Level. PADTAD '12. Proceedings of the 10th Workshop on Parallel and Distributed Systems. New York: Association for Computing Machinery, 2012. p. 36-46. ISBN: 978-1-4503-1456-5. Detail
FIEDOR, J.; VOJNAR, T. ANaConDA: A Framework for Analysing Multi-threaded C/C++ Programs on the Binary Level. Lecture Notes in Computer Science, 2012, vol. 2012, no. 7687, p. 35-41. ISSN: 0302-9743. Detail
HOLÍK, L.; ROGALEWICZ, A.; ŠIMÁČEK, J.; VOJNAR, T.; HABERMEHL, P. Forest Automata for Verification of Heap Manipulation. FORMAL METHODS IN SYSTEM DESIGN, 2012, vol. 2012, no. 41, p. 83-106. ISSN: 0925-9856. Detail
CHARVÁT, L.; SMRČKA, A.; VOJNAR, T. Automatic Formal Correspondence Checking of ISA and RTL Microprocessor Description. Proceedings of the 13th International Workshop on Microprocessor Test and Verification (MTV 2012). Austin, TX: Institute of Electrical and Electronics Engineers, 2012. p. 6-12. ISBN: 978-1-4673-4441-8. Detail
IOSIF, R.; HOJJAT, H.; KONEČNÝ, F.; KUNCAK, V.; RUMMER, P. Accelerating Interpolants. Lecture Notes in Computer Science, 2012, vol. 2012, no. 7561, p. 187-202. ISSN: 0302-9743. Detail
KONEČNÝ, F.; HOJJAT, H.; IOSIF, R.; KUNCAK, V.; RUMMER, P.; GARNIER, F. A Verification Toolkit for Numerical Transition Systems. Lecture Notes in Computer Science, 2012, vol. 2012, no. 7436, p. 247-251. ISSN: 0302-9743. Detail
KONEČNÝ, F.; IOSIF, R.; BOZGA, M. Deciding Conditional Termination. Lecture Notes in Computer Science, 2012, vol. 2012, no. 7214, p. 252-266. ISSN: 0302-9743. Detail
KŘENA, B.; LETKO, Z.; VOJNAR, T. Analysis and Testing of Concurrent Programs. FIT Monograph. FIT Monograph. Brno: Faculty of Information Technology BUT, 2012. 136 p. ISBN: 978-80-214-4464-5. Detail
KŘENA, B.; LETKO, Z.; VOJNAR, T. Noise Injection Heuristics for Concurrency Testing. Lecture Notes in Computer Science, 2012, vol. 2012, no. 7119, p. 123-131. ISSN: 0302-9743. Detail
LENGÁL, O. An Efficient Finite Tree Automata Library: The Design of BDD-based Semi-symbolic Algorithms for Nondeterministic Finite Tree Automata. Saarbrücken: Lambert Academic Publishing, 2012. 64 p. ISBN: 978-3-659-27069-7. Detail
LENGÁL, O.; ŠIMÁČEK, J.; VOJNAR, T. VATA: A Library for Efficient Manipulation of Non-Deterministic Tree Automata. Lecture Notes in Computer Science, 2012, vol. 2012, no. 7214, p. 79-94. ISSN: 0302-9743. Detail
LETKO, Z.; VOJNAR, T.; KŘENA, B. Coverage Metrics for Saturation-based and Search-based Testing of Concurrent Software. Lecture Notes in Computer Science, 2012, roč. 2012, č. 7186, s. 177-192. ISSN: 0302-9743. Detail
NOVOSAD, P.; ČEŠKA, M. Unfoldings of Bounded Hybrid Petri Nets. Lecture Notes in Computer Science, 2012, vol. 2012, no. 6927, p. 543-550. ISSN: 0302-9743. Detail
ROGALEWICZ, A.; VOJNAR, T.; HABERMEHL, P.; BOUAJJANI, A. Abstract Regular (Tree) Model Checking. International Journal on Software Tools for Technology Transfer, 2012, vol. 14, no. 2, p. 167-191. ISSN: 1433-2779. Detail
ZACHARIÁŠOVÁ, M.; LENGÁL, O.; KAJAN, M. HAVEN: An Open Framework for FPGA-Accelerated Functional Verification of Hardware. Lecture Notes in Computer Science, 2012, vol. 2012, no. 7261, p. 247-253. ISSN: 0302-9743. Detail

2011

ABDULLA, P.; CHEN, Y.; CLEMENTE, L.; HOLÍK, L.; HONG, C.; MAYR, R.; VOJNAR, T. Advanced Ramsey-based Büchi Automata Inclusion Testing. FIT-TR-2011-03, Brno: Faculty of Information Technology BUT, 2011. Detail
ABDULLA, P.; CHEN, Y.; CLEMENTE, L.; HOLÍK, L.; HONG, C.; MAYR, R.; VOJNAR, T. Advanced Ramsey-based Büchi Automata Inclusion Testing. Lecture Notes in Computer Science, 2011, vol. 2011, no. 6901, p. 187-202. ISSN: 0302-9743. Detail
DUDKA, K.; PERINGER, P.; VOJNAR, T. An Easy to Use Infrastructure for Building Static Analysis Tools. Proceedings of the 13th International Conference on Computer Aided Systems Theory. Universidad de Las Palmas de Canaria: The Universidad de Las Palmas de Gran Canaria, 2011. p. 328-329. ISBN: 978-84-693-9560-8. Detail
DUDKA, K.; PERINGER, P.; VOJNAR, T. Predator: A Practical Tool for Checking Manipulation of Dynamic Data Structures Using Separation Logic. FIT-TR-2011-02, Brno: Faculty of Information Technology BUT, 2011. Detail
DUDKA, K.; PERINGER, P.; VOJNAR, T. Predator: A Practical Tool for Checking Manipulation of Dynamic Data Structures Using Separation Logic. Lecture Notes in Computer Science, 2011, vol. 2011, no. 6806, p. 372-378. ISSN: 0302-9743. Detail
DUDKA, V.; FIEDOR, J.; KŘENA, B.; VOJNAR, T. DA-BMC: A Tool Chain Combining Dynamic Analysis and Bounded Model Checking. FIT-TR-2011-06, Brno: Faculty of Information Technology BUT, 2011. Detail
FIEDOR, J.; GACH, M.; ČEŠKA, M. A Novel Approach to Modechart Verification of Real-Time Systems. Proceedings of the 13th International Conference on Computer Aided Systems Theory. Universidad de Las Palmas de Canaria: The Universidad de Las Palmas de Gran Canaria, 2011. p. 338-339. ISBN: 978-84-693-9560-8. Detail
FIEDOR, J.; LETKO, Z.; VOJNAR, T.; KŘENA, B. A Uniform Classification of Common Concurrency Errors. Proceedings of the 13th International Conference on Computer Aided Systems Theory. Universidad de Las Palmas de Canaria: The Universidad de Las Palmas de Gran Canaria, 2011. p. 326-327. ISBN: 978-84-693-9560-8. Detail
HOLÍK, L.; LENGÁL, O.; ŠIMÁČEK, J.; VOJNAR, T. Efficient Inclusion Checking on Explicit and Semi-Symbolic Tree Automata. FIT-TR-2011-04, Brno: Faculty of Information Technology BUT, 2011. Detail
HOLÍK, L.; LENGÁL, O.; ŠIMÁČEK, J.; VOJNAR, T. Efficient Inclusion Checking on Explicit and Semi-Symbolic Tree Automata. Lecture Notes in Computer Science, 2011, vol. 2011, no. 6996, p. 243-258. ISSN: 0302-9743. Detail
HOLÍK, L.; ROGALEWICZ, A.; ŠIMÁČEK, J.; VOJNAR, T.; HABERMEHL, P. Forest Automata for Verification of Heap Manipulation. FIT-TR-2011-01, Brno: Faculty of Information Technology BUT, 2011. Detail
HOLÍK, L.; ROGALEWICZ, A.; ŠIMÁČEK, J.; VOJNAR, T.; HABERMEHL, P. Forest Automata for Verification of Heap Manipulation. Lecture Notes in Computer Science, 2011, vol. 2011, no. 6806, p. 424-440. ISSN: 0302-9743. Detail
VOJNAR, T.; IOSIF, R.; HABERMEHL, P.; BOUAJJANI, A.; BOZGA, M.; MORO, P. Programs with Lists are Counter Automata. FORMAL METHODS IN SYSTEM DESIGN, 2011, vol. 38, no. 2, p. 158-192. ISSN: 0925-9856. Detail
ZACHARIÁŠOVÁ, M.; LENGÁL, O.; KAJAN, M. HAVEN: An Open Framework for FPGA-Accelerated Functional Verification of Hardware. FIT-TR-2011-05, Brno: Faculty of Information Technology BUT, 2011. Detail

2010

BOZGA, M.; IOSIF, R.; KONEČNÝ, F. Fast Acceleration of Ultimately Periodic Relations. Computer Aided Verification. Lecture Notes in Computer Science. Berlin: Springer Verlag, 2010. p. 227-242. ISBN: 978-3-642-14294-9. Detail
FIEDOR, J.; KŘENA, B.; LETKO, Z.; VOJNAR, T. A Uniform Classification of Common Concurrency Errors. FIT-TR-2010-03, Brno: 2010. Detail
HOLÍK, L.; VOJNAR, T. Simulations and Aintichains for Efficient Handling of Tree Automata. FIT Monograph. FIT Monograph. Brno: Faculty of Information Technology BUT, 2010. 150 p. ISBN: 978-80-214-4217-7. Detail
HOLÍK, L.; VOJNAR, T.; ABDULLA, P.; CHEN, Y.; MAYR, R. When Simulation Meets Antichains (On Checking Language Inclusion of Nondeterministic Finite (Tree) Automata). Tools and Algorithms for the Construction and Analysis of Systems. Lecture Notes in Computer Science. Berlín: Springer Verlag, 2010. p. 158-174. ISBN: 978-3-642-12001-5. Detail
HOLÍK, L.; VOJNAR, T.; CHEN, Y.; MAYR, R.; HONG, C.; ABDULLA, P.; CLEMENTE, L. Simulation Subsumption in Ramsey-Based Büchi Automata Universality and Inclusion Testing. Computer Aided Verification. Lecture Notes in Computer Science. Berlín: Springer Verlag, 2010. p. 132-147. ISBN: 978-3-642-14294-9. Detail
HOLÍK, L.; VOJNAR, T.; CHEN, Y.; MAYR, R.; HONG, C.; ABDULLA, P.; CLEMENTE, L. Simulation Subsumption in Ramsey-based Büchi Automata Universality and Inclusion Testing. FIT-TR-2010-02, Brno: Faculty of Information Technology BUT, 2010. Detail
KŘENA, B.; LETKO, Z.; UR, S.; VOJNAR, T. A Platform for Search-Based Testing of Concurrent Software. PADTAD '10. Proceedings of the 8th Workshop on Parallel and Distributed Systems. Trento: Association for Computing Machinery, 2010. p. 48-58. ISBN: 978-1-60558-823-0. Detail
KŘENA, B.; LETKO, Z.; VOJNAR, T.; UR, S. A Platform for Search-Based Testing of Concurrent Software. 6th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science. Brno: Masaryk University, 2010. p. 208-208. ISBN: 978-80-87342-10-7. Detail
LETKO, Z. Sophisticated Testing of Concurrent Software. SSBSE '10. Proceedings of 2nd International Symposium on Search Based Software Engineering. Benevento: Institute of Electrical and Electronics Engineers, 2010. p. 36-40. ISBN: 978-0-7695-4195-2. Detail
SMRČKA, A. Verification of Asynchronous and Parametrized Hardware Designs. Information Sciences and Technologies Bulletin of the ACM Slovakia, 2010, vol. 2, no. 2, p. 60-69. ISSN: 1338-1237. Detail
SMRČKA, A.; VOJNAR, T. Verification of Asynchronous and Parametrized Hardware Designs. FIT Monograph. FIT Monograph. Brno: Faculty of Information Technology BUT, 2010. 115 p. ISBN: 978-80-214-4214-6. Detail

Produkty

2013

CPAlien: Konfigurovatelná analýza programů nad symbolickými paměťovými grafy, software, 2013
Autoři: MÜLLER, P.; VOJNAR, T.

2012

ANaConDA: Prostředí pro analýzu vícevláknových C/C++ programů na binární úrovni, software, 2012
Autoři: FIEDOR, J.; VOJNAR, T.
HAVEN: Otevřený rámec pro akceleraci funkční verifikace hardwaru pomocí FPGA, software, 2012
Autoři: ZACHARIÁŠOVÁ, M.; LENGÁL, O.; KAJAN, M.
VATA: Knihovna pro efektivní práci s nedeterministickými stromovými automaty, software, 2012
Autoři: LENGÁL, O.; ŠIMÁČEK, J.; VOJNAR, T.

2011

Nástroj propojující dynamickou analýzu a bounded model checking, software, 2011
Autoři: DUDKA, V.; FIEDOR, J.; VOJNAR, T.; KŘENA, B.

2010

Forester: Nástroj pro verifikaci programů s ukazateli, software, 2010
Autoři: ŠIMÁČEK, J.; HOLÍK, L.; ROGALEWICZ, A.; VOJNAR, T.; HABERMEHL, P.
Framework pro formální verifikaci asynchronních komponent, software, 2010
Autoři: SMRČKA, A.; VOJNAR, T.
libSFTA: Prototyp knihovny pro efektivní práci se semi-symbolicky reprezentovanými nedeterministickými stromovými automaty, software, 2010
Autoři: LENGÁL, O.; HOLÍK, L.; VOJNAR, T.
Nástroj pro přehrávání běhu programu (Replay Tracer & BMC), software, 2010
Autoři: DUDKA, V.; FIEDOR, J.; KŘENA, B.; LETKO, Z.; VOJNAR, T.
Nástroj pro verifikaci systémů popsaných formalismem Modechart, software, 2010
Autoři: GACH, M.; FIEDOR, J.; ČEŠKA, M.
Nástroj pro verifikaci systémů specifikovaných jazykem RT-Logiky, software, 2010
Autoři: FIEDOR, J.; GACH, M.; ČEŠKA, M.
Predator: Nástroj pro ověřování manipulace s dynamickými datovými strukturami založený na separační logice, software, 2010
Autoři: DUDKA, K.; PERINGER, P.; VOJNAR, T.
Snadno použitelná infrastruktura pro výstavbu nástrojů na statickou analýzu, software, 2010
Autoři: DUDKA, K.; PERINGER, P.; VOJNAR, T.
Testovací prostředí využívající techniky prohledávání prostoru (SearchBestie), software, 2010
Autoři: LETKO, Z.; VOJNAR, T.; KŘENA, B.