informИнформатикаInformatics1816-03012617-6963UIIP NASB10.37661/1816-0301-2025-22-1-7-26inform-1316Research ArticleЛОГИЧЕСКОЕ ПРОЕКТИРОВАНИЕLOGICAL DESIGNУправляемые вероятностные тесты с ограниченным значением расстояния ХэммингаControlled random tests with limited Hamming distanceЯрмоликВ. Н.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ДеменковецД. В.DemenkovetsD. V.

Деменковец Денис Викторович - магистр технических наук.

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

Denis V. Demenkovets - M. Sc. (Eng.).

St. P. Brovki, 6, Minsk, 220013

Demenkovets@bsuir.byЛеванцевичВ. А.LevantsevichV. A.

Леванцевич Владимир Александрович, магистр технических наук.

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

Vladimer A. Levantsevich - M. Sc. (Eng.).

St. P. Brovki, 6, Minsk, 220013

lvn@bsuir.byБелорусский государственный университет информатики и радиоэлектроникиBelarusian State University of Informatics and Radioelectronics202531032024221726Copyright © Ярмолик В.Н., Петровская В.В., Деменковец Д.В., Леванцевич В.А., 20252025Ярмолик В.Н., Петровская В.В., Деменковец Д.В., Леванцевич В.А.Yarmolik V.N., Petrovskaya V.V., Demenkovets D.V., Levantsevich V.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/1316Цели

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

Методы

Методы. На базе расстояния Хэмминга, используемого в теории и практике формирования управляемых вероятностных тестов, рассматриваются новые меры различия для сравнения двух двоичных тестовых наборов. Основой предлагаемых мер различия является формирование множества расстояний Хэмминга для исходных наборов, представляемых в виде последовательностей символов различных алфавитов.

Результаты

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

Заключение

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

Objectives

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

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

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

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.

