informИнформатикаInformatics1816-03012617-6963UIIP NASB10.37661/1816-0301-2024-21-2-54-72inform-1283Research ArticleЛОГИЧЕСКОЕ ПРОЕКТИРОВАНИЕLOGICAL DESIGNМеры различия, основанные на применении расстояния Хэмминга, для генерирования управляемых вероятностных тестовDissimilarity measures based on the application of Hamming distance to generate controlled probabilistic testsЯрмоликВ. Н.YarmolikV. N.

Ярмолик Вячеслав Николаевич, доктор техническихнаук, профессор

ул. П. Бровки, 6, Минск, 220013

Vyacheslav N. Yarmolik, D. Sc. (Eng.), Prof.

st. P. Brovki, 6, Minsk, 220013

yarmolik10ru@yahoo.comПетровскаяВ. В.PetrovskayaV. V.

Петровская Вита Владленовна, магистр технических наук

ул. П. Бровки, 6, Минск, 220013

Vita V. Petrovskaya, M. Sc. (Eng.)

st. P. Brovki, 6, Minsk, 220013

vita.petrovskaya@gmail.comШевченкоН. А.ShevchenkoN. A.

Шевченко Николай Алексеевич, студент

Каролиненплац, 5, Дармштадт, 64289

Nikolai А. Shevchenko, Student

Karolinenplatz, 5, Darmstadt, 64289

nik.sh.de@gmail.comБелорусский государственный университет информатики и радиоэлектроникиBelarusian State University of Informatics and RadioelectronicsДармштадтский технический университетTechnical University of Darmstadt2024280620242125472Copyright © Ярмолик В.Н., Петровская В.В., Шевченко Н.А., 20242024Ярмолик В.Н., Петровская В.В., Шевченко Н.А.Yarmolik V.N., Petrovskaya V.V., Shevchenko N.A.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://inf.grid.by/jour/article/view/1283

Цели. Решается задача построения мер различия, основанных на применении расстояния Хэмминга, для генерирования управляемых вероятностных двоичных тестовых наборов. Целью настоящей статьи является развитие методов определения расстояния Хэмминга для нахождения различия между тестовыми наборами при их совпадении по оценкам других мер различия.Методы. На базе расстояния Хэмминга, используемого в теории и практике формирования управляемых вероятностных тестов, предлагаются новые меры различия для сравнения двух двоичных n-разрядных тестовых наборов. Основой предлагаемых мер различия является формирование множества расстояний Хэмминга для исходных наборов, представляемых в виде последовательностей символов различных алфавитов.Результаты. Показывается неразличимость пар двоичных тестовых наборов при использовании меры различия, основанной на применении расстояния Хэмминга. В этом случае отличающиеся пары наборов могут иметь совпадающие значения расстояния Хэмминга. Для построения новых мер различия исходные двоичные тестовые наборы представляются в виде последовательностей, состоящих из символов, принадлежащих различным алфавитам. Предлагаются различные стратегии применения новых мер различия, основанных на использовании одного из трех правил, при генерировании управляемых вероятностных тестов. Показано, что во всех трех случаях новых мер различия информативными являются только несколько первых их компонент, как правило, не более двух или трех. Соответственно, вычислительная сложность для всех трех вариантов сравнима и не превышает 3n операций сравнения. Проведенные экспериментальные исследования подтверждают эффективность предложенных мер различия и их невысокую вычислительную сложность.Заключение. Предложенные меры различия расширяют возможности генерирования тестовых наборов при формировании управляемых вероятностных тестов. Показывается, что тестовые наборы, неразличимые при использовании в качестве меры различия расстояния Хэмминга, имеют отличающиеся значения предложенных мер различия. Это позволяет более точно классифицировать формируемые случайным образом наборы, которые являются кандидатами в тестовые наборы.

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

