arXiv:1506.05893v1 [] 19 Jun 2015

On Systematic Testing for Execution-Time Analysis
Daniel Bundala

Sanjit A. Seshia

UC Berkeley
Email: bundala@berkeley.edu

UC Berkeley
Email: sseshia@berkeley.edu

Abstract—Given a program and a time deadline, does the
program finish before the deadline when executed on a given
platform? With the requirement to produce a test case when such
a violation can occur, we refer to this problem as the worst-case
execution-time testing (WCETT) problem.
In this paper, we present an approach for solving the WCETT
problem for loop-free programs by timing the execution of a
program on a small number of carefully calculated inputs. We
then create a sequence of integer linear programs the solutions
of which encode the best timing model consistent with the measurements. By solving the programs we can find the worst-case
input as well as estimate execution time of any other input. Our
solution is more accurate than previous approaches and, unlikely
previous work, by increasing the number of measurements we
can produce WCETT bounds up to any desired accuracy.
Timing of a program depends on the properties of the platform
it executes on. We further show how our approach can be used
to quantify the timing repeatability of the underlying platform.

I. I NTRODUCTION
Execution-time analysis is central to the design and verification of real-time embedded systems. In particular, over the
last few decades, much work has been done on estimating
the worst-case execution time (WCET) (see, e.g. [1], [2], [3]).
Most of the work on this topic has centered on techniques
for finding upper and lower bounds on the execution time
of programs on particular platforms. Execution time analysis
is a challenging problem due to the interaction between
the interaction of a large space of program paths with the
complexity of underlying platform (see, e.g., [4], [5]). Thus,
WCET estimates can sometimes be either too pessimistic (due
to conservative platform modeling) or too optimistic (due to
unmodeled features of the platform).
The above challenges for WCET analysis can limit its
applicability in certain settings. One such problem is to verify,
given a program P , a target platform H, and a deadline d,
whether P can violate deadline d when executed on H —
with the requirement to produce a test case when such a
violation can occur. We refer to this problem as the worstcase execution-time testing (WCETT) problem.
Tools that compute conservative upper bounds on execution
time have two limitations in addressing this WCETT problem:
(i) if the bound is bigger than d, one does not know whether
the bound is too loose or whether P can really violate d,
and (ii) such tools typically aggregate states for efficiency
and hence do not produce counterexamples. Moreover, such
tools rely on having a fairly detailed timing model of the
hardware platform (processor, memory hierarchy, etc.). In
some industrial settings, due to IP issues, hardware details are

not readily available, making the task much harder for timing
analysis (see e.g, this NASA report for more details [6]); in
such settings, one needs an approach to timing analysis that
can work with a “black-box” platform.
In this paper, we present an approach to systematically test
a program’s timing behavior on a given hardware platform.
Our approach can be used to solve the WCETT problem,
in that it not only predicts the execution times of the worstcase (longest) program path, but also produces a suitable test
case. It can also be adapted to produce the top K longest
paths for any given K. Additionally, the timing estimate for
a program path comes with a “guard band” or “error bound”
characterizing the approximation in the estimate — in all our
experiments, true value was closed to the estimate and well
within the guard band.
Our approach builds upon on prior work on the GameTime
system [7], [8]. GameTime allows one to predict the execution
time of any program path without running it by measuring a
small sample of “basis paths” and learning a timing model of
the platform based on those measurements.
The advantage of the GameTime approach is that the
platform timing model is automatically learned from endto-end path measurements, and thus it is easy to apply to
any platform. However, the accuracy of GameTime’s estimate
(the guard bands) depend on the knowledge of a platform
parameter µmax which bounds the cumulative variation in the
timing of instructions along a program path from a baseline
value.
For example, a load instruction might take just 1 cycle if the
value is in a register, but several 10s of cycles if it is in main
memory and not cached. The parameter µmax can be hard to
pre-compute based on documentation of the processors ISA
or even its implementation, if available.
Our approach shares GameTime’s ease of portability to any
platform, and like it, it is also suitable for black-box platforms.
However, rather than depending on knowledge of µmax , we
show how one can compute the guard bands using an integer
linear programming formulation. Experimental results show
that our approach can be more accurate than the original
GameTime algorithm [8], at a small extra computational cost.
Moreover, our algorithm is tunable: depending on the desired
accuracy specified by a user, the algorithm measures more
paths and yields more precise estimate; possibly measuring all
paths if perfect accuracy is requested. Finally, we also show
how to estimate the parameter µmax .

int f ( int x) {
i f ( x % 2 == 0 ) {
i f ( x & 101) {
x ++;
} else {
x +=7;
}
}
return x ;
}

[x%2]

[!(x&101)]

[x&101]

[!(x%2)]
x+ = 7

x++

return x

Fig. 1: Source code (top) and its corresponding control flow
graph (bottom)

II. P RELIMINARIES
Our solution to the problem is an extension of the
measurement-based GameTime approach [11]. We now
present the model used in [11] as well as in this paper.
A. Model
To decide whether a program can exceed a given time
limit d, it suffices to decide whether the worst input exceeds
the limit d. However, recall that without any restrictions on the
program, when the program contains unbounded loops or recursion, even determining whether the program terminates not
even the number of steps it performs is undecidable. Therefore,
we consider only deterministic programs with bounded loops
and no recursion. We did not find this limitation restricting
as reactive controllers are already often written with this
limitation in mind.
Given a computer program, one can associate with it the
control-flow graph (CFG) in the usual way (Figure 1); vertices
representing locations and edges the basic blocks (straight-line
code fragments) of the program. Since we assume that the
loops are bounded and there is no recursion, the loops can
be unrolled and all function calls inlined. Thus, the resulting
CFG is always a directed and an acyclic graph (DAG).
Given a DAG G = (V, E), with the set of vertices V , set
of edges E, we designate two vertices: source s and sink t

