A Survey of Outlier Detection Methods in Network Anomaly Identification <s> Proximity-based Approaches <s> In this paper, we propose a novel formulation for distance-based outliers that is based on the distance of a point from its kth nearest neighbor. We rank each point on the basis of its distance to its kth nearest neighbor and declare the top n points in this ranking to be outliers. In addition to developing relatively straightforward solutions to finding such outliers based on the classical nested-loop join and index join algorithms, we develop a highly efficient partition-based algorithm for mining outliers. This algorithm first partitions the input data set into disjoint subsets, and then prunes entire partitions as soon as it is determined that they cannot contain outliers. This results in substantial savings in computation. We present the results of an extensive experimental study on real-life and synthetic data sets. The results from a real-life NBA database highlight and reveal several expected and unexpected aspects of the database. The results from a study on synthetic data sets demonstrate that the partition-based algorithm scales well with respect to both data set size and data set dimensionality. <s> BIB001 </s> A Survey of Outlier Detection Methods in Network Anomaly Identification <s> Proximity-based Approaches <s> The wide spread of worms poses serious challenges to today's Internet.Various IDSes (Intrusion Detection Systems) have been proposed to identify or prevent such spread. These IDSes can be largely classified as signature-based or anomaly-based ones depending on what type of knowledge the system knows. Signature-based IDSes are unable to detect the outbreak of new and unidentified worms when the worms' characteristic patterns are unknown. In addition, new worms are often sufficiently intelligent to hide their activities and evade anomaly detection. Moreover, modern worms tend to spread more quickly, and the outbreak period lasts in the order of hours or even minutes. Such characteristics render existing detection mechanisms less effective.In this work, we consider the drawbacks of current detection approaches and propose PAIDS, a proximity-assisted IDS approach for identifying the outbreak of unknown worms. PAIDS does not rely on signatures.Instead, it takes advantage of the proximity information of compromised hosts. PAIDS operates on an \emph{orthogonal} dimension with existing IDS approaches and can thus work \emph{collaboratively} with existing IDSes to achieve better performance. We test the effectiveness of PAIDS with trace-driven simulations and show that PAIDS has a high detection rate and a low false positive rate. <s> BIB002
Proximity-based techniques are simple to implement and make no prior assumptions about the data distribution model. However, they suffer high computational cost as they are founded on the calculation of the distances between all records. The computational complexity is directly proportional to both the dimensionality of the data m and the number of records n. The k-nearest neighbour (k-NN) algorithm is suitable for outlier detection; it calculates the nearest neighbours of a record using a suitable distance calculation metric such as Euclidean distance or Mahalanobis distance. A definition of proximity based outlier D k (p) from BIB001 is discussed in Definition 4 in Sub-section 2.1. A partition-based outlier detection algorithm first partitions the input points using a clustering algorithm, and computes lower and upper bounds on D k for points in each partition. It then uses this information to identify the partitions that cannot possibly contain the top n outliers and prunes them. Outliers are then computed from the remaining points (belonging to unpruned partitions) in a final phase. PAIDS (Proximity assisted intrusion detection) BIB002 , is an approach for identifying the outbreak of unknown worms. PAIDS does not rely on signatures. Instead, it takes advantage of the proximity information of compromised hosts. PAIDS operates on an orthogonal dimension with existing IDS approaches and can thus work collaboratively with existing IDSs to achieve better performance. The effectiveness of PAIDS with trace-driven simulations has a high detection rate and a low false positive rate. The major limitation of this approach is selectiing an appropriate proximity measure, especially for the high dimensional mixed type data. Also, developing a heuristic method for appropriate threshold selection is a difficult task.