Exploiting interleaving semantics in symbolic state-space generation

Symbolic techniques based on Binary Decision Diagrams (BDDs) are widely employed for reasoning about temporal properties of hardware circuits and synchronous controllers. However, they often perform poorly when dealing with the huge state spaces underlying systems based on interleaving semantics, such as communications protocols and distributed software, which are composed of independently acting subsystems that communicate via shared events. This article shows that the efficiency of state-space exploration techniques using decision diagrams can be drastically improved by exploiting the interleaving semantics underlying many event-based and component-based system models. A new algorithm for symbolically generating state spaces is presented that (i) encodes a model’s state vectors with Multi–valued Decision Diagrams (MDDs) rather than flattening them into BDDs and (ii) partitions the model’s Kronecker–consistent next–state function by event and subsystem, thus enabling multiple lightweight next–state transformations rather than a single heavyweight one. Together, this paves the way for a novel iteration order, called saturation, which replaces the breadth–first search order of traditional algorithms. The resulting saturation algorithm is implemented in the tool SMART, and experimental studies show that it is often several orders of magnitude better in terms of time efficiency, final memory consumption, and peak memory consumption than existing symbolic algorithms.     

The saturation algorithm for symbolic state-space exploration

We present various algorithms for generating the state space of an asynchronous system based on the use of multiway decision diagrams to encode sets and Kronecker operators on boolean matrices to encode the next-state function. The Kronecker encoding allows us to recognize and exploit the “locality of effect” that events might have on state variables. In turn, locality information suggests better iteration strategies aimed at minimizing peak memory consumption. In particular, we focus on the saturation strategy, which is completely different from traditional breadth-first symbolic approaches, and extend its applicability to models where the possible values of the state variables are not known a priori. The resulting algorithm merges “on-the-fly” explicit state-space generation of each submodel with symbolic state-space generation of the overall model. Each algorithm we present is implemented in our tool SmArT. This allows us to run fair and detailed comparisons between them on a suite of representative models. Saturation, in particular, is shown to be many orders of magnitude more efficient in terms of memory and time with respect to traditional methods.     

A linear-time model-checking algorithm for the alternation-free modal mu-calculus

We develop a model-checking algorithm for a logic that permits propositions to be defined using greatest and least fixed points of mutually recursive systems of equations. This logic is as expressive as the alternation-free fragment of the modal mu-calculus identified by Emerson and Lei, and it may therefore be used to encode a number of temporal logics and behavioral preorders. Our algorithm determines whether a process satisfies a formula in time proportional to the product of the sizes of the process and the formula; this improves on the best known algorithm for similar fixed-point logics.     

FuzzyTree crossover for multi-valued stock valuation

Stock valuation is very important for fundamental investors in order to select undervalued stocks so as to earn excess profits. However, it may be difficult to use stock valuation results, because different models generate different estimates for the same stock. This suggests that the value of a stock should be multi-valued rather than single-valued. We therefore develop a multi-valued stock valuation model based on fuzzy genetic programming (GP). In our fuzzy GP model the value of a stock is represented as a fuzzy expression tree whose terminal nodes are allowed to be fuzzy numbers. There is scant literature available on the crossover operator for our fuzzy trees, except for the vanilla subtree crossover. This study generalizes the subtree crossover in order to design a new crossover operator for the fuzzy trees. Since the stock value is estimated by a fuzzy expression tree which calculates to a fuzzy number, the stock value becomes multi-valued. In addition, the resulting fuzzy stock value induces a natural trading strategy which can readily be executed and evaluated. These experimental results indicate that the fuzzy tree (FuzzyTree) crossover is more effective than a subtree (SubTree) crossover in terms of expression tree complexity and run time. Secondly, shorter training periods produce a better return of investment (ROI), indicating that long-term financial statements may distort the intrinsic value of a stock. Finally, the return of a multi-valued fuzzy trading strategy is better than that of single-valued and buy-and-hold strategies.     

Probabilistic symbolic model checking with PRISM: a hybrid approach

