Using heuristic search for finding deadlocks in concurrent systems

Model checking is a formal technique for proving the correctness of a system with respect to a desired behavior. This is accomplished by checking whether a structure representing the system (typically a labeled transition system) satisfies a temporal logic formula describing the expected behavior. Model checking has a number of advantages over traditional approaches that are based on simulation and testing: it is completely automatic and when the verification fails it returns a counterexample that can be used to pinpoint the source of the error. Nevertheless, model checking techniques often fail because of the state explosion problem: transition systems grow exponentially with the number of components. The aim of this paper is to attack the state explosion problem that may arise when looking for deadlocks in concurrent systems described through the calculus of communicating systems. We propose to use heuristics-based techniques, namely the A* algorithm, both to guide the search without constructing the complete transition system, and to provide minimal counterexamples. We have realized a prototype tool to evaluate the methodology. Experiments we have conducted on processes of different size show the benefit from using our technique against building the whole state space, or applying some other methods.     

Behaviour Analysis of Distributed Systems Using the Tracta Approach

Behaviour analysis should form an integral part of the software development process. This is particularly important in the design of concurrent and distributed systems, where complex interactions can cause unexpected and undesired system behaviour. We advocate the use of a compositional approach to analysis. The software architecture of a distributed program is represented by a hierarchical composition of subsystems, with interacting processes at the leaves of the hierarchy. Compositional reachability analysis (CRA) exploits the compositional hierarchy for incrementally constructing the overall behaviour of the system from that of its subsystems. In the Tracta CRA approach, both processes and properties reflecting system specifications are modelled as state machines. Property state machines are composed into the system and violations are detected on the global reachability graph obtained. The property checking mechanism has been specifically designed to deal with compositional techniques. Tracta is supported by an automated tool compatible with our environment for the development of distributed applications.     

On the composition of time Petri nets

Complex systems are often designed and built from smaller pieces, called components. Components are open sub-systems meant to be combined (or composed) to form other components or closed systems. It is well known that Petri nets allow such a component based modeling, relying on parallel composition and transition synchronization. However, synchronizing transitions that carry temporal constraints does not yield a compositional method for assembling components, a highly desirable property. The paper addresses this particular problem: how to build complex systems in a compositional manner from components specified by Time Petri nets (TPN). A first solution is proposed, adequate for a particular subclass of Time Petri nets but significantly increasing the complexity of components. Then an improved solution is developed, relying on an extension of Time Petri nets with two relations added on transitions. This latter solution requires a much simpler transformation of nets, does not significantly increase their complexity, and is applicable to a larger class of TPN.     

Learning-based symbolic assume-guarantee reasoning for Markov decision process by using interval Markov process

Many real-life critical systems are described with large models and exhibit both probabilistic and non-deterministic behaviour. Verification of such systems requires techniques to avoid the state space explosion problem. Symbolic model checking and compositional verification such as assume-guarantee reasoning are two promising techniques to overcome this barrier. In this paper, we propose a probabilistic symbolic compositional verification approach (PSCV) to verify probabilistic systems where each component is a Markov decision process (MDP). PSCV starts by encoding implicitly the system components using compact data structures. To establish the symbolic compositional verification process, we propose a sound and complete symbolic assume-guarantee reasoning rule. To attain completeness of the symbolic assume-guarantee reasoning rule, we propose to model assumptions using interval MDP. In addition, we give a symbolic MTBDD-learning algorithm to generate automatically the symbolic assumptions. Moreover, we propose to use causality to generate small counterexamples in order to refine the conjecture assumptions. Experimental results suggest promising outlooks for our probabilistic symbolic compositional approach.     

A bandwidth allocation scheme for compositional real-time systems with periodic resources

Allocation of bandwidth among components is a fundamental problem in compositional real-time systems. State-of-the-art algorithms for bandwidth allocation use either exponential-time or pseudo-polynomial-time techniques for exact allocation, or linear-time, utilization-based techniques which may over-provision bandwidth. In this paper, we propose research into a third possible approach: parametric approximation algorithms for bandwidth allocation in compositional real-time systems. We develop a fully-polynomial-time approximation scheme (FPTAS) for allocating bandwidth for sporadic task systems scheduled by earliest-deadline first (EDF) upon an Explicit-Deadline Periodic (EDP) resource. Our algorithm takes, as parameters, the task system and an accuracy parameter ϵ>0, and returns a bandwidth which is guaranteed to be at most a factor (1+ϵ) more than the optimal minimum bandwidth required to successfully schedule the task system. Furthermore, the algorithm has time complexity that is polynomial in the number of tasks and 1/ϵ.     

