Last week, Sanjay Shakkottai (UT Austin) talked about how external agents affect spreading properties of an epidemic -- a prediction or "forward" problem. This talk is about "inverse" problems -- what explains what we are seeing? In particular, is it an epidemic?
Specifically, we ask: can we (early) detect the spread of a new disease, or of a new kind of malware, one whose properties have not been studied, and characteristics not yet identified? We consider the problem of detecting an infection process in a network when the indication that any particular node is infected is extremely noisy -- statistically indistinguishable from everyday behavior.
Such a scenario occurs, for instance, when the only signature of a worm infecting a neighboring network node is a (rarely occurring) temporally-localized increased processor and network load (when the worm is actively spreading from one node to its neighbor). However, many other benign activities have a similar signature; further these benign activities occur frequently (as opposed to the rare occurrence of a worm infection). While it is impossible to distinguish between an infection incidence and a benign activity merely from observing a single node, we show that the spread itself can be used as a global signature of epidemic spread, and thus we can reliably distinguish between these two hypotheses (epidemic / benign activity). In addition, we explore how graph topology impacts our ability to do early detection.
Based on joint with work Chris Milling, Eli Meirom, Sanjay Shakkottai, Shie Mannor and Ariel Orda.
The Information Systems Laboratory Colloquium (ISLC) is typically held in Packard 101 every Thursday at 4:15 pm during the academic year. Refreshments are usually served after the talk.
The Colloquium is organized by graduate students Chris Fougner, Hyeji Kim, Neal Master and Dor Shaviv. To suggest speakers, please contact any of the students.