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.

Algebraic Power Analysis by Abstract Interpretation

MASTROENI, Isabella
2004-01-01

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.
abstract interpretation; static program analysis; algebraic power analysis; abstract domains; software watermarking
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11562/302244
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? ND
social impact