Coverage-Directed Test Generation Automated by Machine Learning -- A Review

Abstract

The increasing complexity and size of digital designs, in conjunction with the lack of a potent verification methodology that can effectively cope with this trend, continue to inspire engineers and academics in seeking ways to further automate design verification. In an effort to increase performance and to decrease engineering effort, research has turned to artificial intelligence (AI) techniques for effective solutions. The generation of tests for simulation-based verification can be guided by machine-learning techniques. In fact, recent advances demonstrate that embedding machine-learning (ML) techniques into a coverage-directed test generation (CDG) framework can effectively automate the test generation process, making it more effective and less error-prone. This article reviews some of the most promising approaches in this field, aiming to evaluate the approaches and to further stimulate more directed research in this area.

References

1. Banzhaf, W. 1998. Genetic Programming: An Introduction on the Automatic Evolution of Computer Programs and Its Applications. Morgan Kaufmann, San Francisco, CA.
2. Baras, D., Fournier, L., and Ziv, A. 2008. Automatic boosting of cross-product coverage using Bayesian networks. In Proceedings of the Hardware and Software: Verification and Testing. 4th International Haifa Verification Conference (HVC’08). Springer, Berlin, 53--67.
3. Bergeron, J. 2003. Writing Testbenches: Functional Verification of HDL Models 2nd Ed., Springer, Berlin.
4. Bernardi, P., Christou, K., Grosso, M., Michael, M. K., Sanchez, E., and Sonza Reorda, M. 2008. Exploiting MOEA to automatically generate test programs for path-delay faults in microprocessors. In Applications of Evolutionary Computing. Lecture Notes in Computer Science, vol. 4974, Springer, Berlin, 224--234.
5. Bharda, J., Abadir, M. S., Wang, L. S., and Ray, S. 2007. A survey of hybrid techniques for functional verification. IEEE Des. Test Comput. 24, 2, 112--122.
6. Bose, M., Shin, J., Rudnik, E. M., Dukes, T., and Abadir M. 2001. A genetic approach to automatic bias generation for biased random instruction generation. In Proceedings of the IEEE Conference on Evolutionary Computation (ICEC). IEEE, Los Alamitos, CA, 442--448.
7. Braun, M., Rosenstiel, W., and Schubert, K. 2003. Comparison of Bayesian networks and data mining for coverage directed verification category simulation-based verification. In Proceedings of the 8th IEEE International High-Level Design Validation and Test Workshop. IEEE, Los Alamitos, CA, 91--95.
8. Braun, M., Fine, S., and Ziv, A. 2004. Enhancing the efficiency of Bayesian network based coverage directed test generation. In Proceedings of the IEEE International Workshop on High-Level Design, Validation, and Test. IEEE, Los Alamitos, CA, 75--80.
9. Breiman, L. 1984. Classification and Regression Trees. Wadsworth International Group, Belmont, CA.
10. Corno, F., Cumani, G., and Squillero, G. 2003a. Exploiting auto-adaptive μGP for highly effective test programs generation. In Evolvable Systems: From Biology to Hardware. Springer, Berlin, 262--273.
11. Corno, F., Cumani, G., Sonza Reorda, M., and Squillero, G. 2003b. Automatic test program generation for pipelined processors. In Proceedings of the ACM Symposium on Applied Computing. ACM, New York, 736--740.
12. Corno, F., Cumani, G., Sonza Reorda, M., and Squillero, G. 2003c. Fully automatic test program generation for microprocessor cores. In Proceedings of the Conference on Design, Automation and Test in Europe. Vol. 1, IEEE, Los Alamitos, CA, 1006--1011.
13. Corno, F., Squillero, G., and Sonza Reorda, M. 2003d. Code generation for functional validation of pipelined microprocessors. In Proceedings of the 8th IEEE European Test Workshop. IEEE, Los Alamitos, CA, 113--118.
14. Corno, F., Sanchez, E., Sonza Reorda, M., and Squillero, G. 2004. Automatic test program generation: A case study. IEEE Des. Test Comput. 21, 2, 102--109.
15. Cover, T. M. and Thomas, J. A. 2006. Elements of Information Theory 2nd Ed. Wiley-Interscience.
16. Eder, K., Flach, P., and Hsueh, H. 2007. Towards automating simulation-based design verification using ILP. In Inductive Logic Programming. Lecture Notes in Computer Science, vol. 4455, Springer, Berlin, 154--168.
17. Ferrandi, F., Scutio, D., Fin, A., and Fummi, F. 2003. Functional test generation: Overview and proposal of a hybrid genetic approach. In Evolutionary Algorithms for Embedded System Design. Kluwer, Amsterdam, 105--142.
18. Fine, S. and Ziv, A. 2003a. Coverage directed test generation for functional verification using Bayesian networks. In Proceedings of the 40th Annual Design Automation Conference. ACM, New York, 286--291.
19. Fine, S. and Ziv, A. 2003b. Enhancing the control and efficiency of the covering process. In Proceedings of the 8th IEEE International Workshop on High-Level Design Validation and Test. IEEE, Los Alamitos, CA, 96--101.
20. Fine, S., Freund, A., Jaeger, I., Mansour, Y., Naveh, Y., and Ziv, A. 2006. Harnessing machine learning to improve the success rate of stimuli generation. IEEE Trans. Comput. 55, 11, 1344--1355.
21. Guzey, O., Wang, L.C., Levitt, J., and Foster, H. 2008. Functional test selection based on unsupervised support vector analysis. In Proceedings of the 45th Annual Design Automation Conference. ACM, New York, 262--267.
22. Habibi, A., Tahar, S., Samarah, A., Donglin, L., and Ait Mohamed, O. 2006. Efficient assertion based verification using TLM. In Proceedings of the Design, Automation and Test in Europe Conference. IEEE, Los Alamitos, CA, 1--6.
23. Haihua, S., Wenli, W., Yunji, C., Bowen, C., and Qi, G. 2008. Coverage directed test generation: Godson experience. In Proceedings of the 17th Asian Test Symposium. IEEE, Los Alamitos, CA, 321--326.
24. Holland, J. H. 1992. Adaptation in Natural and Artificial Systems. MIT Press, Cambridge, MA.
25. IBM. 2002. Using the Intelligent Miner for Data 1st Ed. IBM Denmark A/S.
26. ITRS. 2008. International Technology Roadmap for Semiconductors. Design chapter 2008 Ed.
27. Jain, A. K., Murty, M. N., and Flynn, P. J. 1999. Data clustering: A review. ACM Comput. Surv. 31, 3, 264--323.
28. Koza, J. R. 1992. Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, Cambridge, MA.
29. Koza, J. R. 1989. Hierarchical genetic algorithms operating on populations of computer programs. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI). Morgan Kaufmann, 768--774.
30. Miczo, A. 2003. Automatic test pattern generation. In Digital Logic Testing and Simulation. Wiley, 165--231. http://dx.doi.org/10.1002/0471457787.ch4.
31. Muggleton, S. H. 1991. Inverting the resolution principle. In Machine Intelligence 12: Towards an Automated Logic of Human Thought. Clarendon Press, 93--103.
32. Muggleton, S. H. 1992. Inductive Logic Programming. Academic Press, London.
33. Muggleton, S. H. 1995. Inverse entailment and Progol. New Generation Comput. (Special Issue on Inductive Logic Programming) 13, 3--4, 245--286.
34. Niermann, T. and Patel, J. 1991. HITEC: A test generation package for sequential circuits. In Proceedings of the European Conference on Design Automation.
35. Piziali, A. 2007. Functional Verification Coverage Measurement and Analysis. Springer, Berlin.
36. Ravotto, D., Sanchez, E., Schillaci, M., and Squillero, G. 2008. An evolutionary methodology for test generation for peripheral cores via dynamic FSM extraction. In Applications of Evolutionary Computing. Lecture Notes in Computer Science, vol. 4974, Springer, Berlin, 214--223.
37. Samarah, A., Habibi, A., Tahar, S., and Kharma, N. 2006. Automated coverage directed test generation using a cell-based genetic algorithm. In Proceedings of the 11th IEEE International High Level Design Validation and Test Workshop. IEEE, Los Alamitos, CA, 19--26.
38. Smith, J., Bartley, M., and Fogarty, T. 1997. Microprocessor design verification by two-phase evolution of variable length tests. In Proceedings of IEEE International Conference on Evolutionary Computation (ICEC’97). IEEE, Los Alamitos, CA, 453--458.
39. Ur, S., and Yadin, Y. 1999. Micro architecture coverage directed generation of test programs. In Proceedings of the 36th Annual ACM/IEEE Design Automation Conference. ACM, New York, 175--180.
40. Wagner, I., Bertacco, V., and Austin, T. 2005. StressTest: An automatic approach to test generation via activity monitors. In Proceedings of the 42nd Annual Design Automation Conference. ACM, New York, 783--788.
41. Wagner, I., Bertacco, V., and Austin, T. 2007. Microprocessor verification via feedback-adjusted Markov models. IEEE Trans. Comput.-Aid. Des. Integrat. Circuits Syst. 26, 6, 1126--1138.
42. Widdoes, C. and Ho, R. 2002. “Deep” formal verification powers assertions. EE Times. http://www.eetimes.com/electronics-news/4142042/-Deep-formal-verification-powers-assertions.
43. Wile, B., Goss, J., and Roesner, W. 2005. Comprehensive Functional Verification: The Complete Industry Cycle (Systems on Silicon). Morgan Kaufmann.
44. Yu, X., Fin, A., Fummi, F., and Rudnik, E. M. 2002. A genetic testing framework for digital integrated circuits. In Proceedings of the 14th IEEE International Conference on Tools with Artificial Intelligence (ICTAI’02). IEEE, Los Alamitos, CA, 521--526.

Index Terms

• Computing methodologies

  • Machine learning

    • Learning paradigms

    • Learning settings

    • Machine learning approaches

      • Markov decision processes

• Hardware

  • Hardware test

  • Hardware validation

    • Functional verification

  • Robustness

• Theory of computation

  • Theory and algorithms for application domains

    • Machine learning theory

      • Markov decision processes