Syntax-driven Behavior Partitioning for Model-checking of Esterel Programs

We consider the issue of exploiting the structural form of Esterel programs to partition the algorithmic RSS (reachable state space) fix-point construction used in model-checking techniques. The basic idea sounds utterly simple, as seen on the case of sequential composition: in P; Q, first compute entirely the states reached in P, and then only carry on to Q, each time using only the relevant transition relation part. Here a brute-force symbolic breadth-first search would have mixed the exploration of P and Q instead, in case P had different behaviors of various lengths, and that would result in irregular BBD representation of temporary state spaces, a major cause of complexity in symbolic model-checking.Difficulties appear in our decomposition approach when scheduling the different transition parts in presence of parallelism and local signal exchanges. Program blocks (or “Macro-states”) put in parallel can be synchronized in various ways, due to dynamic behaviors, and considering all possibilities may lead to an excessive division complexity. The goal is here to find a satisfactory trade-off between compositional and global approaches. Concretely we use some of the features of the TiGeR BDD library, and heuristic orderings between internal signals, to have the transition relation progress through the program behaviors to get the same effect as a global RSS computation, but with much more localized transition applications. We provide concrete benchmarks showing the usefulness of the approach.     

Automated circular assume-guarantee reasoning

Model checking is a successful approach for verifying hardware and software systems. Despite its success, the technique suffers from the state explosion problem which arises due to the large state space of real-life systems. One solution to the state explosion problem is compositional verification, that aims to decompose the verification of a large system into the more manageable verification of its components. To account for dependencies between components, assume-guarantee reasoning defines rules that break-up the global verification of a system into local verification of individual components, using assumptions about the rest of the system. In recent years, compositional techniques have gained significant successes following a breakthrough in the ability to automate assume-guarantee reasoning. However, automation has been restricted to simple acyclic assume-guarantee rules. In this work, we focus on automating circular assume-guarantee reasoning in which the verification of individual components mutually depends on each other. We use a sound and complete circular assume-guarantee rule and we describe how to automatically build the assumptions needed for using the rule. Our algorithm accumulates joint constraints on the assumptions based on (spurious) counterexamples obtained from checking the premises of the rule, and uses a SAT solver to synthesize minimal assumptions that satisfy these constraints. To the best of our knowledge, our work is the first to fully automate circular assume-guarantee reasoning. We implemented our approach and compared it with established non-circular compositional methods that use learning or SAT-based techniques. The experiments show that the assumptions generated for the circular rule are generally smaller, and on the larger examples, we obtain a significant speedup.     

Compositional Analysis of C/C++ Programs with VeriSoft

This paper describes how the state space exploration ool VeriSoft can be used to analyze parallel C/C++ programs compositionally. VeriSoft is employed for two analyses: transition traceanalysis and assume/guarantee reasoning. Both analyses are compositional in the sense that the behaviour of a parallel program is determined in terms of the behaviour of its constituent processes. While both analyses have traditionally been carried out with “pencil and paper”, the paper demonstrates how VeriSoft can be used to automate them. In the context of transition trace analysis, the question whether a given program can exhibit a given trace is addressed with VeriSoft. To implement assume/guarantee reasoning, VeriSoft is used to determine whether a given program satisfies a given assume/guarantee specification. Since VeriSoft’s state space exploration is bounded and thus not complete in general, our proposed analyses are only meant to complement standard reasoning about parallel programs using traces or assume/guarantee specifications. For instance, a successful analysis does not always imply the general correctness of an assume/guarantee specification. However, it increases the confidence in the verification effort. On the other hand, an unsuccessful analysis always produces a counterexample which can be used to correct the specification or the program. VeriSoft’s optimization and visualization techniques make the analyses relatively efficient and effective.     

Aeroelastic modeling and stability analysis: A robust approach to the flutter problem

