In order to find the completeness threshold which offers a practical method of making bounded model checking complete, the over-approximation for the complete threshold is presented. First, a linear logic of knowledge...In order to find the completeness threshold which offers a practical method of making bounded model checking complete, the over-approximation for the complete threshold is presented. First, a linear logic of knowledge is introduced into the past tense operator, and then a new temporal epistemic logic LTLKP is obtained, so that LTLKP can naturally and precisely describe the system＇s reliability. Secondly, a set of prior algorithms are designed to calculate the maximal reachable depth and the length of the longest of loop free paths in the structure based on the graph structure theory. Finally, some theorems are proposed to show how to approximate the complete threshold with the diameter and recurrence diameter. The proposed work resolves the completeness threshold problem so that the completeness of bounded model checking can be guaranteed.展开更多
Bounded Model Checking has been recently introduced as an efficient verification method for reactive systems. This technique reduces model checking of linear temporal logic to propositional satisfiability. In this pap...Bounded Model Checking has been recently introduced as an efficient verification method for reactive systems. This technique reduces model checking of linear temporal logic to propositional satisfiability. In this paper we first present how quantified Boolean decision procedures can replace BDDs. We introduce a bounded model checking procedure for temporal logic CTL＊ which reduces model checking to the satisfiability of quantified Boolean formulas. Our new technique avoids the space blow up of BDDs, and extends the concept of bounded model checking.展开更多
SAT-based bounded model checking （BMC） has been introduced as a complementary technique to BDD-based symbolic model checking in recent years, and a lot of successful work has been done in this direction. The approac...SAT-based bounded model checking （BMC） has been introduced as a complementary technique to BDD-based symbolic model checking in recent years, and a lot of successful work has been done in this direction. The approach was first introduced by A. Biere et al. in checking linear temporal logic （LTL） formulae and then also adapted to check formulae of the universal fragment of computation tree logic （ACTL） by W. Penczek et al. As the efficiency of model checking is still an important issue, we present an improved BMC approach for ACTL based on Penczek＇s method. We consider two aspects of the approach. One is reduction of the number of variables and transitions in the κ-model by distinguishing the temporal operator EX from the others. The other is simplification of the transformation of formulae by using uniform path encoding instead of a disjunction of all paths needed in the κ-model. With these improvements, for an ACTL formula, the length of the final encoding of the formula in the worst case is reduced. The improved approach is implemented in the tool BMV and is compared with the original one by applying both to two well known examples, mutual exclusion and dining philosophers. The comparison shoves the advantages of the improved approach with respect to the efficiency of model checking.展开更多
The traditional system design method cannot guarantee the dependence of large-scale and complex real-time embedded software.The model constructed by UML and other semi-structured modeling languages does not support si...The traditional system design method cannot guarantee the dependence of large-scale and complex real-time embedded software.The model constructed by UML and other semi-structured modeling languages does not support simulation and verification,nor can it find requirements omission and logic contradiction.The Extended Hierarchical State transition Matrix model(EHSTM)which supports hierarchical modeling and concurrent States is proposed.The formal modeling of large-scale software system is simplified by model hierarchy.All relations between any two complex system concepts are clarified by hierarchical States and state parallelization,and the parallel behavior modeling of system is supported at the same time.After the model is constructed,it can be simulated and verified by a bounded model verification tool"GarakabuII".C source codes can be generated automatically after model checking and verification.In this way,system developers can focus only model design,which simplifies the system design process.Finally,a system design tool ZIPC based on EHSTM model is designed.Aiming at the problems of atomicity violation and data race in concurrent program development,ZIPC tool is used to construct the model,and the above problems can be effectively solved by experimental verification.展开更多
基金The National Natural Science Foundation of China (No.10974093)the Scientific Research Foundation for Senior Personnel of Jiangsu University (No.07JDG014)the Natural Science Foundation of Higher Education Institutions of Jiangsu Province (No.08KJD520015)
文摘In order to find the completeness threshold which offers a practical method of making bounded model checking complete, the over-approximation for the complete threshold is presented. First, a linear logic of knowledge is introduced into the past tense operator, and then a new temporal epistemic logic LTLKP is obtained, so that LTLKP can naturally and precisely describe the system＇s reliability. Secondly, a set of prior algorithms are designed to calculate the maximal reachable depth and the length of the longest of loop free paths in the structure based on the graph structure theory. Finally, some theorems are proposed to show how to approximate the complete threshold with the diameter and recurrence diameter. The proposed work resolves the completeness threshold problem so that the completeness of bounded model checking can be guaranteed.
文摘Bounded Model Checking has been recently introduced as an efficient verification method for reactive systems. This technique reduces model checking of linear temporal logic to propositional satisfiability. In this paper we first present how quantified Boolean decision procedures can replace BDDs. We introduce a bounded model checking procedure for temporal logic CTL＊ which reduces model checking to the satisfiability of quantified Boolean formulas. Our new technique avoids the space blow up of BDDs, and extends the concept of bounded model checking.
基金supported by the National Natural Science Foundation of China under Grants No.60573012 and No.60721061the National Basic Research 973 Program of China under Grant No.2002CB312200.
文摘SAT-based bounded model checking （BMC） has been introduced as a complementary technique to BDD-based symbolic model checking in recent years, and a lot of successful work has been done in this direction. The approach was first introduced by A. Biere et al. in checking linear temporal logic （LTL） formulae and then also adapted to check formulae of the universal fragment of computation tree logic （ACTL） by W. Penczek et al. As the efficiency of model checking is still an important issue, we present an improved BMC approach for ACTL based on Penczek＇s method. We consider two aspects of the approach. One is reduction of the number of variables and transitions in the κ-model by distinguishing the temporal operator EX from the others. The other is simplification of the transformation of formulae by using uniform path encoding instead of a disjunction of all paths needed in the κ-model. With these improvements, for an ACTL formula, the length of the final encoding of the formula in the worst case is reduced. The improved approach is implemented in the tool BMV and is compared with the original one by applying both to two well known examples, mutual exclusion and dining philosophers. The comparison shoves the advantages of the improved approach with respect to the efficiency of model checking.
文摘The traditional system design method cannot guarantee the dependence of large-scale and complex real-time embedded software.The model constructed by UML and other semi-structured modeling languages does not support simulation and verification,nor can it find requirements omission and logic contradiction.The Extended Hierarchical State transition Matrix model(EHSTM)which supports hierarchical modeling and concurrent States is proposed.The formal modeling of large-scale software system is simplified by model hierarchy.All relations between any two complex system concepts are clarified by hierarchical States and state parallelization,and the parallel behavior modeling of system is supported at the same time.After the model is constructed,it can be simulated and verified by a bounded model verification tool"GarakabuII".C source codes can be generated automatically after model checking and verification.In this way,system developers can focus only model design,which simplifies the system design process.Finally,a system design tool ZIPC based on EHSTM model is designed.Aiming at the problems of atomicity violation and data race in concurrent program development,ZIPC tool is used to construct the model,and the above problems can be effectively solved by experimental verification.
