Preview

Труды Института системного программирования РАН

Расширенный поиск

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

https://doi.org/10.15514/ISPRAS-2018-30(4)-9

Полный текст:

Аннотация

Конечные автоматы широко используются при построении проверяющих тестов для управляющих систем с гарантированной полнотой обнаружения неисправностей. В ряде случаев такие тесты достигают экспоненциальной длины относительно размеров автомата-спецификации, что мотивирует исследования по оптимизации проверяющих тестов. Существование последовательностей, различающих каждую пару состояний в автомате-спецификации, может существенно сократить длину теста, если такие последовательности достаточно короткие. Более того, при описании современных систем часто приходится учитывать опциональность неформальной спецификации, и соответственно, использовать методы синтеза тестов для недетерминированных автоматов; последнее в большинстве случаев повышает длину тестов. Адаптивные различающие последовательности существуют чаще, чем безусловные, и, как правило, имеют меньшую длину, что делает их выбор более предпочтительным для синтеза тестов. В настоящей работе мы исследуем свойства адаптивных различающих последовательностей и оптимизируем метод построения таковых для полностью определённых, возможно, недетерминированных конечных автоматов. Предложенный подход основан на ограничении размеров различающего автомата, по которому строится различающий тестовый пример, служащий удобной формой представления адаптивной различающей последовательности. Проведённые эксперименты позволили оценить длину и вероятность существования адаптивных различающих последовательностей для случайно сгенерированных автоматов с различной степенью недетерминизма. Также в работе рассмотрен специальный класс так называемых автоматов без слияний, которые описывают широкий класс реальных систем и обладают «хорошими» для синтеза тестов свойствами; в частности, для таких автоматов практически всегда существуют адаптивные различающие последовательности, если для каждой пары «состояние, входной символ» существует не более трех различных переходов, т.е. степень недетерминизма в автомате не больше трех.

Об авторах

А. С. Твардовский
Национальный исследовательский Томский Государственный университет
Россия


Н. В. Евтушенко
Национальный исследовательский Томский Государственный университет; Институт системного программирования им. В.П. Иванникова РАН; Национальный исследовательский университет “Высшая школа экономики”
Россия


Список литературы

1. Гилл А. Введение в теорию конечных автоматов. М., Наука, 1966, 272 стр.

2. Chow, T.S. Test design modeled by finite-state machines. IEEE Transactions on Software Engineering, vol. 4, No 3, 1978, pp. 178-187

3. Petrenko A. and Yevtushenko N. Conformance Tests as Checking Experiments for Partial Nondeterministic FSM. In Proceedings of the 5th International Workshop on Formal Approaches to Testing of Software (FATES 2005), LNCS 3997, 2005, pp. 118-133

4. Dorofeeva R., El-Fakih K., Maag S., Cavalli A.R., Yevtushenko N. FSM-based conformance testing methods: a survey annotated with experimental evaluation. Information and Software Technology, 52, 2010, pp. 1286-1297

5. Alur R., Courcoubetis C., Yannakakis M. Distinguishing tests for nondeterministic and probabilistic machines, In Proc. of the 27th ACM Symposium on Theory of Computing, 1995, pp. 363-372.

6. Petrenko A., Yevtushenko N. Adaptive testing of deterministic implementations specified by nondeterministic FSMs, In Proc. of the International Conference on Testing Software and Systems, LNCS, vol. 7019, 2011, pp. 162-178

7. 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 (EWDTS). 2015. P. 338-341

8. Yevtushenko N., El-Fakih K., and Ermakov, A. On-the-fly construction of adaptive checking sequences for testing deterministic implementations of nondeterministic specifications, LNCS, vol. 9976, 2016, pp. 139-152

9. El-Fakih K., Yevtushenko N., Kushik N. Adaptive distinguishing test cases of nondeterministic finite state machines: test case derivation and length estimation. Formal Aspects of Computing vol. 30, issue 2, 2018, pp. 319-332

10. Tvardovskii A. Refining the Specification FSM When Deriving Test Suites w.r.t. the Reduction Relation. LNCS, vol 10533, 2017, pp. 333-339

11. Shabaldina N. Gromov M. FSMTest-1.0: a manual for researches. In Proceedings of the 13th International symposium on IEEE EAST-WEST DESIGN & TEST SYMPOSIUM (EWDTS’15), 2015, pp. 216-219


Для цитирования:


Твардовский А.С., Евтушенко Н.В. К синтезу адаптивных различающих последовательностей для конечных автоматов. Труды Института системного программирования РАН. 2018;30(4):139-154. https://doi.org/10.15514/ISPRAS-2018-30(4)-9

For citation:


Tvardovskii A.S., Yevtushenko N.V. Deriving adaptive distinguishing sequences for Finite State Machines. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2018;30(4):139-154. (In Russ.) https://doi.org/10.15514/ISPRAS-2018-30(4)-9

Просмотров: 120


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2079-8156 (Print)
ISSN 2220-6426 (Online)