DOKK Library

Frama-C’s metrics manual 20.0

Authors Boris Yakobowski Richard Bonichon

License CC-BY-SA-4.0

Plaintext
Metrics
           Frama-C’s metrics plug-in
                               20.0 (Calcium)




                        Richard Bonichon & Boris Yakobowski


This work is licensed under a Creative Commons “Attribution-
ShareAlike 4.0 International” license.


              CEA LIST, Software Reliability Laboratory, Saclay, F-91191




©2011–2019 CEA LIST
                                           CONTENTS




                                                                              Contents

1 Quick overview                                                                                 7
  1.1   Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    7
        1.1.1   Command-line options . . . . . . . . . . . . . . . . . . . . . . . . . . .       7
        1.1.2   Metrics and abstract syntax trees . . . . . . . . . . . . . . . . . . . . .      8
  1.2   Metrics on the normalized abstract syntax tree . . . . . . . . . . . . . . . . .         8
        1.2.1   Syntactic metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    8
        1.2.2   Graphical User interface . . . . . . . . . . . . . . . . . . . . . . . . . .     8
        1.2.3   Reachability coverage . . . . . . . . . . . . . . . . . . . . . . . . . . .     10
        1.2.4   Eva coverage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    10
  1.3   Metrics on the original abstract syntax tree . . . . . . . . . . . . . . . . . . .      12

2 Practical notes and comments                                                                  13
  2.1   Cyclomatic complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .     13
        2.1.1   Calculation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   13
        2.1.2   Practical notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   13
  2.2   Halstead complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .     14
        2.2.1   Calculation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   14
        2.2.2   Practical notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   15
  2.3   Eva coverage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    15




                                                5
                                                                            Chapter 1

                                                             Quick overview

The Metrics plug-in computes complexity measures on C source code. It can operate either
on Frama-C’s normalized abstract syntax tree (AST) or on the original source code.


1.1      Description

1.1.1     Command-line options

The complete list of command-line options can be obtained by:
        % frama-c -metrics-help

Let us now detail some of them:

-metrics is a necessary switch to activate the plug-in. It also triggers the computation of
    syntactic metrics (slocs, number of statements of certain types, ...) on the normalized
    AST.

-metrics-by-function also computes (and displays) the above metrics, but this time on a
    per-function basis.

-metrics-ast is used to choose the AST the metrics should be computed on. It can be either
    Frama-C’s normalized AST or the original AST. Section 1.1.2 covers this topic in some
    more details. How this affects the availability of metrics is discussed in Section 1.2 and
    1.3.

-metrics-output redirects metrics’ calculations to a file. The selection of the output is
    automatically detected from the extension of the output file. As of now, only .html or
    .txt outputs are supported.

-metrics-cover specifies a set of functions from which to compute a coverage estimate. This
    item is detailed in Section 1.2.4.

-metrics-eva-cover activates the Eva coverage estimation. This item is detailed in Section
    1.2.4.

-metrics-libc controls whether functions from Frama-C’s standard library are shown within
    the results. By default, this option is not set, and those functions are hidden.




                                              7
                                      CHAPTER 1. QUICK OVERVIEW



1.1.2     Metrics and abstract syntax trees

Frama-C analyses usually operate on its own internal normalized abstract syntax tree1 . The
normalization process adds for example missing return statements, transforms all loops into
while(1) { ... } statements, introduces some temporary variables... Although this normal-
ization process does not affect the semantic contents of the code, its syntactic counterpart is
indeed changed. It can therefore affect metrics computed from the source code.
However, Frama-C also keeps the original abstract syntax tree of the source as is. Even
though Frama-C’s analyses are usually centered around the normalized representation, some
facilities do exist to manipulate the other original AST.
Users of the Metrics plug-in can specify the nature of the AST from which the metrics should
be computed. Some metrics are available only for one AST representation.
The default behavior, as enabled by the -metrics switch, is to calculate syntactic metrics on
the normalized AST. Metrics available for each AST are the objects of Sections 1.2 and 1.3.



1.2      Metrics on the normalized abstract syntax tree

1.2.1     Syntactic metrics

Only cyclomatic numbers are available for the normalized AST. These are also available
through Frama-C’s graphical user interface (GUI) (see Section 1.2.2).
Let us calculate the cyclomatic complexity of the program of Figure 1.1 using the following
command 2 .
      % frama-c -metrics -metrics-by-function reach.c

