Подход к генерации тестов, нацеленных на покрытие кода HDL-описаний аппаратуры, на основе расширенных конечных автоматов

Генерация тестов по моделям широко используется для функциональной верификации аппаратуры. Расширенные конечные автоматы (extended finite state machines, EFSM) - удобный формализм для моделирования цифровых устройств. В отличие от обычных конечных автоматов, в EFSM-моделях управляющие сигналы и данные разделены, что позволяет описывать системы в более компактной форме, уменьшая в некотором смысле риск комбинаторного взрыва при верификации. В данной статье представлен метод генерации тестов по EFSM-моделям и проведено его сравнение с другими подходами. Предлагаемый метод сочетает случайный обход графа состояний автомата и направленный поиск реализуемых путей. Первая из указанных фаз направлена на покрытие «простых» переходов, вторая - «сложных». При направленном поиске используется информация о зависимостях по данным и управлению между переходами автомата и задействуется символическое исполнение. Проведенные эксперименты показывают, что в сравнении с другими подходами метод обеспечивает лучшие показатели тестового покрытия более короткими тестами.

проектирование аппаратуры, язык описания аппаратуры, имитационная верификация, генерация тестов, моделирование, расширенный конечный автомат, обход графа, случайный обход, поиск с возвратами, символическое исполнение, разрешение ограничений

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. Лазарев В.Г., Пийль Е.И. Синтез управляющих автоматов. Энергоатомиздат, 1989. 328 с.

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. http://forge.ispras.ru/projects/retrascope

13. Тестовый набор ITC’99. http://www.cad.polito.it/tools/itc99.html

14. Библиотека Fortress. http://forge.ispras.ru/projects/solver-api

15. Решатель ограничений Z3. http://z3.codeplex.com

16. Симулятор Questa. http://www.mentor.com/products/fv/questa/