Меры различия, основанные на применении расстояния Хэмминга, для генерирования управляемых вероятностных тестов

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

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

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

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

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

5. Ярмолик, В. Н. Контроль и диагностика вычислительных систем / В. Н. Ярмолик. – Минск : Бестпринт, 2019. – 387 с.

6. A survey on adaptive random testing / R. Huang [et al.] // IEEE Transactions on Software Engineering. – 2021. – Vol. 47, no. 10. – P. 2052–2083.

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

8. Ярмолик, С. В. Управляемое случайное тестирование / С. В. Ярмолик, В. Н. Ярмолик // Информатика. – 2011. – № 1(29). – С. 79–88.

9. Nikravan, E. Hybrid adaptive random testing / E. Nikravan, S. Parsa // Intern. J. of Computing Science & Mathematics. – 2020. – Vol. 11, no. 3. – P. 209.

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

11. Садовский, М. Г. О сравнении символьных последовательностей / М. Г. Садовский // Вычислительные технологии. – 2005. – № 3(10). – С. 106–116.

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

13. Левенштейн, В. И. Двоичные коды с исправлением выпадений, вставок и замещений символов / В. И. Левенштейн // Доклады Академии наук СССР. – 1965. – Т. 163, № 4. – С. 845–848.

14. Алгоритмы: построение и анализ : пер. с англ. / Т. Кормен [и др.]. – 3-е изд. – М. : Изд. дом «Вильямс», 2013. – 1328 с.

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

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

17. Smith, T. F. Identification of common molecular subsequences / T. F. Smith, M. S. Waterman // J. of Molecular Biology. – 1981. – Vol. 147. – P. 195–197.

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

19. Ярмолик, В. Н. Мера различия для тестовых наборов при генерировании управляемых вероятностных тестов / В. Н. Ярмолик, В. В. Петровская, И. Мрозек // Информатика. – 2022. – Т. 19, № 4. – С. 7–26.

20. Ярмолик, В. Н. Мера различия для управляемых вероятностных тестов / В. Н. Ярмолик, Н. А. Шевченко, В. В. Петровская // Доклады БГУИР. – 2022. – Т. 20, № 6. – С. 52–60.

21. Неразрушающие тесты с четным повторением адресов для запоминающих устройств / В. Н. Ярмолик [и др.] // Информатика. – 2021. – Т. 18, № 3. – С. 18–35.

22. Многомерный портрет цифровых последовательностей идеального «белого шума» в свертках Хэмминга / В. И. Волчихин [и др.] // Известия высших учебных заведений. Поволжский регион. Технические науки. – 2017. – № 4(44). – С. 4–13.

23. Условия корректного вычисления энтропии осмысленных длинных паролей в пространстве сверток Хэмминга с эталонными текстами на русском и английском языках / В. И. Волчихин [и др.] // Измерение. Мониторинг. Управление. Контроль. – 2019. – № 3(29). – С. 33–38.