Developing secure code using SPARK: Part 2 – How to use it

Benjamin M. Brosgol, AdaCore

June 03, 2013

Benjamin M. Brosgol, AdaCoreJune 03, 2013

In Part 1 of this two-part series, we summarized the basic issues with software security and explained how the programming language choice can affect the ease or difficulty of demonstrating that a system meets security requirements such as those defined in the Common Criteria. General purpose languages including C, C++, Ada, and Java are too complex to satisfy the reliability and analyzability requirements at the highest security levels; subsetting is needed. In this second part in the series one such language subset—SPARK*— is described and how it can be used to develop high-security systems cost-effectively.

SPARK1 is based on the principle of Correctness by Construction, an efficient and mathematically rigorous approach to software development that avoids defects, or detects and removes them quickly. Correctness by Construction involves strong static verification as the system is being implemented and allows the cumulative development of certification-oriented evidence.

SPARK is an Ada subset augmented with a notation for specifying contracts (annotations in the form of Ada comments) that are analyzed statically. The current version of SPARK is based on Ada 2005 and includes a large portion of Ada’s static semantic facilities such as packages/ encapsulation, subprograms, most types, and some Object-Oriented Programming features, as well as the Ravenscar tasking profile.2 Features such as exceptions, goto statements, and dynamic binding are excluded because they would complicate formal verification; other features such as access types (pointers), dynamically sized arrays, and recursion are excluded because they would interfere with time or space predictability. Upcoming versions of the SPARK language and toolset are adding support for generic templates.
Despite the restrictions, large real-world applications can be (and have been) programmed in SPARK. Because of the restrictions, developers can rigorously demonstrate security-related properties such as freedom from run-time exceptions, absence of variables that are read before being assigned, and, for a multi-tasking application, absence of variables that are shared but unprotected.

The behavior of every SPARK program is unambiguous; in cases in which the Ada rules offer implementation flexibility, the choice will have no bearing on the program’s effect. Ada does not dictate the order of evaluation in expressions, for example, and in some cases the value may depend on the order chosen. The SPARK rules prevent functions from having side effects, however, so even though different evaluation orders are permitted, the end result will be the same.

SPARK contracts fall into two categories: core annotations and proof annotations. The core annotations relate to data flow and information flow, and inter-module dependences; for example, which global variables are referenced by a subprogram, and how the values of a procedure’s “out” or “in out” parameters are derived.

The proof annotations are optional and may be used for mathematically proving various dynamic properties of the program, such as a subprogram’s pre- and postconditions. In the most general scenario, a proof can demonstrate compliance of the program with respect to its formal specification as expressed in a language such as Z.3

SPARK can help achieve high assurance even without such a formal specification, however; the ability to prove that an exception will not be raised at run time—for example no stack overflow or array bounds violation—is by itself a major advance.

A SPARK example4 of a linear search procedure that updates a counter each time a match is found illustrates both kinds of annotations:
package Search
  --# own Counter;
  --# initializes Counter;

  Counter : Natural := 0;

  type IntArray is array (Integer range <>) of Integer;

  procedure Linear_Search
    (Table : in IntArray;
     Value : in Integer;
     Found : out Boolean;
     Index : out Integer);
  --# global in out Counter;
  --# derives Counter      from Counter, Table, Value &
  --#         Found, Index from Table, Value;
  --# pre  Counter < Integer'Last;
  --# post Found -> (Table(Index) = Value and
                    Counter = Counter~ + 1);

end Search;

package body
Search is

  procedure Linear_Search
    (Table : in IntArray;
     Value : in Integer;
     Found : out Boolean;
     Index : out Integer) is
     Found := False;
     Index := 0;

     for I in Integer range Table'Range loop
        --# assert Found = False and Counter < Integer'Last
        --#        and Counter = Counter~;

        if Table(I) = Value then
           Counter := Counter + 1;
           Found := True;
           Index := I;
        end if;
     end loop;

  end Linear_Search;

end Search;

This example shows several core annotations:

  • The own and initializes annotations in the package specification, which identify a state variable and confirm that it is initialized;
  • The global annotation for the procedure specification, which indicates the intent to both reference and assign to the global variable; and
  • The derives annotation for the procedure specification, which documents the information flow dependences among the formal parameters and global variable.

The proof annotations are the procedure’s pre and post annotations, and the loop invariant assert annotation. The “->” symbol represents logical implication; thus “Found -> …” means “if Found then …”. A variable with an appended tilde (Counter~ in this example) means the value of the variable on entry to the procedure. For simplicity, the state variable Counter is declared in the visible part of the package specification, analogous to public in C++ and Java; encapsulating it in the package body would be better style. A more complete discussion of a similar example appears in AdaCore’s Ada Gems 685 and 696.

*The SPARK programming language is not sponsored by or affiliated with SPARC International Inc. and is not based on the SPARC architecture.

< Previous
Page 1 of 4
Next >

Loading comments...