Stochastic software testing

This paper presents a method for test case selection that allows a formal approach to testing software. The two main ideas are (1) that testers create stochastic models of software behavior instead of crafting individual test cases and (2) that specific test cases are generated from the stochastic models and applied to the software under test. This paper describes a method for creating a stochastic model in the context of a solved example. We concentrate on Markov models and show how non‐Markovian behavior can be embedded in such models without violating the Markov property.     

Markov constraints: steerable generation of Markov sequences

Markov chains are a well known tool to model temporal properties of many phenomena, from text structure to fluctuations in economics. Because they are easy to generate, Markovian sequences, i.e. temporal sequences having the Markov property, are also used for content generation applications such as text or music generation that imitate a given style. However, Markov sequences are traditionally generated using greedy, left-to-right algorithms. While this approach is computationally cheap, it is fundamentally unsuited for interactive control. This paper addresses the issue of generating steerable Markovian sequences. We target interactive applications such as games, in which users want to control, through simple input devices, the way the system generates a Markovian sequence, such as a text, a musical sequence or a drawing. To this aim, we propose to revisit Markov sequence generation as a branch and bound constraint satisfaction problem (CSP). We propose a CSP formulation of the basic Markovian hypothesis as elementary Markov Constraints (EMC). We propose algorithms that achieve domain-consistency for the propagators of EMCs, in an event-based implementation of CSP. We show how EMCs can be combined to estimate the global Markovian probability of a whole sequence, and accommodate for different species of Markov generation such as fixed order, variable-order, or smoothing. Such a formulation, although more costly than traditional greedy generation algorithms, yields the immense advantage of being naturally steerable, since control specifications can be represented by arbitrary additional constraints, without any modification of the generation algorithm. We illustrate our approach on simple yet combinatorial chord sequence and melody generation problems and give some performance results.     

Some relations among stochastic finite state networks used inautomatic speech recognition

In the literature on automatic speech recognition, the popular hidden Markov models (HMMs), left-to-right hidden Markov models (LRHMMs), Markov source models (MSMs), and stochastic regular grammars (SRGs) are often proposed as equivalent models. However, no formal relations seem to have been established among these models to date. A study of these relations within the framework of formal language theory is presented. The main conclusion is that not all of these models are equivalent, except certain types of hidden Markov models with observation probability distribution in the transitions, and stochastic regular grammar     

A computationally efficient technique for transient analysis of repairable Markovian systems

A technique to design efficient methods using a combination of explicit (non-stiff) and implicit (stiff) ODE methods for numerical transient analysis of repairable Markovian systems is proposed. Repairable systems give rise to stiff Markov chains due to extreme disparity between failure rates and repair rates. Our approach is based on the observation that stiff Markov chains are non-stiff for an initial phase of the solution interval. A non-stiff ODE method is used to solve the model for this phase and a stiff ODE method is used to solve the model for the rest of the duration until the end of solution interval. A formal criterion to determine the length of the non-stiff phase is described. A significant outcome of this approach is that the accuracy requirement automatically becomes a part of model stiffness. Two specific methods based on this approach have been implemented. Both the methods use the Runge-Kutta-Fehlberg method as the non-stiff method. One uses the TR-BDF2 method as the stiff method while the other uses an implicit Runge-Kutta method as the stiff method. Numerical results obtained from solving dependability models of a multiprocessor system and an interconnection network are presented. These results show that the methods obtained using this approach are much more efficient than the corresponding stiff methods which have been proposed to solve stiff Markov models.     

On designing of sliding-mode control for stochastic jump systems

In this note, we consider the problems of stochastic stability and sliding-mode control for a class of linear continuous-time systems with stochastic jumps, in which the jumping parameters are modeled as a continuous-time, discrete-state homogeneous Markov process with right continuous trajectories taking values in a finite set. By using Linear matrix inequalities (LMIs) approach, sufficient conditions are proposed to guarantee the stochastic stability of the underlying system. Then, a reaching motion controller is designed such that the resulting closed-loop system can be driven onto the desired sliding surface in a limited time. It has been shown that the sliding mode control problem for the Markovian jump systems is solvable if a set of coupled LMIs have solutions. A numerical example is given to show the potential of the proposed techniques.     

