text: This paper introduces a new similarity measure, the covering similarity, which we formally define for evaluating the similarity between a symbolic sequence and a set of symbolic sequences. A pairwise similarity can also be directly derived from the covering similarity to compare two symbolic sequences. An efficient implementation to compute the covering similarity is proposed which uses a suffix-tree data structure, but other implementations, based on suffix array for instance, are possible and are possibly necessary for handling very large-scale problems. We have used this similarity to isolate attack sequences from normal sequences in the scope of host-based intrusion detection. We have assessed the covering similarity on two well-known benchmarks in the field. In view of the results reported on these two datasets for the state-of-the-art methods, according to the comparative study, we have carried out based on three challenging similarity measures commonly used for string processing, or in bioinformatics, we show that the covering similarity is particularly relevant to address the detection of anomalies in sequences of system calls.
  @cite_7: 
  @cite_48: Business Process Management Systems (BPMS) log events and traces of activities during the execution of a process. Anomalies are defined as deviation or departure from the normal or common order. Anomaly detection in business process logs has several applications such as fraud detection and understanding the causes of process errors. In this paper, we present a novel approach for anomaly detection in business process logs. We model the event logs as a sequential data and apply kernel based anomaly detection techniques to identify outliers and discordant observations. Our technique is unsupervised (does not require a pre-annotated training dataset), employs kNN (k-nearest neighbor) kernel based technique and normalized longest common subsequence (LCS) similarity measure. We conduct experiments on a recent, large and real-world incident management data of an enterprise and demonstrate that our approach is effective.
  @cite_0: We present a set of novel algorithms which we call sequenceMiner that detect and characterize anomalies in large sets of high-dimensional symbol sequences that arise from recordings of switch sensors in the cockpits of commercial airliners. While the algorithms that we present are general and domain-independent, we focus on a specific problem that is critical to determining the system-wide health of a fleet of aircraft. The approach taken uses unsupervised clustering of sequences using the normalized length of the longest common subsequence as a similarity measure, followed by detailed outlier analysis to detect anomalies. In this method, an outlier sequence is defined as a sequence that is far away from the cluster center. We present new algorithms for outlier analysis that provide comprehensible indicators as to why a particular sequence is deemed to be an outlier. The algorithms provide a coherent description to an analyst of the anomalies in the sequence when compared to more normal sequences. In the final section of the paper, we demonstrate the effectiveness of sequenceMiner for anomaly detection on a real set of discrete-sequence data from a fleet of commercial airliners. We show that sequenceMiner discovers actionable and operationally significant safety events. We also compare our innovations with standard hidden Markov models, and show that our methods are superior.
  @cite_44: 
  @cite_23: A computer adaptable method for finding similarities in the amino acid sequences of two proteins has been developed. From these findings it is possible to determine whether significant homology exists between the proteins. This information is used to trace their possible evolutionary development. The maximum match is a number dependent upon the similarity of the sequences. One of its definitions is the largest number of amino acids of one protein that can be matched with those of a second protein allowing for all possible interruptions in either of the sequences. While the interruptions give rise to a very large number of comparisons, the method efficiently excludes from consideration those comparisons that cannot contribute to the maximum match. Comparisons are made from the smallest unit of significance, a pair of amino acids, one from each protein. All possible pairs are represented by a two-dimensional array, and all possible comparisons are represented by pathways through the array. For this maximum match only certain of the possible pathways must, be evaluated. A numerical value, one in this case, is assigned to every cell in the array representing like amino acids. The maximum match is the largest number that would result from summing the cell values of every
  @cite_5: Information is considered to be the most valuable asset of any organization and hence, it should be securely maintained. However, rapid proliferation of the Internet and Web applications has increased the threat of information security breaches. Traditional database security mechanisms are often not sufficient to protect sensitive information against novel attacks. Intrusion detection systems (IDS) are used to detect any such intrusion, once traditional security mechanisms have been compromised. User-level profile is effective for database intrusion detection, but maintaining such profiles is not practical for an organization with a large number of users. Thus, an IDS needs to be flexible enough to choose a profile granularity according to the type of the organization. Further, only intra-transactional pattern matching for intrusion detection is not quite effective for detecting intrusion in a database. We propose an IDS that uses inter-transactional as well as intra-transactional features for intrusion detection. It supports selection of profile and transactional feature granularity as well. We use sequence alignment as a tool for comparing database access patterns of genuine users and intruders.
  @cite_15: One way to detect intruders on the Internet is to compare the similarity of two thumbprints. A thumbprint is a summary of a connection that characterizes the connection. The packet gap thumbprint consists of sequences of non-negative real number representing the time gaps between "send" packets. This paper formalized definitions of similarity between two non-negative real number sequences, by introducing spl epsiv -similarity, partial sum and longest spl epsiv -similar subsequence (LSS). Length of LSS is a measurement of similarity between two sequences. The longest spl epsiv -similar subsequence (LSS) problem is a generalization of the well known longest common subsequence (LCS) problem. The goal of this paper is to find an optimal solution to the LSS problem. We analyzed the property of partial sums and proposed to focus on the minimum matched partial sum which leads to an optimal solution to LSS while reduce the problem space. As the LSS problem has optimal structure, we proposed an algorithm based on dynamic programming technique. Time complexity of this algorithm is O(m sup 2 n sup 2 ). By using a property of the partial sums, we reduced the time complexity to O(mn(m+n)).
  @cite_16: 
summary: @cite_0 process each sequence as a whole and a pair-wise sequence kernel (string kernel) is used to provide the sequence space with a similarity measure. The @math -Near-Neighbor rule or any of the so-called kernel machine methods can then be applied to model the 'normal' clusters and isolate the 'anomalies'. These approaches find their roots in text processing @cite_44 (Levenshtein's distance) or in Bioinformatics @cite_7 @cite_16 (Smith and Watermans), @cite_23 (Needleman-Wunsch), @cite_5 (BLAST) and Longest Common Subsequence (LCS) or Longest Similar Subsequence @cite_15 @cite_48 . Such methods do not seem to outperform window-based approaches and are in general much more costly in term of algorithmic complexity than state of the art methods.