Automated test case generation for the stress testing of multimedia systems

With the advancement in network bandwidth and computing power, multimedia systems have become a popular means for information delivery. However, general principles of system testing cannot be directly applied to testing of multimedia systems on account of their stringent temporal and synchronization requirements. In particular, few studies have been made on the stress testing of multimedia systems with respect to their temporal requirements under resource saturation. Stress testing is important because erroneous behavior is most likely to occur under resource saturation. This paper presents an automatable method of test case generation for the stress testing of multimedia systems. It adapts constraint solving techniques to generate test cases that lead to potential resource saturation in a multimedia system. Coverage of the test cases is defined upon the reachability graph of a multimedia system. The proposed stress testing technique is supported by tools and has been successfully applied to a real‐life commercial multimedia system. Although our technique focuses on the stress testing of multimedia systems, the underlying issues and concepts are applicable to other types of real‐time systems. Copyright © 2002 John Wiley & Sons, Ltd.     

A rigorous method for test templates generation from object-oriented specifications

This paper describes a rigorous method that investigates the suitability of formal specifications written in Object-Z specification language for testing object-oriented software implementation in a black-box fashion. The insight gained in the formalization of a model, the inherent abstractions, and formally specified intended behaviours and exceptions lead to the generation of test templates that are free from any implementation bias. The method described in this paper is an extension of the one proposed by Stocks and Carrington. In particular, the focus of the paper is on generating test templates for composite operations in an Object-Z specification. The method is illustrated using the specification for an electronic mail system. The specification and the test templates generated for the electronic mail system show several interesting properties of the application that require considerable attention during testing. Copyright © 2001 John Wiley & Sons, Ltd.     

Systematic testing: A means for validating reactive systems

The validity of the first (formal) model of a system to be developed is crucial for the whole development process. Systematically checking this validity helps avoid costs that could arise if it were discovered too late that the system does not satisfy the customer's needs and expectations. This paper addresses how to validate synchronous reactive programs using the technique of systematic testing. Testing reactive systems differs from testing sequential systems: instead of checking simple pairs of inputs and outputs, sequences of inputs and outputs have to be checked. Thus, testing cannot be based on a simple function model, mapping input values onto output values nor on a control flow graph model (where a path from the start node to the final node represents one execution through the represented program). The model widely used instead is that of a finite-state machine. A systematic testing approach is presented that is both effective and efficient for validating reactive systems. It uses an additional specification based on a finite-state machine model. The approach is demonstrated for the well-known lift example. It is shown how to use the specification for carefully choosing a set of test criteria that address different types of fault; a procedure for selecting test cases and test data that satisfy the chosen criteria is presented.     

On the effect of test-suite reduction on automatically generated model-based tests

Model checking techniques can be successfully employed as a test-case generation technique to generate tests from formal models. The number of tests-cases produced, however, is typically large for complex coverage criteria such as MC/DC. Test-suite reduction can provide us with a smaller set of test-cases that preserve the original coverage—often a dramatically smaller set. Nevertheless, one potential drawback with test-suite reduction is that this might affect the quality of the test-suite in terms of fault finding. Previous empirical studies provide conflicting evidence on this issue. To further investigate the problem and determine its effect when testing implementations derived from formal models of software we performed an experiment using a large case example of a Flight Guidance System, generated reduced test-suites for a variety of structural coverage criteria while preserving coverage, and recorded their fault finding effectiveness. Our results indicate that the size of the specification based test-suites can be dramatically reduced and that the fault detection of the reduced test-suites is adversely affected. In this report we describe our experiment, analyze the results, and discuss the implications for testing based on formal specifications. This work has been partially supported by NASA grant NAG-1-224 and NASA contract NCC-01001. We also want to thank the McKnight Foundation for their generous support over the years.

---

     

Early quality monitoring in the development of real-time reactive systems

