Combinatorial interaction testing has been well studied in recent years, and has been widely applied in practice. It generally aims at generating an effective test suite (an interaction test suite) in order to identify faults that are caused by parameter interactions. Due to some constraints in practical applications (e.g. limited testing resources), for example in combinatorial interaction regression testing, prioritized interaction test suites (called interaction test sequences) are often employed. Consequently, many strategies have been proposed to guide the interaction test suite prioritization. It is, therefore, important to be able to evaluate the different interaction test sequences that have been created by different strategies. A well-known metric is the Average Percentage of Combinatorial Coverage (shortly APCCλ), which assesses the rate of interaction coverage of a strength λ (level of interaction among parameters) covered by a given interaction test sequence S. However, APCCλ has two drawbacks: firstly, it has two requirements (that all test cases in S be executed, and that all possible λ-wise parameter value combinations be covered by S); and secondly, it can only use a single strength λ (rather than multiple strengths) to evaluate the interaction test sequence - which means that it is not a comprehensive evaluation. To overcome the first drawback, we propose an enhanced metric Normalized APCCλ (NAPCC) to replace the APCCλ Additionally, to overcome the second drawback, we propose three new metrics: the Average Percentage of Strengths Satisfied (APSS); the Average Percentage of Weighted Multiple Interaction Coverage (APWMIC); and the Normalized APWMIC (NAPWMIC). These metrics comprehensively assess a given interaction test sequence by considering different interaction coverage at different strengths. Empirical studies show that the proposed metrics can be used to distinguish different interaction test sequences, and hence can be used to compare different test prioritization strategies.

This paper presents an approach to specification-based testing of concurrent programs with representative test sequences generated from Statecharts. Representative test sequences are a subset of all possible interleavings of concurrent events that define the behaviors of a concurrent program. Because a program's correctness may be determined by checking whether a program implemented all behaviors in its specification or not, the program can be regarded as being correct if it can supply an alternative execution that has the same effects as the program's behavior with each representative test sequence. Based on this observation, we employ each representative test sequence as a seed to generate an automaton that accepts its equivalent sequences to reveal the same behavior. In order to effectively test a concurrent program, the automaton such generated accepts all sequences equivalent to the representative test sequence and it is used to control test execution. This paper describes an automated process of generating automata from a Statecharts specification and shows how the proposed approach works on Statecharts specifications through some examples.

A Unique Input/Output (UIO) sequence for the state J of a protocol is a sequence of input/output pairs that is unique to state J. Obtaining UIO sequences from the protocol specification is a very important problem in protocol conformance testing. Let n and m be the total number of states and transitions of the protocol, respectively, and dmax be the largest outdegree of any state, W. Chun and P. D. Amer proposed an O(n2(dmax)2n-1) algorithm to obtain the minimum-length UIO sequences (where the length refers to the number of input/output pairs). However, n and m are normally very large for real protocols. In this paper, we propose an O(n*m) algorithm for obtaining UIO sequences. In theory, our algorithm yields a UIO sequence which contains at most n1 input/output pairs. In experimentation, ten protocol examples collected from recent papers, the ISO TP0 protocol, the ISDN Q. 931 network-side protocol, and the CCITT X. 25 protocol show that in average the obtained UIO sequences are only 11.8% longer than the minimum-length ones, and 97.4% of the existent UIO sequences can be found. And our algorithm is extended for minimizing the cost of UIO sequences and for obtaining synchronizable UIO sequences, which have not been achieved by any algorithm proposed earlier.

Conformance testing techniques are required for the efficient production of reliable communication protocols. A lot of conformance testing techniques have been developed. However, most of them can only decide whether an implemented protocol conforms to its specification. That is, the exact locations of faults are not determined by them. This paper presents some conditions that enable to find locations of multiple faults, and then proposes a test sequence generation technique under such conditions. The correctness proof and complexity analysis of the proposed technique are also given. The characteristics of this technique are to generate test sequences based on protocol specifications and interim test results, and to find locations of multiple faults in protocol implementations. Although the length of the test sequence generated by the proposed technique is a little longer than the one generated by the previous one, the class to which the proposed technique can be applied is larger than that to which the previous one can be applied.

In this paper we present a method to generate test sequences for stuck-at faults in sequential circuits which have distinguishing sequences. Since the circuit may have no distinguishing sequence, we use two design techniques for circuits which have distinguishing sequences. One is at state transition level and the other is at gate level. In our proposed method complete test sequence can be generated. The sequence consists of test vectors for the combinational part of the circuit, distinguishing sequences and transition sequences. The test vectors, which are generated by a combinational test generator, cause faulty staes or faulty output responses for a fault, and disinguishing sequences identify the differences between faulty states and fault free states. Transition sequences are necessary to make the state in the combinational vectors. And the distinguishing sequence and the transition sequence are used in the initializing sequence. Some techniques for shortening the test sequence is also proposed. The basic ideas of the techniques are to use a short initializing sequence and to find the order in concatenating sequences. But fault simulation is conducted so as not to miss any faults. The initializing sequence is obtained by using a distinguishing sequence. The efficiency of our method is shown in the experimental results for benchmark circuits.

This paper describes a reduction algorithm for SW method which generates test sequences for communication systems. SW method is based upon the Finite State Machine (FSM). SW method uses a set of characterizing sequences and a state transition checking approach. This paper concentrates the characteristics of the SW sequences, and proposes the new derivation algorithm of characterizing sequences. Furthermore, Chinese Postman Tour and Extended Chinese Postman Tour is proposed to reduce redundancy of the SW sequences. This paper also presents an evaluation of this method in terms of an upper bound of the sequence length and generated test sequence length. The evaluation shows that the algorithm dramatically reduces the sequence length of the original method.