Patent Document ID: 7590520
Application ID: 10758797
Patent Status: 1

Claim One:
1. A computerized method of creating test coverage for non-deterministic programs within a testing environment comprising: in a computer, receiving a graph of edges and states representing a program under test, the states comprising a plurality of deterministic states controllable by the testing environment and a plurality of non-deterministic states uncontrollable by the testing environment, wherein a plurality of the edges represent non-deterministic choices associated with at least one of the non-deterministic states and the edges representing non-deterministic choices are assigned respective probabilities; creating a continuous cycle of edges and states through the graph that reaches each state in the graph at least once; splitting the continuous cycle into discrete sequences that end at the non-deterministic states; executing the program under test under test conditions as a first execution of the program; determining discrete sequences not reached by the first execution of the program; determining untested states as states in the discrete sequences not reached by the first execution of the program; creating strategies through the graph to reach the untested states, wherein creating strategies comprises (a), (b), and (c): (a) starting from a given untested state out of the untested states, traversing the graph backwards and computing costs and probabilities at states with a respective edge reaching the given untested state, wherein probabilities are assigned based on likelihood that an edge exiting a respective non-deterministic state uncontrollable by the testing environment will be selected during execution; (b) assigning probabilities and costs to respective vertices based on a probability of providing a path to the given untested state; and (c) choosing vertices such that a next state with a lower cost and higher probability is preferred over a next state with higher cost and lower probability, wherein the strategies comprise respective series of one or more edge transitions through the graph; storing a representation of the created strategies in computer memory; and in the computer, executing the program under test under test conditions as a subsequent execution of the program to the first, the subsequent execution using the created strategies such that the subsequent execution has a higher probability than the first execution of the program to execute through states that correspond to the untested states, wherein the subsequent execution repeats at least one of the strategies and presents the non-deterministic choices from at least one of the non-deterministic states a plurality of times during the subsequent execution, whereby a possibility of reaching at least one of the untested states is increased.