corresponding to the entry and exit points of the program,
respectively.
For vertex v of graph, we use in(v) to denote the set of
incoming edges to v and out(v) to denote the set of outgoing
edges from v.
To model [11] the execution times of a program, we
associate with each edge e ∈ E cost we . The cost we models
the (baseline) execution time of the particular statement the
edge e corresponds to.
As described in the introduction, we measure only execution
times of entire source-to-sink paths and not of individual statements. Given a source-to-sink
P path x, the baseline execution
time of the path x is wx = e∈x we where the sum is over all
edges present in x. However, due to caching, branch misses,
etc. the actual execution time differs from the baseline and thus
the execution time (the length of the path) can be modeled as
X
wx =
we + dx
e∈x

where the term dx denotes the variation from the baseline
value. The term dx is a function of the input and the context the
program runs in. This is known as the bounded path-dependent
repeatability condition [12].
The length of path x is denoted wx . Observe that different
inputs corresponding to the same path in general take different
time to execute. However, we assume that |d| ≤ µx for some
µx ∈ R. We denote the maximum maxx µx by µmax . The
value µmax is a measure of timing repeatability. If µmax = 0
then the system is perfectly time repeatable. In general, the
larger the value of µmax , the less repeatable the timing of the
system is.
The aim of this paper is to find a path x such that wx
is maximal. The algorithm in [11] as well as ours, does not
require the knowledge of µx ’s or µmax to find the worstcase execution input. However, the accuracy of the algorithms
depend of µmax , as that is inherent to the timing of the
underlying hardware,
Our algorithm carefully synthesizes a collection of inputs
on which it runs the given program and measures the times
it takes to execute each of them. Then, using these measurements, it estimates the length of the longest path.
Formally, the pair (x, wx ) consisting of a path x and its
length wx is called a measurement. We denote the length of
the longest path by wM .
To summarize, throughout the paper we use the following
notation.
• G - underlying DAG
• S - set of measured paths
• M = {(xi , li )} - set of measurements consisting of pairs
path xi ∈ S and the observed length li
It was shown in [11] how, using only |E| measurements
of source-to-sink paths, to find an input corresponding to a
path of length at least wM − 2|E|µmax . In particular, if the
longest path is longer than the second longest path by at least
2|E|µmax , the algorithm in [11] in fact finds the longest path.
Thus, we say that the “accuracy” of the algorithm is 2|E|µmax .

in such a way that for any path x, it always holds that |cb | ≤ 2
for every b ∈ B. The paths in B are called the basis paths as
they suffice to express any other path.
P
Now, if the path px can be written as px = b∈B cb · pb
then its estimated (baseline) length is
X
wx =
cb · wb
b∈B

Fig. 2: DAG with exponentially many paths

In this paper, we show how to (i) improve the accuracy without
increasing the number of measurements, (ii) by increasing the
number of measurements improve the accuracy even further,
(iii) how to estimate the timing repeatability of the underlying
platform (as captured by µmax ).
Our algorithm as well as the algorithm in [11] measures the
length of some paths and then estimates the lengths of other
paths based on those measurements. Note that as long as not
all the lengths of all the paths are measured, the inaccuracy
of estimates is unavoidable. Consider for example the graph
in Figure 2 and assume the graph consists of n “diamonds”.
Clearly, there are 2n source-to-sink paths in the graph.
Assume that we = 1 for each edge and µx = 0 for all paths
x except for one path y for which µy = µmax > 0. Now,
suppose we measure the lengths of some collection of paths S.
As long as S does not contain y, the length of every observed
path is 2n. Hence, any length of wy of y in the interval
[2n − µmax , 2n + µmax ] is consistent with the measurement.
Therefore, in the worst case, the best achievable estimate of
the length of wy can always be at least µmax from the real
answer.

where wb ’s are the measured lengths of the basis paths.
The algorithm thus runs the program on the inputs corresponding to the basis paths in order to measure the lengths
pb for each b ∈ B. Moreover, it was shown in [11] how,
by encoding the problem as an integer-linear-program (ILP)
instance, to find
Ppath X such that the corresponding estimated
length: pX = b∈B cb · wb is maximized2 .
Consider the accuracy
P of the estimated length of pX . By
construction, pX = b∈B cb · pb . Hence,
X
X X
we =
cb
we .
e∈X

b∈B

e∈b

Further, for b ∈ B, we have wb =

wX −

X

cb · wb

=

X

P

e∈b

we + db . Hence,

w e + dX −

e∈X

b∈B

=

X

=

w e + dX −

X

X
cb (
we + db )

b∈B

we −

e∈X

X

cb

X

b∈B

+dX −

1

cb · wb

b∈B

e∈X

X

X

X

e∈b

we

e∈b

cb · db

b∈B

We now briefly describe the algorithm in [11]; we skip the
standard technical details such as CFG extraction or how to
find an input corresponding to a given path and focus only on
how to extract the longest path.
Let m be the number of edges in E. Then, by numbering
the edges in E, one can think of each path x as a vector px
in Rm such that

0 if ith edge is not used in x
px (i) =
1 if ith edge is used in x

