К синтезу адаптивных проверяющих последовательностей для недетерминированных автоматов

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

недетерминированный конечный автомат, отношение редукции, модель неисправности, адаптивная проверяющая последовательность

1. Kohavi Z. Switching and Finite Automata Theory, McGraw-Hill, New York, 1978.

2. Chow T.S. “Testing software Design Modelled by Finite State Machines”, In IEEE Trans. Software Eng. Vol. 4 (3), 1978, pp. 178-187.

3. Dorofeeva R., El-Fakih K., Maag S., Cavalli A., Yevtushenko N. “FSM-based conformance testing methods: A survey annotated with experimental evaluation”, In Information & Software Technology, Vol. 52 (12), 2010, pp. 1286-1297.

4. Hennie F.C. “Fault-Detecting Experiments for Sequential Circuits”, In Proc. Fifth Ann. Symp. Switching Circuit Theory and Logical Design, 1964, pp. 95-110.

5. Petrenko A., Simão A., Yevtushenko N. “Generating Checking Sequences for Nondeterministic Finite State Machines”, In Proceedings of the ICST, 2012, pp. 310-319.

6. Жигулин M.В., Коломеец А.В., Кушик Н.Г., Шабалдин А.В. “Тестирование программной реализации протокола IRC на основе модели расширенного”, Известия Томского политехнического университета, Т. 318 (5), 2011, сс. 81-84.

7. Petrenko A., Simão A. “Generalizing the DS-Methods for Testing Non-Deterministic FSMs”, In Comput. J. 58(7), 2015, pp. 1656-1672.

8. Ермаков А.Д.“Синтез проверяющих последовательностей для недетерминированных автоматов относительно редукции”, Труды ИСП РАН, Т. 26(6), 2014, сс. 111-124.

9. Alur R., Courcoubetis C., Yannakakis M. “Distinguishing tests for nondeterministic and probabilistic machines”, In Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, 1995, pp. 363-372.

10. Kushik N., El-Fakih K., Yevtushenko N. ”Adaptive Homing and Distinguishing Experiments for Nondeterministic Finite State Machines”, In Lecture Notes in Computer Science, Vol. 8254, 2013, pp. 33-48.

11. Petrenko A., Yevtushenko N. “Conformance Tests as Checking Experiments for Partial Nondeterministic FSM”, In Lecture Notes in Computer Science, Vol. 3997, 2005, pp. 118-133.

12. Petrenko A., Yevtushenko N. “Adaptive Testing of Deterministic Implementations Specified by Nondeterministic FSMs”, In Lecture Notes in Computer Science, Vol. 7019, 2011, pp. 162-178.

13. Кушик Н.Г. Методы синтеза установочных и различающих экспериментов с недетерминированными автоматами. Диссертация на соискание ученой степени кандидата физико-математических наук, Томский Государственный университет, 2013.

14. Shabaldina N., El-Fakih K., Yevtushenko N. “Testing Nondeterministic Finite State Machines with Respect to the Separability Relation”, In Proceedings of Intern. Conf. on Testing Systems and Software (ICTSS/FATYES), 2007, pp. 305-318.

15. Ветрова М.В. Разработка алгоритмов синтеза и тестирования конечно-автоматных компенсаторов. Диссертация на соискание ученой степени технических наук, Томский Государственный университет, 2004.

16. Yevtushenko N., Kushik N. “Decreasing the length of Adaptive Distinguishing Experiments for Nondeterministic Merging-free Finite State Machines”, In Proceedings of IEEE East-West Design & Test Symposium, pp.338 - 341.

17. Güniçen C., Inan K., Türker U.C., Yenigün H. “The relation between preset distinguishing sequences and synchronizing sequences”, In Formal Aspects of Computing, Vol. 26 (6), 2014, pp. 1153-1167.

18. Kushik N., Yevtushenko N., Yenigun H. “Reducing the complexity of checking the existence and derivation of adaptive synchronizing experiments for nondeterministic FSMs”, In Proceedings of International Workshop on Domain Specific Model-based Approaches to Verification and Validation (AMARETTO’2016), 2016, pp. 83-90.