Efficient mobile phone Chinese optical character recognition systems by use of heuristic fuzzy rules and bigram Markov language models

Statistical language models are very useful tools to improve the recognition accuracy of optical character recognition (OCR) systems. In previous systems, segmentation by maximum word matching, semantic class segmentation, or trigram language models have been used. However, these methods have some disadvantages, such as inaccuracies due to a preference for longer words (which may be erroneous), failure to recognize word dependencies, complex semantic training data segmentation, and a requirement of high memory.To overcome these problems, we propose a novel bigram Markov language model in this paper. This type of model does not have large word preferences and does not require semantically segmented training data. Furthermore, unlike trigram models, the memory requirement is small. Thus, the scheme is suitable for handheld and pocket computers, which are expected to be a major future application of text recognition systems.However, due to a simple language model, the bigram Markov model alone can introduce more errors. Hence in this paper, a novel algorithm combining bigram Markov language models with heuristic fuzzy rules is described. It is found that the recognition accuracy is improved through the use of the algorithm, and it is well suited to mobile and pocket computer applications, including as we will show in the experimental results, the ability to run on mobile phones.The main contribution of this paper is to show how fuzzy techniques as linguistic rules can be used to enhance the accuracy of a crisp recognition system, and still have low computational complexity.     

Towards a dynamical model for wireless sensor networks

In this paper we introduce two dynamical models for a broadcast process in wireless sensor networks. We obtain a convergent martingale sequence for the two models. To our knowledge, such martingales were unknown previously. We look at the formal models using the formalisms of martingales, dynamical systems and Markov chains, each formalism providing complementary and coherent information with each other. The dynamics of both models are comparable and are validated in their domain of application with numerical simulation of wireless sensor networks. We make explicit the situations where the models are realistic. We also provide a formal analysis of the quasi-stationary distribution associated to the Markov chain corresponding to the second model proposed.     

An algorithmic approach for analysis of finite-source retrial systems with unreliable servers

This paper aims at presenting an approach for analyzing finite-source retrial systems with servers subject to breakdowns and repairs, using Generalized Stochastic Petri Nets (GSPNs). This high-level formalism allows a simple representation of such systems with different breakdown disciplines. From the GSPN model, a Continuous Time Markov Chain (CTMC) can be automatically derived. However, for multiserver retrial systems with unreliable servers, the models may have a huge state space. Using the GSPN model as a support, we propose an algorithm for directly computing the infinitesimal generator of the CTMC without generating the reachability graph. In addition, we develop the formulas of the main stationary performance and reliability indices, as a function of the number of servers, the size of the customer source and the stationary probabilities. Through numerical examples, we discuss the effect of the system parameters and the breakdown disciplines on performance.     

Systemic banking crisis early warning systems using dynamic Bayesian networks

For decades, the literature on banking crisis early-warning systems has been dominated by two methods, namely, the signal extraction and the logit model methods. However, these methods, do not model the dynamics of the systemic banking system. In this study, dynamic Bayesian networks are applied as systemic banking crisis early-warning systems. In particular, the hidden Markov model, the switching linear dynamic system and the naïve Bayes switching linear dynamic system models are considered. These dynamic Bayesian networks provide the means to model system dynamics using the Markovian framework. Given the dynamics, the probability of an impending crisis can be calculated. A unique approach to measuring the ability of a model to predict a crisis is utilised. The results indicate that the dynamic Bayesian network models can provide precise early-warnings compared with the signal extraction and the logit methods.     

Rare event simulation for highly dependable systems with fast repairs

Probabilistic model checking has been used recently to assess, among others, dependability measures for a variety of systems. However, the numerical methods employed, such as those supported by model checking tools such as PRISM and MRMC, suffer from the state-space explosion problem. The main alternative is statistical model checking, which uses standard Monte Carlo simulation, but this performs poorly when small probabilities need to be estimated. Therefore, we propose a method based on importance sampling to speed up the simulation process in cases where the failure probabilities are small due to the high speed of the system’s repair units. This setting arises naturally in Markovian models of highly dependable systems. We show that our method compares favourably to standard simulation, to existing importance sampling techniques, and to the numerical techniques of PRISM.     

