Preview

Информатика

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

Верификация систем с параллелизмом поведения на основе графа достижимых состояний

Аннотация

Рассматривается задача верификации систем управления на основе моделей их поведения, которая состоит в проверке соответствия поведения системы требованиям, предъявляемым спецификацией на ее проектирование. Тестирование предполагает выполнение экспериментов, заключающихся в моделировании исследуемой системы, в ходе которого она проверяется на вход-выходное соответствие модели. Тестовая последовательность генерируется на основе модели, описывающей желаемое поведение системы. Предлагается метод построения тестовой последовательности для верификации схемной (или программной) реализации системы управления с параллелизмом поведения, который основан на обходе графа состояний, достижимых при функционировании системы. Описывается метод построения множества достижимых полных состояний для параллельного алгоритма описания поведения системы управления и получения тестовых наборов. Полагается, что описание функционирования системы, заданное спецификацией на проектирование, корректно; проверке подлежит схемная (или программная) реализация, которая должна соответствовать этой спецификации.

Об авторах

Ю. В. Поттосин
Объединенный институт проблем информатики Национальной академии наук Беларуси
Беларусь
Поттосин Юрий Васильевич, кандидат физикоматематических наук, ведущий научный сотрудник


В. И. Романов
Объединенный институт проблем информатики Национальной академии наук Беларуси
Романов Владимир Ильич, кандидат технических наук, ведущий научный сотрудник


Л. Д. Черемисинова
Объединенный институт проблем информатики Национальной академии наук Беларуси
Черемисинова Людмила Дмитриевна, доктор технических наук, главный научный сотрудник


Список литературы

1. Валидация на системном уровне. Высокоуровневое моделирование и управление тестированием : пер. с англ. Е. Б. Махияновой / М. Чэнь [и др.]. – М. : Техносфера, 2014. – 296 с.

2. Tretmans, J. Model based testing with labelled transition systems / J. Tretmans // Formal Methods and Testing: Lecture Notes in Computer Science. – Springer, 2008. – Vol. 4949. – P. 1–38.

3. Lee, D. Principles and methods of testing finite state machine – a survey / D. Lee, M. Yannakakis // Proceedings of the IEEE. – 1996. – Vol. 84, no. 8. – P. 1090–1123.

4. Верификация автоматных программ / С. Э. Вельдер [и др.]. – СПб. : Наука, 2011. – 244 с.

5. Питерсон, Дж. Теория сетей Петри и моделирование систем : пер. с англ. М. В. Горбатовой, В. Л. Торхова, В. Н. Четверикова / Дж. Питерсон. – М. : Мир, 1984. – 264 с.

6. Котов, В. Е. Сети Петри / В. Е. Котов. – М. : Наука, 1984. – 160 с.

7. Karatkevich, A. Dynamic Analysis of Petri Net-based Discrete Systems / A. Karatkevich. – Berlin : Springer-Verlag, 2007. – Vol. 358. – 166 p.

8. Закревский, А. Д. Параллельные алгоритмы логического управления / А. Д. Закревский. – Минск : Ин-т техн. кибернетики НАН Беларуси, 1999. – 202 с.

9. Hack, M. Analysis of production schemata by Petri nets / M. Hack // Project MAK-94. – Cambridge, 1972. – 119 р.

10. Experimental system of automated design of logical control devices / A. D. Zakrevskij [et al.] // Proc. of the Intern. Workshop "Discrete Optimization Methods in Scheduling and Computer-Aided Design". – Минск : Ин-т техн. кибернетики НАН Беларуси, 2000. – C. 216–221.

11. Романов, В. И. Разработка инструментальных средств логического проектирования / В. И. Романов // Логическое проектирование. – Минск : Ин-т техн. кибернетики НАН Беларуси, 2001. – Вып. 6. – С.151–170.

12. Thimbleby, H. The directed Chinese Postman Problem / H. Thimbleby // Software Practice and Experience. – 2003. – Vol. 33, no. 11. – P. 1081–1096.

13. Бурдонов, И. Б. Неизбыточные алгоритмы обхода ориентированных графов. Детерминированный случай / И. Б. Бурдонов, А. С. Косачев, В. В. Кулямин // Программирование. – 2003. – № 5. – С. 11–30.

14. Черемисинова, Л. Д. Построение тестов полного перебора для оценки энергопотребления последовательностных схем / Л. Д. Черемисинова // Информатика. – 2017. – № 4. – С. 104–110.

15. Kanso, B. Compositional testing for FSM-based models / B. Kanso, O. Chebaro // Intern. J. of Software Engineering & Applications (IJSEA). – 2014. – Vol. 5, no. 3. – Р. 1–20.

16. Витязь, К. А. Алгоритмы построения функциональных тестов для цифровой схемы на основе автоматной модели ее поведения / К. А. Витязь, В. И. Романов // Танаевские чтения : доклады Восьмой Междунар. науч. конф., Минск, 27–30 марта 2018 г. – Минск : ОИПИ НАН Беларуси, 2018. – C. 52–56.


Рецензия

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


Поттосин Ю.В., Романов В.И., Черемисинова Л.Д. Верификация систем с параллелизмом поведения на основе графа достижимых состояний. Информатика. 2019;16(2):62-72.

For citation:


Pottosin Yu.V., Romanov V.I., Cheremisinova L.D. Verification of systems with behavior parallelism on the basis of the graph of reachable states. Informatics. 2019;16(2):62-72. (In Russ.)

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


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


ISSN 1816-0301 (Print)
ISSN 2617-6963 (Online)