MAGIC: Detecting Advanced Persistent Threats via Masked Graph Representation Learning

1 Introduction

• Prior APT detection methods may require attack data or prior knowledge, miss rich contextual information, or incur prohibitive computation overhead.APTs are described as difficult to detect because of their stealthy and changeful nature.Source: §1 · p. 1
• MAGIC combines self-supervised masked graph representation learning with outlier detection to identify key attack entities from audit logs.Its graph masked auto-encoder uses masked feature reconstruction and sample-based structure reconstruction as joint supervision.Source: §1 · pp. 1–2
• MAGIC supports batched-log and system-entity detection under different supervision levels, with optional feedback-based adaptation to concept drift and false positives.The approach is designed to work without attack-containing data and also supports semi-supervised and fully supervised conditions.Source: §1 · p. 2
• MAGIC achieves 97.26% precision and 99.91% recall for entity-level detection, and is 51 times faster than ShadeWatcher.The evaluation covers three datasets, including real-world DARPA attacks and simulated attacks.Source: §1 · p. 2
• The paper makes MAGIC’s implementation and pre-processed datasets public to benefit future research.The paper also reports evaluation on three widely used datasets involving real-world and simulated attacks.Source: §1 · p. 2

2.1 Motivating Example

• The Pine backdoor with Drakon Dropper illustrates an attack in which a phishing email delivers an executable used for reconnaissance and a silent connection to the attacker.The figure is a pruned provenance-graph subgraph; striped entities are considered malicious.Source: §2.1 · p. 2

2.2 Prior Research and their Limitations

• Supervised detectors can depend on attack patterns or attack-containing logs and remain vulnerable to concept drift or unseen patterns; MAGIC uses self-supervised anomaly detection without attack-containing data.Rule construction and maintenance can also be expensive and time-consuming.Source: §2.2 · pp. 2–3
• Statistics-based methods may mistake rare entities for anomalies and use shallow graph features, while deep-learning detectors can impose prohibitive computation and memory costs.MAGIC uses graph representation learning for deeper feature extraction and graph masked auto-encoders to reduce computational demands.Source: §2.2 · p. 3
• Unlike task-specific end-to-end detectors, MAGIC is described as supporting multiple detection granularities, scenarios, and audit-log sources.Examples of prior task-specific systems include ATLAS for attack reconstruction and Unicorn for system-level alarms from streaming logs.Source: §2.2 · p. 3

2.3 Threat Model and Definitions

• The threat model assumes external attackers leave trackable log evidence and excludes poison and evasion attacks; provenance graphs connect entity nodes with typed interaction edges.MAGIC can alert on batches or locate malicious system entities; the paper also describes a two-stage workflow from batch detection to entity-level analysis.Source: §2.3 · p. 3

3 MAGIC Overview

• MAGIC’s pipeline transforms audit logs into provenance graphs, computes graph embeddings, and detects outliers, with an optional model-adaptation mechanism.Training models benign behavior; inference uses the trained representation and outlier detection on target data.Source: §3 · pp. 3–4
• Provenance graph construction converts system entities and their interactions into nodes and edges, while removing redundant information.The graphs are built from audit logs stored in batches.Source: §3 · p. 4
• The graph representation module combines graph features and structural information to produce node embeddings and a system-state embedding.It is built on graph masked auto-encoders and sample-based structure reconstruction.Source: §3 · p. 4
• System-state embeddings support batched-log detection, whereas node embeddings support finer-grained detection of suspicious entities.An outlier system state is unseen and potentially malicious; node-embedding outliers indicate suspicious entities.Source: §3 · p. 4
• A two-stage workflow screens log batches before entity-level analysis, reducing computation compared with entity-level detection on every batch.The paper says this can save computational resources and avoid false alarms without affecting detection fineness.Source: §3 · p. 4
• Analyst-confirmed detection results can feed back into MAGIC to adapt to benign behavior changes and address concept drift.The paper describes this adaptation as semi-supervised.Source: §3 · p. 4

4 Design Details

• MAGIC’s pipeline has graph construction, graph representation, detection, and an adaptation mechanism for concept drift and feedback.Source: §4 · p. 5

4.1 Provenance Graph Construction

• Log parsing extracts entities, interactions, and categorical labels from audit logs to form a prototype provenance graph.Source: §4.1 · p. 5
• Lookup embeddings map node and edge labels to fixed-size vectors; construction also combines redundant edges and averages the embeddings of remaining edge labels.The lookup operates under a transductive setting, with unique labels determined by the data source.Source: §4.1 · p. 5

Ⅱ. Redundant Edges Removed

• 79.60% of all edges are reduced on the DARPA E3 Trace dataset, while MAGIC reports little information loss from generalizing entity and interaction descriptions.Source: Ⅱ. Redundant Edges Removed · p. 5

4.2 Graph Representation Module

