Model checking is an automated formal verification method to verify whether epistemic multi-agent systems adhere to property specifications.Although there is an extensive literature on qualitative properties such as s...Model checking is an automated formal verification method to verify whether epistemic multi-agent systems adhere to property specifications.Although there is an extensive literature on qualitative properties such as safety and liveness,there is still a lack of quantitative and uncertain property verifications for these systems.In uncertain environments,agents must make judicious decisions based on subjective epistemic.To verify epistemic and measurable properties in multi-agent systems,this paper extends fuzzy computation tree logic by introducing epistemic modalities and proposing a new Fuzzy Computation Tree Logic of Knowledge(FCTLK).We represent fuzzy multi-agent systems as distributed knowledge bases with fuzzy epistemic interpreted systems.In addition,we provide a transformation algorithm from fuzzy epistemic interpreted systems to fuzzy Kripke structures,as well as transformation rules from FCTLK formulas to Fuzzy Computation Tree Logic(FCTL)formulas.Accordingly,we transform the FCTLK model checking problem into the FCTL model checking.This enables the verification of FCTLK formulas by using the fuzzy model checking algorithm of FCTL without additional computational overheads.Finally,we present correctness proofs and complexity analyses of the proposed algorithms.Additionally,we further illustrate the practical application of our approach through an example of a train control system.展开更多
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.展开更多
Model checking based on linear temporal logic reduces the false negative rate of misuse detection.However,linear temporal logic formulae cannot be used to describe concurrent attacks and piecewise attacks.So there is ...Model checking based on linear temporal logic reduces the false negative rate of misuse detection.However,linear temporal logic formulae cannot be used to describe concurrent attacks and piecewise attacks.So there is still a high rate of false negatives in detecting these complex attack patterns.To solve this problem,we use interval temporal logic formulae to describe concurrent attacks and piecewise attacks.On this basis,we formalize a novel algorithm for intrusion detection based on model checking interval temporal logic.Compared with the method based on model checking linear temporal logic,the new algorithm can find unknown succinct attacks.The simulation results show that the new method can effectively reduce the false negative rate of concurrent attacks and piecewise attacks.展开更多
A formal model representing the navigation behavior of a Web application as the Kripke structure is proposed and an approach that applies model checking to test case generation is presented. The Object Relation Diagra...A formal model representing the navigation behavior of a Web application as the Kripke structure is proposed and an approach that applies model checking to test case generation is presented. The Object Relation Diagram as the object model is employed to describe the object structure of a Web application design and can be translated into the behavior model. A key problem of model checking-based test generation for a Web application is how to construct a set of trap properties that intend to cause the violations of model checking against the behavior model and output of counterexamples used to construct the test sequences. We give an algorithm that derives trap properties from the object model with respect to node and edge coverage criteria.展开更多
The soundness is a very important criterion for the correctness of the workflow. Specifying the soundness with Computation Tree Logic （CTL） allows us to verify the soundness with symbolic model checkers. Therefore t...The soundness is a very important criterion for the correctness of the workflow. Specifying the soundness with Computation Tree Logic （CTL） allows us to verify the soundness with symbolic model checkers. Therefore the state explosion problem in verifying soundness can be overcome efficiently. When the property is not satisfied by the system, model checking can give a counter-example, which can guide us to correct the workflow. In addition, relaxed soundness is another important criterion for the workflow. We also prove that Computation Tree Logic ＊ （CTL ＊ ） can be used to character the relaxed soundness of the workflow.展开更多
Product detection based on state abstraction technologies in the software product line(SPL)is more complex when compared to a single system.This variability constitutes a new complexity,and the counterexample may be v...Product detection based on state abstraction technologies in the software product line(SPL)is more complex when compared to a single system.This variability constitutes a new complexity,and the counterexample may be valid for some products but spurious for others.In this paper,we found that spurious products are primarily due to the failure states,which correspond to the spurious counterexamples.The violated products correspond to the real counterexamples.Hence,identifying counterexamples is a critical problem in detecting violated products.In our approach,we obtain the violated products through the genuine counterexamples,which have no failure state,to avoid the tedious computation of identifying spurious products dealt with by the existing algorithm.This can be executed in parallel to improve the efficiency further.Experimental results showthat our approach performswell,varying with the growth of the system scale.By analyzing counterexamples in the abstract model,we observed that spurious products occur in the failure state.The approach helps in identifying whether a counterexample is spurious or genuine.The approach also helps to check whether a failure state exists in the counterexample.The performance evaluation shows that the proposed approach helps significantly in improving the efficiency of abstraction-based SPL model checking.展开更多
Graph transformation systems have become a general formal modeling language to describe many models in software development process.Behavioral modeling of dynamic systems and model-to-model transformations are only a ...Graph transformation systems have become a general formal modeling language to describe many models in software development process.Behavioral modeling of dynamic systems and model-to-model transformations are only a few examples in which graphs have been used to software development.But even the perfect graph transformation system must be equipped with automated analysis capabilities to let users understand whether such a formal specification fulfills their requirements.In this paper,we present a new solution to verify graph transformation systems using the Bogor model checker.The attributed graph grammars(AGG)-like graph transformation systems are translated to Bandera intermediate representation(BIR),the input language of Bogor,and Bogor verifies the model against some interesting properties defined by combining linear temporal logic(LTL) and special-purpose graph rules.Experimental results are encouraging,showing that in most cases our solution improves existing approaches in terms of both performance and expressiveness.展开更多
This study focuses on automatic searching and verifying methods for the teachability, transition logics and hierarchical structure in all possible paths of biological processes using model checking. The automatic sear...This study focuses on automatic searching and verifying methods for the teachability, transition logics and hierarchical structure in all possible paths of biological processes using model checking. The automatic search and verification for alternative paths within complex and large networks in biological process can provide a considerable amount of solutions, which is difficult to handle manually. Model checking is an automatic method for verifying if a circuit or a condition, expressed as a concurrent transition system, satisfies a set of properties expressed in a temporal logic, such as computational tree logic （CTL）. This article represents that model checking is feasible in biochemical network verification and it shows certain advantages over simulation for querying and searching of special behavioral properties in biochemical processes.展开更多
Web-services are highly distributed programs, and concurrent software is notoriously error-prone. Model checking is a powerful technique to find bugs in concurrent systems. However, the existing model checkers have no...Web-services are highly distributed programs, and concurrent software is notoriously error-prone. Model checking is a powerful technique to find bugs in concurrent systems. However, the existing model checkers have no enough ability to support for the programming languages and communication mechanisms used for Web services. We propose to use Kripke structures as means of modeling Web service. This paper presents an automated way to extract formal models from programs implementing Web services using predicate abstraction for abstract model checking. The abstract models are checked by means of a model checker that implements automatic abstraction refinement. These results enable the verification of the applications that implement Web services.展开更多
Model checking techniques have been widely used in verifying web service compositions to ensure the trustworthi- ness. However, little research has focused on testing web services. Based on the research of model check...Model checking techniques have been widely used in verifying web service compositions to ensure the trustworthi- ness. However, little research has focused on testing web services. Based on the research of model checking techniques~ we propose a model checking based approach for testing web service composition which is described by using the web services choreography description language （WS-CDL）. According to worldwide web consortium （W3C） candidate recommendation, the WS-CDL specification provides a language for characterizing interactions between distinct web services using XML. Since the behaviors of web service composition are asynchronous, distributed, low-coupled and platform independent, we employ the guarded automata （GA） model for specifying the composition described in WS-CDL and using the simple promela interpreter （SPIN） model checker for detecting the collaborations of web services. Test cases can be transformed from counterexamples generated by SPIN using adequacy criteria. In this paper we apply the transition coverage criterion for generating counterex- amples. To illustrate our approach, we set ＂E-commerce service system＂ as an example for demonstrating how test cases can be generated using SPIN for compositions specified in WS-CDL.展开更多
Classical logic cannot be used to effectively reason about concurrent systems with inconsistencies (inconsistencies often occur, especially in the early stage of the development, when large and complex concurrent syst...Classical logic cannot be used to effectively reason about concurrent systems with inconsistencies (inconsistencies often occur, especially in the early stage of the development, when large and complex concurrent systems are developed). In this paper, we propose the use of a guasi-classical temporal logic (QCTL) for supporting the verification of temporal properties of such systems even where the consistent model is not available. Our models are paraKripke structures (extended standard Kripke structures), in which both a formula and its negation are satisfied in a same state, and properties to be verified are expressed by QCTL with paraKripke structures semantics. We introduce a novel notion of paraKripke models, which grasps the paraconsistent character of the entailment relation of QCTL. Furthermore, we explore the methodology of model checking over QCTL, and describe the detailed algorithm of implementing QCTL model checker. In the sequel, a simple example is presented, showing how to exploit the proposed model checking technique to verify the temporal properties of inconsistent concurrent systems.展开更多
Web service （WS） is an emerging software technology, especially acting an important role in cloud computing. The WS choreography description language （WS-CDL） is the standard for modeling the observable behavior o...Web service （WS） is an emerging software technology, especially acting an important role in cloud computing. The WS choreography description language （WS-CDL） is the standard for modeling the observable behavior of WS composition across multiple participants from a global point of view. However, it lacks of a formal semantics and could easily lead to misunderstanding and different implementations. In this paper, the WS-CDL based specifications are formally extracted in a communicating sequential process supporting a formal approach to checking WS models. In addition, formalisms and model checking are explicitly illustrated through a simple but non-trivial example with the help of model checker process analysis toolkit （PAT）.展开更多
Recurrent neural networks (RNNs) have been heavily used in applications relying on sequence data such as time series and natural languages. As a matter of fact, their behaviors lack rigorous quality assurance due to t...Recurrent neural networks (RNNs) have been heavily used in applications relying on sequence data such as time series and natural languages. As a matter of fact, their behaviors lack rigorous quality assurance due to the black-box nature of deep learning. It is an urgent and challenging task to formally reason about the behaviors of RNNs. To this end, we first present an extension of linear-time temporal logic to reason about properties with respect to RNNs, such as local robustness, reachability, and some temporal properties. Based on the proposed logic, we formalize the verification obligation as a Hoare-like triple, from both qualitative and quantitative perspectives. The former concerns whether all the outputs resulting from the inputs fulfilling the pre-condition satisfy the post-condition, whereas the latter is to compute the probability that the post-condition is satisfied on the premise that the inputs fulfill the pre-condition. To tackle these problems, we develop a systematic verification framework, mainly based on polyhedron propagation, dimension-preserving abstraction, and the Monte Carlo sampling. We also implement our algorithm with a prototype tool and conduct experiments to demonstrate its feasibility and efficiency.展开更多
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.展开更多
Neural networks, as an important computing model, have a wide application in artificial intelligence (AI) domain. From the perspective of computer science, such a computing model requires a formal description of its b...Neural networks, as an important computing model, have a wide application in artificial intelligence (AI) domain. From the perspective of computer science, such a computing model requires a formal description of its behaviors, particularly the relation between input and output. In addition, such specifications ought to be verified automatically. ReLU (rectified linear unit) neural networks are intensively used in practice. In this paper, we present ReLU Temporal Logic (ReTL), whose semantics is defined with respect to ReLU neural networks, which could specify value-related properties about the network. We show that the model checking algorithm for theΣ2∪Π2 fragment of ReTL, which can express properties such as output reachability, is decidable in EXPSPACE. We have also implemented our algorithm with a prototype tool, and experimental results demonstrate the feasibility of the presented model checking approach.展开更多
In this paper, model checking problem is considered for general linear model when covariables are measured with error and an independent validation data set is available, Without assuming any error model structure bet...In this paper, model checking problem is considered for general linear model when covariables are measured with error and an independent validation data set is available, Without assuming any error model structure between the true variable and the surrogate variable, the author first apply nonparametric method to model the relationship between the true variable and the surrogate variable with the help of the validation sample. Then the author construct a score-type test statistic through model adjustment. The large sample behaviors of the score-type test statistic are investigated. It is shown that the test is consistent and can detect the alternative hypothesis close to the null hypothesis at the rate n^-r with 0 ≤ r ≤1/2. Simulation results indicate that the proposed method works well. Key words General linear model, measurement error, model checking, validation data.展开更多
Recent development on distributed systems has shown that a variety of fairness constraints （some of which are only recently defined） play vital roles in designing self- stabilizing population protocols. Existing mod...Recent development on distributed systems has shown that a variety of fairness constraints （some of which are only recently defined） play vital roles in designing self- stabilizing population protocols. Existing model checkers are deficient in verifying the systems as only limited kinds of fair- ness are supported with limited verification efficiency. In this work, we support model checking of distributed systems in the toolkit PAT （process analysis toolkit）, with a variety of fairness constraints （e.g., process-level weak/strong fairness, event-level weak/strong fairness, strong global fairness）. It performs on-the-fly verification against linear temporal prop- erties. We show through empirical evaluation （on recent pop- ulation protocols as well as benchmark systems） that PAT has advantage in model checking with fairness. Previously un- known bugs have been revealed against systems which are designed to function only with strong global fairness.展开更多
Stochastic model checking is a recent extension and generalization of the classical model checking, which focuses on quantitatively checking the temporal property of a system model. PCTL＊ is one of the important quan...Stochastic model checking is a recent extension and generalization of the classical model checking, which focuses on quantitatively checking the temporal property of a system model. PCTL＊ is one of the important quantitative property specification languages, which is strictly more expressive than either PCTL （probabilistic computation tree logic） or LTL （linear temporal logic） with probability bounds. At present, PCTL＊ stochastic model checking algorithm is very complicated, and cannot provide any relevant explanation of why a formula does or does not hold in a given model. For dealing with this problem, an intuitive and succinct approach for PCTL＊ stochastic model checking with evidence is put forward in this paper, which includes： presenting the game semantics for PCTL＊ in release-PNF （release-positive normal form）, defining the PCTL＊ stochastic model checking game, using strategy solving in game to achieve the PCTL＊ stochastic model checking, and refining winning strategy as the evidence to certify stochastic model checking result. The soundness and the completeness of game-based PCTL＊ stochastic model checking are proved, and its complexity matches the known lower and upper bounds. The game-based PCTL＊ stochastic model checking algorithm is implemented in a visual prototype tool, and its feasibility is demonstrated by an illustrative example.展开更多
The state space explosion problem is still the key obstacle for applying model checking to systems of industrial size. Abstraction-based methods have been particularly successful in this regard. This paper presents an...The state space explosion problem is still the key obstacle for applying model checking to systems of industrial size. Abstraction-based methods have been particularly successful in this regard. This paper presents an approach based on refinement of search space partition and abstraction which combines these two techniques for reducing the complexity of model checking. The refinement depends on the representation of each portion of search space. Especially, search space can be refined stepwise to get a better reduction. As reported in the case study, the integration of search space partition and abstraction improves the efficiency of verification with respect to the requirement of memory and obtains significant advantage over the use of each of them in isolation.展开更多
基金The work is partially supported by Natural Science Foundation of Ningxia(Grant No.AAC03300)National Natural Science Foundation of China(Grant No.61962001)Graduate Innovation Project of North Minzu University(Grant No.YCX23152).
文摘Model checking is an automated formal verification method to verify whether epistemic multi-agent systems adhere to property specifications.Although there is an extensive literature on qualitative properties such as safety and liveness,there is still a lack of quantitative and uncertain property verifications for these systems.In uncertain environments,agents must make judicious decisions based on subjective epistemic.To verify epistemic and measurable properties in multi-agent systems,this paper extends fuzzy computation tree logic by introducing epistemic modalities and proposing a new Fuzzy Computation Tree Logic of Knowledge(FCTLK).We represent fuzzy multi-agent systems as distributed knowledge bases with fuzzy epistemic interpreted systems.In addition,we provide a transformation algorithm from fuzzy epistemic interpreted systems to fuzzy Kripke structures,as well as transformation rules from FCTLK formulas to Fuzzy Computation Tree Logic(FCTL)formulas.Accordingly,we transform the FCTLK model checking problem into the FCTL model checking.This enables the verification of FCTLK formulas by using the fuzzy model checking algorithm of FCTL without additional computational overheads.Finally,we present correctness proofs and complexity analyses of the proposed algorithms.Additionally,we further illustrate the practical application of our approach through an example of a train control system.
基金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.
基金supported by National Natural Science Foundation of China under Grant No. 61003079
文摘Model checking based on linear temporal logic reduces the false negative rate of misuse detection.However,linear temporal logic formulae cannot be used to describe concurrent attacks and piecewise attacks.So there is still a high rate of false negatives in detecting these complex attack patterns.To solve this problem,we use interval temporal logic formulae to describe concurrent attacks and piecewise attacks.On this basis,we formalize a novel algorithm for intrusion detection based on model checking interval temporal logic.Compared with the method based on model checking linear temporal logic,the new algorithm can find unknown succinct attacks.The simulation results show that the new method can effectively reduce the false negative rate of concurrent attacks and piecewise attacks.
基金Supported by the National Natural Science Foundation of China (60673115)the National Basic Research Program of China (973 Program) (2002CB312001)the Open Foundation of State Key Laboratory of Soft-ware Engineering (SKLSE05-13)
文摘A formal model representing the navigation behavior of a Web application as the Kripke structure is proposed and an approach that applies model checking to test case generation is presented. The Object Relation Diagram as the object model is employed to describe the object structure of a Web application design and can be translated into the behavior model. A key problem of model checking-based test generation for a Web application is how to construct a set of trap properties that intend to cause the violations of model checking against the behavior model and output of counterexamples used to construct the test sequences. We give an algorithm that derives trap properties from the object model with respect to node and edge coverage criteria.
基金Supported by the National Natural Science Foun-dation of China (60573046)
文摘The soundness is a very important criterion for the correctness of the workflow. Specifying the soundness with Computation Tree Logic （CTL） allows us to verify the soundness with symbolic model checkers. Therefore the state explosion problem in verifying soundness can be overcome efficiently. When the property is not satisfied by the system, model checking can give a counter-example, which can guide us to correct the workflow. In addition, relaxed soundness is another important criterion for the workflow. We also prove that Computation Tree Logic ＊ （CTL ＊ ） can be used to character the relaxed soundness of the workflow.
基金supported by the Fund of ExcellentYouth Scientific and Technological Innovation Team of Hubei’s Universities(Project No:T201818)Science and Technology Research Program of Hubei Provincial Education Department(Project No:Q20143005)Guiding project of scientific research plan of Hubei Provincial Department of Education(Project No:B2021261).
文摘Product detection based on state abstraction technologies in the software product line(SPL)is more complex when compared to a single system.This variability constitutes a new complexity,and the counterexample may be valid for some products but spurious for others.In this paper,we found that spurious products are primarily due to the failure states,which correspond to the spurious counterexamples.The violated products correspond to the real counterexamples.Hence,identifying counterexamples is a critical problem in detecting violated products.In our approach,we obtain the violated products through the genuine counterexamples,which have no failure state,to avoid the tedious computation of identifying spurious products dealt with by the existing algorithm.This can be executed in parallel to improve the efficiency further.Experimental results showthat our approach performswell,varying with the growth of the system scale.By analyzing counterexamples in the abstract model,we observed that spurious products occur in the failure state.The approach helps in identifying whether a counterexample is spurious or genuine.The approach also helps to check whether a failure state exists in the counterexample.The performance evaluation shows that the proposed approach helps significantly in improving the efficiency of abstraction-based SPL model checking.
文摘Graph transformation systems have become a general formal modeling language to describe many models in software development process.Behavioral modeling of dynamic systems and model-to-model transformations are only a few examples in which graphs have been used to software development.But even the perfect graph transformation system must be equipped with automated analysis capabilities to let users understand whether such a formal specification fulfills their requirements.In this paper,we present a new solution to verify graph transformation systems using the Bogor model checker.The attributed graph grammars(AGG)-like graph transformation systems are translated to Bandera intermediate representation(BIR),the input language of Bogor,and Bogor verifies the model against some interesting properties defined by combining linear temporal logic(LTL) and special-purpose graph rules.Experimental results are encouraging,showing that in most cases our solution improves existing approaches in terms of both performance and expressiveness.
文摘This study focuses on automatic searching and verifying methods for the teachability, transition logics and hierarchical structure in all possible paths of biological processes using model checking. The automatic search and verification for alternative paths within complex and large networks in biological process can provide a considerable amount of solutions, which is difficult to handle manually. Model checking is an automatic method for verifying if a circuit or a condition, expressed as a concurrent transition system, satisfies a set of properties expressed in a temporal logic, such as computational tree logic （CTL）. This article represents that model checking is feasible in biochemical network verification and it shows certain advantages over simulation for querying and searching of special behavioral properties in biochemical processes.
基金the National Natural Science Foundation of China (60663005, 60563005)the Natural Science Foundation of Guangxi Province (0542036, 0728093, 0728089)
文摘Web-services are highly distributed programs, and concurrent software is notoriously error-prone. Model checking is a powerful technique to find bugs in concurrent systems. However, the existing model checkers have no enough ability to support for the programming languages and communication mechanisms used for Web services. We propose to use Kripke structures as means of modeling Web service. This paper presents an automated way to extract formal models from programs implementing Web services using predicate abstraction for abstract model checking. The abstract models are checked by means of a model checker that implements automatic abstraction refinement. These results enable the verification of the applications that implement Web services.
基金Project supported by the Open Foundation of State Key Laboratory of Software Engineering(Grant No.SKLSE20080712)the National Natural Science Foundation of China(Grant No.60970007)+2 种基金the National Basic Research Program of China(Grant No.2007CB310800)the Shanghai Leading Academic Discipline Project(Grant No.J50103)the Science and Technology Commission of Shanghai Municipality(Grant No.09DZ2272600)
文摘Model checking techniques have been widely used in verifying web service compositions to ensure the trustworthi- ness. However, little research has focused on testing web services. Based on the research of model checking techniques~ we propose a model checking based approach for testing web service composition which is described by using the web services choreography description language （WS-CDL）. According to worldwide web consortium （W3C） candidate recommendation, the WS-CDL specification provides a language for characterizing interactions between distinct web services using XML. Since the behaviors of web service composition are asynchronous, distributed, low-coupled and platform independent, we employ the guarded automata （GA） model for specifying the composition described in WS-CDL and using the simple promela interpreter （SPIN） model checker for detecting the collaborations of web services. Test cases can be transformed from counterexamples generated by SPIN using adequacy criteria. In this paper we apply the transition coverage criterion for generating counterex- amples. To illustrate our approach, we set ＂E-commerce service system＂ as an example for demonstrating how test cases can be generated using SPIN for compositions specified in WS-CDL.
基金Supported by the National Natural Science Foundation of China (No.60603036)the Jiangsu Province Research Foundation (No.BK2007139)
文摘Classical logic cannot be used to effectively reason about concurrent systems with inconsistencies (inconsistencies often occur, especially in the early stage of the development, when large and complex concurrent systems are developed). In this paper, we propose the use of a guasi-classical temporal logic (QCTL) for supporting the verification of temporal properties of such systems even where the consistent model is not available. Our models are paraKripke structures (extended standard Kripke structures), in which both a formula and its negation are satisfied in a same state, and properties to be verified are expressed by QCTL with paraKripke structures semantics. We introduce a novel notion of paraKripke models, which grasps the paraconsistent character of the entailment relation of QCTL. Furthermore, we explore the methodology of model checking over QCTL, and describe the detailed algorithm of implementing QCTL model checker. In the sequel, a simple example is presented, showing how to exploit the proposed model checking technique to verify the temporal properties of inconsistent concurrent systems.
基金supported by the Shanghai Leading Academic Discipline Project (Grant No.J50103)
文摘Web service （WS） is an emerging software technology, especially acting an important role in cloud computing. The WS choreography description language （WS-CDL） is the standard for modeling the observable behavior of WS composition across multiple participants from a global point of view. However, it lacks of a formal semantics and could easily lead to misunderstanding and different implementations. In this paper, the WS-CDL based specifications are formally extracted in a communicating sequential process supporting a formal approach to checking WS models. In addition, formalisms and model checking are explicitly illustrated through a simple but non-trivial example with the help of model checker process analysis toolkit （PAT）.
基金supported by the National Natural Science Foundation of China under Grant Nos.61872371,62032024,and U19A2062the Open Fund from the State Key Laboratory of High Performance Computing of China(HPCL)under Grant No.202001-07.
文摘Recurrent neural networks (RNNs) have been heavily used in applications relying on sequence data such as time series and natural languages. As a matter of fact, their behaviors lack rigorous quality assurance due to the black-box nature of deep learning. It is an urgent and challenging task to formally reason about the behaviors of RNNs. To this end, we first present an extension of linear-time temporal logic to reason about properties with respect to RNNs, such as local robustness, reachability, and some temporal properties. Based on the proposed logic, we formalize the verification obligation as a Hoare-like triple, from both qualitative and quantitative perspectives. The former concerns whether all the outputs resulting from the inputs fulfilling the pre-condition satisfy the post-condition, whereas the latter is to compute the probability that the post-condition is satisfied on the premise that the inputs fulfill the pre-condition. To tackle these problems, we develop a systematic verification framework, mainly based on polyhedron propagation, dimension-preserving abstraction, and the Monte Carlo sampling. We also implement our algorithm with a prototype tool and conduct experiments to demonstrate its feasibility and efficiency.
文摘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.
基金This work is supported by the National Natural Science Foundation of China under Grant No.61872371the Open Fund from the State Key Laboratory of High Performance Computing of China(HPCL)under Grant No.202001-07the Natural Key Research and Development Program of China under Grant No.2018YFB0204301.
文摘Neural networks, as an important computing model, have a wide application in artificial intelligence (AI) domain. From the perspective of computer science, such a computing model requires a formal description of its behaviors, particularly the relation between input and output. In addition, such specifications ought to be verified automatically. ReLU (rectified linear unit) neural networks are intensively used in practice. In this paper, we present ReLU Temporal Logic (ReTL), whose semantics is defined with respect to ReLU neural networks, which could specify value-related properties about the network. We show that the model checking algorithm for theΣ2∪Π2 fragment of ReTL, which can express properties such as output reachability, is decidable in EXPSPACE. We have also implemented our algorithm with a prototype tool, and experimental results demonstrate the feasibility of the presented model checking approach.
基金This research is supported by the National Natural Science Foundation of China （10901162, 10926073）, the President Fund of GUCAS and China Postdoctoral Science Foundation.
文摘In this paper, model checking problem is considered for general linear model when covariables are measured with error and an independent validation data set is available, Without assuming any error model structure between the true variable and the surrogate variable, the author first apply nonparametric method to model the relationship between the true variable and the surrogate variable with the help of the validation sample. Then the author construct a score-type test statistic through model adjustment. The large sample behaviors of the score-type test statistic are investigated. It is shown that the test is consistent and can detect the alternative hypothesis close to the null hypothesis at the rate n^-r with 0 ≤ r ≤1/2. Simulation results indicate that the proposed method works well. Key words General linear model, measurement error, model checking, validation data.
文摘Recent development on distributed systems has shown that a variety of fairness constraints （some of which are only recently defined） play vital roles in designing self- stabilizing population protocols. Existing model checkers are deficient in verifying the systems as only limited kinds of fair- ness are supported with limited verification efficiency. In this work, we support model checking of distributed systems in the toolkit PAT （process analysis toolkit）, with a variety of fairness constraints （e.g., process-level weak/strong fairness, event-level weak/strong fairness, strong global fairness）. It performs on-the-fly verification against linear temporal prop- erties. We show through empirical evaluation （on recent pop- ulation protocols as well as benchmark systems） that PAT has advantage in model checking with fairness. Previously un- known bugs have been revealed against systems which are designed to function only with strong global fairness.
基金The work was supported by the National Natural Science Foundation of China under Grant Nos. 61303022 and 61472179, the China Postdoctoral Science Foundation under Grant No. 2013M531328, the Natural Science Foundation of Shandong Province of China under Grant No. ZR2012FQ013, the Project of Shandong Province Higher Educational Science and Technology Program under Grant No. J13LN10, and the Science and Technology Program of Taian of China under Grant No. 201330629. This work was partially supported by Jiangsu Collaborative Innovation Center of Novel Software Technology and Industrialization of China.
文摘Stochastic model checking is a recent extension and generalization of the classical model checking, which focuses on quantitatively checking the temporal property of a system model. PCTL＊ is one of the important quantitative property specification languages, which is strictly more expressive than either PCTL （probabilistic computation tree logic） or LTL （linear temporal logic） with probability bounds. At present, PCTL＊ stochastic model checking algorithm is very complicated, and cannot provide any relevant explanation of why a formula does or does not hold in a given model. For dealing with this problem, an intuitive and succinct approach for PCTL＊ stochastic model checking with evidence is put forward in this paper, which includes： presenting the game semantics for PCTL＊ in release-PNF （release-positive normal form）, defining the PCTL＊ stochastic model checking game, using strategy solving in game to achieve the PCTL＊ stochastic model checking, and refining winning strategy as the evidence to certify stochastic model checking result. The soundness and the completeness of game-based PCTL＊ stochastic model checking are proved, and its complexity matches the known lower and upper bounds. The game-based PCTL＊ stochastic model checking algorithm is implemented in a visual prototype tool, and its feasibility is demonstrated by an illustrative example.
基金Supported by the National Natural Science Foundation of China (Grant Nos. 60573012 and 60421001) the National Grand FundamentalResearch 973 Program of China (Grant No. 2002cb312200)
文摘The state space explosion problem is still the key obstacle for applying model checking to systems of industrial size. Abstraction-based methods have been particularly successful in this regard. This paper presents an approach based on refinement of search space partition and abstraction which combines these two techniques for reducing the complexity of model checking. The refinement depends on the representation of each portion of search space. Especially, search space can be refined stepwise to get a better reduction. As reported in the case study, the integration of search space partition and abstraction improves the efficiency of verification with respect to the requirement of memory and obtains significant advantage over the use of each of them in isolation.