тестирование вычислительных системуправляемые вероятностные тестыдвоичный тестовый набормера различия символьных набороврасстояние Хэммингаcomputer systems testincontrolled random testsbinary test patternscharacter patterns difference measureHamming distanceReferencesDuran, J. W. An evaluation of random testing / J. W. Duran, S. C. Ntafos // IEEE Transactions on Software Engineering. – 1984. – Vol. SE-10, no. 4. – P. 438–444.Duran J. W., Ntafos S. C. An evaluation of random testing. IEEE Transactions on Software Engineering, 1984, vol. SE-10, no. 4, рр. 438–444.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.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.An orchestrated survey on automated software test case generation / S. Anand [et al.] // J. of Systems and Software. – 2014. – Vol. C-39, no. 4. – P. 582–586.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.An empirical comparison of combinatorial testing, random testing and adaptive random testing / H. Wu [et al.] // IEEE Transactions on Software Engineering. – 2020. – Vol. 46, no. 3. – P. 302–320.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.Ярмолик, В. Н. Контроль и диагностика вычислительных систем / В. Н. Ярмолик. – Минск : Бестпринт, 2019. – 387 с.Yarmolik V. N. Control’ i diagnostika vuchislitel’nuch system. Computer Systems Testing and Diagnoses. Minsk, Bestprint, 2019, 387 p. (In Russ.).A survey on adaptive random testing / R. Huang [et al.] // IEEE Transactions on Software Engineering. – 2021. – Vol. 47, no. 10. – P. 2052–2083.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.A preliminary study of adaptive random testing techniques / M. S. Roslina [et al.] // Intern. J. of Information Technology & Computer Science. – 2015. – Vol. 19, no. 1. – P. 116–127.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.Ярмолик, С. В. Управляемое случайное тестирование / С. В. Ярмолик, В. Н. Ярмолик // Информатика. – 2011. – № 1(29). – С. 79–88.Yarmolik S. V., Yarmolik V. N. Controlled random testing. Informatika [Informatics], 2011, no. 1(29), pp. 79–88 (In Russ.).Nikravan, E. Hybrid adaptive random testing / E. Nikravan, S. Parsa // Intern. J. of Computing Science & Mathematics. – 2020. – Vol. 11, no. 3. – P. 209.Nikravan E., Parsa S. Hybrid adaptive random testing. International Journal of Computing Science and Mathematics, 2020, vol. 11, no. 3, p. 209.Zhibo, Li. An enhanced adaptive random testing by dividing dimensions independently / Li. Zhibo, Li. Qingbao, Yu Lei // Mathematical Problems in Engineering. – 2019. – Vol. 2019. – P. 1–15.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.Садовский, М. Г. О сравнении символьных последовательностей / М. Г. Садовский // Вычислительные технологии. – 2005. – № 3(10). – С. 106–116.Sadovskii M. G. About symbolical sequences comparigion. Vuchislitel’nue technologii [Computational Technologise], 2005, no. 3(10), pp. 106–116 (In Russ.).Hamming, R. W. Error detecting and error correcting codes / R. W. Hamming // The Bell System Technical J. – 1950. – Vol. 29, no. 2. – P. 147–160.Hamming R. W. Error detecting and error correcting codes. The Bell System Technical Journal, 1950, vol. 29, no. 2, pp. 147–160.Левенштейн, В. И. Двоичные коды с исправлением выпадений, вставок и замещений символов / В. И. Левенштейн // Доклады Академии наук СССР. – 1965. – Т. 163, № 4. – С. 845–848.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.).Алгоритмы: построение и анализ : пер. с англ. / Т. Кормен [и др.]. – 3-е изд. – М. : Изд. дом «Вильямс», 2013. – 1328 с.Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. Introduction to Algorithm, 3rd edition. MIT Press, 2009, 1292 p.Tannga, M. J. Comparative analysis of Levenshnein distance algorithm and Jaro Winkler for text plagiarism detection application / M. J. Tannga, S. Rahman, Hasniati // J. of Technology Research in Information System and Engineering. – 2017. – Vol. 4, no. 2. – P. 44–54.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.Needleman, S. A general method applicable to the search for similarities in the amino acid sequence of two proteins / S. Needleman, C. Wunsch // J. of Molecular Biology. – 1970. – Vol. 48, no. 3. – P. 443–453.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.Smith, T. F. Identification of common molecular subsequences / T. F. Smith, M. S. Waterman // J. of Molecular Biology. – 1981. – Vol. 147. – P. 195–197.Smith T. F., Waterman S. Identification of common molecular subsequences. Journal of Molecular Biology, 1981, vol. 147, pp. 195–197.Candidate test set reduction for adaptive random testing: An overheads reduction technique / R. Huang [et al.] // J. of Molecular Biology. – 2021. – Vol. 214, no. C. – Р. 102730.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.Ярмолик, В. Н. Мера различия для тестовых наборов при генерировании управляемых вероятностных тестов / В. Н. Ярмолик, В. В. Петровская, И. Мрозек // Информатика. – 2022. – Т. 19, № 4. – С. 7–26.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.).Ярмолик, В. Н. Мера различия для управляемых вероятностных тестов / В. Н. Ярмолик, Н. А. Шевченко, В. В. Петровская // Доклады БГУИР. – 2022. – Т. 20, № 6. – С. 52–60.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.).Неразрушающие тесты с четным повторением адресов для запоминающих устройств / В. Н. Ярмолик [и др.] // Информатика. – 2021. – Т. 18, № 3. – С. 18–35.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.).Многомерный портрет цифровых последовательностей идеального «белого шума» в свертках Хэмминга / В. И. Волчихин [и др.] // Известия высших учебных заведений. Поволжский регион. Технические науки. – 2017. – № 4(44). – С. 4–13.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.).Условия корректного вычисления энтропии осмысленных длинных паролей в пространстве сверток Хэмминга с эталонными текстами на русском и английском языках / В. И. Волчихин [и др.] // Измерение. Мониторинг. Управление. Контроль. – 2019. – № 3(29). – С. 33–38.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.).

The authors declare that there are no conflicts of interest present.