|
...experiments. (6-9) However, specification-based modeling strategy for generating test suites has yet to reach widespread deployment in the software industry.
Software standards and language specifications are defined in natural language. Although they are usually supported by compliance test suites, each test suite is manually derived from the natural language description. As such, it is hard to determine if the compliance test suite is complete. Moreover, despite the huge investment of resources devoted to the preparation of such standards, they are still inherently ambiguous due to the use of natural language. We pose the following questions: Could a less ambiguous formal description be used instead of natural language? Can the conformance test suite that tests a standard implementation be derived automatically from the model specification?
The communications industry has used models written in SDL (Specification and Description Language), Estelle, PROMELA, UML (Unified Modeling Language), and others to investigate standards conformance. (10,11,3) These models are typically used for the verification of individual properties of the implementation and less frequently to generate conformance test suites. When they are used to generate test suites, several notions of coverage are applied.
In this paper, we show how certain complex aspects of software standards can be described using finite state machine (FSM) models. We investigate the POSIX ** (Portable Operating System Interface) fcntl byte range locking feature and the Java ** language exception handling feature as described in the standards. We also show that the test suites produced by these models are stronger than the conformance tests required by the standards. A larger case study is required to determine if the definition of commercial software standards using formal languages is practical.
In our approach, we developed an FSM model to substitute for the natural language description. The test suite is automatically obtained from the model using an FSM model-based test generator named GOTCHA-TCBeans. (7) GOTCHA-TCBeans is built on top of the Mur[phi] model checker. (12)
The FSM models can be reused to test different implementations of the specification. In addition, as the standard evolves, the model can be modified. As a result, the test suite evolves automatically with the standard. This innovation has the potential to change the entire process of standard development, implementation, and maintenance, which leads to improved quality of standard implementation. Finally, the GOTCHA model resembles a light implementation of the standard and is easily understood by developers. This approach to standard implementation enhances communication between testers and developers.
Previous work on test generation did not focus exclusively on the use of state machine models. Other techniques for test generation include reducing infinite domains to finite ones, data refinement, and syntactic coverage of the specification model. (13-15) Syntactic coverage of the specification model is analogous to code-based coverage of the implementation. (15,16) Our approach to coverage relates to the functionality and not to the syntax of the specification. Thus, the coverage criteria defined in our case studies are directly related to the semantics of the test objectives (e.g., test all types of lock collisions) and fit better with Marick's notion of test development. (17)
Automatic generation of test suites for protocol conformance is characterized by the existence of a formal specification for the protocol (typically in the SDL specification language (10)). Similarly, UML-based test generation assumes the existence of a UML specification that is used in the test generation process. (3) In contrast, we assume in our studies that software specifications use natural language, a situation typical for industrial software. Our studies indicate that the development of partial formal models focused on a specific feature or component of the software under test, for the sole purpose of test generation, is feasible and can provide good results in a realistic industrial setting.
We chose two very different case studies. The first study tested a subset of the POSIX (18) byte range locking standard API (application programming interface). The test cases are sequences of API invocations. In the second study, we tested the Java language exception handling feature. The test cases are programs in the Java language. In both case studies, the test cases are generated automatically from the FSM model.
The IEEE (Institute of Electrical and Electronics Engineers) POSIX Certification Authority and the National Institute of Technology Standards and Conformance Testing Group (SCTG) (19) offer a validation service and conformance test suites for POSIX. The use of the SCTG test suite is the accepted practice for testing conformance to the POSIX standard. We are not aware of any test suites produced for the POSIX standard that use FSM modeling.
In the second study, faults are hard to observe even when a defect occurs. This is due to the nature of the software under test. The component under test is a part of the garbage collector that analyzes the program control flow. This analysis is difficult when the program includes exception handling. (20,21) A serious fault in the garbage collector occurs whenever it collects live objects. If a defect occurs in the component (the map generator), the fault may not manifest itself. This depends on the specific program behavior. As a result, a combination of black box and white box testing strategies is required. Furthermore, complete code coverage is needed in order to fully exercise the map generator. Hence, the second study combines FSM modeling and automatic measurement of code-based coverage.
In the section "Strategies for software testing" that follows, we place our research within the state-of-the-art of software testing. Then, in the next two sections, "FSM modeling background" and "Modeling and test generation framework," we introduce the tools and techniques we used in our studies--FSM-based modeling and coverage-directed test generation. Next we describe our two case studies in "The POSIX byte range locking study" and "The Java exception handling study" sections. The last section, "Conclusions," contains our final comments.
Strategies for software testing
Two basic approaches to software testing are specification-based testing (black box) and program-based testing (white box). The black box approach to testing (22,23) focuses on the externally observable behavior of a program under test, whereas white box testing utilizes internal knowledge of the program under test, such as the program control flow or the program data flow. (24) Research on software testing indicates that both approaches are useful in the effective detection of faults. (25) This paper focuses on specification-based, black box testing.
Two strategies for the generation of tests are risk analysis and coverage analysis. Under risk analysis, we include statistical-based testing and manual, risk-based, test generation. Under the heading of coverage analysis we include combinatorial design techniques and state machine enumeration techniques.
Risk analysis test generation. In statistics-based software testing, (26) a test suite is chosen using some probability distribution. The probability distribution attempts to capture usage patterns of the program under test. The probability distribution can be defined over the space of possible program inputs. Alternatively, a state of a program that accepts inputs is defined by the values of its internal variables. Each program state determines a different probability distribution over the set of program inputs, which yield a Markov chain. For example, if a file is opened for a read operation, a subsequent write operation is illegal, whereas a subsequent read operation is legal. In this case, the program state is determined by the way the file is opened. The history of the test results can be used to derive reliability measures, such as mean time to failure (MTTF) and test stopping criteria.
On the one hand, statistics-based software testing is good at producing formal estimates of program reliability. On the other hand, it is often hard to estimate the typical usage of the software and thus provide an accurate probability distribution. (26) Furthermore, the usage pattern of the software may change, thus requiring the software reliability measures to be re-estimated. Finally, if the cost of a fault is high, as in safety critical software, the testing process must guarantee that the software has no defects even under test scenarios that have very low probability in the usage model.
Strategies have been suggested in References 27 and 28 for the manual selection of test cases from a model in order to minimize the risk of defects escaping to the field. These strategies are applied to a UML model specification in Reference 27 and a version of a statechart model in Reference 28. These approaches are especially relevant as a supplement to automatic test generation.
Coverage-based test generation. Exhaustive black box testing of commercial software systems is impractical due to the size of the input space. Coverage techniques define a set of subdomains whose union contains the input space. The size of this set is usually much smaller than the size of the original input space. Only a representative of each subdomain is chosen in order to cover the input space. The choice of the subdomains is usually guided by some fault model. Test generation techniques have focused on coverage of the input space to meet the testing objectives.
Combinatorial design strategies are used to obtain coverage. For example, the AETG ** tool from Bell-core implements a test generation coverage technique based on combinatorial design. (29) In contrast to the state machine enumeration techniques discussed below, combinatorial-based testing techniques are scalable, but do not deal with the selection of stimuli sequences to test the implementation. Recent attempts to deal with this problem are reported for UML specifications using UCBT (30) (use case-based testing) and API testing using SALT. (31)
In state machine enumeration, different techniques such as state exploration have been used to generate the tests. All of these test generation techniques have worst-case exponential run time as a result of the reachability state space enumeration. Compared to the combinatorial design strategies, these techniques deal well with the selection of complex stimuli sequences. When using state machines, or any other automated test generation technique, the coverage criteria may be provided implicitly, by stating a general feature of the model, or explicitly by providing a list of all features to be covered.
Explicit test generation requires that the test designer choose what to test through the choice of an explicit test purpose (or goal) for each test case generated. Automating the selection of individual stimuli in each test case requires user intervention and considerable manual input for each test case. (32) Test generation tools that support explicit test generation include: TGV, SAMSTAG, TVEDA, Verilog's ObjectGeode **, and Telelogic's Tau (see Reference 32 for references to these tools). All of these tools are SDL-based and have been applied primarily to telecommunication systems.
The test selection criteria used in implicit test generation are discussed by Horgan et al. (33) An example of implicit test generation is the extended message flow graph (EMFG) state exploration used in Reference 32 to automatically obtain a test suite. A data-flow-oriented criterion is used during state exploration to select the tests. This paper demonstrates the method with the all-use criterion. Others use coverage of the state machine structure as a test selection criterion. For example, ObjectGeode and Tau support structural coverage test generation of the specification. (34) Implicit test generation requires less manual effort compared to the explicit approach, but has less flexibility in the choice of test criteria.
In this paper, we present a different approach to test generation. A projection graph is derived from the specification state machine by the test designer based on some intuitive concern or fault model. During state exploration of the specification state machine, structural coverage of the projection graph is obtained. Thus, the test designer specifies an entire test suite instead of a single test as performed in explicit test generation. In view of the above, our approach requires less manual work than explicit test generation. In addition, the expressive power of the projection graph for specifying selection criteria is stronger than the selection criteria used in the implicit method and may be simpler and more natural than the explicit method. For example, given that the specification describes several processes and their interaction, a projection graph can easily be used to obtain the coverage of the transactions of a single process. This coverage requirement cannot be described by the implicit method and is not easily described by the explicit method, since a goal for each process transaction must be specified.
We apply our approach to the testing of the...
NOTE: All illustrations and photos
have been removed from this article.
More articles from IBM Systems Journal
Multithreaded Java program test generation., March 01, 2002
The software testing automation framework., March 01, 2002
Flavers: a finite state verification technique for software systems., March 01, 2002
Looking for additional articles?
Search our database of over 3 million articles.
Looking for more in-depth information on this industry?
Search our complete database of Industry & Market reports by text, subject, publication
name or publication date.
About Goliath
Whether you're looking for sales prospects, competitive information, company
analysis or best practices in managing your organization,
Goliath can help you meet your business needs.
Our extensive business information databases empower business
professionals with both the breadth and depth of credible,
authoritative information they need to support their business
goals. Whether it be strategic planning, sales prospecting,
company research or defining management best practices -
Goliath is your leading source for accurate information.
|
