An iterative method for two-dimensional scaling of controlled random tests

Objectives. To study the limitations of classical approaches to generating test patterns for controlled random tests based on enumerating test set candidates through their one-dimensional scaling. To address the problem of constructing controlled random tests using an iterative method for two-dimensional scaling of initial templates. The main goal of the article is to develop a method for constructing tests based on initial templates and expanding them to the required bit size and number of test patterns using an iterative procedure.

Methods. For two-dimensional scaling of initial templates with given characteristics, scaling matrices are used, which, like templates, can also be controlled random tests. Statistical testing method was used during the experimental research.

Results. It is shown that methods for constructing controlled random tests based on the use of templates can be considered as a procedure for scaling controlled random tests to the required bit size. To construct the desired tests, both templates characterized by a minimum test suite capacity and any controllable random tests are used. This procedure allows increasing the test suite capacity while maintaining the number of their patterns. A simultaneous increase in the suite capacity and their number is achieved using the proposed approach, which is based on iterative two-dimensional scaling of templates using scaling matrices. In this case, the resulting controllable random tests are generated without the labor-intensive procedure of listing candidate test suites and calculating the difference measure(s) for them. The dependences of the main characteristics of the resulting controllable random test on the characteristics of the template and the scaling matrix are presented, which, like a template, can also represent a controllable random test. A statement is proved that determines the dependence of the characteristics of the test generated at the k-th iteration on the values of the characteristics of the test obtained at the (k–1)-th iteration and the scaling test. Useful consequences and properties of tests constructed based on the proposed procedure are presented. The performance and effectiveness of an iterative method for constructing controlled random tests are demonstrated and evaluated for binary test sets. It is shown that controlled random tests constructed using the discussed procedure have significantly larger Hamming distances compared to random tests.

Conclusion. An iterative method for constructing controlled random tests through two-dimensional scaling is considered. The basis of the proposed method is the use of initial templates and scaling matrices, which represent controlled random tests with a small number of test sets and a small bit size. It is shown that the use of various templates and their two-dimensional scaling allows for the construction of controlled random tests with the required bit size and a large number of test patterns.

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

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

3. Yarmolik V. N. Control’ i diagnostika vuchislitel’nuch system. Computer Systems Testing and Diagnoses. Minsk, Bestprint, 2019, 387 p. (In Russ.).

4. Krupp A., Muller W. A systematic approach to the test of combined HW/SW systems. Proceedings of the IEEE Conference on the Testing and Automation of Embedded Systems (DATE 2010), Dresden, Germany, 08–12 March 2010. Dresden, 2010, pp. 323–326.

5. Teller-Giron R., David R. Random fault detection in logical networks. Proceedings of the International Symposium on Discrete Systems, Riga, USSR, 30 September – 4 October 1974. Riga, 1974, pp. 232–241.

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

7. Bernet G., Bouaziz L., LeGall P. A theory of probabilistic functional testing. Proceedings of the 1997 International Conference on Software Engineering, Boston, Massachusetts, USA, 17–23 May 1997. Boston, 1997, pp. 216–226.

8. Arcuri A., Iqbal Z., Briand L. Random testing: Theoretical results and practical implications. IEEE Transactions on Software Engineering, 2011, vol. 38, no. 2, pp. 258–277.

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

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

11. Anand S., Burke E. K., Chen T. Y., Clark J., Cohen M. B., …, Zhu H. An orchestrated survey on automate software test case generation. Journal of Systems and Software, 2014, vol. C-39, no. 4, pp. 582–586.

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

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

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

15. Huang R., Sun W., Xu Y., Chen H., Towey D., Xia X. A survey on adaptive random testing. IEEE Transactions on Software Engineering, 2021, vol. 47, no. 10, pp. 2052–2083.

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

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

18. Wu S. H., Jandhyala S., Malaiya Y. K., Jayasumana A. P. Antirandom testing: A distance-based approach. Hindawi Publishing Corporation VLSI Design, 2008, vol. 2008, art. ID 165709, 9 p. https://doi.org/10.1155/2008/165709.

19. Xu S., Chen J. Maximum distance testing. Proceedings of the 11th Asian Test Symposium (ATS’02), Guam, USA, 18–20 November 2002. Guam, 2002, pp. 15–20.

20. Xu S. Orderly random testing for both hardware and software. Proceedings of the 2008 14th IEEE Pacific Rim International Symposium on Dependable Computing, Washington, DC, USA, 15–17 December 2008. Washington, 2008, pp. 160–167.

21. Mrozek I., Yarmolik V. N. Multiple Controlled Random Testing. Fundamenta Informaticae, 2016, vol. 144, no. 1, pp. 23–43.

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

23. Yarmolik S. V., Yarmolik V. N. Controlled random testing. Informatika [Informatics], 2011, no. 1(29), pp. 79−88 (In Russ.).

24. Yarmolik S. V., Yarmolik V. N. Controlled random tests. Automation and Remote Control, 2012, vol. 73, no. 10, pp. 1704–1714.

25. Hamming R. W. Error detecting and error correcting codes. The Bell System Technical Journal, 1950, vol. 29, no. 2, pp. 147–160.

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

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

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

29. Yarmolik V. N., Shauchenka M. A., Petrovskaya V. V. Scaling controlled random tests based on Hadamard matrices. Informatika [Informatics], 2025, vol. 22, no. 2, pp. 63–80 (In Russ.).

30. Yarmolik V. N., Mrozek I., Brancevich P. Yu., Demenkovets D. V., Levantsevich V. A. Method of controlled random tests generation. Doklady BGUIR [BSUIR Proceedings], 2025, vol. 23, no. 6, pp. 87–95 (In Russ.).

31. Hahn G. J., Shapiro S. S. Statistical Models in Engineering. New York, USA, John Wiley & Sons, 1994, 376 p.

32. Yarmolik V. N., Yarmolik S. V. Multiple non-destructive marching tests with variable address sequences. Automation and Remote Control, 2007, vol. 4, pp. 126–137.

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