FSM-based incremental conformance testing methods

The development of appropriate test cases is an important issue for conformance testing of protocol implementations and other reactive software systems. A number of methods are known for the development of a test suite based on a specification given in the form of a finite state machine. In practice, the system requirements evolve throughout the lifetime of the system and the specifications are modified incrementally. We adapt four well-known test derivation methods, namely, the HIS, W, Wp, and UIOv methods, for generating tests that would test only the modified parts of an evolving specification. Some application examples and experimental results are provided. These results show significant gains when using incremental testing in comparison with complete testing, especially when the modified part represents less than 20 percent of the whole specification.     

The softest program test system

This paper reviews the current status of both research and commercial testing systems, and addresses the features necessary for a commercial test system. These include test case specification, test data generation, testbed generation, program instrumentation, automatic test execution and validation, as well as dynamic analysis of control and data flow. Of particular value is the linking of the details of the test to the program specification by means of an assertion language. These and other features are then described within the contest of , an integrated system for testing Assembler, , and / 1 programs in a simulated test environment. This system is now being used to validate programs in a test laboratory.     

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.     

基于TTCN-3的SIP一致性测试

应用层控制协议SIP（Session Initiation Protocol）已被用于在IP网络中建立、修改和终止多个参与者参加的多媒体会话.为了保证SIP的不同实现之间能够可靠地进行通信,需要对其进行严格的一致性测试并检验SIP实现是否与标准一致.ETSI（European Telecom munications Standards Institute）开发的下一代测试描述语言TTCN-3（Testing and Test Control Notation version 3）在SIP一致性测试中起着重要的作用.本文描述了通用TTCN-3测试系统的设计和实现以及使用TTCN-3对SIP进行测试的情况.     

Combining Testing with Formal Specifications: A Case Study

This paper describes our experience specifying, implementing, and validating a record-oriented text editor similar to one discussed in [7]. Algebraic axioms served as the specification notation; and the implementation was tested with a compiler-based system that uses the axioms to test implementations with a finite collection of test cases. Formal specifications were sometimes difficult to produce, but helped reveal errors during unit testing. Thorough exercising of the implementations by the specifications resulted in few errors persisting until integration.     

Complete open-state testing of limitedly nondeterministic systems

An approach to the problem of complete testing is proposed. Testing is interpreted as the check of an implementation’s conformance to the given requirements described by a specification. The completeness means that a test suite finds all the possible implementation errors. In practice, testing must end in a finite amount of time. In the general case, the requirements of completeness and finiteness contradict each other. However, finite complete test suites can be constructed for certain classes of implementations and specifications provided that there are specific test capabilities. Test algorithms are proposed for finite specifications and finite implementations with limited nondeterminism for the case of open-state testing. The complexity of those algorithms is estimated.     

A generic interoperability testing framework and a systematic development process for automated interoperability testing

Interoperability is a prerequisite to allow users to access systems implemented by different vendors seamlessly. A good baseline to achieve interoperability is the implementation of a common set of standards. However, this is often not sufficient as different implementations of a standard are not necessarily interoperable. Therefore, different implementations of systems need to be assessed for interoperability by applying interoperability testing. In this article, we present a generic framework that enables automated interoperability testing with message checks, which assess the compliance of messages exchanged between systems. The goal of this framework is the provision of a basic functionality of interoperability test entities, the definition of a generic interoperability test environment, and guidelines for the specification of automated interoperability tests. The framework also considers aspects related to interoperability testing including verdicts, automation, and limitations of the system under test. Through the application of the framework, interoperability of systems can be assessed, systems can be validated, and standards can be improved. In addition, we present a systematic development process for automated interoperability tests to formalize the development and specification of an interoperability test system. We also consider aspects and critical issues, which are important for the development of a complete interoperability test system. The framework and the process are language and system technology independent. We present their application in a case study that includes interoperability tests for the Internet Protocol Multimedia Subsystem (IMS) using the Testing and Test Control Notation Version 3 (TTCN-3).     

Complete deterministic stream X-machine testing