In this paper, a general approach to address modeling of aeroelastic systems, with the final goal to apply μ analysis, is discussed. The chosen test bed is the typical section with unsteady aerodynamic loads, which enables basic modeling features to be captured and so extend the gained knowledge to practical problems treated with modern techniques. The aerodynamic operator has a nonrational dependence on the Laplace variable s, and hence, 2 formulations for the problem are available: frequency domain or state‐space (adopting rational approximations). The study attempts to draw a parallel between the 2 consequent linear fractional transformation modeling processes, emphasizing critical differences and their effect on the predictions obtained with μ analysis. A peculiarity of this twofold formulation is that aerodynamic uncertainties are inherently treated differently and therefore the families of plants originated by the possible linear fractional transformation definitions are investigated. One of the main results of the paper is to propose a unified framework to address the robust modeling task, which enables the advantages of both the approaches to be retained. On the analysis side, the application of μ analysis to the different models is shown, emphasizing its capability to gain insight into the problem.     

Developing systems methodically

First there is a general discussion of: formality in the software development process; the weaknesses of a purely functional view of systems; the pros and cons of development by a process of decomposition versus a process of incremental composition; the relationship between the technical substance of a software project and the managerial framework.Some particular characteristics of one approach, the JSD approach, are described, in particular: the use of processes as a modelling tool; the elaboration of a process model into an executable specification; the relationship of JSD to data analysis techniques; the transformation of many specification processes into a small number of implementation processes; the structure of individual processes.Finally there is a brief summary of JSD followed by the development of a small example.     

平行系统和数字孪生的一种数据驱动形式表示及计算框架

旨在为平行系统及ACP方法建立一种数据驱动的数学形式和计算框架, 该形式与框架也适用于数字孪生系统.首先, 基于动态系统状态方程方法论, 给出了平行系统的虚实双系统表示方法, 基于此表示方法为平行系统问题提供了一种数学表示.围绕该表示, 讨论了虚实系统互动、平行系统与数字孪生系统异同等问题.然后, 为ACP方法提供了一种计算框架, 详细解释了人工系统(Artificial systems, A)、计算实验(Computational experiments, C)、平行执行(Parallel execution, P)的数学计算求解过程, 并讨论了“学习与训练”、“实验与评估”、“管理与控制”、灵捷–聚焦–收敛(AFC)、小数据-大数据-小智能等概念的相关数学表示, 并讨论了智能科学与平行系统数学架构的关系以及平行智能的内涵.最后, 以大学校园园区能源管理系统为案例, 为平行系统数学架构和方法提供一个直观的算例.     

Domain decomposition and multigrid solvers for flow simulation in porous media on distributed memory parallel processors

Realistic simulations of fluid flow in oil reservoirs have been proven to be computationally intensive. In this work, techniques for solving large sparse systems of linear equations that arise in simulating these processes are developed for parallel computers such as INTEL hypercubes iPSC/2 and iPSC/860. This solver is based on a combined multigrid and domain decomposition approach. The Algorithm uses line corrections solved using a multigrid method, line Jacobi and block incomplete domain decomposition as an overall preconditioner for a conjugate gradient-like acceleration method, ORTHOMIN (k). This is shown to be a factor of ten times faster on a 32-processor hypercube compared to widely used sequential solvers. Three test problems are used to validate the results which include implicit wells and faults: The first is based on highly heterogeneous two-phase flow, the second on the SPE Third Comparative Solution and the third on real production compositional data.     

An effective approach to the optimal-control problem for time-varying linear systems via Taylor series

The Taylor series is used for the solution of the optimal-control problem for time-varying linear systems. Instead of solving the state transition matrix from the state equation with a terminal condition, the present approach first transforms the terminal condition into an initial condition, and then solves the initial-value problem to find the transition matrix. This approach leads lo a recursive algebraic formulation for the transition matrix, and only an inverse matrix of small dimension 2n × 2n appears in this formulation. Thus a closed-loop control law is obtained without solving the non-linear Riccati equation, and the matrix to be inverted has only small dimension 2n × 2n. The present approach is of great interest because of its simplicity and numerical stability.     

State space reduction by non-standard semantics for deadlock analysis

In recent years many techniques have been developed for automatically verifying concurrent systems and most of them are based on the representation of the concurrent system by means of a transition system. State explosion is one of the most serious problems of this approach: often the prohibitive number of states renders the verification inefficient and, in some cases, impossible.

We propose a method for reducing the state space of the transition system corresponding to a CCS process that suites deadlock analysis. The reduced transition system is generated by means of a non-standard operational semantics containing a set of rules which are, in some sense, an abstraction, preserving deadlock freeness, of the inference rules of the standard semantics. Our method does not build the standard transition system, but directly generates an abstract system with a fewer number of states, so saving memory space. We characterize a class of processes whose abstract transition system is not exponential in the number of parallel components.     

