Coverity Extend™ Language Reference

Coverity Prevent™ checkers analyze code by traversing the statements and subexpressions of that code, matching each tree for properties the checker cares about, and acting when it finds those matches.

Coverity Extend is a language for defining Coverity Prevent checkers. The interesting parts of a checker are the rules for matching, and the actions to take on a match. The rest of the checker are infrastructure and boilerplate; the goal of Coverity Extend is to take care of those details for you and to make the task of writing match rules and actions as simple as possible.

Accordingly, the Coverity Prevent back end takes care of all the details up to and including traversing the code. It presents an Coverity Extend checker with the trees as it encounters them, and all a checker needs to do is define what to do when it sees those trees.

Coverity Extend is currently implemented as a set of C++ base classes for checkers, C++ support classes and functions for use inside the checker callbacks, and macros which abstract as much as possible the implementation details of checkers. Therefore in the current implementation, Coverity Extend checkers can include any valid C++ code before and after the checker definition, as well as within each callback function. This is done to minimize the learning curve on Coverity Extend -- since you are writing checkers for C++ code, you probably already know C++. However, checkers should not require very complicated C++ code, and for the most part once you understand patterns (see Chapter 3, Patterns) it will be very straightforward to write most checkers.

Coverity Extend's primary design goal is to be as easy to use as possible. It must be easy to express the rules we wish to check; if checkers are complicated they become error prone, which diminishes their value. Furthermore, Coverity Extend users typically are experts about the code they wish to check, but not necessarily experts on static source code analysis. The mechanics of writing a checker ought to be intuitive to allow the user to apply their expertise about the domain being checked without being obscured by the details of source code analysis.

This ease of use does conflict at times with performance and expressive power. Thus, Coverity Extend checkers are often slightly slower than the built in Coverity Prevent checkers, and do not have access to some of the more complicated and esoteric capabilities of the Coverity Prevent analysis engine. The last bit of speed and power/precision would greatly increase the complexity of Coverity Extend and make it unwieldy to use.

The following is a list of rules which can be checked with Coverity Extend. This is only a small list, not nearly an exhaustive one, meant to inspire ideas about what kinds of checkers might be helpful for a particular user.

There are two things you need in order to use Coverity Extend: the Coverity Extend compiler, and the extend directory. Each is simply a compressed directory that can be uncompressed to the appropriate place and used as-is. Both directories can be placed anywhere, independent of the Coverity Prevent installation.

The Coverity Extend compiler is a regular C++ compiler with all the standard headers needed to compile a checker. We package this to ensure that checkers are compiled with the correct version of these headers, making installation and use of Coverity Extend as simple as possible.

The extend directory consists of the following subdirectories:

The extend directory also contains a script, build-checker (build-checker.bat for Windows), which will compile a single Coverity Extend checker. Its usage is described in Section 1.4, “Creating a Coverity Extend™ checker”.

The easiest way to create an Coverity Extend checker is by copying an existing sample checker and modifying it to suit your needs. You can then compile the checker using the build-checker script (build-checker.bat on Windows) found in the top level extend directory. It expects one argument: the name of the checker source file without the extension (and the script will assume the file has a .c extension).

Your checkers may be located anywhere, as long as the build script is run from the directory where the checker source file is.

The following enviroment variables affect how the build script works, and are required by the script.

The script will compile the checker and leave the executable in the current directory. This checker works the same way the main PREVENT integrated checker, cov-analyze[-cxx], works, and should be added to the PREVENT usage pipeline either instead of or immediately following running the integrated checker. Please see the PREVENT documentation for more details.

Below is a simple checker that reports every time a parameter is dereferenced in a program:

#include "extend-lang.h"

START_EXTEND_CHECKER( param_deref, simple );

ANALYZE_TREE()
{
    Parm p;

    if( MATCH( *p ) ) {
        OUTPUT_ERROR( "dereferenced parameter" << p );
    }
}

END_EXTEND_CHECKER();

MAKE_MAIN( param_deref )

This checker includes all the essential elements of a Coverity Extend program:

When writing Coverity Extend checkers, be sure to use the commands as described in this section. Do not expand any macros, and do not use any calls except as described. Doing so will decrease compatibility with future versions of Coverity Extend, which may change how the commands are implemented.

All pieces of the checker definition must appear between START_EXTEND_CHECKER and END_EXTEND_CHECKER. Typically this consists only of the checker handler functions. You can also define functions which will be callable by the handler functions, as well as variables whose values will persist between callbacks into the checker. However, the use of the values of such variables is discouraged: due to how the traversal works, these values may not be what you would expect after branches and such. Any data you need to persist between checker callbacks should be placed in the store (see Chapter 4, The Store for more details).