The increasing trend toward complex software systems has highlighted the need to incorporate quality requirements earlier in the development cycle. We propose a new methodology for monitoring quality in the earliest phases of real-time reactive system (RTRS) development. The targeted quality characteristics are functional complexity, performance, reliability, architectural complexity, maintainability, and test coverage. All these characteristics should be continuously monitored throughout the RTRS development cycle, to provide decision support and detect the first signs of low or decreasing quality as the system design evolves. The ultimate goal of this methodology is to assist developers in dealing with complex user requirements and ensure that the formal development process yields a high-quality application. Each aspect of quality monitoring is formalized mathematically and illustrated using a train-gate-controller case study.     

Conformance testing for real-time systems

We propose a new framework for black-box conformance testing of real-time systems. The framework is based on the model of partially-observable, non-deterministic timed automata. We argue that partial observability and non-determinism are essential features for ease of modeling, expressiveness and implementability. The framework allows the user to define, through appropriate modeling, assumptions on the environment of the system under test (SUT) as well as on the interface between the tester and the SUT. We consider two types of tests: analog-clock tests and digital-clock tests. Our algorithm for generating analog-clock tests is based on an on-the-fly determinization of the specification automaton during the execution of the test, which in turn relies on reachability computations. The latter can sometimes be costly, thus problematic, since the tester must quickly react to the actions of the system under test. Therefore, we provide techniques which allow analog-clock testers to be represented as deterministic timed automata, thus minimizing the reaction time to a simple state jump. We also provide algorithms for static or on-the-fly generation of digital-clock tests. These tests measure time only with finite-precision digital clocks, another essential condition for implementability. We also propose a technique for location, edge and state coverage of the specification, by reducing the problem to covering a symbolic reachability graph. This avoids having to generate too many tests. We report on a prototype tool called and two case studies: a lighting device and the Bounded Retransmission Protocol. Experimental results obtained by applying on the Bounded Retransmission Protocol show that only a few tests suffice to cover thousands of reachable symbolic states in the specification.     

Dynamic method for software test data generation

Test data generation in program testing is the process of identifying a set of test data which satisfies a given testing criterion. Existing pathwise test data generators proceed by selecting program paths that satisfy the selected criterion and then generating program inputs for these paths. One of the problems with this approach is that unfeasible paths are often selected; as a result, significant computational effort can be wasted in analysing those paths. In this paper, an approach to test data generation, referred to as a dynamic approach for test data generation, is presented. In this approach, the path selection stage is eliminated. Test data are derived based on the actual execution of the program under test and function minimization methods. The approach starts by executing a program for an arbitrary program input. During program execution for each executed branch, a search procedure decides whether the execution should continue through the current branch or an alternative branch should be taken. If an undesirable execution flow is observed at the current branch, then a real-valued function is associated with this branch, and function minimization search algorithms are used to locate values of input variables automatically, which will change the flow of execution at this branch.     

Traffic-aware stress testing of distributed real-time systems based on UML models using genetic algorithms

This paper presents a model-driven, stress test methodology aimed at increasing chances of discovering faults related to network traffic in distributed real-time systems (DRTS). The technique uses the UML 2.0 model of the distributed system under test, augmented with timing information, and is based on an analysis of the control flow in sequence diagrams. It yields stress test requirements that are made of specific control flow paths along with time values indicating when to trigger them. The technique considers different types of arrival patterns (e.g., periodic) for real-time events (common to DRTSs), and generates test requirements which comply with such timing constraints. Though different variants of our stress testing technique already exist (that stress different aspects of a distributed system), they share a large amount of common concepts and we therefore focus here on one variant that is designed to stress test the system at a time instant when data traffic on a network is maximal. Our technique uses genetic algorithms to find test requirements which lead to maximum possible traffic-aware stress in a system under test. Using a real-world DRTS specification, we design and implement a prototype DRTS and describe, for that particular system, how the stress test cases are derived and executed using our methodology. The stress test results indicate that the technique is significantly more effective at detecting network traffic-related faults when compared to test cases based on an operational profile.     

