A formal analysis of MCDC and RCDC test criteria

The Modified Condition Decision Coverage (MCDC) test criterion is a mandatory requirement for the testing of avionics software as per the DO‐178B standard. This paper presents a formal analysis for the three different forms of MCDC. In addition, a recently proposed test criterion, Reinforced Condition Decision Coverage (RCDC), has also been investigated in comparison with MCDC. In contrast with the earlier analysis approaches that have been based on empirical and probabilistic models, the principles of Boolean ogic are used here to study the fault detection effectiveness of the MCDC and RCDC criteria. Based on the properties of Boolean specifications, the analysis identifies the detection conditions for six kinds of faults. The results allow the measurement of the effort required in testing and the effectiveness of generated test sets satisfying the MCDC and RCDC criteria. Copyright © 2004 John Wiley & Sons, Ltd.     

A formal model of the software test process

A novel approach to model the system test phase of the software life cycle is presented. This approach is based on concepts and techniques from control theory and is useful in computing the effort required to reduce the number of errors and the schedule slippage under a changing process environment. Results from these computations are used, and possibly revised, at specific checkpoints in a feedback-control structure to meet the schedule and quality objectives. Two case studies were conducted to study the behavior of the proposed model. One study reported here uses data from a commercial project. The outcome from these two studies suggests that the proposed model might well be the first significant milestone along the road to a formal and practical theory of software process control.     

A formal analysis of stopping criteria of decomposition methods for support vector machines

In a previous paper, the author (2001) proved the convergence of a commonly used decomposition method for support vector machines (SVMs). However, there is no theoretical justification about its stopping criterion, which is based on the gap of the violation of the optimality condition. It is essential to have the gap asymptotically approach zero, so we are sure that existing implementations stop in a finite number of iterations after reaching a specified tolerance. Here, we prove this result and illustrate it by two extensions: /spl nu/-SVM and a multiclass SVM by Crammer and Singer (2001). A further result shows that, in final iterations of the decomposition method, only a particular set of variables are still being modified. This supports the use of the shrinking and caching techniques in some existing implementations. Finally, we prove the asymptotic convergence of a decomposition method for this multiclass SVM. Discussions on the difference between this convergence proof and the one in another paper by Lin are also included.     

A formal approach to software error removal

There is a dichotomy of opinion on the use of software testing versus formal verification in software development. Testing has been the accepted method for detecting and removing errors and has played a significant error removal role. Formal verification has only recently matured into accepted practice but shows the potential for playing an even more significant error prevention role. The Cleanroom software development process which has been developed by the IBM Federal Systems Division combines both ideas into an effective development tool. Software engineering methods based on functional verification support the production of software with sufficient quality to forego traditional unit or structural testing. Statistical methods are introduced that define objective and formal strategies for product or functional testing. The synergism between the two ideas results in software with fewer errors which are both easier to find and to fix and in products with exceptional operating characteristics. Error prevention, not removal, is the key and the only viable approach to any sustained software quality growth. The Cleanroom development method and its impact on the error prevention and removal processes are covered in this paper. The results from its use for software development are also discussed.     

A formal framework for software product lines

ContextA Software Product Line is a set of software systems that are built from a common set of features. These systems are developed in a prescribed way and they can be adapted to fit the needs of customers. Feature models specify the properties of the systems that are meaningful to customers. A semantics that models the feature level has the potential to support the automatic analysis of entire software product lines.ObjectiveThe objective of this paper is to define a formal framework for Software Product Lines. This framework needs to be general enough to provide a formal semantics for existing frameworks like FODA (Feature Oriented Domain Analysis), but also to be easily adaptable to new problems.MethodWe define an algebraic language, called SPLA, to describe Software Product Lines. We provide the semantics for the algebra in three different ways. The approach followed to give the semantics is inspired by the semantics of process algebras. First we define an operational semantics, next a denotational semantics, and finally an axiomatic semantics. We also have defined a representation of the algebra into propositional logic.ResultsWe prove that the three semantics are equivalent. We also show how FODA diagrams can be automatically translated into SPLA. Furthermore, we have developed our tool, called AT, that implements the formal framework presented in this paper. This tool uses a SAT-solver to check the satisfiability of an SPL.ConclusionThis paper defines a general formal framework for software product lines. We have defined three different semantics that are equivalent; this means that depending on the context we can choose the most convenient approach: operational, denotational or axiomatic. The framework is flexible enough because it is closely related to process algebras. Process algebras are a well-known paradigm for which many extensions have been defined.     

Applying formal software synthesis

A software synthesis method that combines elements of graphical tools, specification writing, and code construction is discussed. Practical applications of the components and efforts to integrate them into a conceptually coherent prototype environment are described. The hallmarks of the approach are the use of formal methods and a general-purpose inference engine, supported by a comprehensive, interactive development environment. The development model is a formal method, but it differs from other formal approaches in that its notations are used primarily to represent programming knowledge and support automated code generation. The performance of the system is also described     

A formal framework for on-line software version change

