Please use this identifier to cite or link to this item:
Title: Oracles for distributed testing
Authors: Hierons, RM
Keywords: Distributed testing;Oracle problem
Issue Date: 2011
Publisher: IEEE
Citation: IEEE Transactions on Software Engineering, 99: 1-1, Apr 2011
Abstract: The problem of deciding whether an observed behaviour is acceptable is the oracle problem. When testing from a finite state machine (FSM) it is easy to solve the oracle problem and so it has received relatively little attention for FSMs. However, if the system under test has physically distributed interfaces, called ports, then in distributed testing we observe a local trace at each port and we compare the set of local traces with the set of allowed behaviours (global traces). This paper investigates the oracle problem for deterministic and non-deterministic FSMs and for two alternative definitions of conformance for distributed testing. We show that the oracle problem can be solved in polynomial time for the weaker notion of conformance but is NP-hard for the stronger notion of conformance, even if the FSM is deterministic. However, when testing from a deterministic FSM with controllable input sequences the oracle problem can be solved in polynomial time and similar results hold for nondeterministic FSMs. Thus, in some cases the oracle problem can be efficiently solved when using stronger notion of conformance and where this is not the case we can use the decision procedure for weaker notion of conformance as a sound approximation.
Description: Copyright @ 2010 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other users, including reprinting/ republishing this material for advertising or promotional purposes, creating new collective works for resale or redistribution to servers or lists, or reuse of any copyrighted components of this work in other works.
ISSN: 0098-5589
Appears in Collections:Computer Science
Dept of Computer Science Research Papers

Files in This Item:
File Description SizeFormat 
Fulltext.pdf233.16 kBAdobe PDFView/Open

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