Studying Maximum Information Leakage Using
Karush–Kuhn–Tucker Conditions
Han Chen

Pasquale Malacaria

School of Electronic Engineering and Computer Science
Queen Mary University of London
hanchen@dcs.qmul.ac.uk

School of Electronic Engineering and Computer Science
Queen Mary University of London
pm@dcs.qmul.ac.uk

When studying the information leakage in programs or protocols, a natural question arises: “what is
the worst case scenario?”. This problem of identifying the maximal leakage can be seen as a channel
capacity problem in the information theoretical sense. In this paper, by combining two powerful
theories: Information Theory and Karush–Kuhn–Tucker conditions, we demonstrate a very general
solution to the channel capacity problem. Examples are given to show how our solution can be
applied to practical contexts of programs and anonymity protocols, and how this solution generalizes
previous approaches to this problem.

1

Introduction

As emphasized in the existing literature, no electronic system can guarantee perfect confidentiality or
anonymity [19]. Hence, measuring the leakage of confidential information is a pressing but increasingly
challenging issue. The ability to preemptively assess possible information leaks is crucial for designing
and understanding a system that contains information which ought to be protected [1].
Information Theory [25] provides a general method for measuring information flow in information
channels, and extends to quantify the loss of confidentiality and anonymity. A number of previous works
have addressed and measured the channel capacity of information leakage channels, which describes the
worst-case leakage. Recently a novel technique to measure the channel capacity of anonymity protocols
and programs using Lagrange multipliers has been proposed in [21, 7]: this setting is able to answer
questions like: “what is the maximum leakage of a system where a random string is 1000 times less
likely to be the secret than a dictionary word” i.e. an equality constraint like prand = 1000pword .1
In order to analyze a much wider range of systems and scenarios, inequality constraints ought to be
supported. An example of such constraint is: “the password is over 1000 times more likely to be a word
from a dictionary than a meaningless string”, i.e. prand < 1000pword : these inequality constraints cannot
be solved using lagrangians. Therefore, we introduce Karush–Kuhn–Tucker (KKT) conditions to enable
inequality constraints for deriving the channel capacity, and present a set of theorems and propositions
which can be readily applied. This makes the approach more powerful and enables it to deal with a much
wider spectrum of cases, as demonstrated later on in this paper. Further, we believe that this approach,
orthogonal to the probabilistic methods which have dominated protocol security analysis [12, 11, 24],
will provide novel and more practical results to the research community.
The paper is organized as follows: the next subsection discusses existing literature and the background is introduced in Section 2. In Section 3, we briefly describe the theorems and propositions for
channel capacity using Karush-Kuhn-Tucker conditions with full proofs. We show that our method can
1 By maximum leakage we mean the maximum number of bits leaked. Notice that this is different from the maximum
percentage of the secret leaked.

M. Boreale, S. Kremer (Eds.):
Security Issues in Concurrency (SecCo’09)
EPTCS 7, 2009, pp. 1–15, doi:10.4204/EPTCS.7.1

c Han Chen & Pasquale Malacaria
This work is licensed under the
Creative Commons Attribution License.

2

Studying Maximum Information Leakage Using Karush–Kuhn–Tucker Conditions

be applied to programs and protocols in Section 4. Finally, we provide concluding remarks and discuss
future works in Section 5.

1.1

Related Works

This work extends from previous works by Chen and Malacaria [21, 7]. Information Leakage is measured
using the same Information Theoretical definitions used by a number of authors[8, 19, 3, 15, 16], and
follows pioneering works by Denning[10], Gray[13], Mclean[18] and Millen[22]. A recent alternative
Information Theoretical definition of leakage has been proposed by Smith [26] in terms of min entropy;
in the context of protocols those ideas have been investigated by [4]. A discussion of the relation between
min entropy and Shannon entropy relevant to the context of this work can be found in [20]. In a program
analysis context channel capacity has been recently investigated in [23].
Channel capacity of anonymity protocols in a restricted context has been characterized by Chatzikokolakis, Palamidessi and Panangaden [6]. However, their method applies to protocols with “symmetric”
properties. These restrictions are overcome in [21, 7] where Lagrange multipliers are used to compute
the maximum leakage of deterministic programs and anonymity protocols with additional equality constraints. Blahut [2] mentioned KKT conditions while proposing his iterative algorithm for approximate
channel capacity. However, the use of KKT conditions in the context of this work is original.
There is a large set of work on anonymity protocols using probabilistic techniques [12, 11, 24].
A probabilistic approach would assume a certain kind of distribution to work out an expectation of
anonymity in a given model. In comparison, our method allows for the use of more flexible relationships
to track the maximum leakage, which is a pressing problem that remains largely unsolved. Whilst it is
known that information theoretical and probabilistic notions are related, the extent of this relationship
requires further investigation.

2

Background

