Home page > Teams > DCS > Projects

VERIDYC

ANR-09-SEGI-016, 2009-2012

The goal of this project is the verification of C programs that are used to control safety-critical systems, such as airplanes, subway lines or power plants.

Table of contents

1 2

News

VERIDYC Meeting 16-17 February 2012 at VERIMAG. Click here for the program!
VVS Workshop 30 June 2011 at VERIMAG.
Jules Villard’s thesis defence
The Numerical Transition Systems Competition is coming up!

Introduction

Within the past decade, push-button verification techniques (e.g. model checking, SAT solving, etc.) have become commonplace in the development of hardware systems. An integration of such methods within the development of software systems is highly required by the manufacturers of critical and embedded systems (avionics, telecommunications, public transport, etc.). Indeed, software programs used for the control of safety-critical systems (e.g., airplanes, trains, power plants, etc.) are required nowadays, by the certification authorities, to undergo formal verification, in order to ensure absence of run-time errors (e.g., null pointer exceptions, memory leaks, arithmetic exceptions, etc.). Such errors have caused in the past considerable losses, both economical and human (e.g., the crash of ESA/ARIANE 5 maiden flight, due to an arithmetic exception).

Goal

The goal of this project is the verification of C programs that are used to control safety-critical systems, such as power plants. A major problem is the scalability of existing verification techniques for programs with dynamic data structures. These techniques are capable nowadays of analyzing and finding bugs in toy programs of about 100 lines of code. In this project we aim, on one hand, at extending the existing verification techniques in order to deal with parallel programs handling singly-linked lists and array data structures. On the other hand, we aim at applying these techniques to real-life test cases, with sizes of several tens of thousands lines of C code. The project will follow two main directions:

Model extraction from C programs This direction will use slicing and abstraction techniques for parallel programs, in order to eliminate parts of code which are irrelevant for the properties verified. These properties include memory violations (e.g. null pointer exceptions, memory leaks, etc.). deadlocks (in case of concurrent programs) and out of bounds array accesses.

Verification of memory consistency properties Existing verification techniques are capable of dealing with sequential programs handling lists and arrays of integers. One of our goals is extending the existing techniques to multi-threading programs using lock-based synchronization mechanisms, as it is usually the case in C applications.

The final result of the project will be a prototype tool capable of analyzing an important number of test cases, provided by the industrial partners (in particular, EDF)