Please use this identifier to cite or link to this item: doi:10.22028/D291-25778
Title: Control flow graphs for real-time systems analysis: reconstruction from binary executables and usage in ILP-based path analysis
Author(s): Theiling, Henrik
Language: English
Year of Publication: 2002
SWD key words: Echtzeitsystem ; Worst-Case-Laufzeit ; Statische Analyse ; Planbarkeitsanalyse ; Kontrollflussdiagramm ; Pfadanalyse
DDC notations: 004 Computer science, internet
Publikation type: Doctoral Thesis
Abstract: Real-time systems have to complete their actions w.r.t. given timing constraints. In order to validate that these constraints are met, static timing analysis is usually performed to compute an upper bound of the worst-case execution times (WCET) of all the involved tasks. This thesis identifies the requirements of real-time system analysis on the control flow graph that the static analyses work on. A novel approach is presented that extracts a control flow graph from binary executables, which are typically used when performing WCET analysis of real-time systems. Timing analysis can be split into two steps: a) the analysis of the behaviour of the hardware components, b) finding the worst-case path. A novel approach to path analysis is described in this thesis that introduces sophisticated interprocedural analysis techniques that were not available before.
Echtzeitsysteme müssen ihre Aufgaben innerhalb vorgegebener Zeitschranken abwickeln. Um die Einhaltung der Zeitschranken zu überprüfen, sind für gewöhnlich statische Analysen der schlimmsten Ausführzeiten der Teilprogramme des Echtzeitsystems nötig. Diese Arbeit stellt die Anforderungen von Echtzeitsystem an den Kontrollflussgraphen vor, auf dem die statischen Analysen arbeiten. Ein neuartiger Ansatz zur Rückberechnung von Kontrollflußgraphen aus Maschinenprogrammen, die häufig die Grundlage der WCET-Analyse von Echtzeitsystemen bilden, wird vorgestellt. WCET-Analysen können in zwei Teile zerlegt werden: a) die Analyse des Verhaltens der Hardwarebausteine, b) die Suche nach dem schlimmsten Ausführpfad. In dieser Arbeit wird ein neuartiger Ansatz der Pfadanalyse vorgestellt, der für ausgefeilte interprozedurale Analysemethoden ausgelegt ist, die vorher hier nicht verfügbar waren.
Link to this record: urn:nbn:de:bsz:291-scidok-2973
hdl:20.500.11880/25834
http://dx.doi.org/10.22028/D291-25778
Advisor: Reinhard Wilhelm
Date of oral examination: 4-Feb-2003
Date of registration: 12-Jul-2004
Faculty: MI - Fakultät für Mathematik und Informatik
Department: MI - Informatik
Collections:SciDok - Der Wissenschaftsserver der Universität des Saarlandes

Files for this record:
File Description SizeFormat 
HenrikTheiling_ProfDrReinhardWilhelm.pdf997,74 kBAdobe PDFView/Open


Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.