Controlled random tests with limited Hamming distance

Objectives. The problem of constructing controlled random tests with a fixed minimum Hamming distance is solved. The limitations of classical approaches to generating test patterns based on enumeration of test pattern candidates are shown. With an increase in the threshold values of the difference measures of binary test patterns, the computational complexity of constructing such tests increases. The main goal of this article is to develop methods for constructing tests based on initial templates and rules for expanding them to the required bit size.

Methods. Based on the Hamming distance used in the theory and practice of forming controlled random tests, new measures of difference are considered for comparing two binary test patterns. The basis of the proposed measures of difference is the formation of a set of Hamming distances for the original patterns, represented as sequences of symbols of different alphabets.

Results. The paper demonstrates the indistinguishability of pairs of binary test patterns using a difference measure based on the Hamming distance. In this case, different pairs of patterns may have coinciding Hamming distance values. New measures of difference for binary test sequences based on their representation as sequences consisting of symbols of different alphabets are considered. As an alternative to known solutions, an approach is proposed based on increasing the number of test patterns in a test while maintaining the minimum Hamming distance between patterns at an acceptable level. The main feature of the proposed approach is the use of the difference measure proposed by the authors based on determining the Hamming distance for test patterns consisting of symbols of different alphabets. It is shown that achieving the maximum Hamming distance value for patterns represented by a large number of binary symbols ensures the same distance value for the case when the symbols are specified by a smaller number of bits. This allows one to construct controlled random tests without the procedure of listing candidates for test patterns.

Conclusion. The considered measures of difference expand the possibilities of generating test patterns when forming controlled random tests. It is shown that the use of various templates and rules applied to them allows constructing tests with a fixed minimum Hamming distance and the required bit size of test patterns.

1. Orso A., Rothermel G. Software testing: A research travelogue (2000–2014). Proceeding of Future of of ware Eng neer ng roceed ng ( O E’14), Hyderabad, Ind a, 31 ay – 7 June 2014. Hyderabad, 2014, pp. 117–132.

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

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

4. Malaiya Y. K., Yang S. The coverage problem for random testing. Proceeding of the International Test Conference, Philadelphia, PA, USA, 16–18 October 1984. Philadelphia, 1984, pp. 237–242.

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

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

7. Malaiya Y. K. Antirandom testing: getting the most out of black-box testing. Proceedings of the International Symposium on Software Reliability Engineering, Toulose, France, 24–27 October 1995. Toulose, 1995, pp. 86–95.

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

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

10. 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, article ID 165709, 9 p. DOI: 10.1155/2008/165709.

11. Von Mayrhauser A., Bai A., Chen T., Anderson C., Hajjar A. Fast antirandom (FAR) test generation. Proceedings of the Third IEEE International High-Assurance System Engineering Symposium, Washington, D.C., USA, 13–14 November 1998. Washington, 1998, pp. 262–269.

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

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

14. Kuo F. С. An indepth study of mirror adaptive random testing. Proceedings of the Ninth International Conference on Quality Software (QSIC 2009), Jeju, Korea (South), 24–25 August 2009. Jeju, 2009, pp. 51–58.

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

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

17. Nikravan E., Parsa S. Hybrid adaptive random testing. International Journal of Computing Science & Mathematics, 2020, vol. 11, no. 3, p. 209.

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

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

20. Mrozek I., Yarmolik V. Multiple controlled random testing. Fundamenta Informaticae, 2016, vol. 144, no. 1, pp. 23–43.

21. Yarmolik S. V., Yarmolik V. N. Iterative almost pseudo-exhaustive random tests. Informatika [Informatics], 2010, vol. 26, no. 2, pp. 66−75 (In Russ.).

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

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

24. Sadovskii M. G. About symbolical sequences comparigion. Vuchislitel’nue technologii [Computational Technologise], 2005, no. 3(10), pp. 106–116 (In Russ.).

25. Yarmolik V. N., Petrovskaya V. V., Shevchenko N. A. Dissimilarity measures based on the application of Hamming distance to generate controlled probabilistic tests. Informatika [Informatics], 2024, vol. 21, no. 2, pp. 54−72 (In Russ.).

26. Volchikhin V. I., Ivanov A. I., Yunin A. P., Malygina E. A. A multidimensional picture of numerical sequences of the ideal "white noise" in Hamming convolutions. Informatika, vychislitel’naya technika i upravlenie [Computer Science, Computer Engineering and Control], 2017, vol. 1, no. 4, pp. 4–12 (In Russ.).

27. Yarmolik V. N., Petrovskaya V. V., Shauchenka M. A. Distance measure for controlled random tests. Doklady BGUIR [BSUIR Proceedings], 2024, vol. 22, no. 4, pp. 76–83 (In Russ.).

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

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

30. Mrozek I., Yarmolik V. Optimal controlled random tests. Proceedings of Computer Information Systems and Industrial Management: 16th IFIP TC8 International Conference, CISIM 2017, Bialystok, Poland, 16–18 June 2017. Bialystok, 2017, pp. 27–38.

31. Sokol B., Yarmolik V. N. Memory faults detection techniques with use of degrees of freedom in march tests. Proceedings of IEEE East-West Design & Test Workshop, Odessa, Ukraine, 15–19 September 2005. Odessa, 2005, pp. 96–101.

32. Yarmolik S. V., Yarmolik V. N. Detection of code-sensitive faults in memory devices using multiple march tests. Informatika [Informatics], 2006, vol. 19, no. 1, pp. 104−113 (In Russ.).