Project detail

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

Duration: 01.01.2010 — 31.12.2013

Funding resources

Czech Science Foundation - Standardní projekty

- whole funder (2010-01-01 - 2013-12-31)

On the project

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.

Description in English
Automated verification of programs is currently a very hot issue due to the rising influence of computer-controlled systems on our lives and the recognised need to minimise the number of errors in them. The project, in particular, considers verification of programs with advanced features of concurrency and unboundedness, which both belong among especially problematic features to be dealt with in automated verification. In the former case, the project pays a special attention to verification of applications intended to run on the current multi-core processors. In the latter case, verification of programs manipulating different unbounded structures, notably (parametrised-size) arrays and complex dynamic linked data structures (such as lists or trees), is considered. The project contains research on methods of dynamic as well as static verification, including model checking, and possibly their suitable combinations. For handling infinite-state programs, efficient symbolic verification methods based on automata and logics are the primary target of the research in the project.

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

Key words in English
automated verification of programs; static and dynamic analysis; formal verification; model checking; concurrency; infinite-state programs; dynamic data structures

Mark

GAP103/10/0306

Default language

Czech

People responsible

Češka Milan, prof. RNDr., CSc. - fellow researcher
Křena Bohuslav, Ing., Ph.D. - fellow researcher
Peringer Petr, Dr. Ing. - fellow researcher
Rogalewicz Adam, doc. Mgr., Ph.D. - fellow researcher
Smrčka Aleš, Ing., Ph.D. - fellow researcher
Vojnar Tomáš, prof. Ing., Ph.D. - principal person responsible

Units

Faculty of Information Technology
- beneficiary (2010-01-01 - 2013-12-31)

Results

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

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

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

LETKO, Z. Sophisticated Testing of Concurrent Programs. 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

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

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

SMRČKA, A. Verification of Asynchronous and Parametrized Hardware Designs. Brno: Department of Intelligent Systems FIT BUT, 2010.
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

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

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

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

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

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

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

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

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

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

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

Č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

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. Noise Injection Heuristics for Concurrency Testing. Lecture Notes in Computer Science, 2012, vol. 2012, no. 7119, p. 123-131. 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

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

DUDKA, K.; MÜLLER, P.; PERINGER, P.; VOJNAR, T. Predator: A Verification Tool for Programs with Dynamic Linked Data Structures. Lecture Notes in Computer Science, 2012, vol. 2012, no. 7214, p. 544-547. 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

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

DUDKA, V.; KŘENA, B.; LETKO, Z.; UR, S.; VOJNAR, T. Testování vícevláknových aplikací pomocí genetických algoritmů. Lecture Notes in Computer Science, 2012, roč. 2012, č. 7515, s. 152-167. 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

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

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

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

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

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

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

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

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

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

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

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

ROGALEWICZ, A.; IOSIF, R. Automata-Based Termination Proofs. Computing and Informatics, 2013, vol. 2013, no. 4, p. 739-775. ISSN: 1335-9150.
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

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

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

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

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

DUDKA, V.; FIEDOR, J.; KŘENA, B.; LETKO, Z.; VOJNAR, T.: RecRev; Replay Tracer & BMC. http://www.fit.vutbr.cz/research/groups/verifit/tools/RecRev. URL: http://www.fit.vutbr.cz/research/groups/verifit/tools/RecRev. (software)
Detail

SMRČKA, A.; VOJNAR, T.: cdcreloaded; Framework for Formal Verification of Clock Domain Crossing. http://www.fit.vutbr.cz/~smrcka/w/doku.php?id=research:cdcreloaded. URL: http://www.fit.vutbr.cz/~smrcka/w/doku.php?id=research:cdcreloaded. (software)
Detail

LETKO, Z.; VOJNAR, T.; KŘENA, B.: SearchBestie; Search-based Testing Environment (SearchBestie). http://www.fit.vutbr.cz/research/groups/verifit/tools/SearchBestie. URL: http://www.fit.vutbr.cz/research/groups/verifit/tools/SearchBestie. (software)
Detail

