methods and apparatus are provided for exploring paths through a graph representation of a program or another entity . according to one aspect of the invention , at least one property of a state machine , such as a graph representing a software program , is evaluated . one or more paths in the state machine are evaluated using a state exploration algorithm , wherein the state exploration algorithm maintains a stack data structure representing a current path being processed from an entry state to a current state and a visited state cache indicating zero or more states that have been evaluated . when a state satisfies at least one property , such as having an error , each of the states in the path are removed from the visited states cache if the path satisfies one or more predefined criteria . the one or more predefined criteria may comprise a feasibility of the path .