≤

dX −

X

cb · db

b∈B

≤

(2|B| + 1)µmax

where cb ’s are coefficients in R. Moreover, using theory of 2barycentric spanners [13], it was shown that B can be chosen

Thus, the algorithm in [11], finds the longest path (and the
corresponding input) only up to the error term of (2|B| +
1)µmax , under certain assumptions outlined in [11]. A challenge, as noted earlier, is that it is not easy to estimate the
value of µmax . Consider the first four columns in Table V.
The second column in the table shows the lengths of the
longest path as estimated by the algorithm in [11]. However,
the third column shows the actual length of the path that is
measured when the program is executed on the corresponding
inputs. Notice that in some cases the prediction does not
match the measured time. Also, the algorithm in [11] does not
provide any error bounds on the estimates, thereby making the
predicted values less useful.
In this paper we show how, given the exactly same set of
measurements as in [11], we can find a tighter estimate and
how to incorporate the knowledge of additional measurements
to obtain even tighter bounds. In fact, for the benchmarks given

1 In general, however, it holds that the more paths are included in S the
better is the estimate of the longest path.

2 In case the resulting path is infeasible in the program, a constraint is added
into the ILP and the ILP is solved again.

Now, given two paths x and y, one can define the linear
combination a · x + b · y for a, b ∈ R in the natural (component
wise) way. Thus, one can think of paths as points in an mdimensional vector space over R. In particular, it was show
in [11] that there is always a basis B of at most m source-tosink paths such that each source-to-sink path x can be written
as a linear combination of paths from B:
X
px =
cb · pb
b∈B

x0

x1

x2

x3

Fig. 3: Basis paths for DAG in Figure 2. For example, the
path that always takes the bottom path through each diamond
can be expressed as x1 + x2 + x3 − 2 ∗ x0

in Table V, we not only obtain more accurate predictions of
running time, we can also give error bounds for our estimates.
III. A LGORITHM
A. Overview
We now give an overview of our algorithm. Recall, that the
problem studied can be considered as follows: Given a DAG
with source s and sink t, find the longest source-to-sink path
where the lengths of that paths are modeled as described in
the Preliminaries, Section II.
The algorithm in [11] expresses every path as a linear
combination of basis paths; using their lengths to estimate
the length of the paths not measured. Intuitively, if two paths
overlap (they share common edges) then knowing the length of
one provides some information about the length of the other.
Even basis paths with zero coefficient in the linear combination
can provide information about the length of an estimated path.
In our algorithm, we write integer linear programs (ILPs),
with one constraint per measurement, looking for the longest
path with the edge weights consistent with the measurements
and µx . Even though, µx are not observable, we show how to
obtain consistent bound on µmax from the measurements.
B. Path Extraction
In this section we assume that we have a set of measurements M, consisting of pairs (x, lx ) where x is a path and lx is
the measured length of x and we show how to find the longest
path consistent with the measurements. In Section III-D we
then show how to actually calculate the set S. To make the
notation consistent with [11], we call the measured paths the
basis paths, even if they do not necessarily form a basis in
the underlying vector space as was the case in [11].
Suppose, for the moment, that the value of µmax is known
and equal to D ∈ R. Then the following problem encodes
the existence of individual
edge weights (we ) such that the
P
cumulative sum ( e∈xi we ) along each measured path is
consistent with its measured length; that is, the measured value
differs by at most D from the cumulative sum.

Problem 1. Input: DAG G, a set of measurements M and
D ∈ R
max len(path)P
s.t. li − D ≤ e∈xi we ≤ li + D
for each measurement (xi , li ) ∈ M
vars : we ≥ 0
for each edge e
Where max len(path) expresses the length of the longest
cumulative sum along some source-to-sink path in the graph.
We now turn this problem into an ILP by expressing the
existence of a path as follows:
Problem 2. Input: DAG G, a set of measurements M and
D ∈ R
P
max
e∈E pe P
s.t. li − D ≤ e∈xi we ≤ li + D
Pfor each measurement (xi , li ) ∈ M
b =1
Pe∈out(s) e
b
=1
Pe∈in(t) e P
e∈(v) be =
e∈out(b) be
for each vertex v 6∈ {s, t}
pe ≤ we
for each edge e
pe ≤ M · be
for each edge e
vars : for each edge e:
we ≥ 0
be ∈ {0, 1}
pe ≥ 0
Where M ∈ R is a constant larger than any potential we .
In the implementation, we take M to be the largest li in the
set of measurements S plus one.
In the above ILP (Problem 2), Boolean variables be ’s specify
which edges of the graph are present in the extremal
source-toP
sink path and pe ’s shall equal be ×we . Thus, e∈E pe denotes
the length of the extremal source-to-sink path.
The existence of a path is encoded by the constraints
specifying that there is a flow from the source to the sink. That
is, that exactly one edge from the source has be = 1, exactly
one edge to the sink has be = 1 and that for all intermediate
vertices, the number of incoming edges to that vertex with
be = 1 equals the number of outgoing edges from that vertex
with be = 1.
Further, for each edge e ∈ E, we use the variable pe to
denote the multiplication pe = be · we . As be ∈ {0, 1}, we
have pe ≤ we . Also, the constraints pe ≤ M · pe ensure that
if be = 0 then pe = 0. On the other hand, if be = 1 then
constraints imply only that 0 ≤ pe ≤
Pwe . Finally, note that the
objective function is to maximize e∈E pe . hence, if be = 1
then optimum value for pe is to set pe to we . Hence, in the
optimal solution, if be = 1 then pe = we = 1 · we = be · we
as desired.
PRecall, that for measurement (xi , li ) it holds that li =
e∈xi we + d where |d| ≤ µx ≤ µmax . Thus, in general,