Markov models for offline handwriting recognition: a survey

Since their first inception more than half a century ago, automatic reading systems have evolved substantially, thereby showing impressive performance on machine-printed text. The recognition of handwriting can, however, still be considered an open research problem due to its substantial variation in appearance. With the introduction of Markovian models to the field, a promising modeling and recognition paradigm was established for automatic offline handwriting recognition. However, so far, no standard procedures for building Markov-model-based recognizers could be established though trends toward unified approaches can be identified. It is therefore the goal of this survey to provide a comprehensive overview of the application of Markov models in the research field of offline handwriting recognition, covering both the widely used hidden Markov models and the less complex Markov-chain or n-gram models. First, we will introduce the typical architecture of a Markov-model-based offline handwriting recognition system and make the reader familiar with the essential theoretical concepts behind Markovian models. Then, we will give a thorough review of the solutions proposed in the literature for the open problems how to apply Markov-model-based approaches to automatic offline handwriting recognition.     

Average Profile of the Lempel-Ziv Parsing Scheme for a Markovian Source

For a Markovian source, we analyze the Lempel—Ziv parsing scheme that partitions sequences into phrases such that a new phrase is the shortest phrase not seen in the past. We consider three models: In the Markov Independent model, several sequences are generated independently by Markovian sources, and the ith phrase is the shortest prefix of the ith sequence that was not seen before as a phrase (i.e., a prefix of previous (i-1) sequences). In the other two models, only a single sequence is generated by a Markovian source. In the second model, called the Gilbert—Kadota model, a fixed number of phrases is generated according to the Lempel—Ziv algorithm, thus producing a sequence of a variable (random) length. In the last model, known also as the Lempel—Ziv model, a string of fixed length is partitioned into a variable (random) number of phrases. These three models can be efficiently represented and analyzed by digital search trees that are of interest to other algorithms such as sorting, searching, and pattern matching. In this paper we concentrate on analyzing the average profile (i.e., the average number of phrases of a given length), the typical phrase length, and the length of the last phrase. We obtain asymptotic expansions for the mean and the variance of the phrase length, and we prove that appropriately normalized phrase length in all three models tends to the standard normal distribution, which leads to bounds on the average redundancy of the Lempel—Ziv code. For the Markov Independent model, this finding is established by analytic methods (i.e., generating functions, Mellin transform, and depoissonization), while for the other two models we use a combination of analytic and probabilistic analyses. Received June 6, 2000; revised January 14, 2001.     

Non-stationary fuzzy Markov chain

This paper deals with a recent statistical model based on fuzzy Markov random chains for image segmentation, in the context of stationary and non-stationary data. On one hand, fuzzy scheme takes into account discrete and continuous classes through the modeling of hidden data imprecision and on the other hand, Markovian Bayesian scheme models the uncertainty on the observed data. A non-stationary fuzzy Markov chain model is proposed in an unsupervised way, based on a recent Markov triplet approach. The method is compared with the stationary fuzzy Markovian chain model. Both stationary and non-stationary methods are enriched with a parameterized joint density, which governs the attractiveness of the neighbored states. Segmentation task is processed with Bayesian tools, such as the well known MPM (Mode of Posterior Marginals) criterion. To validate both models, we perform and compare the segmentation on synthetic images and raw optical patterns which present diffuse structures.     

On Using Multidimensional Markov Chains for Performance Evaluation of Hybrid Wireless Networks

