Title: Automatic Generation of Program Invariants from Traces

Speaker: Deepak Kapur (University of New Mexico, USA)         http://www.cs.unm.edu/~kapur/ 

Time: 14:00, Oct. 16, 2013

Venue: Lecture Room, 3rd Floor, Building #5, State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences

Abstract:

An effective approach for generating program invariants by dynamic analysis will be presented. Nonlinear equality and inequality invariants are shown to be generated automatically from observed program traces. The approach also considers invariants involving the array data structure, including relations among multi-dimensional array variables. These properties are nontrivial and challenging for current static and dynamic invariant analysis methods. More recently, methods have been developed to derive disjunctive invariants in which disjunctions are specified using max and min functions. The approach has been implemented as a software tool call DIG (Dynamic Invariant Generator). The key difference between DIG and existing dynamic methods such as DAIKON is its generative technique, which infers invariants directly from traces, instead of using traces to filter out pre-defined templates. Experimental results on numerical algorithms and an implementation of AES encryption provide evidence that DIG is　effective at generating invariants for these programs.

This work is part of Thanh Vu Nguyen's Ph.D. dissertation research.