D needs to be at least 0 to ensure that Problem 2 is feasible.
By the assumption, taking D = µmax yields a feasible ILP.

TABLE I: Different values of D obtained in the benchmarks
by perturbing the measurements.

Lemma 1. Problem 2 is feasible for D = µmax .

Benchmark

However, the value of µmax is neither directly observable
nor known as it depends on the actual hardware the program
is running on. We now show how to obtain a valid D yielding
a feasible ILP in Problem 2. Later we show under what
circumstances the solution of the resulting ILP gives the
correct longest path.
Consider the following LP3 .

altitude
stabilisation
automotive
cctask
irobot
sm

Problem 3. Input: DAG G and a set of measurements M
min µ
P
s.t. li − µ ≤ e∈xi we ≤ li + µ
for each measurement (xi , li ) ∈ M
vars : for each edge e:
we ≥ 0
µ≥0
Intuitively, the problem above finds the least value of D for
which Problem 2 is feasible, i.e., the least D consistent with
the given set of measurements M . Formally, we have:
Theorem 2. Let p(µ) be the solution of Problem 3. Then
taking D = p(µ) in Problem 2 yields a feasible ILP.
Proof: First, note that Problem 3 always has a solution,
e.g., take we = 0 and µ = maxi li .
Notice that, assuming there is at least one source-to-sink
path, the only possible way for Problem 2 to be infeasible
is that D is small enough so that the constraints li − D ≤
P
e∈xi we ≤ li + D are inconsistent.
However, by
Pthe construction of Problem 3, p(µ) satisfies,
li − p(µ) ≤
e∈xi we ≤ li + p(µ) for every path xi . The
result now immediately follows.
Note that, by construction, taking µ = µmax in Problem 3 is
feasible. Hence, D ≤ µmax as D is the least value consistent
with the measurements.
Notice that the solution of Problem 3, can be used as a
measure of timing repeatability of the underlying hardware
platform. In case of perfect timing repeatability, that is if each
edge (each statement of the underlying program) always took
exactly the same time (regardless of concrete values of cache
hits, misses, branch predictions, etc) to execute and that dx =
0 for every measured path, then the solution of Problem 3
would be 0. Conversely, the larger the value of the solution
of Problem 3 the bigger the discrepancy between different
measurements.
To measure the effect of timing repeatability on the computed value of D, we have taken measurements for a set of
benchmarks used to evaluate our tool on (Section IV-B) and
randomly perturbed the measured execution times. We have
perturbed each measurement randomly by up to 10%, 25% and
50%. Table I shows the calculated values of D. As expected,
the larger the perturbation, the larger the calculated value of D.
3 Note

that Problem 3 is a linear program and not an integer linear program.

0%
57.0
343.2
1116.0
73.9
37.2
0.1

Perturbation
10%
25%
66.1
87.8
371.3
807.1
1281.3 1486.9
110.6
150.9
95.9
288.8
23.2
117.4

50%
126.5
1107.2
2961.3
270.6
552.8
216.8

C. Optimality
The solution of Problem 2 is the best estimate of the longest
path that is consistent with measurements M. We now show
how good the estimate is.
Consider the solution of Problem 2 with D equal to the
solution of Problem 3. For each edge e, let p(we ) denote the
value of the variable we in the solution, and let τ be the path
corresponding to the solution of Problem 2. Denote the length
of τ in the solution by p(len(τ )). We now show how much
p(len(τ )) differs from the actual length of τ . Specifically, we
shall show that the goodness of the estimate of the length of
τ is related to the following ILP4 .
Problem 4. Input: DAG G and a set of measurements M
max | len(path)|
P
s.t. −1 ≤ e∈xi we ≤ +1
for each measurement (xi , li ) ∈ M
vars : we
for each edge e
The existence of a path and the length of the path is
expressed in the above ILP in exactly the same way as was
done in Problem 2. Note that the above ILP is always feasible
with | len(path) at least 1; one solution is to set we = 1 for
one edge outgoing from the sink and set we = 0 for all other
edges. Further, note that Problem 4 depends only on the graph
and the set of the measured basis paths; it is independent of
the (measured) lengths of the paths. In fact, we can show that
as long as some path does not appear in the measurements
M, the solution of the above ILP is strictly greater than 1.
Theorem 3. Let G be a DAG, M a set of measurements and
π a source-to-sink path in G such that π is not present in M.
Then the solution of Problem 4 is strictly greater than 1.
Proof: We give a satisfying assignment to variables we
in Problem 4 such that len(π) > 1.
Specifically, let ei be the first edge of π, that is, the edge
outgoing from the sink of G. Further, let, D = {(u, v) |u ∈ π}
be the set of edges with the initial vertex lying on π. Then the
assignment to weights we is as follows:

1
e = ei
 1 + |E|
1
− |E|
e∈D
we =

0 otherwise
4 To find the absolute value | len(path)| we solve two linear programs.
One with the objective function max len(path) and one with the objective
function max − len(path).