In this work we refer to a program or a protocol as an information leakage channel. We define an
information leakage channel as a triple
hH , O, φ i
where the input, H , is a set of confidential information, and the output, O, is a set of observations.
To introduce probabilities we use two random variables: h for H and O for O respectively. We also
denote members of H as hi ∈ H , and members of O as o j ∈ O. φ describes the conditional probability
between the two random variables:
φ = P(O|h)
In deterministic channels, one input hi can only produce one output o j thus φ j,i = 1.
With this definition, both programs and anonymity protocols can be seen as information leakage
channels. In general, information leakage channel has three elements: confidential information as inputs,
public information as observations and the corresponding probabilities between them.
The triple above: hH , O, φ i can be represented by a probability matrix: rows describe elements of
H , columns describe elements of O and the value at position (hi , o j ) is the conditional probability φ j,i .
This is the chance of observing o j given hi as the input.

Han Chen & Pasquale Malacaria

2.1

3

Background on Karush–Kuhn–Tucker Conditions

Karush–Kuhn–Tucker (KKT) conditions [17] generalize the Lagrange method for finding the extrema
of a function subject to a family of constraints: while Lagrange multipliers consider only equality constraints, KKT conditions allow for general inequality constraints. We refer the reader to [21, 7] for a
background on Lagrange Multipliers in this context.

2.2

A Simple Example

We will illustrate the use of the method by a simple example below.
Suppose we want to maximize the following function:
f (x, y) = xy
subject to the inequality constraint
x+y ≤ 8
First we construct the Lagrange function which combines the original function waiting to be maximized
and the constraint
L(x, y) = xy + λ (8 − x − y)
where λ is a number which indicates the weight associated with the constraint, for example ignoring the
constraint is equivalent to setting λ = 0.
Formally, the term λ which is the Lagrange multipliers and the Lagrange technique are used in order
to find the maximum of the function by differentiating on x, y and λ .
Using KKT we get the optimal solution for the original optimization problem by solving the following equations:
δ L(x, y)
δ L(x, y)
= y − λ = 0,
= x − λ = 0, λ (8 − x − y) = 0
δx
δy
We deduce the additional constraint
x + y ≤ 8, x = y = λ
We use the conclusion x = y = λ to replace x and y in the original function and get the maximal value
Max f (x, y) = λ 2
Notice there is another equation we didn’t use so far λ (8 − x − y) = 0, from this and the constraint
x + y ≤ 8 we get two cases
λ = 0, or x + y = 8
It’s easy to see that λ = 0 is a saddle point because this value can not give the local maximum. Then we
use λ replace the variables x and y in the second case and get
2λ = 8 ⇒ λ = 4
It is then easy to derive the values for the other variables i.e.
x = 4, y = 4
Now the values x = 4, y = 4 do satisfy the constraint and also are the values that maximize the original
function
Max f (x, y) = xy = 16

4

Studying Maximum Information Leakage Using Karush–Kuhn–Tucker Conditions

2.3

Theoretical Basis of Karush–Kuhn–Tucker Conditions

We consider the problem of finding the extrema of a function f subject to a family of constraints C1≤i≤m
where Ci is an inequality of the form gi (x) ≥ bi .
The first step is to construct the Lagrange function L(x, λ ) where λ is a Lagrange multiplier for the
inequality constraint which is similar as the multiplier for equality constraint. The inequality constraints
are expressed in the form gi (x) − bi ≥ 0 and then we introduce the λ associated with the constraints.
In a general setting let L(x, λ ) be the Lagrangian of a function f subject to a family of constraints
C1≤i≤m (Ci ≡ gi (x) ≥ bi ), i.e.
L(x, λ ) = f (x) +

∑

λi (gi (x) − bi )

1≤i≤m

The basic result justifying KKT method is the following:
Theorem 2.1 Assume the vector x∗ = (x1∗ , . . . , xn∗ ) maximizes (or minimizes) the continuous function f (x)
subject to the constraints (gi (x) ≥ bi )1≤i≤m . Then either
1. the vectors (∇gi (x∗ ))1≤i≤m are linearly dependent, or
2. there exists a vector λ ∗ = (λ1∗ , . . . , λm∗ ) which is an optimal solution for the original optimization
problem satisfying the following conditions
∇L(λ ∗ , x∗ ) = 0 i.e.
δL ∗
(
(x ) = 0)1≤i≤n
δ xi
and
λ ∗ (gi (x∗ ) − bi ) = 0, gi (x∗ ) ≥ bi , λi ≥ 0
where ∇ is the gradient and these conditions are called KKT conditions.
The condition λi ≥ 0 implies non-negative Lagrange multiplier and λ ∗ (gi (x∗ ) − bi ) = 0 implies two
cases:
gi (x∗ ) = bi

(1)

gi (x ) > bi → λi = 0

(2)

∗

2.4

Results of Lagrange Multipliers: A Short Review

