Тестирование системы автоматов с буферизацией сообщений
Автор: Бурдонов И.Б., Косачев А.С.
Журнал: Труды Института системного программирования РАН @trudy-isp-ran
Статья в выпуске: 1 т.28, 2016 года.
Бесплатный доступ
Статья посвящена проблеме тестирования составных систем, компоненты которых моделируются конечными автоматами, а взаимодействие между ними - обменом сообщениями по симплексным каналам связи. Система описывается ориентированным графом связей, вершины которого соответствуют автоматам компонентов, а дуги - каналам связи. Предполагается выполненной следующая гипотеза о связях: граф связей статический, а отображаемая им структура связей не содержит ошибок. Автомат, находящийся в вершине графа, в каждом состоянии может принимать несколько сообщений по входным дугам (не более одного по каждой дуге) и посылать несколько сообщений по выходным дугам (не более одного по каждой дуге). Целью тестирования является покрытие переходов автоматов компонентов, которые достижимы при работе этих автоматов в системе. Предполагается, что при тестировании возможно наблюдение изменения состояний автоматов в вершинах графа и сообщений на дугах графа. Сначала рассматривается упрощённая модель системы, в которой циркулирует только одно сообщение. На её примере показывается, что гипотеза о связях позволяет существенно сократить время тестирования. Полное тестирование системы автоматов без учёта гипотезы о связях может потребовать число тестовых воздействий порядка произведения чисел состояний автоматов компонентов, а с учётом гипотезы о связях - порядка суммы этих чисел. При равном числе состояний всех автоматов это даёт экспоненциальное уменьшение числа тестовых воздействий. Затем рассматривается более общая модель, когда в системе может быть одновременно много сообщений, но не более одного на каждой дуге. Определяется композиция автоматов системы и показывается, при каких ограничениях на автоматы их композиция детерминирована. Для детерминированной композиции предлагается алгоритм генерации тестов, основанный на фильтрации тестов, генерируемых для покрытия всех переходов композиции. Тест отбрасывается, если он покрывает только такие переходы в компонентах системы, которые покрываются остающимися тестами. В заключение определяются направления дальнейших исследований.
Ориентированные графы, покрытие графа, взаимодействующие автоматы, распределенные системы, тестирование, сети
Короткий адрес: https://sciup.org/14916317
IDR: 14916317 | DOI: 10.15514/ISPRAS-2016-28(1)-7
Testing of automata system
The problem of testing of aggregate systems is considered. The system is described with an oriented graph of links. The nodes correspond to automata of the components and arcs correspond to simplex communication channels. The hypothesis of the links is assumed: the graph of links is static and the link structure is error-free. In each state, the automaton can accept and send multiple messages through incoming and outgoing arcs (at most one message through each arc). 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 state changes of automata and the messages on the arcs. A simplified system model with only one message circulating is considered at the beginning. On its example we show that the hypothesis on links allows considerably reduce the number of required testing actions from the multiplication of numbers of the component automata states to 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. Then the more general model is considered when the system can simultaneously contain multiple messages, but not more than one on each arc. A composition of the system automata is defined and the restrictions on automata making the system deterministic are described. An algorithm of test generation is proposed basing on test filtration generated for covering all transitions of the deterministic composition system. 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.
Список литературы Тестирование системы автоматов с буферизацией сообщений
- 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.1109/HASE.2014.39
- 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 DOI: 10.1016/j.entcs.2006.09.008
- Bourdonov I.B., Kossatchev A.S., Kuliamin V.V. Formalization of Test Experiments. Programming and Computer Software, vol. 33(5), 2007, pp. 239-260. 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. Sistemy s prioritetami: konformnost', testirovanie, kompozitsiya . Trudy ISP RAN , vol. 14(1), 2008, pp.23-54
- 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
