Model Checking Games for the Quantitative μ-Calculus

We investigate quantitative extensions of modal logic and the modal μ-calculus, and study the question whether the tight connection between logic and games can be lifted from the qualitative logics to their quantitative counterparts. It turns out that, if the quantitative μ-calculus is defined in an appropriate way respecting the duality properties between the logical operators, then its model checking problem can indeed be characterised by a quantitative variant of parity games. However, these quantitative games have quite different properties than their classical counterparts, in particular they are, in general, not positionally determined. The correspondence between the logic and the games goes both ways: the value of a formula on a quantitative transition system coincides with the value of the associated quantitative game, and conversely, the values of quantitative parity games are definable in the quantitative μ-calculus.     

Predicate μ-Calculus for Mobile Ambients

Ambient logics have been proposed to describe properties for mobile agents which may evolve over time as well as space. This paper takes a predicate-based approach to extending an ambient logic with recursion, yielding a predicate μ-calculus in which fixpoint formulas are formed using predicate variables. An algorithm is developed for model checking finite-control mobile ambients against formulas of the logic, providing the first decidability result for model checking a spatial logic with recursion.     

A Graphical μ—Calculus and Local Model Checking

A graphical notation for the propositional μ-calculus,called modal graphs,is presented.It is shown that both the textual an equational presentations of the μ-calculus can be translated into modal graphs.A model checking algorithm based on such graphs is proposed.The algorithm is truly local in the sense that it only generates the parts of the underlying search space which are necessary for the computation of the final result.The correctness of the algorithm is proven and its complexity analysed.     

Debugging Smart Contract’s Business Logic Using Symbolic Model Checking

Programming and Computer Software - Smart contracts are a special type of programs running inside a blockchain. Immutable and transparent, they provide means to implement fault-tolerant and...     

Efficient Model Checking for Duration Calculus?

Duration Calculus (abbreviated to DC) is an interval-based, metric-time tempo-ral logic designed for reasoning about embedded real-time systems at a high level of abstrac-tion. But the complexity of model checking any decidable fragment featuring both negation and chop, DC’s only modality, is non-elementary and thus impractical. Even worse, when such decidable fragments are generalized just slightly to cover more interesting durational constraints the resulting fragments become undecidable. We here investigate a similar approximation as frequently employed in model checking situation-or point-based temporal logics, where linear-time problems are safely approximated by branching-time counterparts amenable to more e.cient model-checking algorithms. Mim-icking the role that a situation has in (A)CTL as the origin of a set of linear traces, we de.ne a branching-time counterpart to interval-based temporal logics building on situation pairs spanning sets of intervals. While this branching-time interval semantics yields the desired reduction in complexity of the model-checking problem, from undecidable to linear in the size of the formula and cubic in the size of the model, the approximation is too coarse to be practical. We therefore re.ne the semantics by an occurrence count for crucial states (e.g., cuts of loops) in the model, arriving at a 4-fold exponential model-checking problem su.ciently accurately approximating the original one. Furthermore, when chop occurs in negative polarity only in DC formulas, we have a doubly exponential model-checking algo-rithm.     

Model Checking Data Consistency for Cache Coherence Protocols

A method for automatic verification of cache coherence protocols is presented, in which cache coherence protocols are modeled as concurrent value-passing processes, and control and data consistency requirement are described as formulas in first-orderμ-calculus. A model checker is employed to check if the protocol under investigation satisfies the required properties. Using this method a data consistency error has been revealed in a well-known cache coherence protocol. The error has been corrected, and the revised protocol has been shown free from data consistency error for any data domain size, by appealing to data independence technique.     

Assumption–Commitment Support for CSP Model Checking

