Original title: Použití šablon změn kódu počas analýzy ekvivalence programů
Translated title: Applying Code Change Patterns during Analysis of Program Equivalence
Authors: Šilling, Petr ; Fiedor, Tomáš (referee) ; Malík, Viktor (advisor)
Document type: Bachelor's theses
Year: 2021
Language: eng
Publisher: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstract: [eng] [cze]
Cílem této práce je návrh statické analýzy pro rozpoznávání vzorů, popisujících často se vyskytující změny mezi různými verzemi nízkoúrovňového kódu. V rámci práce je navržen způsob kódování vzorů, využívající vnitřní reprezentaci LLVM, a algoritmus pro hledání vzorů založený na postupném porovnávání instrukcí podle toku řízení. Navržená analýza byla implementována jako rozšíření nástroje DiffKemp pro analýzu sémantických rozdílů různých verzí rozsáhlých projektů napsaných v jazyce C. Výsledky experimentů provedených na třech dvojicích minulých verzí linuxového jádra ukazují, že navržené rozšíření dokáže eliminovat podstatné množství falešně pozitivních či obecně nežádoucích rozdílů z výsledků porovnání nástrojem DiffKemp, které by jinak vyžadovaly manuální kontrolu. 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: analýza sémantických rozdílů mezi programy; Clang; DiffKemp; GNU/Linux kernel; graf toku řízení; izomorfismus podgrafů; LLVM; LLVM metadata; odstraňování falešně pozitivních hlášení; porovnávání vzorů změn kódu; refaktorovací vzory; reprezentace vzorů změn kódu; SimpLL; vnitřní reprezentace LLVM; Clang; code change pattern matching; code change pattern representation; control-flow graph; DiffKemp; elimination of false-positive reports; GNU/Linux kernel; LLVM; LLVM intermediate representation; LLVM metadata; refactoring patterns; semantic difference analysis; SimpLL; subgraph isomorphism

Institution: Brno University of Technology (web)
Document availability information: Fulltext is available in the Brno University of Technology Digital Library.
Original record: http://hdl.handle.net/11012/199411

Permalink: http://www.nusl.cz/ntk/nusl-567070


The record appears in these collections:
Universities and colleges > Public universities > Brno University of Technology
Academic theses (ETDs) > Bachelor's theses