Улучшение алгоритмов тестирования: математические подходы в тестировании программного обеспечения

Новые методологии проектирования тестов не всегда появляются одновременно. Значительная часть современных методов тестирования возникла благодаря кропотливой теоретической и экспериментальной работе по адаптации математических моделей. Хотя не обязательно быть математиком, чтобы быть хорошим тестировщиком, понимание теоретической основы методов тестирования может оказаться полезным.

Максимальное покрытие и минимизация количества тестовых случаев

Математическая логика может применяться для оптимизации покрытия кода системы. Давайте рассмотрим простой пример с оператором «if», содержащим две ветви и длинную логическую формулу в условии:

 if ( (& a2) & (!(a2 || a4) ) || a3 ) { # action 1 } else { # action 2 }

Чтобы охватить обе ветви, необходимо понять структуру формулы. Можно задаться вопросом: а что можно сделать? Вы всегда можете протестировать этот фрагмент кода (логическую формулу) полностью, в результате чего получится 16 тестов. Однако это довольно много, и следует приложить усилия к сокращению количества тестов. Количество тестов можно сократить, используя метод модифицированного покрытия условий/решений (MC/DC) (что дает 11-12 тестов). Если охват филиала достаточен для тестирования рисков, нужны только два теста, но непонятно какие.

Чтобы решить эту проблему, к логической формуле можно применить булеву алгебру:

 if( (& a2) & (! (a2 || a4) ) || a3 ) = = ( (& a2) & ( (!a2 || !a4) ) || a3 ) = = ( a1 & a2 & !a2 & !a4 || a3 ) = = 0 || a3 = a3

После преобразования исходной формулы становится очевидным, что на истинное значение действительно влияет только одна переменная a3 . В результате получение тестовых примеров становится проще (один с a3 == false , другой с a3 == false ). Более того, становится очевидным, что код не оптимизирован, так как странно иметь сложное логическое выражение, зависящее только от одной переменной. К сожалению, такие ситуации довольно распространены в действительности, и приведенный пример относительно прост.

В заключение:

• 2 теста, если используется исчерпывающее тестирование

• 2 теста методом MC/DC

• 2 теста, применяется ли покрытие филиалов

  
  

В общем, логические выражения можно упростить (минимизировать) с помощью алгебры, математических методов и алгоритмов. Существует как минимум три подобных метода. Прямые преобразования с использованием булевой алгебры, как объяснялось выше, всегда работают. Можно найти и применить методы минимизации выражений, которые учитывают характеристики конкретной предметной области, опираясь не только на математику и логику, но и на особенности предметной области.

Оптимизация парного тестирования

Метод попарного тестирования предполагает создание тестовых наборов таким образом, что вместо тестирования всех возможных комбинаций входных параметров путем исчерпывающего тестирования (которое может занять много времени и ресурсов), тестовые наборы разрабатываются таким образом, чтобы каждое значение параметра сочеталось с каждым значение остальных тестируемых параметров хотя бы один раз. Это значительно сокращает количество тестовых случаев.

Это хорошо зарекомендовавший себя и часто используемый метод. Однако, к сожалению, этот метод не всегда работает, поскольку системы усложняются. Возникает вопрос: достаточно ли попарного тестирования для тщательного тестирования сложной системы с многочисленными входными параметрами? Этот вопрос заинтриговал многих специалистов по тестированию и исследователей, в том числе Национальный институт стандартов и технологий (NIST) в США.

• Pairwise finds 65-97% of errors
• 3-way finds 89-99% of errors
• 4-way finds 96-100% of errors
• 5-way finds 96-100% of errors
• 6-way finds 100% of errors

Согласно исследованиям, парное тестирование находит ошибки в 65-97% случаев. Если мы начнем комбинировать не пары параметров, а тройки или четверки, т. е. использовать k-way тестирование, мы получим большее количество тестов, но и поймаем больше ошибок.

Например, предположим, что система имеет два параметра по три значения каждый и три параметра по два значения каждый:

• Pairwise: 10 tests with 14% coverage
• 3-way: 18 tests with 25% coverage
• 4-way: 36 tests with 50% coverage
• 5-way: 72 tests with 100% coverage

Вы можете выбрать удовлетворительный уровень тестового покрытия и приемлемое количество тестовых случаев.

Основой парного метода являются ортогональные массивы, содержащие n-кортежи (пары, тройки, четверки и т. д.) значений одинаковое количество раз.

Обычной основой для парного и k-стороннего тестирования является OA(N, V^k, t) , где:

• N — количество строк

• k — количество столбцов

• V — количество различных значений в столбце

• t — сила (t=2 для парных)

  
  

В OA каждый набор из t столбцов включает все t кортежей одинаковое количество раз.

Вместо ортогональных матриц лучше использовать покрывающие матрицы. Эти матрицы отличаются от ортогональных тем, что каждый набор значений встречается хотя бы один раз, а не «одинаковое количество раз». В этом случае тестов немного меньше. При покрывающих матрицах могут возникнуть неправильные тестовые случаи, но в целом процесс тестирования происходит намного быстрее. Таким образом, процесс тестирования существенно упрощается.

CA(N, V^k, t), где:

• N — количество строк
• k — количество столбцов
• V — количество различных значений в столбце
• t — сила (t=2 для парных)

В CA каждый набор из t столбцов включает все t кортежей хотя бы один раз. Использование покрывающих матриц позволяет перейти от парного тестирования к k-стороннему без существенного увеличения количества тестов.

Состояния системы и тестирование изменения состояний системы

Обычно (почти всегда) система имеет более двух состояний: «работает» и «не работает». Рассмотрим часть штатов, имеющих биржевой порядок. Чтобы транзакция была завершена, приказ на покупку или продажу акций должен пройти ряд состояний. Сначала создается заявка, затем ее подтверждает биржа, затем следуют многочисленные мелкие сделки покупки и, наконец, покупается или продается необходимое количество акций. Все состояния биржевого ордера отражаются в торговых системах, и все переходы и состояния, конечно же, должны быть протестированы.

Почти всегда проверяются либо все состояния, либо все переходы, но чаще всего проверяются оба. Полный охват достижим, но это потребует много времени, денег и ресурсов.

Графы и конечные автоматы

Рассмотрим задачу коммивояжера (commi voyager) и алгоритм де Брейна. Достаточно понять, что алгоритм позволяет получить оптимальный или достаточно оптимальный набор коротких путей, которые можно пройти в графе, чтобы полностью его покрыть (строго говоря, можно использовать любой другой алгоритм, реализующий нечто подобное, или изобрести собственный алгоритм).

• Сначала возьмем начальные состояния системы и построим новый граф, вершины которого соответствуют переходам исходного графа.
• Далее покрываем вершины нового графа, т. е. переходы в старом.
• Некоторые пути очевидны и оказываются достаточно короткими (что очень удобно для тестирования состояний и переходов системы).
• Продолжайте строить другие пути. В результате они могут стать слишком длинными (и это нехорошо).

Для анализа ситуации рассмотрим следующий пример:

Есть три тестера. Первый выполнит первое испытание, второй – второе испытание, третий – третье испытание. Первые два выполнят первые два теста довольно быстро, потому что пути короткие (по сравнению с третьим, потому что первые два пути короткие), а вот последний займет очень много времени (поскольку третий путь очень короткий). длинный).

