# Presentation: 478173

## Comparative Evaluation of Anomaly Detection Techniques for Sequence Data

- Varun Chandola, Vipin Kumar
- Department of Computer Science
- University of Minnesota
*{chandola,kumar}@cs.umn.edu*

- Varun Mithal
- Department of Computer Science
- Indian Institute of Technology Kanpur
*varunm@iitk.ac.in*

## Outline

- Problem Statement
- Techniques
- Kernel Based Techniques
- Window Based Techniques
- Markovian Techniques
- Experimental Evaluation
- Experimental Methodology
- Data Sets
- Artificial Data Generator
- Results
- Conclusions

## Motivation

- Several anomaly detection techniques for symbolic sequences have been proposed.
- Each technique proposed for a single application domain.
- No comparative evaluation of techniques across different domains.
- Such evaluation is essential to identify relative strengths and weaknesses of the techniques.

| 

Data/Applications | State Based |  |  |  | Model Based | Kernel Based |  |
| --- | --- | --- | --- | --- | --- | --- | --- |
|  | FSA | PST | SMT | HMM | Ripper | Clustering | kNN |
| Operating System Call Data | [4][7]
[11] [13] |  | [3] | [4][5] [12] | [4][9] |  |  |
| Protein  Data |  | [10] |  |  |  |  |  |
| Flight Safety Data |  |  |  | [15] |  | [14] |  |

- Anomaly Detection for Symbolic Sequences – Current State of Art

## Problem Statement

- Given a set of *n *sequences **S**, and a query sequences *S**q*, find an anomaly score for *S**q* with respect to **S**.
- Sequences in **S** are assumed to be (mostly) normal.
- This definition is applicable in multiple domains such as
- Flight safety
- System call intrusion detection
- Proteomics

## Techniques

- Kernel Based Techniques
- Window Based Techniques
- Markovian Techniques

## Kernel Based Techniques

- Define a similarity kernel between sequences.
- Manhattan Distance – *not applicable for unequal length sequences*.
**Normalized Longest Common Sequence.**
- Apply any traditional proximity based anomaly detection technique.
- CLUSTER*
- Cluster normal sequences into a fixed number of clusters.
- Anomaly score of a test sequence is the inverse of similarity to its closest cluster medoid.
- kNN
- Anomaly score of a test sequence is the inverse of its similarity to the kth nearest neighbor in the normal sequence data set.

- *S. Budalakoti, A. Srivastava, R. Akella, and E. Turkov. Anomaly detection in large sets of high-dimensional symbol sequences. Technical Report NASA TM-2006-214553, NASA Ames Research Center, 2006.

## Window Based Technique (tSTIDE*)

- Extract finite length sliding windows from test sequence.
- For each window, find its frequency in the training data set.
- The frequency acts an inverse anomaly score for the window.
- Combine the per-window anomaly score to obtain overall anomaly score for the test sequence.

- *S. Forrest, C. Warrender, and B. Pearlmutter. Detecting intrusions using system calls: Alternate data models. In *Proceedings of the 1999 IEEE Symposium on Security and Privacy, pages 133–145, Washington, DC, *USA, 1999.

## Markovian Techniques

- Estimate the probability of each event of the test sequence conditioned on the previously observed events.
- Combine the per-event probabilities to obtain an overall anomaly score.
- FSA [Michael and Ghosh, 2000]
- Event probability is the conditioned on previous l-1 events.
- If previous l-1 events do not occur in training data, the event is ignored.
- FSA-z
- Same as FSA, except if the previous l-1 events do not occur in training data, the event probability is 0.
- PST [Song et al, 2006]
- If the previous l-1 events do not occur in the training data sufficient number of times, they are replaced by the largest *suffix* which occurs more than the required threshold.
- Ripper [W. Lee and S. Stolfo, 1998]
- If the previous l-1 events do not occur in the training data sufficient number of times, they are replaced by the largest *subset* which occurs more than the required threshold.
- HMM [Forrest et al, 1999]
- The event probability is equal to the corresponding transition probability in an HMM learnt from the training data.

## Artificial Data Generator

- HMM based generator that can generate normal sequences that are similar to each other and also two type of anomalous sequences.
- Anomalous sequences are generated from a different HMM than what is used for normal  sequences.
- Anomalous sequences are similar to normal sequences with minor deviations.

**HMM used to generate artificial sequences.**

## Evaluation

- Sequence Database, **S**

- Anomaly Data, **S****A**

- Test Data, **S****A**

*p*

*q*

- Model **M**

- Training

- Testing

- Anomaly Scores, A(**S****q**)

- δq % Predicted Anomalies

- Clustering
- kNN
- tStide
- FSA
- FSA-z
- PST
- Ripper
- HMM

- Either contains only normal sequences (*semi-supervised setting*)
- Or
- Majority normal sequences (*unsupervised setting*)

- The ratio q/(p+q) sets a baseline accuracy (random selection)

- δ determines how many top anomalies  are considered significant in the domain.

- Training Data, **S****T**

## Experimental Setup

