Preview

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

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

Система автоматов: условия детерминизма и тестирование

https://doi.org/10.15514/ISPRAS-2016-28(1)-9

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

Аннотация

Статья посвящена проблеме тестирования составных систем, компоненты которых моделируются конечными автоматами с несколькими входами и выходами, а взаимодействие между ними - обменом сообщениями по симплексным каналам связи. Система описывается ориентированным графом связей, вершина которого соответствует автомату компонента, а дуга - каналу связи, соединяющему выход одного автомата со входом другого автомата. Предполагается выполненной следующая гипотеза о связях: граф связей статический, а отображаемая им структура связей не содержит ошибок. Автомат, находящийся в вершине графа, в каждом состоянии может принимать несколько сообщений по своим входам (не более одного по каждому входу) и посылать несколько сообщений по своим выходам (не более одного по каждому выходу). Определяется ассоциативная композиция автоматов системы. Показывается, при каких ограничениях на автоматы и граф связей их композиция, т.е. сама система, детерминирована. Целью тестирования является покрытие переходов автоматов компонентов, которые достижимы при работе этих автоматов в системе. Предполагается, что при тестировании возможно наблюдение изменения состояний автоматов системы и передаваемых между ними сообщений. Полное тестирование системы автоматов без учёта гипотезы о связях может потребовать число тестовых воздействий порядка произведения чисел состояний автоматов компонентов, а с учётом гипотезы о связях - порядка суммы этих чисел. При равном числе состояний всех автоматов это даёт экспоненциальное уменьшение числа тестовых воздействий. При условии выполнения гипотезы о связях для детерминированной системы предлагается алгоритм генерации тестов, основанный на фильтрации тестов, генерируемых для покрытия всех переходов композиции. Тест отбрасывается, если он покрывает только такие переходы в компонентах системы, которые покрываются остающимися тестами. В заключение определяются направления дальнейших исследований.

Об авторах

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


А. С. Косачев
Институт системного программирования РАН
Россия


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

1. И.Б.Бурдонов, А.С.Косачев. Тестирование системы автоматов. Труды ИСП РАН, том 28(1), 2016 г. DOI: 10.15514/ISPRAS-2016-28(1)-7

2. И.Б.Бурдонов, А.С.Косачев. Система автоматов: композиция по графу связей. Труды ИСП РАН, том 28(1), 2016 г. DOI: 10.15514/ISPRAS-2016-28(1)-8

3. Revised Working Draft on “Framework: Formal Methods in Conformance Testing”. JTC1/SC21/WG1/Project 54/1, ISO Interim Meeting, ITU-T on, Paris, 1995 г.

4. И.Б.Бурдонов, Косачев А.С., В.В.Кулямин. Теория соответствия для систем с блокировками и разрушением. «Физ-мат лит» Наука, Москва, 2008 г., 412 стр.

5. И.Б.Бурдонов. Теория конформности (функциональное тестирование программных систем на основе формальных моделей). LAP Lambert Academic Publishing, 2011 г., 428 стр.

6. И.Б.Бурдонов, А.С.Косачев. Пополнение спецификации для ioco. Программирование, 2011 г., №1, стр. 3-18.

7. А. Камкин, М. Чупилко. Обзор современных технологий имитационной верификации аппаратуры. Программирование, 2011 г., №3, стр. 42-49.

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

9. Ананий В. Левитин. Алгоритмы: введение в разработку и анализ. М.: «Вильямс», 2006 г., стр. 160-163, ISBN 0-201-74395-7.

10. Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ. 2-ое издание. М.: «Вильямс», 2006 г., стр. 456-458, ISBN 0-07-013151-1.

11. Бурдонов И.Б., Косачев А.С., Кулямин В.В. Использование конечных автоматов для тестирования программ. Программирование. 2000 г., № 2, стр.12-28.

12. И.Б. Бурдонов, А.С. Косачев. Полное тестирование с открытым состоянием ограниченно недетерминированных систем. Программирование, 2009 г., №6, стр. 3-18.

13. И.Б.Бурдонов, А.С.Косачев. Семантики взаимодействия с отказами, дивергенцией и разрушением. Часть 2. Условия конечного полного тестирования. Вестник Томского Государственного Университета, № 2(15), 2011 г., стр. 89-98.

14. И.Б. Бурдонов, А.С. Косачев. Тестирование конформности на основе соответствия состояний. Труды ИСП РАН, № 18, 2010 г., стр. 183-220.

15. И.Б.Бурдонов, А.С.Косачев, Безопасное тестирование симуляции систем с отказами и разрушением. Моделирование и анализ информационных систем, том 17(4), 2010 г., стр. 27-40.

16. I.B.Bourdonov, A.S.Kossatchev, V.V.Kuliamin. Formal Conformance Testing of Systems with Refused Inputs and Forbidden Actions. Proceedings of the Workshop on Model Based Testing (MBT 2004), Elsevier, 2006.

17. И.Б.Бурдонов, А.С.Косачев, В.В.Кулямин. Формализация тестового эксперимента. Программирование, 2007 г., №5, стр. 3-32.

18. И.Б.Бурдонов, А.С.Косачев, В.В.Кулямин. Безопасность, верификация и теория конформности. Материалы второй международной научной конференции по проблемам безопасности и противодействия терроризму. МГУ 2006, М., МЦНМО, 2007 г., стр. 135-158.

19. И.Б.Бурдонов, Косачев А.С. Системы с приоритетами: конформность, тестирование, композиция. Программирование, 2009 г., № 4, стр.24-40.

20. И.Б. Бурдонов, А.С. Косачев. Тестирование с преобразованием семантик. Труды ИСП РАН, том 17, 2009 г., стр.193-208.

21. A.Kossachev, I.Burdonov. Formal Conformance Verifcation, Short Papers of the 22nd IFIP ICTSS, Alexandre Petrenko, Adenilso Simao, Jose Carlos Maldonado (eds.), Nov. 08-10, 2010, Natal, Brazil, pp.1-6.

22. А.С. Косачев, И.Б.Бурдонов. Семантики взаимодействия с отказами, дивергенцией и разрушением. Программирование, 2010 г., №5, стр. 3-23.

23. И.Б.Бурдонов, А.С.Косачев. Согласование конформности и композиции. Программирование, 2013 г., №6, стр. 3-15.


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


Бурдонов И.Б., Косачев А.С. Система автоматов: условия детерминизма и тестирование. Труды Института системного программирования РАН. 2016;28(1):151-184. https://doi.org/10.15514/ISPRAS-2016-28(1)-9

For citation:


Burdonov I., Kossatchev A. Automata system: determinism conditions and testing. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2016;28(1):151-184. (In Russ.) https://doi.org/10.15514/ISPRAS-2016-28(1)-9

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


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


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