Abstract
The objective of testing is to see if an implementation conforms to its specification. Testing is costly and time-consuming on both development and test application phases. How to efficiently design test cases for minimizing test time and cost is considered. In this dissertation, we study several efficient test case problems, including timing issue (test timing assignment), test time reduction issues (redundant test cases removal and test cases interconnection), and test architecture simplification issue (synchronizable test case generation), which are arisen from memory testing and communication protocol testing. The purpose of memory testing is to ensure that memory chip can work correctly in timing as well as functionality. We begin with solving timing assignment problem automatically. The proposed method is comprehensive enough to take the test objective and constraints from specification and tester into consideration. The test timing assignment problem is then transformed into a linear programming model, which can be automatically solved. Redundant test cases can be removed without reducing fault coverage. Test time reduction by removing redundant test cases for both test development phase, which has a well-defined fault model, and production test phase, which has no fault model, is discussed. During the test development phase, the process is to analyze fault detectability with respect to a given fault model. An optimal set of test cases is selected to compose the final test program, which results in minimum test application time. After proceeding to the production test phase, redundancy can also exhibit due to dependency of faults or discord between theoretical and practical fault models. The process is to analyze fail labels to remove redundant test cases optimally. Our result shows that these two methods are just dual to each other, and moreover, their underlying problem is an instance of weighted set-covering problem. In practical application, these two problems can be transformed into integer linear programming models, which can be automatically solved. As the production test process goes, a further test time reduction technique can be applied. The idea is to interconnect test cases to reuse memory states left from the previous test case for saving initialization and verification sequences as well as signal settling time of tester. The interconnection problem is transformed into an instance of Rural Chinese Postman (RCP) problem. However, the number of constraints could be exponential in the worst case if transforming RCP problem into an integer linear programming model. In this dissertation, a novel incremental constraining method is proposed, and our approach is to solve a number of successive integer linear programming models with smaller number of constraints. The total numbers of iterations and constraints applied to solve RCP problem are analyzed and compared. The test synchronization problem happens in a special test architecture, which requires at least two remote testers to test the implementation coordinately. This problem is usually encountered in testing multi-party communication protocol implementations. Testing system can be significantly simplified if synchronizable test cases are applied. In this dissertation, we propose a multiplex digraph model for synchronizable test case generation, which will consider both the costs of input/output operations and external synchronization operations. Applications for generating minimum-cost synchronizable transfer sequence, T-method test sequence, and Overlapping U-method test sequence are discussed and analyzed.