|
|
Applying formal methods to analysis of semantic differences between versions of software
Nečas, František ; Vojnar, Tomáš (oponent) ; Malík, Viktor (vedoucí práce)
The goal of this work is to propose an integration of formal methods into DiffKemp, a static analysis tool for analyzing semantic differences of large-scale C projects. The aim of this extension is to facilitate analysis of more complex code changes, which would typically be better handled by a tool based on formal methods, while also maintaining DiffKemp’s scalability to large projects. To achieve this, whenever a possible semantic change is found, the equivalence of the relevant instructions is encoded into an SMT problem instance and the difference is either confirmed or refuted using an SMT solver. The proposed solution has been implemented in DiffKemp and our experiments on a set of benchmarks called EqBench show that it extends the capabilities of DiffKemp, mainly with regards to sound analysis of refactorings of arithmetic expressions.
|
|
|
Generating Code Change Patterns from C
Kučma, Tomáš ; Pavela, Jiří (oponent) ; Malík, Viktor (vedoucí práce)
Ensuring the semantic stability of software projects is often a costly task. DiffKemp is a tool that automatizes this process, with a special emphasis placed on performance and usability in large-scale projects. A trade-off for its efficiency is a greater degree of inaccuracy compared to formal tools. To minimize this issue, DiffKemp allows users to define their own semantics-preserving patterns, describing what kind of changes are to be treated as equal. Currently, this support is restricted to patterns written in LLVM internal representation, which is not a user-friendly language. The purpose of this work is to extend this capability to patterns written in C, significantly simplifying the process of their creation. This includes a proposal of a representation of the patterns, which must be able to encode all necessary meta-information, and subsequent design, implementation, and testing of a DiffKemp extension that allows utilization of patterns encoded in C.
|
|
|
Equivalence-Based Slicing of Programs
Malecová, Tatiana ; Vojnar, Tomáš (oponent) ; Malík, Viktor (vedoucí práce)
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.
|
|
|
Automatic Forward Slicing of Programs
Patrik, Nikolas ; Vojnar, Tomáš (oponent) ; Malík, Viktor (vedoucí práce)
This thesis presents designing new forward slicing solution for the DiffKemp tool. After strenuous analysis of currently implemented solution in DiffKemp for forward slicing we decided to retain current solution and extend it by few enhancements that should improve the analysis provided by DiffKemp in a quite big scope. We have implemented extensions so DiffKemp can perform analysis on fields of structured types which might represent run-time parameters and also we extended slicing criterion with the value of analyzed variable. Also we added support for slicing module kernel parameters. After implementing this solutions, we did experiments which proved that implemented solution has improved the analysis performed by DiffKemp.
|
|
|
Applying Code Change Patterns during Analysis of Program Equivalence
Šilling, Petr ; Fiedor, Tomáš (oponent) ; Malík, Viktor (vedoucí práce)
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.
|
|
|
Automatické generování šablon změn kódu
Kříž, Daniel ; Vašíček, Ondřej (oponent) ; Vojnar, Tomáš (vedoucí práce)
The aim of this thesis is to propose a method for automatic generation of custom code change patterns in LLVM IR language for DiffKemp, a tool for analyzing semantic differences between version of large scale projects. The goal is to enable automatic generation of changes between versions of a project with values, global variables or structure types. This has been achieved by finding the common pattern between changes and then generating its variants, which differ in usage of global variables and types. The proposed solution was implemented as an extension of DiffKemp and our experimentation on small programs shows that out proposed method is able to yield at least partially satisfactory results.
|
|
|
Vizualizace výsledků statického porovnávání sémantické ekvivalence různých verzí software v jazyce C
Petr, Lukáš ; Fiedor, Tomáš (oponent) ; Vojnar, Tomáš (vedoucí práce)
Cílem této práce je vytvořit přehlednější prezentaci výsledků nástroje DiffKemp sloužícího pro statickou analýzu sémantických rozdílů ve velkých projektech napsaných v jazyce C. V současnosti DiffKemp zobrazuje všechny informace o nalezených rozdílech v nestrukturované textové podobě, což je pro uživatele mnohdy nepřehledné. Pro vyřešení tohoto problému byl v této práci vytvořen nový výstup nástroje DiffKemp, který poskytuje výsledky v serializované podobě pomocí formátu YAML. Tento výstup je následně zpracován a zobrazen pomocí nově vytvořeného prohlížeče výsledků, realizovaného jako webová aplikace pomocí knihovny React, frameworku Bootstrap a balíčku react-diff-view. Dále se práce zaměřila na poskytnutí uživateli dodatečného kontextu ve formě zdrojových kódů analyzovaných funkcí a usnadnění navigace a orientace v nalezených rozdílech a k nim poskytovaných informací jako jsou zásobníky volání. Provedené srovnání nově vytvořeného prohlížeče ukázalo, že usnadňuje uživateli oproti původnímu řešení rozpoznat změny v poskytovaných zásobnících volání a umožňuje mu rychlejší navigaci ve výsledcích a také mezi vztahy nalezených rozdílů a analyzovaných částí.
|
|
|
Equivalence-Based Slicing of Programs
Malecová, Tatiana ; Vojnar, Tomáš (oponent) ; Malík, Viktor (vedoucí práce)
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.
|
|
|
Applying Code Change Patterns during Analysis of Program Equivalence
Šilling, Petr ; Fiedor, Tomáš (oponent) ; Malík, Viktor (vedoucí práce)
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.
|
|
|
Automatic Forward Slicing of Programs
Patrik, Nikolas ; Vojnar, Tomáš (oponent) ; Malík, Viktor (vedoucí práce)
This thesis presents designing new forward slicing solution for the DiffKemp tool. After strenuous analysis of currently implemented solution in DiffKemp for forward slicing we decided to retain current solution and extend it by few enhancements that should improve the analysis provided by DiffKemp in a quite big scope. We have implemented extensions so DiffKemp can perform analysis on fields of structured types which might represent run-time parameters and also we extended slicing criterion with the value of analyzed variable. Also we added support for slicing module kernel parameters. After implementing this solutions, we did experiments which proved that implemented solution has improved the analysis performed by DiffKemp.
|
host ::
RSS.