Система автоматов: условия детерминизма и тестирование
Автор: Бурдонов И.Б., Косачев А.С.
Журнал: Труды Института системного программирования РАН @trudy-isp-ran
Статья в выпуске: 1 т.28, 2016 года.
Бесплатный доступ
Статья посвящена проблеме тестирования составных систем, компоненты которых моделируются конечными автоматами с несколькими входами и выходами, а взаимодействие между ними - обменом сообщениями по симплексным каналам связи. Система описывается ориентированным графом связей, вершина которого соответствует автомату компонента, а дуга - каналу связи, соединяющему выход одного автомата со входом другого автомата. Предполагается выполненной следующая гипотеза о связях: граф связей статический, а отображаемая им структура связей не содержит ошибок. Автомат, находящийся в вершине графа, в каждом состоянии может принимать несколько сообщений по своим входам (не более одного по каждому входу) и посылать несколько сообщений по своим выходам (не более одного по каждому выходу). Определяется ассоциативная композиция автоматов системы. Показывается, при каких ограничениях на автоматы и граф связей их композиция, т.е. сама система, детерминирована. Целью тестирования является покрытие переходов автоматов компонентов, которые достижимы при работе этих автоматов в системе. Предполагается, что при тестировании возможно наблюдение изменения состояний автоматов системы и передаваемых между ними сообщений. Полное тестирование системы автоматов без учёта гипотезы о связях может потребовать число тестовых воздействий порядка произведения чисел состояний автоматов компонентов, а с учётом гипотезы о связях - порядка суммы этих чисел. При равном числе состояний всех автоматов это даёт экспоненциальное уменьшение числа тестовых воздействий. При условии выполнения гипотезы о связях для детерминированной системы предлагается алгоритм генерации тестов, основанный на фильтрации тестов, генерируемых для покрытия всех переходов композиции. Тест отбрасывается, если он покрывает только такие переходы в компонентах системы, которые покрываются остающимися тестами. В заключение определяются направления дальнейших исследований.
Ориентированные графы, покрытие графа, взаимодействующие автоматы, композиция автоматов, детерминизм, распределенные системы, тестирование, сети
Короткий адрес: https://sciup.org/14916319
IDR: 14916319 | DOI: 10.15514/ISPRAS-2016-28(1)-9
Automata system: determinism conditions and testing
The problem of testing of aggregate systems is considered. The system components are described with finite automata with multiple entries and exits. The communication between automata is described with message passing over simplex communication channels. The system is described with an oriented graph of links. Each node of the graph corresponds to automaton of a component and an arc corresponds to a communication channel connecting exit of one automaton with entry of another automaton. The hypothesis of the links is assumed: the graph of links is static and the link structure is error-free. Automaton of the graph node in each state can accept multiple messages from its entries (at most one message from each entry) and send multiple messages to its exits (at most one message to each exit). An associative composition of the automata is defined. The restrictions on the automata and the graph of links are determined, for which their composition, i.e. the system itself, is deterministic. The goal of testing is to cover transitions of the automata reachable during the system work. It assumed that during testing it is possible to observe the states of automata and the messages on the arcs. The complete testing of the automata system without considering the hypothesis of links may require the number of testing actions of order of multiplication of numbers of states of the component automata, while with the consideration of the hypothesis of links - of order of the sum of these numbers. If the numbers of states of all automata are equal, it gives exponential reduction of the number of test actions. If the hypothesis of links is true, an algorithm of test generation for a deterministic system is proposed basing on filtration of tests generated for covering all transitions of the composition. Test is rejected if it covers only such transitions of the components that are covered by the remaining tests. In conclusion, the directions of future research are described.
Список литературы Система автоматов: условия детерминизма и тестирование
- I. B. Burdonov, A. S. Kossatchev. Testirovanie sistemy avtomatov Trudy ISP RAN , Vol. 28, (Issue 1), 2016, pp. 103-130 DOI: 10.15514/ISPRAS-2016-28(1)-7
- I. B. Burdonov, A. S. Kossatchev. Sistema avtomatov: kompoziciia po grafu sviazei Trudy ISP RAN , Vol. 28 (Issue 1), 2016, pp. 131-150 DOI: 10.15514/ISPRAS-2016-28(1)-8
- Revised Working Draft on “Framework: Formal Methods in Conformance Testing”. JTC1/SC21/WG1/Project 54/1, ISO Interim Meeting, ITU-T on, Paris, 1995.
- Bourdonov I.B., Kossatchev A.S., Kuliamin V.V. Teoriya sootvetstviya dlya system s blokirovkami I razrusheniem . Moscow, «Nauka», 2008, 412 p.
- Bourdonov I. Teoriya konformnosti (funkcional'noe testirovanie prorammny'kh system na osnove formal'ny'kh modelej . LAP LAMBERT Academic Publishing, Saarbrucken, Germany, 2011, ISBN 978-3-8454-1747-9, 428 p.
- Bourdonov I.B., Kossatchev A.S. Specification Completion for IOCO. Programming and Computer Software, vol. 37(1), 2011, pp. 1-14 DOI: 10.1134/S0361768811010014
- A. S. Kamkin, M. M. Chupilko. Survey of modern technologies of simulation-based verification of hardware. Programming and Computer Software, vol. 37 (3), 2011, pp. 147-152 DOI: 10.1134/S0361768811030017
- I. B. Burdonov, A. S. Kossatchev, V. V. Kuliamin. Irredundant Algorithms for Traversing Directed Graphs: The Deterministic Case. Programming and Computer Software, vol. 29(5), 2003, pp. 245-258 DOI: 10.1023/A:1025733107700
- A. Levitin. Algoritmy: vvedenie v razrabotku i analiz . M.: «Viliams», 2006, pp. 160-163, ISBN 0-201-74395-7.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. Introduction to Algorithms. 2-nd Edition. MIT Press Cambridge, MA, USA, 2001, ISBN 0-262-03293-7.
- Bourdonov I.B., Kossatchev A.S., Kuliamin V.V. Application of Finite Automatons for Program Testing. Programming and Computer Software, vol. 26(2), 2000, pp. 61-73 DOI: 10.1007/BF02759192
- Bourdonov I.B., Kossatchev A.S. Complete Open-State Testing of Limitedly Nondeterministic Systems. Programming and Computer Software, vol. 35(6), 2009, pp.301-313 DOI: 10.1134/S0361768809060012
- Bourdonov I.B., Kossatchev A.S. Semantiki vzaimodejstviya s otkazami, divergentsiej i razrusheniem. Chast' 2. Usloviya konechnogo polnogo testirovaniya. . Vestnik Tomskogo gosudarstvennogo universiteta. Upravlenie, vychislitel'naya tekhnika i informatika. , 2011, №2, pp. 89-98.
- Bourdonov I.B., Kossatchev A.S. Testirovanie konformnosti na osnove sootvetstviya sostoyanij . Trudy ISP RAN , vol. 18, 2010, pp. 183-320.
- Bourdonov I.B., Kossatchev A.S. Safe simulation testing of systems with refusals and destructions. Automatic Control and Computer Sciences, vol. 45(7), 2011, pp. 380-389 DOI: 10.3103/S0146411611070042
- 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.
- Bourdonov I.B., Kossatchev A.S., Kuliamin V.V. Formalization of Test Experiments. Programming and Computer Software, vol. 33(5), 2007, pp. 239-260 DOI: 10.1134/S0361768807050015
- Bourdonov I.B., Kossatchev A.S., Kuliamin V.V. Bezopasnost', verifikatsiya i teoriya konformnosti . Materialy Vtoroj mezhdunarodnoj nauchnoj konferentsii po problemam bezopasnosti i protivodejstviya terrorizmu , Moscow, MNCMO, 2007, pp. 135-158.
- Bourdonov I.B., Kossatchev A.S. Systems with Priorities: Conformance, Testing, and Composition. Programming and Computer Software, 2009, Vol/35(4), pp.198-211 DOI: 10.1134/S0361768809040045
- Bourdonov I.B., Kossatchev A.S. Testirovanie s preobrazovaniem semantic Trudy ISP RAN , vol. 17, 2009, pp. 193-208.
- 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.
- Bourdonov I.B., Kossatchev A.S. Interaction Semantics with Refusals, Divergence, and Destruction. Programming and Computer Software, vol. 36(5), 2010, pp. 247-263 DOI: 10.1134/S0361768810050014
- Bourdonov I.B., Kossatchev A.S. Agreement between Conformance and Composition. Programming and Computer Software, vol. 39(6), 2013, pp. 269-278 DOI: 10.1134/S0361768813060029
