TL;DR
This paper introduces the Motif Tracking Algorithm (MTA), an immune-inspired method for discovering unknown, variable-length patterns (motifs) in time-series data. Applied to system call sequences, the MTA effectively compresses complex execution traces into a set of meaningful motifs, paving the way for enhanced security profiling and anomaly detection.
What Problem Does This Paper Address?
Identifying patterns in time-series data is a well-established research area, but most existing methods focus on finding known patterns. The challenge this paper tackles is the discovery of unknown and potentially variable-length motifs within complex sequential data. Specifically, the authors are interested in system call sequences generated by operating systems. These sequences, while low-level, offer a detailed view of process execution and are crucial for security applications like intrusion detection. However, the sheer volume and complexity of these sequences make manual analysis or traditional pattern-matching techniques impractical. The goal is to find repeating subsequences within these system call traces that can represent higher-level functional behaviors, thereby enabling data compression and the creation of process profiles for anomaly detection.
Methods
The core of the paper is the Motif Tracking Algorithm (MTA). Inspired by the human immune system's memory theory, the MTA employs a population-based approach. It uses a Symbolic Aggregate approximation (SAX) technique to convert raw time-series data (system calls represented as integers) into a symbolic representation. This discretization helps manage amplitude scaling issues and reduces dimensionality.
The MTA then uses a sliding window to extract subsequences, which are converted into symbol strings (words). These words form a symbol matrix. The algorithm initializes a population of trackers, which are essentially signatures for potential motifs. These trackers are then matched against the words in the symbol matrix. Trackers that show repeated matches are "stimulated" and candidates for proliferation (extending their length) and mutation (incorporating new symbols).
A key aspect is the algorithm's ability to handle variable-length motifs without prior knowledge of their length. It also incorporates trivial match elimination (TME) to prune less significant patterns and focus the search. The process iteratively refines the tracker population and motif candidates until no further significant motifs are found. The use of Euclidean distance with a match threshold (r) is employed to confirm genuine motif status by comparing original time-series data.
Datasets
The primary dataset used in this paper is a sequence of 1,000 system calls generated from a Linux SSH server session. This data was collected using the strace utility on a VMware virtual machine running Debian Linux. The system calls were converted to their OS ID numbers, and arguments were removed, resulting in a one-dimensional sequence of integers. The authors make this dataset available online.
Key Insights and Ideas
- Immune System Inspiration for Pattern Discovery: The paper demonstrates the efficacy of drawing inspiration from biological immune systems (specifically immune memory) for developing novel pattern recognition algorithms.
- Discovering Unknown, Variable-Length Motifs: The MTA's ability to find motifs of unknown and varying lengths is a significant advantage over methods that require predefined lengths.
- System Calls as a Rich Source for Security Profiling: System call sequences, despite their low-level nature, contain valuable information about process behavior that can be distilled into meaningful motifs for security applications.
- Data Compression for Anomaly Detection: The MTA's ability to compress large system call traces into a limited set of motifs offers a practical way to represent "normal" behavior, making it easier to identify deviations indicative of anomalies or intrusions.
- Trade-off Between Speed and Accuracy: The research highlights a clear trade-off between search speed and detection accuracy, controllable through parameters like symbol length (
s) and the use of trivial match elimination (TME).
Key Results
The MTA was applied to a dataset of 1,000 system calls from an SSH session. The algorithm successfully compressed this data into eight significant motifs.
- Motif 1 was the largest, spanning 280 system calls and occurring twice, representing repeated
lsandchmodcommands. - The MTA identified motifs that were a super-set of observed command-level patterns, validating its accuracy.
- The research showed that reducing symbol length (
s) increased the number of motifs detected but significantly slowed down execution time. For instance, increasingsfrom 10 to 40 reduced execution time by 96.2% but also led to fewer motifs being detected. - Trivial Match Elimination (TME) was found to significantly improve search speed (e.g., reducing time by 84.2% when
a=4) but could lead to a loss in detection accuracy or a shift in the detected motifs. - The alphabet size (
a) had less impact on detection ability when TME was off, but with TME, changes inacould alter which motifs were found.
Limitations and Future Work
Limitations:
- The paper acknowledges that the system call representation (averaging values within a window) might not perfectly capture the nuances of system call sequences, as there isn't always a direct numerical relationship between consecutive calls.
- The sensitivity to parameters (
sanda), particularly when TME is active, suggests that the choice of parameters can influence the search space and the consistency of results.
Future Work:
- The authors propose developing a System Call Expression Language (SCEL). This language would act as a higher-level, regular-expression-like tool for describing system call motifs, representing atomic actions and higher-level functionality.
- This SCEL could potentially be used as input to the MTA to enhance its motif detection capabilities by providing a more structured representation of system call similarity.
- The motifs identified can be used to build process profiles for anomaly detection and behavior classification, which is a key area for future security applications.
Summary updated