Применение задачи о кратчайшем покрытии при тестировании программного продукта | Вестн. Том. гос. ун-та. Управление, вычислительная техника и информатика. 2019. № 47. DOI: 10.17223/19988605/47/12

Применение задачи о кратчайшем покрытии при тестировании программного продукта

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

Application of the shortest cover problem in testing a software product.pdf Многие комбинаторные оптимизационные задачи сводятся к задаче о кратчайшем покрытии, которая ставится следующим образом. Пусть даны некоторое множество А = {a1, a2, ..., a„} и совокупность его подмножеств В, В2, ..., Вт, т.е. Б, с A, i = 1, 2, ..., m, причем В1 и В2 и ... и Вт = А. Требуется среди данных подмножеств выделить такую совокупность Bj , Bj , ... , Bik с минимальным к, чтобы каждый элемент из А попал хотя бы в одно из Bj. (j = 1, 2, ..., к), т.е. Bt uBt и... uBt = A. J 12 к Удобно рассматривать матричную формулировку данной задачи, при которой совокупность В1, В2, ., Вт задается в виде булевой матрицы, строки которой соответствуют подмножествам из данной совокупности, а столбцы - элементам множества А. Элемент i-й строки и j-го столбца имеет значение 1, если и только если aj е Б,. В этом случае говорят, что i-я строка покрывает j-й столбец. Требуется найти такое множество строк данной матрицы, чтобы каждый ее столбец имел единицу хотя бы в одной строке из этого множества, и при этом мощность выбранного множества должна быть минимальной. В такой интерпретации имеем дело с задачей поиска кратчайшего строчного покрытия булевой матрицы. Задача о кратчайшем покрытии булевой матрицы нашла применение в теории графов, в теории логического проектирования дискретных устройств, при решении задач технической диагностики, в некоторых алгоритмах минимизации логических функций [1]. Встал вопрос, может ли успешно применяться данная задача при тестировании программного обеспечения. Проблема качества программных продуктов (ПП) становится сегодня все более острой, особенно по мере расширения использования информационных технологий и роста сложности ПП, при работе большой команды разработчиков. Высокое качество продуктов дает разработчикам не только конкурентные преимущества и кредит доверия клиентов, но и облегчает сопровождение и развитие ПП. Одним из ключевых элементов обеспечения качества ПП является тестирование [2, 3]. Для тестирования ПП необходима разработка тестов. Разработчики ПП проводят тестирование своих продуктов в несколько этапов, которые отличаются видами выполняемых работ и привлекаемыми ресурсами. Фактически тестирование начинается еще в процессе кодирования очередной версии программы. Затраты на тестирование вносят существенный вклад в общую стоимость сопровождения программы. Выборочный подход к регрессионному тестированию измененной программы требует исключения некоторых тестов из существующего набора, что приводит к уменьшению затрат. При проведении тестирования важно выбрать подмножество тестов минимальной мощности, обеспечивающее достижение целей регрессионного тестирования. В научной литературе подчеркивается важность комплексного подхода [2, 3]. Под комплексным подходом к управлению качеством IIII имеется в виду необходимость поиска и устранения дефектов на каждом этапе жизненного цикла ПП [4]. Основными методами поиска дефектов являются отладка и тестирование. Методы поиска дефектов имеют различную эффективность и стоимость. Классификация дефектов по типам позволит отправлять их на устранение определенным разработчикам, что приведет к уменьшению затрат. Для проведения регрессионного тестирования реальных проектов и устранения в них дефектов можно предложить две задачи, решение которых сводится к нахождению кратчайшего покрытия некоторой булевой матрицы. Одна из них связана с нахождением минимального набора тестов при регрессионном тестировании функционала программы. Вторая задача позволяет получить минимальный диагностический тест при классификации дефектов в программном продукте. Обе задачи решаются с помощью минимаксного алгоритма, одним из приближенных методов решения задачи о кратчайшем покрытии. 1. Задача о нахождении минимального набора тестов при регрессионном тестировании функционала программы Регрессионное тестирование - это выборочное тестирование, позволяющее убедиться, что изменения не вызвали нежелательных побочных эффектов или что измененная система по-прежнему соответствует требованиям. После каждой модификации программы необходимо удостовериться, что на функциональность программы не оказал влияния модифицированный код. Регрессионное тестирование - дорогостоящий род деятельности: процесс регрессионного тестирования может включать исполнение достаточно большого количества тестов на скорректированной программе, даже если изменений очень мало. Несмотря на то, что усилия, требуемые для внесения небольших изменений, как правило, минимальны, они могут требовать достаточно больших усилий для проверки качества измененной программы. Тем не менее проведение регрессионного тестирования необходимо. Надежная и эффективная разработка и дальнейшее сопровождение программного обеспечения невозможны без регрессионного тестирования. Выполнить полное регрессивное тестирование вряд ли возможно. По мере роста и расширения становится все сложнее тестировать отдельные части системы программного обеспечения. Эта проблема усложняется из-за частоты создания сборок программ. Необходимо тестировать предыдущую функциональность, чтобы обеспечить возможность тестирования новых исправлений и новых функций. В настоящее время выделяют следующие методы отбора тестов для регрессионного тестирования: случайные методы; безопасные методы; методы минимизации; методы, основанные на покрытии кода. Каждый из представленных методов имеет свои достоинства и недостатки [4]. Применение задачи о кратчайшем покрытии булевой матрицы для отбора тестов при проведения регрессионного тестирования безопасным выборочным методом позволяет сократить временные затраты на проведение регрессионного тестирования без потери качества программного продукта. В качестве булевой матрицы выступает матрица R, строки которой соответствуют тестируемым функционалам программы, а столбцы соответствуют тестам, предназначенным для этого. Элемент матрицы rij равен 1, если для тестирования функционала f пригоден тест tj, иначе элемент rij. матрицы R равен 0. В качестве примера рассмотрен реальный проект «Сайт-платформа сравнения цен на услуги по страхованию автомобиля». Для этого выделены 17 ключевых элементов системы (тестируемый функционал), безотказная работа которых была критична для данного приложения. К ним относятся: a - вход на сайт; b - выход; c - регистрация; d - идентифицированный пользователь; e - пользователь-студент; f - работающий пользователь; g - безработный пользователь; h - пользователь с дополнительным водителем; i - анонимный пользователь; k - пользователь с истекшим временем покупки; m - проверка уведомлений об ошибке; n - пользователь, вернувшийся на сайт после 11 месяцев; o - активный пользователь; p - пользователь с дополнительной работой; r - индивидуальный предприниматель; s - страница с результатами покупки; t - рассылка информации на почту. Далее был создан тестовый набор регрессионного тестирования, который содержал проверки заявленной функциональности (14 тестов): 1 - «приходящий через 11 месяцев»; 2 - анонимный посетитель; 3 - дополнительный водитель; 4 - базовый тест; 5 - граничный тест; 6 - редактирование; 7 -пользовательский отчет; 8 - встроенный вход; 9 - навигация по сайту; 10 - сброс пароля; 11 - страница с результатами; 12 - повторный покупатель; 13 - проверка ошибок, 14 - рассылка на почту. Затем была построена диагностическая матрица (таблица). Строки матрицы соответствуют функциональным модулям программы, а столбцы - тестам. Элемент матрицы С на пересечении 7-й строки и j-го столбца имеет значение 1, если для тестирования /-го модуля необходим j-й тест. В противном случае элемент матрицы равен 0. Далее к данной матрице был применен алгоритм поиска кратчайшего столбцового покрытия. Результаты оказались достаточно успешными: удалось сократить тестовый набор на 14,3% без потери процента покрытия функциональных возможностей программы. Два теста, а именно тесты с номерами 3 и 4, оказались излишними. Диагностическая матрица Функционал Тесты 1 2 3 4 5 6 7 8 9 10 11 12 13 14 a 1 1 1 1 1 1 1 1 1 1 1 1 1 1 b 1 1 1 1 1 1 1 1 1 1 1 1 1 1 c 1 1 1 1 1 1 1 1 1 1 1 1 d 1 1 1 1 1 1 1 e 1 1 1 1 f 1 1 1 1 g 1 1 1 h 1 1 1 1 1 7 1 к 1 m 1 n 1 o 1 1 1 1 1 1 1 1 1 1 1 P 1 1 1 1 1 1 1 1 1 1 1 1 1 r 1 1 s 1 1 1 1 t 1 Аналогично данный метод был применен для другого проекта - «Сайта страхования недвижимости». По реализуемой задаче оба приложения похожи и имеют небольшое количество отличительных черт. Поэтому и тестовый набор во многом одинаков. Во втором случае удалось добиться уменьшения первоначального тестового набора на 21,4%. 2. Задача о нахождении минимального диагностического теста при классификации дефектов в программном продукте Автоматизированное тестирование подразумевает под собой разработку и использование специального программного обеспечения для запуска и контроля выполнения тестовых сценариев и сравнения реальных и запланированных результатов согласно спецификации. При организации автоматизации тестирования больших проектов, когда необходимо разделение специалистов по тестированию на определенные группы, появляется задача о классификации дефектов. Опишем распределение ролей в достаточно крупной команде специалистов, занимающихся автоматизацией тестирования. Сама по себе автоматизация крайне редко применяется на краткосрочных или часто изменяющихся проектах, что связано с постоянно растущими затратами на поддержку и написание автоматических тестов. Проект с применением автоматизации имеет большое количество вариантов использования. Это можем быть работа, связанная с тестированием интерфейсов (внешнего отображения), сервисов, производительности и нагрузки, стрессовым тестированием, тестированием взаимодействия с внешними приложениями по отношению к данному и т.д. Само собой разумеется, что и за дефекты, возникающие в процессе тестирования и работы приложения, будут отвечать специалисты, занимающиеся поддержкой данной деятельности на проекте и являющиеся в ней наиболее квалифицированными. Работа многих систем отслеживания и устранения дефектов организована при помощи данных классификаций дефекта [5]. Используется следующая классификация дефектов с точки зрения степени влияния (Severity) на работоспособность программы: - блокирующий (Blocker). Блокирующая ошибка, приводящая приложение в нерабочее состояние, в результате чего дальнейшая работа с тестируемой системой или ее ключевыми функциями становится невозможной. Решение проблемы необходимо для дальнейшего функционирования системы; - критический (Critical). Критическая ошибка, неправильно работающая ключевая бизнес-логика, дыра в системе безопасности, проблема, приведшая к временному падению сервера или приводящая в нерабочее состояние некоторую часть системы, без возможности решения проблемы, используя другие входные точки. Решение проблемы необходимо для дальнейшей работы с ключевыми функциями тестируемой системой; - значительный (Major). Значительная ошибка, часть основной бизнес-логики работает некорректно. Ошибка не критична или есть возможность для работы с тестируемой функцией, используя другие входные точки; - незначительный (Minor). Незначительная ошибка, не нарушающая бизнес-логику тестируемой части приложения, очевидная проблема пользовательского интерфейса; - тривиальный (Trivial). Тривиальная ошибка, не касающаяся бизнес-логики приложения, плохо воспроизводимая проблема, малозаметная посредствам пользовательского интерфейса, проблема сторонних библиотек или сервисов, проблема, не оказывающая никакого влияния на общее качество продукта. Градация дефектов с точки зрения приоритетности исправления (Priority): - высокий (High): ошибка должна быть исправлена как можно быстрее, так как ее наличие является критической для проекта; - средний (Medium): ошибка должна быть исправлена, ее наличие не является критичной, но требует обязательного решения; - низкий (Low): ошибка должна быть исправлена, ее наличие не является критичной и не требует срочного решения. В зависимости от того, какой методологии придерживаются на проекте, распределение зарегистрированных дефектов между специалистами может быть различным. Однако на данный момент одним из наиболее распространенных и приоритетных способов является наличие одной общей «доски с дефектами», куда помещаются все найденные дефекты. Далее специалист по автоматизации открывает «доску» и смотрит на список дефектов, расположенных там. Разумеется, сложно с первого взгляда определить, к какому типу относится дефект и какому специалисту лучше поручить работу над ним. Поэтому на процесс анализа, классификации и дальнейшего устранения дефектов тратится достаточно большой объем времени. В подобных условиях применение автоматизированной классификации дефектов является не только рациональным, но желательным для организации эффективной деятельности команды. Это позволит уменьшить время простоев, которые неминуемо возникают в случае ошибочной передачи дефекта. Задача о нахождении минимального диагностического теста, предложенная в [1], может оказаться весьма полезной. Рассмотрим множества D = {D1, D2, ..., Dn} и B = {Ъ, Ъг, ..., Ъп}. Множество D является множеством возможных дефектов, множество В - множеством внешних признаков (симптомов), которые возникают вследствие обнаружения дефекта. Симптом - свойство дефекта, позволяющее классифицировать дефекты по их типичному проявлению. Строится булева диагностическая матрица С, которая показывает, какими признаками характеризуется тот или иной дефект. Элемент матрицы Cij равен 1, если дефект Di влечет симптом bj, иначе элемент су матрицы С равен 0. Для матрицы С строится матрица различий R, строки которой соответствуют парам строк диагностической матрицы и показывают, какими компонентами отличаются строки в этих парах; при этом будем использовать покомпонентную операцию сложения по модулю два, выполняя ее над всеми парами строк диагностической матрицы. Для полученной матрицы различий можно найти кратчайшее столбцовое покрытие. Множество признаков, соответствующих столбцам найденного покрытия, будет искомым решением задачи. При этом каждый дефект можно однозначно определить соответствующей строкой подматрицы С'матри-цы С. Это позволяет наиболее рациональным образом классифицировать дефекты на момент их возникновения по данным признакам. В качестве примера рассмотрен реальный проект - веб-приложение для МТБанка «Halva.by», в котором были выделены такие симптомы дефектов, как: 1. Косметический симптом - визуально заметный недостаток интерфейса, не влияющий на функциональность приложения. 2. Некорректная операция - некорректное выполнение некоей операции. 3. Нереализованная функциональность - некая функция приложения не выполняется или не может быть вызвана. 4. Низкая производительность - выполнение неких операций занимает недопустимо большое время. 5. Крах системы - приложение прекращает работу или теряет способность выполнять свои ключевые функции. 6. Неожиданное поведение - в процессе выполнения некоторой типичной операции приложение ведет себя необычным образом. 7. Недружественное поведение - поведение приложения создает пользователю неудобства в работе. 8. Расхождение с требованиями - приложение ведет себя не так, как указано в требованиях. 9. Предложение по улучшению - приложение ведет себя согласно требованиям, но у специалиста по тестированию есть обоснованное мнение о том, как ту или иную функциональность можно улучшить. При проведении тестирования в программном продукте найдены следующие дефекты: Di: отсутствует логотип компании при авторизации в системе. D2: отображается страница «Акции» при клике на раздел «Аксессуары». D3: отсутствует раздел «Избранные магазины». D4: не загружается страница «Техника» со списком соответствующих магазинов при одновременном пользовании сайтом количеством человек, равным 10 000. D5: крах плагина Adobe Flash при попытке просмотра видеозаписи. De. номер телефона технической поддержки не удается набрать в мобильном браузере. Для нахождения минимального диагностического теста построим диагностическую матрицу С: 1 2345678 9 "1 0 0 0 0 0 0 1 0" 0 1 0 0 0 1 1 1 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 0 1 D1 D2 С = D3 D4 D5 D6 Ниже представлена матрица различий R, строки которой соответствуют парам строк диагностической матрицы и показывают, какими компонентами отличаются строки в этих парах; при этом будем использовать покомпонентную операцию сложения по модулю два, выполняя ее над всеми парами строк диагностической матрицы. Столбцы матрицы соответствуют симптомам. 1 2345678 9 "1 1 0 0 0 1 1 0 0" 1 0 1 0 0 0 0 0 0 1 0 0 1 0 0 1 1 0 110 0 11110 1 0 0 0 0 0 1 1 1 0 1 1 0 0 0 1 0 0 0 1 0 1 0 0 0 1 0 0 10 0 110 10 . 0 1 0 0 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 1 1 1 0 0 0 1 0 0 0 1 1 1 0 10 1110 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 1 0 0 1 Используя минимаксный алгоритм поиска кратчайшего столбцового покрытия матрицы R, получаем одно их возможных кратчайших покрытий П = (1, 2, 3, 4, 6). Действительно, множество симптомов П однозначно диагностирует каждый дефект данного программного продукта, поскольку все строки подматрицы C 'различны: 1 2 3 4 6 D "1 0 0 0 0" D2 0 1 0 0 1 C'= D3 0 0 1 0 0 D4 0 0 0 1 0 D5 0 0 0 0 1 D6 0 0 0 0 0 Так, дефект D1 характеризуется только симптомом 1, дефект D2 характеризуется наличием симптомов 2, 6 и отсутствием симптомов 1, 3, 4 и т.д. Что касается практического применения данного подхода, то каждому из признаков (симптомов) дефекта может соответствовать определенная метка, которая будет однозначно идентифицировать дефект на «доске». проекта. Последнее ускорит поиск и распределение дефектов между специалистами, а в дальнейшем эффективно скажется на работе всего проекта. Также это имеет и обратную связь: в случае, если после исправления дефекта он снова был обнаружен, поиск причин такого поведения системы будет организован гораздо легче и быстрее. Заключение Для автоматизации процесса мониторинга и контроля дефектов, регрессионного тестирования при разработке программных продуктов создана система управления задачами и отслеживанием ошибок, в которой представлены программные модули для реализации решения рассмотренных выше задач. Система может применяться, например, в начинающих организациях, которые не обладают средствами для обеспечения себя дорогостоящими продуктами, такими как JIRA, Trello, Yodiz. Бюджетные программные средства, использующиеся на данный момент организациями, имеют ограниченные возможности и не обладают достаточным набором функций. Система выполняет следующие функции и задачи: - добавление, изменение, просмотр и удаление проектов, задач, дефектов, а также сотрудников команды, работающей над созданием программного продукта; - осуществление поиска задачи, дефектов, сотрудника по различным параметрам; DD2 D1D3 D1D4 D1D5 DD6 В2 D3 D2 D4 D2 D5 D2D6 D3 D4 D3 D5 D3D6 D4 D5 D4D6 D5 D6 R = - отображение личного кабинета сотрудника компании; - разграничение функционала в зависимости от роли: проектный менеджер (администратор) и специалист по тестированию или обнаружению дефектов (пользователь); - определение минимального диагностического теста и минимального тестового набора при регрессионном тестировании. Система реализована в виде распределенного приложения на языке Java c использованием технологий и фреймворков разработки веб-приложений. Веб-приложение представлено в виде клиент-серверного приложения, в котором клиентом выступает браузер, а сервером - веб-сервер.

