Hybrid Statistical Estimation of Mutual Information for
Quantifying Information Flow ?
Yusuke Kawamoto1 , Fabrizio Biondi2 , and Axel Legay2
1
2

AIST, JapanINRIA, France

Abstract. 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 thesystem. To avoid the high computational cost of such an exhaustive search, statistical analysis has been studied to efficiently obtain approximate estimates byanalyzing only a small but representative subset of the system’s behavior. In thispaper we propose a hybrid statistical estimation method that combines precise
and statistical analyses to estimate mutual information and its confidence interval.
We show how to combine the analyses on different components of the systemwith different precision to obtain an estimate for the whole system. The new
method performs weighted statistical analysis with different sample sizes overdifferent components and dynamically finds their optimal sample sizes. Moreoverit can reduce sample sizes by using prior knowledge about systems and a new
abstraction-then-sampling technique based on qualitative analysis. We show the
new method outperforms the state of the art in quantifying information leakage.

1

Introduction

In modeling and analyzing software and hardware systems, the statistical approach isoften useful to evaluate quantitative aspects of the behaviors of the systems. In particular,
probabilistic systems with complicated internal structures can be approximately andefficiently modeled and analyzed. For instance, statistical model checking has widely
been used to verify quantitative properties of many kinds of probabilistic systems [1].
The statistical analysis of a probabilistic system is usually considered as a blackbox testing approach in which the analyst does not require prior knowledge of theinternal structure of the system. The analyst runs the system many times and records theexecution traces to construct an approximate model of the system. Even when the formal
specification or precise model of the system is not provided to the analyst, statisticalanalysis can be directly applied to the system if the analyst can execute the blackbox implementation. Due to this random sampling of the systems, statistical analysis
provides only approximate estimates. However, it can evaluate the accuracy and error of
the analysis for instance by providing the confidence intervals of the estimated values.
One of the important challenges in statistical analysis is to estimate entropy-based
properties in probabilistic systems. For example, statistical methods [2,3,4,5,6] have?

This work was supported by JSPS KAKENHI Grant Number JP15H06886, by the MSR-Inria
Joint Research Center, by the Sensation European grant, and by région Bretagne.

been studied for quantitative information flow analysis [7,8,9], which estimates anentropy-based property to quantify the leakage of confidential information in a system.
More specifically, the analysis estimates mutual information or other properties between
two random variables on the secrets and on the observable outputs in the system tomeasure the amount of information that is inferable about the secret by observing theoutput. The main technical difficulties in the estimation of entropy-based properties are
1. to efficiently compute large matrices that represent probability distributions, and
2. to provide a statistical method for correcting the bias of the estimate and computing
a confidence interval to evaluate the accuracy of the estimation.
To overcome these difficulties we propose a method for statistically estimating
mutual information, one of the most popular entropy-based properties. The new method,
called hybrid statistical estimation method, integrates black-box statistical analysis andwhite-box precise analysis, exploiting the advantages of both. More specifically, thismethod employs some prior knowledge on the system and performs precise analysis(e.g., static analysis of the source code or specification) on some components of thesystem. Since precise analysis computes the exact sub-probability distributions of thecomponents, the hybrid method using precise analysis is more accurate than statisticalanalysis alone.
Moreover, the new method can combine multiple statistical analyses on different
components of the system to improve the accuracy and efficiency of the estimation. Thisis based on our new theoretical results that extend and generalize previous work [10,11,2]
on purely statistical estimation. As far as we know this is the first work on a hybrid
method for estimating entropy-based properties and their confidence intervals.
To illustrate the method we
0.05
0propose, Fig. 1 presents an ex0
0.1
0.1
ample of a joint probability dis0.15 0.05
Y
0
0
0.05
S1
S2
y1 y2 y3 y4
tribution PXY between two ran000.05 0.1
0x1 0.05 0
0.1
0.1
dom variables X and Y , built up
0
0
from 3 overlapping components
x2 0.15 0.1
0
0
0.05
0
0.05
X
S1 , S2 and T . To estimate thex3 0 0.05 0.05 0.15
T
0.1 0.15
0full joint distribution PXY , thex4 0 0.1 0.15 0
analyst separately computes thejoint sub-distribution for the comFig. 1: Joint distribution composed of 3 components.
ponent T by precise analysis, estimates those for S1 and S2 by statistical analysis, and then combines these subdistributions. Since the statistical analysis is based on the random sampling of execution traces, the empirical sub-distributions for S1 and S2 are different from the true
ones, while the sub-distribution for T is exact. From these approximate and precise
sub-distributions, the proposed method can estimate the mutual information for theentire system and evaluate its accuracy by providing a confidence interval. Owing to
the combination of different kinds of analyses (with possibly different parameters suchas sample sizes), the computation of the bias and confidence interval of the estimate ismore complicated than the previous work on statistical analysis.
2

1.1

Contributions

The contributions of this paper are as follows:– We propose a new method, called hybrid statistical estimation, that combines statistical and precise analyses on the estimation of mutual information (which canalso be applied to Shannon entropy and conditional Shannon entropy). Specifically,
we show theoretical results on compositionally computing the bias and confidence
interval of the estimate from multiple statistical and precise analyses;– We present a weighted statistical analysis method with different sample sizes overdifferent components and a method for adaptively optimizing sample sizes fordifferent components by evaluating the quality and cost of the analysis;– We show how to reduce the sample sizes by using prior knowledge about systems,
including an abstraction-then-sampling technique based on qualitative analysis;– We show that the proposed method can be applied not only to composed systems
but also to the source codes of a single system by decomposing it into components
and determine the analysis method for each component;– We evaluate the quality of the estimation in this method, showing that the estimates
are more accurate than statistical analysis alone for the same sample size, and that the
new method outperforms the state-of-the-art statistical analysis tool LeakWatch [5];– We demonstrate the effectiveness of the hybrid method in case studies on thequantification of information leakage.
The rest of the paper is structured as follows. Section 2 introduces background in
information theory and quantification of information. We compare precise analysis withstatistical analysis for the estimation of mutual information. Section 3 describes the main
results of this paper: the hybrid method for mutual information estimation, including
the method for optimizing sample sizes for different components. Section 4 presents
how to reduce sample sizes by using prior knowledge about systems, including theabstraction-then-sampling technique with qualitative analysis. Section 5 overviews how
to decompose the source code of a system into components and to determine the analysis
method for each component. Section 6 evaluates the proposed method and illustrates its
effectiveness against the state of the art. Section 7 discusses related work and Section 8
concludes the paper. All proofs can be found in Appendix A.

2Information Theory and Quantification of Information

In this section we introduce some background on information theory, which we use
to quantify the amount of information in a system. We write X and Y to denote two
random variables, and X and Y to denote the sets of all possible values of X and Y ,respectively. We denote the number of elements of a set S by #S.
2.1

Channels

In information theory, a channel models the input-output relation of a system as aconditional probability distribution of outputs given inputs. This model has also been3

used to formalize information leakage in a system that processes confidential data: inputs
and outputs of a channel are respectively regarded as secrets and observables in thesystem and the channel represents relationships between the secrets and observables.
A discrete channel is a triple (X , Y, C) where X and Y are two finite sets of discrete
input and output values respectively and C is an #X × #Y matrix where each element
C[x, y] represents
P the conditional probability of an output y given an input x; i.e., foreach x ∈ X , y∈Y C[x, y] = 1 and 0 ≤ C[x, y] ≤ 1 for all y ∈ Y.
A prior is a probability distribution on input values X . Given a prior PX over X anda channel C from X to Y, the joint probability distribution PXY of X and Y is definedby: PXY [x, y] = PX [x]C[x, y] for each x ∈ X and y ∈ Y.
2.2

Mutual Information

The amount of information gained about a random variable X by knowing a randomvariable Y is defined as the difference between the uncertainty about X before and after
observing Y . The mutual information I(X; Y ) between X and Y is one of the mostpopular measures to quantify the amount of information on X gained/leaked by Y :X
PXY [x, y]I(X; Y ) =PXY [x, y] log2
PX [x]PY [y]x∈X ,y∈Y

P
where PY is the marginal probability distribution defined as PY [y] = x∈X PXY [x, y].
In the security scenario, information-theoretical measures quantify the amount ofsecret information leaked against some particular attacker: the mutual information
between two random variables X on the secrets and Y on the observables in a systemmeasures the information that is inferable about the secret by knowing the observable.
In this scenario mutual information, or Shannon leakage, assumes an attacker that can
ask binary questions on the secret’s value after observing the system while min-entropy
leakage [12] considers an attacker that has only one attempt to guess the secret’s value.
Mutual information has been employed in many other applications including Bayesian
networks [13], telecommunications [14], pattern recognition [15], machine learning [16],quantum physics [17], and biology [18]. In this work we focus on mutual information for
the above security scenario as well as for other purposes such as decision tree training.
2.3

Precise Analysis vs. Statistical Analysis

The calculation of the mutual information I(X; Y ) between input X and output Y in aprobabilistic system requires the computation of the joint probability distribution PXYof X and Y . The joint distribution can be computed precisely or estimated statistically.
Precise Analysis To obtain the exact joint probability PXY [x, y] for each x ∈ X andy ∈ Y, we sum the probabilities of all execution traces of the system that have input x
and output y. This means the computation time depends on the number of traces in thesystem. If the system has a very large number of traces, it is intractable for analysts toprecisely compute the joint distribution and consequently the mutual information.
4

In [19] the calculation of mutual information is shown to be computationally expensive. This computational difficulty comes from the fact that entropy-based properties
are hyperproperties [20] that are defined using all execution traces of the system andtherefore cannot be verified on each single trace. For example, when we investigate theleakage of confidential information in a system, it is insufficient to check the information
leakage separately for each component of the system, because the attacker may derivesensitive information by combining the outputs of different components. More generally,
the computation of entropy-based properties (such as the amount of leaked information)
is not compositional in the sense that an entropy-based property of a system is not the(weighted) sum of those of the components.
For this reason it is inherently difficult to naïvely combine analyses of different
components of a system to compute entropy-based properties. In fact, previous studies
on the compositional approach in quantitative information flow analysis have faced
certain difficulties in obtaining useful bounds on information leakage [21,22,23,24].
Statistical Analysis Due to the complexity of precise analysis, some previous studies
have focused on computing approximate values of entropy-based measures. One of thecommon approaches is the statistical analysis based on Monte Carlo methods, in whichapproximate values are computed from repeated random sampling. Previous work on
quantitative information flow has used statistical analysis to mutual information [2,10,11],channel capacity [2,6] and min-entropy leakage [5,25].
In the statistical estimation of mutual information between two random variables X
and Y in a probabilistic system, analysts execute the system many times and collect theexecution traces each recording a pair of values (x, y) ∈ X × Y. This set of execution
traces is used to estimate the empirical joint distribution P̂XY of X and Y and then tocompute the mutual information I(X; Y ).
Note that the empirical distribution P̂XY is different from the true distribution PXY
and thus the estimated mutual information is different from the true value. In fact, it is
known that entropy-based measures such as mutual information and min-entropy leakage
have some bias and error that depends on the number of collected traces, the matrix
size and other factors. However, results on statistics allow us to correct the bias of theestimate and to compute its 95% confidence interval. This way we can guarantee thequality of the estimation, which differentiates our approach from testing.
Comparing the Two Analysis Methods The cost of the statistical analysis is proportional to the size #X × #Y of the joint distribution matrix (strictly speaking, to thenumber of non-zero elements in the matrix). Therefore, this method is significantly more
efficient than precise analPrecise
Statisticalysis if the matrix is relaType
White
box
Black/graybox
tively small and the number
Analyzes
Source code
Implementationof all traces is very large
Impractical for Large number of traces
Large matrices(for instance because theProduces
Exact value
Estimate & confidence
system’s internal variables
have a large range). On the
Table 1: Comparison of the two analysis methods.
other hand, if the matrix is5

very large, the number of executions needs to be very large to obtain a reliable and small
confidence interval. In particular, for a small sample size, statistical analysis does notdetect rare events, i.e., traces with a low probability that affect the result.
Main differences between precise and statistical analysis are summarized in Table 1.

3

