Fsm-based Test Cases Generation And Test Optimization

With the complexity, pervasiveness and criticality of software growing ceaselessly, ensuring that it behaves according to the desired level of quality and dependability becomes more crucial, and increasingly difficult and expensive. The existing research estimated that testing can consume 50%, or even more, of the development costs. A recent detailed survey in USA shows that test inadequacy has the high economic impacts.Model-based testing has been highlighted for several decades to search a way of test cases generation from system's behavior model. Since the model can precisely describe software what to do and not how to do, test cases derived from the model of software does not need to consider the real implementation of programs.A series of model-based test generation methods and test criteria have been proposed, such as the W method, the UIO method, the DS method, state coverage, transition coverage and transition-pairs coverage. Since the test purpose of each test generation method differs from others, each of them can not solve all problems in software testing. For example, the W method has the powerful faulty detection capability, as well as the prohibited length of test sequences, which leads to the rapid increase of test cost. To overcome this disadvantage, some improved methods, such as the PW method and the R-PW method, were presented in the past. Compared with the W method, those proposed methods have the same faulty detection capability and the shorter length of test sequences.Our purpose is to research the techniques for the generation and the optimization of test cases derived from the FSM model. Certainly, our research also can be used to the label transition system (LTS), constrainted logic program (CLP) and Petri etc. On the basis of the existing research, the paper presents a whole set of techniques for generating or optimizing test cases derived from the FSM model.Firstly, the paper studies the theories of Model-based testing, where the modeling languages contain CLP, FSM and LTS. The paper lays emphasis on the introduction about the theory of FSM, the assumptions of FSM-based testing, test generation, test criteria and their applicable scopes, and some evaluations for part of existing test criteria. In addition, test optimization types and traditional techniques are also introduced in the paper.Secondly, the paper discusses some traditional algorithms for test generation or for realizing test criteria, and analyzes their time and space efficiency. And then we present two new algorithms to improve the time efficiency of the traditional algorithms. Thirdly, the paper designs a new test criterion for FSM-based test generation. The purpose of software testing is to test each part of software at minimum cost. However, in practice, it is not possible to test all parts of software. So we need to get the tradeoff between the test cost and test efficiency. By the 2-8 law, the paper proposes the DFSM-based minimum test cost transition coverage criterion. According to this criterion, we get a test set of test sequences which covers all transitions and has the shortest length. So this criterion can effectively get the tradeoff between test cost and test efficiency.Fourthly, the paper presents a new approach to generating high quality test cases. This method needs to decompose regular expression of the FSM model into some subexpressions. And then test cases can be derived from those subexpressions. Our method lays emphasis on information completeness after regular expression is decomposed. Based on two empirical assumptions, we propose two processes of regular expression decomposition and three decomposition rules. This test method can test all loops in software.Fifthly, to solve the problem of redundancy in the test set, the paper also presents a new solution. Different from the previous heuristic algorithms, our method takes a test sequence as a string, and then by way of string matching, we eliminate redundancy among test sequences. The main advantage of our method is that the reduced set of test sequences also satisfies the original test coverage criterion.Sixthly, the paper uses logic coverage criteria to realize generate effective and executable test cases. And the paper discusses the existing logic coverage criteria, analyzes the relationship between test criteria and test generation, presents a new coverage criterion (TTJ), and design the effective algorithm to implement this criterion. According to this criterion, we can obtain a suite of test cases from the test set of test sequences.Finally, the paper develops a FSM-based test generation tool to support the above all techniques of both test cases generation and test optimization. By using the tool, the visual FSM model of system can be displayed and effective test cases are also generated.