Ключевые слова

регрессионное тестирование, задача о покрытии, дефекты программного продукта, диагностический тест, матрица различий, regression testing, short cover problem, defects of a software product, diagnostic test, distinction matrix

Авторы

ФИООрганизацияДополнительноE-mail
Поттосина Светлана АнатольевнаБелорусский государственный университет информатики и радиоэлектроникидоцент, кандидат физико-математических наук, доцент кафедры экономической информатикиs.pottosina@gmail.com
Всего: 1

Ссылки

Закревский А.Д., Поттосин Ю.В., Черемисинова Л.Д. Логические основы проектирования дискретных устройств. М. : Физматлит, 2007. 592 с.
Бейзер Б. Тестирование черного ящика. Технологии функционального тестирования программного обеспечения и систем : пер. с англ. СПб. : Питер, 2004. 318 с.
Wang Sh., Wu Yu., Lu M., Li H. Software reliability accelerated testing method based on test // Proceedings «Annual Reliability and Maintainability Symposium». Lake Buena Vista, FL, USA. 24-27 Jan. 2011.
Котляров В.П. Основы тестирования программного обеспечения : учеб. пособие. М. : БИНОМ. Лаборатория знаний, 2006. 285 с.
Куликов С.С. Тестирование программного обеспечения : базовый курс. Минск : Четыре четверти, 2017. 312 с.
 Применение задачи о кратчайшем покрытии при тестировании программного продукта | Вестн. Том. гос. ун-та. Управление, вычислительная техника и информатика. 2019. № 47. DOI: 10.17223/19988605/47/12

Применение задачи о кратчайшем покрытии при тестировании программного продукта | Вестн. Том. гос. ун-та. Управление, вычислительная техника и информатика. 2019. № 47. DOI: 10.17223/19988605/47/12