# 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.
*

Related papers:

Available:
PDF,
BibTeX
Entry.

* mastroeni@sci.univr.it *