Information Flow Is Linear Refinement of Constancy

  • Fausto Spoto
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3722)


Detecting information flows inside a program is useful to check non-interference of program variables, an important aspect of software security. Information flows have been computed in the past by using abstract interpretation over an abstract domain IF which expresses sets of flows. In this paper we reconstruct IF as the linear refinement CC of a basic domain C expressing constancy of program variables. This is important since we also show that CC, and hence IF, is closed w.r.t. linear refinement, and is hence optimal and condensing. Then a compositional, input-independent static analysis over IF has the same precision of a non-compositional, input-driven analysis. Moreover, we show that CC has a natural representation in terms of Boolean formulas, efficiently implementable through binary decision diagrams.


Logic Program Complete Lattice Abstract Interpretation Program Variable Boolean Formula 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Bossi, A., Gabbrielli, M., Levi, G., Martelli, M.: The s-Semantics Approach: Theory and Applications. Journal of Logic Programming 19/20, 149–197 (1994)CrossRefMathSciNetGoogle Scholar
  2. 2.
    Bryant, R.E.: Graph-based Algorithms for Boolean Function Manipulation. IEEE Transactions on Computers 35(8), 677–691 (1986)zbMATHCrossRefGoogle Scholar
  3. 3.
    Clark, D., Hankin, C., Hunt, S.: Information Flow for Algol-like Languages. Computer Languages and Security 28(1), 3–28 (2002)zbMATHGoogle Scholar
  4. 4.
    Cousot, P., Cousot, R.: Abstract Interpretation: A Unified Lattice Model for Static Analysis of Programs by Construction or Approximation of Fixpoints. In: Proc. of the 4th ACM Symposium on Principles of Programming Languages (POPL), pp. 238–252 (1977)Google Scholar
  5. 5.
    Cousot, P., Cousot, R.: Systematic Design of Program Analysis Frameworks. In: Proc. of the 6th ACM Symp. on Principles of Programming Languages, pp. 269–282 (1979)Google Scholar
  6. 6.
    Genaim, S., Giacobazzi, R., Mastroeni, I.: Modeling Secure Information Flow with Boolean Functions. In: Ryan, P. (ed.) ACM SIGPLAN and GI FoMSESS Workshop on Issues in the Theory of Security, April 2004, pp. 55–66 (2004)Google Scholar
  7. 7.
    Genaim, S., Spoto, F.: Information Flow Analysis for Java Bytecode. In: Cousot, R. (ed.) VMCAI 2005. LNCS, vol. 3385, pp. 346–362. Springer, Heidelberg (2005)CrossRefGoogle Scholar
  8. 8.
    Giacobazzi, R., Mastroeni, I.: Abstract Non-Interference: Parameterizing Non-Interference by Abstract Interpretation. In: Proc. of the 31st Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL’04), Venice, Italy, January 2004, pp. 186–197. ACM-Press, New York (2004)CrossRefGoogle Scholar
  9. 9.
    Giacobazzi, R., Ranzato, F., Scozzari, F.: Making Abstract Domains Condensing. ACM Transactions on Computational Logic (ACM-TOCL) 6(1), 33–60 (2005)CrossRefMathSciNetGoogle Scholar
  10. 10.
    Giacobazzi, R., Scozzari, F.: A Logical Model for Relational Abstract Domains. ACM Transactions on Programming Languages and Systems 20(5), 1067–1109 (1998)CrossRefGoogle Scholar
  11. 11.
    Sabelfeld, A., Myers, A.C.: Language-based Information-Flow Security. IEEE Journal on Selected Areas in Communications 21(1), 5–19 (2003)CrossRefGoogle Scholar
  12. 12.
    Sabelfeld, A., Sands, D.: A PER Model of Secure Information Flow in Sequential Programs. Higher-Order and Symbolic Computation 14(1), 59–91 (2001)zbMATHCrossRefGoogle Scholar
  13. 13.
    Scozzari, S.: Logical Optimality of Groundness Analysis. Theoretical Computer Science 277(1-2), 149–184 (2002)zbMATHCrossRefMathSciNetGoogle Scholar
  14. 14.
    Sekar, M.C., Mishra, P., Ramakrishnan, I.V.: On the Power and Limitation of Strictness Analysis Based on Abstract Interpretation. In: Proc. of the 18th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL 1991), Orlando, Florida, January 1991, pp. 37–48 (1991)Google Scholar
  15. 15.
    Volpano, D., Smith, G., Irvine, C.: A Sound Type System for Secure Flow Analysis. Journal of Computer Security 4(2,3), 167–187 (1996)Google Scholar
  16. 16.
    Winskel, G.: The Formal Semantics of Programming Languages. The MIT Press, Cambridge (1993)zbMATHGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

  • Fausto Spoto
    • 1
  1. 1.Dipartimento di InformaticaUniversità di VeronaItaly

Personalised recommendations