In this paper we present efficient symbolic techniques for probabilistic model checking. These have been implemented in PRISM, a tool for the analysis of probabilistic models such as discrete-time Markov chains, continuous-time Markov chains and Markov decision processes using specifications in the probabilistic temporal logics PCTL and CSL. Motivated by the success of model checkers such as SMV which use BDDs (binary decision diagrams), we have developed an implementation of PCTL and CSL model checking based on MTBDDs (multi-terminal BDDs) and BDDs. Existing work in this direction has been hindered by the generally poor performance of MTBDD-based numerical computation, which is often substantially slower than explicit methods using sparse matrices. The focus of this paper is a novel hybrid technique which combines aspects of symbolic and explicit approaches to overcome these performance problems. For typical examples, we achieve a dramatic improvement over the purely symbolic approach. In addition, thanks to the compact model representation using MTBDDs, we can verify systems an order of magnitude larger than with sparse matrices, while almost matching or even beating them for speed.     

Combining partial order reductions with on-the-fly model-checking

Partial order model-checking is an approach to reduce time and memory in model-checking concurrent programs. On-the-fly model-checking is a technique to eliminate part of the search by intersecting an automaton representing the (negation of the) checked property with the state during its generation. We prove conditions under which these two methods can be combined in order to gain reduction from both. An extension of the model-checker SPIN, which implements this combination, is studied, showing substantial reduction over traditional search, not only in the number of reachable states, but directly in the amount of memory and time used. We also describe how to apply partial-order model-checking under given fairness assumptions.     

A note on approximation measures for multi-valued dependencies in relational databases

We consider the problem of defining a normalized approximation measure for multi-valued dependencies in relational database theory. An approximation measure is a function mapping relation instances to real numbers. The number to which an instance is mapped, intuitively, describes the strength of the dependency in that instance. A normalized approximation measure for functional dependencies has been proposed previously: the minimum number of tuples that need be removed for the functional dependency to hold divided by the total number of tuples. This leads naturally to a normalized measure for multi-valued dependencies: the minimum number of tuples that need be removed for the multi-valued dependency to hold divided by the total number of tuples.The measure for functional dependencies can be computed efficiently, O(|r|log(|r|)) where |r| is the relation instance. However, we show that an efficient algorithm for computing the analogous measure for multi-valued dependencies is not likely to exist. A polynomial time algorithm for computing the measure would lead to a polynomial time algorithm for an NP-complete problem (proven by a reduction from the maximum edge biclique problem in graph theory). Hence, we argue that it is not a good measure. We propose an alternate measure based on the lossless join characterization of multi-valued dependencies. This measure is efficiently computable, O(|r|²).     

Centre and Range method for fitting a linear regression model to symbolic interval data

This paper introduces a new approach to fitting a linear regression model to symbolic interval data. Each example of the learning set is described by a feature vector, for which each feature value is an interval. The new method fits a linear regression model on the mid-points and ranges of the interval values assumed by the variables in the learning set. The prediction of the lower and upper bounds of the interval value of the dependent variable is accomplished from its mid-point and range, which are estimated from the fitted linear regression model applied to the mid-point and range of each interval value of the independent variables. The assessment of the proposed prediction method is based on the estimation of the average behaviour of both the root mean square error and the square of the correlation coefficient in the framework of a Monte Carlo experiment. Finally, the approaches presented in this paper are applied to a real data set and their performance is compared.     

A refined difference field theory for symbolic summation

In this article we present a refined summation theory based on Karr’s difference field approach. The resulting algorithms find sum representations with optimal nested depth. For instance, the algorithms have been applied successively to evaluate Feynman integrals from Perturbative Quantum Field Theory.     

Generating test sequences using symbolic execution for event-driven real-time systems

Real-time software, often used to control event-driven process control systems, is usually structured as a set of concurrent and interacting tasks. Therefore, output values of real-time software depend not only on the input values but also on internal and nondeterministic execution patterns caused by task synchronization. In order to test real-time software effectively, one must generate test cases which include information on both the event sequences and the times at which various events occur. However, previous research on real-time software testing focused on generating the latter information. Our paper describes a method of generating test sequences from a Modechart specification using symbolic execution technique. Based on the notion of symbolic system configurations and the equivalence definitions between them, we demonstrate, using the railroad crossing system, how to construct a time-annotated symbolic execution tree and generate test sequences according to the selected coverage criteria.     

