Incremental design-space model checking via reusable reachable state approximations

Thumbnail Image
Date
2021-01-01
Authors
Dureja, Rohit
Rozier, Kristin Yvonne
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Authors
Person
Rozier, Kristin Yvonne
Associate Professor
Research Projects
Organizational Units
Organizational Unit
Aerospace Engineering

The Department of Aerospace Engineering seeks to instruct the design, analysis, testing, and operation of vehicles which operate in air, water, or space, including studies of aerodynamics, structure mechanics, propulsion, and the like.

History
The Department of Aerospace Engineering was organized as the Department of Aeronautical Engineering in 1942. Its name was changed to the Department of Aerospace Engineering in 1961. In 1990, the department absorbed the Department of Engineering Science and Mechanics and became the Department of Aerospace Engineering and Engineering Mechanics. In 2003 the name was changed back to the Department of Aerospace Engineering.

Dates of Existence
1942-present

Historical Names

  • Department of Aerospace Engineering and Engineering Mechanics (1990-2003)

Related Units

Organizational Unit
Organizational Unit
Organizational Unit
Organizational Unit
Mathematics
Welcome to the exciting world of mathematics at Iowa State University. From cracking codes to modeling the spread of diseases, our program offers something for everyone. With a wide range of courses and research opportunities, you will have the chance to delve deep into the world of mathematics and discover your own unique talents and interests. Whether you dream of working for a top tech company, teaching at a prestigious university, or pursuing cutting-edge research, join us and discover the limitless potential of mathematics at Iowa State University!
Journal Issue
Is Version Of
Versions
Series
Department
Aerospace EngineeringComputer ScienceVirtual Reality Applications CenterElectrical and Computer EngineeringMathematics
Abstract

The design of safety-critical systems often requires design space exploration: comparing several system models that differ in terms of design choices, capabilities, and implementations. Model checking can compare different models in such a set, however, it is continuously challenged by the state space explosion problem. Therefore, learning and reusing information from solving related models becomes very important for future checking efforts. For example, reusing variable ordering in BDD-based model checking leads to substantial performance improvement. In this paper, we present a SAT-based algorithm for checking a set of models. Our algorithm, FuseIC3, extends IC3 to minimize time spent in exploring the common state space between related models. Specifically, FuseIC3 accumulates artifacts from the sequence of over-approximated reachable states, called frames, from earlier runs when checking new models, albeit, after careful repair. It uses bidirectional reachability; forward reachability to repair frames, and IC3-type backward reachability to block predecessors to bad states. We extensively evaluate FuseIC3 over a large collection of challenging benchmarks. FuseIC3 is on-average up to 5.48× (median 1.75×) faster than checking each model individually, and up to 3.67× (median 1.72×) faster than the state-of-the-art incremental IC3 algorithm. Moreover, we evaluate the performance improvement of FuseIC3 by smarter ordering of models and property grouping using a linear-time hashing approach.

Comments

This is a pre-print of the article Dureja, Rohit, and Kristin Yvonne Rozier. "Incremental design-space model checking via reusable reachable state approximations." (2021). Posted with permission.

Description
Keywords
Citation
DOI
Source
Copyright
Fri Jan 01 00:00:00 UTC 2021
Collections