The use of Wireless in Local Loop (WiLL) has generated considerable interest due to the advantages it offers such as ease and low cost of deployment and maintenance. With an increase in the number of subscribers in the network, it becomes expedient to employ spectrum reusability techniques such as the use of multihop relaying in order to improve the capacity of the wireless systems. Throughput enhanced Wireless in Local Loop (TWiLL) is one such architecture that employs multihop relaying and shortcut relaying to reuse bandwidth in WiLL Systems. Compared to other multihop wireless network architectures, TWiLL architecture assumes significance due to its potential use in fixed wireless broadband services such as LMDS (Local Multipoint Distribution Service) and MMDS (Multichannel Multipoint Distribution System). Analysis of the Call Acceptance Ratio (CAR) in multihop wireless architectures including TWiLL is nontrivial as the Erlang B formula no longer holds. In this paper, we build multidimensional Markov Chains to analyze the performance of multihop wireless systems such as TWiLL that has multiple types of channels. We also compare the results of our analysis with results from simulations. We observe that multihop relaying and shortcut relaying lead to a significant increase in the CAR of WiLL systems. Also, the free space propagation model that is normally used to model the radio channel is a very unrealistic model and does not consider reflection, diffraction, scattering, and multipath propagation that hinder transmissions in WiLL systems. In this paper, we studied the effect of several realistic radio channel propagation models on the performance of the TWiLL system through analysis and simulations.     

Introducing probabilities in Statecharts to specify reactive systems for performance analysis

Statecharts are expressed in a graphical language to specify complex reactive systems. They are extension of state-transition diagrams to which notions of hierarchy and orthogonality have been added. Recently, they have been suggested to represent performance models and in this regard a software package has been developed. In these performance models, the behavior of a system under study is considered to be probabilistic. Therefore, the inclusion of probabilities in Statecharts formalism will be studied. The proposed extension considers that a modeled system reacts probabilistically to events. In order to deal with these models, an analytical computational method based on constructing a Continuous-Time Markov Chain that is equivalent to the Statecharts model is proposed. The aspect of generating a Continuous-Time Markov Chain from Statecharts representation along with the solution to include probabilities among the transitions will be covered in this paper.     

Fast sampling methods for Bayesian max-margin models

Bayesian max-margin models have shown superiority in various practical applications, such as text categorization, collaborative prediction, social network link prediction and crowdsourcing, and they conjoin the flexibility of Bayesian modeling and predictive strengths of max-margin learning. However, Monte Carlo sampling for these models still remains challenging, especially for applications that involve large-scale datasets. In this paper, we present the stochastic subgradient Hamiltonian Monte Carlo (HMC) methods, which are easy to implement and computationally efficient. We show the approximate detailed balance property of subgradient HMC which reveals a natural and validated generalization of the ordinary HMC. Furthermore, we investigate the variants that use stochastic subsampling and thermostats for better scalability and mixing. Using stochastic subgradient Markov Chain Monte Carlo (MCMC), we efficiently solve the posterior inference task of various Bayesian max-margin models and extensive experimental results demonstrate the effectiveness of our approach.     

Product form solution for a class of PEPA models

The advantages of the compositional structure within the Markovian process algebra PEPA for model construction and simplification have already been demonstrated. In this paper we show that for some PEPA models this structure may also be used to advantage during the solution of the model. Several papers offering product form solutions of stochastic Petri nets have been published during the last 10 years. In [R. Boucherie, A characterisation of independence for competing Markov chains with applications to stochastic Petri nets, IEEE Trans. Software Engrg. 20 (7) (1994) 536–544], Boucherie showed that these solutions were a special case of a simple exclusion mechanism for the product process of a collection of Markov chains. The results presented in this paper take advantage of his observation. In particular we show that PEPA models that generate such processes may be readily identified and show how the product form solution may be obtained. Although developed here in the context of PEPA the results presented can be easily generalised to any of the other Markovian process algebra languages.     

Stability of Markov modulated discrete-time dynamic systems

Motivated by various control applications, this paper develops stability analysis of discrete-time systems with regime switching, in which the dynamics are modulated by Markov chains with two time scales. Using the high contrast of the different transition rates among the Markovian states, singularly perturbed Markov chains are used in the formulations. Taking into consideration of the regime changes and time-scale separation makes the stability analysis a difficult task. In this work, asymptotic stability analysis is carried out using perturbed Liapunov function techniques. It is demonstrated that if the limit system is stable, then the original system is also stable. In addition, we examine path excursion, derive bounds on mean recurrence time, and obtain the associated probability bounds.