• The graph representation module masks node features, encodes graph information into embeddings, and uses feature and structure reconstruction for training supervision.Source: §4.2 · p. 5

4.2.1 Feature Masking

• During training, randomly selected nodes have their initial embeddings replaced by a mask token; nodes are not masked during detection.Source: §4.2.1 · p. 6

4.2.2 Graph Encoder

• Stacked GAT layers use attention to incorporate node features and multi-hop interactions, while average pooling produces a graph-level system-state embedding.Source: §4.2.2 · pp. 6–7

4.2.3 Graph Decoder

• The decoder combines scaled-cosine reconstruction of masked node features with sampled edge-pair reconstruction, avoiding full O(N^2) adjacency decoding.An MLP-based structure objective aims to maximize behavioral information in embeddings; the two reconstruction losses jointly train the representation module.Source: §4.2.3 · p. 7

4.3 Detection Module

• A K-D Tree stores benign embeddings; thresholded nearest-neighbor anomaly scores flag entities or batched-log system states as outliers.The search takes log(N) time in the number of memorized training embeddings.Source: §4.3 · pp. 7–8

4.4 Model Adaption

• MAGIC can learn from all analyst feedback in its representation module, but the detection module accepts only benign feedback and discounts older embeddings as the store grows.The authors recommend adapting with confirmed false positives.Source: §4.4 · p. 8

5 Implementation

• MAGIC is implemented in Python with NetworkX, PyTorch and DGL, and Scikit-learn for its detection module.The implementation comprises about 3,500 lines of code and includes parsers for StreamSpot, Camflow, and CDM audit-log formats.Source: §5 · p. 8
• Experiments use a three-layer graph encoder, a 0.5 mask rate, k=10 neighbors, and a 0.001 learning rate.The feature-reconstruction scaling factor γ is 3, and weight decay is 5 × 10^-4.Source: §5 · p. 8
• The embedding dimension is 256 for batched-log detection and 64 for entity-level detection; the threshold is selected by linear search on each dataset.Source: §5 · p. 8

6.1 Experimental Settings

• The benchmarks cover simulated StreamSpot and Wget batched-log detection and real-world DARPA E3 entity detection, with benign-only training.StreamSpot has no labels for log entries or system entities; DARPA E3 includes 51.69GB of audit records across three sub-datasets.Source: §6.1 · p. 9

6.2 Effectiveness

• StreamSpot’s single-activity batches separate into six scenarios; on Wget, MAGIC achieves 98.01% precision and 96.00% recall, recovering 24 of 25 attacks with 0.5 false positives.The StreamSpot embedding visualization shows six scenario categories; Wget’s stealthy attacks are harder to distinguish from benign behavior.Source: §6.2 · pp. 9–10, Figure 6 · p. 10
• On DARPA, MAGIC achieves 99.91% recall and 0.15% false positive rate using benign-only training, despite an imbalanced test set.Of 1,386,046 test entities, 106,246 are labeled malicious.Source: §6.2 · p. 10
• MAGIC outperformed unsupervised Unicorn and ThreaTrace across the compared datasets and trained 51 times faster than ShadeWatcher on E3-Trace.The comparison excludes methods requiring a priori attack information because they use a different detection scenario.Source: Table 4 · p. 10, §6.2 · pp. 10–11

6.3 False Positive Analysis

• Adapting on benign feedback consistently reduces false positives, with further reductions when true negatives are also fed to the model.The graph representation module can be retrained with additional data.Source: §6.3 · p. 11

6.4 Performance Overhead

• MAGIC trains 51 times faster than ShadeWatcher on E3-Trace; CPU-only use takes two minutes to detect and adapt to the daily 1.37GB of logs.Graph construction and outlier detection are unaffected by CPU-only operation, though training becomes slower.Source: §6.4 · pp. 11–12

6.5 Ablation Study

• Masked feature reconstruction slightly boosts performance and cuts training time; sampled structure reconstruction accelerates training without performance loss, while larger embeddings and more GAT layers cost more compute.The component comparison is conducted on the difficult Wget dataset.Source: §6.5 · p. 12
• A 0.5 mask rate performs best; lower detection thresholds trade more false positives for recall, while score separation makes precise threshold selection less critical.The paper reports that most malicious entities have high anomaly scores, with little overlap with benign entities.Source: §6.5 · p. 12

• Incomplete training coverage of up-to-date benign behaviors can generate many false positives, and KNN detection takes 13.8 minutes for 684,111 targets—99% of inference time.The authors note that cluster-based methods or approximate KNN search may better suit huge datasets, but leave these improvements for future work.Source: §7 · p. 12
• Attackers who learn MAGIC’s details might devise attacks to infiltrate the detector, although the paper reports a robustness analysis in Appendix A.Source: §7 · p. 12
• Designing and defending against adversarial attacks on input graphs and GNNs remains an open research topic as graph-based approaches grow more capable.Source: §7 · p. 13

