The present invention extends to methods, systems, and computer program products for automatically generating test cases for binary code. Embodiments of the present invention can automatically generate test inputs for systematically covering program execution paths within binary code. By monitoring program execution of the binary code on existing or random test cases, branch predicates on execution paths can be dynamically inferred. These inferred branch predicates can then be used to drive the program along previously unexplored execution paths, enabling the learning of further execution paths. Embodiments of the invention can be used in combination with other analysis and testing techniques to provide better test coverage and expose program errors.