======MuJava : An Automated Class Mutation System======

Yu-Seung Ma, Jeff Offutt, and Yong Rae Kwon. 2005. MuJava: an automated class mutation system: Research Articles. Softw. Test. Verif. Reliab. 15, 2 (June 2005), 97-133. DOI=10.1002/stvr.v15:2 http://dx.doi.org/10.1002/stvr.v15:2

=====Изложение статьи=====
Рассматривается такое понятие, как <<Мутационное тестирование>>.
Мутационное тестирование измеряет эффективность тестов для ПО.
Суть мутационного тестирования в том, что к исходная программа
незначительно изменяется (получается т.н. <<мутант>>), после этого прогоняются уже существующие тесты, и,
если некоторый тест различает исходную программу и мутанта, значит он
эффективен в нахождении ошибок в программе. Действительно --- это значит,
что такой тест как раз и нацелен на проверку ошибочного изменения программы
при получении мутанта.

Мутационным оперетором называется правило получения мутанта из исходного кода --- фактически, это
синтаксическое правило изменения части текста программы.

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

Существующие подходы к уменьшению вычислительной стоимости мутационного тестирования условно
делятся на три группы: do fewer (меньше --- пытаться осуществлять меньшее количество
запусков программ-мутантов, по возможности, без потери эффективности тестирования,
простейший случай --- случайная выборка мутантов),
do smarter (умнее --- разделить вычисления по нескольким машинам или пытаться использовать
информацию, полученную между различными запусками мутантов),
do faster (быстрее --- сфокусироваться на максимально быстрой генерации программ-мутантов и их запуске).
Все эти методы были разработаны для традиционных языков программирования и не всегда
применимы к объектно-ориентированным языкам.

Данная статья пытается применить подход do faster к тестированию классов объектно-ориентированного языка.

Для того, чтобы производить мутационное тестирование программ на ОО-языке нужен специфический
набор мутационных операторов, учитывающих ОО-специфику. Такой набор есть, он был разработан ранее, и,
включает в себя, в частности: изменение модификатора доступа, переименование или удаление
перегружающего метода, объявление переменной с типом родительского класса, изменение иодификатора static,
удаление ключевого слова this и другие, связанные с ОО-спецификой.

Мутанты создаются из тестируемой программы посредством применения мутационных операторов
тестирующей системой. Затем добавляются тесты, <<убивающие>> мутантов посредством определения
различного результата работы оригинальной программы и мутанта. В результате получим набор тестов
для покрытия заданного исходного кода.

Инструменты для мутационного тестирования должны принципиально отличаться от таковых для тестирования процедурных программ.
Например, мутационные операторы для обычных языков программирования (не ОО) не меняют объявления типов или структур данных,
однако для ОО-языка это делается и, например, для оператора, изменяющего тип ссылки на совместимый требуется
не только дерево синтаксического разбора исходного кода, но и информация о структуре типов.

Для тестирования Java-программ можно использовать Reflection, поскольку это позволяет динамически получать
информацию о типах, инстанцировать объекты, и т. п. Однако, стандартное API Reflection-a в Java
не позволяет менять поведение программы. Существуют альтернативные реализиции Reflection, имеющие такой функционал,
но выбор конкретной системы может значительно повлияеть на эффективность мутационного тестирования.

Более ранние подходы к мутационному тестированию изменяли исходный код и компилировали его для каждого мутанта. 
Это неэффективно, поэтому в статье предлагается напрямую менять байт-код.

В статье делается краткий обзор фреймворков для изменения байт-кода. В основном они все различаются по
степени вводимых ограничений (некоторые не позволяют удалять методы), проверке на корректность получаемого кода,
легкости использования. Некоторые требуют модифицированную JVM для работы с загрузкой классов, некоторые
независимы от JVM, поскольку написаны на чистой Java.

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

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

Для примера рассматривается мутационный оператор <<замена оператора>> --- например, замена в коде $a+b$ на $a-b$,
$a*b$, $a/b$. В этом месте происходит метамутация --- конструкция заменяется на абстрактное $ArithmeticOperation(a, b)$.
Это корректная синтаксическая замена. Такая функция ArithmeticOperation называется
метапроцедурой --- метапроцедура содержит в себе варианты выполнения операций, которые
она выбирает в зависимости от параметров создания конкретного мутанта.

Рассмотрим еще пример --- изменение числа аргументов при вызове перегруженного метода.
Допустим, есть две перегрузки метода, с 2 и 3 аргументами. Возможна ошибка программиста, который забыл дописать параметр,
поэтому небходимо реализовать мутацию, чтобы удостовериться, что есть тест, который это ловит.
Вместо вызова этого метода вставляется метод, которые принимает объединение множества параметров для каждой из
перегрузок и содержет в себе switch, вызывающий все допустимые варианты перегрузок, а также дефолтный вариант ---
оригинальный вызов. Этот switch зависит от целочисленного параметра, который определяет конкретного мутанта из
множества возможных для данного метамутанта. Таким же образом делается инстацирование класса-потомка вместо родителя.

Структурные мутации --- уже другое дело. Нельзя, например, поменять модификатор доступа посредством switch-case.
Поэтому здесь используются модификации байт-кода. Это позволяет делать такие мутации, как, например, удаление
перегружающего метода.

Итак, MuJava реализовывает мутации, как описано выше. То есть генерацию метамутанта и изменение байт-кода.
Такой подход сравнивается с подходом, в котором каждый мутант генерируется из исходного кода и компилируется
отдельно. Для второго подхода использовался уже существующий инструмент.

===== Результаты =====

Выяснилось, что ускорение в генерации мутантов --- в среднем более, чем в 9 раз. Ускорение исполнения тестов --- в 2 раза.
Причем, для поведенческих мутантов ускорение генерации и исполнения тестов --- в 6-7 раз. Для структурных же мутантов,
среднее ускорение при генерации мутанта --- 44 (время исполнения одинаковое, ибо поведение не меняется).

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

   - http://www.cs.gmu.edu/~offutt/rsrch/papers/mujava.pdf