一种面向AADL架构的模型测试方法

鉴于模型在软件系统开发中日趋重要的地位和AADL模型在嵌入式软件建模中的良好应用前景,为了在嵌入式软件系统开发前期保证AADL模型的质量,提出了一种基于模型测试的AADL架构验证方法;该方法应用马尔可夫链描述AADL架构的行为,然后根据得到的马尔可夫链模型以及系统设计要求标准生成相应的测试用例和测试预言,并通过测试用例执行输出和期望值的比较判断AADL模型的正确性,实现对系统AADL模型的测试;最后通过案例分析证明了该方法的有效性。     

基于UML的软件Markov链使用模型构造研究

软件统计测试要求基于软件使用模型产生测试例对软件系统进行测试,并根据测试结果评价软件可靠性,是高可靠软件测试的重要组成部分.由于统一建模语言(unified modeling language,简称UML)已经成为事实上的面向对象标准建模语言,因此,从软件UML模型构造软件使用模型就成为面向对象软件统计测试的关键.为此,定义了加入统计测试约束的UML用例图、序列图以及用例执行顺序关系,为基于UML的软件统计测试提供了一个形式化描述基础.在此基础上,给出一个从软件UML模型构造软件Markov链使用模型的算法,并给出了自动化支持工具UMGen的类图结构,基于一个卫星控制系统,说明了所提出方法的有效性.     

测试资源受约束的安全关键软件加速测试方法

基于马尔可夫链使用模型提出了一种针对安全关键软件测试资源受约束的启发式加速测试方法.该方法利用一种新的随机优化技术--交叉熵方法,以软件投放后软件失效风险损失最小为目标,基于失效风险损失通过修正操作剖面,自动生成测试数据集.实验结果表明该方法能有效地降低软件失效风险,提高测试效率,是一种快速有效的加速测试方法.     

A Markov chain model for statistical software testing

Statistical testing of software establishes a basis for statistical inference about a software system's expected field quality. This paper describes a method for statistical testing based on a Markov chain model of software usage. The significance of the Markov chain is twofold. First, it allows test input sequences to be generated from multiple probability distributions, making it more general than many existing techniques. Analytical results associated with Markov chains facilitate informative analysis of the sequences before they are generated, indicating how the test is likely to unfold. Second, the test input sequences generated from the chain and applied to the software are themselves a stochastic model and are used to create a second Markov chain to encapsulate the history of the test, including any observed failure information. The influence of the failures is assessed through analytical computations on this chain. We also derive a stopping criterion for the testing process based on a comparison of the sequence generating properties of the two chains     

基于模型的软件测试综述

随着面向对象软件开发技术的广泛应用和软件测试自动化的要求，特别是基于UML的软件开发技术的逐渐普及，基于模型的软件测试逐渐得到了软件开发人员和软件测试人员的认可和接受。针对被测试软件的不同特征和不同测试目的，已经提出了多种测试模型。本文详细阐述了基于模型的软件测试研究现状和应用现状，并对测试中使用的不同模型进行了比较，着重介绍了状态机模型、UML模型和马尔可夫链模型。最后提出了未来的研究方向。     

双随机软件可靠性模型的建模

本文在仔细分析了软件故障的物理过程及模型机理后，认为：由于软件故障过程的随机因素太复杂以致于用某一个传统随机过程不足以为软件故障过程建模．传统上采用的马尔可夫非齐次泊松过程模型或二项型式模型只能部分地表述软件的故障行为．若要全面地去表述软件的故障行为，就需要一个补偿随机过程．也就是说本文采用了两个随机函数来为软件故障行为建模．     

Numerical analysis of rational processes beyond Markov chains

Matrix exponential distributions and rational arrival processes have been proposed as an extension to pure Markov models. The paper presents an approach where these process types are used to describe the timing behavior in quantitative models like queueing networks, stochastic Petri nets or stochastic automata networks. The resulting stochastic process, which is called a rational process, is defined and it is shown that the matrix governing the behavior of the process has a structured representation which allows one to represent the matrix in a very compact form.     

Generating transition probabilities to support model‐based software testing

Markov chain usage models support test planning, test automation, and analysis of test results. In practice, transition probabilities for Markov chain usage models are often specified using a cycle of assigning, verifying, and revising specific values for individual transition probabilities. For large systems, such an approach can be difficult for a variety of reasons. We describe an improved approach that represents transition probabilities by explicitly preserving the information concerning test objectives and the relationships between transition probabilities in a format that is easy to maintain and easy to analyze. Using mathematical programming, transition probabilities are automatically generated to satisfy test management objectives and constraints. A more mathematical treatment of this approach is given in References [ 1 ] (Poore JH, Walton GH, Whittaker JA. A constraint‐based approach to the representation of software usage models. Information and SoftwareTechnology 2000; at press) and [ 2 ] (Walton GH. Generating transition probabilities for Markov chain usage models. PhD Thesis, University of Tennessee, Knoxville, TN, May 1995.). In contrast, this paper is targeted at the software engineering practitioner, software development manager, and test manager. This paper also adds to the published literature on Markov chain usage modeling and model‐based testing by describing and illustrating an iterative process for usage model development and optimization and by providing some recommendations for embedding model‐based testing activities within an incremental development process. Copyright © 2000 John Wiley & Sons, Ltd.     

