RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ЛИЧНЫЙ КАБИНЕТ
Общая информация
Последний выпуск
Архив

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Труды ИСП РАН:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Труды ИСП РАН, 2016, том 28, выпуск 1, страницы 103–130 (Mi tisp7)  

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

И. Б. Бурдонов, А. С. Косачев

Институт системного программирования РАН, 109004, Россия, г. Москва, ул. А. Солженицына, д. 25

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

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

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

Полный текст: PDF файл (368 kB)
Список литературы: PDF файл   HTML файл

Реферативные базы данных:

Тип публикации: Статья

Образец цитирования: И. Б. Бурдонов, А. С. Косачев, “Тестирование системы автоматов с буферизацией сообщений”, Труды ИСП РАН, 28:1 (2016), 103–130

Цитирование в формате AMSBIB
\RBibitem{BurKos16}
\by И.~Б.~Бурдонов, А.~С.~Косачев
\paper Тестирование системы автоматов с буферизацией сообщений
\jour Труды ИСП РАН
\yr 2016
\vol 28
\issue 1
\pages 103--130
\mathnet{http://mi.mathnet.ru/tisp7}
\crossref{https://doi.org/10.15514/ISPRAS-2016-28(1)-7}
\elib{http://elibrary.ru/item.asp?id=26166314}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/tisp7
  • http://mi.mathnet.ru/rus/tisp/v28/i1/p103

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Труды института системного программирования РАН
    Просмотров:
    Эта страница:65
    Полный текст:10
    Литература:15

     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2018