informИнформатикаInformatics1816-03012617-6963UIIP NASB10.37661/1816-0301-2022-19-4-7-26inform-1236Research ArticleЛОГИЧЕСКОЕ ПРОЕКТИРОВАНИЕLOGICAL DESIGNМера различия для тестовых наборов при генерировании управляемых вероятностных тестовA measure of the difference between test sets for generating controlled random testsЯрмоликВ. Н.YarmolikV. N.

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

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

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

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МрозекИ.MrozekI.

Мрозек Иренеуш, доктор, адъюнкт

ул. Вейска, 45A, 15-351, Белосток

Ireneusz Mrozek, D. Sc., Lecture

Wiejska, 45A, 15-351, Białystok

i.mrozek@pb.edu.plБелорусский государственный университет информатики и радиоэлектроникиBelarusian State University of Informatics and RadioelectronicsБелостоцкий технический университетBialystok University of Technology202206012023194726Copyright © Ярмолик В.Н., Петровская В.В., Мрозек И., 20222022Ярмолик В.Н., Петровская В.В., Мрозек И.Yarmolik V.N., Petrovskaya V.V., Mrozek I.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://inf.grid.by/jour/article/view/1236

Цели. Решается задача построения характеристик различия тестовых наборов, представляющих собой наборы символов, включая двоичные наборы. Обосновывается ее актуальность для генерирования управляемых вероятностных тестов и сложность нахождения мер различия для символьных тестов. Показывается ограниченность применения расстояния Хэмминга и Дамерау – Левенштейна для получения меры различия тестовых наборов.Методы. На основе характеристики интервала, применяемого в теории строя цепи последовательных событий, определяется новая мера различия двух символьных тестовых наборов. В качестве меры различия рассчитывается расстояние AD(Ti, Tk) между тестовыми наборами Ti и Tk, использующее характеристику интервала и основанное на определении независимых пар одинаковых (тождественных) символов, принадлежащих двум наборам, и вычислении интервалов между ними.Результаты . Показывается комбинаторный характер вычисления предложенной меры различия для символьных тестовых наборов произвольного алфавита и размерности. Приводится пример вычисления данной меры для различных видов тестовых наборов, в том числе таких, как адресные тестовые наборы. Показываются возможные ее модификации и определяются некоторые свойства и ограничения. Рассматривается применение данной меры различия для случая многократного тестирования запоминающих устройств на основе адресных последовательностей pA с четным p повторением адресов. Для случая p = 2 приводятся математические соотношения вычисления интервалов и расстояния AD(Ti, Tk) для последовательностей адресов 2A, используемых для управляемого вероятностного тестирования запоминающих устройств. Основное внимание уделяется двоичным тестовым наборам, для которых задача вычисления данной метрики различия сводится к классической задаче о назначениях с использованием венгерского алгоритма. Вычислительная сложность венгерского алгоритма оценивается соотношением O(n4). Как альтернатива венгерскому алгоритму предлагается алгоритм вычисления рассматриваемой меры, сложность которого существенно меньше и имеет оценку O(n2). Проведенные экспериментальные исследования подтверждают эффективность рассмотренного алгоритма.Заключение. Предложенная мера различия расширяет возможности генерирования тестовых последовательностей при генерировании управляемых вероятностных тестов. Показано, что тестовые наборы, неразличимые при использовании в качестве меры различия расстояния Хэмминга, имеют различные значения AD(Ti, Tk), позволяющие более точно классифицировать формируемые случайным образом наборы, которые являются кандидатами в тестовые наборы.