改进Hu矩的ATM机异常行为识别研究

提出一种基于改进Hu矩和隐马尔可夫模型相结合的ATM机异常行为识别方法。对ATM机前用户存(取)款行为的视频序列用改进Hu变换提取运动目标的行为特征,采用Baum-Welch算法对用户的正常行为进行训练,并建立隐马尔可夫模型;最后通过模型输出测试样本序列的概率来识别异常行为。采用Matlab对ATM机用户运动行为的模拟视频进行实验仿真,结果表明:该方法对ATM机前的用户行为具有较高的识别率。     

Modelling financial time series based on heavy-tailed market microstructure models with scale mixtures of normal distributions

This paper presents a type of heavy-tailed market microstructure models with the scale mixtures of normal distributions (MM-SMN), which include two specific sub-classes, viz. the slash and the Student-t distributions. Under a Bayesian perspective, the Markov Chain Monte Carlo (MCMC) method is constructed to estimate all the parameters and latent variables in the proposed MM-SMN models. Two evaluating indices, namely the deviance information criterion (DIC) and the test of white noise hypothesis on the standardised residual, are used to compare the MM-SMN models with the classic normal market microstructure (MM-N) model and the stochastic volatility models with the scale mixtures of normal distributions (SV-SMN). Empirical studies on daily stock return data show that the MM-SMN models can accommodate possible outliers in the observed returns by use of the mixing latent variable. These results also indicate that the heavy-tailed MM-SMN models have better model fitting than the MM-N model, and the market microstructure model with slash distribution (MM-s) has the best model fitting. Finally, the two evaluating indices indicate that the market microstructure models with three different distributions are superior to the corresponding stochastic volatility models.     

Markov切换系统的随机稳定性分析

根据混合系统离散状态的动态行为和Markov链的状态也是离散的特点,提出了一类离散状态的动态行为是Markov链的混合系统。与传统的混合系统相比,这类系统能够刻画出混合系统离散动态行为的随机性,可以用来描述系统受到外界环境因素制约和内部突发事件等随机因素影响而发生变化的动态行为。根据动态系统的稳定性定义以及随机过程理论,给出了Markov线性切换系统的随机稳定性定义,并且分析了Markov线性切换系统的随机稳定性问题,给出了判定随机稳定性的充分必要条件。     

A non-equilibrium analysis and control framework for active queue management

We present a non-equilibrium analysis and control approach for the Active Queue Management (AQM) problem in communication networks. Using simplified fluid models, we carry out a bifurcation study of the complex dynamic queue behavior to show that non-equilibrium methods are essential for analysis and optimization in the AQM problem. We investigate an ergodic theoretic framework for stochastic modeling of the non-equilibrium behavior in deterministic models and use it to identify parameters of a fluid model from packet level simulations. For computational tractability, we use set-oriented numerical methods to construct finite-dimensional Markov models, including control Markov chains and hidden Markov models. Subsequently, we develop and analyze an example AQM algorithm using a Markov Decision Process (MDP) based control framework. The control scheme developed is optimal with respect to a reward function, defined over the queue size and aggregate flow rate. We implement and simulate our illustrative AQM algorithm in the ns-2 network simulator. The results obtained confirm the theoretical analysis and exhibit promising performance when compared with well-known alternative schemes under persistent non-equilibrium queue behavior.     

基于Markov决策过程用交叉熵方法优化软件测试

研究了待测软件某些参数已知的条件下,以最小化平均测试费用为目标的软件测试优化问题.将软件测试过程处理成马尔可夫(Markov)决策过程,给出了软件测试的马尔可夫决策模型,运用交叉熵方法,通过一种学习策略获得软件测试的最优测试剖面,用于优化软件测试.模拟结果表明,学习策略给出的测试剖面要优于随机测试策略,检测和排除相同数目的软件缺陷,学习策略比随机测试能够显著地减少测试用例数,降低测试成本,提高缺陷检测效率.     

A new disk-based technique for solving the largeness problem of stochastic modeling formalisms

