1. Motivation for a Common Generic Interface

Figure 1: Why we need a common interface!

In the middle of 4_fig:projects_libs_api, there are five static analyzers: PIPS [PIPb,IJT91], NBAC [NBA,JEA00], ASTREE [AST,BCC$^$03], the OMEGA framework [Ome,PUG91] and CHINA [CHI,PAR,BRZaH02] which are detailed in the author's thesis. On the left hand side of the API, we have the current status: each static analyzer has its own library dealing with its own abstract domain(s). In practice, they all have problems when dealing with large scale applications.

However, recent developments from one team such as new abstract domains, e.g. the Octagon library [MIN,MIN01], or algorithmic improvements, e.g. Cartesian factorization [HMPV03], cannot be readily exploited by other teams. Meanwhile existing static analyzers are mostly modular, and are mostly based on similar technologies.

On the right hand side of the API in 4_fig:projects_libs_api, we show how a generic API would let any analyzer benefit from specific features in other libraries. For example, this API would allow PIPS to use another abstract domain, e.g. octagonal domain or Presburger formulae, while keeping the infrastructure developed in PIPS for the polyhedral domain. Precisely, an unified framework could free its users from the compatibility burdens such as different signatures for the same semantic abstract operator, exception handlers and sometimes operator availability. Moreover, whenever a new improvement takes place somewhere for a given abstract domain, for instance the Cartesian factorization in PPL [HMPV03], then not only CHINA but also PIPS could profit from it without additional work. Finally, the new API should provide mechanisms to assure the robustness for available implementations, e.g. the timeout management.

As described in prj:apron, a French project named APRON was launched in 2004 where such a common interface is of interest. Although OMEGA [Ome,PUG91] and Parma [CHI,PAR,BRZaH02] teams are not members of the project, the common interface must be compatible with their interfaces which are dot linked in 4_fig:projects_libs_api. Meanwhile, other teams have promised to support the new interface when it is finished.

In order to design an interface which can replace all interfaces already used in current implementations, first of all we need to study these interfaces and to find out common points and incompatibilities among them. Incompatibilities may happen at the interface level, that is to say the signatures of operators, the data structures, etc., as well as at the implementation level, with exception management, thread-safety features, underlying arithmetics, etc. We will discuss these problems later in this section.

At the interface level, different abstract domains lead to different data structures, then to different signatures for one generic operator. If we take the example of the octagonal and the polyhedral domains, we need an abstract object that represents an octagon and/or a polyhedron. Even for the same abstract domain, e.g. the polyhedral domain, many differences appear because each interface was designed to meet the need of their own developers. New POLKA was designed to be used in NBAC analyzer for automation analysis: a dense representation is chosen since the number of variables and hence the dimension is low, between $10$ and $30$ (see the author's thesis). The $C^3$ library was designed for and used by PIPS which is an automatic inter-procedural analyzer. Hundreds of variables may be analyzed and a sparse representation is the logical choice. The octagon library is only used by ASTREE analyzer (see the author's thesis).

In the following sections, we describe in a general way, the difficulties which have not been explored yet. Then, in 4_sec:HQ_interface, 4_sec:HQ_interface, we analyze them in greater details with respect to the API reference that was developed by the author. We begin with the comparison between polyhedral interfaces, and then the comparison with other abstract domains.