Мутаційне тестування

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

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

Мутаційні тестування проводиться шляхом вибору мутаційних операторів та застосування їх одного за іншим до кожного фрагменту вихідного коду програми. Результат одного застосування мутаційного оператора до програми називається мутантом. Якщо набір тестів здатний виявити зміну (тобто один з тестів не проходить), то мутант називається вбитим. Як правило, мутант відрізняється від вихідної програми невеликим числом мутацій. У вихідній програмі можуть піддаватися мутаціям ділянки коду пов'язані з дефектами (змінюються значення змінних, модифікуються індекси та межі циклів, вносяться мутації в умови). Таким чином, з первісної програми шляхом внесення n числа мутацій отримують k мутантів, n >= k (як мінімум одна мутація на одного мутанта). Якщо сформоване безліч тестових наборів виявляє всі мутації у всіх мутантів, то воно відповідає мутаційному критерію. Якщо тестування вихідної програми на заданій множині тестових наборів не виявило помилок, то програма оголошується коректною. У разі мутаційного тестування важливо створити таке число мутантів, яке б охоплювало всі можливі ділянки прояви помилок. Наприклад, розглянемо наступний фрагмент з програми на С++:

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].

Багато видів мутаційних операторів були досліджені. Наприклад, для імперативних мов наступні оператори можуть бути використанні:

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

Крім того існують оператори для об'єктно-орієнтованих мов[4], оператори для паралельного програмування[5], оператори для структур даних, таких як контейнери[6] та ін.