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.

directed graphs, graph coverage, communicating automata, automata composition, distributed systems, testing, networks

1. I. B. Burdonov, A. S. Kossatchev. Testirovanie sistemy avtomatov [Testing of automata system]. Trudy ISP RAN [The proceeding of ISP RAS], Vol. 28, (Issue 1), 2016, pp. 103-130 (in Russian). DOI: 10.15514/ISPRAS-2016-28(1)-7

2. I. B. Burdonov, A. S. Kossatchev. Sistema avtomatov: kompoziciia po grafu sviazei [Automata system: composition on connection graph]. Trudy ISP RAN [The proceeding of ISP RAS], Vol. 28 (Issue 1), 2016, pp. 131-150 (in Russian). DOI: 10.15514/ISPRAS-2016-28(1)-8

3. Revised Working Draft on “Framework: Formal Methods in Conformance Testing”. JTC1/SC21/WG1/Project 54/1, ISO Interim Meeting, ITU-T on, Paris, 1995.

4. Bourdonov I.B., Kossatchev A.S., Kuliamin V.V. Teoriya sootvetstviya dlya system s blokirovkami I razrusheniem [Conformance theory of the systems with Refused Inputs and Forbidden Actions]. Moscow, «Nauka», 2008, 412 p. (in Russian)

5. Bourdonov I. Teoriya konformnosti (funkcional'noe testirovanie prorammny'kh system na osnove formal'ny'kh modelej [Conformance theory (functional testing on formal model base)]. LAP LAMBERT Academic Publishing, Saarbrucken, Germany, 2011, ISBN 978-3-8454-1747-9, 428 p. (in Russian)

6. 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

7. 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

8. 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

9. A. Levitin. Algoritmy: vvedenie v razrabotku i analiz [Introduction to The Design and Analysis of Algorithms]. M.: «Viliams», 2006, pp. 160-163, ISBN 0-201-74395-7. (in Russian)

10. 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.

11. 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

12. 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

13. Bourdonov I.B., Kossatchev A.S. Semantiki vzaimodejstviya s otkazami, divergentsiej i razrusheniem. Chast' 2. Usloviya konechnogo polnogo testirovaniya. [Semantics of Interaction with Refused Inputs, Divergence and Forbidden Actions. Part 2. The condition of finite complete testing]. Vestnik Tomskogo gosudarstvennogo universiteta. Upravlenie, vychislitel'naya tekhnika i informatika. [Tomsk State University. Journal of Control and Computer Science], 2011, №2, pp. 89-98. (in Russian)

14. Bourdonov I.B., Kossatchev A.S. Testirovanie konformnosti na osnove sootvetstviya sostoyanij [Conformance testing based on a state relation]. Trudy ISP RAN [The proceeding of ISP RAS], vol. 18, 2010, pp. 183-320. (in Russian)

15. 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

16. 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.

17. 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

18. Bourdonov I.B., Kossatchev A.S., Kuliamin V.V. Bezopasnost', verifikatsiya i teoriya konformnosti [Safety, Verification and Conformance Theory]. Materialy Vtoroj mezhdunarodnoj nauchnoj konferentsii po problemam bezopasnosti i protivodejstviya terrorizmu [The proceeding of the Second international conference on the problems of safety and counteraction against terrorizm], Moscow, MNCMO, 2007, pp. 135-158. (in Russian)

19. 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

20. Bourdonov I.B., Kossatchev A.S. Testirovanie s preobrazovaniem semantic [Testing with Semantics Conversion] Trudy ISP RAN [The proceeding of ISP RAS], vol. 17, 2009, pp. 193-208. (in Russian)

21. 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.

22. 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

23. 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