We present a simple formulation of Assumption–Commitment reasoning using CSP (Communicating Sequential Processes). An assumption–commitment style property of a process SYS takes the form $COM \sqsubseteq SYS \| ASS $ , for ‘assumption’ and ‘commitment’ processes ASS and COM. We describe proof rules that allow derivation of assumption–commitment style properties of a composite system from such properties of its components, given appropriate side conditions. Most of the rules have a superficially appealing ‘homomorphic’ quality: the overall assumption and commitment processes are composed similarly to the overall system. We also give a ‘non-homomorphic’ rule that corresponds quite well to classical assumption–commitment rules. Antecedants and side conditions can be expressed as refinements and checked separately by the refinement-style model checker FDR. Examples illustrate application of our theory.     

Remove Irrelevant Atomic Formulas for Timed Automaton Model Checking

Most of the timed automata reachability analysis algorithms in the literature explore the state spaces by enumeration of symbolic states, which use time constraints to represent a set of concrete states. A time constraint is a conjunction of atomic formulas which bound the differences of clock values. In this paper, it is shown that some atomic formulas of symbolic states generated by the algorithms can be removed to improve the model checking time- and space-efficiency. Such atomic formulas are called as irrelevant atomic formulas. A method is also presented to detect irrelevant formulas based on the test-reset information about clock variables. An optimized model-checking algorithm is designed based on these techniques. The case studies show that the techniques presented in this paper significantly improve the space- and time-efficiency of reachability analysis.     

基于Model Checking的系统脆弱性分析

基于规则的脆弱性分析技术依赖于对系统组件间关系的经验知识,系统复杂性、竞态条件、隐含假设等因素,使规则的生成异常困难。该文提出了采用NuSMV作为Model Checkjng执行机验证系统安全行为模型的脆弱性分析方法。并详细描述了对两个模型实例进行验证的过程。结果显示,这种方法具有识别已知和未知脆弱性的能力。     

Computing Bisimulations for Finite-Controlπ-Calculus

Symbolic bisimulation avoids the infinite branching problem caused by instantiating input names with all names in the standard definition of bisimulation in π-calculus.However,it does not automatically lead to an efficient algorithm,because symbolic bisimulation is indexed by conditions on names,and directly manipulating such conditions can be computationally costly.In this paper a new notion of bisimulation is introduced,in which the manipulation of maximally consistent conditions is replaced with a systematic employment of schematic names.It is shown that the new notion captures symbolic bisimulation in a precise sense.Based on the new definition an efficient algorithm,which instantiates input names “on-the -fly“,is presented to check bisimulations for finite-control π-calculus.     

Control of Non-Deterministic Systems With μ-Calculus Specifications Using Quotienting

The supervisory control problem for discrete event system(DES) under control involves identifying the supervisor, if one exists, which, when synchronously composed with the DES,results in a system that conforms to the control specification. In this context, we consider a non-deterministic DES under complete observation and control specification expressed in action-based propositional μ-calculus. The key to our solution is the process of quotienting the control specification against the plan resulting in a new μ-calculus formula such that a model for the formula is the supervisor. Thus the task of control synthesis is reduced a problem of μ-calculus satisfiability. In contrast to the existing μ-calculus quotienting-based techniques that are developed in deterministic setting, our quotienting rules can handle nondeterminism in the plant models. Another distinguishing feature of our technique is that while existing techniques use a separate μ-calculus formula to describe the controllability constraint(that uncontrollable events of plants are never disabled by a supervisor), we absorb this constraint as part of quotienting which allows us to directly capture more general state-dependent controllability constraints. Finally, we develop a tableau-based technique for verifying satisfiability of quotiented formula and model generation. The runtime for the technique is exponential in terms of the size of the plan and the control specification. A better complexity result that is polynomial to plant size and exponential to specification size is obtained when the controllability property is state-independent. A prototype implementation in a tabled logic programming language as well as some experimental results are presented.     

A Distributed Model of WebGIS Based on Java Servlett

