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

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

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

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

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

1. Ledin, J. Modern Computer Architecture and Organization / J. Ledin. – Birmingham : Packt Publishing Ltd., 2020. – 536 p.

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

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

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, 08–12 Mar. 2010. – Dresden, 2010. – P. 323–326.

5. Teller-Giron, R. Random fault detection in logical networks / R. Teller-Giron, R. David // Proc. of Intern. Symp. on Discrete Systems, Riga, USSR, 30 Sept. – 4 Oct. 1974. – Riga, 1974. – P. 232–241.

6. Agrawal, V. D. When to use random testing / V. D. Agrawal // IEEE Transactions on Computers. – 1978. – Vol. C-27, no 11. – P. 1054–1055.

7. Bernet, G. A theory of probabilistic functional testing / G. Bernet, L. Bouaziz, P. LeGall // Proc. of the 1997 Intern. Conf. on Software Engineering, Boston, Massachusetts, USA, 17–23 May 1997. – Boston, 1997. – P. 216–226.

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

9. Bushnell, M. Essentials of Electronic Testing for Digital, Memory and Mixed-Signal VLSI Circuits (Frontiers in Electronic Testing) / M. Bushnell, V. Agrawal. – Dordrecht, Netherlands : Springer, 2004. – 690 p.

10. Yarmolik, V. N. Self-Testing VLSI Design / V. N. Yarmolik, I. V. Kachan. – Amsterdam : Elsevier Science Publishers, 1993. – 345 p.

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

12. Myers, G. J. The Art of Software Testing / G. J. Myers, C. Sandler, T. Badgett. – 3rd ed. – Canada : John Wiley & Sons, Inc., 2012. – 240 p.

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

14. Goor, A. J. Testing Semiconductor Memories, Theory and Practice / A. J. Goor. – Chichester, UK : John Wiley & Sons, 1991. – 536 p.

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

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

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

18. 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, art. ID 165709. – 9 p. – https://doi.org/10.1155/2008/165709.

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

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

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

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

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

24. Yarmolik, S. V. Controlled Random Tests / S. V. Yarmolik, V. N. Yarmolik // Automation and Remote Control. – 2012. – Vol. 73, no. 10. – P. 1704–1714.

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

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

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

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

29. Ярмолик, В. Н. Масштабирование управляемых вероятностных тестов с применением матриц Адамара / В. Н. Ярмолик, Н. А. Шевченко, В. В. Петровская // Информатика. – 2025. – Т. 22, № 2. – С. 63–80.

30. Метод построения управляемых вероятностных тестов / В. Н. Ярмолик, И. Мрозек, П. Ю. Бранцевич [и др.] // Доклады БГУИР. – 2025. – Т. 23, № 6. – С. 87–95.

31. Hahn, G. J. Statistical Models in Engineering / G. J. Hahn, S. S. Shapiro. – N. Y., USA : John Wiley & Sons, 1994. – 376 p.

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

33. Mrozek, I. Problemy funkcjonalnego testowania pamięci RAM / I. Mrozek, V. Yarmolik. – Bialystok, Polska : Politechnika Pialostocka, 2009. – 264 р.