Preview

Информатика

Расширенный поиск

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

https://doi.org/10.37661/1816-0301-2022-19-4-7-26

Аннотация

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

Об авторах

В. Н. Ярмолик
Белорусский государственный университет информатики и радиоэлектроники
Беларусь

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

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



В. В. Петровская
Белорусский государственный университет информатики и радиоэлектроники
Беларусь

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

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



И. Мрозек
Белостоцкий технический университет
Польша

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

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



Список литературы

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

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

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

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

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

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

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

8. Ярмолик, В. Н. Многократные управляемые вероятностные тесты / В. Н. Ярмолик, В. А. Леванцевич, И. Мрозек // Информатика. – 2015. – № 2(46). – С. 63–76.

9. Mrozek, I. Multiple controlled random testing / I. Mrozek, V. N. Yarmolik // Fundamenta Informaticae. – 2016. – Vol. 144, no. 1. – P. 23–43.

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

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

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

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

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

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. О мерах сходства расположения компонентов в массивах естественно упорядоченных данных / А. С. Гуменюк [и др.] // Тр. СПИИРАН. – 2019. – Vol. 18, no. 2. – P. 471–503.

17. Ярмолик, В. Н. Адресные последовательности для многократных маршевых тестов / В. Н. Ярмолик, С. В. Ярмолик // Автоматика и вычислительная техника. – 2006. – № 5. – С. 59–68.

18. Savage, C. A survey of combinatorial Gray code / С. Savage // SIAM Review. – 1997. – Vol. 3, no. 4. – P. 605–629.

19. Mrozek, I. Transparent memory tests based on the double address sequences / I. Mrozek, V. N. Yarmolik // Entropy. – 2021. – No. 23. – Р. 894.

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

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

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

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


Рецензия

Для цитирования:


Ярмолик В.Н., Петровская В.В., Мрозек И. Мера различия для тестовых наборов при генерировании управляемых вероятностных тестов. Информатика. 2022;19(4):7-26. https://doi.org/10.37661/1816-0301-2022-19-4-7-26

For citation:


Yarmolik V.N., Petrovskaya V.V., Mrozek I. A measure of the difference between test sets for generating controlled random tests. Informatics. 2022;19(4):7-26. (In Russ.) https://doi.org/10.37661/1816-0301-2022-19-4-7-26

Просмотров: 302


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1816-0301 (Print)
ISSN 2617-6963 (Online)