Exploring very large state spaces using genetic algorithms

We present a novel framework for exploring very large state spaces of concurrent reactive systems. Our framework exploits application-independent heuristics using genetic algorithms to guide a state-space search toward error states. We have implemented this framework in conjunction with VeriSoft, a...

Full description

Saved in:
Bibliographic Details
Published in:International journal on software tools for technology transfer 2004-08, Vol.6 (2), p.117-127
Main Authors: GODEFROID, Patrice, KHURSHID, Sarfraz
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Applied sciences
Computer science
control theory
systems
Errors
Exact sciences and technology
Genetic algorithms
Heuristic
Software
Space
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We present a novel framework for exploring very large state spaces of concurrent reactive systems. Our framework exploits application-independent heuristics using genetic algorithms to guide a state-space search toward error states. We have implemented this framework in conjunction with VeriSoft, a tool for exploring the state spaces of software applications composed of several concurrent processes executing arbitrary code. We present experimental results obtained with several examples of programs, including a C implementation of a public-key authentication protocol. We discuss heuristics and properties of state spaces that help a genetic search detect deadlocks and assertion violations. For finding errors in very large state spaces, our experiments show that a genetic search using simple heuristics can significantly outperform random and systematic searches. [PUBLICATION ABSTRACT]
ISSN:1433-2779
1433-2787
DOI:10.1007/s10009-004-0141-1