• APT detectors are grouped into rule-based methods that use prior attack knowledge [3] [4] [5], statistics-based methods, and learning-based methods [10] [13] [17] [45].Source: §8 · p. 13
• Sequence-based methods detect execution or workflow patterns, while graph-based methods model entities and interactions with GNNs [10] [17] [45].Source: §8 · p. 13
• Graph auto-encoders use feature and structure reconstruction for self-supervised embeddings [25] [27], while graph masked auto-encoders use masked feature reconstruction [19].Earlier graph auto-encoders focus on link prediction and graph clustering, rather than MAGIC’s application.Source: §8 · p. 13
• Outlier detection treats objects outside an ordinary distribution as anomalies; traditional methods include One-class SVM, Isolation Forest, and Local Outlier Factor.Source: §8 · p. 13

• MAGIC models benign system behaviors from raw audit logs with masked graph representation learning and performs multi-granularity APT detection via outlier detection.Source: §9 · p. 13
• Evaluations on three widely used datasets under various detection scenarios report promising detection results, low false-positive rates, and minimum computation overhead.Source: §9 · p. 13
• The conclusion presents MAGIC as a universally applicable APT detection approach that operates with little overhead.Source: §9 · p. 13

A Analysis on Adversarial Attack

• 0.057 AUC reduction followed manipulation of 161,029 benign entities in BFP; MFE had almost no impact, while structure evasion was slightly more damaging.The evaluated strategies were MFE, MSE, their combination MCE, and BFP.Source: Table 7 · p. 16, A Analysis on Adversarial Attack · p. 16

B Time and Space Complexity of MAGIC

• MAGIC’s overall training and inference time is O(N*logN*d*k + E*d^2*l*r + (N + E)*t), with overall space complexity O((N + E)*(t + d)).The detection module takes O(logN*d*k) time per target; memory use depends largely on d and t.Source: B Time and Space Complexity of MAGIC · pp. 16–17

C Case Study

• Malicious system entities received anomaly scores of 3598.58–6802.93, exceeding the 3000 detection threshold; benign entities scored 0.01–1636.34, and MAGIC detected the malicious entities with no false alarm.Source: C Case Study · p. 17

D Hyper-parameter Choice Guideline

• On E3-Trace, θ=1980 yielded 0.99985 recall with FPR below 1%, while θ up to 6600 retained recall above 99%.The paper reports wide threshold ranges and relatively flat curves, so precise per-dataset threshold selection is unnecessary.Source: D Hyper-parameter Choice Guideline · p. 17

E Noise Reduction

• MAGIC preserves irrelevant nodes and repeated-behavior nodes: irrelevant nodes inform benign behavior, while duplicates affect neighboring nodes’ embeddings.Source: E Noise Reduction · p. 17

F Auto-encoder Based Anomaly Detection

• Auto-encoder reconstruction errors are unsuitable here because sampled structure reconstruction has high-variance per-sample loss, and batched log embeddings lack reconstruction targets.Source: F Auto-encoder Based Anomaly Detection · p. 18

G Entity-level Data Labeling on DARPA TC datasets

• The labeling process was repeated on E3-Trace, E3-THEIA, and E3-CADETS, addressing the effort required to label attack-relevant entities in difficult-to-read ground-truth documents.The methodology follows a prior successful labeling attempt on E3-Trace.Source: G Entity-level Data Labeling on DARPA… · p. 18
• The process extracts process, file, and netflow entities from log entries and obtains their semantic names from dataset fields.For E3-Trace, process names are stored in Subject.properties.map.name.Source: G Entity-level Data Labeling on DARPA… · p. 18
• Key entities mined from ground-truth documents are matched to extracted entities, then neighborhood exploration identifies additional attack-involved entities labeled positive.The approach also uses a well-recorded attack with the same strategy when another attack is poorly recorded.Source: G Entity-level Data Labeling on DARPA… · p. 18
• E3-Trace ground truth covers Browser Extension and Pine Backdoor attacks, including attacker communication, sensitive-information scanning, and local-network postscanning.The Pine Backdoor attempt followed execution of the phishing executable tcexec.Source: G Entity-level Data Labeling on DARPA… · p. 18
• E3-THEIA ground truth covers Firefox Backdoor, Browser Extension, and Pine Backdoor attempts; the Pine attempt stopped after a missing-library error.The attack graph for E3-THEIA is shown in Figure 12.Source: G Entity-level Data Labeling on DARPA… · p. 18, Figure 12 · p. 18
• E3-CADETS ground truth describes Nginx Backdoor attacks involving privileged malicious processes, attempted sshd infection, host crash, and later portscanning.The E3-CADETS attack graph is shown in Figure 13.Source: G Entity-level Data Labeling on DARPA… · p. 18, Figure 13 · p. 18