Пріоритезація тестів у регресивному тестуванні
Prioritization (test ranking) in the regression testing is considered with the purpose of increasing the rate of fault detection in software during execution of a test suite. New prioritization techniques with higher effectiveness and lower prioritization costs have been developed. Also, comparative...
Saved in:
| Date: | 2019 |
|---|---|
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
2019
|
| Online Access: | https://journal.iasa.kpi.ua/article/view/154653 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | System research and information technologies |
| Download file: |  |
Institution
System research and information technologies| _version_ | 1866302295091707904 |
|---|---|
| author | Malishevsky, A. G. |
| author_facet | Malishevsky, A. G. |
| author_sort | Malishevsky, A. G. |
| baseUrl_str | http://journal.iasa.kpi.ua/oai |
| collection | OJS |
| datestamp_date | 2019-01-18T15:10:28Z |
| description | Prioritization (test ranking) in the regression testing is considered with the purpose of increasing the rate of fault detection in software during execution of a test suite. New prioritization techniques with higher effectiveness and lower prioritization costs have been developed. Also, comparative evaluation of the effectiveness of both new and previously developed prioritization methods has been made. |
| first_indexed | 2025-07-17T10:24:20Z |
| format | Article |
| fulltext |
© А.Г. Малышевский, 2006
16 ISSN 1681–6048 System Research & Information Technologies, 2006, № 4
TIДC
ПРОГРЕСИВНІ ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ,
ВИСОКОПРОДУКТИВНІ КОМП’ЮТЕРНІ
СИСТЕМИ
УДК 004.415.53
ПРИОРИТЕЗАЦИЯ ТЕСТОВ В РЕГРЕССИВНОМ
ТЕСТИРОВАНИИ
А. Г. МАЛЫШЕВСКИЙ
Рассмотрена приоритезация (ранжирование тестов) в регрессивном тестирова-
нии для ускорения выявления ошибок в программном обеспечении при вы-
полнении набора тестов. Приведены новые методы приоритезации для повы-
шения эффективности и понижения затрат в случае их применения. Проведена
оценка сравнительной эффективности как новых, так и известных из литерату-
ры методов.
ВВЕДЕНИЕ
Цель верификации программы — определить, удовлетворяет ли программа
заданным требованиям и ее спецификации. Одним из видов верификации
является тестирование (выполнение программы и проверка ее поведения на
соответствие спецификациям). Обычно в тестировании используется набор
тестов. Каждый тест состоит из множества входных значений (сценариев
тестирования), применяемых к программе для проверки ее поведения. Назо-
вем конечное множество тестов (или сценариев тестирования) T набором
тестов. Одним из подходов тестирования может быть исчерпывающее тес-
тирование, при котором набор тестов состоит из всех возможных допусти-
мых входных значений программы. Однако в большинстве случаев такой
подход не практичен. Поэтому набор создается, исходя из некоторого мно-
жества правил, определяющих его состав, называемого критерием адекват-
ности тестов. Критерий адекватности выражает условия, которым должен
удовлетворять набор тестов [1].
Регрессивное тестирование — это тестирование, применяемое после
внесения изменений в программу для ее проверки. Оно используется в ста-
дии сопровождения после исправления ошибок, адаптации программы к но-
вой среде или увеличения ее производительности. Таким образом выполня-
ется проверка того, что внесенные в программу модификации не только
изменили программу в соответствии с новыми спецификациями и исправи-
ли найденные ошибки, но и не внесли новых ошибок [1]. Разработчики про-
граммного обеспечения часто сохраняют написанные ими тесты для их по-
вторного использования в процессе эволюции программного обеспечения.
Для проверки новой функциональности программы разработчики добавляют
Приоритезация тестов в регрессивном тестировании
Системні дослідження та інформаційні технології, 2006, № 4 17
новые тесты в набор, который в результате растет, а вместе с ним растет и
стоимость регрессивного тестирования.
Так как регрессивное тестирование применяется многократно, его
стоимость может существенно влиять на стоимость всего программного
продукта. Поэтому даже небольшое уменьшение стоимости регрессивного
тестирования может значительно снизить стоимость всего программного
обеспечения. Уменьшая время тестирования, можно уменьшить время соз-
дания новой версии программы. Пример высокой стоимости регрессивного
тестирования — программный продукт, тестирование которого занимает
семь недель. Существует несколько подходов к уменьшению стоимости
регрессивного тестирования: 1) в регрессивном отборе тестов (regression test
selection) перед каждой сессией тестирования выбирается подмножество
набора тестов, и затем оно применяется для проверки модифицированной
программы; 2) в редукции набора тестов (test suite reduction), где в некото-
рый момент времени набор перманентно редуцируется, из данного набора
удаляется часть тестов и не используется при будущих тестированиях.
В некоторых случаях, когда невозможно или не разрешается пропус-
кать тесты в регрессивном тестировании, описанные два подхода неприем-
лемы, например, для программ, надежность которых является критичной
(авионика или управление медицинским оборудованием). В данном случае
для уменьшения стоимости регрессивного тестирования может быть приме-
нен иной подход: тесты упорядочиваются (приоритезируются) для регрес-
сивного тестирования таким образом, чтобы более важные из них выполня-
лись перед менее важными. В методах приоритезации тесты сортируют
таким образом, чтобы эффективнее достичь заданной цели [2, 3]. Примером
такой цели может быть наиболее быстрое покрытие операторов програм-
много кода, функций программы в порядке частоты их использования или
подсистем в порядке частоты их сбоя в прошлом. Возможная цель приори-
тезации — увеличение скорости выявления ошибок набором тестов в про-
цессе тестирования. Возросшая скорость выявления ошибок может обеспе-
чить более раннюю обратную связь с регрессивно тестируемой системой и
позволить разработчикам начать поиск местонахождения ошибок, а также
их исправление раньше, чем это было бы возможно в ином случае. Такая
обратная связь обеспечивает более ранние признаки того, что заданные цели
еще не достигнуты и позволяет принимать более ранние стратегические ре-
шения о сроках релиза. Кроме этого, улучшенная скорость выявления оши-
бок повышает вероятность того, что в случае преждевременного прекраще-
ния процесса тестирования тесты, обеспечивающие наибольшую
способность выявлять ошибки в сроки, выделенные под тестирование, уже
были выполнены.
Рассмотрим результаты, известные из литературных источников.
Rothermel и другие авторы в работе [2] описывают эксперименты над
несколькими небольшими программами на языке Си. Исследовано шесть
методов приоритезации, включая приоритезацию тестов по общему и до-
полнительному покрытию операторов, ветвей, а также операторов, исполь-
зующих потенциал выявления ошибок. Все рассмотренные в [2] методы по-
казали некоторую способность улучшать значение метрики APFD по
сравнению со случайным упорядочиванием. В целом методы, использую-
А.Г. Малышевский
ISSN 1681–6048 System Research & Information Technologies, 2006, № 4 18
щие потенциал выявления ошибок, показали наилучшую эффективность. За
ними следует приоритезация тестов по общему покрытию ветвей и операто-
ров.
В работе [4] Rothermel и другие авторы расширили эти результаты, ис-
пользуя те же программы, что и в [2]. Здесь в роли ошибок выступали му-
танты (измененные операторы). Подобно результатам предыдущих экспе-
риментов приоритезация по дополнительному покрытию операторов,
использующая потенциал выявления ошибок, достигла статистически зна-
чимых наилучших результатов.
Wong и другие авторы в работе [3] предлагают приоритезировать тесты
в соответствии со следующим критерием: сортировать по увеличивающейся
стоимости тестов на единицу дополнительного покрытия. Авторы ограни-
чиваются приоритезацией подмножества тестов, выбранных безопасным
методом регрессивного отбора, хотя оставшиеся тесты могут быть добавле-
ны к концу списка для дальнейшего выполнения.
Jones и Harrold в работе [5] описывают метод приоритезации для набо-
ров тестов с таким критерием адекватности, как покрытие решений моди-
фицируемым условием (modified condition/decision coverage). Данный метод
использует итеративный подход, обновляя информацию о тестах в процессе
добавления их к отсортированной последовательности. Алгоритм создает
список упорядоченных последовательностей тестов.
Srivastava и Thiagarajan в работе [6] показали метод приоритезации, ос-
нованный на покрытии базисных блоков (часть кода, имеющая только один
вход и один выход). В данном алгоритме в каждой итерации выбирается
тест, покрывающий наибольшее количество еще непокрытых модифициро-
ванных базисных блоков кода. Этот метод был применен к нескольким
большим системам в Microsoft, демонстрируя возможность его эффективно-
го использования. Приоритезированные тесты быстро достигают покрытия
кода и могут рано выявлять ошибки. Однако в работе [6] нет сравнения
предложенного авторами метода с другими известными методами и со слу-
чайным упорядочиванием тестов. Следовательно, невозможно сказать, уве-
личивает ли этот метод скорость выявления ошибок в сравнении с другими
методами.
Kim и Porter в работе [7] демонстрируют метод, который они опреде-
ляют как «приоритезация, основанная на прошлом». Здесь используется ин-
формация из предыдущих циклов регрессивного тестирования для лучшего
информирования процесса выбора подмножества тестов из существующего
набора в случае применения к модифицированной версии системы. Этот
метод не является методом приоритезации с точки зрения формального оп-
ределения, так как он не ранжирует тесты (основная характеристика опреде-
ления приоритезации), а выбирает их подмножество, используя информа-
цию о предыдущих тестированиях. Более точно он описывается как метод
регрессивного отбора тестов [8]. Исходной информацией может быть ре-
зультат выполнения теста, выявление ошибки или покрытие элемента про-
граммы (например, оператор, ветвь).
Avritzer и Weyuker в работе [9] описали методы генерирования тестов
для программ, моделируемых цепями Маркова при наличии данных опера-
Приоритезация тестов в регрессивном тестировании
Системні дослідження та інформаційні технології, 2006, № 4 19
ционного профиля. Хотя авторы не используют термин «приоритезация», их
методы генерируют тесты в таком порядке: бóльшие подмножества состоя-
ний программы, наиболее вероятные при ее нормальном использовании,
покрываются как можно раньше (особенно при сортировке тестов в порядке
увеличения вероятности того, что ошибки, которые могут привести к сбоям
программы при ее нормальном использовании, выявятся раньше в процессе
тестирования). Данный метод не рассматривает приоритезацию сущест-
вующих тестов при тестировании модифицированной программы, однако он
показывает пример использования приоритезации в случае недоступности
набора тестов.
Несмотря на проведенные исследования в работах [2, 4, 5, 6, 7, 9], для
успешной интеграции приоритезации в процесс регрессивного тестирования
необходима разработка эффективных и дешевых методов, которые сделают
ее применение целесообразным. В дополнение к проведенным ранее иссле-
дованиям на ограниченном наборе программ (объектов исследования), в
данной работе проводятся эмпирические исследования на расширенном
множестве подобных объектов, что позволит проверить возможность обоб-
щения полученных ранее результатов и необходимость дальнейших иссле-
дований.
ОПРЕДЕЛЕНИЕ ПРИОРИТЕЗАЦИИ ТЕСТОВ
Дано: T — набор тестов; PT — множество перестановок T ; f — функ-
ция →PT ℝ.
Задача: найти такое PTT' ∈ , что для всех T'' из PT : )]()([ TfT'f ′′≥ ,
где PT — множество всех возможных перестановок T ; f — функция,
примененная к любой такой перестановке, вычисляет ценность этой пере-
становки.
МЕТОДЫ ПРИОРИТЕЗАЦИИ
Существуют различные методы достижения цели приоритезации. Напри-
мер, для увеличения скорости выявления ошибок тесты могут быть приори-
тезированы в соответствии с выполнением модулей, имеющих тенденцию к
сбоям в прошлом. Таким же образом можно приоритезировать тесты в соот-
ветствии с покрытием компонентов программного кода или охватом функ-
циональностей, упомянутых в требованиях к программе. В любом случае
задачей приоритезации является увеличение вероятности достижения за-
данной цели приоритезированным набором тестов по сравнению с непри-
оритезированным. В наших исследованиях цель приоритезации — увеличе-
ние скорости выявления ошибок в процессе выполнения набора тестов.
Другими словами: так упорядочить тесты, чтобы как можно быстрее вы-
явить ошибки.
Рассмотрим 14 методов приоритезации (табл. 1), разделенные на три
группы.
А.Г. Малышевский
ISSN 1681–6048 System Research & Information Technologies, 2006, № 4 20
Т а б л и ц а 1 . Методы приоритезации
Метка Мнемоника Метка Мнемоника Метка Мнемоника
T1 random T6 st-fep-addtl T11 fn-fi-total
T2 optimal T7 fn-total T12 fn-fi-addtl
T3 st-total T8 fn-addtl T13 fn-fi-fep-total
T4 st-addtl T9 fn-fep-total T14 fn-fi-fep-addtl
T5 st-fep-total T10 fn-fep-addtl
Первая — контрольная. Содержит два метода: random и optimal.
Вторая — группа методов, использующих информацию на уровне опе-
раторов. Содержит четыре метода с мелкой гранулярностью (гранулярности
уровня операторов).
Данные методы использовались в работе [2], здесь же мы их изучаем в
контексте приоритезации, ориентированной на заданную версию программы
(version-specific).
Третья — группа уровня функций. Содержит восемь методов крупной
гранулярности (гранулярности на уровне функций), четыре из них похожи
на методы уровня операторов, остальные четыре дополнительно используют
информацию о вероятности существования ошибок. Опишем каждую из них
отдельно.
Группа 1. Контрольные методы. Используются для оценки мини-
мальной и максимальной эффективности приоритезации (в своем роде точек
отсчета).
T1. Случайный порядок — случайное упорядочение тестов в наборе.
T2. Оптимальный порядок — метод оптимальной приоритезации
(быстрейшего выявления ошибок). Имея информацию об ошибках и выяв-
ляющих их тестах, можно найти порядок тестов, при котором скорость вы-
явления ошибок максимальна. Хотя в реальной ситуации такой подход не
практичен, он обеспечивает верхнюю границу эффективности других эври-
стических методов.
Группа 2. Методы, использующие информацию на уровне операто-
ров.
T3. Приоритезация по общему покрытию операторов. Вставляя в
программу дополнительный код, можно определить для каждого теста, ка-
кие операторы им покрыты. Эти тесты можно приоритезировать в соответ-
ствии с количеством покрытых ими операторов, сортируя тесты в порядке
убывания данного общего покрытия. Так как в общем случае невозможно
получить данные о покрытии, избежав выполнения всех тестов, использует-
ся приближенная информация о покрытии операторов, полученная на осно-
вании предыдущего регрессивного тестирования, т.е. предыдущая версия
программы.
T4. Приоритезация по дополнительному покрытию операторов.
Приоритезация по общему покрытию операторов планирует тесты в порядке
достижения совокупного покрытия операторов. Однако, выполнив тест и
Приоритезация тестов в регрессивном тестировании
Системні дослідження та інформаційні технології, 2006, № 4 21
покрыв некоторые операторы, целесообразно при последующем тестирова-
нии покрыть еще не покрытые операторы. Приоритезация по дополнитель-
ному покрытию операторов выбирает тест, достигший наибольшего покры-
тия еще не покрытых, повторяя этот процесс до тех пор, пока ни один из
оставшихся тестов не сможет увеличить покрытие операторов. Когда это
происходит, данный алгоритм применяется рекурсивно к оставшимся тес-
там.
T5. Приоритезация по общему покрытию операторов с учетом FEP.
Выявление тестом ошибки зависит не только от выполнения им компонента
кода, содержащего ошибку, но также и от вероятности сбоя в результате
этой ошибки [10]. Необходимо выяснить, можно ли использовать эту веро-
ятность для увеличения эффективности приоритезации с точки зрения ско-
рости выявления ошибок. Для оценки потенциала выявления ошибок FEP
(fault-exposing-potential) теста был использован мутационный анализ [11].
Дана программа P и набор тестов T . Для каждого теста t из T и для
каждого оператора s в P найдена оценка мутаций (mutation score) ),( tsms
теста t для оператора s (отношение количества мутантов оператора s , уби-
тых (выявленных) тестом t , к общему количеству мутантов оператора s ).
Затем для каждого теста Tt∈ вычислялась ценность путем суммирования
всех значений ),( tsms . Приоритезация по общему покрытию операторов с
учетом FEP сортирует тесты в порядке убывания полученных значений
ценности. Из-за высокой стоимости получения значений FEP данный метод
приоритезации дороже методов, базирующихся только на покрытии опера-
торов. Однако, если данный метод будет достаточно эффективным, то
станет целесообразным поиск приемлемых по стоимости методов аппрок-
симации значений FEP.
T6. Приоритезация по дополнительному покрытию операторов с
учетом FEP. Аналогично трансформации приоритезации по общему покры-
тию операторов в приоритезацию по дополнительному покрытию транс-
формируем предыдущий метод с учетом FEP. В новом методе после плани-
рования теста t понизим вес всех других тестов, покрывающих операторы,
покрытые данным тестом. Затем данный процесс повторяется до полного
упорядочивания тестов.
Группа 3. Методы, работающие на уровне функций.
T7. Приоритезация по общему покрытию функций аналогична при-
оритезации по общему покрытию операторов, но оперирует на уровне
функций.
T8. Приоритезация по дополнительному покрытию функций анало-
гична приоритезации по дополнительному покрытию операторов, но опери-
рует на уровне функций.
T9. Приоритезация по общему покрытию функций с учетом FEP
аналогична приоритезации по общему покрытию операторов с учетом FEP,
но оперирует на уровне функций.
T10. Приоритезация по дополнительному покрытию функций с
учетом FEP аналогична приоритезации по дополнительному покрытию
операторов с учетом FEP, но оперирует на уровне функций.
А.Г. Малышевский
ISSN 1681–6048 System Research & Information Technologies, 2006, № 4 22
T11. Приоритезация по общему покрытию функций с использова-
нием FI. Присутствие ошибок не является равновероятным в каждой функ-
ции. Уровень склонности к содержанию ошибок (fault proneness) может
быть ассоциирован с измеряемыми атрибутами программного кода [12, 13].
Для того чтобы отразить уровень склонности к ошибкам, используется ин-
декс ошибок FI (fault index), базирующийся на методе главных компонент
[14]. Определение значений FI для каждой функции требует вычисления
значений FI для базовой и для новой версий, а также их сравнения. Таким
образом, каждой функции присваивается абсолютное значение FI, показы-
вающее ее склонность к содержанию ошибок с учетом сложности модифи-
каций этой функции. При полученных значениях FI приоритезация по об-
щему покрытию FI выполняется подобно приоритезации по общему
покрытию функций. Для каждого теста просуммируем значения FI каждой
функции, покрытой этим тестом. Затем упорядочим тесты в порядке убыва-
ния этих сумм. Таким образом тесты планируются согласно покрытию ими
склонных к ошибкам функциям.
T12. Приоритезация по дополнительному покрытию FI подобна
приоритезации по дополнительному покрытию функций, за исключением
того, что ценность каждого теста вычисляется как сумма значений FI до-
полнительно покрытых функций.
T13. Приоритезация по общему покрытию функций с применением
FI и FEP. Используя приближенную оценку потенциала выявления ошибок
и оценку уровня склонности к ошибкам, что дает большую скорость выяв-
ления ошибок, мы применили приоритезацию по общему покрытию функ-
ций с учетом FI. В случаях, когда два и более теста имеют равные значения
ценности, применили приоритезацию по общему покрытию функций с уче-
том FEP.
T14. Приоритезация по дополнительному покрытию функций с
применением FI и FEP. Чтобы свести метод T13 к данному, используем
приоритезацию по дополнительному покрытию функций с учетом FI. В слу-
чаях, когда два и более теста имеют равные значения ценности, сортируем
их по общему покрытию функций с учетом FEP.
ЭМПИРИЧЕСКИЕ ИССЛЕДОВАНИЯ
Для изучения возможности применения приоритезации на практике прове-
дено несколько эмпирических исследований с целью получения ответов на
такие вопросы: способна ли приоритезация, ориентированная на заданную
версию программы, увеличить скорость выявления ошибок и как сравнива-
ются методы приоритезации низкой гранулярности (уровень операторов) с
методами крупной гранулярности (уровень функций) с точки зрения скоро-
сти выявления ошибок, а также может ли использование оценки склонности
к ошибкам повысить эффективность методов приоритезации.
Эффективность приоритезации и ее измерение
Для анализа эффективности приоритезации необходимо оценить ее количе-
ственно. Введем метрику, оценивающую скорость выявления ошибок набо-
Приоритезация тестов в регрессивном тестировании
Системні дослідження та інформаційні технології, 2006, № 4 23
ром тестов. Назовем ее «взвешенное среднее процента выявленных ошибок»
APFD (weighted average of the percentage of faults detected). Метрика APFD
измеряет скорость выявления ошибок в интервале (0...100). Чем больше зна-
чение метрики, тем быстрее выявляются ошибки.
Для иллюстрации данной метрики рассмотрим программу с десятью
ошибками и набором из пяти тестов (A, B, C, D, E). Рис. 1, а демонстрирует
способность данных тестов выявлять эти ошибки. Допустим, что мы размес-
тим тесты в порядке A-B-C-D-E, формируя таким образом приоритезиро-
ванный набор тестов T1. Рис. 1, б показывает процент выявленных ошибок
относительно уже выполненной части набора тестов T1. После выполнения
теста A выявлены две ошибки из десяти. Таким образом 20% ошибок выяв-
лены после выполнения 20% набора тестов T1. После выполнения теста B
две другие ошибки выявлены, и таким образом 40% ошибок выявлены после
использования 40% набора тестов. На рис. 1, б пространство в прямоуголь-
никах с прерывистыми линиями показывает взвешенное среднее процента
выявленных ошибок в течение выполнения соответствующей части набора
тестов. Сплошные линии, связывающие углы прямоугольников, интерполи-
руют прирост процента выявленных ошибок. Эта интерполяция — поправка
гранулярности (когда только небольшое количество тестов составляет их
набор). Чем больше набор тестов, тем меньше эта поправка. Таким образом,
площадь под кривой будет метрикой APFD приоритезированного набора
тестов. В данном примере APFD равна 50%. Рис. 1, в отражает ситуацию,
Рис. 1. Пример метрики APDF
xxxE
xD
xxxxxxxC
xxxxB
xxA
10987654321
Ошибка
Тест
xxxE
xD
xxxxxxxC
xxxxB
xxA
10987654321
Ошибка
Тест
20
40
60
80
0,2 0,4 0,6 0,8 1,00
0
100
П
ро
це
нт
вы
яв
ле
нн
ы
х
ош
иб
ок
Выполненная часть набора тестов
Порядок тестов: A-B-C-D-E
Площадь = 50%
20
40
60
80
0,2 0,4 0,6 0,8 1,00
0
100
П
ро
це
нт
вы
яв
ле
нн
ы
х
ош
иб
ок
Выполненная часть набора тестов
Порядок тестов: C-E-B-A-D
Площадь = 84%
a б
20
40
60
80
0,2 0,4 0,6 0,8 1,00
0
100
П
ро
це
нт
вы
яв
ле
нн
ы
х
ош
иб
ок
Выполненная часть набора тестов
Порядок тестов: E-D-C-B-A
Площадь = 64%
в г
А.Г. Малышевский
ISSN 1681–6048 System Research & Information Technologies, 2006, № 4 24
когда порядок тестов изменился на E-D-C-B-A, получив набор тестов с бо-
лее быстрым выявлением ошибок, чем набор T1 с соответствующим APFD,
равным 64%. На рис. 1, г показано влияние использования приоритезиро-
ванного набора тестов T3 в порядке C-E-B-A-D. Данный порядок (в этом
примере оптимальный) раньше других выявляет большинство ошибок
(APFD равен 84%).
Метрика APFD вычисляется по формуле
nnm
TF
APFD
m
i
i
2
11 1 +−=
∑
= и вы-
ражается в процентах, где n — количество тестов в наборе; m — количест-
во ошибок, выявленных данным набором тестов; iTF — порядковый номер
теста (начинающийся с единицы) в упорядоченном наборе, первым вы-
явившим i -ю ошибку.
Инструментарий эмпирических исследований
В роли объектов исследований использованы восемь программ на языке Си.
Семь из них в виде наборов тестов и версий с внесенными ошибками подго-
товлены исследователями из Siemens Corporate Research для изучения спо-
собности к выявлению ошибок при использовании критериев покрытия по
потокам управления (control-flow) и по потокам данных (data-flow). Мы на-
зовем их «Siemens-программы». Восьмая программа, space, разработана
для ЕКА.
Siemens-программы решают следующие задачи: tcas предупреждает
столкновение самолетов, schedule2 и schedule планирует с использованием
приоритетов, tot_info вычисляет некоторую статистику, print_tokens и
print_tokens2 — лексические анализаторы и replace осуществляет поиск по
шаблону и замену. Используя прием разделения категорий, для каждой про-
граммы исследователи в Siemens создали пул тестов, состоящий из функ-
циональных тестов. Затем они вручную добавили к данному пулу разрабо-
танные структурные тесты, чтобы гарантировать покрытие как минимум 30
тестами каждого оператора, ребра и du-пары (если это возможно теоре-
тически) в базовой версии программы или ее графа потоков управления.
Для каждой программы путем модификации кода в базовой версии исследо-
ватели создали версии, содержащие ошибки. В большинстве случаев они
изменили единственную строку кода, и только в нескольких случаях моди-
фицировали от двух до пяти строк кода. Целью было внедрение макси-
мально реалистичных ошибок. Исследователи сохранили только ошибки,
выявляемые, как минимум, тремя и, как максимум, 350-ю тестами в со-
ответствующем пуле тестов.
Программа space — это интерпретатор языка для задания конфигура-
ции массива ADL. Эта программа содержит 35 версий, каждая из которых
имеет единственную ошибку. Все эти ошибки реальные и были обнаружены
либо в ходе разработки программы, либо в процессе использования ее в ис-
следованиях. Для данной программы создан тестовый пул за две стадии.
Изначально пул состоял из 10 000 случайным образом сгенерированных тес-
Приоритезация тестов в регрессивном тестировании
Системні дослідження та інформаційні технології, 2006, № 4 25
тов, созданных Vokolos и Frankl. Затем новые тесты добавлялись до тех пор,
пока каждое исполняемое ребро в графе потоков управления программой не
было покрыто как минимум 30 тестами. В результате получен пул с 13585
тестами. При создании наборов тестов для данных программ использова-
лись пулы тестов для базовых версий и информация о покрытии элементов
программы тестами в этих пулах с целью генерирования 1000 адекватных
покрытию ветвлений наборов тестов для каждой программы. В наших ис-
следованиях для каждой программы случайным образом выбрали 50. Тре-
бовались программы с разным количеством ошибок. Каждая программа
изначально обеспечивалась корректной базовой версией и несколькими вер-
сиями, содержащими по одной ошибке (версии 1-го порядка). Среди этих
версий идентифицированы все версии, не мешающие друг другу, другими
словами, все ошибки, которые могут быть внесены в базовую версию и од-
новременно сосуществовать. Затем были созданы версии более высокого
порядка путем комбинирования не мешающих друг другу версий 1-го по-
рядка. Чтобы увеличить достоверность наших экспериментов, для каждой
программы было получено одинаковое количество версий (29) со случай-
ным числом ошибок в каждой.
Инструментарий для приоритезации и анализа. С целью получения
информации о покрытии операторов и функций тестами, о графах потоков
управления и об оценках мутаций использовались те же инструменты, что и
в работах [2, 4, 15]. Были реализованы методы приоритезации (табл. 1).
Чтобы получить информацию о склонности функций содержать ошиб-
ки, использовались три инструмента [16, 17]: измеряющий исходный
программный код для вычисления метрики сложности кода, сам генератор
значения склонности кода к ошибкам и сравнивающий инструмент для
оценки каждой версии относительно базовой.
Далее детально опишем эмпирические исследования и их результаты.
На рис. 2 показана диаграмма размаха объединенных данных всех программ
(«all program total») и отдельные диаграммы для каждой из них, демонстри-
руюшие распределение значений APFD для 14 методов приоритезации
(табл. 1).
Приоритезация, ориентированная на заданную версию. Первое ис-
следование рассматривает, может ли приоритезация, ориентированная на
заданную версию, улучшить способность ускорять выявление ошибок набо-
рами тестов. Предполагаем, что различия в гранулярности могут вызвать
значительные различия в выявлении ошибок, поэтому нами проведен экспе-
римент, состоящий из двух частей: первая — методы на уровне операторов
и вторая — методы на уровне функций. Обе части выполнены в одинаковом
факториальном дизайне (исследованы все комбинации на всех уровнях всех
факторов). Факторами являлись программа и метод приоритезации. В каж-
дой программе было восемь уровней с 29 версиями и 50 наборами тестов.
Внутри методов — четыре уровня. В первой части рассматривались методы
st-total, st-addtl, st-fep-total и st-fep-addtl, а во второй — fn-total, fn-addtl, fn-
fep-total и fn-fep-addtl. Методы optimal и random [2] статистически значимо
отличались от остальных методов, поэтому в данных экспериментах они
А.Г. Малышевский
ISSN 1681–6048 System Research & Information Technologies, 2006, № 4 26
исключены из статистического анализа (представлены здесь лишь как точки
отсчета).
Рис. 2. Диаграммы размаха значений APFD для всех программ (горизонтальные
оси — методы (табл. 1), вертикальные — значения APFD)
replace
a
schedule
b
schedule2
c
space
d
tcas
e
print_tokens
f
print_tokens2
g
tot_info
h
all programs
i
Приоритезация тестов в регрессивном тестировании
Системні дослідження та інформаційні технології, 2006, № 4 27
Проведен дисперсионный анализ (ANOVA) для изучения основного
влияния факторов и взаимодействия между ними. В верхней половине
табл. 2 приведены результаты первой части эксперимента при рассмотрении
всех программ. Результаты показывают, что имеется достаточно статисти-
ческих оснований для отклонения нулевой гипотезы: средние значения
APFD, полученные различными методами, на уровне операторов отличают-
ся. Однако из анализа видно, что существует значительная взаимосвязь ме-
жду методами и программами. Различия между методами не идентичны для
каждой из программ. Таким образом, их необходимо осторожно интерпре-
тировать в индивидуальном порядке. Средние значения APFD ранжировали
методы, дисперсионный анализ оценил, различались ли методы, а процедура
множественного сравнения, использующая критерий Бонферрони, численно
оценила различия методов. В нижней половине табл. 2 приведены результа-
ты для методов на уровне операторов. Методы с одинаковой буквой груп-
пирования не имеют статистически значимых различий с точки зрения мет-
рики APFD. Например, в st-fep-total среднее значение больше, чем в st-total,
но они сгруппированы вместе, так как между ними нет статистически зна-
чимых различий. С другой стороны, st-fep-addtl — метод, использующий
FEP-информацию лучше, чем другие методы, и данные различия являются
статистически значимыми.
Т а б л и ц а 2 . Дисперсионный анализ и критерий Бонферрони, методы
уровня операторов, все программы
Источник Количество
степеней свободы Средний квадрат F P > F
Эффект 31 146227,87 397,72 0,0001
Ошибка 31836 367,66
Минимальное значимое различие 0,80
Группа Среднее значение Метод
A 78,88 st-fep-addtl
B 76,99 st-fep-total
B 76,30 st-total
C 74,44 st-addtl
В табл. 3 показаны аналогичные результаты дисперсионного анализа и
критерия Бонферрони для второй части эксперимента. Эффекты взаимодей-
ствия между методами и программами являлись значимыми для данных ме-
тодов на уровне функций. Результаты также показывают статистически зна-
чимые различия между методами. Методы заняли порядок, идентичный их
двойникам на уровне операторов: первый — fn-fep-addtl, второй — fn-fep-
total, третий — fn-total и последний — fn-addtl. Однако в данном случае три
наилучших метода не имели статистически значимого различия между со-
бой. Как минимум, данный результат наводит на мысль о том, что метод,
применявшийся для приближенной оценки значений FEP на уровне функ-
ций может не быть таким же эффективным, как метод для приближенной
А.Г. Малышевский
ISSN 1681–6048 System Research & Information Technologies, 2006, № 4 28
оценки этих значений на уровне операторов. Чтобы определить, обобщается
ли данный результат и можно ли найти более эффективные методы оценки
FEP на уровне функций, необходимы дальнейшие исследования.
Т а б л и ц а . 3 . Дисперсионный анализ и критерий Бонферрони, методы
уровня функций, все программы
Источник Количество
степеней свободы Средний квадрат F P > F
Эффект 31 169080,15 436,93 0,0001
Ошибка 31836 386,96
Минимальное значимое различие 0,82
Группа Среднее значение Метод
A 75,59 fn-fep-addtl
A 75,48 fn-fep-total
A 75,09 fn-total
B 71,66 fn-addtl
Влияние гранулярности. Во втором исследовании сравниваются ме-
тоды приоритезации с мелкой и крупной гранулярностью. Анализ данных
показал, что гранулярность имеет влияние на значения APFD. Это очевидно,
если посмотреть на диаграммы размаха, где для всех случаев средние значе-
ния APFD для методов на уровне функций были меньше, чем для соответст-
вующих методов на уровне операторов. Например, среднее значение APFD
для fn-fep-addtl равно 75,59, но для st-fep-addtl — 78,88. Каждый метод на
уровне функций имеет меньшее значение APFD, чем каждый метод на
уровне операторов. Выполнен эксперимент (эксперимент 2), подобный опи-
санным выше. Проведены сравнения между следующими парами методов:
(st-total, fn-total), (st-addtl, fn-addtl), (st-fep-total, fn-fep-total) и (st-fep-addtl, fn-
fep-addtl). Для данных четырех пар методов различные уровни гранулярно-
сти имели основное влияние на значение APFD. Таким образом, несмотря на
различное ранжирование в обеих частях первого эксперимента, статистиче-
ской значимости было достаточно для подтверждения более высокой эф-
фективности методов на уровне операторов по сравнению с методами на
уровне функций.
Использование информации о склонности кода к ошибкам —
третье исследование, направленное на увеличение скорости выявления
ошибок с учетом оценки склонности кода к ошибкам. Предполагалось, что
использование такой информации в методах приоритезации увеличило бы
их эффективность. Разработан эксперимент (эксперимент 3) для изучения
данной гипотезы на уровне функций. Он подобен второй части первого ис-
следования за исключением добавления четырех новых методов: fn-fi-total,
fn-fi-addtl, fn-fi-fep-total и fn-fi-fep-addtl. Дисперсионный анализ полученных
в этом эксперименте данных (табл. 4) показал, что имела место статистиче-
ская значимость различия в эффективности этих методов. Результаты кри-
терия Бонферрони оказались неожиданными. Несмотря на то, что метод fn-
fi-fep-addtl имел наибольшее среднее значение APFD, он не отличался ста-
Приоритезация тестов в регрессивном тестировании
Системні дослідження та інформаційні технології, 2006, № 4 29
тистически значимо от fn-fep-addtl. Это означает что комбинация метрик
FEP и FI (склонности к ошибкам) не увеличила эффективности методов с
точки зрения метрики APFD. Отсутствие значимых различий имело также
место и в других случаях, где использовалась оценка склонности к ошибкам,
что произошло с такими парами соответствующих методов, как fn-fi-fep-
total и fn-fep-total, fn-fi-total и fn-total, а также fn-fi-addtl и fn-addtl.
Т а б л и ц а 4 . Дисперсионный анализ и критерий Бонферрони, все мето-
ды приоритезации на уровне функций, все программы
Источник Количество
степеней свободы Средний квадрат F P > F
Эффект 63 166395,24 440,71 0,0001
Ошибка 63736 377,59
Минимальное значимое различие 0,96
Группа Среднее значение Метод
A 76,34 fn-fi-fep-addtl
A B 75,92 fn-fi-fep-total
A B 75,63 fn-fi-total
A B 75,59 fn-fep-addtl
A B 75,49 fn-fep-total
B 75,09 fn-total
C 72,62 fn-fi-addtl
C 71,66 fn-addtl
Итак, возможно, примененные методы оценивания FI не улучшили эф-
фективность предложенных методов приоритезации. Такие результаты про-
тиворечат как нашим ожиданиям, так и результатам ранее опубликованных
исследований [16]. Распределение ошибок в программах могло быть одной
из возможных причин этого: иногда версии программ содержали только по
единственной ошибке в программном коде. В таких случаях значение мет-
рики FI сводилось к простейшему критерию: изменилась ли данная функ-
ция, снизив способность быть индикатором склонности к ошибкам. Хотя эта
гипотеза требует дальнейших исследований, можно предположить, что от-
носительная польза методов приоритезации для регрессивного тестирования
зависит от свойств тестируемой программы, поэтому необходимо прогнози-
ровать эффективность того или иного метода приоритезации в каждой кон-
кретной ситуации.
Сравнительный анализ. Для построения общей картины всех рас-
смотренных методов приоритезации использовались дисперсионный анализ
и критерий Бонферрони для всех методов, включая optimal и random
(табл. 5). Как и ожидалось, дисперсионный анализ показал значительные
различия между методами, а критерий Бонферрони сгруппировал их, под-
тверждая наши исследования. Стало очевидно: метод optimal значительно
лучше любого другого метода. Это указывает на то, что методы приоритеза-
А.Г. Малышевский
ISSN 1681–6048 System Research & Information Technologies, 2006, № 4 30
ции могут быть улучшены. Однако все методы превзошли случайное упоря-
дочивание. Другое наблюдение: некоторые методы на уровне функций бо-
лее эффективны по сравнению с методами на уровне операторов.
Т а б л и ц а 5 . Дисперсионный анализ и критерий Бонферрони, все мето-
ды, все программы
Источник Количество
степеней свободы Средний квадрат F P > F
Эффект 111 190818,46 529,84 0,0001
Ошибка 111426 360,14
Минимальное значимое различие 1,039
Группа Среднее значение Метод
A 94,24 optimal
B 78,88 st-fep-addtl
C 76,99 st-fep-total
D C 76,34 fn-fi-fep-addtl
D C 76,30 st-total
D E 75,92 fn-fi-fep-total
D E 75,63 fn-fi-total
D E 75,59 fn-fep-addtl
D E 75,49 fn-fep-total
F E 75,09 fn-total
F 74,44 st-addtl
G 72,62 fn-fi-addtl
G 71,66 fn-addtl
H 59,73 random
ВЫВОДЫ
Результаты показывают статистически значимые различия в эффективности
методов приоритезации с точки зрения влияния на скорость выявления
ошибок. Конечно, отличия в скорости выявления ошибок могут и не иметь
практического значения. Например, если время выполнения всех тестов яв-
ляется небольшим, данные отклонения могут быть незначительными. Одна-
ко, когда такое время достаточно большое, разница может стать весьма зна-
чительной. В данной работе эмпирически исследованы возможности
увеличения скорости выявления ошибок наборами тестов нескольких мето-
дов приоритезации. Наши исследования ориентированы на приоритезацию
заданной версии программы, для которой ранжируются тесты и измеряется
скорость выявления ошибок. Описанные исследования имеют несколько
практических результатов. Методы могут увеличить скорость выявления
ошибок. Важен тот факт, что методы на уровне функций могут быть эффек-
тивными, кроме того, они дешевле и для них проще получить информацию.
Однако методы на уровне операторов могут обеспечить более высокий уро-
Приоритезация тестов в регрессивном тестировании
Системні дослідження та інформаційні технології, 2006, № 4 31
вень эффективности, и потому предпочтительней в случае большой стоимо-
сти задержек в выявлении ошибок. С другой стороны, наши исследования о
внедрении в процесс приоритезации информации о склонности к ошибкам
показали, что, вопреки ожиданиям, внедрение этой информации существен-
но не улучшило эффективности приоритезации, следовательно, еще рано
применять такой подход на практике.
Результаты подсказывают несколько направлений будущих исследова-
ний. В первую очередь, необходимо обобщить полученные результаты. Раз-
личия в эффективности рассмотренных методов приоритезации требуют
дальнейших исследований факторов, влияющих на их эффективность. Было
бы полезно разработать методы прогнозирования, которые для заданной
программы, набора тестов и модификаций могли бы выбрать самый эф-
фективный метод приоритезации. Необходимо изучить альтернативные це-
ли приоритезации и альтернативные измерения ее эффективности. И, нако-
нец, необходим поиск более эффективных методов приоритезации и
методов аппроксимации оценок FEP и FI. Цель данной работы — создать
для разработчиков программного обеспечения методы улучшения процессов
регрессивного тестирования.
Автор благодарит Г. Ротермела и С. Элбаума за участие в проведении
описанных исследований.
ЛИТЕРАТУРА
1. Ghezzi C., Jazayeri M., Mandrioli D. Fundamentals of Software Engineering. —
Upper Saddle River: Prentice Hall, 1991. — 573 p.
2. Rothermel G., Untch R., Chu C., Harrold M.J. Test case prioritization: an em-
pirical study // In Proceedings of the International Conference on Software Main-
tenance. — 1999. — P. 179–188.
3. Wong W., Horgan J., London S., Agrawal H. A study of effective regression testing
in practice // In Proceedings of the Eighth International Symposium on Software
Reliability Engineering. — 1997. — P. 230–238.
4. Rothermel G., Untch R.H., Chu C., Harrold M.J. Test case prioritization // IEEE
Transactions on Software Engineering. — 2001. — 27, № 10. — Р. 929–948.
5. Jones J.A., Harrold M.J. Test-suite reduction and prioritization for modified condi-
tion/decision coverage // In Proceedings of the International Conference on Soft-
ware Maintenance. — 2001. — Р. 92–101.
6. Srivastava A., Thiagarajan J. Effectively prioritizing tests in development environ-
ment // In Proceedings of the International Symposium on Software Testing and
Analysis. — 2002. — Р. 97–106.
7. Kim J.-M., Porter A. A history-based test prioritization technique for regression test-
ing in resource constrained environments // In Proceedings of the International
Conference on Software Engineering. — 2002. — Р. 119–129.
8. Rothermel G., Harrold M.J. Analyzing regression test selection techniques // IEEE
Transactions on Software Engineering. — 1996. — 22, № 8. — Р. 529–551.
9. Avritzer A., Weyuker E.J. The automatic generation of load test suites and the
assessment of the resulting software // IEEE Transactions on Software Engineer-
ing. — 1995. — 21, № 9. — Р. 705–716.
А.Г. Малышевский
ISSN 1681–6048 System Research & Information Technologies, 2006, № 4 32
10. Voas J. PIE: A dynamic failure-based technique // IEEE Transactions on Software
Engineering. — 1992. — Р. 717–727.
11. DeMillo R.A., Lipton R.J., Sayward F.G. Hints on Test Data Selection: Help for the
Practicing Programmer // Computer. — 1978. — 11, № 4. — Р. 34–41.
12. Khoshgoftaar T.M., Munson J.C. Predicting software development errors using com-
plexity metrics // Journal on Selected Areas in Communications. — 1990. — 8,
№ 2. — Р. 253–261.
13. Munson J.C. Software measurement: Problems and practice // Annals of Software
Engineering. — 1995. — 1, № 1. — Р. 255–285.
14. Elbaum S.G., Munson J.C. Code churn: A measure for estimating the impact of code
change // In Proceedings of the International Conference on Software Mainte-
nance. — 1998. — Р. 24–31.
15. Elbaum S., Malishevsky A., Rothermel G. Prioritizing test cases for regression testing
// In Proceedings of the International Symposium on Software Testing and
Analysis. — 2000. — Р. 102–112.
16. Munson J.C., Elbaum S.G., Karcich R.M., Wilcox J.P. Software risk assessment
through software measurement and modeling // In Proceedings of the IEEE Aero-
space Conference. — 1998. — Р. 137–147.
17. Elbaum S.G., Munson J.C. Software evolution and the code fault introduction
process // Empirical Software Engineering Journal. — 1999. — 4, № 3. —
Р. 241–262.
Поступила 04.04.2006
|
| id | journaliasakpiua-article-154653 |
| institution | System research and information technologies |
| keywords_txt_mv | keywords |
| language | Russian |
| last_indexed | 2025-07-17T10:24:20Z |
| publishDate | 2019 |
| publisher | The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" |
| record_format | ojs |
| resource_txt_mv | journaliasakpiua/46/e97ffd5dfe9fb423b4ca4833bd5aa146.pdf |
| spelling | journaliasakpiua-article-1546532019-01-18T15:10:28Z Prioritizing test cases for regression testing Приоритезация тестов в регрессивном тестировании Пріоритезація тестів у регресивному тестуванні Malishevsky, A. G. Prioritization (test ranking) in the regression testing is considered with the purpose of increasing the rate of fault detection in software during execution of a test suite. New prioritization techniques with higher effectiveness and lower prioritization costs have been developed. Also, comparative evaluation of the effectiveness of both new and previously developed prioritization methods has been made. Рассмотрена приоритезация (ранжирование тестов) в регрессивном тестировании для ускорения выявления ошибок в программном обеспечении при выполнении набора тестов. Приведены новые методы приоритезации для повышения эффективности и понижения затрат в случае их применения. Проведена оценка сравнительной эффективности как новых, так и известных из литературы методов. Розглянуто пріоритезацію (ранжування тестів) у регресивному тестуванні для пришвидшення виявлення помилок у програмному забезпеченні при виконанні набору тестів. Наведено нові методи пріоритезації для підвищенння їхньої ефективності та зниження витрат при застосуванні. Проведено порівняльну оцінку ефективності як нових, так і відомих з літератури методів. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2019-01-18 Article Article application/pdf https://journal.iasa.kpi.ua/article/view/154653 System research and information technologies; No. 4 (2006); 16-32 Системные исследования и информационные технологии; № 4 (2006); 16-32 Системні дослідження та інформаційні технології; № 4 (2006); 16-32 2308-8893 1681-6048 ru https://journal.iasa.kpi.ua/article/view/154653/154257 Copyright (c) 2021 System research and information technologies |
| spellingShingle | Malishevsky, A. G. Пріоритезація тестів у регресивному тестуванні |
| title | Пріоритезація тестів у регресивному тестуванні |
| title_alt | Prioritizing test cases for regression testing Приоритезация тестов в регрессивном тестировании |
| title_full | Пріоритезація тестів у регресивному тестуванні |
| title_fullStr | Пріоритезація тестів у регресивному тестуванні |
| title_full_unstemmed | Пріоритезація тестів у регресивному тестуванні |
| title_short | Пріоритезація тестів у регресивному тестуванні |
| title_sort | пріоритезація тестів у регресивному тестуванні |
| url | https://journal.iasa.kpi.ua/article/view/154653 |
| work_keys_str_mv | AT malishevskyag prioritizingtestcasesforregressiontesting AT malishevskyag prioritezaciâtestovvregressivnomtestirovanii AT malishevskyag príoritezacíâtestívuregresivnomutestuvanní |