An Extended Finite State Machine-Based Approach to Code Coverage-Directed Test Generation for Hardware Designs

Model-based test generation is widely spread in functional verification of hardware designs. The extended finite state machine (EFSM) is known to be a powerful formalism for modelling digital hardware. As opposed to conventional finite state machines, EFSM models separate datapath and control, which makes it possible to represent systems in a more compact way and, in a sense, reduces the risk of state explosion during verification. In this paper, a new EFSM-based test generation approach is proposed and compared with the existing solutions. It combines random walk on a state graph and directed search of feasible paths. The first phase allows covering “easy-to-fire” transitions. The second one is aimed at “hard-to-fire” cases; the algorithm tries to build a path that enables a given transition; it is carried out by analyzing control and data dependencies and applying symbolic execution techniques. Experiments show that the suggested approach provides better transition coverage with shorter test sequences comparing to the known methods and achieves a high level of code coverage.

hardware design, hardware description language, simulation-based verification, test generation, modelling, extended finite state machine, graph traversal, random walk, backjumping, symbolic execution, constraint solving

1. Bergeron J. Writing Testbenches: Functional Verification of HDL Models, Kluwer Academic Publishers, 2003.

2. Blyler J. Are Best Practices Resulting in a Verification Gap? (http://chipdesignmag.com/sld/blog/2014/03/04/are-best-practices-resulting-in-a-verification-gap).

3. Jusas V., Neverdauskas T. FSM Based Functional Test Generation Framework for VHDL. Proceedings of International Conference on Information and Software Technologies (ICIST), 2012. pp. 138-148.

4. Duale A.Y., Uyar M.U. A Method Enabling Feasible Conformance Functional Test Sequence Generation for EFSM Models. IEEE Transactions on Computers, 53(5), 2004. pp. 614-627.

5. Lazarev V.G., Pijl' E.I. Sintez upravljajushhih avtomatov. Energoatomizdat, Moscow, 1989. 328 p. (in Russian)

6. Cheng K.T., Krishnakumar A.S. Automatic Generation of Functional Vectors Using the Extended Finite State Machine Model. ACM Transactions on Design Automation of Electronic Systems (TODAES), 1996. pp. 57-79.

7. Di Guglielmo G., Di Guglielmo L., Fummi F., Pravadelli G. Efficient Generation of Stimuli for Functional Verification by Backjumping Across Extended FSMs. Journal of Electronic Functional testing: Theory and Application, 27(2), 2011. pp. 137-162.

8. Kamkin A. Smolov S. The Method of EFSM Extraction from HDL: Application to Functional Verification. Proceedings of the Conference on Problems of Perspective Micro- and Nanoelectronic Systems Development, Part II, 2014. pp. 113-118.

9. Navabi Z. Languages for Design and Implementation of Hardware. W.-K. Chen (Ed.). The VLSI Handbook. CRC Press, 2007. 2320 p.

10. Dijkstra E.W. A Note on Two Problems in Connexion with Graphs. Numerische Mathematik, 1, 1959, pp. 269-271.

11. Dijkstra E.W. A Discipline of Programming. Prentice Hall, 1976, 217 p.

12. Retrascope toolkit. http://forge.ispras.ru/projects/retrascope

13. ITC’99 benchmark. http://www.cad.polito.it/tools/itc99.html

14. Fortress library. http://forge.ispras.ru/projects/solver-api

15. Z3 solver. http://z3.codeplex.com

16. Questa simulator. http://www.mentor.com/products/fv/questa/