Empirical comparison of three metrics suites for fault prediction in packages of object-oriented systems: A case study of Eclipse

Packages are important high-level organizational units for large object-oriented systems. Package-level metrics characterize the attributes of packages such as size, complexity, and coupling. There is a need for empirical evidence to support the collection of these metrics and using them as early indicators of some important external software quality attributes. In this paper, three suites of package-level metrics (Martin, MOOD and CK) are evaluated and compared empirically in predicting the number of pre-release faults and the number of post-release faults in packages. Eclipse, one of the largest open source systems, is used as a case study. The results indicate that the prediction models that are based on Martin suite are more accurate than those that are based on MOOD and CK suites across releases of Eclipse.     

Generation of test sequences from formal specifications: GSM 11‐11 standard case study

This paper presents the results of a case study on generating test cases for a fragment of the smart card GSM 11‐11 standard. The generation method is based on an original approach using the B notation and techniques of constraint logic programming with sets. The GSM 11‐11 technical specifications were formalized with the B notation. From this B specification, a system of constraints was derived, equivalent to this formal model. Using a set constraint solver, boundary states were computed and test cases were obtained by traversing the constrained reachability graph of the specifications. The purpose of this project was to evaluate the contribution of this testing environment, called B ‐TESTING ‐TOOLS , in an industrial process on a real life‐size application, by comparing the generated test sequences with the already used and high‐quality manually‐designed tests. This comparison enabled us to validate our approach and showed its effectiveness in the validation process of critical applications: the case study gives a wide coverage (about 85%) of the generated tests compared to the pre‐existing tests and a saving of 30% in test design time. Copyright © 2004 John Wiley & Sons, Ltd.     

On guiding the augmentation of an automated test suite via mutation analysis

Mutation testing has traditionally been used as a defect injection technique to assess the effectiveness of a test suite as represented by a “mutation score.” Recently, mutation testing tools have become more efficient, and industrial usage of mutation analysis is experiencing growth. Mutation analysis entails adding or modifying test cases until the test suite is sufficient to detect as many mutants as possible and the mutation score is satisfactory. The augmented test suite resulting from mutation analysis may reveal latent faults and provides a stronger test suite to detect future errors which might be injected. Software engineers often look for guidance on how to augment their test suite using information provided by line and/or branch coverage tools. As the use of mutation analysis grows, software engineers will want to know how the emerging technique compares with and/or complements coverage analysis for guiding the augmentation of an automated test suite. Additionally, software engineers can benefit from an enhanced understanding of efficient mutation analysis techniques. To address these needs for additional information about mutation analysis, we conducted an empirical study of the use of mutation analysis on two open source projects. Our results indicate that a focused effort on increasing mutation score leads to a corresponding increase in line and branch coverage to the point that line coverage, branch coverage and mutation score reach a maximum but leave some types of code structures uncovered. Mutation analysis guides the creation of additional “common programmer error” tests beyond those written to increase line and branch coverage. We also found that 74% of our chosen set of mutation operators is useful, on average, for producing new tests. The remaining 26% of mutation operators did not produce new test cases because their mutants were immediately detected by the initial test suite, indirectly detected by test suites we added to detect other mutants, or were not able to be detected by any test.

A survey of timed automata for the development of real-time systems

Timed automata are a popular formalism to model real-time systems. They were introduced two decades ago to support formal verification. Since then they have also been used for other purposes and a large number of variants has been introduced to be able to deal with the many different kinds of requirements of real-time system development. This survey attempts to introduce a massive and complicated theoretical research area to a reader in an easy and compact manner. One objective of this paper is to inform a reader about the theoretical properties (or capabilities) of timed automata which are (or might be) useful for real-time model driven development. To achieve this goal, this paper presents a survey on semantics, decision problems, and variants of timed automata. The other objective of this paper is to inform a reader about the current state of the art of timed automata in practice. To achieve the second aim, this article presents a survey on timed automata’s implementability and tools.