Project Details

Práce se složitými datovými strukturami a paralelismem v prostředí Rich Model Toolkit

Project Period: 1. 1. 2010 - 31. 12. 2012

Project Type: grant

Code: OC10009

Agency: Ministry of Education, Youth and Sports Czech Republic

Program: COST

English title
Dealing with Complex Data Structures and Concurrency within the Rich Model Toolkit
Type
grant
Keywords

Automated verification, programs with complex data structures, concurrent systems, symbolic verification, static and dynamic analysis, model checking, theory of automata and logics

Abstract

The project contributes to the research planned within the COST action IC0901: Rich Model Toolkit - An Infrastructure for Reliable Computer Systems, which is targeted at (1) development of a language for describing in a homogeneous way a broad range of computer systems to be verified and (2) research in the area of methods for formal verification with the goal of significantly increasing their generality, efficiency, and degree of automation. The proposed project in particular considers two aspects of the systems dealt with in the COST action IC0901 that constitute a very significant challenge for the current verification methods. Namely, the project considers development of new verification methods for computer systems with complex data structures (including dynamic data structures based on pointers) and/or with advanced features of concurrency. In the former case, the project concentrates on research on symbolic verification methods based on the theory of automata, logics, and their combinations. In the latter case, the project pursues research in the areas of model checking, static analysis, dynamic analysis as well as their suitable combinations aimed at significantly improving their capabilities for verification of modern massively concurrent systems.

Team members
Vojnar Tomáš, prof. Ing., Ph.D. (UITS FIT VUT) , research leader
Češka Milan, prof. RNDr., CSc. (UITS FIT VUT) , team leader
Křena Bohuslav, Ing., Ph.D. (UITS FIT VUT) , team leader
Peringer Petr, Dr. Ing. (UITS FIT VUT) , team leader
Rogalewicz Adam, doc. Mgr., Ph.D. (UITS FIT VUT) , team leader
Smrčka Aleš, Ing., Ph.D. (UITS FIT VUT) , team leader
Dudka Kamil, Ing. (UITS FIT VUT)
Dudka Vendula, Ing. (UITS FIT VUT)
Fiedor Jan, Ing., Ph.D. (UITS FIT VUT)
Gach Marek, Ing. (UITS FIT VUT)
Holík Lukáš, doc. Mgr., Ph.D. (UITS FIT VUT)
Charvát Lukáš, Ing. (UITS FIT VUT)
Konečný Filip, Ing. (UITS FIT VUT)
Letko Zdeněk, Ing., Ph.D. (UITS FIT VUT)
Šimáček Jiří, Ing., Ph.D. (UITS FIT VUT)
Publications

2013

  • KŘENA Bohuslav and VOJNAR Tomáš. Automated formal analysis and verification: an overview. International Journal of General Systems, vol. 2013, no. 42, pp. 335-365. ISSN 0308-1079. Detail
  • ABDULLA Parosh A., CEDERBERG Jonathan and VOJNAR Tomáš. Monotonic Abstraction for Programs with Multiply-Linked Structures. International Journal of Foundations of Computer Science, vol. 24, no. 2, 2013, pp. 187-210. ISSN 0129-0541. Detail

