Управляемые вероятностные тесты с ограниченным значением расстояния Хэмминга

Цели. Решается задача построения управляемых вероятностных тестов с фиксированным минимальным расстоянием Хэмминга. Показывается ограниченность применения классических подходов генерирования тестовых наборов, основанных на перечислении кандидатов в тестовые наборы. С повышением пороговых значений мер различия двоичных тестовых наборов увеличивается вычислительная сложность построения таких тестов. Главной целью настоящей статьи является развитие методов построения тестов на базе исходных шаблонов и правил их расширения до требуемой разрядности.

Методы. На базе расстояния Хэмминга, используемого в теории и практике формирования управляемых вероятностных тестов, рассматриваются новые меры различия для сравнения двух двоичных тестовых наборов. Основой предлагаемых мер различия является формирование множества расстояний Хэмминга для исходных наборов, представляемых в виде последовательностей символов различных алфавитов.

Результаты. Показывается неразличимость пар двоичных тестовых наборов при использовании меры различия, основанной на применении расстояния Хэмминга. В этом случае отличающиеся пары наборов могут иметь совпадающие значения расстояния Хэмминга. Рассматриваются новые меры различия двоичных тестовых последовательностей, которые основаны на их представлении в виде последовательностей, состоящих из символов различных алфавитов. В качестве альтернативы известным решениям предлагается подход, базирующийся на увеличении числа тестовых наборов в тесте при сохранении величины минимального значения расстояния Хэмминга между наборами на приемлемом уровне. Главной особенностью предлагаемого подхода является применение предложенной авторами меры различия, основанной на определении расстояния Хэмминга для тестовых наборов, состоящих из символов различных алфавитов. Показано, что достижение максимального значения расстояния Хэмминга для наборов, представленных большим количеством двоичных символов, обеспечивает такое же значение расстояния для случая, когда символы задаются меньшим числом бит. Это позволяет строить управляемые вероятностные тесты без процедуры перечисления кандидатов в тестовые наборы.

Заключение. Рассмотренные меры различия расширяют возможности генерирования тестовых наборов при формировании управляемых вероятностных тестов. Показывается, что использование различных шаблонов и применяемых к ним правил позволяет строить тесты с фиксированным минимальным расстоянием Хэмминга и требуемой разрядностью тестовых наборов.

1. Orso, A. Software testing: A research travelogue (2000–2014) / A. Orso, G. Rothermel // Proc. of Future of Software Engineering Proceeding (FOSE’14), Hyderabad, India, 31 May – 7 June 2014. – Hyderabad, 2014. – P. 117–132.

2. An orchestrated survey on automated software test case generation / S. Anand, E. Burke, T. Chen [et al.] // Journal of Systems and Software. – 2014. – Vol. C-39, no. 4. – P. 582–586.

3. Arcuri, A. Random testing: Theoretical results and practical implications / A. Arcuri, M. Z. Iqbal, L. Briand // IEEE Transactions on Software Engineering. – 2011. – Vol. 38, no. 2. – P. 258–277.

4. Malaiya, Y. K. The coverage problem for random testing / Y. K. Malaiya, S. Yang // Proc. of the Intern. Test Conf., Philadelphia, PA, USA, 16–18 Oct. 1984. – Philadelphia, 1984. – P. 237–242.

5. Duran, J. W. An evaluation of random testing / J. W. Duran, S. C. Ntafos // IEEE Transactions on Software Engineering. – 1984. – Vol. SE-10, no. 4. – P. 438–444.

6. Ярмолик, В. Н. Контроль и диагностика вычислительных систем / В. Н. Ярмолик. – Минск : Бест-принт, 2019. – 387 с.

7. Malaiya, Y. K. Antirandom testing: getting the most out of black-box testing / Y. K. Malaiya // Proc. of the Intern. Symp. on Software Reliability Engineering, Toulose, France, 24–27 Oct. 1995. – Toulose, 1995. – P. 86–95.

8. A survey on adaptive random testing / R. Huang, W. Sun, Y. Xu [et al.] // IEEE Transactions on Software Engineering. – 2021. – Vol. 47, no. 10. – P. 2052–2083.

9. Adaptive random testing: The art of test case diversity / T. Y. Chen, F. C. Kuo, R. G. Merkel, T. H. Tse // Journal of Systems and Software. – 2010. – Vol. 83. – P. 60–66.

10. Antirandom testing: A distance-based approach / S. N. Wu, S. Jandhyala, Y. K. Malaiya, A. P. Jayasumana // Hindawi Publishing Corporation VLSI Design. – 2008. – Vol. 2008, article ID 165709. – 9 p. – DOI: 10.1155/2008/165709.

11. Fast antirandom (FAR) test generation / A. von Mayrhauser, A. Bai, T. Chen [et al.] // Proc. of the Third IEEE Intern. High-Assurance System Engineering Symp., Washington, D.C., USA, 13–14 Nov. 1998. – Washington, 1998. – P. 262–269.

