maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2017-4-496-507mais-537Research ArticleОригинальные статьиArticlesСинтез тестов с гарантированной полнотой для недетерминированных временных автоматовTesting Timed Nondeterministic Finite State Machines with the Guaranteed Fault Coveragehttps://orcid.org/0000-0001-7705-7214ТвардовскийАлександр СергеевичTvardovskiiAleksandr S.

магистрант

Master student

tvardal@mail.ruЭль-ФакиКаледEl-FakihKhaled

д-р компьютерных наук, доцент

PhD in computer science, professor

kelfakih@aus.eduhttps://orcid.org/0000-0002-2990-8245ГромовМаксим ЛеонидовичGromovMaksim L.

канд. физ.-мат. наук, доцент

PhD in computer science, associate professor

maxim.leo.gromov@gmail.ruhttps://orcid.org/0000-0002-4006-1161ЕвтушенкоНина ВладимировнаYevtushenkoNina V.

д-р техн. наук, профессор

doctor of technical sciences, professor

nyevtush@gmail.comНациональный исследовательский Томский государственный университетРоссияNational Research Tomsk State UniversityRussian FederationАмериканский университет ШарджаОбъединенные Арабские ЭмиратыAmerican University of SharjahUnited Arab Emirates201731082017244496507Copyright © Твардовский А.С., Эль-Факи К., Громов М.Л., Евтушенко Н.В., 20172017Твардовский А.С., Эль-Факи К., Громов М.Л., Евтушенко Н.В.Tvardovskii A.S., El-Fakih K., Gromov M.L., Yevtushenko N.V.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.mais-journal.ru/jour/article/view/537

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

Nowadays, the behaviour of many systems can be properly described by taking into account time constraints, and this motivates the adaptation of existing Finite State Machine (FSM)- based test derivation methods to timed models. In this paper, we propose a method for deriving conformance tests with the guaranteed fault coverage for a complete possibly nondeterministic FSM with a single clock; such Timed FSMs (TFSMs) are widely used when describing the behaviour of software and digital devices. The fault domain contains every complete TFSM with the known upper bounds on the number of states and finite boundary of input time guards. The proposed method is carried out by using an appropriate FSM abstraction of the given TFSM; the test is derived against an FSM abstraction and contains timed input sequences. Shorter test suites can be derived for a restricted fault domain, for instance, for the case when the smallest duration of an input time guard is larger than two. Moreover, the obtained test suites can be reduced, while preserving the completeness, when all input time guards of the specification and an implementation are right closed (or all intervals are left closed). Experiments are conducted to study the length of test suites constructed by different methods.

временные автоматынедетерминированные автоматысинтез тестовобласть неисправностиtimed finite state machinesnondeterministic finite state machinestest derivationfault coverageReferencesChow T. S., “Test design modeled by finite-state machines”, IEEE Transactions on Software Engineering, 4:3 (1978), 178–187.Chow T. S., “Test design modeled by finite-state machines”, IEEE Transactions on Software Engineering, 4:3 (1978), 178–187.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.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.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.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.Springintveld J., Vaandrager F., D’Argenio P., “Testing timed automata”, Theoretical Computer Science, 254:1–2 (2001), 225–257.Springintveld J., Vaandrager F., D’Argenio P., “Testing timed automata”, Theoretical Computer Science, 254:1–2 (2001), 225–257.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.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.Krichen M., Tripakis S., “Conformance testing for real-time systems”, Formal Methods in System Design, 34:3 (2009), 238–304.Krichen M., Tripakis S., “Conformance testing for real-time systems”, Formal Methods in System Design, 34:3 (2009), 238–304.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.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.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.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.Petrenko A., Yevtushenko N., Bochmann G.v., “Fault Models for Testing in Context”, FORTE, 1996, 163–178.Petrenko A., Yevtushenko N., Bochmann G.v., “Fault Models for Testing in Context”, FORTE, 1996, 163–178.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.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.Petrenko A., Yevtushenko N., “Adaptive Testing of Deterministic Implementations Specified by Nondeterministic FSMs”, Proceedings of ICTSS, 2011, 162–178.Petrenko A., Yevtushenko N., “Adaptive Testing of Deterministic Implementations Specified by Nondeterministic FSMs”, Proceedings of ICTSS, 2011, 162–178.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.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.

The authors declare that there are no conflicts of interest present.