2012

  • ČEŠKA Milan, FIEDOR Jan and GACH Marek. A Novel Approach to Modechart Verification of Real-Time systems. Lecture Notes in Computer Science, vol. 2012, no. 6927, pp. 559-567. ISSN 0302-9743. Detail
  • FIEDOR Jan, KŘENA Bohuslav, LETKO Zdeněk and VOJNAR Tomáš. A Uniform Classification of Common Concurrency Errors. Lecture Notes in Computer Science, vol. 2012, no. 6927, pp. 519-526. ISSN 0302-9743. Detail
  • KONEČNÝ Filip, HOJJAT Hossein, IOSIF Radu, KUNCAK Viktor, RUMMER Philipp and GARNIER Florent. A Verification Toolkit for Numerical Transition Systems. Lecture Notes in Computer Science, vol. 2012, no. 7436, pp. 247-251. ISSN 0302-9743. Detail
  • BOUAJJANI Ahmed, HABERMEHL Peter, ROGALEWICZ Adam and VOJNAR Tomáš. Abstract Regular (Tree) Model Checking. International Journal on Software Tools for Technology Transfer, vol. 14, no. 2, 2012, pp. 167-191. ISSN 1433-2779. Detail
  • IOSIF Radu, HOJJAT Hossein, KONEČNÝ Filip, KUNCAK Viktor and RUMMER Philipp. Accelerating Interpolants. Lecture Notes in Computer Science, vol. 2012, no. 7561, pp. 187-202. ISSN 0302-9743. Detail
  • DUDKA Kamil, PERINGER Petr and VOJNAR Tomáš. An Easy to Use Infrastructure for Building Static Analysis Tools. Lecture Notes in Computer Science, vol. 2012, no. 6927, pp. 527-534. ISSN 0302-9743. Detail
  • FIEDOR Jan and VOJNAR Tomáš. ANaConDA: A Framework for Analysing Multi-threaded C/C++ Programs on the Binary Level. Lecture Notes in Computer Science, vol. 2012, no. 7687, pp. 35-41. ISSN 0302-9743. Detail
  • KŘENA Bohuslav, LETKO Zdeněk and VOJNAR Tomáš. Analysis and Testing of Concurrent Programs. FIT Monograph. Brno: Faculty of Information Technology BUT, 2012. ISBN 978-80-214-4464-5. Detail
  • CHARVÁT Lukáš, SMRČKA Aleš and VOJNAR Tomáš. Automatic Formal Correspondence Checking of ISA and RTL Microprocessor Description. In: Proceedings of the 13th International Workshop on Microprocessor Test and Verification (MTV 2012). Austin, TX: Institute of Electrical and Electronics Engineers, 2012, pp. 6-12. ISBN 978-1-4673-4441-8. Detail
  • KŘENA Bohuslav, LETKO Zdeněk and VOJNAR Tomáš. Coverage Metrics for Saturation-based and Search-based Testing of Concurrent Software. Lecture Notes in Computer Science, vol. 2012, no. 7186, pp. 177-192. ISSN 0302-9743. Detail
  • DUDKA Vendula, FIEDOR Jan, KŘENA Bohuslav and VOJNAR Tomáš. DA-BMC: A Tool Chain Combining Dynamic Analysis and Bounded Model Checking. Lecture Notes in Computer Science, vol. 2012, no. 7186, p. 5. ISSN 0302-9743. Detail
  • KONEČNÝ Filip, IOSIF Radu and BOZGA Marius. Deciding Conditional Termination. Lecture Notes in Computer Science, vol. 2012, no. 7214, pp. 252-266. ISSN 0302-9743. Detail
  • HABERMEHL Peter, HOLÍK Lukáš, ROGALEWICZ Adam, ŠIMÁČEK Jiří and VOJNAR Tomáš. Forest Automata for Verification of Heap Manipulation. Formal Methods in System Design, vol. 2012, no. 41, pp. 83-106. ISSN 0925-9856. Detail
  • ZACHARIÁŠOVÁ Marcela, LENGÁL Ondřej and KAJAN Michal. HAVEN: An Open Framework for FPGA-Accelerated Functional Verification of Hardware. Lecture Notes in Computer Science, vol. 2012, no. 7261, pp. 247-253. ISSN 0302-9743. Detail
  • KŘENA Bohuslav, LETKO Zdeněk and VOJNAR Tomáš. Noise Injection Heuristics for Concurrency Testing. Lecture Notes in Computer Science, vol. 2012, no. 7119, pp. 123-131. ISSN 0302-9743. Detail
  • FIEDOR Jan and VOJNAR Tomáš. Noise-Based Testing and Analysis of Multi-threaded C/C++ Programs on the Binary Level. In: PADTAD '12. Proceedings of the 10th Workshop on Parallel and Distributed Systems. New York: Association for Computing Machinery, 2012, pp. 36-46. ISBN 978-1-4503-1456-5. Detail
  • DUDKA Kamil, MÜLLER Petr, PERINGER Petr and VOJNAR Tomáš. Predator: A Verification Tool for Programs with Dynamic Linked Data Structures. Lecture Notes in Computer Science, vol. 2012, no. 7214, pp. 544-547. ISSN 0302-9743. Detail
  • DUDKA Vendula, KŘENA Bohuslav, LETKO Zdeněk and VOJNAR Tomáš. Testing of Concurrent Programs Using Genetic Algorithms. FIT-TR-2012-01, Brno, 2012. Detail
  • DUDKA Vendula, KŘENA Bohuslav, LETKO Zdeněk, UR Shmuel and VOJNAR Tomáš. Testing of Concurrent Programs with Genetic Algorithms. Lecture Notes in Computer Science, vol. 2012, no. 7515, pp. 152-167. ISSN 0302-9743. Detail
  • LENGÁL Ondřej, ŠIMÁČEK Jiří and VOJNAR Tomáš. VATA: A Library for Efficient Manipulation of Non-Deterministic Tree Automata. Lecture Notes in Computer Science, vol. 2012, no. 7214, pp. 79-94. ISSN 0302-9743. Detail

2011

  • ČEŠKA Milan, FIEDOR Jan and GACH Marek. A Novel Approach to Modechart Verification of Real-Time systems. In: 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, pp. 338-339. ISBN 978-84-693-9560-8. Detail
  • FIEDOR Jan, KŘENA Bohuslav, LETKO Zdeněk and VOJNAR Tomáš. A Uniform Classification of Common Concurrency Errors. In: 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, pp. 326-327. ISBN 978-84-693-9560-8. Detail
  • ABDULLA Parosh A., CHEN Yu-Fang, CLEMENTE Lorenzo, HOLÍK Lukáš, HONG Chih-Duo, MAYR Richard and VOJNAR Tomáš. Advanced Ramsey-based Büchi Automata Inclusion Testing. FIT-TR-2011-03, Brno: Faculty of Information Technology BUT, 2011. Detail
  • ABDULLA Parosh A., CHEN Yu-Fang, CLEMENTE Lorenzo, HOLÍK Lukáš, HONG Chih-Duo, MAYR Richard and VOJNAR Tomáš. Advanced Ramsey-based Büchi Automata Inclusion Testing. Lecture Notes in Computer Science, vol. 2011, no. 6901, pp. 187-202. ISSN 0302-9743. Detail
  • DUDKA Kamil, PERINGER Petr and VOJNAR Tomáš. An Easy to Use Infrastructure for Building Static Analysis Tools. In: 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, pp. 328-329. ISBN 978-84-693-9560-8. Detail
  • DUDKA Vendula, FIEDOR Jan, KŘENA Bohuslav and VOJNAR Tomáš. DA-BMC: A Tool Chain Combining Dynamic Analysis and Bounded Model Checking. FIT-TR-2011-06, Brno: Faculty of Information Technology BUT, 2011. Detail
  • HOLÍK Lukáš, LENGÁL Ondřej, ŠIMÁČEK Jiří and VOJNAR Tomáš. Efficient Inclusion Checking on Explicit and Semi-Symbolic Tree Automata. Lecture Notes in Computer Science, vol. 2011, no. 6996, pp. 243-258. ISSN 0302-9743. Detail
  • HOLÍK Lukáš, LENGÁL Ondřej, ŠIMÁČEK Jiří and VOJNAR Tomáš. Efficient Inclusion Checking on Explicit and Semi-Symbolic Tree Automata. FIT-TR-2011-04, Brno: Faculty of Information Technology BUT, 2011. Detail
  • HABERMEHL Peter, HOLÍK Lukáš, ROGALEWICZ Adam, ŠIMÁČEK Jiří and VOJNAR Tomáš. Forest Automata for Verification of Heap Manipulation. Lecture Notes in Computer Science, vol. 2011, no. 6806, pp. 424-440. ISSN 0302-9743. Detail
  • HABERMEHL Peter, HOLÍK Lukáš, ROGALEWICZ Adam, ŠIMÁČEK Jiří and VOJNAR Tomáš. Forest Automata for Verification of Heap Manipulation. FIT-TR-2011-01, Brno: Faculty of Information Technology BUT, 2011. Detail
  • ZACHARIÁŠOVÁ Marcela, LENGÁL Ondřej and KAJAN Michal. HAVEN: An Open Framework for FPGA-Accelerated Functional Verification of Hardware. FIT-TR-2011-05, Brno: Faculty of Information Technology BUT, 2011. Detail
  • ABDULLA Parosh A., CEDERBERG Jonathan and VOJNAR Tomáš. Monotonic Abstraction for Programs with Multiply-Linked Structures. Lecture Notes in Computer Science, vol. 2011, no. 6945, pp. 125-138. ISSN 0302-9743. Detail
  • DUDKA Kamil, PERINGER Petr and VOJNAR Tomáš. Predator: A Practical Tool for Checking Manipulation of Dynamic Data Structures Using Separation Logic. Lecture Notes in Computer Science, vol. 2011, no. 6806, pp. 372-378. ISSN 0302-9743. Detail
  • DUDKA Kamil, PERINGER Petr and VOJNAR Tomáš. 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
  • BOUAJJANI Ahmed, BOZGA Marius, HABERMEHL Peter, IOSIF Radu, MORO Pierre and VOJNAR Tomáš. Programs with Lists are Counter Automata. Formal Methods in System Design, vol. 38, no. 2, 2011, pp. 158-192. ISSN 0925-9856. Detail

