NDLI: Optimal strategies for testing nondeterministic systems

Content Provider	ACM Digital Library
Author	Nachmanson, Lev Schulte, Wolfram Veanes, Margus Tillmann, Nikolai Grieskamp, Wolfgang
Abstract	This paper deals with testing of nondeterministic software systems. We assume that a model of the nondeterministic system is given by a directed graph with two kind of vertices: states and choice points. Choice points represent the nondeterministic behaviour of the implementation under test (IUT). Edges represent transitions. They have costs and probabilities. Test case generation in this setting amounts to generation of a game strategy. The two players are the testing tool (TT) and the IUT. The game explores the graph. The TT leads the IUT by selecting an edge at the state vertices. At the choice points the control goes to the IUT. A game strategy decides which edge should be taken by the TT in each state. This paper presents three novel algorithms 1) to determine an optimal strategy for the bounded reachability game, where optimality means maximizing the probability to reach any of the given final states from a given start state while at the same time minimizing the costs of traversal; 2) to determine a winning strategy for the bounded reachability game, which guarantees that given final vertices are reached, regardless how the IUT reacts; 3) to determine a fast converging edge covering strategy, which guarantees that the probability to cover all edges quickly converges to 1 if TT follows the strategy.
Starting Page	55
Ending Page	64
Page Count	10
File Format	PDF
ISSN	01635948
DOI	10.1145/1013886.1007520
Journal	ACM SIGSOFT Software Engineering Notes (SOEN)
Volume Number	29
Issue Number	4
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1979-04-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Optimal game strategies Abstract state machines Probabilistic nondeterministic finite state machines
Content Type	Text
Resource Type	Article

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

Optimal strategies for testing nondeterministic systems

Distinguishing tests for nondeterministic and probabilistic machines (1995).

Optimal transfer trees and distinguishing trees for testing observable nondeterministic finite-state machines

On adaptive experiments for nondeterministic finite state machines

Optimal strategies for testing nondeterministic systems (2004)

Optimal Pursuit Strategies in Discrete-State Probabilistic Systems

Generating finite state machines from abstract state machines

Generating finite state machines from abstract state machines

Testing from a nondeterministic finite state machine using adaptive state counting

Optimal strategies for testing nondeterministic systems

Similar Documents

Optimal strategies for testing nondeterministic systems

Distinguishing tests for nondeterministic and probabilistic machines (1995).

Optimal transfer trees and distinguishing trees for testing observable nondeterministic finite-state machines

On adaptive experiments for nondeterministic finite state machines

Optimal strategies for testing nondeterministic systems (2004)

Optimal Pursuit Strategies in Discrete-State Probabilistic Systems

Generating finite state machines from abstract state machines

Generating finite state machines from abstract state machines

Testing from a nondeterministic finite state machine using adaptive state counting

Optimal strategies for testing nondeterministic systems