SAT and SMT based model checking of concurrent systems (コンカレント工学)
スポンサーリンク
概要
- 論文の詳細を見る
We discuss model checking that uses a SAT (satisfiability) or SMT (satisfiability modulo theory) solver. The basic idea behind this model checking approach is to reduce the model checking problem to the satisfiability problem of a formula of some logic. Recent advances in SAT and SMT solvers make this particular approach significantly attractive. However, it does not work effectively in verification of concurrent systems, because the size of the formula blows up if the system has high concurrency. To overcome this challenge, we propose a new semantics for concurrent systems. The new semantics allows a compact formula representation of the behavior of concurrent systems. In this paper, we first introduce this new semantics and bounded model checking based on it, in the context of a general model of concurrent systems. Then we apply it to two specific concurrent system models, namely Petri nets and concurrent programs using unbounded integer variables.
- 社団法人電子情報通信学会の論文
- 2009-05-27
著者
-
TSUCHIYA Tatsuhiro
Graduate School of Information Science and Technology, Osaka University
-
KIKUNO Tohru
Graduate School of Information Science and Technology, Osaka University
-
Tsuchiya Tatsuhiro
Graduate School Of Information Science And Technology Osaka University
-
Kikuno Tohru
Graduate School Of Engineering Science Osaka University
関連論文
- Probabilistic Model Checking of the One-Dimensional Ising Model
- Constructing Overlay Networks with Short Paths and Low Communication Cost
- Feature Interaction Verification Using Unbounded Model Checking with Interpolation
- Prediction of Fault-Prone Software Modules Using a Generic Text Discriminator
- Probabilistic Model Checking of the One-Dimensional Ising Model
- An Effective Testing Method for Hardware Related Fault in Embedded Software(Software Engineering for Embedded Systems)
- Feature Interaction Detection by Bounded Model Checking(Dependable Communication)(Dependable Computing)
- Software Project Simulator for Effective Process Improvement (特集 〔情報処理学会〕創立40周年記念論文)
- Three-Mode Failure Model for Reliability Analysis of Distributed Programs (Special Issue on Fault-Tolerant Computing)
- Verifying Fault Tolerance of Concurrent Systems by Model Checking(Special Section on Concurrent System Technology and Its Application to Multiple Agent Systems)
- A Hierarchical Approach to Dependability Evaluation of Distributed Systems with Replicated Resources
- Computing the Stabilization Times of SElf-Stabilizing Systems (Special Section on Concurrent Systems Technology)
- New Constructions for Nondominated k-Coteries
- New System Model Based on Autonomous Decentralized System for Highly Productive Processing Equipment (IEICE/IEEE Joint Special Issue on Autonomous Decentralized Systems)
- Constructing a Bayesian Belief Network to Predict Final Quality in Embedded System Development(Software Engineering for Embedded Systems)
- Test Item Prioritizing Metrics for Selective Software Testing(Software Engineering)
- Enhancing Software Project Simulator toward Risk Prediction with Cost Estimation Capability(Special Section on Concurrent Systems Technology)
- Experimental Evaluation of Two-Phase Project Control for Software Development Process(Special Section on Concurrent Systems Technology)
- A New Verification Method Using Virtual System States for Responsive Communication Protocols and Its Application to a Broadcasting Protocol(Special Section on Concurrent Systems Technology)
- Timed Reachability Analysis Method for Communication Protocols Modeled by Extended Finite State Machines (Special Issue on Multimedia Communication and Distributed Processing)
- Experimental Evaluation of Processor Scheduling Algorithm for Parallel Logic Simulation Using Benchmark Circuits
- New 2-Factor Covering Designs for Software Testing(Regular Section)
- A BDD-based approach to reliability-optimal module allocation in networks (信頼性)
- SAT and SMT based model checking of concurrent systems (コンカレント工学)
- Parallelizing SDP(Sum of Disjoint Products)Algorithms for Fast Reliability Analysis
- An Energy-Efficient Broadcast Scheme for Multihop Wireless Ad Hoc Networks Using Variable-Range Transmission Power(Networks)
- Effective Scheduling of Duplicated Tasks for Fault Tolerance in Multiprocessor Systems
- Error Models and Fault-Secure Scheduling in Multiprocessor Systems
- Constructing Overlay Networks with Short Paths and Low Communication Cost
- A Distributed Routing Protocol for Finding Two Node-Disjoint Paths in Computer Networks (Special Issue on Distributed Processing for Controlling Telecommunications Systems)