Масштабирование управляемых вероятностных тестов с применением матриц Адамара

Цели. Решается задача двухмерного масштабирования управляемых вероятностных тестов небольшого размера, задающих исходные шаблоны, с помощью матриц Адамара. Показывается ограниченность применения классических подходов генерирования тестов, основанных на перечислении кандидатов в тестовые наборы. С повышением пороговых значений мер различия двоичных тестовых наборов увеличивается вычислительная сложность построения таких тестов. Главной целью настоящей статьи является развитие методов построения тестов на базе исходных шаблонов путем их расширения до требуемой разрядности на основании применения формальных правил.
Методы. Для двухмерного масштабирования исходных шаблонов с заданными пороговыми значениями расстояния Хэмминга применяются матрицы Адамара и рекурсивная процедура Сильвестра для их построения. При проведении экспериментальных исследований использовался метод статистических испытаний.
Результаты. Показано, что методы построения управляемых вероятностных тестов, основанные на использовании шаблонов, можно рассматривать как процедуру масштабирования управляемых вероятностных тестов до требуемой их разрядности. Для построения искомых тестов используются как шаблоны, характеризующиеся минимальной разрядностью наборов, так и любые управляемые вероятностные тесты. Сама процедура характеризуется как одномерное масштабирование, которое увеличивает разрядность тестовых наборов, но сохраняет их количество. С целью одновременного увеличения разрядности наборов и их количества предлагается метод, основанный на двухмерном масштабировании шаблонов с применением матриц Адамара. Это позволяет строить управляемые вероятностные тесты без трудоемкой процедуры перечисления кандидатов в тестовые наборы и вычисления для них значений меры (мер) различия. Показано, что уникальное свойство ортогональности матриц Адамара с ростом их порядка позволяет достигать отношений среднего значения расстояния Хэмминга между тестовыми наборами к их разрядности, близких к 1/2. Отмечено, что характеристики исходных шаблонов несущественно влияют на характеристики результирующих тестов, построенных с применением матриц Адамара, которые получены на основании рекурсивной процедуры Сильвестра. Работоспособность и эффективность предложенного подхода к построению управляемых вероятностных тестов оценены для случая тестирования запоминающих устройств. Показано, что управляемые вероятностные тесты, построенные с применением матриц Адамара, имеют заметно большую покрывающую способность по сравнению с вероятностными тестами.
Заключение. Рассмотрен метод генерирования тестовых наборов при формировании управляемых вероятностных тестов с использованием матриц Адамара. Основой предложенного метода является двухмерное масштабирование исходных шаблонов с применением указанных матриц. Показано, что использование различных шаблонов и их двухмерное масштабирование позволяют строить управляемые вероятностные тесты с требуемой разрядностью тестовых наборов и большим их количеством

1. 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.

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

3. Karmore, S. P. Testing of embedded system, an issues and challenges / S. P. Karmore, A. R. Mahajan // International Journal of Enhanced Research in Science, Technology & Engineering. – 2015. – Vol. 4, no. 8. – P. 181–186.

4. Krupp, A. A Systematic approach to the test of combined HW/SW systems / A. Krupp, W. Muller // Proc. of IEEE Conf. on the Testing and Automation of Embedded Systems (DATE 2010), Dresden, Germany, 8–12 Mar. 2010. – Dresden, Germany, 2010. – P. 323–326.

5. 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.

6. 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.

7. Garousi, V. Testing embedded software: A survey of the literature / V. Garousi, M. elderer, C. M. Karapıçak, U. Yılmaz // Information and Software Technology. – 2018. – Vol. 104. – P. 14–45.

8. Saini, D. K. Software testing for embedded systems / D. K. Saini // International Journal of Computer Applications. – 2012. – Vol. 43, no. 17. – P. 1–6.

9. Karmore, S. P. Universal methodology for embedded system testing / S. P. Karmore, A. R. Mahajan // Proc. of the 8th Intern. Conf. on Computer Science & Education (ICCSE 2013), Colombo, Sri Lanka, 26–28 Apr. 2013. – Colombo, 2013. – P. 567–572.

10. 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.

11. Chen, T. Y. 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.

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

13. 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.

14. Alamgir, A. Adaptive random testing with total Cartesian distance for black box circuit under test / A. Alamgir // Indonesian Journal of Electrical Engineering and Computer Science. – 2020. – Vol. 20, no. 2. – P. 720–726.

15. Wu, S. H. Antirandom testing: A distance-based approach / S. H. 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.

16. 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.

17. 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.

18. 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.

19. 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.

20. 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.

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

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

23. Ярмолик, С. В. Управляемое случайное тестирование / С. В. Ярмолик, В. Н. Ярмолик // Информатика. – 2011. − Т. 29, № 1. – С. 79–88.

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

25. Управляемые вероятностные тесты с фиксированным минимальным значением расстояния Хэмминга / В. Н. Ярмолик, В. В. Петровская, Д. В. Деменковец, В. А. Леванцевич // Информатика. – 2025. − Т. 22, № 1. – С. 7–26.

26. MacWilliams, F. J. The Theory of Error-Correcting Codes / F. J. MacWilliams, N. J. A. Sloane. – Amsterdam, The Netherland : Elsevier-North-Holland Pub. Co., 1977. – 762 p.

27. Hedayat, A. Hadamard matrices and their applications / A. Hedayat, W. D. Wallis // Annals of Statistics. – 1978. – Vol. 6, no. 6. – P. 1184–1238.

28. Seberry, J. Hadamard matrices: Constructions using number theory and linear algebra / J. Seberry, M. Yamada. – Hoboken, NJ, USA : John Wiley & Sons, Inc., 2020. – 384 p.

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

30. Ярмолик, В. Н. Многократные неразрушающие маршевые тесты с изменяемыми адресными последовательностями / В. Н. Ярмолик, С. В. Ярмолик // Автоматика и телемеханика. – 2007. – Вып. 4. – С. 126–137.

31. Cheng, K.-L. Neighborhood pattern-sensitive fault testing and diagnostics for random-access memories / K.-L. Cheng, M.-F. Tsai, C. T. Wu // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. – 2002. – Vol. 21, no. 11. – P. 284–267.

32. Parvathi, M. Novel test methods for NPSF faults in SRAM / M. Parvathi, T. Hmiasree, T. Bhavyasree // Proc. of Intern. Conf. on Computational and Characterization Techniques in Engineering & Sciences (CCTES), Lucknow, India, 14–15 Sept. 2018. – Lucknow, 2018. – P. 112–118.

33. Ярмолик, В. Н. Построение и применение маршевых тестов для обнаружения кодочувствительных неисправностей запоминающих устройств / В. Н. Ярмолик, В. А. Леванцевич, Д. В. Деменковец, И. Мрозек // Информатика. – 2021. − Т. 18, № 1. – С. 25–42.