DUDKA, K.; PERINGER, P.; VOJNAR, T.: code-listener; An Easy to Use Infrastructure for Building Static Analysis Tools.    - http://www.fit.vutbr.cz/research/groups/verifit/tools/code-listener. URL: https://www.fit.vut.cz/research/product/150/. (software)
Detail

LENGÁL, O.; HOLÍK, L.; VOJNAR, T.: libSFTA; libSFTA: A Semi-symbolic Nondeterministic Finite Tree Automata Library Prototype. https://github.com/ondrik/libsfta. URL: https://github.com/ondrik/libsfta. (software)
Detail

FIEDOR, J.; GACH, M.; ČEŠKA, M.: zetav; Tool for verification of systems specified in RT-Logic language. http://www.fit.vutbr.cz/research/groups/verifit/tools/zetav. URL: http://www.fit.vutbr.cz/research/groups/verifit/tools/zetav. (software)
Detail

MÜLLER, P.; VOJNAR, T.: cpalien; CPAlien: Configurable Program Analysis over Symbolic Memory Graphs. http://www.fit.vutbr.cz/research/groups/verifit/tools/cpalien. URL: http://www.fit.vutbr.cz/research/groups/verifit/tools/cpalien. (software)
Detail

ŠIMÁČEK, J.; HOLÍK, L.; ROGALEWICZ, A.; VOJNAR, T.; HABERMEHL, P.: fapointers; Forester: A Tool for Verification of Programs with Pointers. Nástroj i dokumentaci lze získat na URL: http://www.fit.vutbr.cz/research/groups/verifit/tools/forester/. URL: https://www.fit.vut.cz/research/product/142/. (software)
Detail

DUDKA, K.; PERINGER, P.; VOJNAR, T.: predator; Predator: A Tool for Checking Manipulation of Dynamic Data Structures Using Separation Logic.    - http://www.fit.vutbr.cz/research/groups/verifit/tools/predator. URL: https://www.fit.vut.cz/research/product/149/. (software)
Detail

DUDKA, V.; FIEDOR, J.; VOJNAR, T.; KŘENA, B.: DA-BMC; A Tool Chain Combining Dynamic Analysis and Bounded Model Checking. http://www.fit.vutbr.cz/research/groups/verifit/tools/da-bmc. URL: http://www.fit.vutbr.cz/research/groups/verifit/tools/da-bmc. (software)
Detail

LENGÁL, O.; ŠIMÁČEK, J.; VOJNAR, T.: vata; VATA: A Library for Efficient Manipulation of Non-Deterministic Tree Automata. Nástroj i dokumentaci lze získat na URL: http://www.fit.vutbr.cz/research/groups/verifit/tools/libvata/. URL: https://www.fit.vut.cz/research/product/223/. (software)
Detail

ZACHARIÁŠOVÁ, M.; LENGÁL, O.; KAJAN, M.: haven; HAVEN: An Open Framework for FPGA-Accelerated Functional Verification of Hardware. Nástroj i dokumentaci lze získat na URL http://www.fit.vutbr.cz/~isimkova/haven/ (http://www.fit.vutbr.cz/%7Eisimkova/haven/). URL: https://www.fit.vut.cz/research/product/234/. (software)
Detail

FIEDOR, J.; VOJNAR, T.: ANaConDA; ANaConDA: A Framework for Analysing Multi-threaded C/C++ Programs on the Binary Level. http://www.fit.vutbr.cz/research/groups/verifit/tools/anaconda/. URL: http://www.fit.vutbr.cz/research/groups/verifit/tools/anaconda/. (software)
Detail

GACH, M.; FIEDOR, J.; ČEŠKA, M.: verif; Tool for verification of systems described using the Modechart formalism. http://www.fit.vutbr.cz/research/groups/verifit/tools/verif. URL: http://www.fit.vutbr.cz/research/groups/verifit/tools/verif. (software)
Detail

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