Paper Info
Title
A functional approach to worst-case execution time analysis
Abstract
Modern hard real-time systems demand safe determination of bounds on the execution times of programs. To this purpose, program execution for all possible combinations of input values is impracticable. In alternative, static analysis methods provide sound and efficient mechanisms for determining execution time bounds, regardless of input data. We present a calculation-based and compositional development of a functional static analyzer using the Abstract Interpretation framework. Meanings of programs are expressed in fixpoint form, using a two-level denotational meta-language. At the higher level, we devise a uniform fixpoint semantics with a relational-algebraic shape, defined as the reflexive transitive closure of the program binary relations. Fixpoints are calculated in the point-free style using functional composition and a proper recursive operator. At the lower level, state transformations are specified by semantic transformers designed as abstract interpretations of the transition semantics.
Year
DOI
Venue
2011
10.1007/978-3-642-22531-4_6
WFLP
Keywords
Field
DocType
higher level,execution time bound,input data,execution time,lower level,functional static analyzer,program execution,functional composition,input value,worst-case execution time analysis,functional approach,fixpoint form
Worst-case execution time,Programming language,Computer science,Abstract interpretation,Binary relation,Program counter,Static analysis,Theoretical computer science,Operator (computer programming),Transitive closure,Recursion
Conference
Volume
ISSN
Citations 
6816
0302-9743
3
PageRank 
References 
Authors
0.39
9
3
Name
Order
Citations
PageRank
Vítor Rodrigues150.76
Mário Florido212214.44
Simão Melo de Sousa3959.60