According to the application of Java in Web Geographical Information System （WebGIS）, a model of WebGIS based on Java Servlet is defined and a new distributed model is proposed. The dislributed model relies on the implementation of distribt, tcd Servlet. And in the model a locator is adopted to manage client access to the Servlet and balance the loads of cluster Web servers. The programming rule of distributcd Servlet and the operating principle of locator are studied in detail. The model has been applied in a practical system, and the actual operating effect shows that it remarkably improves access performance of the WebGIS application and possesses characteristics of load balance, fail-over and so on.     

An Optimal Model and Algorithm of Distributed Information System

Distributed information system makes itself be placed in changing file storage position according to the users＇ request pattern. In this paper, we rebuild the model for a management system to turn the process of file managing into a 0-1 programming problem, and present a new individual form to improve the operating efficiency. Aiming at the model, we define a neighborhood span to make segmentation for searching space by using the fitness, based on the region contraction algorithm, present a new evolution algorithm which has the capability of self-adaptively generating new individuals, and ultimately solve the management problem of the distributed file system.     

On the Formalization of the Modal μ-Calculus in the Calculus of Inductive Constructions

We present a natural deduction proof system for the propositional modal μ-calculus and its formalization in the calculus of inductive constructions. We address several problematic issues, such as the use of higher-order abstract syntax in inductive sets in the presence of recursive constructors, and the formalization of modal (sequent-style) rules and of context sensitive grammars. The formalization can be used in the system Coq, providing an experimental computer-aided proof environment for the interactive development of error-free proofs in the modal μ-calculus. The techniques we adopt can be readily ported to other languages and proof systems featuring similar problematic issues.     

Model and Algorithm of Backward Error Recovery of Distributed Software

Backward error recovery is one of the important techniques of software fault tolerance. Because of error propagation its recovery in distributed software needs cooperation between processes to achieve consistent recovery. However, the techniques of the achievement suffer from either concurrency level decreasing or the domino effect. Based on a formal model of the distributhed system, a backward recovery protocol without the two drawbacks is specified in this paper. The algorithm of the protocol is Woven strictly and its implementation is proposed.     

A Commit Strategy for Distributed Real-Time Transaction

Ramamritham gives three common types of constraints for the execution his-tory of concurrent transactions. This paper extends the constraints and gives the fourth type of constraint. Then the weak commit dependency and abort dependency between transactions, be-cause of data access conflicts, axe analyzed. Based on the analysis, an optimistic commit protocol 2LC (two-Level Commit) is proposed, which is specially designed for the distributed real-time do-main. It allows transactions to optimistically access the locked data in a controlled manner, which reduces the data inaccessibility and priority inversion inherent and undesirable in distributed real-time database systems. Furthermore, if the prepared transaction is aborted, the transactions in its weak commit dependency set will execute as normal according to 2LC. Extensive simulation ex-periments have been performed to compare the performance of 2LC with that of the base protocol,the permits reading of modified prepared-data for timeliness (PROMPT) and the deadline-driven conflict resolution (DDCR). The simulation results show that 2LC is effective in reducing the num-ber of missed transaction deadlines. Furthermore, it is easy to be incorporated with the existing concurrency control protocols.     

Distributed Integrated Information System for Product Design

A new approach to construct Distributed Integrated Information System for product design(DIIS) is presented. Design knowledge of parts and products is expressed in STEP form, it is neutral and independent to commercial CAD platforms. After compiling by STEP Developer and being pre/post processed, the binary codes of data dictionary model can be sent into the end user's design platform directly and readily supports the product design.     

A Recovery Technique for Distributed Communicating Process Systems

This paper presents a recovery technique for distributed communicating processsystems.It handles both hardware faults and software faults uniformly.Differing fromother recovery techniques,it brings an extremely small amount of execution overheadto nonfailing processes and can be implemented easily.It can be applied to aprogramming procedure to mask the software design errors or imbeded into anoperating system to enhance the reliability of the whole system.The theoretical workis carried out first,then the implementation problems are considered and theevaluation techniques are discussed last.