We propose an algorithm to over-approximate data dependencies with respect to abstract properties of data, described as abstract domains. To the best of our knowledge, no other explicit calculi of abstract dependencies exist in the literature. In our setting, relevant variables are those which may affect abstract properties of expressions they occur in. Unlike its non-abstracted counterpart, the calculus of abstract dependencies is forced to rely on semantics: the syntactic occurrence of a variable is not sufficient to decide whether an expression depends on it. The algorithm computes the set of relevant variables for an expression, w.r.t. an abstract domain; it is proved to be sound, that is, the computed set is an over approximation of truly (semantically) relevant variables. We exploit static analysis techniques, together with our knowledge of the structure of expressions and domains, in order to improve efficiency. Applications to program slicing (w.r.t. abstract properties) and to abstract non-interference are discussed; moreover, we propose a domain transformer which approximates the most precise domain ruling out a given set of dependencies.

Data Dependencies and Program Slicing: from Syntax to Abstract Semantics

MASTROENI, Isabella;ZANARDINI, Damiano
2008-01-01

Abstract

We propose an algorithm to over-approximate data dependencies with respect to abstract properties of data, described as abstract domains. To the best of our knowledge, no other explicit calculi of abstract dependencies exist in the literature. In our setting, relevant variables are those which may affect abstract properties of expressions they occur in. Unlike its non-abstracted counterpart, the calculus of abstract dependencies is forced to rely on semantics: the syntactic occurrence of a variable is not sufficient to decide whether an expression depends on it. The algorithm computes the set of relevant variables for an expression, w.r.t. an abstract domain; it is proved to be sound, that is, the computed set is an over approximation of truly (semantically) relevant variables. We exploit static analysis techniques, together with our knowledge of the structure of expressions and domains, in order to improve efficiency. Applications to program slicing (w.r.t. abstract properties) and to abstract non-interference are discussed; moreover, we propose a domain transformer which approximates the most precise domain ruling out a given set of dependencies.
2008
978-1-59593-977-7
Abstract Interpretation; Abstract non-interference; Dependencyanalysis; Program slicing
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/313572
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 31
  • ???jsp.display-item.citation.isi??? 17
social impact