A simple Eva tutorial, part 1

(with the collaboration of T. Antignac, Q. Bouillaguet, F. Kirchner and B. Yakobowski)

This is the first of a series of posts on a new Eva tutorial primarily aimed at beginners (some of the later posts contain more advanced content).

Reminder: Eva is the new name of the Value analysis plug-in.

There is a Value tutorial on Skein-256 that is part of the Value Analysis user manual. The present tutorial is complementary and presents some new techniques available in Frama-C. If you intend to use Eva, we recommend you read the Skein-256 tutorial as well because it details several things that will not be repeated here. (However, it is not required to have read the Skein-256 before this one.)

The source code used in this tutorial is the version 0.3 of Monocypher, a C99-conformant cryptographic library that also includes a nice test suite.

Note: newer versions of Monocypher are available! For this tutorial, please ensure you download version 0.3, otherwise you will not obtain the same behavior as described in this tutorial.

Future posts will include more advanced details, useful for non-beginners as well, so stay tuned!

Starting with Frama-C/Eva

This tutorial will use Monocypher’s code, but it should help you to figure out how to analyze your code as well. First and foremost, it should help you answer these questions:

1. Is my code suitable for a first analysis with Frama-C/Eva?
2. How should I proceed?

(Un)Suitable code

There are lots of C code in the wild; for instance, searching Github for language:C results in more than 250k projects. However, many of them are not suitable candidates for a beginner, for reasons that will be detailed in the following.

Note that you can analyze several kinds of codes with Frama-C/Eva. However, without previous experience, some of them will raise many issues at the same time, which can be frustrating and inefficient.

Here is a list of kinds of code that a Frama-C/Eva beginner should avoid:

1. Libraries without tests

   Eva is based on a whole-program analysis. It considers executions starting from a given entry point. Libraries without tests contain a multitude of entry points and no initial context for the analysis. Therefore, before analyzing them, you will have to write your own contexts¹ or test cases.

2. Command-line tools that rely heavily on the command-line (e.g. using getopt), without test cases.

   Similar to the previous situation: a program that receives all of its input from the command-line behaves like a library. Command-line parsers and tools with complex string manipulation are not the best use cases for the Eva’s current implementation. A fuzzer might be a better tool in this case (though a fuzzer will only find bugs, not ensure their absence). Again, you will have to provide contexts¹ or test cases.

3. Code with lots of non-C99 code (e.g. assembly, compiler extensions)

   Frama-C is based on the C standard, and while it includes numerous extensions to handle GCC and MSVC-specific code, it is a primarily semantic-based tool. Inline assembly is supported syntactically, but its semantics needs to be given via ACSL annotations. Exotic compiler extensions are not always supported. For instance, trying to handle the Linux kernel without previous Frama-C experience is a daunting task.

4. Code relying heavily on libraries (including the C standard library)

   Frama-C ships with an annotated standard library, which has ACSL specifications for many commonly-used functions (e.g. string.h and stdlib.h). This library is however incomplete and in some cases imprecise². You will end up having to specify and refine several functions.

¹ A context, here, is similar to a test case, but more general. It can contain, for instance, generalized variables (e.g. by using Frama_C_interval or ACSL specifications).

² A balance is needed between conciseness (high-level view), expressivity, and precision (implementation-level details). The standard library shipped with Frama-C tries to be as generic as possible, but for specific case studies, specialized specifications can provide better results.

Each new version of Frama-C brings improvements concerning these aspects, but we currently recommend you try a more suitable code base at first. If your objective is to tackle such a challenging code base, contact us! Together we can handle such challenges more efficiently.

This explains why Monocypher is a good choice: it has test cases, it is self-contained (little usage of libc functions), and it is C99-conforming.

The 3-step method

In a nutshell, the tutorial consists in performing three steps:

1. Parsing the code (adding stubs if necessary);
2. Running Eva with mostly default parameters (for a first, approximated result);
3. Tuning Eva and running it again.

The initial parsing is explained in this post, while the other steps will be detailed in future posts.

General recommendations

Before starting the use of Frama-C, we have some important general recommendations concerning the Eva plug-in:

1. DO NOT start with the GUI. Use the command-line. You should consider Frama-C/Eva as a command-line tool with a viewer (the GUI). The Frama-C GUI is not an IDE (e.g. you cannot edit code with it), and Eva does not use the GUI for anything else other than rendering its results.
2. Use scripts. Even a simple shell script, just to save the command-line options, is already enough for a start. For larger code bases, you will want Makefiles or other build tools to save time.
3. Use frama-c -kernel-help (roughly equivalent to the Frama-C manpage) and frama-c -value-help to obtain information about the command-line options. Each option contains a brief description of what it does, so grepping the output for keywords (frama-c -kernel-help | grep debug for instance) is often useful. Otherwise, consider Stack Overflow - there is a growing base of questions and answers available there.
4. Advance one step at a time. As you will see, the very first step is to parse the code, and nothing else. One does not simply run Eva, unless he or she is very lucky (or the program is very simple). Such precautions may seem excessive at first, but being methodical will save you time in the long run.

