Please use this identifier to cite or link to this item:
Title: Optimizing the length of checking sequences
Authors: Hierons, RM
Ural, H
Keywords: Finite state machine;Checking sequence;Test minimization;Distinguishing sequence
Issue Date: 2006
Publisher: IEEE Computer Society
Citation: IEEE Transactions Computers 55(5): 618-629
Abstract: A checking sequence, generated from a finite state machine, is a test sequence that is guaranteed to lead to a failure if the system under test is faulty and has no more states than the specification. The problem of generating a checking sequence for a finite state machine M is simplified if M has a distinguishing sequence: an input sequence D~ with the property that the output sequence produced by M in response to D is different for the different states of M. Previous work has shown that, where a distinguishing sequence is known, an efficient checking sequence can be produced from the elements of a set A of sequences that verify the distinguishing sequence used and the elements of a set /spl gamma/ of subsequences that test the individual transitions by following each transition t by the distinguishing sequence that verifies the final state of t. In this previous work, A is a predefined set and /spl gamma/ is defined in terms of A. The checking sequence is produced by connecting the elements of /spl gamma/ and A to form a single sequence, using a predefined acyclic set E/sub c/ of transitions. An optimization algorithm is used in order to produce the shortest such checking sequence that can be generated on the basis of the given A and E/sub c/. However, this previous work did not state how the sets A and E/sub c/ should be chosen. This paper investigates the problem of finding appropriate A and E/sub c/ to be used in checking sequence generation. We show how a set A may be chosen so that it minimizes the sum of the lengths of the sequences to be combined. Further, we show that the optimization step, in the checking sequence generation algorithm, may be adapted so that it generates the optimal E/sub c/. Experiments are used to evaluate the proposed method.
Appears in Collections:Computer Science
Dept of Computer Science Research Papers
Software Engineering (B-SERC)

Files in This Item:
File Description SizeFormat 
Optimizing.pdf643.37 kBAdobe PDFView/Open

Items in BURA are protected by copyright, with all rights reserved, unless otherwise indicated.