Thesis Details

Equivalence-Based Slicing of Programs

Bachelor's Thesis Student: Malecová Tatiana Academic Year: 2020/2021 Supervisor: Malík Viktor, Ing.
Czech title
Prořezávání programů založené na jejich podobnosti

The aim of this work is to design a method that simplifies two programs based on the results of analysis of their semantic difference. The goal is to remove as many semantically equivalent parts of the programs as possible. To find these equivalent parts, we apply our own solution to the problem of finding the maximum common induced subgraph. Subsequently, we are able to simplify the programs by using backward static slicing. By applying this simplification, we obtain sliced programs that consist of the differing parts and parts that can affect these differences. The method has been implemented as an extension of the DiffKemp tool, which is a static analyser of semantic differences between different versions of large scale programs. Our experiments on the Linux kernel show that the method is able to produce correct slices very efficiently (the analysis is prolonged only by 3.2%). Moreover, the created slices are much smaller than the original programs, which makes them suitable for further analysis.


DiffKemp, static analysis, backward static slicing of programs, maximum common induced subgraph

Degree Programme
Information Technology
defended, grade A
15 June 2021
Vojnar Tomáš, prof. Ing., Ph.D. (DITS FIT BUT), předseda
Kořenek Jan, doc. Ing., Ph.D. (DCSY FIT BUT), člen
Peringer Petr, Dr. Ing. (DITS FIT BUT), člen
Ryšavý Ondřej, doc. Ing., Ph.D. (DIFS FIT BUT), člen
MALECOVÁ, Tatiana. Equivalence-Based Slicing of Programs. Brno, 2021. Bachelor's Thesis. Brno University of Technology, Faculty of Information Technology. 2021-06-15. Supervised by Malík Viktor. Available from:
    author = "Tatiana Malecov\'{a}",
    type = "Bachelor's thesis",
    title = "Equivalence-Based Slicing of Programs",
    school = "Brno University of Technology, Faculty of Information Technology",
    year = 2021,
    location = "Brno, CZ",
    language = "english",
    url = ""
Back to top