Verification of Hierarchical State/Event Systems using Reusability and Compositionality

We investigate techniques for verifying hierarchical systems, i.e., finite state systems with a nesting capability. The straightforward way of analysing a hierarchical system is to first flatten it into an equivalent non-hierarchical system and then apply existing finite state system verification techniques. Though conceptually simple, flattening is severely punished by the hierarchical depth of a system. To alleviate this problem, we develop a technique that exploits the hierarchical structure to reuse earlier reachability checks of superstates to conclude reachability of substates. We combine the reusability technique with the successful compositional technique of J. Lind-Nielsen, H.R. Andersen, G. Behrmann, H. Hulgaard, K. Kristoffersen, and K.G. Larsen, 1998. In: Tools and Algorithms for the Construction and Analysis of Systems, Vol. 1384 of Lecture Notes in Computer Science, pp. 201–216, and investigate the combination experimentally on industrial systems and hierarchical systems generated according to our expectations to real systems. The experimental results are very encouraging: whereas a flattening approach degrades in performance with an increase in the hierarchical depth (even when applying the technique of J. Lind-Nielsen et al. (1998)), the new approach proves not only insensitive to the hierarchical depth, but even leads to improved performance as the depth increases.     

Contextual local analysis in the design of distributed systems

Compositional Reachability Analysis is a popular technique for studying behaviour of finite-state distributed systems. The technique is applied by a repetition oflocal analyses, the basic steps of which are to construct and examine the behaviour of subsystems. In most cases, behaviour of the subsystem is constrained by its environment (calledcontext) formed by neighbouring components. These behaviour constraints are normally not considered when using local analysis in conventional techniques of compositional reachability analysis. As a result, many execution paths derived in the local analysis may not be actually traversed by the subsystem. These paths are made impossible to traverse by the constraints. The paths are unnecessary for understanding the subsystem behaviour and their removal greatly simplifies the local analysis.In this paper, we describe an elegant technique, calledcontextual local analysis, to include these behaviour constraints in conventional local analysis. The technique can alleviate dramatically the state explosion problem encountered in local analysis. It also facilitates early detection of anomalous behaviour of a distributed system at its design stage. The technique works by composing an interface process with the subsystem being examined. That interface process is so chosen that it captures behaviour constraints enforced by the environment while its composition with the subsystem does not affect the global system behaviour. This interface process can be automatically derived using a simple algorithm. The contextual local analysis technique results in a simplified labelled transition system which can be used as a substitute for the original subsystem in the construction of the global system behaviour. The contextual local analysis technique is illustrated with a clients/server example implementing a round-robin protocol.     

Deadlock detection without wait-for graphs

Deadlock detection is an important service that the run-time system of a parallel environment should provide. In parallel programs deadlock can occur when the different processes are waiting for various events, as opposed to concurrent systems, where deadlock occurs when processes wait for resources held by other processes. Therefore classical deadlock detection techniques such as checking for cycles in the wait-for graph are unapplicable. An alternative algorithm that checks whether all the processes are blocked is presented. This algorithm deals with situations in which the state transition from blocked to unblocked is indirect, as may happen when busy-waiting is used.     

Scheduling task graphs optimally with A*

Scheduling tasks onto the processors of a parallel system is a crucial part of program parallelisation. Due to the NP-hard nature of the task scheduling problem, scheduling algorithms are based on heuristics that try to produce good rather than optimal schedules. Nevertheless, in certain situations it is desirable to have optimal schedules, for example for time-critical systems or to evaluate scheduling heuristics. This paper investigates the task scheduling problem using the A* search algorithm which is a best-first state space search. The adaptation of the A* search algorithm for the task scheduling problem is referred to as the A* scheduling algorithm. The A* scheduling algorithm can produce optimal schedules in reasonable time for small to medium sized task graphs with several tens of nodes. In comparison to a previous approach, the here presented A* scheduling algorithm has a significantly reduced search space due to a much improved consistent and admissible cost function f(s) and additional pruning techniques. Experimental results show that the cost function and the various pruning techniques are very effective for the workload. Last but not least, the results show that the proposed A* scheduling algorithm significantly outperforms the previous approach.