Research topics for a thesis or an internship

by Martin Monperrus

Are you a KTH student? Read Master's thesis / Bachelor's thesis at KTH with Martin Monperrus

Are you a brilliant international student? Contact me by email


Category Code Analysis
               Feature-guided program debloating
               Mining of common programming mistakes by students for automatic feedback generation
               Just-In-Time Repair of SonarQube Static Warnings
               Binary Retargeting with Neural Machine Translation
               Automatic grafting of easter eggs
Category Program Repair
     Artificial Intelligence for Repair (Sequencer)
               Trace Embeddings for Patch Generation in Program Repair
               Graph Neural Networks for Program Repair
               Automatic Categorization on AI Patches with AST Analysis
               Sequence-to-sequence machine learning for automatic program repair
     Artificial Software Developer on Github (Repairnator)
               Online reinforcement learning for automatic program repair
               Conversational Program Repair Bots
               Automatic repair of unreproducible builds
               Automatic ranking of pull-requests for merging or rejecting
     Generate-and-validate program repair (Astor)
               Deep Learning of variable relationships for automatic program repair
               Automatic Program Repair with Property Based Testing
               Explainable repair templates for Astor
Category Program Hardening
     Chaos Engineering
               Maximum Likelihood Perturbations for Chaos Engineering
               Chaos Engineering for Microservices with Resilience4J
               Self-healing capabilities for Python/Flask Applications
     Webassembly
               Neural decompilation for WebAssembly/WASM
               Fuzzing for WebAssembly
     Randomization
               Preventing cache attacks on AES with blackbox randomization
               Preventing algorithmic DOS attacks with blackbox randomization
               Automatic Randomization of Programs with Neural Networks
Category Commit Analysis
               Automatic Clustering of Code Changes with Maximum Density Clustering
               Automatic Identification of Bug-Fix Commits
               Automatic Identification And Backporting of Vulnerability Fixes
               Automatic Labeling of Commits to Identify Fix Patterns
Category Software Testing
               Automatic Identification of Pseudo-tested Conditions
               Automatic Prioritization of Mutants in Mutation Testing
               Automatic Repair of Flaky Tests
               Automatic Renaming of Test Variables to Improve Maintainability

Category Code Analysis

Feature-guided program debloating

Supervisor: Cesar Soto-Valero, Martin Monperrus, KTH Royal Institute of Technology

Description: One of the fundamental challenges of debloating consists in trimming unused features from an application [3]. There could be several reasons that motivate this approach. For example, the maintenance of unused (or unpopular) features leads to unnecessary costs. Thus, the identification and removal of unneeded features can help product owners to prioritize maintenance efforts [4]. You will the feature space in the program by constructing a static call graph first, and then collecting dynamic traces representing specific executions of it. This approach will allow us to get diverse sets concerning the utilization of the program in distinct user scenarios. Our approach is similar to [2], with the difference that we will identify the features using community graph-based algorithms over the static call graph, and we’ll perform the dynamic analysis automatically through the execution of the test suite of the program. Validation You will our approach by conducting case studies on removing cross-cutting features from real-world Java programs. We’ll compare the programs before and after the debloat w.r.t correctness, size, performance, and reduction of the attack surface.

See also https://www.cesarsotovalero.net/collaborations

  1. Brown, Michael D. and Pande, Santosh “CARVE: Practical Security-Focused Software Debloating Using Simple Feature Set Mappings”. FEAST, 2019.

  2. Xin, et al. “Identifying features of Android apps from execution traces”. MOBILESoft, 2019.

  3. Jiang, et al. “Feature-Based Software Customization: Preliminary Analysis, Formalization, and Methods”. HASE, 2016.

  4. Eder, et al. “Which Features Do My Users (Not) Use?”. ICSME, 2014.

Mining of common programming mistakes by students for automatic feedback generation

Supervisor: Ric Glassey, Martin Monperrus, KTH Royal Institute of Technology

