Résumé Technique : L'aiguille est un fil : Trouver des chemins plantés dans des arbres de processus bruités

1. Définition du Problème

Le document traite du problème du « chemin planté » (planted path), un défi mathématique défini par la récupération d'une séquence courte et significative (un chemin) enfouie au sein d'un grand graphe orienté acyclique (DAG) étiqueté et bruité. Bien que le problème présente des analogues théoriques dans la littérature sur le « clique plantée » et la « structure plantée », ce travail se concentre sur des applications pratiques en cybersécurité, plus précisément au sein des arbres de processus.

Dans ce contexte, l'objectif est d'identifier la séquence de processus exécutés par un attaquant (le « chemin planté ») dissimulée dans les journaux massifs et bruités de serveurs compromis. Le défi réside dans le fait que :

• Le volume total de données de journaux est énorme.
• Les heuristiques naïves produisent trop de lignes « suspectes » pour une inspection humaine.
• La véritable séquence malveillante est souvent une infime fraction de l'arbre total et est obscurcie par le bruit (événements manquants, faux positifs et processus d'arrière-plan non pertinents).
• L'événement complet peut ne pas exister strictement sous la forme d'un chemin contigu unique dans les données observées.

Les auteurs soutiennent que, bien que l'abstraction du chemin planté soit imparfaite pour les données réelles, l'extraction de chemins partiels constitue une étape critique d'« agrégation de signal » pour amplifier le signal des séquences malveillantes et filtrer le bruit.

2. Méthodologie

2.1 Algorithme de Correspondance Floue (Algorithme 1)

La contribution centrale est un algorithme de programmation dynamique conçu pour calculer un score de similitude basé sur les caractéristiques entre deux arbres, $G$ et $H$.

• Entrée : Deux arbres orientés dont les nœuds sont étiquetés par des caractéristiques issues d'un ensemble $S$, et une fonction de poids $w$ quantifiant la similitude entre deux caractéristiques.
• Mécanisme : L'algorithme utilise une approche de tabulation par remontée (évitant la récursion) pour trouver l'appariement optimal de nœuds $(u_1, v_1), \dots, (u_k, v_k)$ de telle sorte que la séquence respecte l'ordre parent-enfant dans les deux arbres ($u_i <_G u_{i+1}$ et $v_i <_H v_{i+1}$).
• Scoring : Le score d'un appariement est la somme des poids $w(\phi_G(u_i), \phi_H(v_i))$. L'algorithme maximise ce score pour trouver le meilleur alignement « flou ».
• Complexité : La complexité temporelle est polynomiale, $O(nm)$, où$n$ et $m$ sont le nombre de nœuds dans les arbres respectifs.
• Sortie : L'algorithme renvoie la séquence des nœuds appariés et le score maximum. Il peut être configuré pour renvoyer le meilleur chemin unique ou adapté pour des approches « Top-K ».

2.2 Flux de Travail (Workflows)

Les auteurs proposent d'utiliser l'Algorithme 1 comme brique élémentaire pour des flux de travail d'apprentissage automatique plus larges :

• Clustering Non Supervisé (Algorithme 2) :

  • Objectif : Identifier des modèles (templates) inconnus au sein d'une collection de grands graphes.
  • Processus :
    1. Calculer les scores de similitude par paires entre tous les arbres d'un jeu de données en utilisant l'Algorithme 1.
    2. Convertir la matrice de similitude en une matrice de distance en utilisant une normalisation spécifique (Éq. 5).
    3. Plonger (embed) les arbres dans un espace de faible dimension (en utilisant UMAP).
    4. Clustériser les plongements (en utilisant HDBSCAN).
    5. Appliquer une approche d'alignement de séquences multiples (MSA) aux meilleures séquences appariées au sein des clusters pour extraire des « exemplaires » représentatifs.