Hybrid Statistical Estimation of Mutual Information

To overcome the above limitations on the previous approaches we introduce a new
method, called hybrid statistical estimation method, that integrates both precise andstatistical analyses. In this section we present the method for estimating the mutual
information between two random variables X (over the inputs X ) and Y (over the
outputs Y) in a probabilistic system S, and for providing a confidence interval of thisestimate. In the method we perform different types of analysis (with different parameters)on different components of a system.
– If a component is deterministic, we perform a precise analysis on it.
– If a component Si has a joint sub-distribution matrix over small subsets of X and Y(relatively to the number of all traces), then we perform a statistical analysis on Si .
– If a component Tj has a large matrix (relatively to the number of all traces), we
perform a precise analysis on Tj .
– By combining the analysis results on all components we compute the mutual information estimate and its confidence interval. See the rest of Section 3 for details.
– By qualitative information flow analysis, the analyst may obtain partial knowledge
on components and reduce the sample sizes. See Section 4 for details.
One of the main advantages of the new method is that we guarantee the quality ofthe outcome by providing its confidence interval even though different kinds of analyses
with different parameters are combined together, such as multiple statistical analyses
with different sample sizes.
Another advantage is the compositionality in estimating bias and confidence intervals.
The random sampling of execution traces is performed independently for each component.
Thanks to this we obtain that the bias and confidence interval of mutual information
can be computed in a compositional way. This compositionality enables us to findoptimal sample sizes for the different components that maximize the accuracy of theestimation (i.e., minimize the confidence interval size) given a fixed total sample size forthe entire system. On the other hand, the computation of mutual information itself is notcompositional; It requires calculating the full joint probability distribution of the system
by summing the joint sub-distributions of all components of the system.
Note that these results can be applied to the estimation of Shannon entropy andconditional Shannon entropy as special cases. See Appendix B for the details.
3.1

Computation of Probability Distributions

We consider a probabilistic system S that consists of (m+k) components S1 , S2 , . . . , Sm
and T1 , T2 , . . . , Tk each executed with probabilities θ1 , θ2 , . . . , θm and ξ1 , ξ2 , . . . , ξk ;i.e., when S is executed, it yields Si with the probability θi and Tj with the probability
6ξj . We assume S does not have non-deterministic transitions. Let I = {1, 2, . . . , m}
and J = {1, 2, . . . , k}, one of which can be empty. We assume the analyst can run thecomponent Si for each i ∈ I to record its execution traces, and precisely analyze thecomponents Tj for j ∈ J , e.g., by static analysis of the source code or specification.
In the estimation of mutual information between two random variables X and Y
in the system S, we need to estimate the joint distribution PXY of X and Y . In our
approach this is obtained by combining the joint sub-probability distributions of X andY for all the components Si ’s and Tj ’s. More specifically, let Ri and Qj be the joint
sub-distributions of X and Y for the components Si ’s and Tj ’s respectively. Then the
joint (full) distribution PXY for the whole system S is defined by:XX
def
PXY [x, y] =Ri [x, y] +Qj [x, y]
i ∈I

j ∈J

for x ∈ X and y ∈ Y. Note that for each i ∈ I and j ∈ J , the sums of all probabilities
in Ri and Qj equal the probabilities θi and ξj of executing Si and Tj respectively.
To estimate the joint distribution PXY the analyst computes– for each i ∈ I, the empirical sub-distribution R̂i for the component Si from a set oftraces obtained by executing Si , and– for each j ∈ J , the exact sub-distribution Qj for Tj by a precise analysis on Tj .
The empirical sub-distribution R̂i is constructed as follows. Let ni be the numberof Si ’s executions. For each x ∈ X and y ∈PY, let Kixy be the number of Si ’s traces
that have input x and output y. Then ni = x∈X ,y∈Y Kixy . From these we computedef Kixyni . Since Si isdef
θi Kixy
executed with probability θi , R̂i is given by R̂i [x, y] = θi D̂i [x, y] = ni .

the empirical joint (full) distribution D̂i of X and Y by D̂i [x, y] =3.2

Estimation of Mutual Information and its Confidence Interval

