Preview

Труды Института системного программирования РАН

Расширенный поиск

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

https://doi.org/10.15514/ISPRAS-2015-27(3)-12

Полный текст:

Аннотация

Генерация тестов по моделям широко используется для функциональной верификации аппаратуры. Расширенные конечные автоматы (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/


Для цитирования:


Мельниченко И..., Камкин А..., Смолов С... Подход к генерации тестов, нацеленных на покрытие кода HDL-описаний аппаратуры, на основе расширенных конечных автоматов. Труды Института системного программирования РАН. 2015;27(3):161-182. https://doi.org/10.15514/ISPRAS-2015-27(3)-12

For citation:


Melnichenko I..., Kamkin A..., Smolov S... An Extended Finite State Machine-Based Approach to Code Coverage-Directed Test Generation for Hardware Designs. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2015;27(3):161-182. (In Russ.) https://doi.org/10.15514/ISPRAS-2015-27(3)-12

Просмотров: 176


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2079-8156 (Print)
ISSN 2220-6426 (Online)