maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2016-6-729-740mais-410Research ArticleОригинальные статьиArticlesМетод синтеза тестов с гарантированной полнотой по модели расширенного автоматаDeriving Test Suites with the Guaranteed Fault Coverage for Extended Finite State Machineshttps://orcid.org/0000-0003-0838-8014ЕрмаковА. Д.ErmakovA. D.

аспирант, пр. Ленина, 36, г. Томск, 634050 Россия

researcher, 36 Lenina ave., Tomsk 634050, Russia

antonermak@inbox.ruhttps://orcid.org/0000-0002-4006-1161ЕвтушенкоН. В.YevtushenkoN. V.

профессор, д-р. техн. наук, пр. Ленина, 36, г. Томск, 634050 Россия

Professor, Doctor of Technical Sciences, 36 Lenina ave., Tomsk 634050, Russia

nyevtush@gmail.comТомский государственный университетРоссияTomsk State UniversityRussian Federation201620122016236729740Copyright © Ермаков А.Д., Евтушенко Н.В., 20162016Ермаков А.Д., Евтушенко Н.В.Ermakov A.D., Yevtushenko N.V.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.mais-journal.ru/jour/article/view/410

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

Extended Finite State Machines (EFSMs) are widely used when deriving tests for checking functional requirements for software implementations. However, the fault coverage of tests covering appropriate paths, variables, etc. of the specification EFSM, remains rather obscure and such tests do not detect many functional faults in EFSM implementations. In this paper, an approach is proposed for deriving complete tests with respect to functional faults of a proper Java EFSM implementation. First, an initial test suite derived against the specification EFSM is checked with respect to faults generated by a µJava tool. Since the EFSM software implementation is template based, each undetected fault can be easily mapped into a mutant EFSM of the specification machine. Thus, a distinguishing sequence is derived for two Finite State Machines modeling two EFSMs instead of deriving such a sequence for two programs. If the corresponding FSMs are too complex or cannot be completely derived, a test suite can be incomplete. However, the performed experiments clearly show that a test suite extended by such distinguishing sequences detects much more functional faults in software implementations of a system whose behaviour is described by the given EFSM.