Description: Over years, we have consolidated a dataset of student programs in order to devise to new supporting technology for education. You will analyze this data with automatic mining techniques to identify common programming mistakes by students. This knowledge will then be used to build a system that would automatically propose hints and feedback to future KTH students.

  1. A systematic literature review of automated feedback generation for programming exercises

Just-In-Time Repair of SonarQube Static Warnings

Supervisor: Martin Monperrus, KTH Royal Institute of Technology

Description: SonarQube is very used in industry to statically detect bugs and code smells. We have a system for automatically repairing SonarQube warnings. You will research in the area of just-in-time repair of SonarQube warnings: it is the idea of repairing the warnings that appear in an ongoing pull-request and then to do an automated Github suggestion. You will integrate sonarqube-repair into repairnator and run a live Repairnator instance to repair dozens of Sonarqube warnings live in Travis.

  1. Are Static Analysis Violations Really Fixed? A Closer Look at Realistic Usage of SonarQube. Dataset for OSS organizations

  2. Automatically Generating Fix Suggestions in Response to Static Code Analysis Warnings

Binary Retargeting with Neural Machine Translation

Binary retargeting consists of porting binary code from one platform to another, eg from x89 to arm. Binary retargeting is important for porting old code and maximizing interoperability. In the sister field of decompilation, recent progress has been made with neural machine translation [1,2,3]. In this work, you will explore the use of neural machine translation for binary retargeting.

  1. A Neural-based Program Decompiler

  2. Towards Neural Decompilation

  3. Using recurrent neural networks for decompilation

Automatic grafting of easter eggs

Supervisor: Benoit Baudry, Martin Monperrus, KTH Royal Institute of Technology

Description: Easter eggs in software are unexpected and fun features that are deliberately engineered and hidden in code. Easter eggs bring emotions and bonding to your relation to a software product. For instance, a Tesla car is full of easter eggs [1]. You will study the cultural phenomenon of software easter eggs and set up a code transformation framework to automatically graft easter eggs in arbitrary software.

  1. New Tesla Easter Egg: Monty Python Squashes v10 Bugs!

See also https://github.com/INRIA/spoon/labels/mastersthesis

Category Program Repair

Artificial Intelligence for Repair (Sequencer)

You would commit in project https://github.com/KTH/sequencer.

Trace Embeddings for Patch Generation in Program Repair

Supervision: Zimin Chen, Martin Monperrus (KTH)

Description: To reason about programs one can use source code or/and dynamic traces. Most works in machine learning on programs only use code [1]. However, the usage of traces is a very promising research direction [2,3]. You will invent a new patch generation systems, based on trace embeddings. The work will be done on top of recent works in the field [2,3], for generating patches in Java.

  1. A survey of machine learning for big code and naturalness

  2. Learning Blended, Precise Semantic Program Embeddings (2019)

  3. Learning to Encode and Classify Test Executions (2020)

Graph Neural Networks for Program Repair

Supervision: Zimin Chen, Martin Monperrus (KTH)

Recently, it has been shown that one can use graph neural networks to synthesize code [1]. The key insight is to use self-supervision during learning. This opens up many new possibilities for program repair. The goal of this work is to extend the system in the context of Java programs and to apply it on known Java bugs. The work will be made on top of recent advances on graph neural networks.

  1. Learning to Represent Programs with Graphs

  2. Generative Code Modeling with Graphs arxiv 1805.08490

  3. SequenceR: Sequence-to-Sequence Learning for End-to-End Program Repair

Automatic Categorization on AI Patches with AST Analysis

Supervisor: Martin Monperrus, KTH Royal Institute of Technology

KTH has invented a new system called Sequencer for producing patches with machine learning [1]. Sequencer learns from past diffs using sequence-to-sequence learning. The student will perform a large scale analysis of the Sequencer patches. The experiment will involve the Gumtree AST diff library and will be done on a scientific computing grid.

  1. SequenceR: Sequence-to-Sequence Learning for End-to-End Program Repair

  2. Benchmark of single-line bugs

Sequence-to-sequence machine learning for automatic program repair

Supervisor: Martin Monperrus, KTH Royal Institute of Technology

