Monitoring event frequencies The monitoring of event frequencies can be used to recognize behavioral anomalies, to identify trends, and to deduce or discard hypotheses about the underlying system. For example, the performance of a web server may be monitored based on the ratio of the total count of requests from the least and most active clients. Exact frequency monitoring, however, can be prohibitively expensive; in the above example it would require as many counters as there are clients. In this paper, we propose the efficient probabilistic monitoring of common frequency properties, including the mode (i.e., the most common event) and the median of an event sequence. We define a logic to express composite frequency properties as a combination of atomic frequency properties. Our main contribution is an algorithm that, under suitable probabilistic assumptions, can be used to monitor these important frequency properties with four counters, independent of the number of different events. Our algorithm samples longer and longer subwords of an infinite event sequence. We prove the almostsure convergence of our algorithm by generalizing ergodic theory from increasinglength prefixes to increasinglength subwords of an infinite sequence. A similar algorithm could be used to learn a connected Markov chain of a given structure from observing its outputs, to arbitrary precision, for a given confidence.

Learning Marked Markov Modulated Poisson Processes for Online Predictive Analysis of Attack Scenarios Runtime predictive analysis of quantitative models can support software reliability in various application scenarios. The spread of logging technologies promotes approaches where such models are learned from observed events. We consider a system visiting transient states of a hidden process until reaching a final state and producing observations with stochastic arrival times and types conditioned by visited states, and we abstract it as a marked Markov modulated Poisson Process (MMMPP) with leftto right structure. We present an ExpectationMaximization (EM) algorithm that learns the MMMPP parameters from observation sequences acquired in repeated execution of the transient behavior, and we use the model at runtime to infer the current state of the process from actual observed events and to dynamically evaluate the remaining time to the final state. The approach is illustrated using synthetic datasets generated from a stochastic attack tree of the literature enriched with an observation model associating each state with an expected statistics of observation types and arrival times. Accuracy of prediction is evaluated under different variability of hidden states sojourn durations and of the observations arrival process, and compared against previous literature that mainly exploits either the timing or the types of observed events.