The results are detailed in Figures 1.2 and 1.3. The output contains a summary, for each
function, of the number of assignments, function calls, exit points, declared functions (it
should always be 1), goto instructions, if statements, pointer dereferencings and lines of
code. The cyclomatic number of the function is also computed. Per-function results are
available only if the option -metrics-by-function is specified; otherwise only the “Syntactic
metrics” part of the output is shown (Figure 1.3). Note that these results can be printed to
a text or html file using the -metrics-output option.


1.2.2     Graphical User interface

Metrics on the normalized AST are also accessible through Frama-C’s GUI. Cyclomatic com-
plexity numbers are shown either globally on the left-hand side pane of the GUI, after left-
clicking the Measure button (see Figure 1.4), or for a chosen function (see Figure 1.5). To
access this functionality, you must right-click on the line where the function is defined to
make a menu appear, then left-click on Metrics as shown in the figure.
  1
    Note that the parsing machinery and the production of the abstract syntax trees originally come from
CIL (http://cil.sourceforge.net/).
  2
    frama-c -metrics -metrics-by-function -metrics-ast cil reach.c is also a valid command for this purpose.




                                                     8
             1.2. METRICS ON THE NORMALIZED ABSTRACT SYNTAX TREE




void (*bar) (int); void (*t[2])(int);

void baz (int j) { return; }

void (*t[2])(int)= {
  baz,
  0};

void foo (int k) {
  int i = 0;
  return ;
}

/∗ foo is unreachable since j is always 0; baz is not called ∗/
int main() {
   int j = 0;
  void (*(*pt)[2])(int) = &t;
   if (!j) {
      return 1;
  }
   else {
     bar = foo;
     bar (1);
      return 0;
  }
}

                       Figure 1.1: Source code for reach.c




                                        9
                                 CHAPTER 1. QUICK OVERVIEW




  Figure 1.2: Output of by-function syntactic metrics for the normalized AST of reach.c


     Figure 1.3: Output of global syntactic metrics for the normalized AST of reach.c




                     Figure 1.4: Metrics GUI: calculate global metrics

1.2.3   Reachability coverage

Given a function f, the reachability coverage analysis over-approximates the functions of the
program that can be called from f. On our example, to activate it on the functions main and
foo, one can use:
     % frama-c -metrics -metrics-cover main,foo reach.c

The results are displayed in Figure 1.6. The reachability coverage analysis is conservative.
For example, it considers that all function whose addresses are referenced within a reachable
function may be called. This explains why it considers that baz and foo are reachable from
the main function.


1.2.4   Eva coverage

The -metrics-eva-cover option can be used to compare the code effectively analyzed by Eva
with what Metrics considers reachable from the main function (wrt. the criterion described




                                             10
                    1.2. METRICS ON THE NORMALIZED ABSTRACT SYNTAX TREE




                  Figure 1.5: Metrics GUI: calculate metrics for a function



                         Figure 1.6: Reachability coverage for reach.c


in Section 1.2.3). The results of this option on our example are given in Figure 1.7. This
particular feature is activated by the following command:
     % frama-c -metrics -metrics-eva-cover reach.c


Syntactic reachability is an over-approximation of what is actually reachable by Eva. Thus,
the coverage estimation will always be equal to or less than 100%, especially if the source
code relies a lot on the use of function pointers.
For all functions that are considered syntactically reachable, but that are not analyzed by
Eva, the plug-in indicates the locations in the code where a call might have been analyzed.
In our example, this consists in the call to foo at ligne 24. Also, since the address of baz
is contained in the initializer of the array t (itself referenced in main), baz is considered as
callable; thus the plug-in signals the initializer of t as a possible calling point. Finally, the
plug-in displays the percentage of statements analyzed by Eva for each function.



                        Figure 1.7: Eva coverage estimate for reach.c




                                               11
                                CHAPTER 1. QUICK OVERVIEW




              Figure 1.8: Cyclomatic metrics on the original AST for reach.c


               Figure 1.9: Halstead metrics on the original AST for reach.c


1.3     Metrics on the original abstract syntax tree

Only syntactic metrics are available on the original AST. Both Halstead and cyclomatic
complexity are computed. Note that this part of the plug-in cannot be used through the
GUI.
      % frama-c -metrics -metrics-by-function -metrics-ast cabs reach.c

The effect is to calculate both cyclomatic and Halstead complexities for the argument files,
as shown in Figures 1.8 and 1.9 . The results for Halstead measures are only global while
cyclomatic numbers can be done on a per-function basis. Halstead measures also produce a
detailed account of the syntactic elements of the files.




                                            12
                                                                            Chapter 2

                              Practical notes and comments

2.1     Cyclomatic complexity

Cyclomatic complexity, also called conditional complexity was introduced by Thomas McCabe
[2] in 1976. It is a measure of the number of paths through a source code and represent the
complexity of the control-flow of the program.
The cyclomatic number of a source code has been shown to be weakly correlated to its number
of defects.


2.1.1   Calculation

Cyclomatic complexity is a notion defined on a directed graph. It can therefore be defined on
a program taken as its control-flow graph. For a directed graph, the cyclomatic complexity
C is defined as
                                     C = E − N − 2P
where E is the number of edges of the graph, N the number of nodes and P the number of
(strongly) connected components.
This notion of complexity is extended to deal with programs using the following formula

                                       C =π−s+2

where π is the number of decision points in the program and s the number of exit points.


2.1.2   Practical notes

Cyclomatic complexity can be computed on all abstract syntax trees in Frama-C. The re-
sulting complexity will nonetheless stay the same in both AST representations, as Frama-C’s
normalized AST does not add control-flow directives to the source code.
Prior to the computation of cyclomatic complexity, the plug-in gathers the following syntactic
information from the source code:

  • Number of lines of code (assuming one C statement equals one line of code);

  • Number of if statements;

  • Number of loops;




                                             13
                        CHAPTER 2. PRACTICAL NOTES AND COMMENTS



  • Number of function calls;

  • Number of gotos;

  • Number of assignments;

  • Numbers of exit points (return statements);

  • Number of functions declared;

  • Number of pointer derefencings.

  • Number of decision points (conditional statements (if) and expressions (? :), switch
    cases, lazy logical operators, loops).

These informations are computed both for the complete source code, and on a per-function
basis – except for the number of functions declared.
Cyclomatic complexity is then derived from these informations, both for the full code and
for each defined function.


2.2     Halstead complexity

Halstead complexity is as set of software metrics introduce by Maurice Halstead [1] in 1977.
The goal is to identify measurable properties of the code and to go beyond pure complexity
measures.


2.2.1   Calculation

Halstead complexity measures first need the following informations from the source code:

  • η1 is the number of distinct operators;

  • η2 is the number of distinct operands;

  • N1 is the total number of operators;

  • N2 is the total number of operands;

From the above informations, Halstead defines the following measures:

                Program vocabulary            η    η1 + η2
                Program length                N    N1 + N2
                Calculated program length     N̂   n1 × log2 η1 + η2 × log2 η2
                Volume                        V    N × log2 η
                Difficulty                    D    (η1 /2) × N2 /η2
                Effort                        E    D×V
                Time required to program      T    E/18
                Bugs                          B    E 2/3 /3000

Note that “Time required to program” is an estimate given in seconds.




                                              14
                                      2.3. EVA COVERAGE



2.2.2   Practical notes

To implement the measures defined in Section 2.2.1, it is necessary to define what the operands
and operators of the language are. For Frama-C, the target language is C and we define its
operands and operators as follows:

Distinct operands Identifiers and constants are operands, as well as type names and type
     specification keywords.

Distinct operators Storage class specifiers, type qualifiers, reserved keywords of C and
     other operators (+, ++, + =, ...) are considered as operators.

It is important to note that the measure of bugs delivered is considered under-approximated
for programs written in C.


2.3     Eva coverage

This part of the Metrics plug-in is thought of as a help for new code exploration with Frama-
C’s Eva plug-in. The first steps into a new code can be quite complicated and, more often
than not, Eva stops due to too much imprecision. This imprecision can have a lot of different
causes (body of library functions missing, imprecisions of reads in memory, . . . ).
The graphical user interface helps visualizing where Eva has stopped. The penetration esti-
mate of Metrics aims to complement that by giving a rough approximate of the percentage
of code that Eva has seen. This is especially interesting when comparing two runs of Eva on
the same code, after performing some tweaks and improvements to help Eva: one can thusly
quantify the added penetration due to the tweaks.




                                              15
                                      BIBLIOGRAPHY




                                                               Bibliography

[1] Maurice H. Halstead. Elements of Software Science. Elsevie North-Holland, 1977.

[2] Thomas J. McCabe. A complexity measure. IEEE Trans. Software Eng., 2(4):308–320,
    1976.




                                           17