Information flow in an
information theoretical context is the transfer of information from a
variable
Variable may refer to:
* Variable (computer science), a symbolic name associated with a value and whose associated value may be changed
* Variable (mathematics), a symbol that represents a quantity in a mathematical expression, as used in many ...
to a variable
in a given
process
A process is a series or set of activities that interact to produce a result; it may occur once-only or be recurrent or periodic.
Things called a process include:
Business and management
*Business process, activities that produce a specific se ...
. Not all flows may be desirable; for example, a system should not leak any confidential information (partially or not) to public observers--as it is a violation of privacy on an individual level, or might cause major loss on a corporate level.
Introduction
Securing the data manipulated by computing systems has been a challenge in the past years. Several methods to limit the information disclosure exist today, such as
access control list
In computer security, an access-control list (ACL) is a list of permissions associated with a system resource (object). An ACL specifies which users or system processes are granted access to objects, as well as what operations are allowed on gi ...
s,
firewalls, and
cryptography
Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adver ...
. However, although these methods do impose limits on the information that is released by a system, they provide no guarantees about information ''propagation''.
[Andrei Sabelfeld and Andrew C. Myers. Language-Based Information-Flow Security. IEEE Journal on Selected Areas in Communications, 21(1), Jan. 2003.] For example, access control lists of file systems prevent unauthorized file access, but they do not control how the data is used afterwards. Similarly, cryptography provides a means to exchange information privately across a non-secure channel, but no
guarantees about the confidentiality of the data are given once it is decrypted.
In low level information flow analysis, each variable is usually assigned a security level. The basic model comprises two distinct levels: low and high, meaning, respectively, publicly observable information, and secret information. To ensure confidentiality, flowing information from high to low variables should not be allowed. On the other hand, to ensure integrity, flows to high variables should be restricted.
More generally, the security levels can be viewed as a
lattice
Lattice may refer to:
Arts and design
* Latticework, an ornamental criss-crossed framework, an arrangement of crossing laths or other thin strips of material
* Lattice (music), an organized grid model of pitch ratios
* Lattice (pastry), an orna ...
with information flowing only upwards in the lattice.
[Dorothy Denning. A lattice model of secure information flow. Communications of the ACM, 19(5):236-242, 1976.]
For example, considering two security levels
and
(low and high), if
, flows from
to
, from
to
, and
to
would be allowed, while flows from
to
would not.
Throughout this article, the following notation is used:
* variable
(low) shall denote a publicly observable variable
* variable
(high) shall denote a secret variable
Where
and
are the only two security levels in the
lattice
Lattice may refer to:
Arts and design
* Latticework, an ornamental criss-crossed framework, an arrangement of crossing laths or other thin strips of material
* Lattice (music), an organized grid model of pitch ratios
* Lattice (pastry), an orna ...
being considered.
Explicit flows and side channels
Information flows can be divided in two major categories. The simplest one is explicit flow, where some secret is explicitly leaked to a publicly observable variable. In the following example, the secret in the variable ''h'' flows into the publicly observable variable ''l''.
var l, h
l := h
The other flows fall into the
side channel category. For example, in the
timing attack
In cryptography, a timing attack is a side-channel attack in which the attacker attempts to compromise a cryptosystem by analyzing the time taken to execute cryptographic algorithms. Every logical operation in a computer takes time to execute, and ...
or in the
power analysis attack, the system leaks information through, respectively, the time or power it takes to perform an action depending on a secret value.
In the following example, the attacker can deduce if the value of ''h'' is one or not by the time the program takes to finish:
var l, h
if h = 1 then
(* do some time-consuming work *)
l := 0
Another side channel flow is the implicit information flow, which consists in leakage of information through the program control flow. The following program (implicitly) discloses the value of the secret variable ''h'' to the variable ''l''. In this case, since the ''h'' variable is boolean, all the bits of the variable of ''h'' is disclosed (at the end of the program, ''l'' will be 3 if ''h'' is true, and 42 otherwise).
var l, h
if h = true then
l := 3
else
l := 42
Non-interference
Non-interference is a policy that enforces that an attacker should not be able to distinguish two computations from their outputs if they only vary in their secret inputs.
However, this policy is too strict to be usable in realistic programs.
The classic example is a password checker program that, in order to be useful, needs to disclose some secret information: whether the input password is correct or not (note that the information that an attacker learns in case the program ''rejects'' the password is that the attempted password is ''not'' the valid one).
Information flow control
A mechanism for ''information flow control'' is one that enforces information flow policies. Several methods to enforce information flow policies have been proposed. Run-time mechanisms that tag data with information flow labels have been employed at the operating system level and at the programming language level. Static program analyses have also been developed that ensure information flows within programs are in accordance with policies.
Both static and dynamic analysis for current programming languages have been developed. However, dynamic analysis techniques cannot observe all execution paths, and therefore cannot be both sound and precise. In order to guarantee noninterference, they either terminate executions that might release sensitive information or they ignore updates that might leak information.
A prominent way to enforce information flow policies in a program is through a security type system: that is, a type system that enforces security properties. In such a sound type system, if a program type-checks, it meets the flow policy and therefore contains no improper information flows.
Security type system
In a programming language augmented with a security
type system
In computer programming, a type system is a logical system comprising a set of rules that assigns a property called a type to every "term" (a word, phrase, or other set of symbols). Usually the terms are various constructs of a computer progr ...
every expression carries both a type (such as boolean, or integer) and a security label.
Following is a simple security type system from
that enforces non-interference.
The notation
means that the expression
has type
. Similarly,
means that the command
is typable in the security context
.
Well-typed commands include, for example,
:
.
Conversely, the program
:
is ill-typed, as it will disclose the value of variable
into
.
Note that the rule