We now give a short review of the results in [21, 7]. These works use Lagrange multiplier to solve the
channel capacity in programs and anonymity protocols with equality constraints.
Theorem 2.2 In probabilistic channels, the probabilities hi maximizing I(h; O) subject to the family of
constraint (Ck )k∈K are given by solving in hi the equations

∑
os ∈Ôi

φs,i ln(

φs,i
) − 1 + ∑ λk fi,k = 0
os
k

and the constraints (Ck )k∈K .
where φs,i is the probability of observing os when the input is hi ; Ôi denotes the set of observations
possible for the secret hi ; fi,k is the factor of hi in the kth constraint.
Using the probabilities hi we can work out the channel capacity.

Han Chen & Pasquale Malacaria

5

Proposition 2.3 The channel capacity is given by

∑ hi (1 − ∑ λk fi,k )d
i

k

If the system is deterministic, the formula in Theorem 2.2 can be simplified to
ln(oi ) − 1 + ∑ λk fi,k = 0
k

Moreover, in the case of the single constraint ∑i hi = 1 the channel capacity of deterministic information leakage channels can be further simplified.
Proposition 2.4 The channel capacity of deterministic information leakage channels without any additional constraint is given by
d(1 − λ0 )
where d =

1
ln 2 .

From Theorem 2.2 we can know that Proposition 2.4 implies the well known fact that the channel capacity of unconstrained deterministic programs is the log of the number of possible outputs.

3
3.1

Channel Capacity using Karush–Kuhn–Tucker Conditions
Constraints

Often the attacker’s knowledge about the secret can be expressed in terms of inequalities: for example,
“a unix password is 100 times more likely to be a word from a dictionary than a meaningless string”.
We hence need KKT conditions to compute channel capacity in this context. Remember that there is
always at least one constraint for the input distribution requiring that the sum of their probabilities is
1; we denote this constraint as C0 . Additional constraints are used to specify the conditions of inputs
needed to satisfy: we use Ck for these conditions.
C0 ≡ ∑ hi = 1
Ck ≡ gk (hi ) ≥ Fk (k > 0)
where Fk are constants and gk (hi ) are “statistics” or expectations , i.e. linear inequality expressions in
the form of
gk (hi ) ≡ ∑ hi fi,k
i

KKT conditions only provides precise solutions for non strict inequalities; for strict inequalities, we can
only provide an approximate solution.

3.2

Theory and Proof

Convention:
As previously explained, we denote hi as the i-th possible value that the variable h can assume. Also,
o j denotes the j-th possible value for the observation variable O. Each possible event hi has a given
probability µ(hi ). To ease the exposition we will use hi both for the event hi and for its probability µ(hi ),

6

Studying Maximum Information Leakage Using Karush–Kuhn–Tucker Conditions

and similarly o j for µ(o j ). However when it is clear from the context we may use hi for the i-th value of
the variable h, i.e. h = vi . The context will disambiguate what meaning is intended.
As usual we use the conditional probability of φk,i for the probability of observing ok given the input
hi . Using Information Theory we have:
I(h; O) = H(h) − H(h|O)
= H(h) + ∑ ok ∑(hi |ok ) log(hi |ok )
k

i

= H(h) + ∑(hi , ok ) log(hi |ok )
i,k

= − ∑ hi log(hi ) + ∑ hi φk,i log(
i

i,k

hi φk,i
)
ok

= − ∑ hi φk,i log(hi ) + ∑ hi φk,i log(
i,k

i,k

hi φk,i
)
ok

φk,i
)
= ∑ hi φk,i log(
ok
i,k
Notice that
φk,i

∑ hi φk,i log( ok )

= d

i,k

where d =

1
ln 2

∑

hi φs,i ln

os ∈Ôi

φs,i
+d
os

∑

hr φs,r ln(

os ∈Ôi ,hr ∈Pi

φs,r
))
os

and
Pi = {hr |φs,r 6= 0, os ∈ Ôi , r 6= i}

where in the formula Ôi denotes the set of observations possible for the secret hi (i.e. the set of non zero
observations compatible with input hi ).
Assuming a set of constraints (Ck )k∈K ≡ gk (hi ) ≥ Fk , the Lagrange function hence becomes
L(hi ) = I(h; O) + d ∑ λk (∑ hi fi,k − Fk )
k

= d

∑
os ∈Ôi

i

φs,i
hi φs,i ln
+d
os

∑
os ∈Ôi ,hr ∈Pi

hr φs,r ln(

φs,r
)) + d ∑ λk (∑ hi fi,k − Fk )
os
i
k

where d = ln12 is used to convert the logarithm in base 2 log into natural logarithm ln.
As mentioned earlier, we always assume the constraint C0 ≡ ∑ hi = 1.
Using KKT the maximum L(hi ) is given by the following theorem:
Theorem 3.1 In information leakage channels, the probabilities hi maximizing I(h; O) subject to the
family of constraint (Ck )k∈K ≡ gk (hi ) ≥ Fk are given by solving in hi the following system of inequalities:

