A BNF-based automatic test program generator for compatible microprocessor verification

Abstract

A novel Backus-Naur-form- (BNF-) based method to automatically generate test programs from simple to complex ones for advanced microprocessors is presented in this paper. We use X86 architecture to illustrate our design method. Our method is equally applicable to other processor architectures by redefining BNF production rules. Design issues for an automatic program generator (APG) are first outlined. We have resolved the design issues and implemented the APG by a top-down recursive descent parsing method which was originated from compiler design. Our APG can produce not only random test programs but also a sequence of instructions for a specific module to be tested by specifying a user menu-driven file. In addition, test programs generated by our APG have the features of no infinite loop, not entering illegal states, controllable data dependency, flexible program size, and data cache testable. Our method has been shown to be efficient and feasible for the development of an APG compared with other approaches. We have also developed a coverage tool to integrate with the APG. Experimental evaluation of the generated test programs indicates that our APG, with the guidance of the coverage tool, only needs to generate a small number of test programs to sustain high coverage.