Even though the importance of microprocessor design verification is widely acknowledged, no rigorous methodology is being commonly followed for its realization. This paper attempts to delineate such a methodology, and shows how it is promoted by Genesys, an automatic pseudo-random test-program generator. The methodology relies on a verification plan which induces smart sets of tests that carry out the verification tasks. The paper reports on an application of this methodology, using Genesys, to verify an x86 design and describes, in particular, how this methodology could have helped to avoid known escape bugs, such as the recent two infamous Pentium Floating Point bugs. © 1999 IEEE.