We propose an algorithm for simultaneously detecting and locating changepoints in a time series, and a framework for predicting the distribution of the next point in the series. The kernel of the algorithm is a system of equations that computes, for each index i, the probability that the last (most recent) change point occurred at i. We evaluate this algorithm by applying it to the change point detection problem and comparing it to the generalized likelihood ratio (GLR) algorithm. We find that our algorithm is as good as GLR, or better, over a wide range of scenarios, and that the advantage increases as the signal-to-noise ratio decreases.
We are aware of a few examples where these techniques have been applied to network measurements. Bla z explore the use of change-point algorithms to detect denial of service attacks @cite_3 . Similarly Deshpande, Thottan and Sikdar use non-parametric CUSUM to detect BGP instabilities @cite_4 .
@cite_4 @cite_3
2123002543 2146697465 2146467316 2119227347
This paper develops two parametric methods to detect low-rate denial-of-service attacks and other similar near-periodic traffic, without the need for flow separation. The first method, the periodic attack detector, is based on a previous approach that exploits the near-periodic nature of attack traffic in aggregate traffic by modeling the peak frequency in the traffic spectrum. The new method adopts simple statistical models for attack and background traffic in the time-domain. Both approaches use sequential probability ratio tests (SPRTs), allowing control over false alarm rate while examining the trade-off between detection time and attack strength. We evaluate these methods with real and synthetic traces, observing that the new Poisson- based scheme uniformly detects attacks more rapidly, often in less than 200 ms, and with lower complexity than the periodic attack detector. Current entropy-based detection methods provide an equivalent time to detection but require flow-separation since they utilize source destination IP addresses. We evaluate sensitivity to attack strength (compared to the rate of background traffic) with synthetic traces, finding that the new approach can detect attacks that represent only 10 of the total traffic bitrate in fractions of a second. The increasing incidence of worm attacks in the Internet and the resulting instabilities in the global routing properties of the border gateway protocol (BGP) routers pose a serious threat to the connectivity and the ability of the Internet to deliver data correctly. In this paper we propose a mechanism to detect predict the onset of such instabilities which can then enable the timely execution of preventive strategies in order to minimize the damage caused by the worm. Our technique is based on online statistical methods relying on sequential change-point and persistence filter based detection algorithms. Our technique is validated using a year's worth of real traces collected from BGP routers in the Internet that we use to detect predict the global routing instabilities corresponding to the Code Red II, Nimda and SQL Slammer worms. Denial-of-service (DoS) detection techniques - such as activity profiling, change-point detection, and wavelet-based signal analysis - face the considerable challenge of discriminating network-based flooding attacks from sudden increases in legitimate activity or flash events. This survey of techniques and testing results provides insight into our ability to successfully identify DoS flooding attacks. Although each detector shows promise in limited testing, none completely solve the detection problem. Combining various approaches with experienced network operators most likely produce the best results. A low-rate distributed denial of service (DDoS) attack has significant ability of concealing its traffic because it is very much like normal traffic. It has the capacity to elude the current anomaly-based detection schemes. An information metric can quantify the differences of network traffic with various probability distributions. In this paper, we innovatively propose using two new information metrics such as the generalized entropy metric and the information distance metric to detect low-rate DDoS attacks by measuring the difference between legitimate traffic and attack traffic. The proposed generalized entropy metric can detect attacks several hops earlier (three hops earlier while the order α = 10 ) than the traditional Shannon metric. The proposed information distance metric outperforms (six hops earlier while the order α = 10) the popular Kullback-Leibler divergence approach as it can clearly enlarge the adjudication distance and then obtain the optimal detection sensitivity. The experimental results show that the proposed information metrics can effectively detect low-rate DDoS attacks and clearly reduce the false positive rate. Furthermore, the proposed IP traceback algorithm can find all attacks as well as attackers from their own local area networks (LANs) and discard attack traffic.