12. Xu, S. Orderly random testing for both hardware and software / S. Xu // Proc. of the 2008 14th IEEE Pacific Rim Intern. Symp. on Dependable Computing, Washington, D.C., USA, 15–17 Dec. 2008. – Washington, 2008. – P. 160–167.

13. Xu, S. Maximum distance testing / S. Xu, J. Chen // Proc. of the 11th IEEE Asian Test Symp. (ATS’02), Guam, USA, 18–20 Nov. 2002. – Guam, 2002. – P. 15–20.

14. Kuo, F. C. An indepth study of mirror adaptive random testing / F. C. Kuo // Proc. of the Ninth Intern. Conf. on Quality Software (QSIC 2009), Jeju, Korea (South), 24–25 Aug. 2009. – Jeju, 2009. – P. 51–58.

15. Tappenden, A. A novel evolutionary approach for adaptive random testing / A. Tappenden, J. Miller // IEEE Transactions on Reliability. – 2009. – Vol. 58, no. 4. – P. 619–633.

16. Zhibo, Li. An enhanced adaptive random testing by dividing dimensions independently / Li Zhibo, Li Qingbao, Yu Lei // Mathematical Problems in Engineering. – 2019. – Vol. 2019. – P. 1–15.

17. Nikravan, E. Hybrid adaptive random testing / E. Nikravan, S. Parsa // International Journal of Computing Science & Mathematics. – 2020. – Vol. 11, no. 3. – P. 209.

18. Yarmolik, S. V. Controlled random tests / S. V. Yarmolik, V. N. Yarmolik // Automation and Remote Control. – 2012. – Vol. 73, no. 10. – P. 1704–1714.

19. Mrozek, I. Antirandom test vectors for BIST in hardware/software systems / I. Mrozek, V. N. Yarmolik // Fundamenta Informaticae. – 2012. – Vol. 119, no. 2. – P. 163–185.

20. Mrozek, I. Multiple controlled random testing / I. Mrozek, V. N. Yarmolik // Fundamenta Informaticae. – 2016. – Vol. 144, no. 1. – P. 23–43.

21. Ярмолик, С. В. Итеративные почти псевдоисчерпывающие вероятностные тесты / С. В. Ярмолик, В. Н. Ярмолик // Информатика. – 2010. – № 2(26). – С. 66–75.

22. Hamming, R. W. Error detecting and error correcting codes / R. W. Hamming // The Bell System Technical Journal. – 1950. – Vol. 29, no. 2. – P. 147–160.

23. Peterson, W. W. Error-Correction Codes / W. W. Peterson, E. J. Weldon. – Cambridge, Massachusetts, London, England : The MIT Press, 1972. – 560 p.

24. Садовский, М. Г. О сравнении символьных последовательностей / М. Г. Садовский // Вычислительные технологии. – 2005. – № 3(10). – С. 106–116.

25. Ярмолик, В. Н. Модификации способов определения расстояния Хэмминга для их применения в качестве мер различия при генерировании управляемых вероятностных тестов / В. Н. Ярмолик, В. В. Петровская, Н. А. Шевченко // Информатика. – 2024. − Т. 21, № 2. – С. 54–72.

26. Многомерный портрет цифровых последовательностей идеального «белого шума» в свертках Хэмминга / В. И. Волчихин, А. И. Иванов, А. П. Юнин, Е. А. Малыгина // Информатика, вычислительная техника и управление. – 2017. – № 4(1). – С. 4–12.

27. Ярмолик, В. Н. Мера различия для управляемых вероятностных тестов / В. Н. Ярмолик, В. В. Петровская, Н. А. Шевченко // Доклады БГУИР. – 2024. – № 4(22). – С. 76–83.

28. Plotkin, M. Binary codes with specified minimum distance / M. Plotkin // IRE Transactions on Information Theory. – 1960. – Vol. 6, no. 4. – P. 445–450.

29. Yarmolik, S. V. The synthesis of probability tests with a small number of kits / S. V. Yarmolik, V. N. Yarmolik // Automatic Control and Computer Sciences. – 2011. – Vol. 45, no. 3. – P. 133–141.

30. Mrozek, I. Optimal controlled random tests / I. Mrozek, V. Yarmolik // Proc. of Computer Information Systems and Industrial Management: 16th IFIP TC8 Intern. Conf., CISIM 2017, Bialystok, Poland, 16–18 June 2017. – Bialystok, 2017. – P. 27–38.

31. Sokol, B. Memory faults detection techniques with use of degrees of freedom in march tests / B. Sokol, V. N. Yarmolik // Proc. of IEEE East-West Design & Test Workshop (EWDTW’05), Odessa, Ukraine, 15–19 Sept. 2005. – Odessa, 2005. – P. 96–101.

32. Ярмолик, С. В. Обнаружение кодочувствительных неисправностей запоминающих устройств с многократным использованием маршевых тестов / С. В. Ярмолик, В. Н. Ярмолик // Информатика. – 2006. − Т. 19, № 1. – С. 104–113.