Abstract
Numerical sensors are numerical functions applied on memory contents. We study the computability of the mutual information rate between two sensors in various forms of automata, including nondeterministic pushdown automata augmented with reversal-bounded counters as well as discrete timed automata. The computed mutual information rate can be used to determine whether it is the case that there is essentially no information flow between a low sensor and a high sensor and hence could provide a way to quantitatively and algorithmically analyze some covert channels.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Alur, R., Dill, D.L.: A theory of timed automata. Theoret. Comput. Sci. 126(2), 183–235 (1994)
Alvim, M.. Andrs, M., Palamidessi, C.: Probabilistic information flow. In: LICS 2010, pp. 314–321
Backes, M., Berg, M., Köpf, B.: Non-uniform distributions in quantitative information-flow. In: ASIACCS 2011, pp. 367–375
Bishop, M.: Introduction to Computer Security. Addison-Wesley, Reading (2011)
Chomsky, N., Miller, G.A.: Finite state languages. Inf. Control 1, 91–112 (1958)
Cover, T.M., Thomas, J.A.: Elements of Information Theory, 2nd edn. Wiley-Interscience, New York (2006)
Cui, C., Dang, Z., Fischer, V, Ibarra, O.H.: Execution information rate for some classes of automata. Information and Computation (accepted)
Cui, C., Dang, Z., Fischer, T.R., Ibarra, O.H.: Information Rate of Some Classes of Nonregular Languages: An Automata-Theoretic Approach, Information and Computation (conditionally accepted)
Dang, Z., Ibarra, O.H., Bultan, T., Kemmerer, R.A., Su, J.: Binary reachability analysis of discrete pushdown timed automata. In: Emerson, E.A., Sistla, A.P. (eds.) CAV 2000. LNCS, vol. 1855, pp. 65–84. Springer, Heidelberg (2000)
Dang, Z.: Pushdown timed automata: a binary reachability characterization and safety verification. Theoret. Comput. Sci. 302(13), 93–121 (2003)
Dang, Z., Fischer, T., Hutton, W., Ibarra, O., Li, Q.: Quantifying communication in synchronized languages. In: COCOON 2015 (to appear)
Flajolet, P., Sedgewick, R.: Analytic Combinatorics. Cambridge University Press, Cambridge (2009)
Gonnet, G.H.: Expected length of the longest probe sequence in hash code searching. J. ACM 28, 289–304 (1981)
Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages and Computation. Addison-Wesley Publishing Company, Reading (1979)
Ibarra, O.H.: Reversal-bounded multicounter machines and their decision problems. J. ACM 25(1), 116–133 (1978)
Ibarra, O.H., Dang, Z., Egecioglu, O., Saxena, G.: Characterizations of catalytic membrane computing systems. In: Rovan, B., Vojtáš, P. (eds.) MFCS 2003. LNCS, vol. 2747, pp. 480–489. Springer, Heidelberg (2003)
Kaminger, F.P.: The noncomputability of the channel capacity of context-sensitive languages. Inf. Comput. 17(2), 175–182 (1970)
Kuich, W.: On the entropy of context-free languages. Inf. Control 16(2), 173–200 (1970)
Lanotte, R., Maggiolo-Schettini, A., Troina, A.: Time and probability-based information flow analysis. IEEE TSE 36(5), 719–734 (2010)
Li, Q., Dang, Z.: Sampling automata and programs. Theoret. Comput. Sci. 577, 125–140 (2015)
Lowe, G.: Defining information flow quantity. J. Comput. Secur. 12(3–4), 619–653 (2004)
Mu, C., Clark, D.: Quantitative analysis of secure information flow via probabilistic semantics. In: ARES 2009, pp. 49–57
Paun, G.: Membrane Computing: An Introduction. Springer, Berlin (2000)
Raab, M., Steger, A.: “Balls into Bins” - a simple and tight analysis. In: Rolim, J.D.P., Serna, M., Luby, M. (eds.) RANDOM 1998. LNCS, vol. 1518, p. 159. Springer, Heidelberg (1998)
Shannon, C.E., Weaver, W.: The Mathematical Theory of Communication. University of Illinois Press, Champaign (1949)
Smith, G.: On the foundations of quantitative information flow. In: de Alfaro, L. (ed.) FOSSACS 2009. LNCS, vol. 5504, pp. 288–302. Springer, Heidelberg (2009)
Xie, G., Dang, Z., Ibarra, O.: A solvable class of quadratic Diophantine equations with applications to verification of infinite-state systems. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol. 2719. Springer, Heidelberg (2003)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Dang, Z., Dementyev, D., Fischer, T.R., Hutton, W.J. (2015). Security of Numerical Sensors in Automata. In: Drewes, F. (eds) Implementation and Application of Automata. CIAA 2015. Lecture Notes in Computer Science(), vol 9223. Springer, Cham. https://doi.org/10.1007/978-3-319-22360-5_7
Download citation
DOI: https://doi.org/10.1007/978-3-319-22360-5_7
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-22359-9
Online ISBN: 978-3-319-22360-5
eBook Packages: Computer ScienceComputer Science (R0)