Differences

This shows you the differences between two versions of the page.

--- mdd:mujava_an_automated_class_mutation_system [2014/06/06 19:35] – created 93.175.9.191
+++ mdd:mujava_an_automated_class_mutation_system [2026/08/29 07:59] (current) – external edit 127.0.0.1
@@ Line 1: / Line 1: @@
+====== 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|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|http://www.cs.gmu.edu/~offutt/rsrch/papers/mujava.pdf]]