Parsing the code

Often overlooked, this step is erroneously considered as “too simple” (“just give all files to the command-line!”). In a few cases, it is indeed possible to run frama-c *.c -val and succeed in parsing everything and running Eva.

When this does not work, however, it is useful to isolate the steps to identify the error. Here are some general recommendations:

1. Start with few files, and include more when needed

   Note that parsing may succeed even if some functions are only declared, but not defined. This will of course prevent Eva from analyzing them. If so, you may have to return to this step later, adding more files to be parsed.

2. Ensure that preprocessor definitions and inclusions are correct

   Several code bases require the use of preprocessor definitions (-D in GCC) or directory inclusions (-I in GCC) in order for the code to be correctly preprocessed. Such information is often available in Makefiles, and can be given to Frama-C using e.g. -cpp-extra-args="-DFOO=bar -Iheaders".

   -cpp-extra-args is the most useful option concerning this step. It is used in almost every case study, and often the only required option for parsing. Note: old releases of Frama-C did not have this option, and -cpp-command was recommended instead. Nowadays, -cpp-command is rarely needed and should be avoided, because it is slightly more complex to use.

3. Make stubs for missing standard library definitions

   Frama-C’s standard library is incomplete, especially for system-dependent definitions that are not in C99 or in POSIX. Missing constants, for instance, may require the inclusion of stub files (e.g. stubs.h) with the definitions and/or the ACSL specifications. A common way to include such files is to use GCC’s -include option, documented here.

4. Save the result

   Use Frama-C’s -save/-load options to avoid having to reparse the files each time. There is no default extension associated with Frama-C save files, although .sav is a common choice. For instance, running:

   frama-c <parse options> -save parsed.sav

   will try to parse the program and, if it succeeds, will save the Frama-C session to parsed.sav. You can then open it in the GUI (frama-c-gui -load parse.sav), to see what the normalized source code looks like, or use it as an input for the next step.

Reminder: for the Eva plug-in, the GUI is not recommended for parametrizing/tuning an analysis. It is best used as a viewer for the results.

The default output of Eva is rather verbose but very useful for studying small programs. For realistic case studies, however, you may want to consider the following options:

• -no-val-show-progress: does not print when entering a new function. This will be the default in Frama-C 15 (Phosphorus);

• -value-msg-key=-initial-state: does not print the initial state;

• -value-msg-key=-final-states: does not print the final states of the analysis.

Note the minus symbols (-) before initial-state and final-states. They indicate we want to hide the messages conditioned by these categories.

Parsing monocypher

As indicated above, the naive approach (frama-c *.c) does not work with monocypher:

$ frama-c *.c

[kernel] Parsing FRAMAC_SHARE/libc/__fc_builtin_for_normalization.i (no preprocessing)
[kernel] Parsing monocypher.c (with preprocessing)
[kernel] Parsing more_speed.c (with preprocessing)
[kernel] syntax error at more_speed.c:15:
         13
         14    // Specialised squaring function, faster than general multiplication.
         15    sv fe_sq(fe h, const fe f)
               ^^^^^^^^^^^^^^^^^^^^^^^^^^
         16    {
         17        i32 f0 = f[0]; i32 f1 = f[1]; i32 f2 = f[2]; i32 f3 = f[3]; i32 f4 = f[4];

The first line is always printed when Frama-C parses a source file, and can be ignored.

The second line indicates that monocypher.c is being parsed.

The third line indicates that more_speed.c is now being parsed, implying that the parsing of monocypher.c ended without issues.

Finally, we have a parsing error in more_speed.c, line 15. That line, plus the lines above and below it, are printed in the console.

Indeed, the file more_speed.c is not a valid C source (sv is not a type defined in that file, and it does not include any other files). But this is not an actual issue, since more_speed.c is not part of the library itself, simply an extra file (this can be confirmed by looking into the makefile). Thus we are going to restrict the set of files Frama-C is asked to analyze.

Note: Frama-C requires the entire program to be parsed at once. It may be necessary to adapt compilation scripts to take that into account.

We also see that the rule for building monocypher.o includes a preprocessor definition, -DED25519_SHA512. We will add that to our parsing command, which will then become:

frama-c test.c sha512.c monocypher.c -cpp-extra-args="-DED25519_SHA512" -save parsed.sav

The lack of error messages is, in itself, a resounding success.

The first part of this tutorial ends here. See you next week!

For now, you can start reading the Skein-256 tutorial available at the beginning of the Eva manual. Otherwise, if you already know Eva (and still decided to read this), you may try to find some undefined behavior (UB) in Monocypher 0.3!

Hint: There is indeed some UB, although it does not impact the code in any meaningful way. At least not with today’s compilers, maybe in the future… and anyway, it has been fixed in the newer releases of Monocypher.