Diplomová práce
Získaná ocenění: Cena děkana FI za vynikající závěrečnou práci

Symbolic Loop Bound Analysis

Bc. Pavel Čadek, DiS.
Anotace

Práce uvádí novou metodu pro určování horních hranic na počet navštívení dané lokace v programu. Tyto hranice jsou vyjádřeny jako funkce nad vstupními proměnnými. Algoritmus je experimentálně naimplementován v nástroji Looperman. Součástí práce je jeho porovnání s ostatními nástroji na sadě testovacích programů. Práce také podrobněji popisuje dva další nástroje: Loopus a KoAT.

Abstract

We present a new method for computation of upper bounds on the number of visits of given program locations. These bounds are expressed as functions over input variable symbols. We have implemented our method in a prototype tool Looperman and evaluated it on a set of benchmarks. Besides the evaluation results, we provide also a detailed description of two other tools, Loopus and KoAT, which we used for the comparison with our tool.

Klíčová slova
static analysis loop bound analysis symbolic bound computation worst case execution time time complexity size complexity program termination reachability bound problem symbolic execution abstracting path conditions
Zadání práce
Cílem je vytvořit a experimentálně implementovat algoritmus, který k označeným místům programu určí horní hranici na počet průchodů přes daná místa během libovolného spuštění programu. Tato hranice bude vyjádřena jako funkce nad hodnotami vstupních proměnných programu. Součástí práce je také přehled dalších relevantních nástrojů v dané tematice, bližší představení dvou z nich (Loopus a KoAT) a jejich teoretické i experimentální srovnání s vlastním algoritmem.
Administrativní informace
Práce zkontrolována:
26. 5. 2015 09:43, prof. RNDr. Jan Strejček, Ph.D., učo 3366
Plný text práce
528,2 KB / soubor PDF
Přílohy (1)
Jazyk práce
angličtina angličtina
Termín obhajoby
25. 6. 2015
Práce byla úspěšně obhájena

Vedoucí

prof. RNDr. Jan Strejček, Ph.D., učo 3366
ITI FI MU

Oponenti

prof. RNDr. Ivana Černá, CSc., učo 1419
KTP FI MU
Florian Zuleger, Ph.D.
Citovat tuto práci
Masarykova univerzita Fakulta informatiky
Studijní program
Informatika
Obor

Práce na příbuzné téma

Seznam prací, které mají shodná klíčová slova.

Podobné práce

  • Přidání souboru

    Soubor nebo složku lze nahrát pomocí tlačítka Přidat.

  • Další operace se soubory

    Podrobnosti lze zjistit označením příslušného řádku.

  • Pohled pro experty

    Pro častou práci je možné zvolit režim Více možností.

  • Vyhledávání souborů

    Vyhledávaný výraz můžete zadat přímo do adresního řádku.

  • Rychlý přístup k souborům

    Pomocí funkce Nedávné je možné se rychle vrátit k právě prohlíženým souborům. Oblíbené soubory je také možné označit Hvězdičkou.