CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Termination-Insensitive Noninterference Leaks More Than Just a Bit.

Aslan Askarov (Institutionen för data- och informationsteknik, Datavetenskap (Chalmers)) ; Sebastian Hunt ; Andrei Sabelfeld (Institutionen för data- och informationsteknik, Datavetenskap (Chalmers)) ; David Sands (Institutionen för data- och informationsteknik, Datavetenskap (Chalmers))
In Proceedings of the 13th European Symposium on Research in Computer Security, Malaga, Spain, October 2008. (0302-9743). Vol. 5283 (2008), p. 333-348.
[Konferensbidrag, refereegranskat]

Current tools for analysing information flow in programs build upon ideas going back to Denning's work from the 70's. These systems enforce an imperfect notion of information flow which has become known as termination-insensitive noninterference. Under this version of noninterference, information leaks are permitted if they are transmitted purely by the program's termination behaviour (i.e., whether it terminates or not). This imperfection is the price to pay for having a security condition which is relatively liberal (e.g. allowing while-loops whose termination may depend on the value of a secret) and easy to check. But what is the price exactly? We argue that, in the presence of output, the price is higher than the ``one bit'' often claimed informally in the literature, and effectively such programs can leak all of their secrets. In this paper we develop a definition of termination-insensitive noninterference suitable for reasoning about programs with outputs. We show that the definition generalises ``batch-job'' style definitions from the literature and that it is indeed satisfied by a Denning-style program analysis with output. Although more than a bit of information can be leaked by programs satisfying this condition, we show that the best an attacker can do is a brute-force attack, which means that the attacker cannot reliably (in a technical sense) learn the secret in polynomial time in the size of the secret. If we further assume that secrets are uniformly distributed, we show that the advantage the attacker gains when guessing the secret after observing a polynomial amount of output is negligible in the size of the secret.

Denna post skapades 2008-12-03. Senast ändrad 2017-09-14.
CPL Pubid: 79625


Institutioner (Chalmers)

Institutionen för data- och informationsteknik, Datavetenskap (Chalmers)


Datavetenskap (datalogi)

Chalmers infrastruktur

Relaterade publikationer

Denna publikation ingår i:

Policies and Mechanisms for Securing Information Release