NDLI: Oracles for Distributed Testing

Content Provider	IEEE Xplore Digital Library
Author	Hierons, R.M.
Copyright Year	1976
Abstract	The problem of deciding whether an observed behavior 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 behaviors (global traces). This paper investigates the oracle problem for deterministic and nondeterministic 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 (⊆_w) 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 ⊆_s and where this is not the case, we can use the decision procedure for ⊆_w as a sound approximation.
Sponsorship	IEEE Computer Society Technical Council on Software Engineering Association for Computing Machinery (ACM) IEEE Computer Society
Starting Page	629
Ending Page	641
Page Count	13
File Size	856563
File Format	PDF
ISSN	00985589
Volume Number	38
Issue Number	3
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2012-05-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Testing Controllability Observability Polynomials Software Software engineering local observability. Software engineering/software/program verification software engineering/testing and debugging systems and software distributed systems finite state machine nondeterminism test oracle controllability
Content Type	Text
Resource Type	Article
Subject	Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Controllable Testing from Nondeterministic Finite State Machines with Multiple Ports

Verifying and Comparing Finite State Machines for Systems that Have Distributed Interfaces

Automated Oracle Data Selection Support

Testing from a nondeterministic finite state machine using adaptive state counting

Towards a complexity theory for local distributed computing

Using Test Oracles Generated from Program Documentation (1998)

Semi-Proving: An Integrated Method for Program Proving, Testing, and Debugging

Metamorphic Testing: A Simple Method for Alleviating the Test Oracle Problem

Structural Controllability and Observability of Linear Systems Over Finite Fields With Applications to Multi-Agent Systems

Oracles for Distributed Testing

Similar Documents

Controllable Testing from Nondeterministic Finite State Machines with Multiple Ports

Verifying and Comparing Finite State Machines for Systems that Have Distributed Interfaces

Automated Oracle Data Selection Support

Testing from a nondeterministic finite state machine using adaptive state counting

Towards a complexity theory for local distributed computing

Using Test Oracles Generated from Program Documentation (1998)

Semi-Proving: An Integrated Method for Program Proving, Testing, and Debugging

Metamorphic Testing: A Simple Method for Alleviating the Test Oracle Problem

Structural Controllability and Observability of Linear Systems Over Finite Fields With Applications to Multi-Agent Systems

Oracles for Distributed Testing