∑

φs,i ln(

os ∈Ôi

φs,i
) − 1 + ∑ λk fi,k = 0 ∧ λk ≥ 0, gk (hi ) ≥ Fk
os
k

or

∑
os ∈Ôi

φs,i ln(

φs,i
) − 1 + λ0 = 0 ∧ gk (hi ) ≥ Fk
os

Han Chen & Pasquale Malacaria

7

Proof: Recall that the KKT conditions are
(

δL ∗
(h ) = 0)1≤i≤n
δ hi

λk (∑ hi fi,k − Fk ) = 0,
i

∑ hi fi,k ≥ Fk ,

λk ≥ 0

i

Compared to the KKT conditions for equality constraints we found that there are three additional ones:
λk (∑ hi fi,k − Fk ) = 0,
i

other than

∑ hi fi,k ≥ Fk ,

λk ≥ 0

i

δL ∗
(λ ) = 01≤i≤n
δ λi

which actually represents the constraints

∑ hi fi,k − Fk = 0
i

Firstly we simplify the three additional constraints as
λk (∑i hi fi,k − Fk ) = 0
∑ h f = Fk ∧ λk ≥ 0 or
⇒ i i i,k
∑i hi fi,k ≥ Fk
∑i hi fi,k ≥ Fk ∧ λk = 0
λ ≥0
Combine the result with the derivative condition
(

δL ∗
(h ) = 0)1≤i≤n
δ hi

we can have the new pair of conditions for maximizing L
(
(

δL ∗
(h ) = 0, λ ∗ = 0)1≤i≤n ∧ λk ≥ 0 or
δ hi

δL ∗
(h ) = 0)1≤i≤n ∧ ∑ hi fi,k ≥ Fk ∧ λk = 0
δ hi
i

We first consider the derivative δδhLi (h∗ ) because this is the only derivative that needs to be satisfied.
This process is the same as equality constraints.
So, the maximum can be found by solving for all i
δ L(hi )
=0
hi
Recall our previous analysis of the Lagrange function:
L(hi ) = I(h; O) + d ∑ λk (∑ hi fi,k − Fk )
k

= d

∑
os ∈Ôi

i

φs,i
hi φs,i ln( ) + d
os

∑
os ∈Ôi ,hr ∈Pi

hr φs,r ln(

φs,r
) + d ∑ λk (∑ hi fi,k − Fk )
os
i
k

8

Studying Maximum Information Leakage Using Karush–Kuhn–Tucker Conditions
We solve the derivatives for each item in the Lagrange function. For the first item:
δ (d ∑os ∈Ôi hi φs,i ln( os,is ))
φ

= d

δ hi

∑

φs,i ln(

os ∈Ôi

2h
φs,i
φs,i
i
)−
os
os

For the second item:
δ (d ∑os ∈Ôi ,hr ∈Pi hr φs,r ln(

φs,r
os ))

δ hi
δ (d ∑os ∈Ôi ,hr ∈Pi hr φs,r ln φs,r − ∑os ∈Ôi ,hr ∈Pi hr φs,r ln os )
δ hi
0−d

∑

hr φs,r

φs,i
os

hr φs,r

φs,i
os

os ∈Ôi ,hr ∈Pi

−d

∑
os ∈Ôi ,hr ∈Pi

=
=
=

Because for hr ∈ Pi , hr φs,r ln φs,r does not include any hi , then the derivative by hi is 0.
We combine the first two items and then simplify the expression as follows:
d

φs,i ln(

∑
os ∈Ôi

d

∑

φs,i ln(

os ∈Ôi

2h
φs,i
φs,i
i
)−d
−d
os
os

φs,i
)−d
os
d

os ∈Ôi ,hr ∈Pi

φs,i (

∑
os ∈Ôi ,hr ∈Pi

∑

φs,i ln(

os ∈Ôi

d

hr φs,r

∑

φs,i
os

=

φs,i hi hr φs,r
+
) =
os
os

φs,i
)−d
os

∑

φs,i (

os ∈Ôi

os
) =
os

φs,i

∑ (φs,i ln( os ) − φs,i )

=

os ∈Ôi

d(

∑

os ∈Ôi

φs,i ln(

φs,i
) − 1)
os

For the third item, the result is a linear function of hi :
δ (d ∑k λk (∑i hi fi,k − Fk ))
= d ∑ λk fi,k
δ hi
k
From these results we conclude that maxI(h; O) can be achieved by solving hi in the following equation system:
δ (L(hi ))
=0⇒
hi
d(

∑

φs,i ln(

os ∈Ôi

∑
os ∈Ôi

φs,i
) − 1) + d ∑ λk fi,k = 0 ⇒
os
k