The usual way of installing a new version of a software system is to shut down the running program and then install the new version. This necessitates a sometimes unacceptable delay during which service is denied to the users of the software. An online software replacement system replaces parts of the software while it is in execution, thus eliminating the shutdown. While a number of implementations of online version change systems have been described in the literature, little investigation has been done on its theoretical aspects. We describe a formal framework for studying online software version change. We give a general definition of validity of an online change, show that it is in general undecidable and then develop sufficient conditions for ensuring validity for a procedural language     

A formal method for building concurrent real-time software

Developing concurrent real-time programs is one of computer science's greatest challenges. Not only is such software expensive to manufacture, but its role in safety-critical systems demands that it be correct. Formal methods of program specification and refinement could strengthen the mathematical precision used to develop such software. Nevertheless, formalisms that embrace both real-time and concurrency requirements are only just emerging. The Quartz method treats time and functional behavior with equal importance in the development process. The authors argue that by modeling program development in a unified framework, we can increase our confidence in the correctness of real-time concurrent code     

A formal approach to AADL model-based software engineering

International Journal on Software Tools for Technology Transfer - Formal methods have become a recommended practice in safety-critical software engineering. To be formally verified, a system should...     

A formal process for evaluating COTS software products

A software product evaluation process grounded in mathematics and decision theory can effectively determine product quality and suitability with less risk and at lower cost than conventional methods     

A formal software development approach using refinement calculus

The advantage of COOZ(Complete Object-Oriented Z) is to specify large scale software,but it does not support refinement calculus.Thus its application is comfined for software development.Including refinement calculus into COOZ overcomes its disadvantage during design and implementation.The separation between the design and implementation for structure and notation is removed as well .Then the software can be developed smoothly in the same frame.The combination of COOZ and refinement calculus can build object-oriented frame,in which the specification in COOZ is refined stepwise to code by calculus.In this paper,the development model is established.which is based on COOZ and refinement calculus.Data refinement is harder to deal with in a refinement tool than ordinary algorithmic refinement,since data refinement usually has to be done on a large program component at once.As to the implementation technology of refinement calculus,the data refinement calculator is constructed and an approach for data refinement which is based on data refinement calculus and program window inference is offered.     

A formal evaluation of data flow path selection criteria

The authors report on the results of their evaluation of path-selection criteria based on data-flow relationships. They show how these criteria relate to each other, thereby demonstrating some of their strengths and weaknesses. A subsumption hierarchy showing their relationship is presented. It is shown that one of the major weaknesses of all the criteria is that they are based solely on syntactic information and do not consider semantic issues such as infeasible paths. The authors discuss the infeasible-path problem as well as other issues that must be considered in order to evaluate these criteria more meaningfully and to formulate a more effective path-selection criterion     

A comparison of tools for teaching formal software verification

We compare four tools regarding their suitability for teaching formal software verification, namely the Frege Program Prover, the Key system, Perfect Developer, and the Prototype Verification System (PVS). We evaluate them on a suite of small programs, which are typical of courses dealing with Hoare-style verification, weakest preconditions, or dynamic logic. Finally we report our experiences with using Perfect Developer in class.     

基于软硬件协同形式验证的固件漏洞分析技术

为了系统高效地分析固件中潜在的安全隐患,提出了一种基于行为时序逻辑 TLA 的软硬件协同形式验证方法。通过对固件工作过程中的软硬件交互机制进行形式建模分析,在动态调整攻击模型的基础上,发现了固件更新过程中存在的安全漏洞,并通过实验证实了该漏洞的存在,从而证明了形式验证方法的可靠性。     

Software reliability analysis and choice of software reliability criteria

Functional reliability of computer software is considered using fuzzy automaton representation of software systems.Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 46–60, March–April, 1992.     

基于可拓学的自适应软件形式化方法

可拓学的核心是建立灵活变通地应对不确定变化和灵感涌现的适应性模型。讨论引入可拓理论去描述、分析和评价软件系统的自适应性质、范围和程度的可能性。用基元描述软件实体,将软件系统构造成基元网,利用拓展分析、可拓变换和优度评价等定性与定量相结合的方法揭示了自适应软件系统的动态性质,并形成了一种自适应软件形式化方法。     

A feature-based classification of formal verification techniques for software models

Software and Systems Modeling - Software models are the core development artifact in model-based engineering (MBE). The MBE paradigm promotes the use of software models to describe structure and...     

基于形式概念分析的软件子系统构建方法及应用

在分析当前软件工程中使用UML方法划分软件子系统方法,存在很大的主观因素的基础上,引入形式概念分析(FCA)理论解决这一不足,通过UML可视化建模得到用例图后生成用例的形式背景,进而构造概念格,最后通过对概念格的分析,完成对软件子系统的划分。     

Introduction to formal methods of software design

The potential benefits of using formal methods in the design of software are discussed. Concepts are illustrated by several small examples, with the objective of helping to bridge the gap between theory and practice. The paper introduces and explains some of the terminology, symbols and notation for the discrete mathematics used in the formal methods literature, intended to assist the reader in further study.