A lot of automatic bug fixing generation techniques rely on slightly modifying the existing code. The student will devise and evaluate a new repair algorithm that will learn from past diffs, using sequence-to-sequence learning. The planned methodology is as follows: 1) set up a training and evaluation dataset based on diffs 2) devise, implement and assess a new repair algorithm based on this data. The student will perform the experiment by running it on a scientific computing grid.

  1. An Empirical Investigation into Learning Bug-Fixing Patches in the Wild via Neural Machine Translation

  2. SequenceR: Sequence-to-Sequence Learning for End-to-End Program Repair

  3. Benchmark of single-line bugs

Artificial Software Developer on Github (Repairnator)

You would commit in project https://github.com/eclipse/repairnator.

Online reinforcement learning for automatic program repair

Supervisor: Martin Monperrus, KTH Royal Institute of Technology

Description: Repairnator is a program repair bot [1] for continuous integration. Today, it only reacts to failing builds. Instead, we plan to also use passing builds as source of knowledge. The student will work on a version of Repairnator that learns from every build such as all Github commits are used as data points for training a repair system.

  1. Human-competitive Patches in Automatic Program Repair with Repairnator

  2. Smart data structures: an online machine learning approach to multicore data structures

Conversational Program Repair Bots

Supervisor: Martin Monperrus, KTH Royal Institute of Technology

Description: Repairnator is a program repair bot [1,2]. In order to work effectively with developers, development bots must be able to interact with the developers. We imagine conversational systems for pull request explanation: developers would be able to ask questions about the pull request, and the bot would answer to those questions [3]. Such a system can be data-driven, based on the analysis of the millions of similar conversations that have happened in open-source repositories. The system could use a chatbot library such as Rasa [4].

  1. Human-competitive Patches in Automatic Program Repair with Repairnator

  2. https://github.com/eclipse/repairnator/issues/840

  3. Explainable Software Bot Contributions: Case Study of Automated Bug Fixes

  4. https://github.com/RasaHQ/rasa/

Automatic repair of unreproducible builds

Supervisor: Martin Monperrus, KTH Royal Institute of Technology

Description: Achieving reproducible builds is essential for achieving a secure software supply chain. In particular, one must be sure that no malicious actor has injected malware during the build process. The Debian linux distribution has deployed this in the large. However, when a project build process is no reproducible or becomes unstable again, it can be really hard to find the root cause and fix it. You will design, implement and evaluate a system that automatically suggests repair actions for unreproducible build processes.

  1. Automated Localization for Unreproducible Builds (2018)

  2. Debian Reproducible Builds

Automatic ranking of pull-requests for merging or rejecting

Supervisor: Martin Monperrus, KTH Royal Institute of Technology

Description: On Github, certain projects have too many pull requests and the maintainers need a way to order the pull requests. The ranking could be according to their maturity, importance or likelihood to be merged or rejected. You will devise, implement and evaluate an approach for ranking pull-requests based the history of merged and rejected pull-requests.

  1. Wait for it: determinants of pull request evaluation latency on GitHub

  2. Improving the pull requests review process using learning-to-rank algorithms

Generate-and-validate program repair (Astor)

Repository: https://github.com/SpoonLabs/astor

Deep Learning of variable relationships for automatic program repair

Supervisor: Martin Monperrus (KTH Royal Institute of Technology), Matias Martinez (University of Valenciennes)

Description: Most patches don't introduce new variables, they only reuse existing variables and method calls. The student will set up and perform an experiment to use deep learning for mining variables relationships so that snippets can be fitted in the current repair context. The planned methodology is as follows: 1) extract a dataset of variable relations based on existing code 2) apply deep-learning on this data and analyze the results 3) devise, implement and assess a extension of Nopol/Astor to use the mined informatio in particular to adapt program repair ingredients. The student will perform the experiment by running it on a scientific computing grid.

  1. ASTOR: A Program Repair Library for Java

  2. Sorting and Transforming Program Repair Ingredients via Deep Learning Code Similarities

  3. SmartPaste: Learning to Adapt Source Code