Objectives . The problem of constructing the characteristics of the difference between test sequences is solved. Its relevance for generating controlled random tests and the complexity of finding measures of difference for symbolic tests are substantiated. The limitations of using the Hamming and Damerau – Levenshtein distances to obtain a measure of the difference between test sets are shown.Methods . Based on the characteristic of the interval used in the theory of the chain of successive events, a new measure of the difference between two symbolic test sets is determined. As a difference measure, the distance AD(Ti, Tk) between the test sets Ti and Tk is calculated using the interval characteristic, which is based on determining independent pairs of same (identical) symbols belonging to two sets and calculating the intervals between them.Results. The combinatorial nature of the calculation of the proposed difference measure for symbolic test sets of an arbitrary alphabet and dimension is shown. An example of calculating this measure for various types of test sets, including such as address test sets, is given. Possible modifications are shown and some properties and limitations are determined. The application of the measure of difference is considered for the case of repeated testing of storage devices based on address sequences pA with even p repetition of addresses. For the case p = 2, mathematical relations are given for calculating the intervals and distances AD(Ti, Tk) for address sequences 2A used for controlled random testing of storage devices. The main attention is paid to binary test sets, when the task of calculating given difference metric is reduced to the classical assignment problem using the Hungarian algorithm. The computational complexity of the Hungarian algorithm is estimated by the relation O(n4). As an alternative to the Hungarian algorithm, an algorithm for calculating the considered difference measure is proposed, the complexity of which is much less and has an estimate equal to O(n2). The experimental studies confirm the effectiveness of the proposed algorithm.Conclusion. The proposed difference measure extends the possibilities of generating test sequences when generating controlled random tests. It is shown that test sets, which are indistinguishable when Hamming distance is used as a measure of difference, have different values of AD(Ti, Tk) that allows to make more accurate classification of randomly generated sets as candidates for test sets.