One of the strengths of using stream X-machines to specify a system is that, under certain well defined conditions, it is possible to produce a test set that is guaranteed to determine the correctness of an implementation. However, the existing method assumes that the implementation of each processing function is proved to be correct before the actual testing can take place, so it only test the system integration. This paper presents a new method for generating test sets from a deterministic stream X-machine specification that generalises the existing integration testing method. This method no longer requires the implementations of the processing functions to be proved correct prior to the actual testing. Instead, the testing of the processing functions is performed along with the integration testing.Accepted in revised form 27 February 2004 by D.A. Duce     

Interaction semantics with refusals,divergence, and destruction

Formal methods for testing the conformance of a software system to its specification are considered. The interaction semantics determines the testing capabilities, which are reduced to the observation of actions and refusals (absence of actions). The semantics is parameterized by the families of observable and unobservable refusals. The concept of destruction as a prohibited action that should be avoided in the course of interaction is introduced. The concept of safe testing, the implementation safety hypothesis, safe conformance, and generation of a complete test suite based on the specification are defined. Equivalences of traces, specifications, safety relations, and interaction semantics are examined. A specification completion is proposed that can be used to remove from the specification irrelevant (not included in the safely testable implementations) and nonconformal specification traces is proposed. The concept of total testing that detects all the errors in the implementation (rather than at least one error as is the case in complete testing) is introduced. On the basis of the analysis of dependences between errors, a method for the minimization of test suites is proposed. The problem of preserving the conformance under composition (the monotonicity of conformance) is investigated, and a monotone transformation of the specification solving this problem is proposed.     

Functional conformance testing of graphics software using a configurable reference system

This paper introduces a scheme for conformance checking of GKS implementations with the given GKS standard specification[1] based on functional black box testing. Specific testing problems caused by the nature of graphics systems and a solution are presented. Thereby emphasis is laid on a software generation technique which allows to configure reference implementations from a suitable specification of GKS. The reference implementation is used to produce correct reference data the contents and formats of which are adjusted for the particular candidate implementation.     

A framework for the specification of test cases for real-time distributed systems

The OSI conformance testing methodology and framework (CTMF) is a well established standard which defines and regulates the conformance testing procedure for protocol implementations. Conformance testing is meant to be functional black-box testing. Besides concepts and terminology, the CTMF standardizes testing architectures and the Tree and Tabular Combined Notation (TTCN) test specification language. As more and more distributed systems such as multimedia, safety-critical and real-time systems rely on the timely availability of information, testing of real-time requirements becomes a serious issue, too. Unfortunately, testing real-time and other non-functional requirements (performance and reliability) are outside the scope of CTMF. In this paper we present an extension of CTMF which allows us to specify test cases for testing real-time requirements. The extension includes a generic testing architecture and a notation for test specification, which is called real-time TTCN.     

Integration of “Components” to Test Software Components

We present an ongoing research project aimed at developing a framework for component-based testing, in which we re-use and suitably combine some existing tools: the system architecture and the components are specified by the UML, and specifically the recently proposed UML Components methodology; the test cases are derived by applying the Cow_Suite, an environment for UML-based testing, previously conceived for the integration testing of OO systems; and the tests are codified and executed within the CDT, a framework under development, allowing for the decoupling between the abstract specification of tests, which is made against an architectural model, and their concrete execution, which needs to take into account the component implementations.     

Trace analysis for conformance and arbitration testing

The authors explore a testing approach where the concern for selecting the appropriate test input provided to the implementation under test (IUT) is separated as much as possible from the analysis of the observed output. Particular emphasis is placed on the analysis of the observed interactions of the IUT in order to determine whether the observed input/output trace conforms to the IUT's specification. The authors consider this aspect of testing with particular attention to testing of communication protocol implementations. Various distributed test architectures are used for this purpose, where partial input/output traces are observable by local observers at different interfaces. The error-detection power of different test configurations is determined on the basis of the partial trace visible to each local observer and their global knowledge about the applied test case. The automated construction of trace analysis modules from the formal specification of the protocol is also discussed. Different transformations of the protocol specification may be necessary to obtain the reference specification, which can be used by a local or global observer for checking the observed trace. Experience with the construction of an arbiter for the OSI (open systems interconnection) transport protocol is described     

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.     

