System, method and computer program product for checking a software entity

1. A method for checking a software entity in a computerized environment comprising a processor, the method comprises:

providing a directed acyclic graph representative of possible execution paths of the software entity; wherein multiple successor nodes that succeed a parent node are associated with original execution probabilities;

determining execution probabilities for each of the successor nodes; wherein for at least a portion of the successor nodes the execution probability is different than the original execution probability;

checking the software entity by the processor; wherein said checking comprises:

determining a first state of the software entity; wherein the first state is associated with the software entity executing the parent node;

randomly selecting a successor node out of the multiple successor nodes; wherein said randomly selecting is performed based on a stochastic selection based on the determined execution probabilities;

modifying the first state of the software entity to a second state of the software entity, the second state is associated with the software entity executing the randomly selected successor node; and

whereby a state of the computerized environment is modified in accordance with the successor node.

2. The method according to claim 1 wherein the providing comprises converting a control flow graph representative of possible execution paths of the software entity to the directed acyclic graph.

3. The method according to claim 1 wherein said determining execution probabilities comprises determining an execution probability of a successor node in response to a number of paths in the directed acyclic graph that originate from the successor node; wherein each path comprises at least two nodes.

4. The method according to claim 1 wherein said determining execution probabilities comprises determining an execution probability of a successor node in an inverse proportion to a number of paths in the directed acyclic graph that originate from the parent node.

5. The method according to claim 1 wherein said determining execution probabilities comprises determining an execution probability of a successor node out of the successor nodes in response to a risk indication associated with at least one path that originates from the successor node.

6. The method according to claim 1 further comprising determining a number (E) of software entity check iterations required for testing a predefined number (n) of execution paths at a probability (p); wherein the execution paths comprise at least the successor nodes; and performing said checking the software entity at least the number (E) of software entity check iterations.

7. The method according to claim 1 wherein the providing comprises converting the directed acyclic graph to a spanning tree; and determining an execution probability of a successor node to be negligible in case the successor node is not connected to the parent node in the spanning tree.

8. The method according to claim 7 , wherein the spanning tree is a minimum-leaves spanning tree; and wherein said determining execution probabilities comprises determining the execution probabilities in an iterative manner by:

determining a uniform distribution to all leaves of the minimum-leaves spanning tree:

and determining the execution probabilities associated with nodes of the directed acyclic graph to enforce the uniform distribution.

9. The method according to claim 1 , wherein the possible execution paths are represented by a first group of nodes and a second group of nodes;

wherein the second group comprising the multiple successor nodes; the method further comprises deterministically checking execution paths that originate from the first group nodes; and wherein the first group comprises at least two execution paths that comprise a second parent node; wherein each of the at least two execution paths has an alternative successor node to the second parent node.

10. A computer program product comprising a non-transitory computer usable medium including a computer readable program, wherein the computer readable program when executed on a computer causes the computer to:

provide a directed acyclic graph representative of possible execution paths of the software entity, wherein multiple successor nodes that succeed a parent node are associated with original execution probabilities;

determine execution probabilities for each of the successor nodes; wherein for at least a portion of the successor nodes the execution probability is different than the original execution probability;

check the software entity by the processor; wherein said check comprises:

determine a first state of the software entity; wherein the first state is associated with the software entity executing the parent node;

randomly select a successor node out of the multiple successor nodes; wherein said randomly select is performed based on a stochastic selection based on the determined execution probabilities; and

modify the first state of the software entity to a second state of the software entity; wherein the second state is associated with the software entity executing the randomly selected successor node.

11. The computer program product according to claim 10 wherein the computer readable program when executed on a computer causes the computer to convert a control flow graph representative of possible execution paths of the software entity to the directed acyclic graph.

12. The computer program product according to claim 10 wherein the computer readable program when executed on a computer causes the computer to determine an execution probability of a successor node in response to a number of paths in the directed acyclic graph that originate from the successor node; wherein each path comprises at least two nodes.

13. The computer program product according to claim 10 wherein the computer readable program when executed on a computer causes the computer to determine an execution probability of a successor node in an inverse proportion to a number of paths in the directed acyclic graph that originate from the parent node.

14. The computer program product according to claim 10 wherein the computer readable program when executed on a computer causes the computer to determine an execution probability of a successor node out of the successor nodes in response to a risk indication associated with at least one path that originates from the successor node.

15. The computer program product according to claim 10 wherein the computer readable program when executed on a computer causes the computer to determine a number(E) of software entity check iterations required for testing a predefined number (n) of execution paths at a probability (p); wherein the execution paths comprise at least the successor nodes; and to perform said check the software entity at least the number (E) of software entity check iterations.

16. The computer program product according to claim 10 wherein the computer readable program when executed on a computer causes the computer to convert the directed acyclic graph to a spanning tree and determine an execution probability of a successor node out of the multiple successor nodes to be negligible in case the successor node is not connected to the parent node in the spanning tree.

17. The computer program product according to claim 10 , wherein the possible execution paths are represented by a first group of nodes and a second group of nodes; the second group of nodes comprising the multiple successor nodes; wherein the computer readable program when executed on the computer causes the computer to deterministically check execution paths that originate from the first group of nodes; and wherein the first group comprises at least two execution paths that comprise a second parent node; wherein each of the at least two execution paths has an alternative successor node to the second parent node.

18. A system for checking software entity modules, the system comprises: a storage unit adapted to store a directed acyclic graph representative of possible execution paths of the software entity; wherein multiple successor nodes that succeed a certain parent node are associated with original execution probabilities; and a processor, adapted to check the software entity by:

determining execution probabilities for each of the successor nodes; wherein for at least a portion of the successor nodes the execution probability is different than the original execution probability:

determining a first state of the software entity; wherein the first state is associated with the software entity executing the parent node;

randomly selecting a successor node out of the multiple successor nodes; wherein said randomly select is performed by performing a stochastic selection based on the determined execution probabilities; and

modifying the first state of the software entity to a second state of the software entity; wherein the second state is associated with the software entity executing the randomly selected successor node.

19. The system according to claim 18 wherein the processor is adapted to convert a control flow graph representative of possible execution paths of the software entity to a directed acyclic graph.

20. The system according to claim 18 wherein the processor is adapted to determine an execution probability of a successor node in response to a number of paths in the directed acyclic graph that originate from the successor node; wherein each path comprises at least two nodes.