START_EXTEND_CHECKER takes two arguments: the name of the checker and its type. Both strings are unquoted. The name should be unique among all checkers which might run at the same time. The type should be one of the types described in Chapter 6, Coverity Extend™ Checker Types. Different types give different levels of functionality and complexity. The more complex checker types can detect a broader range of errors because they perform a more sophisticated analysis, but they are also harder to use and take more time to run. It's generally best to use the simplest checker type which includes all the functionality that your checker needs.

END_EXTEND_CHECKER takes no arguments.

Both the start and end statements must end with a semicolon.

These functions are the heart of the checker. The system will use these callbacks to handle various events during the traversal. Your checker will want to find events that are significant to the condition being checked, and take appropriate actions to deal with those events.

What exactly constitutes "appropriate action" depends on which callback occurs, which checker type you are using, and what your checker is looking for. This section describes the various callbacks, while later sections will discuss patterns (which are vital to analyzing each tree), the store (which allows the checker to track information between expressions), and other things you can do in the analysis functions.

The first three functions are the main analysis functions. The five functions after are used for initializing and finalizing the analysis. In general most of the interesting work will happen in the analysis functions, particularly ANALYZE_TREE, and many checkers don't need to use the initializer and finalizer functions.

// assume that int mode and bool use_mangled are member vars
// This function will recognize the following options:
// - mode:<mode_value>
// - use_mangled
// The analysis functions will look at the member variables to
// alter behavior during the analysis.

INIT_OPTIONS()
{
    mode = 0;
    use_mangled = false;
}

HANDLE_OPTION()
{
    CHECK_OPTION( "mode" ) {
        mode = atoi( OPTION_VALUE );
        OPTION_HANDLED();
    }
    CHECK_OPTION( "use_mangled" ) {
        use_mangled = true;
        OPTION_HANDLED();
    }
    OPTION_NOT_HANDLED();
}

In addition to the checker definition, an Coverity Extend program needs a main function which sets up the system and runs the analysis using the Coverity Extend checker. For the majority of checkers, MAKE_MAIN is adequate for doing this: it creates a main function which will properly run the checker. However, some Coverity Extend programs may have slightly different needs, so other variants are provided for such programs.

Pattern matching is the core operation of a Coverity Extend checker. The bulk of a checker will be rules that specify an action to take when the input tree matches a certain pattern. Patterns denote types or properties of trees, and a tree matches a pattern if the tree is of that type or has that property. In the example above, Parm denotes parameters; that pattern type matches all trees that are uses of a parameter.

Note that Parm is a type of pattern, not an actual pattern itself. You must create pattern objects to do the matching. In the example above, Parm p; declares p as a Pattern object of type Parm and the matching is actually done with the object, not the type.

After a successful match, the pattern object will have additional information about the tree that was matched, which can be accessed through various accessor methods of the pattern classes. This is what makes it possible, for example, to pass p into the stream operator: after matching, p will have information about the parameter it matched, and patterns will print out the name of the thing matched when shifted onto a stream.

The most powerful feature of patterns is that they can be composed in a very natural way to build more complicated patterns. The syntax for building patterns mirrors C++ syntax. The example above didn't match parameters, but rather dereferences of a parameter. In C++, the unary operator * is the derefence operator, so in Coverity Extend, the unary operator * builds a new pattern which matches the derefence of something that matches the operand pattern. Therefore, *p denotes a pattern which matches the dereference of something that matches p, or in other words the dereference of a parameter.

All C++ operators can be used to build new patterns with the appropriate meaning. There are also pattern building functions that mirror many keywords, which differ only in capitalization (e.g., to build a pattern that matches an if statement, you can use the function If). There are also functions which build patterns that match more general concepts, such as whether a tree contains (or is within) another tree that matches some other pattern. For example, you can use this to see if a parameter is used within a function call, or if an assignment expression contained a global variable anywhere in its right hand side. As you can see, it is possible to get extremely precise patterns in this way.

After a successful match, patterns will know which tree they matched. This allows you to use matched patterns in places that expect trees; patterns will automatically convert themselves to a tree as needed. This also will allow you to use a pattern's accessor functions to get information about the matched tree. These functions should not be used before a match. Finally, a matched pattern may be written to an output stream. This will result in the text of the matched tree being appended to the stream.

You should use patterns with one of the following operations to perform the match. All of the following operations are boolean expressions (true when the match is successful, false if not).