Achieving dependability throughout the development process: adistributed software experiment

Distributed software engineering techniques and methods for improving the specification and testing phases are considered. To examine these issues, an experiment was performed using the design diversity approach in the specification, design, implementation, and testing of distributed software. In the experiment, three diverse formal specifications were used to produce multiple independent implementations of a distributed communication protocol in Ada. The problems encountered in building complex concurrent processing systems in Ada were also studied. Many pitfalls were discovered in mapping the formal specifications into Ada implementations     

邻居发现协议的形式化测试

Neighbor Discovery(邻居发现 ,ND)协议是下一代互联网协议 IPv6协议中的一个重要组成部分 .随 IPv6在我国的推广应用 ,各种设备蜂拥而来 ,由于各协议实现厂家对协议的不同理解 ,通信设备的协议非一致性问题将日趋严重 ,为了检查各个不同生产厂家的实现是否与标准文本相一致 ,进而确保不同厂家的 IPv6实现之间能够互操作 ,提出了一种协议一致性测试的方法 ,并开发了 IPv6协议实现一致性测试系统 .给出了该测试系统的结构 ,并利用自定义的一种形式化描述语言 ,实现了邻居发现协议一致性测试集的形式化 .并通过对 Solaris8上的 IPv6协议实现进行测试 ,给出测试报告和结果分析 .     

IPv6协议一致性测试系统

随着IPv6协议在我国的推广应用，各种相关设备蜂拥而来，由于各协议实现厂家对协议的不同理解，使得通信设备的协议非一致性问题日趋严重，为检查各个不同生产厂家的IPv6实现是否与标准文本相一致，进而确保不同厂家的IPv6实现之间能够互操作，开发一种IPv6协议一致性测试系统，并利用自定义的一种形式化描述语言，实现IPv6相关协议一致性测试集的形式化，文中给出该测试的结构，通过一个测试例介绍测试集的形式化和测试实现过程，使用该测试系统对多种IPv6协议实现进行测试，发现许不一致问题，为协议实现厂家提供了修改意见，作为例子，给出一种UnixIPv6邻居发现协议实现的测试结果分析。     

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

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

Specification-based Testing for Gui-based Applications

The development of GUI-based applications has raised a lot of new issues, one of them being how to automate effective testing for applications with complicated graphical user interactions. In this paper, we discuss the architectural issues and the implementation concerns of our approach to an automated specification-based testing technique for GUI-based applications. This approach is carried out by enriching existing architecture for automated specification-based testing. An essential part of our work is a visual environment to obtain test specifications. This environment pre-runs the Application Under Test (AUT) under its own control, with two prominent characteristics: First, testers can edit test specifications within the true GUI environment of the AUT. Second, the recorded input and output contain the same references as those in the AUT, so that the test cases generated from the edited specification can be used directly by test oracles during the automated testing procedure.We present our running prototype of a visual specification editor that allows users to graphically manipulate test specifications when these specifications are given in term of Finite State Machines (FSM) and the implementations of the AUT are GUI-based Java applications.     

Hard-to-use evaluation criteria for software engineering

Most evaluations of software tools and methodologies could be called “public relations,” because they are subjective arguments given by proponents. The need for markedly increased productivity in software development is now forcing better evaluation criteria to be used. Software engineering must begin to live up to its second name by finding quantitative measures of quality. This paper suggests some evaluation criteria that are probably too difficult to carry out, criteria that may always remain subjective. It argues that these are so important that we should keep them in mind as a balance to the hard data we can obtain and should seek to learn more about them despite the difficulty of doing so.A historical example is presented as illustration of the necessity of retaining subjective criteria. High-level languages and their compilers today enjoy almost universal acceptance. It will be argued that the value of this tool has never been precisely evaluated, and if narrow measures had been applied at its inception, it would have been found wanting. This historical lesson is then applied to the problem of evaluating a novel specification and testing tool under development at the University of Maryland.