Symmetric Symbolic Safety-Analysis of Concurrent Software with Pointer Data Structures

Farn Wang and Karsten Schmidt

View Related Documents

Abstract

We formally define the model of software with pointer data structures. We developed symbolic algorithms for the manipulation of conditions and assignments with indirect operands for verification with BDD-like data-structures. We rely on two techniques, including inactive variable elimination and process-symmetry reduction in the data-structure configuration, to contain the time and memory complexity. We use binary permutation for efficiency but also identify the possibility of anomaly of image false reachability. We implemented the techniques in tool red and compare performance with Murø and SMC against several other benchmarks.

Keywords  Symmetry - symbolic model-checking - pointers - datastructures

The work is partially supported by NSC, Taiwan, ROC under grants NSC 90-2213- E-001-006, NSC 90-2213-E-001-035, and the by the Broadband network protocol verification project of Institute of Applied Science & Engineering Research, Academia Sinica, 2001.
supported by DARPA/ITOP within the MoBIES project

Fulltext Preview

Image of the first page of the fulltext document