In this section we present our new method for estimating mutual information and its
confidence interval. For each component Si let Di be the joint (full) distribution of X
P
and Y obtainedby normalizing Ri : Di [x, y] = Riθ[x,y]. Let DXi [x] = y∈Y Di [x, y],iPDYi [y] = x∈X Di [x, y] and D = {(x, y) ∈ X × Y : PXY [x, y] 6= 0}.
ˆUsing the estimated P̂XY we can compute the mutual information estimate I(X;Y ).
Note that the mutual information of the whole system is smaller than (or equals) the
weighted sum of those of the components, because of its convexity w.r.t. the channel
matrix. Therefore it cannot be computed compositionally from those of the components;
i.e., it requires to compute the joint distribution matrix P̂XY for the whole system.
ˆY ) is obtained from a limited number of traces, it is different from theSince I(X;ˆ
true value I(X; Y ). The following theorem quantifies the bias E(I(X;Y )) − I(X; Y ).
ˆTheorem 1. The expectation E(I(X; Y )) of the mutual information is given by:X θ2  X
X
X
i
I(X; Y ) +ϕixy −ϕix −ϕiy + O(n−2
i )
2ni
+
+
i ∈I

(x,y)∈D

x∈X

y∈Y

2

2

2

Xi [x]
Yi [y]
i [x,y]where ϕixy = Di [x,y]−D, ϕix = DXi [x]−Dand ϕiy = DYi [y]−D.
PXY [x,y]PX [x]PY [y]

7

The proof is based on the Taylor expansion w.r.t. multiple dependent variables andcan be found in Appendix A. Since the higher-order terms in the formula are negligible
when the sample sizes ni are large enough, we use the following as the point estimate:X
X θ2  XXiˆ
ϕbpe = I(X;
Y)−
ϕ
b
−
ϕ
b
−
iy
ix
ixy
2ni
i∈I

x∈X +

(x,y)∈Dy∈Y +where ϕbixy , ϕbix and ϕbiy are empirical values of ϕixy , ϕix and ϕiy respectively (that arecomputed from traces). Then the bias is closer to 0 when the sample sizes ni are larger.
The quality of the estimate depends on the sample sizes ni and other factors. Theˆ
sampling distribution of the estimate I(X;Y ) tends to follow the normal distribution
when ni ’s are large enough. The following gives the variance of the distribution.
ˆ
Theorem 2. The variance V (I(X;Y )) of the mutual information is given by
X θ2
i

X

ni
i∈I

!

2  X2
PX [x]PY [y]PX [x]PY [y]+O(n−2−Di [x, y] 1+log PXY [x,y]Di [x, y] 1+log PXY [x,y]i )(x,y)∈D(x,y)∈DThe confidence interval of the estimate of mutual information is useful to know
how accurate the estimate is. When the interval is smaller, we learn the estimate ismore accurate. The confidence interval is calculated using the variance v obtained by
Theorem 2. Given a significance level α, we denote by zα/2 the z-score for the 100(1− α2 )percentile point. Then the (1 − α) confidence interval of the estimate is given by:√√[ max(0, pe − zα/2 v), pe + zα/2 v ] .
For example, we use the z-score z0.0025 = 1.96 to
Pcompute the 95% confidence interval.
To ignore the higher order terms the sample size i∈I ni needs to be at least 4·#X ·#Y.
By Theorems 1 and 3, the bias and confidence interval for the whole system can becomputed compositionally from those for the components, unlike the mutual information
itself. This allows us to adaptively optimize the sample sizes for the components.
3.3

Adaptive Optimization of Sample Sizes

The computational cost of the statistical analysis of each component Si generally depends
on the sample size ni and the cost of each execution of Si . When we choose ni we take
into account the trade-off between quality and cost of the analysis: a larger sample size
provides a smaller confidence interval, while the cost increases proportionally to ni .
In this section we present a method for deciding how many times we should run eachcomponent Si to collect a sufficient number of traces to estimate mutual information.
More specifically, we show how to compute optimal sample sizes ni that achieves
P thesmallest confidence interval size within the budget of the total sample size n = i∈I ni .
To compute the optimal sample sizes, we first run each component to collect asmaller number (for instance dozens) of execution traces. Then we calculate certain
intermediate values in computing the variance to determine sample sizes for further
executions. Formally, let vi be the following intermediate value of the variance for Si :vi = θi2XD̂i [x, y]b [x]PbY [y] 2
1 + log PPX−
bXY [x,y](x,y)∈D

X

!

2
bX [x]PbY [y]
PD̂i [x, y] 1 + log Pb [x,y]XY(x,y)∈D

Then we find ni ’s that minimize the variance v =8vii∈I ni of the mutual information.

PTheorem 3. Given the total sample size n and the above intermediate variance vi ofthe component Si for each i ∈ I, the variance of the mutual information
estimate is√v nminimized if, for all i ∈ I, the sample size ni for Si satisfies ni = Pm i√vj .
j=1

By this result the estimation of a confidence interval size is useful to optimally assign
sample sizes to components even when the analyst is not interested in the interval itself.
We show experimentally the effectiveness of this optimization in Appendix F.

4

Estimation Using Prior Knowledge about Systems

In this section we show how to use prior knowledge about systems to improve theestimation, i.e., to make the size of the confidence intervals smaller and reduce therequired sample sizes.
4.1

Approximate Estimation Using Knowledge of Prior Distributions

Our hybrid statistical estimation method integrates both precise and statistical analysis,
and it can be seen as a generalization and extension of previous work [2,10,11].
For example, Chatzikokolakis et.al. [2] present a method for estimating mutual
information between two random variables X (over secret values X ) and Y (overobservable values Y) when the analyst knows the (prior) distribution PX of X. In theestimation they collect execution traces by running a system for each secret value x ∈ X .
Thanks to the precise knowledge of PX , they have more accurate estimates than theother previous work [10,11] that also estimates PX from execution traces.
Estimation using the precise knowledge of PX is an instance of our result if a systemis partitioned into the component Sx for each secret x ∈ X = I. If we assume all joint
probabilities are non-zero, the approximate result in [2] follows from Theorem 1.
ˆCorollary 1. The expectation E(I(X;Y )) of the mutual information is given by
I(X; Y ) + (#X −1)(#Y−1)+ O(n−2 ).
2nIn this result from [2] the bias (#X −1)(#Y−1)
depends only on the size of the joint
2ndistribution matrix. However, the bias can be strongly influenced by zeroes or very small
probabilities in the distribution, therefore their approximate results can be correct only
when all joint probabilities are non-zero and large enough, which is a strong restrictionin practice. We show in Appendix E that the tool LeakWatch [5] implicitly assumes thatall probabilities are large enough, and consequently miscalculates bias and gives anestimate far from the true value in the presence of very small probabilities.
4.2

Our Estimation Using Knowledge of Prior Distributions

To overcome these issues we present more general results in the case the analyst knows
the prior distribution PX . We assume that a system S is partitioned into the disjoint
component Six for each index i ∈ I and secret x ∈ X , and that each Six is executedwith probability θix in the system S. Let Θ = {θix : i ∈ I, x ∈ X }.
9

In the estimation of mutual information we run each component Six separately manytimes to collect execution traces. Unlike the previous work we may change the numberof executions ni PX [x] to ni λi [x] where λi [x] is an importance prior that decides how
the sample size ni is allocated for each component Six . Let Λ = {λi : i ∈ I}.
Given the number Kixy of Six ’s traces with output y, we define the conditional distridef

θ2

K

bution Di of output given input: Di [y|x] = ni λixy
. Let Mixy = λiix[x] Di [y|x] (1−Di [y|x]).
i [x]Then the following is the expectation and variance of the mutual information IˆΘ,Λ (X; Y )calculated using D̂i , Θ, Λ.
Proposition 1. The expectation E(IˆΘ,Λ (X; Y )) of the mutual information is given byP
X 1 X X M
x∈Dy Mixyixy
I(X; Y ) ++ O(n−2i )PXY [x,y] −PY [y]
2ni
+
i∈I

y∈Y

x∈Dy

Proposition 2. The variance V (IˆΘ,Λ (X; Y )) of the mutual information is given by
X X

2
θix
ni λi [x]i∈I x∈X +!

2  X
2
X
PY [y]PY [y]Di [y|x] log PXY [x,y]Di [y|x] log PXY [x,y] −+ O(n−2
i )
y∈Dx

y∈Dx

By applying Theorem 3, the sample sizes ni and the importance priors λi can beadaptively optimized. We describe this in the Appendix A.3 due to space constraints.
4.3

Abstraction-Then-Sampling Using Partial Knowledge of Components

In this section we extend our estimation method to consider the case in which the analyst
has partial knowledge of components (e.g. by static analysis of the source code or
specification) before sampling. Such prior knowledge may help us abstract components
into simpler ones and thus reduce the sample size for the statistical analysis.
For instance, let us consider an analyst who knows two pairs (x, y) and (x0 , y 0 ) of
inputs and outputs have the same probability in a component Si : Di [x, y] = Di [x0 , y 0 ].
Then, when we construct the empirical distribution D̂i from a set of traces, we can countthe number Ki{(x,y),(x0 ,y0 )} of traces having either (x, y) or (x0 , y 0 ), and divide it by two:
K

0

0

,y )}
Kixy = Kix0 y0 = i{(x,y),(x. Then the sample size required for a certain accuracy
2
is smaller than when we do not use the prior knowledge on the equality Kixy = Kix0 y0 .
In the following we generalize this idea to deal with more knowledge of components.
Let us consider a (probabilistic) system in which some components leak no information
on inputs and the analyst can learn this by qualitative information analysis (for verifying non-interference). Then such a component Si has a sub-channel matrix where allnon-zero rows have an identical conditional distribution of outputs given inputs [26].
Consequently, when we estimate the #Xi × #Yi matrix of Si it suffices to estimate
one of the rows, hence the number of executions is proportional to #Yi instead of#Xi × #Yi . Note that even when some components leak no information, computing themutual information for the whole system requires constructing the matrix of the system,
hence the matrices of all components.

10

The following results show that the bias and confidence interval are narrower thanwhen not using the prior knowledge of components. Let I ? be the set of indices of components that have channel matrices whose non-zero rows consist of the same distribution.
For each i ∈ I ? , we define πi [x] as the probability of having an input x in the component
Si . Then the expectation and variance of the mutual information are as follows.
Theorem 4. The expectation E(IˆI ? (X; Y )) of the mutual information is given by
X  X θ2 X
XX X θ2 Xii
ϕ+ϕ−ϕiy +O(n−2
I(X; Y )+
ϕ
−
ψ
−
iy
ix
ixy
ixy
i )
2ni
2ni
i∈I\I ?

(x,y)∈D

x∈X +

y∈Y +

i∈I ?

(x,y)∈D

y∈Y +

2

def

i [x]−Di [x,y]where ψixy = Di [x,y]π.
PXY [x,y]

Theorem 5. The variance V (IˆI ? (X; Y )) of the mutual information is given by
X θ2

X

i

ni
i∈I\I ?

+

i

X

ni

!
2  X2
PX [x]PY [y]−Di [x, y] 1+log PXY [x,y](x,y)∈D2X
DYi [y] log PY [y] −πi [x] log PXY [x, y]

y∈Y +

−

X

x∈X

!

2
X
DYi [y] log PY [y] −πi [x] log PXY [x, y]+ O(n−2
i ).

y∈Y +

5

[x]PY [y]1+log PPXXY[x,y](x,y)∈D

X θ2
i∈I ?

Di [x, y]x∈X

Estimation via Program Decomposition

The hybrid statistical estimation presented in the previous sections is designed to analyze
a system composed of subsystems (for instance, a distributed system over different
software or hardware, potentially geographically separated). However, it can also be
applied to the the source code of a system by decomposing it into disjoint components.
In this section we show how to decompose a code into components and determine foreach component which analysis method to use and the method’s parameters.
The principles to decompose a system’s source code in components are as follows:– The code may be decomposed only at conditional branching. Moreover, each component must be a terminal in the control flow graph, hence no component is executed
afterwards. This is because the estimation method requires that the channel matrix
for the system is the weighted sum of those for its components, and that the weightof a component is the probability of executing it.
– The analysis method and its parameters for each component Si are decided byestimating the computational cost of analyzing Si . Let Zi be the set of all internalrandomness (i.e., the variables whose values are assigned according to probability
distributions) in Si . Then the cost of the statistical analysis is proportional to Si ’s
matrix size #Xi × #Yi , while the cost of the precise analysis is proportional to thenumber of all traces in Si ’s control flow graph (in the worst case proportional to#Xi × #Zi ). Hence the cost estimation is reduced to counting #Yi and #Zi .
11

The procedure for decomposition is shown in Fig. 2 and is illustrated in Appendix D
using the example of Fig. 7. Since this is heuristic, it is not guaranteed to produce an
optimal decomposition. While the procedure is automated, for usability the choice ofanalysis can be controlled by user’s annotations on the code.

1. Build the control flow graph of the system.
2. Mark all possible components based on each conditional branching. Each possible
component must be a terminal as explained in Section 5.
3. For each possible component Si , check whether it is deterministic or not (by syntacticallychecking an occurrence of a probabilistic assignment or a probabilistic function call). If
it is, mark the component for precise analysis.
4. For each possible component Si , check whether Si ’s output variables are independentof its input variables inside Si (by qualitative information flow). If so, mark that theabstraction-then-sampling technique in Section 4.3 is to be used on the component.
5. For each Si , estimate an approximate range size of its internal and observable variables.
6. Looking from the leaves to the root of the graph, decide the decomposition into components. Estimate the cost of statistical and precise analyses and mark the component foranalysis by the cheapest of the two.
7. Join together adjacent components if they are marked for precise analysis, or if they aremarked for statistical analysis and have the same input and output ranges.
8. For each component, perform precise analysis or statistical analysis as marked.

Fig. 2: Procedure for decomposing a system given its source code.

6

Evaluation

We evaluate experimentally the effectiveness of our hybrid method compared to the stateof the art. We first discuss the cost and quality of the estimation, then test the hybrid
method against fully precise/fully statistical analyses on Shannon leakage benchmarks.
Another case study (on decision tree training) is shown in Appendix F.
6.1

On the Tradeoff between the Cost and Quality of Estimation

Frequency

In the hybrid statistical estimation, the estimate takes different values probabilistically,
because it is computed from a set of traces
that are generated by executing a probabilistic
True MI Corrected estimate
50
value Lower bound (95%)
system. Fig. 3 shows the sampling distribuUpper bound (95%)
Biased estimate
40
tion of the mutual information estimate of the30
joint distribution in Fig. 1 in Section 1. The
graph shows the frequency (on the y axis) of20
the mutual information estimates (on the x10axis) when performing the estimation 1000
00.755 0.76 0.765 0.77 0.775 0.78 0.785 0.79 0.795 0.8
times. In each estimation we perform precise
Mutual Information (bits)
analysis on the component T and statisticalanalysis on S1 and S2 (with a sample size Fig. 3: Distribution of mutual informationof 5000). Details of the experiments are pro- estimate and its confidence interval.
vided in Appendix C. As shown in Fig. 3 the
12

140

160

sample = 10000
sample = 5000
sample = 1000

120

120

Frequency

100

Frequency(10,2)-matrix(10,5)-matrix(10,10)-matrix

140

80
60
40

100
80
60
40

20

20
0

0

0.18

0.19

0.2

0.21

0.22

0.23

0.24

0.25

0.17 0.18 0.19

0.26

Corrected mutual information (bits)

0.2

0.21 0.22 0.23 0.24 0.25 0.26 0.27

Corrected mutual information (bits)(a) Estimates and sample sizes.

(b) Estimates and the ratio of precise analysis.

Fig. 4: Smaller intervals when increasing the sample size or the ratio of precise analysis.
estimate after the correction of bias by Theorem 1 is closer to the true value. The estimate
is roughly between the lower and upper bounds of the 95% confidence interval calculatedusing Theorem 2.
The interval size depends on the sample size in statistical analysis√ as shown in Fig. 4a.
When the sample size is k times larger, the confidence interval is k times narrower. Theinterval size also depends on the amount of precise analysis as shown in Fig. 4b. If we
perform precise analysis on larger components, then the sampling distribution becomes
more centered (with shorter tails) and the confidence interval becomes narrower.
The hybrid approach produces better estimates than the state of the art in statisticalanalysis. Due to the combination with precise analysis, the confidence interval estimatedby our approach is smaller than LeakWatch [5] for the same sample size.
6.2

Shannon Leakage Benchmarks

We compare the performance of our hybrid method with fully precise/statistical analysis
on Shannon leakage benchmarks. Our implementations of precise and statistical analyses
are variants of the state-of-the art tools QUAIL [27,28] and LeakWatch [5,29] respectively. They are fully automated except for human-provided annotations to determine
the analysis method for each component. All experiments are performed on an Intel
i7-4960HQ 2.6GHz quad-core machine with 8GB of RAM running Ubuntu 16.04 .
secret array bit[N ] s;observable array bit[K] r;
3 for i=0..K-1 do r[i]=s[i] ;4 for i=K..N -1 do
5
j = uniform(0..i);6
if j<K then r[j]=s[i];
7 end
1
2

Fig. 5: Reservoir sampling.

Reservoir Sampling The reservoir sampling problem[30] consists of selecting K elements randomly froma pool of N > K elements. We quantify the information flow of the commonly-used Algorithm R [30], presented in Fig 5, for various values of N and K = N/2.
In the algorithm, the first K elements are chosen as the
sample, then each other element has a probability toreplace one element in the sample.

13

Multiple Lying Cryptographers Protocol
We test our hybrid method to compute theShannon leakage of a distributed version of
the lying cryptographers protocol. The lying
cryptographers protocol is a variant of thedining cryptographer multiparty computation
protocol [31] in which a randomly-chosen
cryptographer declares the opposite of what
they would normally declare, i.e. they lie ifthey are not the payer, and do not lie if they
are the payer. We consider three simultaneFig. 6: Lying cryptographers.
ous lying cryptographers implementation inwhich 8 cryptographers run the protocol on three separate overlapping tables A, B
and C with 4 cryptographers each. Table A hosts cryptographers 1 to 4, Table B hosts
cryptographers 3 to 6, and Table C hosts cryptographers 5 to 8. The identity of the payer
is the same in all tables. We discuss this example in more details in Appendix E.
secret int h = [0, N ];2 observable array bit[N ] decl;
3 int lie = uniform(1..N );4 randomly generated array bit[N ] coin;
5 for c in coin do c = uniform(0..1) ;6 for i=0..N -1 do
7decl[i]=coin[i] xor coin[(i+1)%N ];8
if h==i+1 then decl[i]=!decl[i];9if i==lie then decl[i]=!decl[i];10 end1

secret int sec = [0,N -1];
2 observable int obs;
3 int S = uniform(0,N -W -1);
4 int ws = uniform(1,W );5 int O = uniform(0,N -W -1);
6 int wo = uniform(1,W );7 if S ≤ sec ≤ S +ws then8
obs = uniform(O,O+wo);
9 else10obs = uniform(0,N -1);
11 end1

Shifting Window In the shifting window example
the secret has N possible values, and a contiguous sequence of this values (the “window”) of random size
from 1 to W is chosen. We assume for simplicity thatN = 2W . If the secret is inside the window then another random window is chosen in the same way anda random value from the new window is printed. Otherwise, a random value from 0 to N − 1 is printed.

Results In Table 2 we show the results of the benchmarks using fully precise, fully statistical and hybrid
Fig. 7: Shifting Window.
analyses, for a sample size of 100000 executions. Timeout is set at 10 minutes. On the reservoir benchmark
the precise analysis is faster for small instances but does not scale, timing out on larger
values of N . The hybrid method is consistently faster than the fully statistical analy-

Reservoir
N=6 N=8 N=10
PreciseLying Crypt
N=12Time(s) 0.7 11.4 timeout timeout
Error
0
0
-

Window
N=20 N=22 N=24

506.4
0

10.0 16.0 28.3000Time(s) 21.6 35.2
Statistical Error 10−3 10−3

60.7
-

91.5
-

254.3
10−3

7.5 7.7 7.1
10−3 10−3 10−4

Time(s) 13.4 22.5
Error 10−4 10−3

34.6
-

58.4
-

240.1
10−3

6.6 7.1 7.1
10−7 10−4 10−4

HybridTable 2: Shannon leakage benchmark results.

14sis and often has a smaller error. On the other benchmarks the hybrid method usuallyoutperforms the others and produces better approximations than the statistical analysis.
The results in Table 2 show the superiority of our hybrid approach compared tothe state of the art. The hybrid analysis scales better than the precise analysis, since
it does not need to analyze every trace of the system. Compared to fully statisticalanalysis, our hybrid analysis exploits precise analysis on components of the system
where statistical estimation would be more expensive than precise analysis. This allows
the hybrid analysis to focus the statistical estimation on components of the system where
it converges faster, thus obtaining a smaller confidence interval in a shorter time.

7

Related Work

The information-theoretical approach to program security dates back to the work of
Denning [32] and Gray [33]. Clark et al. [7,34] presented techniques to automaticallycompute mutual information of an imperative language with loops. For a deterministic
program, leakage can be computed from the equivalence relations on the secret inducedby the possible outputs, and such relations can be automatically quantified [35]. Underand over-approximation of leakage based on the observation of some traces have beenstudied for deterministic programs [36,37]. The combination of static and statistical
approaches to quantitative information flow is proposed in [38] while our paper is generalenough to deal with probabilistic systems under various prior information conditions.
The statistical approach to quantifying information leakage has been studied since theseminal work by Chatzikokolakis et al. [2]. Chothia et al. have developed this approach intools leakiEst [3,39] and LeakWatch [5,29]. The hybrid statistical method in this paper
can be considered as their extension with the inclusion of component weighting andadaptive priors inspired by the importance sampling in statistical model checking [40,41].
To the best of our knowledge, no prior work has applied weighted statistical analysis tothe estimation of mutual information or any other leakage measures.
Fremont and Seshia [42] have presented a polynomial time algorithm to approximate
the weight of traces of deterministic programs with possible application to quantitative
information leakage. Progress in statistical program analysis includes a scalable algorithm for uniform generation of sample from a distribution defined as constraints [43,44],
with applications to constrained-random program verification.
The algorithms for precise computation of information leakage used in this paper are
based on trace analysis [45], implemented in the QUAIL tool [28,27]. Phan et al. [46,47]
developed tools to compute channel capacity of deterministic programs written in the
C or Java languages. McCamant et al. [48] developed tools implementing dynamic
quantitative taint analysis techniques for security. The recent tool Moped-QLeak [49] isable to efficiently compute information leakage of programs as long as it can produce acomplete symbolic representation of the program.

8

Conclusions and Future Work

We have proposed a method for estimating mutual information by combining precise andstatistical analyses and for compositionally computing the bias and confidence interval
15

of the estimate. The results are also used to adaptively find the optimal sample sizes fordifferent components in the statistical analysis. Moreover, we have shown how to reduce
sample sizes by using prior knowledge about systems, including the abstraction-thensampling technique with qualitative analysis. To apply our new method to the source
codes of systems we have shown how to decompose the codes into components anddetermine the analysis method for each component. We have shown both theoreticaland experimental results to demonstrate that the proposed approach outperforms thestate of the art. To obtain better results we are developing theory and tools that integrate
symbolic abstraction techniques in program analysis into our estimation method.

References
1. Legay, A., Delahaye, B., Bensalem, S.: Statistical model checking: An overview. In: Runtime
Verification - First International Conference, RV 2010, St. Julians, Malta, November 1-4,
2010. Proceedings. (2010) 122–135
2. Chatzikokolakis, K., Chothia, T., Guha, A.: Statistical measurement of information leakage.
In Esparza, J., Majumdar, R., eds.: TACAS 2010. Proceedings. Volume 6015 of Lecture Notes
in Computer Science., Springer (2010) 390–404
3. Chothia, T., Kawamoto, Y., Novakovic, C.: A tool for estimating information leakage. In
Sharygina, N., Veith, H., eds.: CAV 2013. Proceedings. Volume 8044 of Lecture Notes in
Computer Science., Springer (2013) 690–695
4. Chothia, T., Kawamoto, Y., Novakovic, C., Parker, D.: Probabilistic point-to-point information
leakage. In: CSF 2013. Proceedings, IEEE (2013) 193–205
5. Chothia, T., Kawamoto, Y., Novakovic, C.: Leakwatch: Estimating information leakage fromjava programs. In Kutylowski, M., Vaidya, J., eds.: ESORICS 2014. Proceedings, Part II.
Volume 8713 of Lecture Notes in Computer Science., Springer (2014) 219–236
6. Boreale, M., Paolini, M.: On formally bounding information leakage by statistical estimation.
In Chow, S.S.M., Camenisch, J., Hui, L.C.K., Yiu, S., eds.: ISC 2014. Proceedings. Volume8783 of Lecture Notes in Computer Science., Springer (2014) 216–236
7. Clark, D., Hunt, S., Malacaria, P.: Quantitative analysis of the leakage of confidential data.
Electr. Notes Theor. Comput. Sci. 59(3) (2001) 238–251
8. Köpf, B., Basin, D.A.: An information-theoretic model for adaptive side-channel attacks. In:
Proc. of CCS, ACM (2007) 286–296
9. Chatzikokolakis, K., Palamidessi, C., Panangaden, P.: Anonymity protocols as noisy channels.
Inf. and Comp. 206(2–4) (2008) 378–401
10. Moddemeijer, R.: On estimation of entropy and mutual information of continuous distributions.
Signal Processing 16 (1989) 233–248
11. Brillinger, D.R.: Some data analysis using mutual information. Brazilian Journal of Probability
and Statistics 18(6) (2004) 163–183
12. Smith, G.: On the foundations of quantitative information flow. In de Alfaro, L., ed.:FOSSACS 2009. Proceedings. Volume 5504 of Lecture Notes in Computer Science., Springer(2009) 288–302
13. Jensen, F.V.: Introduction to Bayesian Networks. 1st edn. Springer-Verlag New York, Inc.,
Secaucus, NJ, USA (1996)
14. Gallager, R.G.: Information Theory and Reliable Communication. John Wiley & Sons, Inc.,New York, NY, USA (1968)
15. Escolano, F., Suau, P., Bonev, B.: Information Theory in Computer Vision and Pattern
Recognition. Springer, Londres (2009)16

16. MacKay, D.J.C.: Information Theory, Inference & Learning Algorithms. Cambridge University Press, New York, NY, USA (2002)
17. Wilde, M.M.: Quantum Information Theory. 1st edn. Cambridge University Press, New York,NY, USA (2013)
18. Adami, C.: Information theory in molecular biology. Physics of Life Reviews 1(1) (April
2004) 3–22
19. Yasuoka, H., Terauchi, T.: Quantitative information flow as safety and liveness hyperproperties.
Theor. Comput. Sci. 538 (2014) 167–182
20. Clarkson, M.R., Schneider, F.B.: Hyperproperties. Journal of Computer Security 18(6) (2010)
1157–1210
21. Barthe, G., Köpf, B.: Information-theoretic bounds for differentially private mechanisms. In:
Proc. of CSF, IEEE (2011) 191–204
22. Espinoza, B., Smith, G.: Min-entropy as a resource. Inf. Comput. (2013)
23. Kawamoto, Y., Chatzikokolakis, K., Palamidessi, C.: Compositionality results for quantitative
information flow. In: QEST 2014. Proceedings. (2014) 368–383
24. Kawamoto, Y., Given-Wilson, T.: Quantitative information flow for scheduler-dependent
systems. In: QAPL 2015. Proceedings. Volume 194. (2015) 48–62
25. Chothia, T., Kawamoto, Y.: Statistical estimation of min-entropy leakage (April 2014)
Manuscript.
26. Cover, T.M., Thomas, J.A.: Elements of information theory (2. ed.). A Wiley-Intersciencepublication. Wiley (2006)
27. Biondi, F., Legay, A., Traonouez, L., Wasowski, A.: QUAIL: A quantitative security analyzer
for imperative code. In Sharygina, N., Veith, H., eds.: CAV 2013. Proceedings. Volume 8044
of Lecture Notes in Computer Science., Springer (2013) 702–707
28. Biondi, F., Legay, A., Traonouez, L.M., Wasowski, A.: QUAIL https://project.inria.fr/quail/.
29. Chothia, T., Kawamoto, Y., Novakovic, C.: LeakWatch http://www.cs.bham.ac.uk/research/
projects/infotools/leakwatch/.
30. Vitter, J.S.: Random sampling with a reservoir. ACM Trans. Math. Softw. 11(1) (March 1985)
37–57
31. Chaum, D.: The dining cryptographers problem: Unconditional sender and recipient untraceability. Journal of Cryptology 1 (1988) 65–75
32. Denning, D.E.: A lattice model of secure information flow. Commun. ACM 19(5) (1976)
236–243
33. Gray, J.W.: Toward a mathematical foundation for information flow security. In: IEEE
Symposium on Security and Privacy. (1991) 21–35
34. Clark, D., Hunt, S., Malacaria, P.: A static analysis for quantifying information flow in a
simple imperative language. Journal of Computer Security 15(3) (2007) 321–371
35. Backes, M., Köpf, B., Rybalchenko, A.: Automatic discovery and quantification of information
leaks. In: 30th IEEE Symposium on Security and Privacy (S&P 2009), 17-20 May 2009,
Oakland, California, USA, IEEE Computer Society (2009) 141–153
36. McCamant, S., Ernst, M.D.: Quantitative information flow as network flow capacity. In
Gupta, R., Amarasinghe, S.P., eds.: Proceedings of the ACM SIGPLAN 2008 Conference on
Programming Language Design and Implementation, Tucson, AZ, USA, June 7-13, 2008,
ACM (2008) 193–205
37. Newsome, J., McCamant, S., Song, D.: Measuring channel capacity to distinguish undue
influence. In Chong, S., Naumann, D.A., eds.: Proceedings of the 2009 Workshop on
Programming Languages and Analysis for Security, PLAS 2009, Dublin, Ireland, 15-21 June,
2009, ACM (2009) 73–85
38. Köpf, B., Rybalchenko, A.: Approximation and randomization for quantitative informationflow analysis. In: CSF 2010. Proceedings, IEEE Computer Society (2010) 3–14

17

39. Chothia, T., Kawamoto, Y., Novakovic, C.: leakiEst http://www.cs.bham.ac.uk/research/
projects/infotools/leakiest/.
40. Barbot, B., Haddad, S., Picaronny, C.: Coupling and importance sampling for statisticalmodel checking. In Flanagan, C., König, B., eds.: TACAS 2012. Proceedings. Volume 7214
of Lecture Notes in Computer Science., Springer (2012) 331–346
41. Clarke, E.M., Zuliani, P.: Statistical model checking for cyber-physical systems. In Bultan,
T., Hsiung, P., eds.: ATVA 2011. Proceedings. Volume 6996 of Lecture Notes in Computer
Science., Springer (2011) 1–12
42. Fremont, D.J., Seshia, S.A.: Speeding up SMT-based quantitative program analysis. In
Rümmer, P., Wintersteiger, C.M., eds.: SMT 2014. Proceedings. Volume 1163 of CEUR
Workshop Proceedings., CEUR-WS.org (2014) 3–13
43. Chakraborty, S., Fremont, D.J., Meel, K.S., Seshia, S.A., Vardi, M.Y.: On parallel scalable
uniform SAT witness generation. In Baier, C., Tinelli, C., eds.: TACAS 2015. Proceedings.
Volume 9035 of Lecture Notes in Computer Science., Springer (2015) 304–319
44. Chakraborty, S., Meel, K.S., Vardi, M.Y.: A scalable approximate model counter. In Schulte,C., ed.: CP 2013. Proceedings. Volume 8124 of Lecture Notes in Computer Science., Springer(2013) 200–216
45. Biondi, F., Legay, A., Malacaria, P., Wasowski, A.: Quantifying information leakage ofrandomized protocols. Theor. Comput. Sci. 597 (2015) 62–87
46. Phan, Q., Malacaria, P.: Abstract model counting: a novel approach for quantification of
information leaks. In Moriai, S., Jaeger, T., Sakurai, K., eds.: AsiaCCS 2014. Proceedings,
ACM (2014) 283–292
47. Phan, Q., Malacaria, P., Pasareanu, C.S., d’Amorim, M.: Quantifying information leaks using
reliability analysis. In Rungta, N., Tkachuk, O., eds.: SPIN 2014. Proceedings, ACM (2014)
105–108
48. Kang, M.G., McCamant, S., Poosankam, P., Song, D.: DTA++: dynamic taint analysis withtargeted control-flow propagation. In: NDSS 2011. Proceedings. (2011)
49. Chadha, R., Mathur, U., Schwoon, S.: Computing information flow using symbolic modelchecking. In: FSTTCS 2014. Proceedings. (2014) 505–516
50. Biondi, F., Legay, A., Quilbeuf, J.: Comparative analysis of leakage tools on scalable casestudies. In Fischer, B., Geldenhuys, J., eds.: SPIN 2015, Proceedings. Volume 9232 of Lecture
Notes in Computer Science., Springer (2015) 263–281
51. Quinlan, J.R.: Induction of decision trees. Machine Learning 1(1) 81–106

18

A

Omitted Proofs

We present proofs omitted in the paper. We refer to literature [26] for the definitions of
the variance V (X) and the covariance Cov (X, Y ).
Hereafter we denote by Q the joint sub-distribution obtained by summing Qj ’s:
Xdef
Q[x, y] =Qj [x, y] .
j ∈JWe write qxy to denote Q[x, y] for abbreviation. Then qxy is the probability that theexecution of S yields one of Tj ’s and has input x and output y.
A.1

Proofs for the Main Results (without assuming the knowledge of the prior)

Proof (Proof of Theorem 1). Recall that the empirical joint probability is given byP̂XY [x, y] = qxy +X θi Kixy
i∈I

ni

.

Then the empirical joint entropy is defined by
X
Ĥ(X, Y ) = −P̂XY [x, y] log P̂XY [x, y]x∈X ,y∈Y

=−

X 

qxy +

x∈X ,y∈Y

X θi Kixy 
ni

i∈I


X θi Kixy 
log qxy +.
nii∈IWe define the set of pairs consisting of secrets and observables that appear with non-zeroprobabilities in the execution of the whole system S:
D = {(x, y) ∈ X × Y : PXY [x, y] 6= 0} .
Let Kixy = E(Kixy ). Then Kixy = ni Di [x, y] = ni Rθii[x,y] . By the Taylor expansion
w.r.t. Kixy for all i ∈ I,
X
X
Ĥ(X, Y ) = −(Axy +
Bixy (Kixy − Kixy )(x,y)∈D+

X i∈I
Cijxy (Kixy − Kixy )(Kjxy − Kjxy )i,j∈I,
Xi6=j

Ciixy (Kixy − Kixy )2 + O(n−2
i ))

+

i∈I

where

X θl Klxy – Axy = qxy +log qxy +
,
nl
nl
l∈I
l∈I


X θl Klxy θi– Bixy =1 + log qxy +
,
ni
nl


X θl Klxy 

l∈I

19

– Cijxy =2ni njθi θjP θ K ,qxy + l∈I l nlxyl

To compute the expectation E(Ĥ(X, Y )) of the joint entropy, it should be noted that
if i 6= j then Kixy and Kjxy are independent, hence E((Kixy −Kixy )(Kjxy −Kjxy )) = 0.
Also note that (Kixy : (x, y) ∈ D) follows the multinomial distribution with the sample
size ni and the probabilities Riθ[x,y]for (x, y) ∈ D, therefore
i





Ri [x, y]Kixy
Ri [x, y]E (Kixy − Kixy )2 = ni
1−
= Kixy 1 −
.
θi
θi
ni
We will also use E(Kixy − Kixy ) = 0, which is immediate from Kixy = E(Kixy ).
Then the expectation of Ĥ(X, Y ) is given by:E(Ĥ(X, Y )) = −X

X(Axy +
Bixy E(Kixy − Kixy )i∈I(x,y)∈D+X

Cijxy E (Kixy − Kixy )(Kjxy − Kjxy )i,j∈I, i6=jX+
Ciixy E (Kixy − Kixy )2 + O(n−2
i ))
i∈I

= H(X, Y ) −

X θ2
i

i∈I

2n2i



K
Kixy 1 − nixyiX(x,y)∈D q
xy +X θl Klxynll∈I= H(X, Y ) −

X θ2
i

i∈I

2ni

X Di [x, y] (1 − Di [x, y])
PXY [x, y](x,y)∈D

where we use Di [x, y] = Riθ[x,y].
iNext we calculate the expectation E(Ĥ(Y )) of the empirical entropy of observables.
For simplicity we use the following
notations. Let Y + be the setno of observables with nonP+zero probabilities: Y = y ∈ Y : x∈Dy PXY [x, y] 6= 0 . Let Dx = {y: (x, y) ∈PD} and Dy = {x: (x, y) ∈ D}. For each i ∈ I and y ∈ Y let Li·y = x∈Dy Kixy .
Then the empirical entropy of observables is defined byĤ(Y ) = −
=−

X

X

y∈Y +

x∈Dy

XX
y∈Y +

x∈Dy


P̂XY [x, y] log

qxy +

X

!
P̂XY [x, y]x∈Dy

X θi Li·y 
i∈I

ni

20

log

X
x∈Dy

qxy +

X θi Li·y 
i∈I

ni

.

P
Let Li·y = E(Li·y ). Then Li·y = x∈Dy Kixy . By the Taylor expansion w.r.t. Li·y for
all i ∈ I,
X
X
X
Ĥ(Y ) = −(A·y +
Bi·y (Li·y − Li·y ) +Cij·y (Li·y − Li·y )(Lj·y − Lj·y )
y∈Y +

i∈I

i,j∈I, i6=jX+
Cii·y (Li·y − Li·y )2 + O(n−2
i ))
i∈I

where
– A·y =

X

qxy +

x∈Dy

X θi Ll·y 
nl

l∈I

log

X

qxy +

x∈Dy

X θi Ll·y 
l∈I

nl

,


X
X θl Ll·y θiqxy +– Bi·y =
1+
,
ni
nl
x∈Dy

l∈I

θi θj

– Cij·y =2ni njPx∈Dy qxy +θl Ll·y
l∈I
nl

P

,

To compute the expectation E(Ĥ(Y )), it should be noted that if i 6= j then Li·yand Lj·y are independent, hence E (Li·y − Li·y )(Lj·y − Lj·y ) = 0. Also note that
(Li·y : y ∈ Y +P) follows the multinomial distribution with the sample size ni and theprobabilitiesx∈Dy Ri [x,y]θifor y ∈ Y + , therefore2

E (Li·y − Li·y )Px∈Dy Ri [x,y]
= ni
1−
θi
θi


P
P

x∈Dy Kixy=.
1−x∈Dy Kixy
niPx∈Dy Ri [x,y]We will also use E(Li·y − Li·y ) = 0, which is immediate from Li·y = E(Li·y ).
The expectation E(Ĥ(Y )) is given by:XXXE(Ĥ(Y )) = −(A·y +
Bi·y E(Li·y − Li·y ) +Cij·y E (Li·y − Li·y )(Lj·y − Lj·y )y∈Y +i,j∈I, i6=j
X i∈I

+
Cii·y E (Li·y − Li·y )2 + O(n−2
i ))
i∈I

P
P

X X
x∈Dy Kixy= H(Y ) −
Cii·y
K
1
−
+ O(n−2
ixy
i ).
x∈Dy
ni
i∈I y∈Y += H(Y ) −X θ2 X

where DYi [y] =y∈Y +X θ2 X D [y](1−D [y])
i

i∈I
P

2n2i


P
K
1 − x∈Dy nixyiPPθl Klxyx∈Dy qxy +l∈Inlx∈Dy Kixyii∈I= H(Y ) −P

2nix∈Dy Kixy

ni

Yi

Yi

PY [y]y∈Y +for each y ∈ Y.
21



Similarly, the expectation E(Ĥ(X)) is given by:
X θ2 X DXi [x] (1 − DXi [x])i2niPX [x]+

E(Ĥ(X)) = H(X) −

i∈I

x∈X

ˆ
The expectation of the mutual information E(I(X;Y )) is given by:ˆE(I(X;Y ))= E(Ĥ(X)) + E(Ĥ(Y )) − E(Ĥ(X, Y ))= I(X; Y )+X θ2

X D [x,y]−D [x,y]2
i

i

i

2ni
i∈I

PXY [x,y]−XD [x]−D [x]2
Xi

Xi

PX [x]−x∈X +(x,y)∈D

XD [y]−D [y]2
Yi

!

Yi

PY [y]+O(n−2i ).

y∈Y +Proof (Proof of Theorem 2). We derive the variance of the estimate as follows.
For any i, i0 ∈ I, x, x0 ∈ X and y, y 0 ∈ Y the covariance Cov (Kixy , Ki0 x0 y0) is given by:0
Cov (Kixy , Ki0 x0 y0 ) = ni Di [x, y](1 − Di [x, y])−ni Di [x, y]Di [x0 , y 0 ]if i 6= i0
if i = i0 , x = x0 and y = y 0
otherwise.

The covariance Cov (Li·y , Li·y0 ) depends on whether y = y 0 or not:Cov (Li·y , Li·y ) = Cov

X

Kixy ,X X

Kix0 yx0 ∈Dy

x∈Dy

=



X

Cov (Kixy , Kix0 y )x∈Dy x0 ∈Dy=Xni Di [x, y](1 − Di [x, y]) −X

ni Di [x, y]Di [x0 , y]x6=x0 ∈Dyx∈Dy

= ni DYi [y](1 − DYi [y])When y 6= y 0 :Cov (Li·y , Li·y0 ) = Cov
=

X

X

X

Kixy ,


Kix0 y0x∈Dyx0 ∈Dy0X

Cov (Kixy , Kix0 y0 )x∈Dy x0 ∈Dy0

= −ni

X

X

Di [x, y]Di [x0 , y 0 ]x∈Dy x0 ∈Dy0

= −ni DYi [y]DYi [y 0 ]22The variance of Ĥ(X, Y ) is given by the following.
 2V (Ĥ(X, Y )) = E Ĥ(X, Y )2 − E(Ĥ(X, Y ))X
X
X=
Bixy Bi0 x0 y0 Cov (Kixy , Ki0 x0 y0 )+ O(n−2i )(x,y)∈D (x0 ,y 0 )∈D i,i0 ∈I

=

X

ni

i∈I

X


Di [x, y]Bixy Bixy −XBix0 y0 Di [x , y ] + O(n−2
i )
0

0

(x0 ,y 0 )∈D(x,y)∈D

The variance of Ĥ(Y ) is given by the following.
 
2V (Ĥ(Y )) = E Ĥ(Y )2 − E(Ĥ(Y ))X X X=
Bi·y Bi0 ·y0 Cov (Li·y , Li0 ·y0 ) + O(n−2i )y∈Y + y 0 ∈Y + i,i0 ∈I

=

X

ni

X



X
DYi [y]Bi·y Bi·y −Bi·y0 DYi [y 0 ] + O(n−2i )y 0 ∈Y +

y∈Y +

i∈I

Similarly, the variance of Ĥ(X) is given by the following.
V (Ĥ(X)) =

X
i∈I

ni

X



X
0
0
DXi [x]Bix· Bix· −
Bix · DXi [x ] + O(n−2i )x0 ∈X +x∈X +The covariance between Ĥ(X, Y ) and Ĥ(Y ) is given by:
Cov (Ĥ(Y ), Ĥ(X, Y )) =

X X

=

X X

X

Bixy Bi·y0 Cov (Kixy , Li·y0 ) + O(n−2i )i∈I (x,y)∈D y 0 ∈Y +

X



X
Bixy Bi·y0 Cov Kixy ,Kix0 y0 +O(n−2i )x0 ∈Dy0i∈I (x,y)∈D y 0 ∈Y +

=

X X

=

ni

X

Bi·y0 Cov (Kixy , Kix0 y0 )+O(n−2i )(x0 ,y 0 )∈Di∈I (x,y)∈D

X

X

Bixy



X
Di [x, y]Bixy Bi·y −Bi·y0 Di [x0 , y 0 ] +O(n−2i )(x0 ,y 0 )∈Di∈I (x,y)∈D

Similarly, the covariance between Ĥ(X, Y ) and Ĥ(X) is given by:
Cov (Ĥ(X), Ĥ(X, Y )) =

X
i∈I

ni

X



X
Di [x, y]Bixy Bix· −Bix0 · Di [x0 , y 0 ] +O(n−2i )(x0 ,y 0 )∈D(x,y)∈D

23

The covariance between Ĥ(X) and Ĥ(Y ) is given by:
Cov (Ĥ(X), Ĥ(Y )) =

X X

=

X X

X

Bix· Bi·y0 Cov (Lix· , Li·y0 )+O(n−2i )i∈I x∈X + y 0 ∈Y +X

Bix· Bi·y0 Cov

Xi∈I x∈X + y 0 ∈Y +

=

X X

=

X

Bix·

ni

i∈I



Kix0 y0 +O(n−2i )x0 ∈Dy0

Bi·y0 Cov (Kixy , Kix0 y0 )+O(n−2i )(x0 ,y 0 )∈Di∈I (x,y)∈D

X

Kixy ,

y∈Dx

X

X



X
Di [x, y]Bix· Bi·y −Bi·y0 Di [x0 , y 0 ] +O(n−2i )(x0 ,y 0 )∈D(x,y)∈D

Therefore the variance of the mutual information is as follows:ˆV (I(X;Y ))= V Ĥ(X) + Ĥ(Y ) − Ĥ(X, Y )= V (Ĥ(X)) + V (Ĥ(Y )) + V (Ĥ(X, Y ))+ 2Cov (Ĥ(X), Ĥ(Y )) − 2Cov (Ĥ(X), Ĥ(X, Y )) − 2Cov (Ĥ(Y ), Ĥ(X, Y ))
 



X
X
X X
=
ni
Di [x, y] Bix Bix −Bix0 Di [x0 , y 0 ] + Biy Biy −Biy0 Di [x0 , y 0 ](x0 ,y 0 )∈Di∈I (x,y)∈D(x0 ,y 0 )∈D






X
X
+Bixy Bixy −Bix0 y0 Di [x0 , y 0 ] +2Bix Biy −Biy0 Di [x0 , y 0 ](x0 ,y 0 )∈D(x0 ,y 0 )∈D




X
X
0 0
0 0
−2Bixy Bix −Bix0 Di [x , y ] −2Bixy Biy −Biy0 Di [x , y ] +O(n−2i )(x0 ,y 0 )∈D(x0 ,y 0 )∈D




2 X

2
X θ2 Xi 
 +O(n−2
Di [x, y] 1 + log PX [x]PY [y] −Di [x, y] 1 + log PX [x]PY [y]
=
i )
ni

i∈I

A.2

PXY [x,y]

PXY [x,y](x,y)∈D(x,y)∈D

Proofs for Adaptive Analysis

To prove Theorem 3 it suffices to show the following:
Theorem 6. Let v1 , v2 , . . . , vm be m positive
Pm real numbers. Let n, n1 , n2 , . . . , nm be(m + 1) positive real numbers such that i=1 ni = n. Then
m
X
vi

1
≥
n
n
i=1 i

m
X
√

!2
vi

.

i=1

√

vi n
The equality holds when ni = Pm √j=1

vj

for all i = 1, 2, . . . , m.

24

Proof. We prove the theorem by induction on m. When m = 1 the equality holds
trivially. When m = 2 it is sufficient to prove√ 2√
v1 + v2
v1
v2
+
≥
.
n1
n2
n1 + n2
By n1 , n2 > 0, this is equivalent to√ 2√(n1 + n2 )(n2 v1 + n1 v2 ) ≥ n1 n2 ( v1 + v2 ) .
We obtain this by√√ 2(n1 + n2 )(n2 v1 + n1 v2 ) − n1 n2 ( v1 + v2 )√= (n1 + n2 )n2 v1 + (n1 + n2 )n1 v2 − n1 n2 (v1 + 2 v1 v2 + v2 )√= n22 v1 + n21 v2 − 2n1 n2 v1 v2√√= (n2 v1 − n1 v2 )2≥ 0.
Next we prove the inductive step as follows.
m
X

m−1
X vi
vi
vm
=
+
n
n
n
i
m
i=1 i
i=1

1
≥
n1 + . . . + nm−1

≥

m−1
X

√

√

!2
vi

+

i=1

1
(n1 + . . . + nm−1 ) + nm

vm 2
nm

2
v
!2
u m−1
u
√ 
t X √
vi+ vm 
(by induction hypothesis)(by induction hypothesis)

i=1

!2
m−1
X√
√
1
=
vi + vm
n1 + . . . + nm i=1
!2
m
1 X√
=
vi .
n i=1
√
vi n
Finally, when ni = Pm √ for all i = 1, 2, . . . , m, the equality holds:
j=1 vj
!2
Pm √
m
m
m
X
X
vi ( j=1 vj )
vi
1 X√
=
=
vi .
√
n
vi n
n i=1
i=1 i
i=1
A.3

Proofs for Other Results (with assuming the knowledge of the prior)

Proof (Proof of Proposition 1). Since the precise prior PX is provided to the analyst,
we haveˆ
E(I(X;Y )) = E(H(X)) + E(Ĥ(Y )) − E(Ĥ(X, Y )).
25

By using the results on E(Ĥ(Y )) and E(Ĥ(X, Y )) in the proof of Theorem 1, we
obtain the proposition.
Proof (Proof of Proposition 2). Since the precise prior PX is provided to the analyst,
we haveˆV (I(X;Y )) = V H(X) + Ĥ(Y ) − Ĥ(X, Y )= V (H(X) + V (Ĥ(Y )) + V (Ĥ(X, Y )) − 2Cov (Ĥ(Y ), Ĥ(X, Y )).
By using the results on V (Ĥ(Y )), V (Ĥ(X, Y )) Cov (Ĥ(Y ), Ĥ(X, Y )) in the proof of
Theorem 2, we obtain Proposition 2.
Then the following proposition is straightforward from the proof of Theorem 3.
Proposition 3. For each i ∈ I and x ∈ X , let vix be the following intermediatevariance of the component Six .
!
2  X2XbY [y]bY [y]PP
2
D̂i [y|x] log Pb [x,y]vix = θixD̂i [y|x] log Pb [x,y] −
.
XY

XY

y∈Dx

y∈Dx

Given the total sample size n, the variance of the estimated mutual information isminimized if, for all i ∈ I and x ∈ X , the sample size ni and the importance prior λi
satisfy the following:√vix nni λi [x] = Pm √.
j=1 vjx
A.4

Proofs for the Results on the Abstraction-Then-Sampling (with assuming
the knowledge of some components)

Proof (Proof of Theorem 4). We use notations that we have introduced in the previous
proofs. For each i ∈ I, let Xi be the set of the elements of X that appear with non-zeroprobabilities in the component Si . Recall that for each i ∈ I ? , πi [x] is the probability of
having an input x in the component Si .
For each i ∈ I ? all the non-zero rows of Si ’s channel matrix are the same conditional[x,y][x0 ,y]distribution; i.e., for each x, x0 ∈ Xi and y ∈ Yi , PXY= PXY
when πi [x] 6= 0πi [x]
πi [x0 ]0and πi [x ] 6= 0. Therefore it is sufficient to estimate only one of the rows. We executethe component Si with an identical input x ∈ X ni times to record the traces. Let Ki·ybe the number of traces of the component Si that outputs y.
From these numbers of traces we define the empirical joint (full) distribution D̂i of
X and Y as
def πi [x]Ki·yD̂i [x, y] =niSince Si is executed with probability θi , the empirical sub-distribution R̂i is given bydefR̂i [x, y] = θi D̂i [x, y] =26

θi πi [x]Ki·y.
ni

The empirical joint probability is given by
X θi Kixy
X θi πi [x]Ki·y
+
.
ni
ni
?
?

P̂XY [x, y] = qxy +

i∈I

i∈I\I

Then the empirical joint entropy is defined byĤI ? (X, Y )X=−
P̂XY [x, y] log P̂XY [x, y](x,y)∈DX θ π [x]K  X θK
X θ π [x]K 
X 
X θK
i i
i·y
i ixy
i i
i·y
i ixy
+
log qxy +
+
.
=−
qxy +
ni
ni
ni
ni
(x,y)∈Di∈I ?

i∈I\I ?

i∈I ?

i∈I\I ?

[x,y]i [x,y]Let Ki·y = E(Ki·y ). Then Ki·y = ni πDii[x]= nθi R
. By the Taylor expansion w.r.t.
i πi [x]Kixy for all i ∈ I \ I ? and Ki·y for all i ∈ I ? ,XXXĤI ? (X, Y ) = −(Axy +
Bixy (Kixy − Kixy ) +πi [x]Bixy (Ki·y − Ki·y )i∈I ?

i∈I\I ?

(x,y)∈D+

X

Cijxy (Kixy − Kixy )(Kjxy − Kjxy )i,j∈I\I ? , i6=j+X

πj [x]Cijxy (Kixy − Kixy )(Kj·y − Kj·y )i∈I\I ? , j∈I ?

+X

πi [x]πj [x]Cijxy (Ki·y − Ki·y )(Kj·y − Kj·y )i,j∈I ? , i6=j+

X

Ciixy (Kixy − Kixy )2 +X

πi [x]2 Ciixy (Ki·y − Ki·y )2 + O(n−2
i ))

i∈I ?

i∈I\I ?


where
X θK
X θ π [x]K  X θK
X θ π [x]K 
l·y
l·y
l lxy
l l
l lxy
l l
– Axy = qxy +
+
log
q
+
+
,
xy
nl
nl
nl
nl
?

?

?

l∈I
l∈I\I
 l∈I\I 
X θ π [x]K 
X θK
θi
l l
l·y
l lxy
– Bixy =+,1 + log qxy +
nl
nl
ni
?
?
l∈I

l∈I\I

– Cijxy =

l∈I ?

θi θj


,
P
P
θ K
θl πl [x]Kl·y
2ni nj qxy + l∈I\I ? l nlxy
+
?
l∈I
nl
l

To compute the expectation E(ĤI ? (X, Y )) of the joint entropy, it should be notedthat if i 6= j then Kixy and Kjxy are independent, hence E((Kixy − Kixy )(Kjxy −Kjxy )) = 0. Similarly, E((Kixy −Kixy )(Kj·y −Kj·y )) = 0 and E((Ki·y −Ki·y )(Kj·y −Kj·y )) = 0. Also note that for each i ∈ I ? , (Ki·y : y ∈ Y + ) follows the multinomial
i [x,y]distribution with the sample size ni and the probabilities R
θi πi [x] for (x, y) ∈ D, thereforeRi [x, y]E (Ki·y − Ki·y )2 = ni
θi πi [x]


1−

27

Ri [x, y]θi πi [x]





Ki·y
= Ki·y 1 −.
niWe will also use E(Ki·y − Ki·y ) = 0, which is immediate from Ki·y = E(Ki·y ).
Then the expectation of ĤI ? (X, Y ) is given by:E(ĤI ? (X, Y ))XXX
πi [x]Bixy E(Ki·y − Ki·y )=−(Axy +
Bixy E(Kixy − Kixy ) +i∈I ?

i∈I\I ?

(x,y)∈DX+

Cijxy E (Kixy − Kixy )(Kjxy − Kjxy )i,j∈I\I ? , i6=jX+

πj [x]Cijxy E (Kixy − Kixy )(Kj·y − Kj·y )

i∈I\I ? , j∈I ?

+X

πi [x]πj [x]Cijxy E (Ki·y − Ki·y )(Kj·y − Kj·y )i,j∈I ? , i6=j

+

X

 X

Ciixy E (Kixy − Kixy )2 +πi [x]2 Ciixy E (Ki·y − Ki·y )2 + O(n−2
i ))
i∈I ?

i∈I\I ?

X θ2i
= H(X, Y ) −
2
2n
i
?
i∈I\I

= H(X, Y ) −

X θ2

Kixy
ni

PXY [x, y](x,y)∈D
i

2ni
?



K
X Ki·y 1 − ni·yiX θ2 πi [x]2
i

−

2n2i

i∈I ?

X D [x,y](1−D [x,y])

i

i∈I\I

X Kixy 1 −i

PXY [x,y]−X θ2

PXY [x, y]

X D [x,y](π [x]−D [x,y])ii∈I(x,y)∈D(x,y)∈D
i

2ni
?

i

i

PXY [x,y](x,y)∈D[x,y]where we use Ki·y = ni πDii[x].

Next we calculate the expectation E(ĤI ? (Y )) of the empirical entropy of observables. Recall that Y + is the set of observables with non-zero probabilities, D is the set ofpairs of secrets and observables with non-zero probabilities, Dx = {y:P (x, y) ∈ D} andDy = {x: (x, y) ∈ D}. For each i ∈ I \ I ? and y ∈ Y let Li·y = x∈Dy Kixy . Thenthe empirical entropy of observables is defined byXθ K   X
Xθ K 
X X
Xθ L
Xθ L
i i·y
i i·y
i i·y
i i·y
+
+
ĤI ? (Y ) = −
qxy +
log
qxy +
.
ni
ni
ni
ni
y∈Y + x∈Dyi∈I ?

i∈I\I ?

For i ∈ I \ I ? , let Li·y = E(Li·y ). Then Li·y =– A·y =

X

qxy +

x∈Dy

X θL
i

l·y

nl

P

x∈Dy Kixy .

Xθ K   X
X θL
X θK 
i l·y
l l·y
l l·y
+
log
q
+
+
,
xy
nl
nl
nl

l∈I\I ?

l∈I ?

x∈Dy

l∈I\I ?

X
X θL
X θ K 
θi
l l·y
l l·y
– Bi·y =1 + log
qxy +
+
,
nl
nl
ni
?
?
x∈Dy

l∈I\I

l∈I

θi θj

– Cij·y =2ni njPi∈I ?

i∈I\I ?

x∈Dy

x∈Dy qxy +P

l∈I\I ?

28P
θl Ll·yθ K+ l∈I ? l nll·y
nl

,

l∈I ?

To compute the expectation E(ĤI ? (Y )), it should be noted that if i 6= j then
Li·y and Lj·y are independent, hence E (Li·y − Li·y )(Lj·y − Lj·y ) = 0. Similarly,
E (Li·y − Li·y )(Kj·y − Kj·y ) = 0 and E (Ki·y − Ki·y )(Kj·y − Kj·y ) = 0.
By the Taylor expansion w.r.t. Li·y for all i ∈ I \ I ? and Ki·y for all i ∈ I ? , theexpectation E(ĤI ? (Y )) is given by:E(ĤI ? (Y )) = H(Y ) −

X X


 X

Cii·y E (Ki·y − Ki·y )2 + O(n−2Cii·y E (Li·y − Li·y )2 +i )y∈Y + i∈I\I ?
X θ2 X DYi [y] (1 − DYi [y])i= H(Y ) −

i∈I

2ni

where for each i ∈ I ? , DYi [y] =PY [y]

y∈Y +

i∈I ?

+ O(n−2i )Ki·y
Di [x,y]ni = πi [x] for all x ∈ X .

The expectation E(ĤI ? (X)) is given by:E(ĤI ? (X)) = H(X) −

X
i∈I\I

θi2 X DXi [x] (1 − DXi [x])2niPX [x]?
+x∈X

The expectation of the mutual information E(IˆI ? (X; Y )) is given by:E(IˆI ? (X; Y ))= E(ĤI ? (X)) + E(ĤI ? (Y )) − E(ĤI ? (X, Y ))X θ2  X D [x,y]−D [x,y]2 XD [x]−D [x]2 XD [y]−D [y]2
i
i
i
Xi
Xi
Yi
Yi
−
−
= I(X; Y ) +PXY [x,y]PX [x]PY [y]
2ni?
++(x,y)∈D
i∈I\I
x∈X
y∈Y
X θ2  X D [x,y]π [x]−D [x,y]2 XD [y]−D [y]2
i
i
i
i
Yi
Yi
+
−
+ O(n−2i ).
PXY [x,y]
PY [y]
2n
i
?
+
i∈I

x∈Dx

y∈Y

Proof (Proof of Theorem 5). We derive the variance of the estimate as follows. We will
use the covariances Cov (Kixy , Ki0 x0 y0 ) and Cov (Li·y , Li0 ·y0 ) shown in the proof of
Theorem 2.
For each i, i0 ∈ I ? and y, y 0 ∈ Y the covariance Cov (Ki·y , Ki0 ·y0 ) is as follows:

Cov (Ki·y , Ki0 ·y0 ) =0ni Di [x,y](πi [x]−Di [x,y])= ni DYi [y](1 − DYi [y])πi [x]2 ni Di [x,y]Di [x,y0 ]−= −ni DYi [y]DYi [y 0 ]πi [x]2

where x is an arbitraly element of Xi
29

if i 6= i0
if i = i0 and y = y 0
otherwise.

The variance of ĤI ? (X, Y ) is given by the following.
 
2V (ĤI ? (X, Y )) = E ĤI ? (X, Y )2 − E(ĤI ? (X, Y ))X
X
X=
Bixy Bi0 x0 y0 Cov (Kixy , Ki0 x0 y0 )i,i0 ∈I\I ? (x,y)∈D (x0 ,y 0 )∈D

+

X

X

X

πi [x]Bixy πi0 [x0 ]Bi0 x0 y0 Cov (Ki·y , Ki0 ·y0 )+ O(n−2i )i,i0 ∈I ? (x,y)∈D (x0 ,y 0 )∈D

X

=

ni

i∈I\I ?

+X

X

Di [x, y]Bixy Bixy −

X

X

0

0



Bix0 y0 Di [x , y ](x0 ,y 0 )∈D(x,y)∈D

ni

i∈I ?





X
DYi [y]πi [x]πi [x0 ]Bixy Bix0 y −Bix0 y0 DYi [y 0 ] + O(n−2i )Xy 0 ∈Dx0(x,y)∈D x0 ∈X +The variances of ĤI ? (Y ) and ĤI ? (X) are given by the following.
X X
X
V (ĤI ? (Y )) =Bi·y Bi0 ·y0 Cov (Li·y , Li0 ·y0 ) +Bi·y Bi0 ·y0 Cov (Ki·y , Ki0 ·y0 ) + O(n−2i )i,i0 ∈I ?

y,y 0 ∈Y + i,i0 ∈I\I ?

=

X

ni

i∈I

V (ĤI ? (X)) =X
i∈I\I ?

XX
0
DYi [y]Bi·y Bi·y −Bi·y0 DYi [y ] + O(n−2i )y 0 ∈Y +

y∈Y +

ni

X


DXi [x]Bix· Bix· −X

Bix0 · DXi [x ] + O(n−2i )0x0 ∈X +x∈X +The covariance between ĤI ? (X, Y ) and ĤI ? (Y ) is given by:X
X X
Cov (ĤI ? (Y ), ĤI ? (X, Y )) =Bixy Bi·y0 Cov (Kixy , Li·y0 )i∈I\I ? (x,y)∈D y 0 ∈Y +

+

X

X

i∈I ? (x,y)∈D

X

=

ni

i∈I\I ?

+X

πi [x]Bixy Bi·y0 Cov (Ki·y , Ki·y0 ) + O(n−2i )y 0 ∈Y +X
Di [x, y]Bixy Bi·y −Bi·y0 Di [x0 , y 0 ]X(x0 ,y 0 )∈D(x,y)∈D

ni

i∈I ?

X

X


πi [x]DYi [y]Bixy Bi·y −X
Bi·y0 DYi [y ] + O(n−2i )0y 0 ∈Y +(x,y)∈D

Similarly, the covariance between ĤI ? (X, Y ) and ĤI ? (X) is given by:


X
X
X
Cov (ĤI ? (X), ĤI ? (X, Y )) =ni
Di [x, y]Bixy Bix· −Bix0 · Di [x0 , y 0 ] + O(n−2i )i∈I\I ?

(x,y)∈D(x0 ,y 0 )∈D

The covariance between ĤI ? (X) and ĤI ? (Y ) is given by:


X
X
X
Cov (ĤI ? (X), ĤI ? (Y )) =ni
Di [x, y]Bix· Bi·y −Bi·y0 Di [x0 , y 0 ] +O(n−2i )i∈I\I ? (x,y)∈D

30(x0 ,y 0 )∈DTherefore the variance of the mutual information is as follows:
V (IˆI ? (X; Y ))
= V ĤI ? (X) + ĤI ? (Y ) − ĤI ? (X, Y )= V (ĤI ? (X)) + V (ĤI ? (Y )) + V (ĤI ? (X, Y )) + 2Cov (ĤI ? (X), ĤI ? (Y ))− 2Cov (ĤI ? (X), ĤI ? (X, Y )) − 2Cov (ĤI ? (Y ), ĤI ? (X, Y ))
 



X X
X
X
=
ni
Di [x, y] Bix Bix −Bix0 Di [x0 , y 0 ] + Biy Biy −Biy0 Di [x0 , y 0 ](x0 ,y 0 )∈D

i∈I\I ? (x,y)∈D(x0 ,y 0 )∈D





X
X
+ Bixy Bixy −Bix0 y0 Di [x0 , y 0 ] + 2Bix Biy −Biy0 Di [x0 , y 0 ](x0 ,y 0 )∈D(x0 ,y 0 )∈D





X
X
− 2Bixy Bix −Bix0 Di [x0 , y 0 ] − 2Bixy Biy −Biy0 Di [x0 , y 0 ](x0 ,y 0 )∈D

+

X

ni

i∈I ?

X

(x0 ,y 0 )∈DX
DYi [y] Bi·y Bi·y −Bi·y0 DYi [y 0 ]y 0 ∈Y +

y∈Y +

+

X

πi [x]Bixy

X



X
πi [x0 ] Bix0 y −Bix0 y0 DYi [y 0 ]y 0 ∈Dx0

x0 ∈X +

x∈Dy

−2

X


πi [x]Bixy Bi·y −X
Bi·y0 DYi [y 0 ] + O(n−2i )y 0 ∈Y +

x∈Dy





2  X2X
X θ2[x]PY [y][x]PY [y]iDi [x, y] 1 + log PPXXY−
Di [x, y] 1 + log PPXXY
=
[x,y]
[x,y]
n
i
?
(x,y)∈D

i∈I\I

+

X θ2
i

i∈I ?

ni

X

(x,y)∈D2X
DYi [y] log PY [y] −πi [x] log PXY [x, y]

y∈Y +

−

 X

x∈X

!

2
X
DYi [y] log PY [y] −πi [x] log PXY [x, y]+ O(n−2
i )

y∈Y +

B

x∈X

Estimation of Other Measures and their Confidence Intervals

In this section we show that the hybrid statistical estimation method can be used toestimate the Shannon entropy and conditional Shannon entropy.
We recall the definitions of these measures as follows. Given a prior PX on input X,
the prior uncertainty (before observing the system’s output Y ) is defined as
X
H(X) = −PX [x] log2 PX [x]x∈X

31while the posterior uncertainty (after observing the system’s output Y ) is defined as
X
X
H(X|Y ) = −PY [y]PX|Y [x|y] log2 PX|Y [x|y],
y∈Y +

x∈X

where PY is the probability distribution on the output Y , Y + is the set of outputs in Y
with non-zero probabilities, and PX|Y is the conditional probability distribution of X
given Y :PY [y] =X

PXY [x0 , y]

PX|Y [x|y] =x0 ∈XPXY [x, y]
PY [y]

if PY [y] 6= 0.

H(X|Y ) is also called the conditional entropy of X given Y .
B.1

Estimation of Shannon Entropy

The new method can also be used to estimate the Shannon entropy H(X) of a randomvariable X in a probabilistic system. For each i ∈ I let DXi be the sub-distribution of X
for the component Si . Then the expectation and variance of the estimate are obtained in
the same way as in the previous sections.
Proposition 4. The expectation E(Ĥ(X)) of the Shannon entropy is given by
H(X) −

X θ2
i

i ∈I

2ni

X DXi [x] (1 − DXi [x])PX [x]x ∈X ++ O(n−2i ).

Proposition 5. The variance V (Ĥ(X)) of the Shannon entropy is given by!
2  X2
X θ2 Xi
DXi [x] 1 + log PX [x] −DXi [x] 1 + log PX [x]+ O(n−2
i ).
ni
+
+
i∈I

x∈X

x∈X

Proof. By the proof of Theorem 1 and 2 we obtain E(Ĥ(X)) and V (Ĥ(X)).
From these we obtain the bias and confidence interval of the Shannon entropy
estimates.
Note that these propositions can respectively be derived from Theorems 1 and 2,
because the Shannon entropy coincides with the mutual information of a random variable
ˆX). Therefore we can apply Theorem 3 and adaptively obtainwith itself: Ĥ(X) = I(X;
the optimal sample sizes ni .
B.2

Estimation of Conditional Entropy

The new method can also estimate the conditional Shannon entropy H(X|Y ) of arandom variable Y given a random variable X in a probabilistic system. Intuitively,
H(X|Y ) represents the uncertainty of a secret X after observing an output Y of thesystem. The expectation and variance of the conditional entropy are obtained from thoseof the mutual information in the case where the analyst knows the prior.
32

Observable
0

1

2

3

4

5

6

7

8

9

0 0.2046 0.1102 0.0315 0.0529 0.1899 0.0064 0.0791 0.1367 0.0386 0.1501
1 0.0852 0.0539 0.1342 0.0567 0.1014 0.1254 0.0554 0.1115 0.0919 0.1844
2 0.1702 0.0542 0.0735 0.0914 0.0639 0.1322 0.1119 0.0512 0.1172 0.1343

Secret

3 0.0271 0.1915 0.0764 0.1099 0.0982 0.0761 0.0843 0.1364 0.0885 0.1116
4 0.0957 0.1977 0.0266 0.0741 0.1496 0.2177 0.0610 0.0617 0.0841 0.0318
5 0.0861 0.1275 0.1565 0.1193 0.1321 0.1716 0.0136 0.0984 0.0183 0.0766
6 0.0173 0.1481 0.1371 0.1037 0.1834 0.0271 0.1289 0.1690 0.0036 0.0818
7 0.0329 0.0825 0.0333 0.1622 0.1530 0.1378 0.0561 0.1479 0.0212 0.1731
8 0.1513 0.0435 0.0527 0.2022 0.0189 0.2159 0.0718 0.0063 0.1307 0.1067
9 0.0488 0.1576 0.1871 0.1117 0.1453 0.0349 0.0549 0.1766 0.0271 0.056

Fig. 8: Channel matrix for the experiments in Section 6.1.

Proposition 6. The expectation E(Ĥ(X|Y )) of the conditional Shannon entropy isˆˆgiven by H(X) − E(I(X;Y )) where E(I(X;Y )) is the expectation of the mutual
information in the case where the analyst knows the prior (shown in Proposition 1).
ˆˆY ), we obtain E(Ĥ(X|Y )) = H(X)−E(I(X;Y )).
Proof. By Ĥ(X|Y ) = H(X)−I(X;Therefore the proposition follows.
Proposition 7. The variance V (Ĥ(X|Y )) of the conditional Shannon entropy coincides
ˆwith the variance V (I(X;Y )) of the mutual information in the case where the analyst
knows the prior (shown in Proposition 2).
ˆˆ
Proof. By Ĥ(X|Y ) = H(X) − I(X;
Y ), we obtain V (Ĥ(X|Y )) = V (I(X;Y )).
Therefore the proposition follows.

C

Details of Evaluation

In this section we describe more details of the discussion on the tradeoff between thecost and quality of the estimation in Section 6.1.
In Fig. 3 we showed the sampling distribution of the mutual information estimate of
the joint distribution in Fig. 1 in Section 1. The graph is obtained from 1000 samples
each of which is generated by combining trace analysis on a component and statisticalanalysis on 3 components (using 5000 randomly generated traces).

33

In Fig. 4a we illustrated the relationships between the size of the confidence interval
and the sample size in the statistical analysis. We used an example with the randomly
generated 10 × 10 channel matrix presented in Fig. 8 and the uniform prior. The graphshows the frequency (on the y axis) of the corrected mutual information estimates (onthe x axis) that are obtained by estimating the mutual information value 1000, 5000 and√
10000 times. When the sample size is k times larger then the confidence interval is ktimes narrower.
In Fig. 4b we illustrated the relationships between the size of the confidence interval
and the amount of precise analysis. The graph shows the frequency (on the y axis) of thecorrected mutual information estimates (on the x axis) that are obtained by estimating
the mutual information value 1000 times when statistical analysis is applied to a 10 × 2,
10 × 5 and 10 × 10 sub-matrix of the full 10 × 10 matrix. Using statistical analysis only
on a smaller component (10 × 2 sub-matrix) yields a smaller confidence interval thanusing it on the whole system (10 × 10 matrix). More generally, if we perform precise
analysis on larger components, then we have a smaller confidence interval.

D

On the Division into Components of the Shifting Window
BenchmarkIn this section we briefly discuss how the Shifting Window benchmark presented inFig. 7 can be divided into components using the procedure in Fig. 2.
As discussed, the division into components follows the conditional branching, andsince the benchmark has only one conditional statement in Line 7 we can divide into
two components. We will call component S the one corresponding to the then branchof the conditional (i.e. Line 8) and component T the one corresponding to the elsebranch of the conditional (i.e. Line 10). The probability of each component corresponds
to that of the conditional guard being true or false, and can be computed from the priordistribution on the secret.
Now for each component we need to determine which type of analysis to use. For
both components it is easy to see that the output does not depend on the value of thesecret, so we mark them for the abstraction-then-sampling technique of Section 4.3,
meaning that their behavior can be analyzed once and the results used for all possible
values of the secret. (Note that the branching depends on the secret value, which indirectly
causes an information leakage in the entire system.)
We compare the estimated costs of precise and statistical analyses on the component
S as follows. Since S is not deterministic, we cannot immediately mark it for precise
analysis. As explained in Section 5 the choice now depends on the size of the output of
the component #YS compared to the size of the internal randomness of the component#ZS . We obtain that #YS = N and #ZS = W (N − W ). Since we set N = 2W andN ≥ 20, we obtain #ZS = W 2  2W = #YS . Consequently, precise trace analysis
is more expensive than statistical analysis on the component S, thus we mark S for
statistical analysis.
Component T has N possible outputs and N possible internal randomness values,
so we mark it for precise analysis.
34

Tool
Result Error
QUAIL 0.50327
0
LeakWatch 0.36245 0.14082
Hybrid 0.50325 0.00002

Table 3: Distributed Lying Cryptographers Example.

E

More on the Multiple Lying Cryptographers Protocol

We revisit the Lying Cryptographers protocol from Section 6. The division into components is executed following the principles in Section 5. The hybrid approach divides the
protocol into 8 components, one for each possible liar. Then each component is analyzed
statistically. This allows the statistical analysis to sidestep the increased variance givenby the presence of the liar, producing a more accurate result.
We can also use this example to show that LeakWatch does not compute bias correctly,
and consequently produces an incorrect result. We have used QUAIL [28] to computethe exact Shannon leakage, and then compared the result of LeakWatch and of the hybrid
approach. The results of the experiment are summarized in Table 3. Due to the bias
correction problem explained in Section 4.1, LeakWatch computes an incorrect result:
LeakWatch’s bias correction only depends on the size of the joint matrix (as shown in
Corollary 1), but the presence of zeroes in the matrix reduces the bias (as shown in
Proposition 1). Finally, our hybrid approach manages to produce a result very close to
the precise one computed by QUAIL, even if it uses statistical estimation.
As regards previous tools on quantitative information flow, some comparison can befound in Biondi et al. [50].

F

Example: Training of a Decision TreeIn this section we present an example outside the security scenario.
Decision trees are commonly used to build tree structures that classify categorical
data. Consider having to take a decision that depends on multiple factors, for instancehaving to decide in which malware category a given malware is included. The malware
category depends on whether the malware has certain attributes, for instance whether it
sends the infected computer’s data to an outside source, whether it installs a malicious
driver, whether it displays advertisement, and so on. Since checking attributes for a given
malware is expensive, we want to be able to categorize the malware by checking theminimal number of attributes. Let the attribute be from the set {A, B, C, D}, and themalware categories be from the set M = {Trojan, Spyware, Virus, Worm, Rootkit}. Each
attribute is Boolean, so the malware can express it or not.
We will consider the ID3 algorithm [51] to construct a decision tree for malware
classification. A decision tree is created, or “trained”, by analyzing data from a database.
In our case, each entry of the database associates a malware category with some of theattributes. For instance, malware of category Worm may have attributes A and C, whilemalware of category Virus may have A, C, and D. In this example we will consider
that the ID3 algorithm has access to multiple databases, for instance because they are35

I(M;D)
I(M;C)
I(M;B)
I(M;A)

Mutual Information

1
0.8
0.6
0.4
0.2
0
0

200

400
600
Sample size

800

1000

(a) Fixed prior.

I(M;D)
I(M;C)
I(M;B)
I(M;A)

Mutual Information

1
0.8
0.6
0.4
0.2
0
0

200

400
600
Sample size

800

1000

(b) Adaptive prior.

Fig. 9: Mutual information estimation for the decision tree training example (average of1000 experiments).

provided by different sources. The information about malware on the different databases
may overlap. We consider three databases with a size ratio of 1:3:6, which is known tothe analyst.
The ID3 algorithm relies on being able to compute the mutual information between
the target M and each of the attributes {A, B, C, D}. In particular, the root of thetree is chosen as the attribute with the highest mutual information with M . Since thedatabases are supposed to be very large and precise mutual information computation
is expensive, this information is not freely available to the algorithm. Instead, we willshow how to train a decision tree by statistically querying the databases and estimating
the mutual information I(M ; X) between the malware categories M and each attributeX ∈ {A, B, C, D} (with the associated confidence intervals).
36

F.1

Hybrid Statistical ID3 Implementation

To estimate the mutual information between the malware categories M and the attributes,
we model each of the 3 databases as a joint probability distribution between M and eachof the attributes {A, B, C, D}.
Ideally, assume that each malware datum in each database is associated with someunique ID i. The analyst randomly chooses an ID i and queries the database to obtain themalware category and attributes of the malware associated with i. The analyst repeats
this many times to create the approximate joint distributions. Finally, they estimate
the mutual informations I(M ; A), I(M ; B), I(M ; C), and I(M ; D) and the respective
confidence intervals as explained in Section 3.
The root of the decision tree is the attribute X ∈ {A, B, C, D} maximizing I(M ; X).
However, due to the random sampling from databases, we need to gather enough data
to claim with confidence that X actually maximizes mutual information. If two mutual
information estimates have overlapping confidence intervals, we cannot guarantee that
one of them has a value higher than the other. Hence, we will continue querying thedatabases until the confidence interval of the mutual information of the attribute withhighest estimated mutual information does not overlap with any other confidence interval.
Note that the ID3 algorithm normally requires precise analysis of the database: using
statistical estimation and confidence intervals is our original approach. In this example
we will compute only the root of the tree, due to space constraints.
F.2

Experimental Results

The results of the experiments are depicted in Fig. 9. We show the estimated mutual
information values between M and each of the components and the relative confidence
interval for increasing sample sizes. While the component with the highest mutual
information is D, a certain sample size is required before its confidence interval is notoverlapping with the confidence interval of the component with the second highest
mutual information, i.e. C. In Fig. 9a we use a fixed prior on the different components,
and the confidence intervals become non-overlapping when the sample size is greaterthan 800. On the other hand, in Fig. 9b we use the adaptive optimization of the priorspresented in Proposition 3, and the confidence interval become non-overlapping when
the sample size is greater than only 600 samples, proving the effectiveness of the adaptive
optimization.

37