Abstract Regular Tree Model Checking of Complex Dynamic Data Structures

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F06%3APU66952" target="_blank" >RIV/00216305:26230/06:PU66952 - isvavai.cz</a>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

Abstract Regular Tree Model Checking of Complex Dynamic Data Structures

Original language description

We consider the verification of non-recursive C programs manipulating dynamic linked data structures with possibly several next pointer selectors and with finite domain non-pointer data. We aim at checking basic memory consistency properties (no null pointer assignments, etc.) and shape invariants whose violation can be expressed in an existential fragment of a first order logic over graphs. We formalise this fragment as a logic for specifying bad memory patterns whose formulae may be translated to testers written in C that can be attached to the program, thus reducing the verification problem considered to checking reachability of an error control line. We encode configurations of programs, which are essentially shape graphs, in an original way as extended tree automata and we represent program statements by tree transducers. Then, we use the abstract regular tree model checking framework for a fully automated verification. The method has been implemented and successfully applied on s

Czech name

Verifikace komplexních dynamických datových struktur za použitím abstraktního regulárního stromového model checkingu

Czech description

Článek se zabývá verifikací programů pracujících s dynamickými datovými strukturami. Každý uzel může obsahovat několik ukazatelů na následující uzly a datovou hodnotu z konečné množiny datových hodnot. Kontrolujeme zakázané manipulace s nulovými a nedefinovanými ukazateli, a dále i tvarové vlastnosti (shape properties) datové struktury. Pro specifikaci těchto vlastností používáme fragment first-order logiky nad grafy. Zakázané stavy popsané v této logice lze automaticky převést do C programu, který je přidán na konec verifikovaného programu. Tímto převedeme problem kontroly datové struktury na problem dosažitelnosti dané řádky v programu. Konfigurace programu, které jsou orientovanými grafy kódujeme jako rozšířené stromové automaty, a příkazy programujako stromové převodníky. Poté můžeme využít metodu abstract regular tree model checking pro automatickou verifikaci těchto programů. Kompletní metoda byla implementována v prototy

Type

D - Article in proceedings

CEP classification

JC - Computer hardware and software

OECD FORD branch

—

Project

Result was created during the realization of more than one project. More information in the Projects tab.

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2006

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

Static Analysis

ISBN

3540377565

ISSN

—

e-ISSN

—

Number of pages

18

Pages from-to

52-69

Publisher name

Springer Verlag

Place of publication

Berlin

Event location

Seoul

Event date

Aug 29, 2006

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—