тестовое диагностированиеуправляемые вероятностные тестыдвоичный тестовый набормера различия символьных набороврасстояние Хэммингакодочувствительные неисправностиtest diagnosticscontrolled random testsbinary test patternscharacter patterns difference measureHamming distancepattern-sensitive faultsReferencesOrso, A. Software testing: A research travelogue (2000–2014) / A. Orso, G. Rothermel // Proc. of Future of Software Engineering Proceeding (FOSE’14), Hyderabad, India, 31 May – 7 June 2014. – Hyderabad, 2014. – P. 117–132.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.An orchestrated survey on automated software test case generation / S. Anand, E. Burke, T. Chen [et al.] // Journal 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.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.Malaiya, Y. K. The coverage problem for random testing / Y. K. Malaiya, S. Yang // Proc. of the Intern. Test Conf., Philadelphia, PA, USA, 16–18 Oct. 1984. – Philadelphia, 1984. – P. 237–242.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.Duran, 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.Ярмолик, В. Н. Контроль и диагностика вычислительных систем / В. Н. Ярмолик. – Минск : Бест-принт, 2019. – 387 с.Yarmolik V. N. Control’ i diagnostika vuchislitel’nuch system. Computer Systems Testing and Diagnoses. Minsk, Bestprint, 2019, 387 p. (In Russ.).Malaiya, Y. K. Antirandom testing: getting the most out of black-box testing / Y. K. Malaiya // Proc. of the Intern. Symp. on Software Reliability Engineering, Toulose, France, 24–27 Oct. 1995. – Toulose, 1995. – P. 86–95.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.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.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.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.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.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, article ID 165709. – 9 p. – DOI: 10.1155/2008/165709.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.Fast antirandom (FAR) test generation / A. von Mayrhauser, A. Bai, T. Chen [et al.] // Proc. of the Third IEEE Intern. High-Assurance System Engineering Symp., Washington, D.C., USA, 13–14 Nov. 1998. – Washington, 1998. – P. 262–269.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.Xu, S. Orderly random testing for both hardware and software / S. Xu // Proc. of the 2008 14th IEEE Pacific Rim Intern. Symp. on Dependable Computing, Washington, D.C., USA, 15–17 Dec. 2008. – Washington, 2008. – P. 160–167.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.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.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.Kuo, F. C. An indepth study of mirror adaptive random testing / F. C. Kuo // Proc. of the Ninth Intern. Conf. on Quality Software (QSIC 2009), Jeju, Korea (South), 24–25 Aug. 2009. – Jeju, 2009. – P. 51–58.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.Tappenden, A. A novel evolutionary approach for adaptive random testing / A. Tappenden, J. Miller // IEEE Transactions on Reliability. – 2009. – Vol. 58, no. 4. – P. 619–633.Tappenden A., Miller J. A novel evolutionary approach for adaptive random testing. IEEE Transactions on Reliability, 2009, vol. 58, no. 4, pp. 619–633.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.Nikravan, E. Hybrid adaptive random testing / E. Nikravan, S. Parsa // International Journal of Computing Science & Mathematics. – 2020. – Vol. 11, no. 3. – P. 209.Nikravan E., Parsa S. Hybrid adaptive random testing. International Journal of Computing Science & Mathematics, 2020, vol. 11, no. 3, p. 209.Yarmolik, S. V. Controlled random tests / S. V. Yarmolik, V. N. Yarmolik // Automation and Remote Control. – 2012. – Vol. 73, no. 10. – P. 1704–1714.Yarmolik S. V., Yarmolik V. N. Controlled random tests. Automation and Remote Control, 2012, vol. 73, no. 10, pp. 1704–1714.Mrozek, I. Antirandom test vectors for BIST in hardware/software systems / I. Mrozek, V. N. Yarmolik // Fundamenta Informaticae. – 2012. – Vol. 119, no. 2. – P. 163–185.Mrozek I., Yarmolik V. Antirandom test vectors for BIST in hardware/software systems. Fundamenta Informaticae, 2012, vol. 119, no. 2, pp. 163–185.Mrozek, I. Multiple controlled random testing / I. Mrozek, V. N. Yarmolik // Fundamenta Informaticae. – 2016. – Vol. 144, no. 1. – P. 23–43.Mrozek I., Yarmolik V. Multiple controlled random testing. Fundamenta Informaticae, 2016, vol. 144, no. 1, pp. 23–43.Ярмолик, С. В. Итеративные почти псевдоисчерпывающие вероятностные тесты / С. В. Ярмолик, В. Н. Ярмолик // Информатика. – 2010. – № 2(26). – С. 66–75.Yarmolik S. V., Yarmolik V. N. Iterative almost pseudo-exhaustive random tests. Informatika [Informatics], 2010, vol. 26, no. 2, pp. 66−75 (In Russ.).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.Hamming R. W. Error detecting and error correcting codes. The Bell System Technical Journal, 1950, vol. 29, no. 2, pp. 147–160.Peterson, W. W. Error-Correction Codes / W. W. Peterson, E. J. Weldon. – Cambridge, Massachusetts, London, England : The MIT Press, 1972. – 560 p.Peterson W. W., Weldon E. J. Error-Correction Codes. Cambridge, Massachusetts, London, England, The MIT Press, 1972, 560 p.Садовский, М. Г. О сравнении символьных последовательностей / М. Г. Садовский // Вычислительные технологии. – 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.).Ярмолик, В. Н. Модификации способов определения расстояния Хэмминга для их применения в качестве мер различия при генерировании управляемых вероятностных тестов / В. Н. Ярмолик, В. В. Петровская, Н. А. Шевченко // Информатика. – 2024. − Т. 21, № 2. – С. 54–72.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.).Многомерный портрет цифровых последовательностей идеального «белого шума» в свертках Хэмминга / В. И. Волчихин, А. И. Иванов, А. П. Юнин, Е. А. Малыгина // Информатика, вычислительная техника и управление. – 2017. – № 4(1). – С. 4–12.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.).Ярмолик, В. Н. Мера различия для управляемых вероятностных тестов / В. Н. Ярмолик, В. В. Петровская, Н. А. Шевченко // Доклады БГУИР. – 2024. – № 4(22). – С. 76–83.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.).Plotkin, M. Binary codes with specified minimum distance / M. Plotkin // IRE Transactions on Information Theory. – 1960. – Vol. 6, no. 4. – P. 445–450.Plotkin M. Binary codes with specified minimum distance. IRE Transactions on Information Theory, 1960, vol. 6, no. 4, pp. 445–450.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.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.Mrozek, I. Optimal controlled random tests / I. Mrozek, V. Yarmolik // Proc. of Computer Information Systems and Industrial Management: 16th IFIP TC8 Intern. Conf., CISIM 2017, Bialystok, Poland, 16–18 June 2017. – Bialystok, 2017. – P. 27–38.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.Sokol, B. Memory faults detection techniques with use of degrees of freedom in march tests / B. Sokol, V. N. Yarmolik // Proc. of IEEE East-West Design & Test Workshop (EWDTW’05), Odessa, Ukraine, 15–19 Sept. 2005. – Odessa, 2005. – P. 96–101.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.Ярмолик, С. В. Обнаружение кодочувствительных неисправностей запоминающих устройств с многократным использованием маршевых тестов / С. В. Ярмолик, В. Н. Ярмолик // Информатика. – 2006. − Т. 19, № 1. – С. 104–113.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.).

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