Note that, with this assignment to we ’s, the length of pi
1
> 1. Now, consider any other path τ
equals len(π) = 1 + |E|
used in measurements M. In particular, τ 6= π. There are |E|
edges in G and the weight we associated with each edge e is
1
1
at least − |E|
. Hence, len(τ ) ≥ |E| × − |E|
= −1.
Now, if τ does not include ei , that is ei 6∈ τ then, len(τ ) ≤ 0
as wei is the only positive weight. If τ includes ei , that is
ei ∈ τ , then τ necessarilly contains at least one edge from
D as τ is different from π. Hence, len(τ ) ≤ 1. In any case,
−1 ≤ len(τ ) ≤ 1 as required and thus we have given a valid
assignment to we ’s with len(π) > 1.
Recall that the set S denotes the set of paths occurring
measurements M. Let r(we ) and r(µx ) be the real values of
we for each edge e and µx for each path x ∈ S. Then for each
edge e the expression |p(we ) − r(we )| denotes the difference
between the calculated values of we and the actual value of
we . Analogously, the expression
P extends to entire paths: for
a path x we have p(wx ) = e∈x p(we ). Now, the difference
for the worst path can be bounded as follows.
Theorem 4. Let k be the solution of Problem 4. Then
|p(len(τ )) − r(len(τ ))| ≤ 2kµmax
Proof: Note that by construction, r(we ) and r(µx ) are a
solution of Problem 3. Hence, for every (xi , li ) ∈ M it holds
that.
li −µmax ≤ li −r(µxi ) ≤

X

r(we ) ≤ li +r(µxi ) ≤ li +µmax .

e∈xi

Recall that D ≤ µmax and that that p(we ) is a solution of
Problem 2. Hence, for every (xi , li ) ∈ M it holds that:
li − µmax ≤ li − D ≤

X

p(we ) ≤ li + D ≤ li + µmax .

e∈xi

Hence, by subtracting the last two equations from each
other, we have for any basis path xi ∈ S that:
−2µmax ≤

X

p(we ) − r(we ) ≤ 2µmax

e∈xi

Now, dividing by 2µmax we have:
P
p(we ) − r(we )
≤ 1.
−1 ≤ e∈xi
2µmax
for any basis path xi ∈ S.
Thus, the above inequality implies that taking
we =

p2 (we ) − r(we )
2µmax

is a (not necessarily optimal) solution of Problem 4. Since k
is the length of the longest path achievable in Problem 4, it
follows that for any path x (not necessarily in the basis), we
have
P
p(we ) − r(we )
−k ≤ e∈x
≤ k.
2µmax

