On the computation of covert channel capacity

Eugene Asarin; Cătălin Dima

RAIRO - Theoretical Informatics and Applications (2010)

  • Volume: 44, Issue: 1, page 37-58
  • ISSN: 0988-3754

Abstract

top
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”).

How to cite

top

Asarin, Eugene, and Dima, Cătălin. "On the computation of covert channel capacity." RAIRO - Theoretical Informatics and Applications 44.1 (2010): 37-58. <http://eudml.org/doc/250797>.

@article{Asarin2010,
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”). },
author = {Asarin, Eugene, Dima, Cătălin},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Covert channels; entropy; synchronous transducers.; covert channel; synchronous transducers},
language = {eng},
month = {2},
number = {1},
pages = {37-58},
publisher = {EDP Sciences},
title = {On the computation of covert channel capacity},
url = {http://eudml.org/doc/250797},
volume = {44},
year = {2010},
}

TY - JOUR
AU - Asarin, Eugene
AU - Dima, Cătălin
TI - On the computation of covert channel capacity
JO - RAIRO - Theoretical Informatics and Applications
DA - 2010/2//
PB - EDP Sciences
VL - 44
IS - 1
SP - 37
EP - 58
AB - 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”).
LA - eng
KW - Covert channels; entropy; synchronous transducers.; covert channel; synchronous transducers
UR - http://eudml.org/doc/250797
ER -

References

top
  1. M.-P. Béal, Codage Symbolique. Masson (1993).  
  2. M.-P. Béal and O. Carton, Determinization of transducers over finite and infinite words. Theoretical Computer Science289 (2002) 225–251.  
  3. V. Blondel and Yu. Nesterov, Polynomial-time computation of the joint spectral radius for some sets of nonnegative matrices. SIAM Journal of Matrix Analysis and Applications31 (2009) 865–876.  
  4. C. Choffrut and S. Grigorieff, 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.  
  5. Department of defense trusted computer system evaluation criteria. DOD 5200.28-STD, National Computer Security Center (December 1985).  
  6. C. Frougny and J. Sakarovitch, Synchronisation déterministe des automates à délai borné. Theoretical Computer Science191 (1998) 61–77.  
  7. F.R. Gantmacher, The theory of matrices. AMS Chelsea Publishing (1959).  
  8. J.A. Goguen and J. Meseguer, Security policies and security models, in Proceedings of the IEEE Symposium on Security and Privacy, Oakland, CA, USA (1982) 11–20.  
  9. R. Jungers, Vl. Protasov and V. Blondel, Efficient algorithms for deciding the type of growth of products of integer matrices. Linear Algebra and its Applications428 (2008) 2296–2311.  
  10. D. Lind and B. Marcus, An Introduction to Symbolic Dynamics and Coding. Cambridge University Press (1995).  
  11. G. Lowe, Quantifying information flow, in Proceedings of the 15th IEEE Computer Security Foundations Workshop (CSFW'02), IEEE Computer Society (2002) 18–31.  
  12. J.K. Millen, Finite-state noiseless covert channels, in Proceedings of the 2nd IEEE Computer Security Foundations Workshop (CSFW'89), IEEE Computer Society (1989) 81–86.  
  13. V. Protasov, R. Jungers and V. Blondel, Joint spectral characteristics of matrices: a conic programming approach. (2009).  URIhttp://www.inma.ucl.ac.be/~jungers/publis_dispo/conic.pdf
  14. W. Thomas, Languages, automata, and logic, in Handbook of Formal Languages, Vol. III. Springer Verlag (1997) 389–455.  
  15. P. Turán, On an extremal problem in graph theory. Matematicko Fizicki Lapok48 (1941) 436–452 (in Hungarian).  
  16. J.T. Wittbold and D.M. Johnson, Information flow in nondeterministic systems, in IEEE Symposium on Security and Privacy (1990) 144–161.  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.