Original title: Vylepšení analýzy živých proměnných pomocí points-to analýzy
Translated title: Improvement of Live Variable Analysis Using Points-to Analysis
Authors: Raiskup, Pavel ; Rogalewicz, Adam (referee) ; Dudka, Kamil (advisor)
Document type: Master’s theses
Year: 2012
Language: cze
Publisher: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstract: [cze] [eng]
Jazyky, jako je C, hojně využívají práce s ukazateli. Implemetace dynamických datových struktur vázaných ukazateli a operací nad nimi však není jednoduchá - významně zvyšuje rizika zanášení chyb do zdrojových kódů. Jedna z cest, jakými lze eliminovat množství těchto chyb, je použití statické analýzy. Tato práce se tedy zabývá vylepšením architektury Code Listner, která nabízí rozhraní pro tvorbu statických analyzátorů. Vlastností tohoto rozhraní je, že poskytuje takovému analyzátoru k rozboru potřebné informace o programu - ku příkladu databázi proměnných, graf toku řízení čí graf volání funkcí. Součástí implementace Code Listeneru je také algoritmus pro analýzu živých proměnných, umožňující odstranit, neboli zabít proměnné, které nejsou v daném místě grafu toku řízení potřeba. Původní algoritmus ale nedovedl z důvodu bezpečnosti zabít žádné proměnné, na něž byla kdekoliv ve zdrojovém kódu vzata adresa. Předpokládalo se, že taková proměnná může být zpřístupněna pomocí reference kdekoliv v programu. Cílem práce tedy bylo navrhnout a implementovat algoritmus pro points-to analýzu, která dovede vyloučit existenci některých referencí v daném kontextu programu a umožní tedy zefektivnit analýzu živých proměnných. Languages such as C use pointers very heavily. Implementation of operations on dynamically linked structures is, however, quite difficult. This can cause the programmer to make more mistakes than usual. One method for dealing with this situation is to use the static analysis tools. This thesis elaborates on the extension to the Code Listener architecture which is an interface for building static analysis tools. Code Listener is able to construct a call-graph or a control flow graph for a given source code and send it to the analyzing tool. One ability of the architecture is that it can conduct the live variable analysis internally. It detects places in the control flow graph where some subset of variables may be killed. The problem was that every variable for which a pointer address was assigned could not been killed, before. This decision had been made because there was no assurance that the variable could never been used through the pointer. So the goal of this work was to design and incorporate a points-to analysis which is able to exclude some references from the set of considered pointers to improve the live variable analysis.
Keywords: alias analysis; Code Listener; formal verification; gcc plugin; live variable analysis; pointer analysis; pointer arithmetic; points-to analysis; Static analysis; analýza aliasů; analýza ukazatelů; analýza živých proměnných; Code Listener; formální verifikace; gcc zásuvný modul; points-to analýza; Statická analýza; ukazatelová aritmetika

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/53654

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


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