Test Synthesis from UML Models of Distributed Software

The object-oriented software development process is increasingly used for the construction of complex distributed systems. In this context, behavior models have long been recognized as the basis for systematic approaches to requirements capture, specification, design, simulation, code generation, testing, and verification. Two complementary approaches for modeling behavior have proven useful in practice: interaction-based modeling (e.g., UML sequence diagrams) and state-based modeling (e.g., UML statecharts). Building on formal V&V techniques, in this article we present a method and a tool for automated synthesis of test cases from scenarios and a state-based design model of the application, remaining entirely within the UML framework. The underlying "on the fly" test synthesis algorithms are based on the input/output labeled transition system formalism, which is particularly appropriate for modeling applications involving asynchronous communication. The method is eminently compatible with classical OO development processes since it can be used to synthesize test cases from the scenarios used in early development stages to model global interactions between actors and components, instead of these test cases being derived manually. We illustrate the system test synthesis process using an air traffic control software example     

Model-based test generation using extended symbolic grammars

A novel, model-based test case generation approach for validating reactive systems, especially those supporting richly structured data inputs and/or interactions, is presented. Given an executable system model and an extended symbolic grammar specifying plausible system inputs, the approach performs a model-based simulation to (i) ensure the consistency of the model with respect to the specified inputs, and (ii) generate corresponding test cases for validating the system. The model-based simulation produces a state transition diagram (STD) automatically justifying the model runtime behaviors within the test case coverage. The STD can further be transformed to produce an evolved symbolic grammar, which can then be used to incrementally generate a refined set of test cases. As a case study, we present a live sequence chart (LSC) model-based test generator, named LCT in short, for LSC simulation and consistency testing. The evolved symbolic grammar produced by the simulator can either be used to generate practical test cases for software testing, or be further refined by applying our model-based test generation approach again with additional test coverage criteria. We further show that LSCs can also be used to specify and test certain temporal system properties during the model simulation. Their satisfaction, reflected in the STD, can either be served as a directive for selective test generation, or a basis for further temporal property model checking.     

Generating semantically valid test inputs using constrained input grammars

ContextGenerating test cases based on software input interface is a black-box testing technique that can be made more effective by using structured input models such as input grammars. Automatically generating grammar-based test inputs may lead to structurally valid but semantically invalid inputs that may be rejected in early semantic error checking phases of a system under test.ObjectiveThis paper aims to introduce a method for specifying a grammar-based input model with the model’s semantic constraints to be used in the generation of positive test inputs. It is also important that the method can generate effective test suites based on appropriate grammar-based coverage criteria.MethodFormal specification of both input structure and input semantics provides the opportunity to use model instantiation techniques to create model instances that satisfy all specified constraints. The input interface of a subject system can be specified using a high-level specification scheme such as attribute grammars, and a transformation function from this scheme to an instantiable formal modeling language can generate the desired model instances.ResultsWe propose a declarative grammar-based input specification method that is based on a variation of attribute grammars and allows the user to specify input constraints in addition to input structure. The model can be instantiated automatically to generate structurally and semantically valid test inputs. The proposed method has the capability to specify test requirements and coverage criteria and use them to generate valid test suites that satisfy test coverage criteria requirements.ConclusionThe work presented in this paper provides a black-box test generation method for grammar-based software inputs that can automatically generate criteria-covering test suites.     

SimFuzz: Test case similarity directed deep fuzzing

Fuzzing is widely used to detect software vulnerabilities. Blackbox fuzzing does not require program source code. It mutates well-formed inputs to produce new ones. However, these new inputs usually do not exercise deep program semantics since the possibility that they can satisfy the conditions of a deep program state is low. As a result, blackbox fuzzing is often limited to identify vulnerabilities in input validation components of a program. Domain knowledge such as input specifications can be used to mitigate these limitations. However, it is often expensive to obtain such knowledge in practice. Whitebox fuzzing employs heavy analysis techniques, i.e., dynamic symbolic execution, to systematically generate test inputs and explore as many paths as possible. It is powerful to explore new program branches so as to identify more vulnerabilities. However, it has fundamental challenges such as unsolvable constraints and is difficult to scale to large programs due to path explosion. This paper proposes a novel fuzzing approach that aims to produce test inputs to explore deep program semantics effectively and efficiently. The fuzzing process comprises two stages. At the first stage, a traditional blackbox fuzzing approach is applied for test data generation. This process is guided by a novel test case similarity metric. At the second stage, a subset of the test inputs generated at the first stage is selected based on the test case similarity metric. Then, combination testing is applied on these selected test inputs to further generate new inputs. As a result, less redundant test inputs, i.e., inputs that just explore shallow program paths, are created at the first stage, and more distinct test inputs, i.e., inputs that explore deep program paths, are produced at the second stage. A prototype tool SimFuzz is developed and evaluated on real programs, and the experimental results are promising.     

