The problem of sequential testing of multiple hypotheses is considered, and two candidate sequential test procedures are studied. Both tests are multihypothesis versions of the binary sequential probability ratio test (SPRT), and are referred to as MSPRTs. The first test is motivated by Bayesian optimality arguments, while the second corresponds to a generalized likelihood ratio test. It is shown that both MSPRTs are asymptotically optimal relative not only to the expected sample size but also to any positive moment of the stopping time distribution, when the error probabilities or, more generally, risks associated with incorrect decisions are small. The results are first derived for the discrete-time case of independent and identically distributed (i.i.d.) observations and simple hypotheses. They are then extended to general, possibly continuous-time, statistical models that may include correlated and nonhomogeneous observation processes. It also demonstrated that the results can be extended to hypothesis testing problems with nuisance parameters, where the composite hypotheses, due to nuisance parameters, can be reduced to simple ones by using the principle of invariance. These results provide a complete generalization of the results given by Veeravalli and Baum (see ibid., vol.41, p.1994-97, 1995), where it was shown that the quasi-Bayesian MSPRT is asymptotically efficient with respect to the expected sample size for i.i.d. observations.
21 August 2006 in IEEE Transactions on Signal Processing
Large-scale computer network attacks in their final stages can readily be identified by observing very abrupt changes in the network traffic. In the early stage of an attack, however, these changes are hard to detect and difficult to distinguish from usual traffic fluctuations. Rapid response, a minimal false-alarm rate, and the capability to detect a wide spectrum of attacks are the crucial features of intrusion detection systems. In this paper, we develop efficient adaptive sequential and batch-sequential methods for an early detection of attacks that lead to changes in network traffic, such as denial-of-service attacks, worm-based attacks, port-scanning, and man-in-the-middle attacks. These methods employ a statistical analysis of data from multiple layers of the network protocol to detect very subtle traffic changes. The algorithms are based on change-point detection theory and utilize a thresholding of test statistics to achieve a fixed rate of false alarms while allowing us to detect changes in statistical models as soon as possible. There are three attractive features of the proposed approach. First, the developed algorithms are self-learning, which enables them to adapt to various network loads and usage patterns. Secondly, they allow for the detection of attacks with a small average delay for a given false-alarm rate. Thirdly, they are computationally simple and thus can be implemented online. Theoretical frameworks for detection procedures are presented. We also give the results of the experimental study with the use of a network simulator testbed as well as real-life testing for TCP SYN flooding attacks
The optimal detection procedure for detecting changes in independent and identically distributed (i.i.d.) sequences in a Bayesian setting was derived by Shiryaev in the 1960s. However, the analysis...
12 December 2012 in IEEE Journal of Selected Topics in Signal Processing
We consider the problem of efficient on-line anomaly detection in computer network traffic. The problem is approached statistically, as that of sequential (quickest) changepoint detection. A multi-cyclic setting of quickest change detection is a natural fit for this problem. We propose a novel score-based multi-cyclic detection algorithm. The algorithm is based on the so-called Shiryaev-Roberts procedure. This procedure is as easy to employ in practice and as computationally inexpensive as the popular Cumulative Sum chart and the Exponentially Weighted Moving Average scheme. The likelihood ratio based Shiryaev-Roberts procedure has appealing optimality properties, particularly it is exactly optimal in a multi-cyclic setting geared to detect a change occurring at a far time horizon. It is therefore expected that an intrusion detection algorithm based on the Shiryaev-Roberts procedure will perform better than other detection schemes. This is confirmed experimentally for real traces. We also discuss the possibility of complementing our anomaly detection algorithm with a spectral-signature intrusion detection system with false alarm filtering and true attack confirmation capability, so as to obtain a synergistic system.
In the standard formulation of the quickest change-point detection problem, a sequence of observations, whose distribution changes at some unknown point in time, is available to a decision maker, and the goal is to detect this change as quickly as possible, subject to false alarm constraints. In this paper, we study the quickest change detection problem in the setting where the information available for decision-making is distributed across a set of geographically separated sensors, and only a compressed version of observations in sensors may be used for final decision-making due to communication bandwidth constraints. We consider the minimax, uniform, and Bayesian versions of the optimization problem, and we present asymptotically optimal decentralized quickest change detection procedures for two scenarios. In the first scenario, the sensors send quantized versions of their observations to a fusion center where the change detection is performed based on all the sensor messages. In the second scenario, the sensors perform local change detection and send their final decisions to the fusion center for combining. We show that our decentralized procedures for the latter scenario have the same first-order asymptotic performance as the corresponding centralized procedures that have access to all of the sensor observations. We also present simulation results for examples involving Gaussian and Poisson observations. These examples show that although the procedures with local decisions are globally asymptotically optimal as the false alarm rate (or probability) goes to zero, they perform worse than the corresponding decentralized procedures with binary quantization at the sensors, unless the false alarm rate (or probability) is unreasonably small.