мутационное тестированиерасширенный автоматконечно-автоматная абстракцияµJavaMutation testingExtended Finite State Machine (EFSM)finite automataµJavaReferencesKaur M., Singh R., “A Review of Software Testing Techniques”, International Journal of Electronic and Electrical Engineering, 7:5 (2014), 463–474.Kaur M., Singh R., “A Review of Software Testing Techniques”, International Journal of Electronic and Electrical Engineering, 7:5 (2014), 463–474.Jorgensen P.C., Software Testing: A Craftsman’s Approach, Third Edition, Auerbach Publications, 2008.Jorgensen P.C., Software Testing: A Craftsman’s Approach, Third Edition, Auerbach Publications, 2008.Nica M., Nica S., Wotawa F., “On the use of mutations and testing for debugging”, Software – practice and experience, 43:9 (2013), 1121–1142.Nica M., Nica S., Wotawa F., “On the use of mutations and testing for debugging”, Software – practice and experience, 43:9 (2013), 1121–1142.Nica S., On the Use of Constraints in Program Mutations and its Applicability to Testing, PhD thesis, Graz Technical University, 2013.Nica S., On the Use of Constraints in Program Mutations and its Applicability to Testing, PhD thesis, Graz Technical University, 2013.Petrenko A., Boroday S., Groz R., “Confirming Configurations in EFSM Testing”, IEEE Trans. Software Eng, 30:1 (2004), 29–42.Petrenko A., Boroday S., Groz R., “Confirming Configurations in EFSM Testing”, IEEE Trans. Software Eng, 30:1 (2004), 29–42.El-Fakih K., Salameh T., Yevtushenko N., “On Code Coverage of Extended FSM Based Test Suites: An Initial Assessment”, LNCS, 8763 (2014), 198–204.El-Fakih K., Salameh T., Yevtushenko N., “On Code Coverage of Extended FSM Based Test Suites: An Initial Assessment”, LNCS, 8763 (2014), 198–204.“µJava documentation. µJava home page. URL: http://cs.gmu.edu/~offutt/mujava/”, 2014, (access date: 10.04.2016).“µJava documentation. µJava home page. URL: http://cs.gmu.edu/~offutt/mujava/”, 2014, (access date: 10.04.2016).Villa, T. et al., The Unknown Component Problem: Theory and Applications, Springer, 2012, 313 pp.Villa, T. et al., The Unknown Component Problem: Theory and Applications, Springer, 2012, 313 pp.Ermakov A., Yevtushenko N., “Increasing the fault coverage of tests derived against Extended Finite State Machines”, System informatics, 7 (2016), 23–32.Ermakov A., Yevtushenko N., “Increasing the fault coverage of tests derived against Extended Finite State Machines”, System informatics, 7 (2016), 23–32.Alcalde B. et al., “Network Protocol System Passive Testing for Fault Management: A Backward Checking Approach”, Proc. of the 24th IFIP WG 6.1 Intern. Conf. on Formal Techniques for Networked and Distributed Systems, FORTE’2004, 150–166.Alcalde B. et al., “Network Protocol System Passive Testing for Fault Management: A Backward Checking Approach”, Proc. of the 24th IFIP WG 6.1 Intern. Conf. on Formal Techniques for Networked and Distributed Systems, FORTE’2004, 150–166.Kushik N. et al., “Optimizing Protocol Passive Testing through ‘Gedanken’ Experiments with Finite State Machines”, Proc. of the Intern conference on Sofware Quality and Reliability, QSR’2016, August, 2016.Kushik N. et al., “Optimizing Protocol Passive Testing through ‘Gedanken’ Experiments with Finite State Machines”, Proc. of the Intern conference on Sofware Quality and Reliability, QSR’2016, August, 2016.Kushik N., YeniguЁn H., “Heuristics for Deriving Adaptive Homing and Distinguishing Sequences for Nondeterministic Finite State Machines”, Lecture Notes in Computer Science, 9447 (2015), 243–248.Kushik N., YeniguЁn H., “Heuristics for Deriving Adaptive Homing and Distinguishing Sequences for Nondeterministic Finite State Machines”, Lecture Notes in Computer Science, 9447 (2015), 243–248.Коломеец А.В., Алгоритмы синтеза проверяющих тестов для управляющих систем на основе расширенных автоматов, дис. ... канд. техн. наук, Томский государственный университет, 2010.Kolomeec A. V., Algoritmy sinteza proverjajushhih testov dlja upravljajushhih sistem na osnove rasshirennyh avtomatov, dis. ... kand. tekhn. nauk, Tomsk State University, 2010, (in Russian).Kushik N., Yevtushenko N., Cavalli A., “On Testing against Partial Non-observable Specifications”, Proc. of the Intern. Conf. on the Quality of Information and Communications Technology, 2014, 230–233.Kushik N., Yevtushenko N., Cavalli A., “On Testing against Partial Non-observable Specifications”, Proc. of the Intern. Conf. on the Quality of Information and Communications Technology, 2014, 230–233.Kushik N. et al., “On adaptive experiments for nondeterministic finite state machines”, The Intern. Journal on Software Tools for Technology Transfer, 18:3 (2016), 251–264.Kushik N. et al., “On adaptive experiments for nondeterministic finite state machines”, The Intern. Journal on Software Tools for Technology Transfer, 18:3 (2016), 251–264.El-Fakih K. et al., “Distinguishing extended finite state machine configurations using predicate abstractions”, Journal on Software Research and Development (published online), 2016.El-Fakih K. et al., “Distinguishing extended finite state machine configurations using predicate abstractions”, Journal on Software Research and Development (published online), 2016.Михайлов Ю.В., Коломеец А.В., “Проверка переходов в расширенном автомате на основе срезов”, Вестник ТГУ. Серия: Управление, вычислительная техника и информатика, 3:4 (2008).Mikhaylov Yu. V., Kolomeets A. V., “Proverka perekhodov v rasshirennom avtomate na osnove srezov”, Vestnik TGU. Seriya: Upravlenie, vychislitel’naya tekhnika i informatika, 3:4 (2008), (in Russian).“JUnit 4, documentation. URL: http://cs.gmu.edu/~offutt/mujava/”, (access date: 10.04.2016).“JUnit 4, documentation. URL: http://cs.gmu.edu/~offutt/mujava/”, (access date: 10.04.2016).

The authors declare that there are no conflicts of interest present.