управляемые вероятностные тестымера различия символьных наборовадресные последовательностизадача о назначенияхвенгерский алгоритмcontrolled random testscharacter set difference measureaddress sequencesassignment problemHungarian algorithmАвторы выражают искреннюю благодарность старшему преподавателю кафедры программного обеспечения информационных технологий БГУИР Н. С. Петюкевич за участие в обсуждении результатов статьи, советы и рекомендации.The authors express their sincere gratitude to N. S. Petyukevich, Senior Lecturer of the Department of Information Technology Software at BSUIR, for participating in the discussion of the results of the article, advice and recommendations.ReferencesAn 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 automated software test case generation. Journal of Systems and Software, 2014, vol. C-39, no 4, pp. 582–586.Malaiya, Y. K. The coverage problem for random testing / Y. K. Malaiya, S. Yang // Proc. of ITC, Philadelphia, PA, USA, Oct. 1984. – Philadelphia, 1984. – P. 237–242.Malaiya Y. K., Yang S. The coverage problem for random testing. Proceedings of the International Test Conference, Philadelphia, PA, USA, October 1984. Philadelphia, 1984, pp. 237–242.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.Using the information: Incorporating positive feedback information into the testing process / K. P. Chan [et al.] // Proc. of the 7th Annual Intern. Workshop on Software Technology and Engineering Practice (STEP’03), Amsterdam, Netherlands, 19–21 Sept. 2003. – Amsterdam, 2003. – P. 71–76.Chan K. P., Towey D., Chen T. Y., Kuo F.-C., Merkel R. G. Using the information: Incorporating positive feedback information into the testing process. Proceedings of the 7th Annual International Workshop on Software Technology and Engineering Practice (STEP’03), Amsterdam, Netherlands, 19–21 September 2003. Amsterdam, 2003, pp. 71–76.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.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.).Ярмолик, В. Н. Многократные управляемые вероятностные тесты / В. Н. Ярмолик, В. А. Леванцевич, И. Мрозек // Информатика. – 2015. – № 2(46). – С. 63–76.Yarmolik V. N., Levantsevich В. А., Mrozek I. Multiple controlled random tests. Informatika [Informatics], 2015, no. 2, pp. 63–76 (In Russ.).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. N. Multiple controlled random testing. Fundamenta Informaticae, 2016, vol. 144, no. 1, pp. 23–43.Садовский, М. Г. О сравнении символьных последовательностей / М. Г. Садовский // Вычислительные технологии. – 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.).Ярмолик, В. Н. Мера различия для управляемых вероятностных тестов / В. Н. Ярмолик, Н. А. Шевченко, В. В. Петровская // Доклады БГУИР. – 2022. – № 6(20). – С. 52–60.Yarmolik V. N., Shauchenka M. A., Petrovskaya V. V. Distance measure for controlled random tests. Doklady BGUIR [BSUIR Proceedings], 2022, no. 6(20), pp. 52–60 (In Russ.).A modified similarity metric for unit testing of object-oriented software based on adaptive random testing / J. Chen [et al.] // Intern. J. of Software Engineering and Knowledge Engineering. – 2019. – Vol. 29, no. 4. – P. 577–606.Chen J., Kudjo P. K., Zhang Z., Su C., Guo Y., …, Song H. A modified similarity metric for unit testing of object-oriented software based on adaptive random testing. International Journal of Software Engineering and Knowledge Engineering, 2019, vol. 29, no. 4, pp. 577–606.Chen, T, Y. Adaptive random testing based on distribution metrics / T. Y. Chen, F-C. Kuo, H. Liu // J. of Systems and Software. – 2009. – Vol. 82, no. 9. – P. 1419–1433.Chen T. Y., Kuo F.-C., Liu H. Adaptive random testing based on distribution metrics. Journal of Systems and Software, 2009, vol. 82, no. 9, pp. 1419–1433.Bard, G. V. Spelling-error tolerant, order-independent pass-phrases via the Damerau – Levenshtein string-edit distance metric / G. V. Bard // Proc. of the Fifth Australasian Symp. on ACSW Frontiers, Ballarat, Australia, 30 Jan. – 2 Feb. 2007. – Ballarat, 2007. – P. 117–124.Bard G. V. Spelling-error tolerant, order-independent pass-phrases via the Damerau – Levenshtein stringedit distance metric. Proceedings of the Fifth Australasian Symposium on ACSW Frontiers, Ballarat, Australia, 30 January – 2 February 2007. Ballarat, 2007, pp. 117–124.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.О мерах сходства расположения компонентов в массивах естественно упорядоченных данных / А. С. Гуменюк [и др.] // Тр. СПИИРАН. – 2019. – Vol. 18, no. 2. – P. 471–503.Gumenyuk A. S., Skiba A. A., Pozdnichenko N. N., Shpynov S. N. About similarity measures of components of naturaly ordered data arrays. Trudy SPIIRAN [SPIIRAS Proceedings], 2019, vol. 18, no. 2, pp. 471–503 (In Russ.).Ярмолик, В. Н. Адресные последовательности для многократных маршевых тестов / В. Н. Ярмолик, С. В. Ярмолик // Автоматика и вычислительная техника. – 2006. – № 5. – С. 59–68.Yarmolik V. N., Yarmolik S. V. Address sequences for multiple march tests. Avtomatika i vuchislitel’naya technika [Automation and Computer Science], 2006, no 5, pp. 59–68 (In Russ.).Savage, C. A survey of combinatorial Gray code / С. Savage // SIAM Review. – 1997. – Vol. 3, no. 4. – P. 605–629.Savage C. A survey of combinatorial Gray code. SIAM Review, 1997, vol. 3, no. 4, pp. 605–629.Mrozek, I. Transparent memory tests based on the double address sequences / I. Mrozek, V. N. Yarmolik // Entropy. – 2021. – No. 23. – Р. 894.Mrozek I., Yarmolik V. N. Transparent memory tests based on the double address sequences. Entropy, 2021, no. 23, pp. 894.Неразрушающие тесты с четным повторением адресов для запоминающих устройств / В. Н. Ярмолик [и др.] // Информатика. – 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.).Kuhn, H. W. Variants of the Hungarian method for assignment problems / H. W. Kuhn // Naval Research Logistics Quarterly. – 1956. – Vol. 3, no. 4. – P. 253–258.Kuhn H. W. Variants of the Hungarian method for assignment problems. Naval Research Logistics Quarterly, 1956, vol. 3, no. 4, pp. 253–258.Munkres, J. Algorithms for the assignment and transportation problems / J. Munkres // J. of the Society for Industrial and Applied Mathematics. – 1957. – Vol. 5, no. 1. – P. 32–38.Munkres J. Algorithms for the assignment and transportation problems. Journal of the Society for Industrial and Applied Mathematics, 1957, vol. 5, no. 1, pp. 32–38.Blum, C. Metaheuristics in combinatorial optimization: Overview and conceptual comparison / C. Blum, A. Roli // ACM Computing Surveys. – 2003. – Vol. 35, no. 3. – P. 268–308.Blum C., Roli A. Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ACM Computing Surveys, 2003, vol. 35, no. 3, pp. 268–308.

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