Automatic Program Repair with Property Based Testing

Supervisor: Martin Monperrus (KTH Royal Institute of Technology)

Description: In automatic program repair, some patches are incorrect because of the incompleteness of the test cases used as specification [1]. One way to overcome this is to have better tests. Property-based testing is one solution to increase completeness of tests [2]. The student will design and perform a novel experiment on using property based tests for automatic program repair, in the context of the Astor repair framework [3].

  1. Automatic Software Repair: a Bibliography (2017)

  2. In praise of property-based testing

  3. https://github.com/SpoonLabs/astor

Explainable repair templates for Astor

Supervisor: Martin Monperrus (KTH Royal Institute of Technology), Matias Martinez (University of Valenciennes)

Description: In practice, template-based repair is promising, because they are very easy to explain to the developer and they also provide reduced overfitting. The student will design and implement a full-fledged template based system for Astor, based on the latest literature on repair templates. A large scale evaluation will be done on the novel repair benchmarks Bugs.jar and BEARS. we can play with the vocabulary to have pure language based templates and project-specific ones

  1. Explainable Software Bot Contributions: Case Study of Automated Bug Fixes

  2. Revisiting template-based automated program repair

  3. FixMiner: Mining Relevant Fix Patterns for Automated Program Repair

Category Program Hardening

See also https://github.com/KTH/royal-chaos.

Chaos Engineering

Maximum Likelihood Perturbations for Chaos Engineering

Supervision: Long Zhang, Martin Monperrus, KTH Royal Institute of Technology

Description: Chaos Engineering [1] is the discipline of verifying resilience capabilities of software systems in production. Our group is doing research in this field, in the context of Java applications [2]. Today, perturbation models are naive: they are either random or based on enumeration. You will study, design and implement a chaos engineering algorithm where each perturbation is chosen according to a utility function in order to maximize the knowledge gained from each perturbation.

  1. Chaos Engineering (the book)

  2. A Chaos Engineering System for Live Analysis and Falsification of Exception-handling in the JVM

Chaos Engineering for Microservices with Resilience4J

Supervision: Long Zhang, Martin Monperrus, KTH Royal Institute of Technology

Description: Chaos Engineering [1] is the discipline of verifying resilience capabilities of software systems in production. Resilience4J [2] is a notable middleware for microservices and DevOps orginally done by Netflix. You will study, design and implement a chaos engineering framework for Resilience4J.

  1. Chaos Engineering (the book)

  2. https://github.com/resilience4j/resilience4j

  3. A Chaos Engineering System for Live Analysis and Falsification of Exception-handling in the JVM

Self-healing capabilities for Python/Flask Applications

Supervisor: Martin Monperrus, KTH Royal Institute of Technology

Description: Over the last few years, the complexity of web applications has extraordinarily increased, incl. with microservice based architecture. The drawback of this complexity is the growing number of runtime errors. You will design and implement a system that provides self-healing capabilities for Python/Flask web applications. The self-healing techniques will be inspired from [1].

  1. Fully Automated HTML and Javascript Rewriting for Constructing a Self-healing Web Proxy

  2. DjangoChecker: Applying extended taint tracking and server side parsing for detection of context‐sensitive XSS flaws

Webassembly

Neural decompilation for WebAssembly/WASM

A decompiler takes compiled binary code and produces textual source code. Decompilation is an essential step for program comprehension, security analyses, etc. However, it is challenging to write an accurate decompiler (that can retrieve the source code that actually corresponds to the compiled code) and the implementation of decompilers currently relies on the careful, manual design of decompilation rules. Some recent works [1,2,3] have proposed to use machine learning in order to train a decompiler. These works successfully applied this concept to decompile from x86 to C source code. In this work, you will study the topic of decompilation learning for WebAssembly/WASM.

  1. A Neural-based Program Decompiler

  2. Towards Neural Decompilation

  3. Adabot: Fault-Tolerant Java Decompiler

Fuzzing for WebAssembly

Supervision: Javier Arteaga, Martin Monperrus, KTH Royal Institute of Technology

