Computing Science: Computational Program Dependence Graph and its Application to Information Flow Security

摘要

This paper develops a novel approach that analyses dependencies of programs in a quantitative aspect. We introduce a definition of Quantitative Program Dependence Graph (QPDG) which can be used to model a program's behaviour given spaces of inputs. The programs we consider are in a core while-language. We also present the semantics for the purpose of building QPDGs. The QPDG reasons about the programs' quantitative uncertainty behaviours based on a probabilistic analysis. It can be used to characterise dependence analysis of programs in a quantitative way. We next provides a further optimisation on the QPDG by doing slicing in order to perform an information flow analysis, e.g. how input variables at the source node might affect a given output variable at the target node and how much. Finally, we suggest its application to quantified secure information flow analysis for programs, and show that simple and intuitive computation can be obtained.