On the computation of covert channel capacity

¹ LIAFA, Université Denis Diderot and CNRS, Case 7014, 75205 Paris Cedex 13, France; asarin@liafa.jussieu.fr
² LACL, Université Paris-Est – Université Paris 12, 61 av. du Général de Gaulle, 94010 Créteil, France; dima@univ-paris12.fr

Abstract

We address the problem of computing the capacity of a covert channel, modeled as a nondeterministic transducer. We give three possible statements of the notion of “covert channel capacity” and relate the different definitions. We then provide several methods allowing the computation of lower and upper bounds for the capacity of a channel. We show that, in some cases, including the case of input-deterministic channels, the capacity of the channel can be computed exactly (e.g. in the form of “the largest root of some polynomial”).

Résumé

Nous proposons l'utilisation des transducteurs nondéterministes pour la modélisation des canaux cachés. Trois définitions possibles de la notion de “capacité du canal caché” sont proposées, et leurs relations sont étudiées. Nous donnons ensuite plusieurs méthodes permettant le calcul des bornes inférieures et supérieures pour la capacité d'un canal caché. Nous montrons que, dans certains cas, qui incluent le cas des transducteurs déterministes en entrée, la capacité peut être calculée exactement (sous forme de “la racine la plus grande d'un polynôme”).