Discussion:
Question about ELOC counting in the KLEE paper
(too old to reply)
Edmund Wong
2014-09-03 21:05:10 UTC
Permalink
Hi KLEE authors,

We are doing research based on KLEE. We followed the tutorials to use gcov
for measuring coverage. But we don't know how to measure the raw size of
test subjects (including library code) in the way mentioned in the KLEE
paper (Section 5.1):

However, we do include library code when measuring the raw size of the
application: KLEE must successfully handle this library code (and gets no
credit for doing so) in order to exercise the code in the tool itself. We
measure size in terms of executable lines of code (ELOC) by counting the
total number of executable lines in the final executable after global
optimization, which eliminates uncalled functions and other dead code. This
measure is usually a factor of three smaller than a simple line count
(using wc -l).
We have tried to do the following:

We first do a fresh build of Coreutils with gcov profiling. Then we invoke
the target program, e.g., 'ls', for a couple of times. Gcov profiling
information is logged into a .gcda file for each source code compiled into
'ls'. We then invoke gcov on all those .gcda files (in lib/ and src/) and
sum up the ELOC of their corresponding source files. However, this result
doesn't agree with Fig. 4 in the KLEE paper (Section 5.2):

Figure 4 breaks down the tools by executable lines of code (ELOC),
including library code the tool calls. While relatively small, the tools
are not toys — the smallest five have between 2K and 3K ELOC, over half
(52) have between 3K and 4K, and ten have over 6K.
E.g., for 'uptime', we get its ELOC as ~1200, which is far less than 2K.

Is anything wrong with the above steps? Could you tell us the method/tool
used to count ELOC "in the final executable after global optimization"?
Thanks a lot!

Edmund Wong
Cristian Cadar
2014-09-15 20:12:38 UTC
Permalink
Hi Edmund,

If I recall correctly, the global optimizations mentioned in the paper
were those done by LLVM -- since KLEE operates at the LLVM level, it
makes sense to consider those, and not the ones done by gcc. The
version of LLVM used in the experiments was somewhere around LLVM 2.2
and 2.3, which I'm not sure how aggressive it is in terms of dead code
elimination. Of course, since dead code elimination is a conservative
optimization, those numbers are an overestimate of the actual sizes. My
co-authors might have more details; unfortunately, I don't have the
script that we used to generate that figure anymore.

Best,
Cristian
Post by Edmund Wong
Hi KLEE authors,
We are doing research based on KLEE. We followed the tutorials to use
gcov for measuring coverage. But we don't know how to measure the raw
size of test subjects (including library code) in the way mentioned in
However, we do include library code when measuring the raw size of
the application: KLEE must successfully handle this library code
(and gets no credit for doing so) in order to exercise the code in
the tool itself. We measure size in terms of executable lines of
code (ELOC) by counting the total number of executable lines in the
final executable after global optimization, which eliminates
uncalled functions and other dead code. This measure is usually a
factor of three smaller than a simple line count (using wc -l).
We first do a fresh build of Coreutils with gcov profiling. Then we
invoke the target program, e.g., 'ls', for a couple of times. Gcov
profiling information is logged into a .gcda file for each source code
compiled into 'ls'. We then invoke gcov on all those .gcda files (in
lib/ and src/) and sum up the ELOC of their corresponding source files.
However, this result doesn't agree with Fig. 4 in the KLEE paper
Figure 4 breaks down the tools by executable lines of code (ELOC),
including library code the tool calls. While relatively small, the
tools are not toys — the smallest five have between 2K and 3K ELOC,
over half (52) have between 3K and 4K, and ten have over 6K.
E.g., for 'uptime', we get its ELOC as ~1200, which is far less than 2K.
Is anything wrong with the above steps? Could you tell us the
method/tool used to count ELOC "in the final executable after global
optimization"? Thanks a lot!
Edmund Wong
_______________________________________________
klee-dev mailing list
https://mailman.ic.ac.uk/mailman/listinfo/klee-dev
Loading...