Kacper Krakowiak

Project Overview

My final year project focused on developing an optimization tool for Sikraken, a C code test case generator, originally developed by Dr Chris Meudec (see Original Sikraken GitHub: SikrakenMainRepository). I implemented a genetic algorithm to find the optimal parameter values for test case generation, significantly improving code coverage and reducing execution time.

Technologies Used

• Python: Core implementation language
• Genetic Algorithms: Evolutionary computation technique
• Concurrent Execution: Parallelized processing for performance
• Sikraken: C code test case generator
• TestCov: Code coverage measurement tool

The Problem

Sikraken is a powerful tool for generating test cases for C programs, but it requires careful parameter tuning. Two critical parameters, $restarts and $tries, control how the generator escapes loops and how many attempts it makes. Finding optimal values for these parameters was previously a manual process.

My Solution

I designed a genetic algorithm that:

• Creates a population of parameter pairs
• Evaluates each pair by running Sikraken/TestCov and measuring code coverage
• Evolves better solutions through selection, crossover, and mutation over iterations
• Uses parallelized execution to significantly reduce optimization time

The algorithm automatically identifies optimal parameter values that maximize code coverage while minimizing execution time.

Challenges & Solutions

• Performance Bottleneck: Running Sikraken and TestCov sequentially was time-consuming. I implemented parallel execution with proper synchronization to achieve significant speedup.
• Resource Conflicts: TestCov had issues with concurrent execution. I implemented a locking mechanism to ensure reliable coverage measurement.
• Parameter Space Exploration: The algorithm needed to efficiently explore a large parameter space. I balanced exploration and exploitation through, selection, crossover, and mutation rates.

Results

The genetic algorithm successfully identified optimal parameter combinations that:

• Increased code coverage to default hard set values
• Reduced the time required to find optimal parameters
• Provided consistent results across different C programs

Performance Comparison: GA vs Random Search

Problem 3 - Genetic Algorithm Results

The genetic algorithm convergence for Problem03, showing coverage improvement over generations.

Problem 3 - Random Search Comparison

Random search results for the same problem, showing less consistent coverage.

Problem 16 - Genetic Algorithm Results

The genetic algorithm convergence for Problem16, demonstrating fast optimization.

Problem 16 - Random Search Comparison

Random search results for Problem16, showing inferior performance compared to GA.

Project Documentation

Below you can find detailed documentations for this project. Click on any document to view it in your browser.

Future Work

This project could be extended by:

• Optimizing additional Sikraken parameters beyond $restarts and $tries

Code Repository

The source code for this project is available on GitHub.