φs,i ln(

φs,i
) − 1 + ∑ λk fi,k = 0
os
k

Han Chen & Pasquale Malacaria

9

As mentioned before, this equation needs to satisfy the following condition:

∑ hi fi,k ≥ Fk ∧ λk = 0

λk ≥ 0 or

i

when λk = 0, the equation can be simplified to

∑

φs,i ln(

os ∈Ôi

φs,i
) − 1 + λ0 = 0
os

where λ0 is for the constraint ∑i hi = 1.
So, we arrive at the conclusion that to maximize L, the following equations need to be solved with
the constraints:

∑

φs,i ln(

os ∈Ôi

φs,i
) − 1 + ∑ λk fi,k = 0 ∧ λk ≥ 0 or
os
k

φs,i ln(

∑
os ∈Ôi

φs,i
) − 1 + λ0 = 0 ∧ ∑ hi fi,k ≥ Fk
os
i

The proof completes.
If the system is completely deterministic, that is one input can only generate one “observation”, then
the o j ’s are defined in terms of the high inputs h ji that generate the “observation”, i.e.
o j = h j1 + · · · + h jn
(h ,o )

Notice then that (hi |o j ) = io j j and that (hi , o j ) = hi if hi generates the observation o j otherwise is 0.
Because there is only one possible observation in the model associated with a high input h = vi ;
denoted as O(hi ) and defined as ôi = µ(O(hi ))
Hence, we can simplify the Theorem 3.1 to the following proposition by replacing φi,s with 1:
Proposition 3.2 In deterministic channels, the probabilities hi maximizing I(h; O) subject to the family
of constraint (Ck )k∈K ≡ gk (hi ) ≥ Fk are given by solving in hi the following system of inequalities:
− ln(os ) − 1 + ∑ λk fi,k = 0 ∧ λ ≥ 0 ∧ gk (hi ) ≥ Fk
k

or
− ln(os ) − 1 + λ0 = 0 ∧ gk (hi ) ≥ Fk
Proposition 3.3 In both probabilistic and deterministic channels, the channel capacity without given
knowledge is given by
∑ hi (1 − ∑ λk fi,k )d
i

k

In the case of λk = 0, for all k > 0 that simplifies to
d(1 − λ0 )
where d =

1
ln 2 .

10