Fuzzing is a very good technique to get behavioral traces of programs. You will work on a fuzzer for WebAssembly. The input is a binary WebAssembly/WASM file, the output is a set of test in Javascript that exercises the WASM code. You will evaluate the fuzzer on a benchmark of WebAssembly programs. This is a heavily technical research topic on top of bleeding-edge WASM technology.

  1. American Fuzzy Loop

  2. https://github.com/phayes/sidefuzz

Randomization

Preventing cache attacks on AES with blackbox randomization

Supervisor: Martin Monperrus, KTH Royal Institute of Technology

Description: The goal of this thesis is to study counter-measures to cache attacks on AES. A cache attack consists of inferring a private key by means of cache observation [1]. Black-box randomization consists of identifying and injecting randomization points in software, without any knowledge of the application domain and implementation choices. The goal of this thesis is to study the usage of black-box randomization for countering cache attacks. The student will devise and perform a scientific experiment in this context. She/he will read the literature, implement the required software for supporting the experiment, design the inclusion criteria for subjects and run the experiment on a scientific computing grid.

  1. Efficient Cache Attacks on AES, and Countermeasures

  2. Correctness Attraction: A Study of Stability of Software Behavior Under Runtime Perturbation

Preventing algorithmic DOS attacks with blackbox randomization

Supervisor: Martin Monperrus, KTH Royal Institute of Technology

Description: The goal of this thesis is to study counter-measures to algorithmic denial of service attacks. An algorithmic DOS consists of a input specifically designed by the attacker to trigger the worst case execution of a program [1]. Black-box randomization consists of identifying and injecting randomization points in software, without any knowledge of the application domain and implementation choices. The goal of this thesis is to study the usage of black-box randomization for countering algorithmic DOS attacks. The student will devise and perform a scientific experiment in this context. She/he will read the literature, implement the required software for supporting the experiment, design the inclusion criteria for subjects and run the experiment on a scientific computing grid.

  1. Denial of Service via Algorithmic Complexity Attacks

  2. Correctness Attraction: A Study of Stability of Software Behavior Under Runtime Perturbation

  3. Slowfuzz: Automated domain-independent detection of algorithmic complexity vulnerabilities

Automatic Randomization of Programs with Neural Networks

Supervisor: Martin Monperrus, KTH Royal Institute of Technology

The fact that programs are executed mostly deterministically is a problem for security [1]. Automatic randomization is one way of overcoming this problem. In this work, we we will explore the use of neural networks, and their ability to generate likely sequences, to synthesize equivalent programs that execute differently. You will use recent libraries from machine learning [2] to learn over big amount of open source code.

  1. The Multiple Facets of Software Diversity: Recent Developments in Year 2000 and Beyond

  2. https://github.com/openai/gpt-2

Category Commit Analysis

For those topics, the work will be done in the Coming project.

Automatic Clustering of Code Changes with Maximum Density Clustering

Supervisors: He Ye, Martin Monperrus

Studying similar code changes is essential for many software engineering areas, such as bug finding, program repair, program synthesis, etc. The state-of-the-art adapts Agglomerative Hierarchical Clustering and DBSCAN based on abstract syntax trees (AST) to clustering code change groups. In this project, you will explore other machine learning techniquesfor clustering code changes. You will learn (1) Learning the code diffs presentation (Coming); (2) Similarity distance metrics (Minkowski distance, Jaccard similarity coefficient, cosine similarity, Pearson similarity, Relative Entropy) (3) Non-supervised clustering algorithms such as MDCA (Maximum Density Clustering Application) and ​spectral clustering.

  1. FixMiner: Mining Relevant Fix Patterns for Automated Program Repair

  2. Automatic clustering of code changes

  3. https://github.com/SpoonLabs/coming

Automatic Identification of Bug-Fix Commits

Supervisors: Matias Martinez, Martin Monperrus

