Mgr. Lukáš Holík, Ph.D.

Automatic Verification of Programs with Dynanic Data Structures with Pointers

Czech title:Automatická verifikace programů s dynamickými datovými strukturami provázanými ukazateli
Reseach leader:Vojnar Tomáš
Team leaders:Habermehl Peter (UPAR7)
Team members:Bouajjani Ahmed (UPAR7), Češka Milan, Erlebach Pavel, Holík Lukáš, Moro Pierre (LIAFA UP7/CNRS), Rogalewicz Adam, Touili Tayssir (LIAFA UP7/CNRS)
Agency:Barrande - Czech-French programme of integrated actions
Code:2-06-27
Start:2006-01-01
End:2007-12-31
Keywords:formal verification, infinite-state systems, regular model checking, programs with dynamic linked data structures
Annotation:
Though there have already been proposed multiple approaches to automatic formal verification (or static analysis) of programs with pointers and dynamic linked data structures, these approaches are still far from being general (i.e. covering all the different shapes of structures that one may encounter in practice), fully automatic, and at the same time efficient. The goal of the present project is thus to push the current state-of-the-art in the given area as far as possible towards obtaining techniques for automated verification of programs with dynamic linked data structures that would meet the above described criteria. The way the project intends to achieve the above goal is primarily based on a further development of the abstract regular model checking (ARMC) framework proposed by A. Boujjani, P. Habermehl, and T. Vojnar at CAV 2004.

Publications

2008ABDULLA Parosh A., BOUAJJANI Ahmed, HOLÍK Lukáš, KAATI Lisa and VOJNAR Tomáš. Computing Simulations over Tree Automata: Efficient Techniques for Reducing Tree Automata. FIT-TR-2008-001, Brno, 2008.
 ABDULLA Parosh A., HOLÍK Lukáš, KAATI Lisa and VOJNAR Tomáš. A Uniform (Bi-)Simulation-Based Framework for Reducing Tree Automata. FIT-TR-2008-005, Brno, 2008.
 HABERMEHL Peter, IOSIF Radu and VOJNAR Tomáš. What else is decidable about integer arrays?. In: Foundations of Software Science and Computation Structures. Berlin: Springer Verlag, 2008, pp. 475-490. ISBN 978-3-540-78497-5.
 VOJNAR Tomáš, ČEŠKA Milan, ROGALEWICZ Adam, ERLEBACH Pavel, HOLÍK Lukáš, BOUAJJANI Ahmed, HABERMEHL Peter, TOUILI Tayssir and MORO Pierre. Automatická verifikace programů s dynamickými datovými strukturami. Inovační podnikání & transfer technologií. 2008, vol. 2008, no. 1, pp. 21-22. ISSN 1210-4612.
2007HABERMEHL Peter, IOSIF Radu, ROGALEWICZ Adam and VOJNAR Tomáš. Proving Termination of Tree Manipulating Programs. In: Automated Technology for Verification and Analysis. Berlin: Springer Verlag, 2007, pp. 145-161. ISBN 978-3-540-75595-1.
 HOLÍK Lukáš and ROGALEWICZ Adam. Counterexample Analysis in Abstract Regular Tree Model Checking of Complex Dynamic Data Structures. In: Third Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS 2007). Znojmo: Ing. Zdeněk Novotný, CSc., 2007, pp. 59-66. ISBN 978-80-7355-077-6.
 ROGALEWICZ Adam. Verification of Programs with Complex Data Structures. Brno, 2007. ISBN 978-80-214-3548-3.
 VOJNAR Tomáš. Cut-offs and Automata in Formal Verification of Infinite-State Systems. Brno: Faculty of Information Technology BUT, 2007. ISBN 978-80-214-3547-6.
 ČEŠKA Milan, ERLEBACH Pavel and VOJNAR Tomáš. Generalised Multi-Pattern-Based Verification of Programs with Linear Linked Structures. Formal Aspects of Computing. London: Springer London, 2007, vol. 19, no. 3, pp. 363-374. ISSN 0934-5043.
 ČEŠKA Milan, ERLEBACH Pavel and VOJNAR Tomáš. Pattern-Based Verification for Trees. In: Computer Aided Systems Theory - EUROCAST 2007. Las Palmas de Grand Canaria: The Universidad de Las Palmas de Gran Canaria, 2007, pp. 181-182. ISBN 978-3-540-75866-2.
 ČEŠKA Milan, ERLEBACH Pavel and VOJNAR Tomáš. Pattern-based Verification for Trees. In: Computer Aided Systems Theory. Berlin: Springer Verlag, 2007, pp. 488-496. ISBN 978-3-540-75866-2.
2006BOUAJJANI Ahmed, HABERMEHL Peter, ROGALEWICZ Adam and VOJNAR Tomáš. Abstract Regular Tree Model Checking of Complex Dynamic Data Structures. In: Static Analysis. Berlin: Springer Verlag, 2006, pp. 52-70. ISBN 978-3-540-37756-6.
 BOUAJJANI Ahmed, HABERMEHL Peter, ROGALEWICZ Adam and VOJNAR Tomáš. Abstract Regular Tree Model Checking. Electronic Notes in Theoretical Computer Science. 2006, vol. 149, no. 1, pp. 37-48. ISSN 1571-0661.
 HABERMEHL Peter, IOSIF Radu and VOJNAR Tomáš. Automata-based Verification of Programs with Tree Updates. In: Tools and Algorithms for the Construction and Analysis of Systems. Berlin: Springer Verlag, 2006, pp. 350-364. ISBN 978-3-540-33056-1.

Your IPv4 address: 54.82.81.154
Switch to IPv6 connection

DNSSEC [dnssec]