Forester: Shape Analysis Based on Forest Automata and Predator: A Brief Note on a New Separation Logic-based Tool

Date: Thursday, November 17, 2011
Speaker: Tomas Vojnar
Venue: TU Vienna

We consider verification of programs manipulating dynamic linked data structures such as various forms of singly and doubly-linked lists or trees. We consider important properties for this kind of systems like no null-pointer dereferences, absence of garbage, shape properties, etc.In the first part of the talk, we present a verification method based on a novel use of tree automata to represent heap configurations. A heap is split into several “separated” parts such that each of them can be represented by a tree automaton. The automata can refer to each other allowing the different parts of the heaps to mutually refer to their boundaries. Moreover, we allow for a hierarchical representation of heaps by allowing alphabets of the tree automata to contain other, nested tree automata. Program instructions can easily be encoded as operations on our representation structure. This allows verification of programs based on a symbolic state-space exploration together with refinable abstraction within the so-called abstract regular tree model checking.In the second part of the talk, a new separation-logic-based tool called Predator will briefly be presented. The tool is specifically tuned to handle various kinds of linked lists in the low-level form used in system software.(Forester is a joint work with Peter Habermehl from LIAFA, Paris, Lukas Holik and Adam Rogalewicz from FIT, Brno University of Technology, and Jiri Simacek from FIT BUT and VERIMAG, Grenoble. Predator is a joint work with Kamil Dudka and Petr Peringer from FIT BUT.)


Posted in RiSE Seminar