Methods and apparatus are disclosed to detect patterns in an executing program. An example method disclosed herein develops a trace of a program; identifies a sequence of program states from the trace by comparing intersecting sets of data at least partially indicative of addresses associated with the trace; develops a set of probabilities of transitioning between pairs of program states in the series of program states; identifies a current program state of the program; and predicts a next program state of the program based on the current program state and at least one of the probabilities.