Thesis Details

Applying Code Change Patterns during Analysis of Program Equivalence

Bachelor's Thesis Student: Šilling Petr Academic Year: 2020/2021 Supervisor: Malík Viktor, Ing.
Czech title
Použití šablon změn kódu počas analýzy ekvivalence programů
Language
English
Abstract

The goal of this thesis is to propose a static analysis method for recognition of code change patterns describing recurrent changes between different versions of low-level code. The thesis proposes an encoding method of patterns, which uses the LLVM intermediate representation, and a pattern matching algorithm based on gradual comparison of instructions according to their control flow. The proposed analysis has been implemented as an extension of DiffKemp, a tool for analysing semantic differences between versions of large C projects. Results of experiments conducted on three pairs of past versions of the Linux kernel show that the extension is able to eliminate a substantial amount of false-positive or generally undesirable differences from the output of DiffKemp, which would otherwise require manual inspection.

Keywords

DiffKemp, SimpLL, LLVM, Clang, GNU/Linux kernel, code change pattern matching, code change pattern representation, subgraph isomorphism, semantic difference analysis, refactoring patterns, LLVM metadata, LLVM intermediate representation, control-flow graph, elimination of false-positive reports

Department
Degree Programme
Information Technology
Files
Status
defended, grade A
Date
15 June 2021
Reviewer
Committee
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
Citation
ŠILLING, Petr. Applying Code Change Patterns during Analysis of Program Equivalence. Brno, 2021. Bachelor's Thesis. Brno University of Technology, Faculty of Information Technology. 2021-06-15. Supervised by Malík Viktor. Available from: https://www.fit.vut.cz/study/thesis/24037/
BibTeX
@bachelorsthesis{FITBT24037,
    author = "Petr \v{S}illing",
    type = "Bachelor's thesis",
    title = "Applying Code Change Patterns during Analysis of Program Equivalence",
    school = "Brno University of Technology, Faculty of Information Technology",
    year = 2021,
    location = "Brno, CZ",
    language = "english",
    url = "https://www.fit.vut.cz/study/thesis/24037/"
}
Back to top