Мутационное тестирование

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

Исторический обзор

Мутационное тестирование было предложено студентом Ричардом Липтоном в 1971 году и было впервые разработано и опубликовано ДеМиллом, Липтоном и Сейвардом. Первая реализация инструмента для мутационного тестирования была создана Тимоти Баддом из Йельского университета в его диссертации (названной «Мутационный анализ») в 1980 году.

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

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

Мутационное тестирование состоит в выборе мутирующих операторов и применения их одного за другим к каждому фрагменту исходного кода программы. Мутирующим оператором называется правило преобразования исходного кода. Результат одного применения мутационного оператора к программе называется мутантом. Если набор тестов способен обнаружить изменение (то есть один из тестов не проходит), то мутант называется убитым. Например, рассмотрим следующий фрагмент из программы на C++:

if (a && b) {
    c = 1;
} else {
    c = 0;
}

Оператор мутации условий заменит && на ||, и создаст следующий мутант:

if (a || b) {
    c = 1;
} else {
    c = 0;
}

Для того, чтобы тест мог убить этого мутанта, необходимо чтобы были выполнены следующие условия:

• Тест должен достигнуть (Reach) мутированного оператора.
• Входные данные теста должны привести к разным состояниям программы-мутанта (Infect) и исходной программы. Например, тест с a = 1 и b = 0 приведет к этому.
• Значение переменной c должно повлиять (Propagate) на вывод программы и быть проверено тестом.

Данные условия вместе называются RIP моделью.

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

Эквивалентные мутанты

Многие мутационные операторы могут привести к эквивалентным программам. Например, рассмотрим следующий фрагмент программы:

int index = 0;
while (…) {
    …; 
    index++;
    if (index == 10) {
        break;
    }
}

Оператор мутации условий может заменить == на >= получая таким образом следующего мутанта:

int index = 0;
while (…) {
    …; 
    index++;
    if (index >= 10) {
        break;
    }
}

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

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

Мутационные операторы

Многие виды мутационных операторов были исследованы. Например, для императивных языков следующие операторы могут быть использованы:

• Удалить оператор программы.
• Заменить каждое логическое выражение на логическую константу «истина» или «ложь».
• Заменить каждую арифметическую операцию на другую. Например, + на *, - или /.
• Заменить каждую логическую операцию на другую. Например, > на >=, == или <=.
• Заменить каждую переменную на другую (из той же области видимости). Переменные должны иметь одинаковые типы.

Кроме того существуют операторы для объектно-ориентированных языков, операторы для параллельного программирования, операторы для структур данных, таких как контейнеры и др.