Fast and Robust Worm Detection Algorithm Tian Bu Aiyou Chen Scott Vander Wiel Thomas Woo bearhsu.


of 23
  • Fast and Robust Worm Detection Algorithm Tian Bu Aiyou Chen Scott Vander Wiel Thomas Woo bearhsu
  • Outline Introduction Algorithm Design CUSUM Maximum Likelihood Inference of Worm Propagation Rate Algorithm Evaluation Conclusion
  • Requirement of worm detections High -speed: Fast worms: making damage within minutes Accuracy: False positives: alarm without worms False negatives: worms without alarms Avoiding both Robustness: Working well for various worms with different propagation characteristics
  • Introduction Motivation: Proposing detecting methods with above requirements Method of work: Monitoring unused IP addresses Unsolicited traffic Using unsolicited packets as input to worm detection algorithms Result: Proposing a two-step algorithm 1st stage: CUSUM counting 2nd stage: Exponential detector
  • Unsolicited traffic Subnets usually has many unused IP addresses Bell Labs use these unused addresses as a network telescope Unsolicited packet: Packets sent to the unused IP addresses Usage: Arrival process of unsolicited packets Arrival of new sources that send these packets
  • Unsolicited Packets vs. Sources Stream of all unsolicited packets “Scan” count t-sample stream stream of unsolicited packets from external sources that have not been observed in the previous t seconds “Scanner” count - Inter-arrival time
  • Unsolicited packets vs. sources - Inter-arrival time
  • Effect of worms without worms Inter arrival-time should be exponentially distributed Poisson Distribution
  • Algorithm Change Detection Maximum Likelihood Inference of Worm Propagation Rate Complete Algorithm
  • Change Detection using CUSUM Sn: CUSUM Xn: Tn – Tn-1, inter-arrival time While Sn exceeds a threshold h, stage 2 is triggered if the mean of Xn shifts from μ to something smaller than μ−pμ at sample nw then Sn will tend to accumulate positive increments after nw and thus eventually cross the threshold h and signal a change.
  • Maximum Likelihood Inference A fresh scanner arrival can be modeled as a non-stationary Poisson process Considering the ‘background’ traffic and simply assuming that the worm starts at 0 (tw =0 ) Tn0: the most resent time that Si >0 (before CUSUM signal) Tj = Tn0+j – Tn0, inter-arrival time relative to n0 We can observe only T1, …, Tn, instead of T1, …Tn
  • Maximum Likelihood Inference
  • Maximum Likelihood Inference
  • Maximum Likelihood Inference
  • Maximum Likelihood Inference normal distributed with mean 0 and variance 1 [20] under the null hypothesis r = r0 r0: maximal rate that can be ignored Purpose of 2nd stage: testing that whether r is abnormally large or not
  • Complete Worm Detection Algorithm
  • Estimation #1 - Slammer
  • Estimation #2 - Witty
  • Estimation #3 - Nimda
  • Estimation #4 - Blaster
  • Estimation - Result
  • Conclusion Devised a fast and robust worm detection algorithm without any payload signatures Applied the algorithm with REAL data to demonstrate the effectiveness Future work next page...
  • Future work Evaluate from a variety of Internet locations Reduce computational complexity Reduce false signal rate of the CUSUM To make MLE computing invoked less frequently Find new MLE algorithms