Hypercollecting semantics and its application to static analysis of information flow
Authors:
Open Access
- 1 January 2017
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM SIGPLAN Notices
- Vol. 52 (1) , 874-887
Abstract
We show how static analysis for secure information flow can be expressed and proved correct entirely within the framework of abstract interpretation. The key idea is to define a Galois connection that directly approximates the hyperproperty of interest. To enable use of such Galois connections, we introduce a fixpoint characterisation of hypercollecting semantics, i.e. a "set of sets" transformer. This makes it possible to systematically derive static analyses for hyperproperties entirely within the calculational framework of abstract interpretation. We evaluate this technique by deriving example static analyses. For qualitative information flow, we derive a dependence analysis similar to the logic of Amtoft and Banerjee (SAS '04) and the type system of Hunt and Sands (POPL '06). For quantitative information flow, we derive a novel cardinality analysis that bounds the leakage conveyed by a program instead of simply deciding whether it exists. This encompasses problems that are hypersafety but not k -safety. We put the framework to use and introduce variations that achieve precision rivalling the most recent and precise static analyses for information flow.Keywords
All Related Versions
Funding Information
- National Science Foundation (CNS-1228930,CCF-1649884)
- Agence Nationale de la Recherche (ANR-14-CE28-0014)
- Commissariat à l'Énergie Atomique et aux Énergies Alternatives
This publication has 57 references indexed in Scilit:
- Inverse-limit and topological aspects of abstract interpretationTheoretical Computer Science, 2012
- Modelling declassification policies using abstract domain completenessMathematical Structures in Computer Science, 2011
- Widening and narrowing operators for abstract interpretationComputer Languages, Systems & Structures, 2011
- A firm foundation for private data analysisCommunications of the ACM, 2011
- Quantitative Notions of Leakage for One-try AttacksElectronic Notes in Theoretical Computer Science, 2009
- The trace partitioning abstract domainACM Transactions on Programming Languages and Systems, 2007
- Language-based information-flow securityIEEE Journal on Selected Areas in Communications, 2003
- Constructive design of a hierarchy of semantics of a transition system by abstract interpretationTheoretical Computer Science, 2002
- Abstract interpretation by dynamic partitioningJournal of Functional Programming, 1992
- Certification of programs for secure information flowCommunications of the ACM, 1977