Generating Cost-effective Criteria-based Tests from Behavioral Models

In software engineering, behavioral models such as finite state machines (FSMs) are used to represent key system behaviors. To evaluate the system behaviors, testers need to generate tests from the models and run the tests to check whether the execution meets the expectation. Coverage criteria are rules to specify which artifacts of the models (test requirements) should be included in the tests. Model-based testing (MBT) generates abstract tests in terms of a model (e.g., paths in a FSM) to satisfy a coverage criterion. Then the abstract tests must be mapped to concrete tests, which are expressed in terms of the implementation of the model. The concrete tests should also include test oracles to decide if the tests pass or not.;This research addressed three major sub-problems in model-based testing: the minimum cost test paths problem (MCTP), the mapping problem, and the test oracle problem. MCTP is to find test paths that satisfy all test requirements with minimum cost, which had not been defined before. The mapping problem refers to how to map abstract tests to concrete tests. The previous techniques for solving the mapping problem required lots of supporting diagrams and complicated conformation among the diagrams, which is hard to use. Therefore, many practitioners often solve this mapping problem by hand.;The test oracle problem considers how to write test oracles. Until now, there have not been many empirical results. With the same test inputs, test oracles that check more program states have the potential to reveal more faults, but also cost more to design and create.;This research presented two new approximation algorithms to solve the MCTP, the greedy set-covering algorithm and the matching-based prefix graph algorithm, and compared them with a previous brute force solution. This research designed a structured test automation language (STAL) to partially automate the mapping problem. This research also defined ten new test oracle strategies that check state invariants of models and different outputs and internal state variables of the program state different numbers of times.;The experiments showed that the two new solutions generated fewer test paths than the brute force approach. The prefix-graph based solution took much less time than the other two solutions when the number of test requirements is large. Thus, the prefix graph based solution is recommended. The automated test generation method using STAL took a fraction of the time the manual method took, and the manual tests contained numerous errors in which concrete tests did not match their abstract tests. So testers should use STAL to automate the mapping problem. Checking state invariants of models is recommended for testers who do not have enough time due to its low cost-effectiveness; otherwise, testers should check state invariants, outputs and parameter objects. Finally, if testers write test oracles by hand, they should check program states once at the end of tests.