Publication Details

Automata-based Verification of Programs with Tree Updates

HABERMEHL, P.; IOSIF, R.; VOJNAR, T. Automata-based Verification of Programs with Tree Updates. Tools and Algorithms for the Construction and Analysis of Systems. Lecture Notes in Computer Science. Berlin: Springer Verlag, 2006. p. 350-364. ISBN: 978-3-540-33056-1.
Czech title
Verifikace programů s operacemi nad vyváženými stromy s využitím automatů
Type
conference paper
Language
English
Authors
Habermehl Peter
Radu Iosif
Vojnar Tomáš, prof. Ing., Ph.D. (DITS)
URL
Keywords

Formal verification, symbolic verification, programs handling balanced trees, theory of automata.

Abstract

This paper describes an effective verification procedure for imperative programs that handle (balanced) tree-like data structures. Since the verification problem considered is undecidable, we appeal to a classical semi-algorithmic approach in which the user has to provide manually the loop invariants in order to check the validity of Hoare triples of the form {P}C{Q}, where P, Q are the sets of states corresponding to the pre- and post-conditions, and C is the program to be verified. We specify the sets of states (representing tree-like memory configurations) using  a special class of tree automata named Tree Automata with Size Constraints (TASC). The main advantage of using TASC in program specifications is that they recognize non-regular sets of tree languages such as the AVL trees, the  red-black trees, and in general, specifications involving arithmetic reasoning about the lengths (depths) of various (possibly all) paths in the tree. The class of TASC is closed under the operations of union, intersection and complement, and moreover, the emptiness problem is decidable, which makes it a practical verification tool. We validate our approach considering red-black trees and the insertion procedure, for which we verify that the output of the insertion algorithm is a balanced red-black tree, i.e. the longest path is at most twice as long as the shortest path.

Published
2006
Pages
350–364
Proceedings
Tools and Algorithms for the Construction and Analysis of Systems
Series
Lecture Notes in Computer Science
Volume
3920
ISBN
978-3-540-33056-1
Publisher
Springer Verlag
Place
Berlin
BibTeX
@inproceedings{BUT30893,
  author="Peter {Habermehl} and Iosif {Radu} and Tomáš {Vojnar}",
  title="Automata-based Verification of Programs with Tree Updates",
  booktitle="Tools and Algorithms for the Construction and Analysis of Systems",
  year="2006",
  series="Lecture Notes in Computer Science",
  volume="3920",
  pages="350--364",
  publisher="Springer Verlag",
  address="Berlin",
  isbn="978-3-540-33056-1",
  url="http://www-verimag.imag.fr/TR/TR-2005-16.ps"
}
Back to top