A constraint-based approach to the representation of software usage models

Software usage models are the basis for statistical testing. They derive their structure from specifications and their probabilities from evolving knowledge about the intended use of the software product. The evolving knowledge comes from developers, customers and testers of the software system in the form of relationships that should hold among the parameters of a model. When software usage models are encoded as Markov chains, their structure can be represented by a system of linear constraints, and many of the evolving relationships among model parameters can be represented by convex constraints. Given a Markov chain usage model as a system of convex constraints, mathematical programming can be used to generate the Markov chain transition probabilities that represent a specific software usage model.     

基于重要抽样的软件统计测试加速

本文提出一种基于重要抽样的软件统计测试加速方法,该方法通过调整软件Markov链使用模型的迁移概率,在根据统计测试结果得到软件可靠性无偏估计的前提下,可以有效提高安全攸关软件的测试效率,部分解决了安全攸关软件统计测试时间和费用开销过大的问题。同时,本文给出了计算优化迁移概率的模拟退火算法。实验仿真结果表明,该方法可以有效地提高安全攸关软件统计测试的效率。     

安全关键系统的软件可靠性评估方法

基于统计测试的Markov使用链模型对安全关键系统的可靠性估计提出了一种有效的方法。该方法利用重要抽样技术在保证佑计的无偏性条件下,以可靠性估计的方差最小为目的,通过Ali-Silvey距离度量两个分布之间的差异,调整各个状态之间的转移概率分布,修正测试剖面,增加关键操作的遍历概率。最后给出了软件可靠性估计的最优测试剖面生成迭代算法。仿真结果表明,该方法能明显降低估计方差,在提高估计精度的同时能有效地加速统计测试。     

基于使用模型的嵌入式软件测试用例生成研究

基于Markov链使用模型的软件统计测试是产生高效测试用例,实现软件可靠性定量评估的有效方法。介绍了基于使用模型的统计测试方法,论述了使用模型的概念和特点,以及从使用模型中可以计算出的静态参数和它们在统计测试和软件开发中所起的作用。提出Markov链使用模型用于嵌入式软件的测试,从理论上得到嵌入式软件的可靠性。具体阐述了嵌入式软件的Markov链使用模,型自动生成测试模型的方法。同时使用改进的Kullback判别式探讨测试的可靠性问题,从理论上证明了测试链到使用链收敛的必然性。理论分析和初步的实例证明该方法是可行的和有前途的。     

基于UML的软件Markov链使用模型的构建

构建软件的使用模型是进行软件可靠性测试及软件可靠性评估的基础.近年来,如何由软件的UML模型构造软件的使用模型成为研究热点.对于大型的软件系统来说,应用现有方法构建的软件Markov链使用模型的状态空间过于庞大,模型描述困难,不利于测试用例的自动生成及软件可靠性评估.针对以上问题,提出了一种由UML模型构建Markov链使用模型的方法.该方法将场景的前置条件和后置条件作为Markov链使用模型的状态,将场景的执行及执行概率作为状态之间的转移及转移概率.与现有方法相比,新方法构建的Markov链使用模型的状态空间小且无需人为干预,而且可以很方便地生成测试输入从而进行可靠性测试.针对UML模型的有效性,提出了经过可靠性评估扩展的UML模型生成Markov链使用模型的验证算法.最后通过一个卫星控制系统的实例对新方法的性能进行了验证.     

基于软件层次化模型的软件测试数据生成

针对基于Markov链模型的软件测试技术在测试数据生成时不考虑软件的结构信息,生成的测试数据集对代码路径的覆盖能力以及缺陷检测能力都较低的问题,将统计测试与基于Markov链模型的测试相结合,提出了一种新的软件测试模型——软件层次化模型。该模型涵盖了软件与外部环境之间的交互,同时描述了软件内部结构信息。还给出了该模型测试数据集的生成算法：首先生成符合使用情况的测试序列,然后为测试序列生成覆盖软件内部结构的输入数据。通过针对示例软件的实验结果表明,与基于Markov链模型的测试方法对比,基于软件层次化模型的测试在满足软件测试充分性要求的同时,提高了测试数据集的代码路径覆盖能力和缺陷检测能力。     

基于Markov链路径使用模型的软件统计测试

探讨了建立基于路径使用的Markov链模型来分析模块内部代码结构的统计测试方法的可能性。提出将统计理论用于软件的结构测试，从理论上得出软件的结构可靠性结论。提出具有有限状态、离散时间序列的Markov链作为程序的使用模型和测试模型，使用Kullback判别式作为测试链收敛到使用链的判断准则，从理论上证明了测试链到使用链收敛的必然性。理论分析和初步的实验证明该方法是可行和有前途的。     

基于Markov链使用模型的软件可靠性测评方法研究

基于Markov链使用模型的软件统计测试是产生高效测试用例,实现软件可靠性定量评估的有效方法.论述了该方法中使用链与测试链的构建技术,基于使用模型的统计分析计算,基于测试链的软件可靠性评估,操作可靠性和使用可靠性评估,以及它们在实际应用中需要注意的若干问题.     

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

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

软件可靠性评估的重要抽样方法