Studying Maximum Information Leakage Using Karush–Kuhn–Tucker Conditions
Proof:
φ j,i hi
)
oj
j,i
oj
) + ∑ φ j,i hi log(hi )
= H(h) − ∑ φ j,i hi log(
φ
j,i
j,i
j,i
oj
= H(h) − ∑ φ j,i hi log(
) − H(h)
φ j,i
j,i
oj
)
= − ∑ φ j,i hi log(
φ
j,i
j,i

H(h) − H(h|O) = H(h) + ∑ φ j,i hi log(

=

φ j,i

∑ hi ∑ φ j,i log( o j )
i

=

j

∑ hi (1 − ∑ λk fi,k )d
i

k

where in deterministic channels φ j,i = 1. In the case λk = 0(k ≥ 1) the expression becomes:
d ∑ hi (1 − λ0 )
i

which indicates one possible result.
The proof completes.

3.3

Comparison with The Results Using Lagrange Multipliers

From Theorem 3.1 we notice that, in the solution of a constrained optimization problem, the inequality
constraints either constrain the solution (i.e. λi 6= 0 ∧ gk (hi ) = Fk ), or they do not (i.e. λi = 0). If they
do, we can use Lagrange Multiplier to find the optimal solution by treating the inequality constraints as
equality ones; otherwise, the constraints do not affect the solution. So, does it mean that the channel
capacity theorem deduced by KKT has no improvement upon [7, 21]? The answer is no, because when
there is a set of inequality constraints, it is difficult to determine which of them are constraining the problem. Then a method of classification is necessary to check whether the inequality constraints constrain
or not. This is exactly what KKT conditions are doing: whether the constraints constrain the maxima or
not, KKT deals with them elegantly.

4

Applications of the Results

Theorem 3.1 and Proposition 3.3 can be applied in both programs and protocols to solve channel capacity
with inequality constraints. In this section, two examples (a program and a protocol) will be studied to
show how Theorem 3.1 and Proposition 3.3 are applied. The results are explained. Further, a short
discussion is given on implementing this approach for automatic computation.

4.1

Example: A Multi-threaded Program

Let us start with a simple probabilistic nested multi-threaded program:
l=h % 2 | (l=0 |

l=1)

Han Chen & Pasquale Malacaria
h
hodd
heven

11

φ(O0 ,h)
p(1 − q) + (1 − p)(1 − q)p
1 − pq − (1 − p)pq

φ(O1 ,h)
1 − p(1 − q) − (1 − p)(1 − q)p
pq + (1 − p)pq

Table 1: A multi-threaded program: observations and probabilities
Suppose that the outer thread has probability p to run first “l=h % 2” and the inner thread has probability
q to run “l=0” before “l=1” . From the program we know that there are two possible observations: 0(O0 )
and 1(O1 ). We list all the possible values of h, observations and the conditional probabilities in Table 1.
Assume h is strictly less likely to be odd than even, i.e. the constraint on the input is:
hodd < heven
Using Theorem 3.1 we get equations:
ahodd + bheven
(1 − a)hodd + (1 − b)heven
) − (1 − a) ln(
) − 1 + λ0 + λ1 = 0
a
1−a
ahodd + bheven
(1 − a)hodd + (1 − b)heven
−b ln(
) − (1 − b) ln(
) − 1 + λ0 − λ1 = 0
b
1−b
−a ln(

where a = p(1 − q) + (1 − p)(1 − q)p ; b = 1 − pq − (1 − p)pq.
Firstly we consider the extreme case p = 1 and we solve the equation system to get
λ0 = 1, λ1 = 0
Using Proposition 3.3 we know that the channel capacity is 0. This is because when p = 1 which means
“l=h % 2” running first then the program is secure because the result can not reveal any information of
the secret. Now we suppose p = q = 13 , and according to that we can solve a = 0.3704 b = 0.8148.
Because the inequality is strict, we cannot have hodd = heven . Thus we consider if the other possibility in
Theorem 3.1 λ1 = 0 can be satisfied and we find:
hodd = 0.4836, heven = 0.5164, λ0 = 0.8931, λ1 = 0
This solution does satisfy hodd < heven and the distribution is the one we are after2 . Using Proposition
3.3 we get the channel capacity:
d(hodd (1 − λ0 − λ1 ) + heven (1 − λ0 + λ1 )) = 0.1069 bits
The channel capacity is small, because among the three statements, only when “l = h % 2” is run in the
end the program leaks, and the leakage is 1 bit. The other two statements do not contribute to the leakage
but further confuse the observation by producing same outputs 0 and 1, making the leakage even smaller.

4.2

Example: Onion Routing

Onion Routing [24] is designed to protect data and sender anonymity in communication over a public network such as the Internet. The general idea is, when a client (sender) wants to send a message to a receiver
r, it will choose a path p1 , . . . , pn of routers and encrypt the message m as P1 (. . . (Pn (R(m), r)) . . . , 2)
2 Notice

that values of hodd > 0.4836 results in a lower leakage

12

Studying Maximum Information Leakage Using Karush–Kuhn–Tucker Conditions
Path
1→2→R
1→2→3→R
1→2→4→3→R
2→4→3→R
2→3→R
3→2→R
4→3→R
4→3→2→R

h
1(h1 )

2(h2 )
3(h3 )
4(h4 )

O (in, out)
(N, N)
(2, R)
(4, R)
(4, R)
(2, R)
(N, R)
(4, R)
(4, 2)

φO(in,out),hi
1
3
1
3
1
3
1
2
1
2

1
1
2
1
2

Table 2: Onion Routing: observations and probabilities
where Pi (resp R) is the public key of the router i (resp receiver r). When the router pi receives
Pi (. . . (Pn (R(m), r)) . . . , i + 1) it will uses its private key to decrypt the message and will so get
Pi+1 (. . . (Pn (R(m), r)) . . . , i+1), so it will send the message Pi+1 (. . . (Pn (R(m), r)) . . . , i+2) to pi+1 . Usual
assumptions are:
1. A circuit can be of any number of nodes as long as no node appears twice.
2. The client never sends the message to the server directly.
3. Observations of a node include the previous node and the next one.
4. All paths are equally likely.
If the attacker can observe one router pi then there may be a loss of anonymity: the attacker is able
to observe which node delivered the packet to it and which node the packet is then be delivered to.
Here we will show how the loss of sender anonymity can be quantitatively analyzed using the definition of channel capacity. We use the same simple Onion Routing network from [7] as shown in Figure 1
but different and meaningful constraints will be demonstrated. The node “R” is the receiver. There are 4
nodes 1,2,3,4 in which either of them can initiate the communication; node 3 is an adversary in the network. We list all the possible paths, observations on the adversary node and the conditional probabilities
for the observations in the Table 2.

2

1

R

4

3

Figure 1: Example of An Onion Routing Network
From the Table 2, we get o using o j = ∑i φ j,i :
1
1
1
o(N,N) = h1 , o(2,R) = h1 + h2 ,
3
3
2
1
1
1
1
o(4,R) = h1 + h2 + h4 , o(N,R) = h3 , o(4,2) = h4
3
2
2
2

Han Chen & Pasquale Malacaria

13

We now consider the case when an active user sends out messages more frequently than non-active
users. Here we assume h1 has greater probability than the node h2 . Then we have an additional constraint
h1 ≥ h2 with the constraint C0 : h1 + h2 + h3 + h4 = 1.
We use Theorem 3.1 to get the following equations:
o(2,R)
o(4,R)
o(N,N)
1
− (ln( 1 ) + ln( 1 ) + ln( 1 )) − 1 + λ0 + λ1 = 0
3
3
3
3
1 o(4,R)
1 o(2,R)
− ln( 1 ) − ln( 1 ) − 1 + λ0 − λ1 = 0
2
2
2
2
1
− ln(
2

o(4,2)
1
2

− ln o(N,R) − 1 + λ0 = 0
1 o(4,R)
) − ln( 1 ) − 1 + λ0 = 0
2
2

We firstly consider if the equality h1 = h2 satisfies, then we solve the above equations and we find
h1 = 0.1674, h2 = 0.1674, h3 = 0.3903, h4 = 0.2750,
λ0 = 0.0591, λ1 = −0.0072
But this solution does not satisfy λ ≥ 0.
Then we only consider the solution for the other possibility λ1 = 0, and we get the results:
h1 = 0.1735, h2 = 0.1603, h3 = 0.3902, h4 = 0.2760,
λ0 = 0.0590, λ1 = 0
This solution does satisfy h1 > h2 . Using Proposition 3.3 we get the channel capacity:
d(h1 (1 − λ0 − λ1 ) + h2 (1 − λ0 + λ1 ) + (h3 + h4 )(1 − λ0 )) = 1.3576 bits
When we have a strict inequality constraint, as we mentioned before, it may find an approximate
solution in case if the accurate solution can not be achieved. The following example shows such a case.
Here we use a similar constraint as above, assuming that the first node is 100 times likely to send the
message compared to the second:
h1 > 100h2
Using Theorem 3.1 we know that the second equation above becomes
1 o(4,R)
1 o(2,R)
− ln( 1 ) − ln( 1 ) − 1 + λ0 − 100λ1 = 0
2
2
2
2
while the other three equations stay the same because the change of constraint does not affect them.
From the above result we can know that the solution for the case λ0 = 0 does not satisfy h1 > 100h2 . We
can use the equality constraint instead to find an approximate solution. Assuming h1 = 100h2 , we have
h1 = 0.2868, h2 = 0.0029, h3 = 0.3979, h4 = 0.3125,
λ0 = 0.0783, λ1 = 0.0024

14

Studying Maximum Information Leakage Using Karush–Kuhn–Tucker Conditions

Using Proposition 3.3 we get the channel capacity:
d(h1 (1 − λ0 − λ1 ) + h2 (1 − λ0 + 100λ1 ) + (h3 + h4 )(1 − λ0 )) = 1.3297 bits
Note that this is an approximate solution achieved when 100h2 + ξ = h1 , ξ → 0.
In the first case when the constraint is h1 ≥ h2 , the channel capacity is 1.3576 bits. We compute
the original secret of 1.9042 bits, which means the protocol leaks up to 72.2% confidential information.
In the second case, where the constraint is h1 > 100h2 , the channel capacity is 1.3297 bits. Since the
original confidential information is 1.5946 bits, the rate is increased to 83.4% which means the system is
much more insecure. The reason is, h1 and h2 share the same observations as (4, R) and (2, R). Once the
attacker observers these pairs, he/she has can more confidently guess the initial sender to be h1 than h2
with knowledge of the constraint h1 > 100h2 . Thus, the constraint does affect the security of the protocol
by reducing the confusion between h1 and h2 .
In both cases, the channel capacity is around 1.3 bits, which seems to imply that the protocol is
insecure. Two observations are in order. First notice that by repeating observations on these networks
the loss of anonymity is not increased. Secondly in the real deployment of onion routing on the Internet
(such as Tor), there are hundreds of nodes, with complex connectivity frequently updated; because of the
number of possible connections in such large scale networks the channel capacity is very low.
We have only one constraint in the above cases, but from the formula in Theorem 3.1

∑
os ∈Ôi

φs,i ln(

φs,i
) − 1 + ∑ λk fi,k = 0
os
k

multiple constraints will only affect the last item ∑k λk fi,k in the equation system. The complexity is
increased linearly by increasing the number of factors λk .

4.3

A Note on Automatic Computation

Automatic analysis of programs and protocols can be achieved in two steps. The first step is to analyze
the program or protocol to deduce the statistical relationship between O and h. Recent works to automate
this part include [14, 16] which tracks the analyzed program iteratively to derive a precise answer. Alternatively, [5, 9] used simulations to derive an estimation. For the particular example of anonymity routing
protocols, it is also possible to work out the statistical relationship based on the graph topology including
vertexes, edges and adversaries. Based on the relationship, the equation system can be produced using
Theorem 3.1. The second step is the automatic solution of the equation system. Automated solution of
such an equation system has been implemented in standard mathematical packages, e.g. MATLAB.

5

Conclusion and Future Work

We apply Karush-Kuhn-Tucker conditions to solve the channel capacity of probabilistic information
leakage channels with inequality constraints. We derived a series of theorems and propositions and we
show how these results can be applied to programs and protocols. Our calculations provide general and
accurate solutions to measure the maximum information leakage in a system.
Our future work will investigate other continuous definitions of information leakage using KarushKuhn-Tucker conditions. Notably, we propose to solve the maximum ratio between the channel capacity
of a leakage channel and that of the original secret, which in some cases could present a better definition
of the worst case. Additionally, a comparison of the information theoretical and probabilistic analysis of
probabilistic channels [12, 11] would also yield interesting results.

Han Chen & Pasquale Malacaria

15

References
[1] Securing cyberspace among top technological challenges of 21st century. http://www.networkworld.
com/news/2008/021908-top-technological-challenges.html.
[2] R. E. Blahut: Computation of Channel Capacity and Rate-Distortion Functions. IEEE Trans. on Information
Theory, 1972.
[3] Michele Boreale: Quantifying Information Leakage in Process Calculi. ICALP (2) 2006: 119-131.
[4] C. Braun, K. Chatzikokolakis and C. Palamidessi Quantitative notions of leakage for one-try attacks. In
Proceedings MFPS 2009
[5] Konstantinos Chatzikokolakis, Tom Chothia, Apratim Guha. Calculation of Probabilistic Anonymity from
Sampled Data. Manuscript 2009. http://www.cs.bham.ac.uk/~tpc/Papers/CalcProbAnon.pdf.
[6] K. Chatzikokolakis , C. Palamidessi , P. Panangaden. Anonymity Protocols as Noisy Channels, Proc. of
TGC’06, LNCS 4661, Springer, 281-300, 2006.
[7] Han Chen and Pasquale Malacaria: Quantifying Maximal Loss of Anonymity in Protocols. In Proc. ACM
Symposium on Information, Computer and Communications Security, 2009.
[8] David Clark, Sebastian Hunt, Pasquale Malacaria: A static analysis for quantifying information flow in a
simple imperative language. Journal of Computer Security, Volume 15, Number 3, 2007.
[9] George Danezis, Claudia Diaz, and Carmela Troncoso. Two-sided Statistical Disclosure Attack. In Proc.
PET’07. 2007.
[10] D. E. Denning: Cyptography and Data Security. Addison-Wesley, 1982.
[11] C. Dı́az, S.Seys, J Claessens and B. Preneel: Towards measuring anonymity. Proceedings of Privacy Enhancing Technologies Workshop (PET 2002),Springer-Verlag, LNCS 2482.
[12] J.Feigenmbaum, A. Johnson, P. Syverson. Probabilistic Analysis of Onion Routing in a Black-box Model.
In Proc. WPES’07, 2007.
[13] James W Gray III: Toward a methematical foundataion for information flow security. Proc. 1991 IEEE
Symposium on Security and Privacy. Oakland, California, May 1991.
[14] Jonathan Heusser and Pasquale Malacaria. Measuring Insecurity of Programs. Tech. Report, EECS, QMUL.
[15] Boris Kopf and David Basin: An Information-Theoretic Model for Adaptive Side-Channel Attacks. In Proc.
14th ACM Conference on Computer and Communications Security (CCS’07), 2007.
[16] Michael Backes, Boris Kopf and Andrey Rybalchenko Automatic Discovery and Quantification of Information Leaks. In Proc. 30th IEEE Symposium on Security and Privacy (S&P’09), 2009.
[17] A tutorial of KKT conditions. http://www.maths.leeds.ac.uk/~cajones/math2640/notes4.pdf
[18] John Mclean: Security models and information flow. In Proc. 1990 IEEE Symposium on Security and
Privacy. Oakland, California, May 1990.
[19] Pasquale Malacaria: Assessing security threats of looping constructs. In Proc. POPL 2007, ACM.
[20] Pasquale Malacaria: Risk Assessment of Security Threats for Looping Constructs. In Journal of Computer
Security, 2009.
[21] Pasquale Malacaria, Han Chen: Lagrange Multipliers and Maximum Information Leakage in Different
Observational Models. In Proc. PLAS 2008, ACM.
[22] Jonathan Millen: Covert channel capacity. In Proc. IEEE Symposium on Security and Privacy, 1987.
[23] J.Newsome, Stephen McCamant and D.Song. Measuring Channel Capacity to distinguish undue influence.
In Proc. PLAS 2009, ACM.
[24] M. Reed, P. Syverson, D. Goldschlag,“Anonymous Connections and Onion Routing”, In Proc. IEEE Symposium on Security and Privacy, 1997.
[25] C. E. Shannon and W. Weaver: A Mathematical Theory of Communication. Univ. of Illinois press, 1963.
[26] Geoffrey Smith: On the Foundations of Quantitative Information Flow. In Proc. FoSSaCS 2009.

