ellibsЭлектронные библиотекиRussian Digital Libraries Journal1562-5419Казанский (Приволжский) федеральный университет10.26907/1562-5419-2023-26-1-18-34ellibs-363Research ArticleСтатьиКонечно-автоматные методы синтеза тестов с гарантированной полнотой для входо-выходных полуавтоматовUsing FSM-Based Strategies for Deriving Tests with Guaranteed Fault Coverage for Input/Output AutomataБурдоновИ. Б.BurdonovI. B.igorburdonov@yandex.ruЕвтушенкоН. В.YevtushenkoN. V.nyevtush@gmail.comКосачевА. С.KossachevA. S.askosachev@gmail.comИнститут системного программирования им. В.П. Иванникова Российской академии наукIvannikov Institute for system programming of the Russian Academy of Sciences2023280220232611834Copyright © Бурдонов И.Б., Евтушенко Н.В., Косачев А.С., 20232023Бурдонов И.Б., Евтушенко Н.В., Косачев А.С.Burdonov I.B., Yevtushenko N.V., Kossachev A.S.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://ellibs.elpub.ru/jour/article/view/363

Рассмотрена проблема использования конечно-автоматных методов для построения конечных тестов с гарантированной полнотой для входо-выходных полуавтоматов. Предложен способ построения конечного автомата, соответствующего полуавтомату-спецификации, и показано, что конечные тесты, построенные по такому автомату, подаваемые на вход-выходной полуавтомат при выполнении специальных таймаутов, являются полными относительно различных моделей неисправности.

In this paper, we study the possibility of using Finite State Machine (FSM-) based methods for deriving finite test suites with guaranteed fault coverage for Input / Output automata. A method for deriving an FSM for a given automaton is proposed and it is shown that finite test suites derived for such an FSM are complete for two fault models based on Input/Output automata if they are applied within the framework of proper timeouts.