Stochastic modeling formalisms such as stochastic Petri nets, generalized stochastic Petri nets, and stochastic reward nets can be used to model and evaluate the dynamic behavior of realistic computer systems. Once we translate the stochastic system model to the underlying corresponding Markov Chain (MC), the developed MC grows wildly to several hundred thousands states. This problem is known as the largeness problem. To tolerate the largeness problem of Markov models, several iterative and direct methods have been proposed in the literature. Although the iterative methods provide a feasible solution for most realistic systems, a major problem appears when these methods fail to reach a solution. Unfortunately, the direct method represents an undesirable numerical technique for tolerating large matrices due to the fill-in problem. In order to solve such problem, in this paper, we develop a disk-based segmentation (DBS) technique based on modifying the Gauss Elimination (GE) technique. The proposed technique has the capability of solving the consequences of the fill-in problem without making assumptions about the underlying structure of the Markov processes of the developed model. The DBS technique splits the matrix into a number of vertical segments and uses the hard disk to store these segments. Using the DBS technique, we can greatly reduce the memory required as compared to that of the GE technique. To minimize the increase in the solution time due to the disk accessing processes, the DBS utilizes a clever management technique for such processes. The effectiveness of the DBS technique has been demonstrated by applying it to a realistic model for the Kanban manufacturing system.     

Transient analysis of stochastic fluid models

We analyze the transient behavior of stochastic fluid flow models in which the input and output rates are controlled by a finite homogeneous Markov process. Such models are used in asynchronous transfer mode (ATM) to evaluate the performance of fast packet switching and in manufacturing systems for the performance of producers and consumers coupled by a buffer. The transient analysis of such models has already been considered in earlier works and solutions have been obtained by the use of Laplace transform. We derive in this paper a new transient solution only based on recurrence relations. We show that this solution is particularly interesting for its numerical properties. The limiting behavior of the solution is also considered. We empirically show that the algorithm for computing the transient solution can be stopped when some stationary behavior is detected.     

A practical model‐based statistical approach for generating functional test cases: application in the automotive industry

With the growing complexity of industrial software applications, industrials are looking for efficient and practical methods to validate the software. This paper develops a model‐based statistical testing approach that automatically generates online and offline test cases for embedded software. It discusses an integrated framework that combines solutions for three major software testing research questions: (i) how to select test inputs; (ii) how to predict the expected results of a test; and (iii) when to stop testing software. The automatic selection of test inputs is based on a stochastic test model that accounts for the main particularity of embedded software: time sensitivity. Software test practitioners may design one or more test models when they generate random, user‐oriented, or fault‐oriented test inputs. A formal framework integrating existing and appropriate specification techniques was developed for the design of automated test oracles (executable software specifications) and the formal measurement of functional coverage. The decision to stop testing software is based on both test coverage objectives and cost constraints. This approach was tested on two representative case studies from the automotive industry. The experiment was performed at unit testing level in a simulated environment on a host personal computer (automatic test execution). The two software functionalities tested had previously been unit tested and validated using the test design approach conventionally used in the industry. Applying the proposed model‐based statistical testing approach to these two case studies, we obtained significant improvements in performing functional unit testing in a real and complex industrial context: more bugs were detected earlier and in a shorter time. Copyright © 2012 John Wiley & Sons, Ltd.     

A robust stochastic stability analysis approach for power system considering wind speed prediction error based on Markov model

This paper proposes a robust stochastic stability analysis approach with partly unknown transition probability by considering the wind speed prediction error in power system. Firstly, taking this prediction error into account, based on Markov modeling theory, the stochastic dynamic model of wind power system with uncertain transition probability is developed. Secondly, according to the stochastic stability theory of Markov jump system, the transition probability of wind power system mode is divided into three cases: fully known, only known upper and lower bounds, and completely unknown. Then, by using linear matrix inequality (LMI) technology, a robust stochastic stability criterion with disturbance attenuation is obtained. Finally, test results show that the proposed analysis approach does not need to obtain the trajectory of the actual system operation parameters, and has the advantages of high computational efficiency.     

基于非马尔可夫随机Petri网的软件再生建模与分析

软件老化是影响软件系统可靠性的重要潜在因素,软件再生作为一种主动预防性的软件容错技术是解决软件老化问题的主要手段.以往的随机Petri网再生模型假定所有变迁的实施时间服从指数分布.针对变迁的实施时间服从确定性分布或一般性分布的情况,文中提出了一种用非马尔可夫随机Petri网建立软件再生模型的方法.该方法采用马尔可夫再生理论对模型进行分析,并给出模型的瞬态解和稳态解.仿真实验表明:选择合适的软件再生周期,可以有效地降低存在老化的软件系统的平均宕机成本,提高系统的可用性和可靠性.     

Computing Equilibrium Wealth Distributions in Models with Heterogeneous-Agents, Incomplete Markets and Idiosyncratic Risk

This paper describes an accurate, fast and robust fixed point method for computing the stationary wealth distributions in macroeconomic models with a continuum of infinitely-lived households who face idiosyncratic shocks with aggregate certainty. The household wealth evolution is modeled as a mixture Markov process and the stationary wealth distributions are obtained using eigen structures of transition matrices by enforcing the conditions for the Perron–Frobenius theorem by adding a perturbation constant to the Markov transition matrix. This step is utilized repeatedly within a binary search algorithm to find the equilibrium state of the system. The algorithm suggests an efficient and reliable framework for studying dynamic stochastic general equilibrium models with heterogeneous agents.