CSC/ECE 517 Fall 2017/M1754 Mutation Testing

Servo uses the Web Platform Test (WPT) suite for testing, but does not perform an evaluation of the breadth of the tests. The goal of this project is to use techniques from mutation testing to evaluate the performance of the WPT suite when bugs are deliberately introduced into the code base.

The implementation of this project was done by writing python scripts that would modify the source code to generate mutants and run tests on them expecting failures. The scripts would temporarily modify the source codes, call the corresponding tests and revert back to the original code by reversing the changes that were made earlier. This process was repeated for multiple iterations by modifying various parts of the source code in random order.

Introduction

Servo

Servo is a modern, high-performance browser engine designed for both application and embedded use. Servo is a web browser layout engine written in Rustand is currently being developed by Mozilla. The aim of the project is not to create a full browser but is rather to create a highly parallel environment that allows for many components be handled by fine-grained, isolated tasks. [1]

Rust

Rust is an open source, systems programming language sponsored by Mozilla Research. Rust performs the majority of its safety checks and memory management decisions at compile time, so that program’s runtime performance is not impacted. Making it useful in programs with predictable space and time requirements, embedding in other languages, and writing low-level code, like device drivers and operating systems.

Web-platform-tests

The web-platform-tests Project is a W3C-coordinated attempt to build a cross-browser test suite for the Web-platform stack. Writing tests in a way that allows them to be run in all browsers gives browser projects confidence that they are shipping software that is compatible with other implementations, and that later implementations will be compatible with their implementations. This, in turn, gives Web authors/developers confidence that they can actually rely on the Web platform to deliver on the promise of working across browsers and devices without needing extra layers of abstraction to paper over the gaps left by specification editors and implementors.

Mutation Testing

Mutation Testing is a type of software testing where we mutate (change) certain statements in the source code and check if the test cases are able to find the errors.The goal of Mutation Testing is to assess the quality of the test cases which should be robust enough to fail mutant code. This method is also called as a Fault-based testing strategy as it involves creating faults in the program.Faults are introduced into the source code of the program by creating many versions called mutants. Each mutant should contain a single fault, and the goal is to cause the mutant version to fail which demonstrates the effectiveness of the test cases.[2]

Project description

Environment Setup

• Clone the repository from link
• The steps to set up the environment for different OS are mentioned in readme file link.

Install packages

Example, In OSX(homebrew):

brew install automake pkg-config python cmake yasm
pip install virtualenv

Running test after setup

After the setup, make sure that everything works in your machine by building and running tests.

build in release mode:

./mach build --release

run WPT tests:

./mach test -wpt --release

Initial steps

• Implemented a simple mutator as a Python script that finds random uses of && in Servo's code base and replaces them by ||.
• Built the mutated implementation of Servo with ./mach build -r and run it on the WPT test suite with ./mach test-wpt: This produced test failures.
• Introduced test mapping framework to map source files to WPT test.
• Optimized the number of test runs by using test mapping to run only relevant tests for a mutant.
• Automated this process by writing scripts in a new python/servo/mutation directory, and called them from scripts in /etc/ci.
• Mutation test can be ran using either of the following command from the servo directory:

python python/servo/mutation/init.py components/script/dom

or

python etc/ci/mutation_test.py

Subsequent steps

• implement mutations like replacing if statements by if true/if false, duplicating statements, reordering statements, changing arithmetic & atomic string constant.
• improving the performance of the testing, for example randomizing the test order, fast-failing, running tests with faster builds (e.g. ./mach build -d).
• find heuristics for identifying false positives, that is mutations which are expected to have no effect, for example removing logging.
• find search heuristics for identifying mutations that cause no test failures.

Existing Mutation Strategy

• Replace random occurrence of && with ||

Example: Before Mutation:

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

After Mutation:

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

This will produce a bug. When a is true and b is false also when a is false and b is true the value of c will be wrong. If our WPT test catches this bug then we can say mutant is killed. Otherwise mutant has lived.

Mutation Strategies

There will be many strategies to mutate a file, like the existing one. And the strategies will be picked randomly during the execution of the program. Some of the strategies are:

• Replace && to ||
• Make 'if condition' to 'if true'
• Make 'if condition' to 'if false'
• Re-order statements
• Duplicate statements
• Change arithmetic operations.

Mutation Strategy Examples

• The example for this strategy has already been mentioned in the Existing Mutation Strategy section.
• Make 'if condition' to 'if true'

Example: Before Mutation:

   if a == 0 
   {
       c = 1;
   }

After Mutation:

   if true 
   {
       c = 1;
   }

• Make 'if condition' to 'if false'

Example: Before Mutation:

   if a == 0 
   {
       c = 1;
   }

After Mutation:

   if false
   {
       c = 1;
   }

• Re-order statements

Example: Before Mutation:

   int a=6, b=11;
   float c,d;
   c= a/b;
   d= c/a;

After Mutation:

   int a=6, b=11;
   float c,d;
   d= c/a;
   c= a/b;

• Duplicate statements

Before Mutation:

   for (i=0;i<5;i++)
   {
    counter++;
   }
   if (counter%2==0)
   {
    x=x+y;
   }

After Mutation:

   for (i=0;i<5;i++)
   {
    counter++;
    counter++;
   }
   if (counter%2==0)
   {
    x=x+y;
   }

• Change arithmetic operations.

Before Mutation:

   if (counter%2==0)
   {
    x=x+y;
   }

After Mutation:

   if (counter%2==0)
   {
    x=x-y;
   }

Excecution Flow

Design Plan

Strategy Design Pattern

There are multiple strategies for mutating a file. Each strategy has the implementation of its strategy in the mutate_line method. The Mutator picks up random strategy during the execution of the program and mutates the file.

Code snippet

   class Mutator:
       def __init__(self, strategy):
           self._strategy = strategy
       def mutate(self, file_name):
           return self._strategy.mutate_random_line(file_name)

   class Strategy:
       def __init__(self):
           self._replace_strategy = {}
   
       def mutate_random_line(self, file_name):
           line_numbers = []
           for line in fileinput.input(file_name):
               if re.search(self._replace_strategy['regex'], line):
                   line_numbers.append(fileinput.lineno())
           if len(line_numbers) == 0:
               return -1
           else:
               mutation_line_number = line_numbers[random.randint(0, len(line_numbers) - 1)]
               for line in fileinput.input(file_name, inplace=True):
                   if fileinput.lineno() == mutation_line_number:
                       line = re.sub(self._replace_strategy['regex'], self._replace_strategy['replaceString'], line)
                   print line.rstrip()
               return mutation_line_number
   
   
   class AndOr(Strategy):
       def __init__(self):
           Strategy.__init__(self)
           self._replace_strategy = {
               'regex': r'\s&&\s',
               'replaceString': ' || '
           }
   
   
   class IfTrue(Strategy):
       def __init__(self):
           Strategy.__init__(self)
           self._replace_strategy = {
               'regex': r'(?<=if\s)(.*)(?=\s\{)',
               'replaceString': 'true'
           }
   
   
   class IfFalse(Strategy):
       def __init__(self):
           Strategy.__init__(self)
           self._replace_strategy = {
               'regex': r'(?<=if\s)(.*)(?=\s\{)',
               'replaceString': 'false'
           }

Test Plan

The project is about writing a python script to change the source code and run tests. It does not add any functionality to Servo. So there is no scope for testing in this project.

References

<references/> 1. https://en.wikipedia.org/wiki/Servo_(layout_engine)
2. https://www.guru99.com/mutation-testing.html
3. https://github.com/servo/servo
4. https://github.com/servo/servo/wiki/Mutation-testing-project