- Data Sources
- Protein Sequence Data [*Sun et al, 2006*]
- Five different protein families selected
- For each family, test data set was constructed by sampling sequences from other four families
- Alphabet size = 46
- System Call Intrusion Detection Data [*Lee et al, 1998 ;Forrest et al, 1999; Michael and Ghosh, 2000*] and Network Intrusion Detection Data [*Lippmann et al, 2000*]
- Data corresponding to different types of intrusions
- Corresponding normal data also available
- Alphabet size = between 26 and 74
- Artificially generated data sets.
- Reporting precision on anomaly class.

## Results on Public Data Sets

**Performance of 8 different anomaly detection techniques on a variety of publicly available data sets.**

## Results on Artificial Data Sets 1

- The anomalous sequences are copies of normal sequences with k random symbols inserted.
- FSA-z is the most effective technique in detecting anomalies.

## Results on Artificial Data Sets 2

- All data sets were generated from the artificial data generator.
- Anomalous sequences in d1 are generated from a totally different HMM than the normal sequences.
- Anomalous sequences in d2-d6 are minor variants of normal sequences.

## Conclusions

- Through experimental evaluation we have provided insights into strengths and weaknesses of different techniques.
- None of the techniques were found to be consistently superior to all others.
- Performance depends on the nature of the sequence data set.
- Artificial data generator allows us to arrive at conclusions that are not evident from the public data sets.
- FSA-z and FSA are most consistent techniques.
- Performance of kNN is somewhat better than that of CLUSTER.
- Performance of both techniques is highly dependent on the choice of similarity measure.

## Future Work

- Extensive evaluation of techniques for continuous sequences.
- Extending the techniques to multivariate case.
- Multivariate symbolic sequences.
- Multivariate continuous sequences.
- Mixed event sequences.

## References

- R. Blender, K. Fraedrich, and F. Lunkeit. Identification of cyclone track regimes in the north atlantic. *Quarterly Journal of the Royal **Meteorological Society, 123(539):727–741, 1997.*
- Y. Bu, T.-W. Leung, A. Fu, E. Keogh, J. Pei, and S. Meshkin. Wat: Finding top-k discords in time series database. In *Proceedings of 7**th** SIAM International Conference on Data Mining, 2007.*
- E. Eskin and S. Stolfo. Modeling system call for intrusion detection using dynamic window sizes. In *Proceedings of DARPA Information Survivability Conference and Exposition, 2001.*
- S. Forrest, C. Warrender, and B. Pearlmutter. Detecting intrusions using system calls: Alternate data models. In *Proceedings of the 1999 IEEE Symposium on Security and Privacy, pages 133–145, Washington, DC, *USA, 1999. IEEE Computer Society.
- B. Gao, H.-Y. Ma, and Y.-H. Yang. Hmms (hidden markov models) based on anomaly intrusion detection method. In *Proceedings of International Conference on Machine Learning and Cybernetics, pages *381–385. IEEE Computer Society, 2002.
- R. Gwadera, M. J. Atallah, and W. Szpankowski. Detection of significant sets of episodes in event sequences. In *Proceedings of the Fourth IEEE International Conference on Data Mining, pages 3–10, Washington, DC, *USA, 2004. IEEE Computer Society.
- S. A. Hofmeyr, S. Forrest, and A. Somayaji. Intrusion detection using sequences of system calls. *Journal of Computer Security, 6(3):151–180, *1998.
- E. Keogh, J. Lin, S.-H. Lee, and H. V. Herle. Finding the most unusual time series subsequence: algorithms and applications. *Knowledge and Information Systems, 11(1):1–27, 2006.*

## References

- W. Lee and S. Stolfo. Data mining approaches for intrusion detection. In *Proceedings of the 7th USENIX Security Symposium, San Antonio, *TX, 1998.
- P. Sun, S. Chawla, and B. Arunasalam. Mining for outliers in sequential databases. In *Proceedings of SIAM Conference on Data Mining, 2006.*
- N. Ye. A markov chain model of temporal behavior for anomaly detection. In *Proceedings of the 5th Annual IEEE Information Assurance Workshop. IEEE, 2004.*
- X. Zhang, P. Fan, and Z. Zhu. A new anomaly detection method based on hierarchical hmm. In *Proceedings of the 4th International Conference on Parallel and Distributed Computing, Applications and Technologies, *pages 249–252, 2003.
- C. C. Michael and A. Ghosh. Two state-based approaches to program based anomaly detection. In *Proceedings of the 16th Annual Computer Security Applications Conference, page 21, *2000.
- S. Budalakoti, A. Srivastava, R. Akella, and E. Turkov. Anomaly detection in large sets of high-dimensional symbol sequences. Technical Report NASA TM-2006-214553, NASA Ames Research Center, 2006.
- A. N. Srivastava. Discovering system health anomalies using data mining techniques. In *Proceedings of 2005 Joint Army Navy NASA Airforce Conference on Propulsion, 2005.*
- P. K. Chan and M. V. Mahoney. Modeling multiple time series for anomaly detection. In *Proceedings of the Fifth IEEE International Conference on Data Mining, pages 90–97, Washington, USA, 2005.*