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”).
@article{ITA_2010__44_1_37_0,
author = {Asarin, Eugene and Dima, C\u at\u alin},
title = {On the computation of covert channel capacity},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
volume = {44},
year = {2010},
pages = {37-58},
doi = {10.1051/ita/2010004},
mrnumber = {2604934},
zbl = {1185.94035},
language = {en},
url = {http://dml.mathdoc.fr/item/ITA_2010__44_1_37_0}
}
Asarin, Eugene; Dima, Cătălin. On the computation of covert channel capacity. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 44 (2010) pp. 37-58. doi : 10.1051/ita/2010004. http://gdmltest.u-ga.fr/item/ITA_2010__44_1_37_0/
[1] , Codage Symbolique. Masson (1993).
[2] and , Determinization of transducers over finite and infinite words. Theoretical Computer Science 289 (2002) 225-251. | Zbl 1061.68088
[3] and , Polynomial-time computation of the joint spectral radius for some sets of nonnegative matrices. SIAM Journal of Matrix Analysis and Applications 31 (2009) 865-876. | Zbl 1201.65051
[4] and , Uniformization of rational relations, in Jewels are Forever, Contributions on Theoretical Computer Science in Honor of Arto Salomaa, edited by J. Karhumäki, H.A. Maurer, Gh. Paun and G. Rozenberg. Springer (1999) 59-71. | Zbl 0944.68107
[5] Department of defense trusted computer system evaluation criteria. DOD 5200.28-STD, National Computer Security Center (December 1985).
[6] and , Synchronisation déterministe des automates à délai borné. Theoretical Computer Science 191 (1998) 61-77. | Zbl 1015.68128
[7] , The theory of matrices. AMS Chelsea Publishing (1959). | Zbl 0927.15001
[8] and , Security policies and security models, in Proceedings of the IEEE Symposium on Security and Privacy, Oakland, CA, USA (1982) 11-20.
[9] , Vl. Protasov and V. Blondel, Efficient algorithms for deciding the type of growth of products of integer matrices. Linear Algebra and its Applications 428 (2008) 2296-2311. | Zbl 1145.65030
[10] and , An Introduction to Symbolic Dynamics and Coding. Cambridge University Press (1995). | Zbl 1106.37301
[11] , Quantifying information flow, in Proceedings of the 15th IEEE Computer Security Foundations Workshop (CSFW'02), IEEE Computer Society (2002) 18-31.
[12] , Finite-state noiseless covert channels, in Proceedings of the 2nd IEEE Computer Security Foundations Workshop (CSFW'89), IEEE Computer Society (1989) 81-86.
[13] , and , Joint spectral characteristics of matrices: a conic programming approach. http://www.inma.ucl.ac.be/~jungers/publis_dispo/conic.pdf (2009). | Zbl 1203.65093
[14] , Languages, automata, and logic, in Handbook of Formal Languages, Vol. III. Springer Verlag (1997) 389-455.
[15] , On an extremal problem in graph theory. Matematicko Fizicki Lapok 48 (1941) 436-452 (in Hungarian). | JFM 67.0732.03 | Zbl 0026.26903
[16] and , Information flow in nondeterministic systems, in IEEE Symposium on Security and Privacy (1990) 144-161.