Here are descriptions of the most common pattern types, with some information on how they can be used. Full information about patterns can be found in headers/accessors/extend-patterns.h.

Parm parm;
Pointer ptr;
DECL_PAT( pp, And( ptr, parm ) );
Any any;

if( MATCH( *pp = any ) ) {
    // ...
}

Fun fn;
Const_int ci;

if( MATCH( fn( _, _ ) ) ) {
    // matches any function call with two arguments of any sort
}

if( MATCH( fn( ci ) ) ) {
    // matches any function call with a single argument which is a constant integer
}

if( MATCH( fn ) ) {
    // matches any function call with zero arguments
}

Patterns provide much of the power behind Coverity Extend, but they have a major limitation: they can only recognize properties within a single expression. In order to find properties which span more than one line of code, a checker needs to maintain state between calls to the ANALYZE_* functions.

There are three levels of state tracking that make sense in checkers: global to the entire analysis, per-function, and per-path. Each checker will only analyze one function at a time, so global and per-function state can be implemented with checker member variables and using CHECKER_INIT/CHECKER_FINAL and FUNCTION_INIT/FUNCTION_FINAL to initalize/finalize this state. However, this doesn't work well for per-path state, because while there are many paths being analyzed at once and therefore many sets of per-path state, there is only one checker. Per-path state tends to be the most commonly used and most useful of the three kinds of state, so we need a convenient and efficient means for tracking it.

We do this with the store. The store is essentially a map which allows a checker to associate state information with any variable or expression. Each ANALYZE_* function has access to the store and can query it for the state of a tree as well as add or modify state for a tree. The traversal infrastructure handles all the details of tracking the different per-path sets of state, such as managing which state corresponds to which path.

Suppose we wanted to detect the use of a pointer after it has been freed. Since the free and the use will most likely occur in different expressions, we need the store to write such a checker. Below is a version of how you might start writing this checker:

#include "extend-lang.h"

START_EXTEND_CHECKER( basic_use_after_free, int_store );

ANALYZE_TREE()
{
    Fun freecall( "free" );
    Pointer p;

    if( MATCH( freecall( p ) ) ) {
        SET_STATE( p, 1 );
        ADD_EVENT( p, "free", "freed pointer " << p );
    }
    else if( MATCH( *p ) ) {
        if( MATCH_STATE( p, 1 ) ) {
            COMMIT_ERROR( p, "deref", "dereferenced free pointer " << p );
        }
    }
    else if( MATCH( p = _ ) ) {
        CLEAR_STATE( p );
    }
}

END_EXTEND_CHECKER();

MAKE_MAIN( basic_use_after_free )

Note that the above checker, as its name implies, catches only basic instances of use after free. It doesn't handle aliasing, interprocedural analysis, or violations other than an explicit dereference. While it would be possible to handle all those details in a Coverity Extend checker, doing so would obscure the illustrative nature of this example.

The rest of this section will offer a brief explanation of this checker. Section 4.3, “Store Operations” will describe in detail all the operations used by this checker.

The first thing to notice is the type of this checker: int_store. This specifies a checker which uses a store whose state information for each tree consists of an integer. In other words, for every variable or expression we encounter during a match, we can track a single integer for it, which we will be able to access in a later match. While it may seem limited, in practice a single integer is sufficient for most checkers. You can often enumerate the various states a variable can be in, and encode that information accordingly. For this checker, we will use the value 1 to mean that the pointer is known to be a freed pointer. Any other value, or absence of state for that pointer, signifies that the pointer is not necessarily free.

A use after free violation is defined as a free of a pointer followed by a use of that pointer. In the above checker, the only use we will worry about is a direct dereference. Accordingly, the first two patterns the checker is concerned with are calls to free, and pointer dereferences.

Whenever the checker sees a call to free on a pointer, it remembers that the pointer was freed by setting the state of the pointer to 1, using the SET_STATE command. Additionally, it annotates the line of code where the free happened with a comment that the pointer was freed, using ADD_EVENT. If an error is later generated relating to this pointer, all such annotations will be part of the error report.

On the other end, whenever the checker sees a pointer dereference, it needs to ask the store whether the state for the pointer has previously been set to 1, using MATCH_STATE. If so, then we know that this pointer has been freed, so we generate an error report (with an additional annotation for the location where the error occurs) using COMMIT_ERROR.