Description: In many situations, it is important to classify the commits according to some labels. For instance, one want to automatically identify security related commits, or bug-fixing commits. The student will work on an automatic commit classifier. The work will be done in the context of the Coming platform. * https://docs.google.com/document/d/18M-0KdI5BdCPz0oSt0mWeUF1TEZpPmHIHLY3imHAE0/editheading=h.6k2tdb1t1jql

  1. Mining Software Repositories for Adaptive Change Commits Using Machine Learning Techniques (2019)

  2. PatchNet: A Tool for Deep Patch Classification (2019)

  3. https://github.com/SpoonLabs/coming

Automatic Identification And Backporting of Vulnerability Fixes

Supervisors: Matias Martinez, Martin Monperrus

Description: When a fix is done to remove a vulnerability, it is important to backport the fixes to other branches. To do this: we need to components: 1) automatic identification of vulnerability fixes 2) automatic porting and fixing of porting conflicts. The student will work on those components. The work will be done in the context of the Coming platform.

  1. An automatic method for assessing the versions affected by a vulnerability

  2. When a patch goes bad: Exploring the properties of vulnerability-contributing commits

  3. Exploiting Token and Path-based Representations of Code for Identifying Security-Relevant Commits

Automatic Labeling of Commits to Identify Fix Patterns

Supervisors: Matias Martinez, Martin Monperrus

Description: In order to do data-driven program repair, one need to have ground truth labels about the fix patterns used in a commit. There are very few tools doing so. You will use those tools to characterize datasets, starting with the CodRep dataset, in order to have a taxonomy of fixes in Sequencer. You will extend PPD and other tools written in Java for commit analysis. The work will be done in the context of the Coming platform.

  1. Towards an automated approach for bug fix pattern detection

  2. https://github.com/SpoonLabs/coming

  3. Exploring and exploiting the correlations between bug-inducing and bug-fixing commits (2019)

Category Software Testing

Automatic Identification of Pseudo-tested Conditions

Supervisors: Benoit Baudry, Martin Monperrus (KTH)

Description: One of the problems with coverage is that it does not detect unspecified code [1]. There is the same problem with conditions, some conditions are well covered according to edge coverage yet the code can actually take any branch without failing. The student will design, implement and evaluate a novel technique for automatically identifying pseudo-tested conditions in Java software.

  1. A Comprehensive Study of Pseudo-tested Methods

  2. https://github.com/STAMP-project/pitest-descartes/

Automatic Prioritization of Mutants in Mutation Testing

Supervisors: Benoit Baudry, Martin Monperrus (KTH)

Description: One of the problems with mutation testing is that the developers are overwhelmed by the number of mutants to kill with new tests. One way to approach this problem is to view it as a recommendation problem based on the dependency graph. The student will design, implement and evaluate a novel technique for automatically prioritizing mutants to be killed in Java software.

  1. Selecting fault revealing mutants (2020)

  2. A Comprehensive Study of Pseudo-tested Methods

Automatic Repair of Flaky Tests

Supervisors: Benoit Baudry, Martin Monperrus (KTH)

Description: Flaky tests are tests that fail in an non-determistic way, and it is is a big problem in industry. Following the automatic repair philosophy, one can automatically repair a some of them by improving sandboxing or virtualizing time. The student will design, implement and evaluation a prototype system for automatic repair of flaky tests.

  1. An empirical analysis of flaky tests (2014)

  2. Automatic Software Repair: a Bibliography (2017)

  3. iFixFlakies: A Framework for Automatically Fixing Order-Dependent Flaky Tests

Automatic Renaming of Test Variables to Improve Maintainability

Supervisors: Benoit Baudry, Martin Monperrus (KTH)

Description: In test code, it is very important to have good variables names, so that the test intention is clear, and so that the test is maintainable. Recent research has shown that we can use machine learning to predict good names in code. The student will work to apply the state-of-the-art technique in variable renaming to test code in C++ or Java. The work will be related to the EU H2020 project STAMP.

  1. code2vec: Learning Distributed Representations of Code (2018), implementation at https://github.com/tech-srl/code2vec.

  2. Context2Name: A Deep Learning-Based Approach to Infer Natural Variable Names from Usage Contexts (2018)

Tagged as: