Falsifying safety properties through games on over-approximating models\r\n
File(s)falsifying-safety-attractor-game.pdf (700.64 KB)
Accepted version
Author(s)
Huth, M
Charlton, N
Type
Journal Article
Abstract
Abstractions of programs are traditionally over-approximations and have proved to be useful for the verification of safety properties. They are presently perceived as being useless for the falsification of safety properties, i.e. showing that program execution definitely reaches a ôbadö state. Alternative techniques, such as the computation of under-approximating must transitions, have addressed this shortcoming in the past. We show that over-approximating models can indeed falsify safety properties by relying on and exploiting the seriality and partial determinism of programs: programs donÆt just stop for no reason, and most program statements have deterministic semantics. Our method is based on solving a two-person attractor game derived from over-approximating models and makes no assumptions about the abstraction domain used. An example demonstrates the successful use of our approach, and highlights the role played by seriality and our handling of nondeterminism. Finally, we show that our method can encode must transitions, if supplied, by a simple modification of the ownership of nodes in the attractor game derived from the over-approximating model.\r\n
Date Issued
2008
Citation
Electronic Notes in Theoretical Computer Science, 2008, 223, pp.71-86
ISSN
1571-0661
Publisher
Elsevier
Start Page
71
End Page
86
Journal / Book Title
Electronic Notes in Theoretical Computer Science
Volume
223
Copyright Statement
© 2008 Elsevier B.V. All rights reserved. NOTICE: this is the author’s version of a work that was accepted for publication in Electronic Notes in Theoretical Computer Science. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE, VOL:223, (2008) DOI:10.1016/j.entcs.2008.12.032
Source Volume Number
223
Coverage Spatial
Liverpool, UK