Test generation from state based use case models

We present a strategy for the automatic generation of test cases from parametrised use case templates that capture control flow, state, input and output. Our approach allows test scenario selection based on particular traces or states of the model. The templates are internally represented as CSP processes with explicit input and output alphabets, and test generation is expressed as counter-examples of refinement checking, mechanised using the FDR tool. Soundness is addressed through an input–output conformance relation formally defined in the CSP traces model. This purely process algebraic characterisation of testing has some potential advantages, mainly an easy automation of conformance verification and test case generation via model checking, without the need to develop any explicit algorithm.     

Symbolic PathFinder: integrating symbolic execution with model checking for Java bytecode analysis

Symbolic PathFinder (SPF) is a software analysis tool that combines symbolic execution with model checking for automated test case generation and error detection in Java bytecode programs. In SPF, programs are executed on symbolic inputs representing multiple concrete inputs and the values of program variables are represented by expressions over those symbolic inputs. Constraints over these expressions are generated from the analysis of different paths through the program. The constraints are solved with off-the-shelf solvers to determine path feasibility and to generate test inputs. Model checking is used to explore different symbolic program executions, to systematically handle aliasing in the input data structures, and to analyze the multithreading present in the code. SPF incorporates techniques for handling input data structures, strings, and native calls to external libraries, as well as for solving complex mathematical constraints. We describe the tool and its application at NASA, in academia, and in industry.     

Testing in context: framework and test derivation

The paper addresses the problem of testing a component embedded within a given modular system. A context of the component represents the rest of the system and serves as its operational or testing environment. A framework for testing in context is presented based on the model of a system of communicating finite state machines. In particular, the problems of test executability and fault propagation in the presence of the context are identified and discussed. The proposed solution to these problems consists in computing so-called approximation of the specification in context, i.e. the FSM model of the component's properties that can be controlled and observed through the context. The approximation assures executability of tests and fault propagation through the context and serves as a base for test derivation. A conformance relation used for test derivation is shown to be the reduction relation between an implementation and the approximation of the given specification. This relation requires that the implementation produces a (sub)set of output sequences that can be produced by its specification in response to every input sequence. An approach to test generation for the reduction relation and deterministic implementations is also presented.     

基于有限自动机的面向对象软件规约测试

面向对象方法已经逐步代替基于过程的方法成为软件开发的主流,然而面向对象软件的测试和维护代价却并没有因此而减少.虽然在面向对象软件测试方面做了很多的研究工作,但是大多数针对面向对象软件测试的研究都是针对单一类的测试,而不是更高层次上的对面向对象软件规约的测试.提出了一种基于有限自动机的测试框架以测试面向对象软件规约中存在的不完整性和不一致性.该方法有别于公式证明和模型检查,它直接依据可执行的有限自动机来执行测试而不是人工的推导公式证明也不产生大量的状态空间.     

Model checking large software specifications

In this paper, we present our experiences in using symbolic model checking to analyze a specification of a software system for aircraft collision avoidance. Symbolic model checking has been highly successful when applied to hardware systems. We are interested in whether model checking can be effectively applied to large software specifications. To investigate this, we translated a portion of the state-based system requirements specification of Traffic Alert and Collision Avoidance System II (TCAS II) into input to a symbolic model checker (SMV). We successfully used the symbolic model checker to analyze a number of properties of the system. We report on our experiences, describing our approach to translating the specification to the SMV language, explaining our methods for achieving acceptable performance, and giving a summary of the properties analyzed. Based on our experiences, we discuss the possibility of using model checking to aid specification development by iteratively applying the technique early in the development cycle. We consider the paper to be a data point for optimism about the potential for more widespread application of model checking to software systems     

面向媒体时序描述的带时间自动机的自动构造方法

依据有穷状态自动机模型,面向程序规范的并发系统和分布式系统测试方法的研究已经取得许多结果。由于特殊的实时和同步要求,这些结果不能直接应用于分布式多媒体软件系统的测试。为此,作者提出一种面向媒体对象时序描述的地间自动机（Ｔｉｍｅｄ ａｕｔｏｍａｔａ）的自动构造方法,根据带时间自动机,对分布式多媒体软件系统进行非确定性测试时,可以较容易地判断运行结果正确与否;在进行确定性测试时,可以辅助自动生成测试用     