• Augmentation de Caractéristiques pour Classificateurs (Section 3.2) :

  • Objectif : Améliorer la classification des arbres (ex: bénins vs malveillants).
  • Processus : Utiliser un ensemble de modèles connus (ex: séquences d'attaque connues) pour générer des caractéristiques auxiliaires pour chaque arbre observé. La caractéristique $X_{i,j}$ représente la longueur du plus long chemin commun (ou le score) entre l'arbre $G_i$ et le modèle $T_j$. Ces caractéristiques sont ensuite injectées dans des classificateurs standards (ex: Forêt Aléatoire).

2.3 Génération de Données Synthétiques

Pour valider l'approche, les auteurs introduisent un processus de génération de données (Algorithmes 3 et 4) analogue au Modèle de Blocs Stochastiques (SBM) mais adapté aux arbres :

• Génération d'Arbres : Utilise un processus de Galton-Watson pour générer des arbres « touffus ».
• Chemin Planté : Une séquence spécifique d'étiquettes est implantée dans un chemin aléatoire au sein de l'arbre.
• Modèle de Bruit : Les étiquettes du chemin planté sont soumises à une probabilité d'observation $p$ (sous-échantillonnage) et une probabilité d'erreur (ré-échantillonnage). Les autres nœuds sont étiquetés uniformément à partir d'un alphabet.
• Objectif de Conception : Le modèle garantit que les algorithmes triviaux (comme le comptage de la fréquence des étiquettes) échouent, car la distribution des étiquettes est indépendante de la classe du chemin planté, forçant l'algorithme à s'appuyer sur l'information structurelle du chemin.

3. Résultats Clés

3.1 Expériences Synthétiques

• Distinguabilité : Le score de similitude dérivé de l'Algorithme 1 a réussi à distinguer les arbres contenant un chemin planté de ceux n'en contenant pas, même lorsque le chemin était une petite fraction d'un grand arbre et observé à un taux faible ($p=0,75$).
• Clustering : Dans des contextes non supervisés avec 4 classes, le flux de travail d'embedding (Algorithme 2) a réussi à séparer les clusters de vérité terrain.
• Impact de la Pondération : Les expériences ont montré que l'utilisation d'une fonction de score pondérée par probabilité (réduisant le poids des symboles rares) améliorait considérablement la séparation des clusters par rapport à un score binaire non pondéré, particulièrement lorsque l'alphabet contenait des symboles rares.

3.2 Application au Monde Réel (Jeu de données ACME4)

Les auteurs ont appliqué leurs méthodes au jeu de données ACME4, un ensemble de données de cybersécurité simulant un réseau d'entreprise Windows avec diverses attaques.

• Échelle des Données : Le jeu de données contenait plus de 1,1 million d'arbres de processus (majoritairement de taille 2) et près de 3 millions de nœuds. Seuls 8 arbres contenaient des utilisateurs « mauvais » (malveillants).
• Construction de Sous-arbres : Pour surmonter la prévalence des petits arbres, les auteurs ont construit 2 693 sous-arbres (taille 3–9 558) à partir d'arbres de processus plus larges.
• Résultats d'Appariement :
  • En utilisant un arbre de référence contenant un utilisateur « mauvais », l'algorithme a réussi à identifier des chemins correspondants dans d'autres arbres.
  • Flexibilité du Scoring : Les auteurs ont démontré que différentes fonctions de score (correspondance exacte sur les noms de processus vs correspondance souple sur les noms de processus et les noms d'utilisateurs) produisaient des résultats différents mais significatifs. Par exemple, une correspondance « souple » pouvait identifier un chemin où la séquence de processus était identique mais le nom d'utilisateur légèrement différent (ex: « user88 » vs « bad3 »).
• Performance du Flux de Travail :
  • Filtrage : Utilisé comme filtre pour sélectionner les arbres partageant des chemins avec des modèles connus, la méthode a réussi à isoler un sous-ensemble d'arbres présentant des scores plus élevés, lesquels corrélaient avec des tailles d'arbres plus grandes et des séquences de processus spécifiques (ex: winlogon.exe $\to$ cmd.exe).
  • Classification : Un classificateur de type Forêt Aléatoire entraîné sur des caractéristiques dérivées de l'appariement de chemins (longueur des chemins communs contre 38 modèles) a atteint une grande précision dans la classification des arbres selon le nom de leur processus racine, avec une confusion mineure entre bash.exe et cmd.exe.

4. Signification et Revendications

Le papier se positionne comme un travail exploratoire démontrant que l'extraction de chemins est à la fois faisable et utile pour des données de cybersécurité réelles.

• Utilité Pratique : Les auteurs affirment que, bien que le problème du « chemin planté » soit une abstraction, l'algorithme proposé agrège efficacement les signaux d'événements liés, filtrant la vaste majorité du bruit qui submergerait les experts humains.
• Portée Modeste : Les auteurs précisent explicitement qu'il s'agit d'une étude préliminaire. Ils reconnaissent que le présent travail ne fournit pas de solutions statistiquement optimales pour des versions « propres » du problème, mais se concentre plutôt sur le développement de modèles réalistes pour des données « désordonnées ».
• Travaux Futurs : Le papier note qu'une version ultérieure fournira plus de détails sur les flux de travail d'apprentissage automatique réalistes, des comparaisons avec d'autres algorithmes sur des jeux de données réels, ainsi qu'une analyse théorique de base.
• Limites : Les auteurs admettent que dans les données réelles, l'événement complet peut ne pas être strictement contenu dans un seul chemin, et que le bruit des observations peut empêcher l'observation d'un chemin planté complet. Cependant, ils soutiennent que même un filtrage imparfait amplifie le signal des séquences malveillantes.

En résumé, le papier introduit un algorithme de correspondance floue comme outil fondamental pour récupérer des séquences significatives à partir d'arbres de processus bruités, validant son efficacité via des modèles synthétiques et démontrant son potentiel en tant que générateur de caractéristiques et filtre dans le triage de la cybersécurité réelle.