A new symbolic calculus for the response of nonlinear systems

We present a new operational calculus for computing the response of nonlinear systems to various deterministic excitations. The use of a new tool: noncommutative generating power series, allows us to derive, by simple algebraic manipulations, the Volterra functional series of the solution of a large class of nonlinear forced differential equations. The symbolic calculus introduced appears as a natural generalization to the nonlinear domain, of the well known Heaviside operational calculus. Moreover, this method has the advantage of allowing the use of a computer.     

An evaluation of the effectiveness of symbolic testing

The effectiveness in discovering errors of symbolic evaluation and of testing sad static program analysis are studied. The three techniques are applied to a diverse collection of programs and the results compared. Symbolic evaluation is used to carry out symbolic testing and to generate symbolic systems of path predicates. The use of the predicates for automated test data selection is analysed. Several conventional types of program testing strategies are evaluated. The strategies include branch testing, structured testing and testing on input values having special properties. The static source analysis techniques that are studied include anomaly analysis and interface analysis. Examples are included which describe typical situations in which one technique is reliable but another unreliable. The effectiveness of symbolic testing is compared with testing on actual data and with the use of an integrated methodology that includes both testing and static source analysis. Situations in which symbolic testing is difficult to apply or not effective are discussed. Different ways in which symbolic evaluation can be used for generating test data are described. Those ways for which it is most effective are isolated. The paper concludes with a discussion of the most effective uses to which symbolic evaluation can he put in an integrated system which contains all three of the validation techniques that are studied.     

A symbolic system for computer-aided development of surface interpolants

The design and implementation of a symbolic input end computation package and its application to the development of several new surface interpolation schemes are described. Capabilities such as the composition of operators and symbolic differentiation have been incorporated into the system. This allows, in particular, the specification of Boolean sum projectors. The new schemes which have been implemented include an interpolant to randomly spaced data and a 'shape operator1 which has quadratic precision.     

A symbolic matrix decomposition algorithm for reduced order linear fractional transformation modelling

In this paper an algorithm that provides an equivalent, but of reduced order, representation for multivariate polynomial matrices is given. It combines ideas from computational symbolic algebra, polynomial/matrix algebraic manipulations and information logic. The algorithm is applied to the problem of finding minimal linear fractional transformation models. Statistical performance analysis of the algorithm reveals that it consistently outperforms currently available algorithms.     

A tool for model-checking Markov chains

Markov chains are widely used in the context of the performance and reliability modeling of various systems. Model checking of such chains with respect to a given (branching) temporal logic formula has been proposed for both discrete [34, 10] and continuous time settings [7, 12]. In this paper, we describe a prototype model checker for discrete and continuous-time Markov chains, the Erlangen–Twente Markov Chain Checker E⊢MC², where properties are expressed in appropriate extensions of CTL. We illustrate the general benefits of this approach and discuss the structure of the tool. Furthermore, we report on successful applications of the tool to some examples, highlighting lessons learned during the development and application of E⊢MC². Published online: 19 November 2002 Correspondence to: Holger Hermanns     

A symbolic framework for multi-faceted security protocol analysis

Verification of software systems, and security protocol analysis as a particular case, requires frameworks that are expressive, so as to properly capture the relevant aspects of the system and its properties, formal, so as to be provably correct, and with a computational counterpart, so as to support the (semi-) automated certification of properties. Additionally, security protocols also present hidden assumptions about the context, specific subtleties due to the nature of the problem and sources of complexity that tend to make verification incomplete. We introduce a verification framework that is expressive enough to capture a few relevant aspects of the problem, like symmetric and asymmetric cryptography and multi-session analysis, and to make assumptions explicit, e.g., the hypotheses about the initial sharing of secret keys among honest (and malicious) participants. It features a clear separation between the modeling of the protocol functioning and the properties it is expected to enforce, the former in terms of a calculus, the latter in terms of a logic. This framework is grounded on a formal theory that allows us to prove the correctness of the verification carried out within the fully fledged model. It overcomes incompleteness by performing the analysis at a symbolic level of abstraction, which, moreover, transforms into executable verification tools.