Affiliations: [a] Department of Electrical and Computer Engineering, Carnegie Mellon University, Pittsburgh, PA, USA. E-mail: mallios@cmu.edu | [b] Institute for Software Research, Carnegie Mellon University, Pittsburgh, PA, USA. E-mail: lbauer@cmu.edu | [c] Computer Science Department, Carnegie Mellon University, Pittsburgh, PA, USA. E-mail: dilsun@cs.cmu.edu | [d] Istituto di Informatica e Telematica, National Research Council, Pisa, Italy. E-mail: Fabio.Martinelli@iit.cnr.it | [e] Newcastle University, Newcastle, UK. E-mail: charles.morisset@newcastle.ac.uk
Correspondence:
[*]
Corresponding author: Yannis Mallios, Department of Electrical and Computer Engineering, Carnegie Mellon University, Pittsburgh, PA, USA. E-mail: mallios@cmu.edu.
Abstract: This paper presents a formal framework for run-time enforcement mechanisms, or monitors, based on probabilistic input/output automata [Task-structured probabilistic I/O automata, Technical Report MIT-CSAIL-TR-2006-060, 2006; Proceedings of the 8th International Workshop on Discrete Event Systems, 2006, pp. 207–214], which allows for the modeling of complex and interactive systems. We associate with each trace of a monitored system (i.e., a monitor interposed between a system and an environment) a probability and a real number that represents the cost that the actions appearing on the trace incur on the monitored system. This allows us to calculate the probabilistic (expected) cost of the monitor and the monitored system, which we use to classify monitors, not only in the typical sense, as sound and transparent [ACM Transactions on Information and System Security 12(3) (2009), 1–41], but also at a more fine-grained level, as cost-optimal or cost-efficient. We show how a cost-optimal monitor can be built using information about cost and the probabilistic future behavior of the system and the environment, showing how deeper knowledge of a system can lead to construction of more efficient security mechanisms.
