Analysis of a probabilistic system often requires to learn the joint probability distribution of its random variables. The computation of the exact distribution is usually an exhaustive precise analysis on all executions of the system. To avoid the high computational cost of such an exhaustive search, statistical analysis has been studied to efficiently obtain approximate estimates by analyzing only a small but representative subset of the system's behavior. In this paper we propose a hybrid statistical estimation method that combines precise and statistical analyses to estimate mutual information, Shannon entropy, and conditional entropy, together with their confidence intervals. We show how to combine the analyses on different components of a discrete system with different accuracy to obtain an estimate for the whole system. The new method performs weighted statistical analysis with different sample sizes over different components and dynamically finds their optimal sample sizes. Moreover, it can reduce sample sizes by using prior knowledge about systems and a new abstraction-then-sampling technique based on qualitative analysis. To apply the method to the source code of a system, we show how to decompose the code into components and to determine the analysis method for each component by overviewing the implementation of those techniques in the HyLeak tool. We demonstrate with case studies that the new method outperforms the state of the art in quantifying information leakage. 168 F. Biondi et al. about systems, including the abstraction-then-sampling technique with qualitative analysis. Section 6 shows the optimal assignment of samples to components to be samples statistically to improve the accuracy of the estimate. Section 7 overviews the implementation of the techniques in the HyLeak tool, including how to decompose the source code of a system into components and to determine the analysis method for each component. Section 8 evaluates the proposed method and illustrates its effectiveness against the state of the art, and Sect. 9 concludes the paper. Detailed proofs can be found in Appendix A. The information-theoretical approach to program security dates back to the work of Denning [Den76] and Gray [III91]. Clark et al. [CHM01, CHM07] presented techniques to automatically compute mutual information of an imperative language with loops. For a deterministic program, leakage can be computed from the equivalence relations on the secret induced by the possible outputs, and such relations can be automatically quantified [BKR09]. Under-and over-approximation of leakage based on the observation of some traces have been studied for deterministic programs [ME08, NMS09]. As an approach without replying on information theory McCamant et al. [KMPS11] developed tools implementing dynamic quantitative taint analysis techniques for security. Fremont and Seshia [FS14] present a polynomial time algorithm to approximate the weight of traces of deterministic programs with possible application to quantitative information leakage. Progress in randomized program analysis includes a scalable algorithm for uniform generation of sample from a distribution defined as constraints [CFM + 15, CMV13], with applications to constrained-random program verification. The statistical approach to quantifying information leakage has been studied since the seminal work by Chatzikokolakis et al. [CCG10]. Chothia et al. have developed this approach in tools leakiEst [CKN13, CKNa] and LeakWatch [CKN14, CKNb]. The hybrid statistical method in this paper can be considered as their extension with the inclusion of component weighting and adaptive priors inspired by the importance sampling in statistical model checking [BHP12, CZ11]. To the best of our knowledge, no prior work has applied weighted statistical analysis to the estimation of mutual information or any other leakage measures. The idea on combining static and randomized approaches to quantitative information flow was first proposed by Köpf and Rybalchenko [KR10] while our approach takes a different approach relying on statistical estimation to have better precision and accuracy and is general enough to deal with probabilistic systems under various prior information conditions. In related fields, the hybrid approach combining precise and statistical analysis have been proven to be effective, for instance in concolic analysis [MS07, LCFS14], where it is shown that input generated by hybrid techniques leads to greater code coverage than input generated by both fully random and concolic generation. After the publication of the preliminary version [KBL16] of this paper, a few papers on quantitative information flow combining symbolic and statistical approaches have been published. Malacaria et al. [MKP + 18] present an approach that performs Monte Carlo sampling over symbolic paths while the prior distributions are restricted to be uniform. Sweet et al. [STS + 18] combine abstraction interpretation with sampling and concolic execution for reasoning about Bayes vulnerability. Unlike our work, these two studies aim at giving only bounds on information leakage and do not use statistical hypothesis testing. Our tool HyLeak processes a simple imperative language that is an extension of the language used in the QUAIL tool version 2.0 [BLQ15]. The algorithms for precise computation of information leakage used in this paper are based on trace analysis [BLMW15], implemented in the QUAIL tool [BLTW, BLTW13, BLQ15]. As remarked above, the QUAIL tool implements only a precise calculation of leakage that examines all executions of programs. Hence the performance of QUAIL does not scale, especially when the program performs complicated computations that yield a large number of execution traces. The performance of QUAIL as compared to HyLeak is represented by the "precise" analysis approach in Sect. 8. Since QUAIL does not support the statistical approach or the hybrid approach, it cannot handle large problems that HyLeak can analyze. As remarked above, the stochastic simulation techniques implemented in HyLeak have also been developed in the tools LeakiEst [CKN13] (with its extension [KCP14]) and LeakWatch [CKNP13, CKN14]. The performance of these tools as compared to HyLeak is represented by the "statistical" analysis approach in Sect. 8. The tool Moped-QLeak [CMS14] computes the precise information leakage of a program by transforming it into an algebraic decision diagram (ADD). As noted in [BLQ15], this technique is efficient when the program under analysis is simple enough to be converted into an ADD, and fails otherwise even when other tools including HyLeak can handle it. In particular, there are simple examples [BLQ15] where Moped-QLeak fails to produce any result but that can be examined by QUAIL and LeakWatch, hence by HyLeak. Many information leakage analysis tools restricted to deterministic input programs have been released, including TEMU [NMS09], squifc [PM14], jpf-qif [PMTP12], QILURA [PMPd14], nsqflow [VEB + 16], and Step 1: Preprocessing Step 1a. Lexing, parsing and syntax checking. HyLeak starts by lexical analysis, macro substitution and syntax analysis. In macro substitution the constants defined in the input program are replaced with their declared values, and simple operations are resolved immediately.
In research of privacy, a few papers (e.g., REF ) present hybrid methods combining symbolic and statistical analyses to quantify privacy leaks.
Hybrid statistical estimation of mutual information and its application to information flow
Formal Aspects of Computing
Formal Aspects of Computing
Computer Science Mathematics