However, there's one very important case to consider: what if, between the free and the dereference, the pointer is reassigned? Then the dereference is not necessarily of a freed pointer, yet with only the two match actions described above, we will still generate an error. We need a match action that will unmark a pointer since it is no longer freed. The third match action does this using CLEAR_STATE. We could also "unmark" the pointer by setting its state to something other than 1. However, CLEAR_STATE both removes the state of the pointer altogether, and also removes all annotations for that pointer. In other words, CLEAR_STATE truly resets the state of the expression to be as if the checker had never matched that expression before.

This section provides details for commands which interact with the store.

#include "extend-lang.h"

START_EXTEND_CHECKER( basic_leak, int_store );

ANALYZE_TREE()
{
    Fun malloc( "malloc" );
    Fun free( "free" );
    LocalVar lv;
    AnySubpart lv_sp( lv );
    DECL_PAT( non_local, Not( lv_sp ) );
    
    if( MATCH( lv_sp = malloc( _ ) ) ) {
        SET_STATE( lv_sp, 1 );
        ADD_EVENT( lv_sp, "alloc", "Allocation assigned to " << lv_sp );
    }

    else if( MATCH( free( lv_sp ) ) ) {
        CLEAR_STATE( lv_sp );
    }
}

ANALYZE_END_OF_PATH()
{
    tree t;
    int v;
    FOREACH_IN_STORE( t, v ) {
        COMMIT_ERROR( t, "leaked", t << " was not freed before the end of path" );
    }
}

END_EXTEND_CHECKER();

MAKE_MAIN( basic_leak )

The analysis engine guarantees that every time ANALYZE_TREE or ANALYZE_COND is called, the store will look as if the analysis has examined the entire path currently being analyzed up to the current tree from the start in approximate execution order. In other words, if a checker respects the store abstraction and doesn't use global, static, or class variables to hold state information about the analysis, then the checker may behave as if the analysis were traversing all paths completely and in order, which is the conceptually easy and intuitive thing to do for checker writers. Basically, match actions should be written as if every preceding tree in the function has already been analyzed and the store has been modified accordingly.

Under the hood, it isn't quite that simple. If the analysis engine were to actually traverse every path in its entirety, it would be performing a lot of redundant analysis (for blocks of code which are common to all paths) and run significantly slower. Instead, the engine identifies common blocks and analyzes them only once, and generally only analyzes trees multiple times if the analysis will result in different state each time. This means that statements and subexpressions which are adjacent in the code will not necessarily be analyzed in consecutive calls to ANALYZE_TREE. However, the store hides all this complexity; this is the main reason the store is necessary.

We described the guarantee as looking like "approximate execution order". What this means is that, from the store's point of view, subexpressions are handled before the statement itself is handled, and these are done in almost the same order as they would happen in the compiled program. There are two main reasons why it might not be exactly the same. In cases where the language does not specify the execution order (for example, order of evaluation of function arguments) the traversal order may not match a particular compiler's execution order. Additionally, in some situations the analysis artificially inserts and reorders some trees that aren't explicitly obvious in the code (for example, variables declared in loop conditions are transformed to declarations before the loop). These transformations will slightly alter how the code looks but results in trees which are functionally equivalent.

These functions return information about the function being currently analyzed. They may be used in the three analysis functions.

The following functions get information about a particular tree. There are three ways to get a tree:

When defining a Coverity Extend checker, you must specify its type as the second argument to START_EXTEND_CHECKER. Different types provide different levels of complexity and access to different functionality. This is done for two reasons: it allows Coverity Extend users to only choose a type best suited for the current checker, so that the user need only deal with as much complexity as necessary; and it also allows Coverity to introduce new checker types as we develop them without affecting already written Coverity Extend checkers.

The types are listed roughly in order of complexity and running time. The ones higher in the list are easier to use and run faster, but are more limited in the sorts of analyses they can do. When writing a checker, select the simplest type that is adequate for your analysis.

This is a very simple checker type. It maintains no state information between analysis callbacks, does not track values for variables, and does no interprocedural analysis. Basically, simple checkers will see every tree once, with no context about what's going on in the function when that tree is encountered. These checkers can be used to perform search operations: for example, searching for all parameter dereferences as seen above, searching for all assignments to the integer constant 0, or all local variable declarations which are of types which exceed a certain size.

This is the simplest checker type which uses a store (see Chapter 4, The Store). The store in this case allows the checker to associate an integer with a particular tree. This checker type does not perform interprocedural analysis. int_store checkers can be used to find ordering properties within a single function (e.g., calls to function A must be followed by calls to function B) as well as properties involving integer values that span multiple lines (e.g., pointers may not be assigned to dynamically allocated blocks of a size which is not a multiple of the size pointed to).