Static Analysis

Transformation rules of imperative concurrent programs, based on congruence and refinement relations between statements, are presented. They introduce and/or eliminate synchronous communication statements and parallelism in these programs. The development is made within a subset of SPL, a good representative of imperative notations for concurrent and reactive programs introduced by Manna and Pnueli. The paper shows that no finite set of transformation rules suffices to eliminate synchronous communication statements from programs involving the concatenation and parallelism operators only. An infinite set is given to suit this purpose, which can be applied recursively. As an important complement for the applications, a collection of tactics, for the acceleration of broader transformations, is described. Tactics apply a sequence of rules to a program with a specific transformation objective. The transformation rules and the tactics could be used in formal design to derive new programs from verified ones, preserving their properties, and avoiding the repetition of verifications for the transformed programs. As an example, the formal parallelization of a non-trivial distributed fast Fourier transform algorithm is outlined.

We abstract a denotational trace semantics for an imperative language into a compositional and focussed watchpoint semantics. Every abstraction of its computational domain induces an abstract, still compositional and focussed watchpoint semantics. We describe its implementation and instantiation with a domain of signs. It shows that its space and time costs are proportional to the number of watchpoints and that abstract compilation reduces those costs significantly.

Logic languages based on the theory of rational, possibly infinite, trees have much appeal in that rational trees allow for faster unification (due to the omission of the occurs-check) and increased expressivity. Note that cyclic terms can provide a very efficient representation of grammars and other useful objects. Unfortunately, the use of infinite rational trees has problems. For instance, many of the built-in and library predicates are ill-defined for such trees and need to be supplemented by run-time checks whose cost may be significant. Moreover, some widely-used program analysis and manipulation techniques are only correct for those parts of programs working over finite trees. It is thus important to obtain, automatically, a knowledge of those program variables (the finite variables) that, at the program points of interest, will always be bound to finite terms. For these reasons, we propose here a new data-flow analysis that captures such information. We present a parametric domain where a simple component for recording finite variables is coupled with a generic domain (the parameter of the construction) providing sharing information. The sharing domain is abstractly specified so as to guarantee the correctness of the combined domain and the generality of the approach.

All practical C programs use structures, arrays, and/or strings. At runtime, such objects are mapped into consecutive memory locations, hereafter referred to as buffers. Many software defects are caused by buffer overflow — unintentional access to memory outside the intended object. String manipulation is a major source of such defects. According to the FUZZ study, they are the cause of most UNIX failures.

A prototype of the algorithm has been implemented and applied to statically uncover defects in real C applications, i.e., errors which occur on some inputs to the program. The applications were selected without a priori knowledge of the number of string manipulation errors. A significant number of string manipulation errors were found in every application, further indicating the extensiveness of such errors. We are encouraged by the fact that our algorithm reports very few false alarms, i.e., warnings on errors that never occur at runtime.

We address the problem of verifying safety and liveness properties for infinite-state systems, using symbolic reachability analysis. The models we consider are fair parametric extended automata, i.e., counter automata with parametric guards, supplied with fairness conditions on their transitions. In previous work, we shown that symbolic reachability analysis using acceleration techniques can be used to generate finite abstractions (symbolic graphs) of the original infinite-state model. In this paper, we show that this analysis can be also used to introduce fairness conditions on the generated abstract model allowing to model-check liveness properties. We show first how to translate faithfully the fairness conditions of the infinite-state original model to conditions on the generated finite symbolic graph. Then, we show that we can also synthesize automatically new fairness conditions allowing to eliminate infinite paths in the symbolic graph which do not correspond to valid behaviours in the original model. These infinite paths correspond to abstractions of boundedly iterable (nested) loops. We show techniques allowing to decide this bounded iterability for a class of components in the symbolic graph. We illustrate the application of these techniques to nontrivial examples.

Enforcing information flow properties for distributed systems adds a new challenges: mutual distrust among the principals, and untrusted hosts. Our new approach, secure program partitioning, automatically rewrites a program into communicating subprograms that run securely on the set of available hosts yet collectively implement the original program. This fine-grained rewriting is based on the security types in the original program and the trust relationships among principals and hosts in the system. Computation in the original program is written in a single-host style, yet the resulting distributed system can satisfy the strong confidentiality and integrity properties specified by the program.