входо-выходной полуавтоматконечный автоматмодель неисправностиполный тестInput/Output automatonFinite State machinefault modelcomplete test suiteReferencesHennie F.C. Fault-Detecting Experiments for Sequential Circuits // The Fifth Ann. Symp. Switching Circuit Theory and Logical Design. 1964. P. 95–110.Hennie F.C. Fault-Detecting Experiments for Sequential Circuits // The Fifth Ann. Symp. Switching Circuit Theory and Logical Design. 1964. P. 95–110.Василевский M. П. О распознавании неисправности автоматов // Кибернетика. 1973. № 4. С. 98–108.Василевский M. П. О распознавании неисправности автоматов // Кибернетика. 1973. № 4. С. 98–108.Bochmann G., Petrenko A. Protocol testing: review of methods and relevance for software testing // Intern. Symp. on Software Testing and Analysis. 1994. P. 109–123.Bochmann G., Petrenko A. Protocol testing: review of methods and relevance for software testing // Intern. Symp. on Software Testing and Analysis. 1994. P. 109–123.Dorofeeva R., El-Fakih K., Cavalli A., Maag S., Yevtushenko N. FSM-based conformance testing methods: A survey annotated with experimental evaluation // Information & Software Technology. 2010. Vol. 52. No 12. P. 1286–1297.Dorofeeva R., El-Fakih K., Cavalli A., Maag S., Yevtushenko N. FSM-based conformance testing methods: A survey annotated with experimental evaluation // Information & Software Technology. 2010. Vol. 52. No 12. P. 1286–1297.Tretmans J. A formal approach to conformance testing // The Intern. Workshop on Protocol Test Systems. 1993. P. 257–276.Tretmans J. A formal approach to conformance testing // The Intern. Workshop on Protocol Test Systems. 1993. P. 257–276.Бурдонов И.Б., Косачев А.С., Кулямин В.В. Теория соответствия для систем с блокировками и разрушением. М.: Наука, Глав. ред. физ.-мат. лит., 2008. 412 c.Бурдонов И.Б., Косачев А.С., Кулямин В.В. Теория соответствия для систем с блокировками и разрушением. М.: Наука, Глав. ред. физ.-мат. лит., 2008. 412 c.Kushik N., Forostyanova M., Prokopenko S., Yevtushenko N. Studying the optimal height of the EFSM equivalent for testing telecommunication protocols // Intern. Conf. on Advances in Computing, Communication and Information Technology. 2014. P. 159–163.Kushik N., Forostyanova M., Prokopenko S., Yevtushenko N. Studying the optimal height of the EFSM equivalent for testing telecommunication protocols // Intern. Conf. on Advances in Computing, Communication and Information Technology. 2014. P. 159–163.Жигулин М.В., Коломеец А.В., Кушик Н.Г., Шабалдин А.В. Тестирование программной реализации протокола IRC на основе модели расширенного автомата // Известия Томского политехнического университета. 2011. Т. 318. № 5. С. 81–84.Жигулин М.В., Коломеец А.В., Кушик Н.Г., Шабалдин А.В. Тестирование программной реализации протокола IRC на основе модели расширенного автомата // Известия Томского политехнического университета. 2011. Т. 318. № 5. С. 81–84.Lee D, Yannakakis M. Principles and methods of testing finite-state machines – a survey // Proceedings of the IEEE. 1996. Vol. 84. No. 8. P. 1089–1123.Lee D, Yannakakis M. Principles and methods of testing finite-state machines – a survey // Proceedings of the IEEE. 1996. Vol. 84. No. 8. P. 1089–1123.Petrenko A., Yevtushenko N. Testing from Partial Deterministic FSM Specifications // IEEE Trans. Computers. 2005. Vol. 54. No. 9. P. 1154–1165.Petrenko A., Yevtushenko N. Testing from Partial Deterministic FSM Specifications // IEEE Trans. Computers. 2005. Vol. 54. No. 9. P. 1154–1165.Petrenko A., Yevtushenko N. Conformance Tests as Checking Experiments for Partial Nondeterministic FSM // Lecture Notes in Computer Science. 2005. Vol. 3997. P. 118–133.Petrenko A., Yevtushenko N. Conformance Tests as Checking Experiments for Partial Nondeterministic FSM // Lecture Notes in Computer Science. 2005. Vol. 3997. P. 118–133.Yevtushenko N., Burdonov I., Kossachev A. Deriving Distinguishing Sequences for Input/Output Automata // The IEEE East-West Design & Test Symposium. 2020. P. 1–5.Yevtushenko N., Burdonov I., Kossachev A. Deriving Distinguishing Sequences for Input/Output Automata // The IEEE East-West Design & Test Symposium. 2020. P. 1–5.Бурдонов И.Б., Евтушенко Н.В., Косачев А.С. Синтез тестов с гарантированной полнотой для входо-выходных полуавтоматов // XXIV Всероссийская научная конференция «Научный сервис в сети Интернет». 2022. C. 93–103.Бурдонов И.Б., Евтушенко Н.В., Косачев А.С. Синтез тестов с гарантированной полнотой для входо-выходных полуавтоматов // XXIV Всероссийская научная конференция «Научный сервис в сети Интернет». 2022. C. 93–103.Гилл А. Введение в теорию конечных автоматов. Наука, 1966. 272 с.Гилл А. Введение в теорию конечных автоматов. Наука, 1966. 272 с.Petrenko A., Yevtushenko N., Bochmann G. Fault models for testing in context // Intern. Conf. on Formal Description Techniques IX. 1996. P. 163–178.Petrenko A., Yevtushenko N., Bochmann G. Fault models for testing in context // Intern. Conf. on Formal Description Techniques IX. 1996. P. 163–178.Жигулин М.В. Методы синтеза проверяющих тестов с гарантированной полнотой для контроля дискретных управляющих систем на основе временных автоматов. Дис. ... канд. тех. наук. 2012. 109 c.Жигулин М.В. Методы синтеза проверяющих тестов с гарантированной полнотой для контроля дискретных управляющих систем на основе временных автоматов. Дис. ... канд. тех. наук. 2012. 109 c.Vinarskii E., Lopez J., Kushik N., Yevtushenko N., Zeghlache D. A model checking based approach for detecting sdn races // The 31st IFIP WG 6.1 Intern. Conf. on Testing Software and Systems. 2019. P. 194–211.Vinarskii E., Lopez J., Kushik N., Yevtushenko N., Zeghlache D. A model checking based approach for detecting sdn races // The 31st IFIP WG 6.1 Intern. Conf. on Testing Software and Systems. 2019. P. 194–211.

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