Search

This paper proposes an algorithm which, given a set of observations of an existing concurrent system that has repetitive sub-functions, constructs a Message Sequence Charts (MSC) graph where repetitive sub-functions of the concurrent system are identified. This algorithm makes fewer assumptions than previously published work, and thus requires fewer and easier to generate observations to construct the MSC-graph. The constructed MSC-graph may then be used as input to existing synthesis algorithms to recover the design of the existing concurrent system. [ABSTRACT FROM AUTHOR]

Extended Finite State Machine (EFSM)-based passive fault detection involves modeling the system under test (SUT) as an EFSM M, monitoring the input/output behaviors of the SUT, and determining whether these behaviors relate to faults within the SUT. We propose a new approach for EFSM-based passive fault detection which randomly selects a state in M and checks whether there is a trace in M starting from this state which is compatible with the observed behaviors. If a compatible trace is found, we determine that observed behaviors are not sufficient to declare the SUT to be faulty; otherwise, we check another unchecked state. If all the states have been checked and no compatible trace is found, we declare that the SUT is faulty. We use a Hybrid method in our approach which combines the use of both Interval Refinement and Simplex methods to improve the performance of passive fault detection. [ABSTRACT FROM AUTHOR]

There are two main shortcomings in the existing models for generating checking sequences based on distinguishing sequences. First, these models require a priori selection of state recognition sequences (called α-sequences) which may not be the best selection for yielding substantial reduction in the length of checking sequences. Second, they do not take advantage of overlapping to further reduce the length of checking sequences. This paper proposes an optimization model that tackles these shortcomings to reduce the lengths of checking sequences beyond what is achieved by the existing models by replacing the state recognition sequences with a set of basic sequences called α-elements and by making use of overlapping. [ABSTRACT FROM AUTHOR]

Application of a test or checking sequence in a distributed test architecture often requires the use of external coordination message exchanges among multiple remote testers for eluding potential controllability and observability problems. Recent literature reports on conditions on a given finite state machine (FSM) under which controllability and observability problems can be overcome without using external coordination messages. However, these conditions do not guarantee that any test/checking sequence constructed from such FSMs are free from controllability and observability problems. For a given test or checking sequence, this paper investigates whether it is possible to eliminate the need for external coordination messages and proposes algorithms to identify or construct subsequences either within the given sequence or as an extension to the given sequence, respectively. Keywords: Finite state machine, testing, distributed test architecture, observability, controllability. [ABSTRACT FROM AUTHOR]

Testing may be used to show that a system under test conforms to its specification. In the case of a distributed system, one may have to use a distributed test architecture, involving p testers in order to test the system under test. These p testers may under some circumstances have to coordinate their actions with each other using external coordination channels. This may require the use of up to p2-p unidirectional coordination channels in the test architecture, which can be an extensive and expensive setup. In this paper, we propose a method to generate checking sequences while minimizing the number of required coordination channels, by adapting existing methods that generate checking sequences to be applied in a centralized test architecture. We consider the case of unidirectional and bidirectional coordination channels, and the case of transitive coordination. [ABSTRACT FROM AUTHOR]

A test suite, constructed either manually or automatically using a coverage criterion, can be reduced without significantly reducing its fault-detection capability by eliminating all but one of the equivalent test cases from each class of equivalent test cases of the test suite. In this paper, we use the analysis of control and data dependencies in an EFSM model of the system requirements to identify patterns of interaction among the elements of the EFSM that affect a requirement under test. These patterns are used to identify equivalent test cases w.r.t. the requirement under test; only one test case per equivalence class is kept, and equivalence classes that are not covered by any test cases are flagged. A software tool - Test Suite Reduction (TSR) based on above concept- is introduced. This tool is implemented in C++ and Java languages and runs on Sun workstations under Solaris Sparc 5.8. Additionally, the results of the application of TSR to several examples are also presented. [ABSTRACT FROM AUTHOR]

Given a set of observations of an existing concurrent system with repetitive sub-functions, we consider the construction of an MSC graph representing the functionality of the concurrent system. We first introduce a formal structure that we call "lattice of repetitive sub-functions". This lattice provides us with a global view of all the repetitive sub-functions of the system and all the compatible observations. Using the lattice, we are able to propose an algorithm that constructs the MSC graph representation of the system functionality in a more general context than in previously published work. [ABSTRACT FROM AUTHOR]

Based on a distinguishing sequence for a Finite State Machine (FSM), an efficient checking sequence may be produced from the elements of a set of -sequences and a set ET of T-sequences, that both recognize the states, and elements of EC which represents the transitions in the FSM. An optimization algorithm may then be used to produce a reduced length checking sequence by connecting the elements of , ET , and EC using transitions taken from an acyclic set E ′′. It is known that only a subset E′C of EC is sufficient to form a checking sequence. This paper improves this result by reducing the number of elements in E′C that must be included in the generated checking sequence. [ABSTRACT FROM AUTHOR]

This paper presents a method for reducing the cost of test generation. A spanning set for a coverage criterion is a set of entities such that exercising every entity in the spanning set guarantees exercising every entity defined by the coverage criterion. The central notion used in constructing a minimum spanning set is subsumption relation. An entity subsumes another entity if exercising the former guarantees exercising the latter. We develop a method for finding subsumption relations which can be uniformly applied to a family of control flow and data flow oriented coverage criteria by reducing the problem of determining whether an entity subsumes another entity to the model checking problem of the linear temporal logic LTL. [ABSTRACT FROM AUTHOR]

Under certain well-defined conditions, determining the correctness of a system under test (SUT) is based on a checking sequence generated from a finite state machine (FSM) specification of the SUT. When there is a distinguishing sequence for the FSM, an efficient checking sequence may be produced from the elements of a set of -sequences that verify subsets of states and the elements of a set EC of subsequences that test the individual transitions. An optimization algorithm may be used in order to produce a shortest checking sequence by connecting the elements of and EC using transitions drawn from an acyclic set. Previous work did not consider whether some transition tests may be omitted from EC. This paper investigates the problem of eliminating subsequences from EC for those transitions that correspond to the last transitions traversed when a distinguishing sequence is applied in an -sequence to obtain a further reduction in the length of a checking sequence. [ABSTRACT FROM AUTHOR]

This paper presents a new approach to structural testing, called dependence testing. First we propose dependence oriented coverage criteria that extend conventional data flow oriented coverage criteria with control dependence. This allows one to capture the full dependence information of a program or specification systematically. We then describe a model checking-based approach to test generation for dependence testing. It is shown that dependence oriented coverage criteria can be characterized in the temporal logics LTL and CTL. This enables one to use any LTL and CTL model checkers as test generators. Finally, we show that the temporal logic-based characterization can also be used for reducing the cost of dependence testing. [ABSTRACT FROM AUTHOR]