CRDT协议的TLA+描述与验证

无冲突复制数据类型（conflict-free replicated data types，简称CRDT）是一种封装了冲突消解策略的分布式复制数据类型，它能保证分布式系统中副本节点间的强最终一致性，即执行了相同更新操作的副本节点具有相同的状态.CRDT协议设计精巧，不易保证其正确性.旨在采用模型检验技术验证一系列CRDT协议的正确性.具体而言，构建了一个可复用的CRDT协议描述与验证框架，包括网络通信层、协议接口层、具体协议层与规约层.网络通信层描述副本节点之间的通信模型，实现了多种类型的通信网络.协议接口层为已知的CRDT协议（分为基于操作的协议与基于状态的协议）提供了统一的接口.在具体协议层，用户可以根据协议的需求选用合适的底层通信网络.规约层则描述了所有CRDT协议都需要满足的强最终一致性与最终可见性（所有的更新操作最终都会被所有的副本节点接收并处理）.使用TLA+形式化规约语言实现了该框架，然后以Add-Wins Set复制数据类型为例，展示了如何使用框架描述具体协议，并使用TLC模型检验工具验证协议的正确性.     

Verifying data refinements using a model checker

In this paper, we consider how refinements between state-based specifications (e.g., written in Z) can be checked by use of a model checker. Specifically, we are interested in the verification of downward and upward simulations which are the standard approach to verifying refinements in state-based notations. We show how downward and upward simulations can be checked using existing temporal logic model checkers.In particular, we show how the branching time temporal logic CTL can be used to encode the standard simulation conditions. We do this for both a blocking, or guarded, interpretation of operations (often used when specifying reactive systems) as well as the more common non-blocking interpretation of operations used in many state-based specification languages (for modelling sequential systems). The approach is general enough to use with any state-based specification language, and we illustrate how refinements between Z specifications can be checked using the SAL CTL model checker using a small example.     

Software assurance by bounded exhaustive testing

Bounded exhaustive testing (BET) is a verification technique in which software is automatically tested for all valid inputs up to specified size bounds. A particularly interesting case of BET arises in the context of systems that take structurally complex inputs. Early research suggests that the BET approach can reveal faults in small systems with inputs of low structural complexity, but its potential utility for larger systems with more complex input structures remains unclear. We set out to test its utility on one such system. We used Alloy and TestEra to generate inputs to test the Galileo dynamic fault tree analysis tool, for which we already had both a formal specification of the input space and a test oracle. An initial attempt to generate inputs using a straightforward translation of our specification to Alloy did not work well. The generator failed to generate inputs to meaningful bounds. We developed an approach in which we factored the specification, used TestEra to generate abstract inputs based on one factor, and passed the results through a postprocessor that reincorporated information from the second factor. Using this technique, we were able to generate test inputs to meaningful bounds, and the inputs revealed nontrivial faults in the Galileo implementation, our specification, and our oracle. Our results suggest that BET, combined with specification abstraction and factoring techniques, could become a valuable addition to our verification toolkit and that further investigation is warranted.     

Exploring alternatives for transition verification

When an implementation under test (IUT) is state-based, and its expected abstract behavior is given in terms of a finite state machine (FSM), a checking sequence generated from a specification FSM and applied to an IUT for testing can provide us with high-level confidence in the correct functional behavior of our implementation. One of the issues here is to generate efficient checking sequences in terms of their lengths. As a major characteristics, a checking sequence must contain all β-sequences for transition verification. In this paper, we discuss the possibility of reducing the lengths of checking sequences by making use of the invertible transitions in the specification FSM to increase the choice of β-sequences to be considered for checking sequence generation. We present a sufficient condition for adopting alternative β-sequences and illustrate typical ways of incorporating these alternative β-sequences into existing methods for checking sequence generation to reduce the lengths. Compared to the direct use of three existing methods, our experiments show that most of the time the saving gained by adopting alternative β-sequences falls in the range of 10–40%.     

Checking experiments for stream X-machines

Stream X-machines are a state based formalism that has associated with it a particular development process in which a system is built from trusted components. Testing thus essentially checks that these components have been combined in a correct manner and that the orders in which they can occur are consistent with the specification. Importantly, there are test generation methods that return a checking experiment: a test that is guaranteed to determine correctness as long as the implementation under test (IUT) is functionally equivalent to an unknown element of a given fault domain Ψ. Previous work has show how three methods for generating checking experiments from a finite state machine (FSM) can be adapted to testing from a stream X-machine. However, there are many other methods for generating checking experiments from an FSM and these have a variety of benefits that correspond to different testing scenarios. This paper shows how any method for generating a checking experiment from an FSM can be adapted to generate a checking experiment for testing an implementation against a stream X-machine. This is the case whether we are testing to check that the IUT is functionally equivalent to a specification or we are testing to check that every trace (input/output sequence) of the IUT is also a trace of a nondeterministic specification. Interestingly, this holds even if the fault domain Ψ used is not that traditionally associated with testing from a stream X-machine. The results also apply for both deterministic and nondeterministic implementations.     