基于统计测试的马尔可夫使用模型对软件可靠性评估提出了一种有效的估计方法.该方法利用重要抽样技术在保证可靠性估计无偏性的条件下,利用交叉熵度量操作剖面与零方差抽样分布之间的差异,通过启发式迭代过程调整各个状态之间的转移概率来修正测试剖面.从理论上证明了利用修正测试剖面测试估计的可靠性是方差为0的无偏估计.最后给出了软件可靠性估计的最优测试剖面生成的启发式迭代算法.仿真结果表明,该方法与模拟退火算法相比,能够明显降低估计的方差,在提高估计精度的同时加快统计测试速度.     

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

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

Measuring complexity and coverage of software specifications

Coverage testing in the context of Markov chain usage models refers to coverage of a model of the specification and profile of intended use, rather than coverage of the code that implements the specification. A new measure of specification complexity based on the number of statistically typical paths through the model of the specification is derived. Formulae are presented to compute bounds on the expected number of test cases required to achieve state and arc coverage. Formulae are presented to compare different usage models with respect to the amount of testing required to achieve coverage of typical paths. Convexity properties are established for these formulae to facilitate their use in optimization calculations that are used to generate transition probabilities for the usage models.     

Software dependability evaluation based on Markov usage models

A general technique for computing optimal state transition probabilities for software tests, based on a Markov usage model, is developed. The optimization criterion is maximum precision of unbiased dependability estimates derived from the test results. Three different dependability measures are considered: (i) risk, (ii) safety, and (iii) reliability. As input, pre-information on failure probabilities and losses in case of failure related with single operations is used. The optimization itself is done by means of a numerical procedure which is fast because of the convexity of the underlying stochastic optimization problem. The procedure can be improved by the construction of a distribution with a common lower bound on state transition probabilities; this distribution may also be used in the more general context of structural statistical testing of software.     

基于使用模型的软件测试路径选择及其性能分析

基于有向图理论对程序正文进行解析，同时对软件的使用模型做了初步的探讨，分析了具有Markov随机性质的软件使用过程和软件测试中的测试路径的选择策略，并对测试结果做出评价，给出软件的可靠性。     

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     

An event‐flow model of GUI‐based applications for testing

Graphical user interfaces (GUIs) are by far the most popular means used to interact with today's software. The functional correctness of a GUI is required to ensure the safety, robustness and usability of an entire software system. GUI testing techniques used in practice are resource intensive; model‐based automated techniques are rarely employed. A key reason for the reluctance in the adoption of model‐based solutions proposed by researchers is their limited applicability; moreover, the models are expensive to create. Over the past few years, the present author has been developing different models for various aspects of GUI testing. This paper consolidates all of the models into one scalable event‐flow model and outlines algorithms to semi‐automatically reverse‐engineer the model from an implementation. Earlier work on model‐based test‐case generation, test‐oracle creation, coverage evaluation, and regression testing is recast in terms of this model by defining event‐space exploration strategies (ESESs) and creating an end‐to‐end GUI testing process. Three such ESESs are described: for checking the event‐flow model, test‐case generation, and test‐oracle creation. Two demonstrational scenarios show the application of the model and the three ESESs for experimentation and application in GUI testing. Copyright © 2007 John Wiley & Sons, Ltd.     

面向复杂UML的Markov建模方法研究

软件可靠性测试技术是保证软件质量的重要研究内容,尤其是对航空航天、金融机构等高信度复杂软件尤为重要。在现有研究的基础上,针对复杂软件UML模型场景消息粒度过大导致构建的Markov链使用模型描述软件的真实度不够的问题,提出了一种基于多层嵌套组合片段UML模型的Markov链使用模型的构建方法,最后结合实例对研究提出的模型构建方法做出应用分析,说明了算法的可行性,为更有效地构建Markov链使用模型提供了指导。     

Application of Markov chains on image enhancement

Stochastic image processing tools have been widely used in digital image processing in order to improve the quality of the images. Markov process is one of the well-known mathematical modeling tools in stochastic theory. In this study, a Markov chain model has been developed and applied to image denoising. The transition probabilities were obtained from Fokker–Planck diffusion equation. According to the results, the proposed Markov chain model supplies very good peak signal to noise ratio values along with low computational cost.     

Using local transition probability models in Markov random fields for forest change detection

Change detection based on the comparison of independently classified images (i.e. post-classification comparison) is well-known to be negatively affected by classification errors of individual maps. Incorporating spatial-temporal contextual information in the classification helps to reduce the classification errors, thus improving change detection results. In this paper, spatial-temporal Markov Random Fields (MRF) models were used to integrate spatial-temporal information with spectral information for multi-temporal classification in an attempt to mitigate the impacts of classification errors on change detection. One important component in spatial-temporal MRF models is the specification of transition probabilities. Traditionally, a global transition probability model is used that assumes spatial stationarity of transition probabilities across an image scene, which may be invalid if areas have varying transition probabilities. By relaxing the stationarity assumption, we developed two local transition probability models to make the transition model locally adaptive to spatially varying transition probabilities. The first model called locally adjusted global transition model adapts to the local variation by multiplying a pixel-wise probability of change with the global transition model. The second model called pixel-wise transition model was developed as a fully local model based on the estimation of the pixel-wise joint probabilities. When applied to the forest change detection in Paraguay, the two local models showed significant improvements in the accuracy of identifying the change from forest to non-forest compared with traditional models. This indicates that the local transition probability models can present temporal information more accurately in change detection algorithms based on spatial-temporal classification of multi-temporal images. The comparison between the two local transition models showed that the fully local model better captured the spatial heterogeneity of the transition probabilities and achieved more stable and consistent results over different regions of a large image scene.     

基于模型的软件测试综述

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