Если применить алгоритм де Брейна, третью последовательность можно «разрезать» на несколько более коротких последовательностей, а выполнение всех тестов можно эффективно распараллелить.

Мы можем получить больше тестов, но в случае параллельного выполнения тестирование завершится намного быстрее, поскольку тесты короче.

Более того, чем больше тестов, тем больше гибкости в их выполнении. Все тесты можно запускать одновременно или удалять неинтересные и менее важные тесты. Более высокие приоритеты могут быть присвоены тестам, проходящим через наиболее важные состояния системы. Существует множество способов использовать результаты алгоритма.

Плюсом является то, что алгоритм не использует предметно-специфичные вещи; он работает с абсолютно абстрактными состояниями и переходами системы.

В этой методике многое зависит от того, как используется алгоритм. В самом крайнем случае тестировщики могут ничего не знать о логике переходов между состояниями. В такой ситуации длинная цепочка переходов состояний будет «разрезана» алгоритмом на несколько коротких. Некоторые из этих цепочек могут оказаться бессмысленными. Поэтому полученные цепочки необходимо оценить на предмет разумности и тех, которые важны и значимы для тестирования. Бессмысленно и неважно, но возможные пути изменения состояний системы могут дать понимание, какая часть системы нуждается в модификации, и будет видно, какая именно часть.

Ключевые выводы можно считать следующими:

• Алгоритмы минимизации логических выражений обеспечивают максимальное тестовое покрытие с минимальными усилиями. Не всегда необходимо использовать алгоритмы минимизации — иногда это пустая трата времени; существуют универсальные подходы.
• Полного покрытия тестированием можно добиться с помощью небольшого набора коротких тестовых примеров, которые легко распараллелить, автоматизировать, являются гибкими и независимыми.
• Анализ статистики использования приложений в реальных условиях позволяет оптимизировать и адаптировать существующие методики тест-дизайна и добиться необходимого тестового покрытия, гарантируя качество приложения.
• Модификация парного тестирования позволяет проводить более глубокое тестирование с большим тестовым покрытием, чем стандартные алгоритмы, и практически с теми же ресурсами.
• Некоторые алгоритмы могут быть эффективны в тех случаях, когда стандартные методы проектирования тестов менее эффективны.
• Есть некоторые проблемы, связанные с неудачами комбинаторных методов проектирования тестов .
• Полученные алгоритмы легко адаптируются к различным системам и не требуют специальных знаний предметной области.

Из мелких недостатков стоит отметить:

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