TABLE II: Comparison of the accuracy in the longest path
extraction between our algorithm and the one in [11]. For our
accuracy, we take 2 ∗ k where k is the solution of Problem 4.
For [11] we take 2 ∗ (# basis paths).
Benchmark
altitude
stabilisation
automotive
cctask
irobot
sm

# Basis Paths
6
10
13
18
21
69

[11] Accuracy
12
20
26
36
42
138

Our Accuracy
10.0
16.4
14.0
34.0
18.0
48.6

By rearranging, we have
−2kµmax ≤

X

p(we ) − r(we ) ≤ 2kµmax .

e∈x

In other words, the calculated length differs from the real
length by at most 2kµmax , as desired.
Recall that the algorithm in [11] has difference between the
estimated and the actual length at most 2|E|µmax whereas our
algorithm has 2kµmax where k is the solution of Problem 4.
Observe that the dependence in the error term on µmax is
unavoidable as µmax is inherent to the timing properties of
the underlying platform.
For comparison, we have generated the same basis as in [11]
and calculated the corresponding k’s for several benchmarks.
Table II summarizes the results (see Table IV for the description of benchmarks). As can be seen from the table, when
using the same set of measurements, our method gives more
accurate estimates than the one in [11].
Furthermore, recall that in Problem 3 we calculate the
best (lower) bound D on µmax consistent with the given
measurements. Together with the above theorem, this gives
“error bounds” to the estimate in Problem 2. Specifically, if
the length of the longest path computed in Problem 2 is T
then, the length of the path when measured, that is consistent
with the measurements is within T ± (2k × D). However,
note that this is only the best bound deducible from the
measurements since D ≤ µmax . Since µmax is not directly
observable and we assume no nontrivial bound on µmax , the
length of the path cannot be bounded more accurately without
actually measuring the path.
The above analysis applies to the extraction of the single
longest path. Now, suppose that instead of extracting just one
longest path, we want to extract K longest paths. To that
end, we iterate the above procedure and whenever a path is
extracted, we add a constraint eliminating the path from the
solution of Problem 2 and then solve the updated ILP. For a
path x, the constraint
eliminating it from the solution space of
P
Problem 2 is e∈x be < |x|. The constraint specifies that not
all the edges along x can be taken together in the solution.
As the length of the predicted and the measured length
differ, it may happen (e.g., Table V) that when measured
the length of the path predicted to be the longest is not
actually the longest. Thus, to find the longest path, we may

need to iterate the above process by generating paths with
ever smaller predicted lengths, stopping whenever the current
estimate differs by more than (2k × D) from the longest
estimate.

TABLE III: Number of paths generated by Algorithm 1 to
reach the desired accuracy (second column). Third column
shows the accuracy (solution of Problem 4) of the generated
set of paths
Benchmark

D. Basis Computation
The algorithm (Problem 2) to estimate the longest path
depends on the set of measurements M of the basis paths S.
In this section we show how to calculate such a set of paths.
In general, arbitrary set of paths can be used as basis paths.
For example, we have shown in Table III that using the set of
paths used in [11], we are able to get more accurate estimates
than those obtained in [11].
Recall that (Theorem 4) the accuracy of the solution of
Problem 2 is tightly coupled with the solution of Problem 4.
This leads to a tunable algorithm, which depending on the
desired accuracy of the predictions, calculates a set of paths
to be used in Problem 2.
Specifically, given a desired accuracy A ∈ R, A ≥ 1, we
want to find a set of feasible paths S such that the solution of
Problem 4 is at most A. We implemented a simple iterative
algorithm (Algorithm 1) that finds such a set by repeatedly
extending the set of paths by the path corresponding to the
solution of Problem 4.
In the algorithm, if the longest extracted path is infeasible
in the underlying program, we add a constraint into the ILP
(Problem 4) prohibiting the path. That is, if the longest path is
infeasible and τ is the unsatisfiable core of the longest path5
then we add a constraint that not all the be ’s corresponding
to
P
the edges used in τ are set to 1 in Problem 2, i.e., e∈τ be <
|τ | where |τ | denotes the number of edges in τ . Then we solve
the updated ILP.
S←∅
while (Solution of Problem 4 with paths S) > A do
x ← longest path in Problem 4
if x is feasible then
S ← S ∪ {x}
else
Add a constraint prohibiting x
end
end
return S
Algorithm 1: Iterative algorithm for basis computation
Theorem 5. If A ≥ 1 then the Algorithm 1 terminates with a
set P of paths such that the solution of Problem 4 with paths
P is at most A.
Proof: Note that each constraint in Problem 4 limits the
length of some path to (at most) 1. In particular, if S contains
all the paths in the graph then the solution of Problem 4
equals 1.
5 Minimal set of edges that cannot be taken together as identified by an
SMT solver

altitude

stabilisation

automotive

cctask

irobot

sm

Desired k
10
5
2
10
5
2
10
5
2
10
5
2
10
5
2
22
18
15

Actual k
5.0
5.0
1.0
7.0
4.7
2.0
7.0
5.0
2.0
9.0
5.0
2.0
9.0
5.0
2.0
21.8
18.0
14.5

# Basis Paths
7
7
10
11
12
40
14
14
30
19
25
76
22
34
118
70
73
77

Time(s)
0.03
0.03
1.66
0.10
0.96
22.78
0.14
0.89
27.60
0.20
4.10
42.91
0.50
20.13
182.42
328.14
7089.04
10311.49

Further, if the algorithm finds some path x to be the longest
in some iteration then the length of x in all subsequent
iterations will be at most 1 as x ∈ S. Therefore, as long as the
solution is greater than 1, the longest path found is different
from all the paths found in the previous iterations.
Also, if the path is infeasible, then a constraint is added
that prevents the path occurring in any subsequent iterations.
It follows from these considerations that the algorithm keeps
adding new paths in each iteration and eventually terminates.
By construction, the solution of Problem 4 with the set of
paths S is at most A.
In the extreme case of A = 1, it immediately follows from
Theorem 3, that Algorithm 1 returns all feasible paths in the
underlying graph.
We have implemented the above iterative algorithm and
evaluated it on several case studies. Table III summarizes the
number of paths generated by the algorithm for the given
accuracy k as well as the running time required to find those
paths.
We have observed that the basis computation took substantial part of the entire algorithm. However, notice that the
basis-computation algorithm (Algorithm 1) need not start with
S = ∅ and works correctly for any initial collection of paths S.
Therefore, as an optimization, we first compute the initial
set of paths S using the original algorithm from [11], which
computes the 2-barycentric spanner of the underlying DAG.
Only then we proceed with the iterative algorithm to find a
set of paths with the desired accuracy.
Figure 4 shows the performance of the iterative algorithm
on two benchmarks. The decreasing (blue) line shows how
the accuracy k decreases with each path added to the basis.
The increasing (red) line shows the time needed to find
each path. The figure shows only the performance after the
precomputation of the 2-barycentric spanner.

Fig. 4: Performance of the Algorithm 1. The decreasing (blue)
line shows the length of x computed (k) in line 3. The
increasing (red) line shows the time taken to perform each
iteration.
(a) cctask

k

time(s)

0.9

12

0.8

10

0.7

8

0.6

6

0.5

4

0.4

2
10

time(s )

k

14

20

30

40

# paths

50

60

70

0.3
80

(b) irobot
11
10

k

time(s)

1.4

1.2

9
8

1.0

k

time(s )

7
6

0.8

5
4

0.6

3
2
20

30

40

50

60
70
# paths

80

90

100

0.4
110

IV. E VALUATION
A. Implementation
The algorithm to identify the longest (up to accuracy k)
path a given program P is shown in Algorithm 2.
We now briefly describe the implementation of main stages
of the Algorithm 2. Our implementation is build on top of [11].
See [11] for further discussion of technical details.
CFG extraction The procedure begins by building the
CFG G of the given program. The vertices correspond to
locations and edges to individual statements. The extraction
is build on top of CIL front end for C [14]. Note that all ILPs
(Problems 2, 3 and 4) introduce a variable per each edge of G

Extract CFG G from the program P
S ← basis with accuracy at most k (Algorithm 1)
D ← Solution of Problem 3
τ ← Solution of Problem 2 with paths S and D
return τ and its estimated length
Algorithm 2: Algorithm to find the worst-case execution
time. Input: Program P , accuracy k

and that each problem optimizes for the length of a source-tosink path. Thus, if some edge is always followed by another
one (the in- and out-degree of the joining vertex is one) then
the edges can be merged into a single one6 without changing
the solution of the ILP problems. Therefore, we process G
by merging edges that lie on a single path into a single edge.
This reduces the number of variables used and improves the
performance.
Basis computation The basis is computed as described in
Section III-D, Algorithm 1. We use Gurobi solver [15] to
solve individual ILPs and use the 2-barycentric spanner as
the initial set S. Solving the ILPs posed the main bottleneck
of our approach.
Input generation Each path through the CFG G corresponds to a sequence of operations in the program and hence
a conjunction of statements. For a given path, we use the
Z3 SMT solver [16] to find an input that corresponds to
the given path or to prove that the path is infeasible and no
corresponding input exists. In the experiments, SMT solving
was fairly fast.
Longest-path extraction We solve Problem 2 using Gurobi
ILP solver [15].
P If the extracted path π is infeasible, we add
a constraint ( e∈π be < |π|) eliminating the path from the
solution and solve the new problem. Similarly, we solve for
K longest paths; we add a constraint prohibiting the extracted
path and solve the resulting ILP again, repeating until we
successfully generate K feasible paths.
Recall that the calculated length of the path is accurate only
up to the precision 2k × D. Thus, we can repeat the process
until the length of the extracted path is outside of the range
for the longest extracted path. However, in practice we did
not find this necessary and found the longest path after a few
iterations.
Path-Length Measurement To measure the execution time
of the given program on a given input, we create a C program
where we set the input to the given values and then run it using
a cycle-accurate simulator of the PTARM processor [17].
B. Benchmarks
We have evaluated our algorithm on several benchmarks
and compared it with the algorithm in [11]. We used the same
benchmarks as in [11] as well as benchmarks from control
tasks from robotic and automotive settings. The benchmarks
in [11] come from Mälardalen benchmark suite [18] and the
6 For example, in Figure 2, every diamond can be replaced by two edges,
one edge for the top half and one edge for the bottom half.

TABLE IV: Number of nodes, edges and paths in the CFGs
extracted from the benchmarks
Benchmark
altitude
stabilisation
automotive
cctask
irobot
sm

# Nodes
36
64
88
102
170
452

# Edges
40
72
100
118
195
523

# Paths
11
216
506
657
8136
33, 755, 520

PapaBench suite [19]. The authors of [11] chose implementations of actual realtime systems (as opposed to hand-crafted
ones) that have several paths, were of various sizes, but do not
require automatic estimation of loop bounds.
Since we assume all programs contain only bounded loops
and no recursion, we preprocessed the programs by unrolling
the loops and inlining the functions where necessary. Table IV
summarizes properties of the benchmarks used.
Table V shows the lengths of five longest paths as found by
our algorithm and the one in [11]. The first half of the table
shows the results as obtained by the algorithm in [11]. The
second half shows the results as obtained (together with the
“error bounds”) by our algorithm (Algorithm 2).
Note that in each case the longest path returned by our
algorithm is never shorter than the longest path found by [11].
In half of the cases, our algorithm is able to find a path longer
than the one in [11]. Also notice that the actual measured
length is always within the computed “error bounds”.
The biggest benchmark, sm, is a collection of nested switchcase logic setting state variables but with minimal computations otherwise. Hence, there is a large number of paths
(33, 755, 520) in the CFG yet, as expected, the computed D
is small.
V. C ONCLUSION
In this paper, we have addressed the problem of estimating
the worst-case timing of a program via systematic testing
on the target platform. Our approach not only generates an
estimate of worst-case timing, but can also produces test cases
showing how that timing is exhibited on the platform. Our
approach improves the accuracy of the previously published
GameTime approach, while also providing error bounds on the
estimate.
Note that our approach can be adapted to produce timing
estimates along arbitrary program paths. In order to do this,
one can fix variables be in Problem 2 suitably. Thus, we can
also estimate the longest execution of a given path that is
consistent with the measurements.
In the paper we have analyzed the timing behavior of a
given program. However, instead of measuring cycles we can
measure energy consumption of the program executions. The
same techniques can then be applied to find the input consuming the most energy. In general, the approach presented in this
paper can also be extended to other quantitative properties of
the program and is not limited only to the WCETT analysis.

R EFERENCES
[1] Y.-T. S. Li and S. Malik, Performance Analysis of Real-Time Embedded
Software. Kluwer Academic, 1999.
[2] Reinhard Wilhelm et al., “The Determination of Worst-Case Execution
Times—Overview of the Methods and Survey of Tools,” ACM Transactions on Embedded Computing Systems (TECS), 2007.
[3] E. A. Lee and S. A. Seshia, Introduction to Embedded Systems: A CyberPhysical Systems Approach, first edition ed. http://leeseshia.org, 2011.
[4] E. A. Lee, “Computing foundations and practice for cyber-physical
systems: A preliminary report,” University of California at Berkeley,
Tech. Rep. UCB/EECS-2007-72, May 2007.
[5] R. Kirner and P. Puschner, “Obstacles in worst-case execution time
analysis,” in ISORC, 2008, pp. 333–339.
[6] NASA Engineering and Safety Center, “NASA report on Toyota unintended acceleration investigation, appendix a: Software,” http://www.
nhtsa.gov/staticfiles/nvs/pdf/NASA FR Appendix A Software.pdf.
[7] S. A. Seshia and A. Rakhlin, “Game-theoretic timing analysis,” in
Proc. IEEE/ACM International Conference on Computer-Aided Design
(ICCAD), 2008, pp. 575–582.
[8] ——, “Quantitative analysis of systems using game-theoretic learning,”
ACM Transactions on Embedded Computing Systems (TECS), 2012.
[9] Y.-T. S. Li and S. Malik, “Performance analysis of embedded software
using implicit path enumeration,” in Proceedings of the 32Nd Annual
ACM/IEEE Design Automation Conference, ser. DAC ’95. New
York, NY, USA: ACM, 1995, pp. 456–461. [Online]. Available:
http://doi.acm.org/10.1145/217474.217570
[10] R. Wilhelm, “Determining bounds on execution times.” 2009.
[11] S. A. Seshia and A. Rakhlin, “Game-theoretic timing analysis,”
in Proceedings of the 2008 IEEE/ACM International Conference
on Computer-Aided Design, ser. ICCAD ’08. Piscataway, NJ,
USA: IEEE Press, 2008, pp. 575–582. [Online]. Available: http:
//dl.acm.org/citation.cfm?id=1509456.1509584
[12] Z. Wasson, “Analyzing data-dependent timing and timing repeatability
with gametime,” Master’s thesis, EECS Department, University of
California, Berkeley, May 2014. [Online]. Available: http://www.eecs.
berkeley.edu/Pubs/TechRpts/2014/EECS-2014-132.html
[13] B. Awerbuch and R. D. Kleinberg, “Adaptive routing with end-toend feedback: Distributed learning and geometric approaches,” in
Proceedings of the Thirty-sixth Annual ACM Symposium on Theory of
Computing, ser. STOC ’04. New York, NY, USA: ACM, 2004, pp. 45–
53. [Online]. Available: http://doi.acm.org/10.1145/1007352.1007367
[14] George Necula et al., “CIL - infrastructure for C program analysis and
transformation,” http://manju.cs.berkeley.edu/cil/.
[15] I. Gurobi Optimization, “Gurobi optimizer reference manual,” 2015.
[Online]. Available: http://www.gurobi.com
[16] L. De Moura and N. Bjørner, “Z3: An efficient smt solver,” in
Proceedings of the Theory and Practice of Software, 14th International
Conference on Tools and Algorithms for the Construction and
Analysis of Systems, ser. TACAS’08/ETAPS’08. Berlin, Heidelberg:
Springer-Verlag, 2008, pp. 337–340. [Online]. Available: http://dl.acm.
org/citation.cfm?id=1792734.1792766
[17] Center for Hybrid and Embedded Software, UC Berkeley, “The PTARM
simulator,” http://chess.eecs.berkeley.edu/pret/.
[18] Mälardalen WCET Research Group, “The Mälardalen benchmark suite,”
http://www.mrtc.mdh.se/projects/wcet/benchmarks.html.
[19] F. Nemer, H. Cass, P. Sainrat, J. paul Bahsoun, and M. D. Michiel,
“Papabench: a free real-time benchmark,” in In WCET ?06, 2006.

TABLE V: Comparison of the results produced by the algorithm presented in this paper and in [11] for generating the top five
longest paths for a set of benchmarks. Column Predicted shows the length predicted by each algorithm. Column Measured
show the running time measured when run on the corresponding input. For our paper, we give “error bounds” of the form
k × D. The column Time shows the time it takes to generate the estimates and test cases. The largest measured value per each
benchmark is shown in bold.
Benchmark

altitude

stabilisation

automotive

cctask

irobot

sm

GameTime [11]
Predicted
Measured Time(s)
867
867
789
789
776
751
11.7
659
763
581
581
4387
3697
4293
4036
4290
3516
26.4
4286
3242
4196
3612
13595
8106
11614
9902
11515
11515
47.0
11361
5010
11243
11138
991
808
972
605
943
852
29.4
936
848
924
821
1462
1430
1459
1463
1457
1418
50.9
1454
1451
1454
1463
2553
2550
2551
2550
2536
2537
211.0
2534
2537
2532
2537

Our Algorithm
Predicted
Measured
909 ± 1.0 × 57.0
867
815 ± 1.0 × 57.0
758
732 ± 1.0 × 57.0
789
719 ± 1.0 × 57.0
737
638 ± 1.0 × 57.0
581
4303 ± 2.0 × 343.0
3599
4302 ± 2.0 × 343.0
4046
4285 ± 2.0 × 343.0
3944
4284 ± 2.0 × 343.0
3516
4248 ± 2.0 × 343.0
3697
11824 ± 2.0 × 1116.0
10982
11696 ± 2.0 × 1116.0
10657
11424 ± 2.0 × 1116.0
10577
11338 ± 2.0 × 1116.0
11515
9830 ± 2.0 × 1116.0
9263
870 ± 2.0 × 73.0
861
869 ± 2.0 × 73.0
858
866 ± 2.0 × 73.0
897
865 ± 2.0 × 73.0
897
861 ± 2.0 × 73.0
873
1451 ± 2.0 × 37.0
1406
1450 ± 2.0 × 37.0
1411
1449 ± 2.0 × 37.0
1411
1448 ± 2.0 × 37.0
1411
1448 ± 2.0 × 37.0
1464
2552 ± 21.81 × 0.2
2550
2551 ± 21.81 × 0.2
2550
2536 ± 21.81 × 0.2
2537
2536 ± 21.81 × 0.2
2537
2531 ± 21.81 × 0.2
2537

Time(s)

14.4

77.2

93.8

138.4

269.0

3290.2

