A Rule Mining-based Advanced Persistent Threats Detection System

Sidahmed Benabderrahmane, Ghita Berrada, James Cheney, Petko ValtchevIJCAI 2021 · DOI

TL;DR

This paper introduces a novel, unsupervised method for detecting Advanced Persistent Threats (APTs) by analyzing system provenance traces. It leverages association rule mining to identify anomalous process behavior, offering an interpretable way to flag suspicious activities and outperform existing anomaly detection techniques on real-world datasets.

What Problem Does This Paper Address?

Advanced Persistent Threats (APTs) are sophisticated, long-term cyberattacks that are notoriously difficult to detect. Traditional security measures like antivirus software and signature-based detection often fail because APTs mimic normal user behavior and are designed to evade detection. While whole-system provenance tracking offers richer data, the sheer volume of this data and the rarity of attack events create a "needle in a haystack" problem. Existing anomaly detection methods struggle with this imbalance and the complexity of provenance data, often requiring extensive manual annotation or failing to capture long-term behavioral patterns. This paper aims to address the challenge of efficiently and effectively detecting APTs by flagging unusual process activities early, minimizing potential damage.

Methods

The core of the proposed system lies in an unsupervised anomaly detection method that utilizes association rule mining on system provenance traces. The authors propose two variants: VR-ARM (Valid Rare ARM) and VF-ARM (Valid Frequent ARM).

  • Provenance Trace Representation: System activities are transformed into a transaction database, where each process is a transaction and its associated events/attributes are items.
  • Association Rule Mining: The system mines for both frequent and rare association rules from this transaction database. Rare rules are particularly emphasized as they can capture unusual, localized patterns indicative of APTs, which might be missed by focusing solely on common behaviors.
  • Anomaly Scoring: Processes are scored based on how well they satisfy rare rules or violate frequent rules. The anomaly score is calculated using a function that combines the "interestingness" (e.g., lift) and length of the matched rules.
  • Ranking: Identified anomalous processes are ranked by their anomaly scores, allowing security analysts to focus their attention on the most suspicious activities.
  • Interpretability: A key advantage highlighted is the explainability of the results. The association rules themselves provide insights into why a process is flagged as anomalous, facilitating deeper understanding and threat prevention.

Datasets

The evaluation was conducted using two publicly available datasets derived from DARPA's Transparent Computing (TC) program. These datasets consist of feature views or "contexts" extracted from raw whole-system provenance graphs.

  • Scenarios: The data covers multiple operating systems (Windows, BSD, Linux, Android) and includes several days of system activity, subjected to APT-like attacks.
  • Contexts: Different contexts were analyzed, focusing on various aspects of process activity:
  • ProcessEvent (PE): Types of events performed by a process.
  • ProcessExec (PX): Name of the process executable.
  • ProcessParent (PP): Name of the parent process executable.
  • ProcessNetflow (PN): IP addresses and ports accessed by a process.
  • ProcessAll (PA): A combination of all the above features.

Key Insights and Ideas

  • Rare Rules as APT Indicators: The paper strongly suggests that APTs often manifest as unusual, localized patterns of behavior that are captured by "rare" association rules, rather than just deviations from globally frequent patterns.
  • Interpretability is Crucial: Providing explainable anomaly detection results (via association rules) is vital for security analysts to effectively investigate and understand APTs, moving beyond simple alerts.
  • Unsupervised Learning is Necessary: Given the inherent data imbalance (low percentage of attack events) and the lack of comprehensive labeled data for APTs, unsupervised learning techniques are essential.
  • Provenance Granularity Matters: The choice of provenance features (PE, PX, PN, etc.) significantly impacts the effectiveness of anomaly detection, with different contexts revealing different types of anomalies.

Key Results

The proposed VR-ARM and VF-ARM methods demonstrated strong performance, often outperforming existing anomaly detection techniques.

  • Ranking Quality: The paper reports high normalized discounted cumulative gain (nDCG) scores, indicating that the methods effectively rank attack processes as highly anomalous, placing them near the top of the ranked lists. For instance, VR-ARM achieved scores up to 0.87 on Android (scenario 1) for the ProcessEvent context.
  • Efficiency: VR-ARM, in particular, showed good time efficiency, attributed to the smaller search space of rare itemsets compared to other methods. Some competing algorithms (e.g., CompreX, FPOF, OD) struggled to complete within reasonable timeframes on larger datasets.
  • Cross-OS Effectiveness: The methods showed consistent performance across various operating systems (Windows, BSD, Linux, Android), highlighting their OS-agnostic nature.
  • Explainable Output: The system successfully provided interpretable outputs, allowing analysts to understand the specific rules that flagged a process as anomalous, such as altering library files and communicating with specific IP addresses.

Limitations and Future Work

  • Limitations:
    • The paper acknowledges that some competing algorithms did not finish within reasonable time limits (indicated as DNF).
  • The current method relies on static analysis of provenance traces.
  • Future Work:
    • Developing a stream version of the method to handle real-time data.
  • Integrating analyst feedback into the scoring loop for active learning.
  • Further exploring the impact of different provenance data granularities and combinations.

Summary updated

BibTeX
@inproceedings{benabderrahmane2021rule,
  author = {Sidahmed Benabderrahmane and Ghita Berrada and James Cheney and Petko Valtchev},
  title = {{A Rule Mining-based Advanced Persistent Threats Detection System}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.24963/ijcai.2021/494},
}
Figure