Синтез тестов с гарантированной полнотой для недетерминированных временных автоматов


https://doi.org/10.18255/1818-1015-2017-4-496-507

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


Аннотация

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


Об авторах

Александр Сергеевич Твардовский
Национальный исследовательский Томский государственный университет
Россия
магистрант


Калед Эль-Факи
Американский университет Шарджа
Объединенные Арабские Эмираты
д-р компьютерных наук, доцент


Максим Леонидович Громов
Национальный исследовательский Томский государственный университет
Россия
канд. физ.-мат. наук, доцент


Нина Владимировна Евтушенко
Национальный исследовательский Томский государственный университет
Россия
д-р техн. наук, профессор


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

1. Chow T. S., “Test design modeled by finite-state machines”, IEEE Transactions on Software Engineering, 4:3 (1978), 178–187.

2. Dorofeeva R., El-Fakih K., Maag S., Cavalli A., Yevtushenko N., “FSM-based conformance testing methods: a survey annotated with experimental evaluation”, Information and Software Technology, 52 (2010), 1286–1297.

3. Petrenko A., Yevtushenko N., “Conformance Tests as checking experiments for partial nondeterministic FSM”, Proc. of the 5th International Workshop on Formal Approaches to Testing of Software (FATES 2005), LNCS, 3997, 2005, 118–133.

4. Springintveld J., Vaandrager F., D’Argenio P., “Testing timed automata”, Theoretical Computer Science, 254:1–2 (2001), 225–257.

5. El-Fakih K., Yevtushenko N., Fouchal H., “Testing timed finite state machines with guaranteed fault coverage”, Proceedings of the 21st IFIP WG 6.1 International Conference on Testing of Software and Communication Systems and 9th International FATES Workshop, 2009, 66–80.

6. Krichen M., Tripakis S., “Conformance testing for real-time systems”, Formal Methods in System Design, 34:3 (2009), 238–304.

7. Merayo M.G., Nunez M., Rodriguez I., “Formal testing from timed finite state machines”, Computer Networks: The International Journal of Computer and Telecommunications Networking, 52:2 (2008), 432–460.

8. Bresolin D., El-Fakih K., Villa T., Yevtushenko N., “Deterministic timed finite state machines: Equivalence checking and expressive power”, International conference GANDALF, 2014, 203–216.

9. Petrenko A., Yevtushenko N., Bochmann G.v., “Fault Models for Testing in Context”, FORTE, 1996, 163–178.

10. Yevtushenko N., El-Fakih K., Ermakov A., “On-the-fly construction of adaptive checking sequences for testing deterministic implementations of nondeterministic specifications”, LNCS, 9976 (2016), 139–152.

11. Petrenko A., Yevtushenko N., “Adaptive Testing of Deterministic Implementations Specified by Nondeterministic FSMs”, Proceedings of ICTSS, 2011, 162–178.

12. Tvardovskii A., Yevtushenko N., “Synthesis complete test suite for nondeterministic finite state machines with time guards”, Russian Physics Journal, 58:11/2 (2015), 107–110.


Дополнительные файлы

Для цитирования: Твардовский А.С., Эль-Факи К., Громов М.Л., Евтушенко Н.В. Синтез тестов с гарантированной полнотой для недетерминированных временных автоматов. Моделирование и анализ информационных систем. 2017;24(4):496-507. https://doi.org/10.18255/1818-1015-2017-4-496-507

For citation: Tvardovskii A.S., El-Fakih K., Gromov M.L., Yevtushenko N.V. Testing Timed Nondeterministic Finite State Machines with the Guaranteed Fault Coverage. Modeling and Analysis of Information Systems. 2017;24(4):496-507. (In Russ.) https://doi.org/10.18255/1818-1015-2017-4-496-507

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

Обратные ссылки

  • Обратные ссылки не определены.


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


ISSN 1818-1015 (Print)
ISSN 2313-5417 (Online)