Algebraic Power Analysis by Abstract Interpretation

By: Isabella Mastroeni

Isabella Mastroeni
Dip. di Informatica
Univ. di Verona
Strada Le Grazie a Ca' Vignal 2
I-37134 Verona, Italy
mastroeni@sci.univr.it

Abstract:

In this paper we design abstract domains for power analysis. These domains are conceived to discover properties of the following type: ``The variable X at a given program point is the power of c with the exponent having a given property p'', where c and p are automatically determined. This construction is general and include different algebraic entities, such as numerical and polynomial (with rational coefficients), as bases. Several families of domains are presented, some of these consider that the exponent can be any natural or integer value, the others include also the analysis of properties of the exponent set. Relevant lattice-theoretic properties of these domains are proved such as the absence of infinite ascending chains and the structure of their meet-irreducible elements. The numerical domains are applied in the analysis of integer powers of imperative programs and in the analysis of probabilistic concurrent programming, with probabilistic non-deterministic choice. Moreover we use the numerical power domains in order to analyze the factorization of integer variables, i.e., invariant properties of factors and of their exponents. In this way we are able to statically detect information hidden in prime factorization, which is useful in software watermarking.