2010

  • KŘENA Bohuslav, LETKO Zdeněk, UR Shmuel and VOJNAR Tomáš. A Platform for Search-Based Testing of Concurrent Software. In: PADTAD '10. Proceedings of the 8th Workshop on Parallel and Distributed Systems. Trento: Association for Computing Machinery, 2010, p. 11. ISBN 978-1-60558-823-0. Detail
  • FIEDOR Jan, KŘENA Bohuslav, LETKO Zdeněk and VOJNAR Tomáš. A Uniform Classification of Common Concurrency Errors. FIT-TR-2010-03, Brno, 2010. Detail
  • BOZGA Marius, IOSIF Radu and KONEČNÝ Filip. Fast Acceleration of Ultimately Periodic Relations. In: Computer Aided Verification. Lecture Notes in Computer Science, vol. 6174. Berlin: Springer Verlag, 2010, pp. 227-242. ISBN 978-3-642-14294-9. Detail
  • ABDULLA Parosh A., CLEMENTE Lorenzo, HOLÍK Lukáš, HONG Chih-Duo, CHEN Yu-Fang, MAYR Richard and VOJNAR Tomáš. Simulation Subsumption in Ramsey-based Büchi Automata Universality and Inclusion Testing. FIT-TR-2010-02, Brno: Faculty of Information Technology BUT, 2010. Detail
  • ABDULLA Parosh A., CLEMENTE Lorenzo, HOLÍK Lukáš, HONG Chih-Duo, CHEN Yu-Fang, MAYR Richard and VOJNAR Tomáš. Simulation Subsumption in Ramsey-Based Büchi Automata Universality and Inclusion Testing. In: Computer Aided Verification. Lecture Notes in Computer Science, vol. 6174. Berlín: Springer Verlag, 2010, pp. 132-147. ISBN 978-3-642-14294-9. Detail
  • HOLÍK Lukáš and VOJNAR Tomáš. Simulations and Aintichains for Efficient Handling of Tree Automata. FIT Monograph. Brno: Faculty of Information Technology BUT, 2010. ISBN 978-80-214-4217-7. Detail
  • ABDULLA Parosh A., HOLÍK Lukáš, CHEN Yu-Fang, MAYR Richard and VOJNAR Tomáš. When Simulation Meets Antichains (On Checking Language Inclusion of Nondeterministic Finite (Tree) Automata). FIT-TR-2010-01, Brno: Faculty of Information Technology BUT, 2010. Detail
  • ABDULLA Parosh A., HOLÍK Lukáš, CHEN Yu-Fang, MAYR Richard and VOJNAR Tomáš. When Simulation Meets Antichains (On Checking Language Inclusion of Nondeterministic Finite (Tree) Automata). In: Tools and Algorithms for the Construction and Analysis of Systems. Lecture Notes in Computer Science, vol. 6015. Berlín: Springer Verlag, 2010, pp. 158-174. ISBN 978-3-642-12001-5. Detail
Products

2012

  • ANaConDA: A Framework for Analysing Multi-threaded C/C++ Programs on the Binary Level, software, 2012
    Authors: Fiedor Jan, Vojnar Tomáš Detail
  • HAVEN: An Open Framework for FPGA-Accelerated Functional Verification of Hardware, software, 2012
    Authors: Zachariášová Marcela, Lengál Ondřej, Kajan Michal Detail
  • VATA: A Library for Efficient Manipulation of Non-Deterministic Tree Automata, software, 2012
    Authors: Lengál Ondřej, Šimáček Jiří, Vojnar Tomáš Detail

2011

  • A Tool Chain Combining Dynamic Analysis and Bounded Model Checking, software, 2011
    Authors: Dudka Vendula, Fiedor Jan, Křena Bohuslav, Vojnar Tomáš Detail

2010

  • An Easy to Use Infrastructure for Building Static Analysis Tools, software, 2010
    Authors: Dudka Kamil, Peringer Petr, Vojnar Tomáš Detail
  • Forester: A Tool for Verification of Programs with Pointers, software, 2010
    Authors: Habermehl Peter, Holík Lukáš, Rogalewicz Adam, Šimáček Jiří, Vojnar Tomáš Detail
  • Predator: A Tool for Checking Manipulation of Dynamic Data Structures Using Separation Logic, software, 2010
    Authors: Dudka Kamil, Peringer Petr, Vojnar Tomáš Detail
  • Replay Tracer & BMC, software, 2010
    Authors: Dudka Vendula, Fiedor Jan, Křena Bohuslav, Letko Zdeněk, Vojnar Tomáš Detail
  • Search-based Testing Environment (SearchBestie), software, 2010
    Authors: Letko Zdeněk, Vojnar Tomáš, Křena Bohuslav Detail
  • Tool for verification of systems described using the Modechart formalism, software, 2010
    Authors: Gach Marek, Fiedor Jan, Češka Milan Detail
  • Tool for verification of systems specified in RT-Logic language, software, 2010
    Authors: Fiedor Jan, Gach Marek, Češka Milan Detail
Back to top