Dissimilarity measures based on the application of Hamming distance to generate controlled probabilistic tests

Objectives. The problem of constructing dissimilarity measures based on the application of the Hamming distance to generate controlled random binary test sets is solved. The main goal of this article is to develop methods for determining the Hamming distance for the achievability of finding the difference between test sets when they coincide according to estimates of other difference measures.
Methods. Based on the Hamming distance used in the theory and practice of generating controlled random tests, new dissimilarity measures are proposed for two binary test n-bit patterns. The basis of the proposed dissimilarity measures is the formation of sets of Hamming distances for initial sets, represented as sequences of characters from different alphabets.
Results. The indistinguishability of pairs of binary test sets Ti and Tk is shown using a dissimilarity measure based on the application of the Hamming distance. In this case, different pairs of sets may have identical Hamming distance values. To construct new measures of difference, the original binary test sequences are represented as sequences consisting of characters belonging to different alphabets. Various strategies are proposed for applying new measures of difference based on the use of one of three rules in generating controlled probability tests. It is shown that in all three cases of dissimilarity measures, only the first few of their components areinformative, as a rule, no more than two or three. Accordingly, the computational complexity for all three options is comparable and does not exceed 3n comparison operations. The experimental studies carried out confirm the effectiveness of the proposed dissimilarity measures and their low computational complexity.
Conclusion. The proposed dissimilarity measures expand the possibilities of generating test sets when forming controlled random tests. It is shown that test sets that are indistinguishable when using the Hamming distance as a dissimilarity measure have different values of the proposed dissimilarity measures, which makes it possible to more accurately classify randomly generated sets that are candidate test cases

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

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

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

4. Wu H., Nie C., Petke J., Jia Y., Harman M. An empirical comparison of combinatorial testing, random testing and adaptive random testing. IEEE Transactions on Software Engineering, 2020, vol. 46, no. 3, pp. 302–320.

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

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

7. Roslina M. S., Ghani A. A. A., Baharom S., Zulzazil H. A preliminary study of adaptive random testing techniques. International Journal of Information Technology & Computer Science, 2015, vol. 19, no. 1, pp. 116–127.

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

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

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

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

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

13. Levenshtein V. I. Binary codes with correction of deletions, insertions and substitutions of characters. Doklady Akademii nauk SSSR [Proceedings of the USSR Academy of Sciences], 1965, vol. 163, no. 4, pp. 845–848 (In Russ.).

14. Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. Introduction to Algorithm, 3rd edition. MIT Press, 2009, 1292 p.

15. Tannga M. J., Rahman S., Hasniati. Comparative analysis of Levenshnein distance algorithm and Jaro Winkler for text plagiarism detection application. Journal of Technology Research in Information System and Engineering, 2017, vol. 4, no. 2, pp. 44–54.

16. Needleman S., Wunsch C. A general method applicable to the search for similarities in the amino acid sequence of two proteins. Journal of Molecular Biology, 1970, vol. 48, no. 3, pp. 443–453.

17. Smith T. F., Waterman S. Identification of common molecular subsequences. Journal of Molecular Biology, 1981, vol. 147, pp. 195–197.

18. Huang R., Chen H., Sun W., Towey D. Candidate test set reduction for adaptive random testing: An overheads reduction technique. Journal of Molecular Biology, 2021, vol. 214, no. C, р. 102730.

19. Yarmolik V. N., Petrovskaya V. V., Mrozek I. Distance measure for controlled random tests. Informatika [Informatics], 2022, vol. 19, no. 4, pp. 7–26 (In Russ.).

20. Yarmolik V. N., Shauchenka M. A., Petrovskaya V. V. Distance measure for controlled random tests. Doklady Belorusskogo gosudarstvennogo universiteta informatiki i radioèlektroniki [Doklady BGUIR], 2022, vol. 20, no. 6, pp. 52–60 (In Russ.).

21. Yarmolik V. N., Mrozek I., Levantsevich V. A., Demenkovets D. V. Transparent memory tests with even repeating addresses for storage devices. Informatika [Informatics], 2021, vol. 18, no. 3, pp. 18–35 (In Russ.).

22. 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. Izvestija vysshih uchebnyh zavedenij. Povolzhskij region. Tehnicheskie nauki [University Proceedings. Volga Region. Engineering Sciences], 2017, no. 4(44), pp. 4–13 (In Russ.).

23. Volchikhin V. I., Ivanov A. I., Karpov A. P., Yunin A. P. Conditions for the correct calculation of the entropy of meaningful long passwords in the Hamming convolution space with reference texts in Russian and English. Izmerenie. Monitoring. Upravlenie. Kontrol' [Measuring. Monitoring. Management. Control], 2019, no. 3(29), pp. 33–38 (In Russ.).