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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Литература

1. ↑ A Practical System for Mutation Testing: Help for the Common Programmer by A. Jefferson Offutt.
2. ↑ Mutation 2000: Uniting the Orthogonal
3. ↑ P. G. Frankl, S. N. Weiss, and C. Hu. All-uses versus mutation testing: An experimental comparison of effectiveness. Journal of Systems and Software, 38:235-253, 1997.
4. ↑ MuJava: An Automated Class Mutation System by Yu-Seung Ma, Jeff Offutt and Yong Rae Kwo.
5. ↑ Mutation Operators for Concurrent Java (J2SE 5.0) by Jeremy S. Bradbury, James R. Cordy, Juergen Dingel.
6. ↑ Mutation of Java Objects by Roger T. Alexander, James M. Bieman, Sudipto Ghosh, Bixia Ji.