序贯分析-tutorial.ppt

Sequential analysis:balancing the tradeoff between detection accuracy and detection delay XuanLong Nguyen xuanlong@eecs.berkeley.edu Radlab, 11/06/06 Outline Motivation in detection problems need to minimize detection delay time Brief intro to sequential analysis sequential hypothesis testing sequential change-point detection Applications Detection of anomalies in network traffic (network attacks), faulty software, etc Three quantities of interest in detection problems Detection accuracy False alarm rate Misdetection rate Detection delay time Network volume anomaly detection So far, anomalies treated as isolated events Spikes seem to appear out of nowhere Hard to predict early short burst unless we reduce the time granularity of collected data To achieve early detection have to look at medium to long-term trend know when to stop deliberating Early detection of anomalous trends We want to distinguish “bad” process from good process/ multiple processes detect a point where a “good” process turns bad Applicable when evidence accumulates over time (no matter how fast or slow) e.g., because a router or a server fails worm propagates its effect Sequential analysis is well-suited minimize the detection time given fixed false alarm and misdetection rates balance the tradeoff between these three quantities (false alarm, misdetection rate, detection time) effectively Example: Port scan detection Detect whether a remote host is a port scanner or a benign host Ground truth: based on percentage of local hosts which a remote host has a failed connection We set: for a scanner, the probability of hitting inactive local host is 0.8 for a benign host, that probability is 0.1 Figure: X: percentage of inactive local hosts for a remote host Y: cumulative distribution function for X Hypothesis testing formulation A remote host R attempts to connect a local host at time i let Yi = 0 if the connection attempt is a success, 1 if failed connection As outcomes Y1, Y2