Game-theoretic simulation checking tool

Model checking is one of the most commonly used methods for checking program correctness. In this method, one verifies a program model given by the Kripke structure (labeled transition system) rather than the program itself. The specification is usually given as a temporal logic formula. In many subtasks of model checking, it is necessary to use relations that are defined on the set of program models and preserve the satisfiability of temporal logic formulas. There exist many relations of this kind, which are called simulation relations. In the present paper, we introduce a tool designed to check a wide class of simulation relations between finite models of programs. This tool is based on the simulation checking game-theoretic approach. The tool consists of two components. The first component is the formal language, which allows one to define various simulation relations in terms of an antagonistic two-player game. The second component is a software tool that, given two labeled transition systems and simulation definition, is able to check whether this simulation is satisfied between these labeled transition systems.     

基于时序规范的测试预言自动生成技术评述

测试预言是一种检验待测系统在特定执行下是否正确运行的方法,是软件测试过程中必不可少的阶段,也是软件测试研究的薄弱环节.针对反应式实时系统,我们使用时序规范来描述系统性质.本文详细阐述了基于时序规范的测试预言自动生成技术的研究现状,并按预言生成的理论基础将预言生成方法分为四类进行介绍.最后,并分析了基于时序规范的的测试预言生成面临的困难.     

基于UML规格说明测试用例生成工具

利用UML状态图,采用基于状态的测试数据生成标准生成测试用例。其中UML状态图是测试用例生成的关键部分,在某种意义上,UML状态图能够图容易生成测试用例。     

Establishing flight software reliability: testing,model checking,constraint-solving,monitoring and learning

In this paper we discuss the application of a range of techniques to the verification of mission-critical flight software at NASA’s Jet Propulsion Laboratory. For this type of application we want to achieve a higher level of confidence than can be achieved through standard software testing. Unfortunately, given the current state of the art, especially when efforts are constrained by the tight deadlines and resource limitations of a flight project, it is not feasible to produce a rigorous formal proof of correctness of even a well-specified stand-alone module such as a file system (much less more tightly coupled or difficult-to-specify modules). This means that we must look for a practical alternative in the area between traditional testing and proof, as we attempt to optimize rigor and coverage. The approaches we describe here are based on testing, model checking, constraint-solving, monitoring, and finite-state machine learning, in addition to static code analysis. The results we have obtained in the domain of file systems are encouraging, and suggest that for more complex properties of programs with complex data structures, it is possibly more beneficial to use constraint solvers to guide and analyze execution (i.e., as in testing, even if performed by a model checking tool) than to translate the program and property into a set of constraints, as in abstraction-based and bounded model checkers. Our experience with non-file-system flight software modules shows that methods even further removed from traditional static formal methods can be assisted by formal approaches, yet readily adopted by test engineers and software developers, even as the key problem shifts from test generation and selection to test evaluation.     

Unit Test Data Generation for C Using Rule-Directed Symbolic Execution

Unit testing is widely used in software development. One important activity in unit testing is automatic test data generation. Constraint-based test data generation is a technique for automatic generation of test data, which uses symbolic execution to generate constraints. Unit testing only tests functions instead of the whole program, where individual functions typically have preconditions imposed on their inputs. Conventional symbolic execution cannot detect these preconditions, let alone converting these preconditions into constraints. To overcome these limitations, we propose a novel unit test data generation approach using rule-directed symbolic execution for dealing with functions with missing input preconditions. Rule-directed symbolic execution uses predefined rules to detect preconditions in the individual function, and generates constraints for inputs based on preconditions. We introduce implicit constraints to represent preconditions, and unify implicit constraints and program constraints into integrated constraints. Test data generated based on integrated constraints can explore previously unreachable code and help developers find more functional faults and logical faults. We have implemented our approach in a tool called CTS-IC, and applied it to real-world projects. The experimental results show that rule-directed symbolic execution can find preconditions (implicit constraints) automatically from an individual function. Moreover, the unit test data generated by our approach achieves higher coverage than similar tools and efficiently mitigates missing input preconditions problems in unit testing for individual functions.