Тестирование системы автоматов с буферизацией сообщений

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

ориентированные графы, покрытие графа, взаимодействующие автоматы, распределенные системы, тестирование, сети

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

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

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

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

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

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

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

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

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

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

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

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

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

14. 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.

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

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

17. И.Б.Бурдонов, Косачев А.С. Системы с приоритетами: конформность, тестирование, композиция. Труды ИСП РАН, том 14 (1), 2008 г., стр.23-54.

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

19. 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.

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

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