Technical Summary: The Needle is a Thread: Finding Planted Paths in Noisy Process Trees

1. Problem Definition

The paper addresses the "planted path" problem, a mathematical challenge defined as recovering a small, meaningful sequence (a path) embedded within a large, noisy, labelled directed acyclic graph (DAG). While the problem has theoretical analogs in the "planted clique" and "planted structure" literature, this work focuses on practical applications in cybersecurity, specifically within process trees.

In this context, the goal is to identify the sequence of processes executed by an attacker (the "planted path") buried within the massive, noisy logs of compromised computers. The challenge lies in the fact that:

• The total volume of log data is enormous.
• Naive heuristics produce too many "suspicious" lines for human inspection.
• The true malicious sequence is often a small fraction of the total tree and is obscured by noise (missing events, false positives, and irrelevant background processes).
• The full event may not strictly exist as a single contiguous path in the observed data.

The authors argue that while the planted path abstraction is imperfect for real-world data, extracting partial paths serves as a critical "signal-aggregation" step to boost the signal of bad sequences and filter noise.

2. Methodology

2.1 Fuzzy Matching Algorithm (Algorithm 1)

The core contribution is a dynamic programming algorithm designed to compute a feature-based similarity score between two trees, $G$ and $H$.

• Input: Two directed trees with nodes labeled by features from a set $S$, and a weight function $w$ quantifying the similarity between any two features.
• Mechanism: The algorithm uses a bottom-up tabulation approach (avoiding recursion) to find the optimal matching of nodes $(u_1, v_1), \dots, (u_k, v_k)$ such that the sequence respects the parent-child ordering in both trees ($u_i <_G u_{i+1}$ and $v_i <_H v_{i+1}$).
• Scoring: The score of a matching is the sum of weights $w(\phi_G(u_i), \phi_H(v_i))$. The algorithm maximizes this score to find the best "fuzzy" alignment.
• Complexity: The time complexity is polynomial, $O(nm)$, where $n$ and $m$ are the number of nodes in the respective trees.
• Output: The algorithm returns the sequence of matched nodes and the maximum score. It can be configured to return the single best path or adapted for "top-K" paths.

2.2 Workflows

The authors propose using Algorithm 1 as a building block for larger machine-learning workflows:

• Unsupervised Clustering (Algorithm 2):

  • Goal: Identify unknown templates within a collection of large graphs.
  • Process:
    1. Compute pairwise similarity scores between all trees in a dataset using Algorithm 1.
    2. Convert the similarity matrix into a distance matrix using a specific normalization (Eq. 5).
    3. Embed the trees into a low-dimensional space (using UMAP).
    4. Cluster the embeddings (using HDBSCAN).
    5. Apply a Multiple Sequence Alignment (MSA) approach to the best-matched sequences within clusters to extract representative "exemplars."

• Feature Augmentation for Classifiers (Section 3.2):

  • Goal: Improve classification of trees (e.g., benign vs. malicious).
  • Process: Use a set of known templates (e.g., known attack sequences) to generate auxiliary features for each observed tree. The feature $X_{i,j}$ represents the length of the longest common path (or the score) between tree $G_i$ and template $T_j$. These features are then fed into standard classifiers (e.g., Random Forest).

2.3 Synthetic Data Generation

To validate the approach, the authors introduce a data-generating process (Algorithms 3 and 4) analogous to the Stochastic Block Model (SBM) but tailored for trees:

• Tree Generation: Uses a Galton-Watson process to generate "bushy" trees.
• Planted Path: A specific sequence of labels is planted into a random path within the tree.
• Noise Model: Labels in the planted path are subject to observation probability $p$ (subsampling) and error probability (re-sampling). Other nodes are labeled uniformly from an alphabet.
• Design Goal: The model ensures that trivial algorithms (like counting label frequencies) fail, as the distribution of labels is independent of the planted path class, forcing the algorithm to rely on structural path information.

3. Key Results

3.1 Synthetic Experiments

• Distinguishability: The similarity score derived from Algorithm 1 successfully distinguished between trees containing a planted path and those without, even when the path was a small fraction of a large tree and observed at a low rate ($p=0.75$).
• Clustering: In unsupervised settings with 4 classes, the embedding workflow (Algorithm 2) successfully separated ground-truth clusters.
• Weighting Impact: Experiments showed that using a probability-weighted score function (down-weighting rare symbols) significantly improved cluster separation compared to an unweighted binary score, particularly when the alphabet contained rare symbols.

3.2 Real-World Application (ACME4 Dataset)

The authors applied their methods to the ACME4 dataset, a cybersecurity dataset simulating a Windows business network with various attacks.

• Data Scale: The dataset contained over 1.1 million process trees (mostly size 2) and nearly 3 million nodes. Only 8 trees contained "bad" (malicious) users.
• Sub-tree Construction: To overcome the prevalence of small trees, the authors constructed 2,693 sub-trees (size 3–9,558) from larger process trees.
• Matching Results:
  • Using a reference tree containing a "bad" user, the algorithm successfully identified matching paths in other trees.
  • Scoring Flexibility: The authors demonstrated that different scoring functions (exact match on process names vs. soft matching on process names and usernames) yielded different but meaningful results. For instance, a "soft" match could identify a path where the process sequence was identical but the username was slightly different (e.g., "user88" vs. "bad3").
• Workflow Performance:
  • Filtering: When used as a filter to select trees sharing paths with known templates, the method successfully isolated a subset of trees with higher scores, which correlated with larger tree sizes and specific process sequences (e.g., winlogon.exe $\to$ cmd.exe).
  • Classification: A Random Forest classifier trained on features derived from path matching (length of common paths against 38 templates) achieved high accuracy in classifying trees based on their root process names, with only minor confusion between bash.exe and cmd.exe.

4. Significance and Claims

The paper positions itself as an exploratory work demonstrating that path extraction is both feasible and useful for real cybersecurity data.

• Practical Utility: The authors claim that while the "planted path" problem is an abstraction, the proposed algorithm effectively aggregates signals from related events, filtering out the vast majority of noise that would overwhelm human experts.
• Modest Scope: The authors explicitly state that this is a preliminary study. They acknowledge that the current work does not provide statistically optimal solutions for specific clean versions of the problem but rather focuses on developing realistic models for "messy" data.
• Future Work: The paper notes that a future version will provide more details on realistic machine learning workflows, comparisons to other algorithms on real datasets, and basic theoretical analysis.
• Limitations: The authors admit that in real data, the full event might not be strictly contained in a single path, and the noisiness of observations may prevent observing a full planted path. However, they argue that even imperfect filtering boosts the signal of malicious sequences.

In summary, the paper introduces a fuzzy matching algorithm as a foundational tool for recovering meaningful sequences from noisy process trees, validating its efficacy through synthetic models and demonstrating its potential as a feature generator and filter in real-world cybersecurity triage.