Théorie des graphes en cybersécurité

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. Pourquoi les questions de sécurité sont des questions de graphes

Un scanner de vulnérabilités produit une liste. Il vous dit que cet hôte utilise une bibliothèque obsolète, que celui-là expose une interface d'administration, qu'un troisième a un compte de service faible. Chaque élément reçoit une sévérité, la liste est triée, et le haut de la liste est corrigé.

Les attaquants ne lisent pas cette liste comme les défenseurs. Une intrusion est une séquence : une tête de pont quelque part sans importance, un identifiant récupéré là, un service qui fait confiance à cet identifiant, un partage qui fait confiance à ce service, et finalement quelque chose qui compte. Chaque étape peut être anodine prise isolément. La combinaison, c'est la brèche.

Cette différence est exactement celle qui sépare un ensemble d'un graphe. Une liste de faiblesses n'a pas de structure ; un ensemble de faiblesses plus les transitions entre elles forme un graphe orienté, et dès qu'il existe, les questions qui intéressent les défenseurs deviennent des algorithmes classiques. Quelle route est la plus facile ? Plus court chemin. Quels contrôles coupent toutes les routes ? Coupe minimale. Qu'atteint une compromission ? Accessibilité. Quand un logiciel malveillant cesse-t-il de s'éteindre tout seul ? La plus grande valeur propre de la matrice d'adjacence.

L'idée n'est pas nouvelle dans la littérature. Phillips et Swiler ont proposé l'analyse de vulnérabilités fondée sur les graphes en 1998, Sheyner et ses collègues ont automatisé la génération de graphes d'attaque par model checking en 2002, et l'approche est standard en recherche depuis. Ce qui est nouveau, c'est que les outils ont enfin rattrapé leur retard : les parcs actuels sont trop grands pour que quiconque garde les chemins en tête, et des graphes de cette taille se résolvent en millisecondes.

Chaque nombre de cet article a été calculé en résolvant le modèle, pas estimé. Si le vocabulaire des graphes vous est étranger, l'introduction à la théorie des graphes couvre les définitions utilisées ici.

2. Le graphe d'attaque : nœuds, arcs et poids

Trois décisions de modélisation portent tout le poids, et chacune comporte un compromis honnête.

Qu'est-ce qu'un nœud ? Le choix utile le plus simple est un hôte, et c'est ce qu'utilise cet article. Les modèles de recherche sont souvent plus fins : un nœud est un état, une paire formée d'une machine et d'un niveau de privilège, de sorte que « utilisateur sur web01 » et « root sur web01 » sont des sommets différents. C'est plus fidèle et beaucoup plus gros, puisque l'espace d'états se multiplie. Il existe aussi des modèles plus grossiers, où un nœud est un sous-réseau entier. Choisissez la granularité à laquelle vos contrôles agissent, car le modèle sert à comparer des contrôles.

Qu'est-ce qu'un arc ? Une transition que l'attaquant peut effectuer : un service exploitable, une relation de confiance, un identifiant réutilisé, un partage monté, une cible d'hameçonnage. Les arcs sont orientés, car la compromission circule dans un seul sens. Un poste de travail qui monte un partage de fichiers vous donne un arc vers le partage, pas depuis lui, et se tromper de sens inverse tous les résultats.

Que met-on sur l'arc ? Au moins un nombre, et ce choix détermine ce que « plus court » veut dire :

• L'effort de l'attaquant, un score de difficulté. Le plus court chemin désigne alors l'intrusion la plus facile. Cet article utilise l'effort.
• La probabilité de réussite. Multipliez le long du chemin au lieu d'additionner, ou additionnez les logarithmes négatifs et utilisez tel quel le même algorithme de plus court chemin.
• Le coût du contrôle. Le prix de la mesure qui supprime cet arc. La coupe minimale sur ces nombres est le moyen le moins cher de couper toutes les routes, c'est la section 6.

D'où viennent les nombres ? Généralement d'un système de notation comme l'exploitabilité CVSS, calibré par quelqu'un qui connaît le parc. Ce sont des estimations, et la position honnête est que le classement est bien plus robuste que les valeurs absolues. Si vous ne pouvez pas défendre un 3 contre un 4, vous pouvez défendre qu'un exploit web public est plus facile que le vol d'un identifiant d'administrateur de domaine, et c'est cet ordre qui détermine les résultats ci-dessous.

3. Le réseau utilisé tout au long de l'article

L'exemple suivi est une petite entreprise, volontairement ordinaire. Internet atteint trois systèmes exposés : un serveur web public, une passerelle mail et un concentrateur VPN. Derrière se trouvent deux postes de travail et un serveur d'application, puis un serveur de fichiers et une base de données, et enfin le contrôleur de domaine, que veut l'attaquant.

Chacun des seize arcs porte un score d'effort et un coût de contrôle. Les scores d'effort disent qu'exploiter l'application web publique coûte 3, qu'un appel de service interne de la DMZ vers la couche applicative coûte 2, et que voler les identifiants d'administrateur de domaine en cache sur un poste de travail coûte 8, ce qui est difficile mais pas impossible. Ces jugements relatifs sont la seule vraie entrée du modèle.

Une remarque structurelle avant de lancer le moindre algorithme : ce graphe n'a pas de cycle, car chaque arc fait avancer l'attaquant vers l'intérieur. Les vrais graphes d'attaque ont des cycles, puisqu'un attaquant peut pivoter dans les deux sens, et tous les algorithmes utilisés ci-dessous les gèrent. Le cas acyclique rend simplement les exemples plus faciles à vérifier à la main.

4. L'entrée la plus facile : les plus courts chemins d'attaque

La première question est celle à laquelle un pentesteur répond à la main en quinze jours : quelle est la route la plus facile d'internet au contrôleur de domaine ? Avec l'effort sur les arcs, c'est un problème de plus court chemin, et l'algorithme de Dijkstra y répond pour tous les actifs à la fois.

La réponse est internet → web01 → app01 → db01 → dc01 pour un effort total de 12. Lisez les étapes : exploiter l'application web publique (3), utiliser l'appel de service interne de confiance vers la couche applicative (2), atteindre la base de données que l'application a le droit d'interroger (3), et abuser du compte de service de la base de données contre le contrôleur de domaine (4).

Deux choses comptent davantage que le nombre dans ce résultat.

Aucune de ces quatre étapes n'est alarmante prise isolément. Une vulnérabilité d'application web notée 3 sur 10 n'arrive pas en tête d'un registre des risques. Pas plus qu'un appel de service entre deux systèmes censés se parler. La route est dangereuse en tant que composition, et aucun score de sévérité par hôte ne peut exprimer une composition. C'est l'argument fondamental en faveur des graphes d'attaque, avancé par Phillips et Swiler en 1998 et repris dans tous les articles depuis.

La route la plus facile évite les humains. L'hameçonnage est le vecteur d'accès initial le plus discuté, et ici la route d'hameçonnage vers le contrôleur de domaine coûte 14, pas 12. Le modèle ne dit pas que l'hameçonnage est sans importance ; il dit que sur ce parc, avec ces scores, le chemin par les serveurs est moins cher. Calculer l'option la moins chère pour l'attaquant plutôt que l'option la plus redoutée par le défenseur, c'est précisément à cela que sert l'algorithme.

Le même calcul donne l'effort pour atteindre chaque autre actif : web01 coûte 3, app01 coûte 5, le serveur de fichiers 8, la base de données 8. Ce sont les nombres à présenter à un comité d'audit qui veut savoir à quelle distance le périmètre se trouve réellement des joyaux de la couronne.

5. Seize façons d'entrer, et quel hôte les porte

Le chemin le moins cher est une réponse. Le bloquer n'est pas une stratégie, car l'attaquant prend simplement le suivant. La question utile est de savoir combien de routes existent et par quels actifs elles passent.

Énumérer tous les chemins simples d'internet au contrôleur de domaine sur ce graphe donne 16 routes distinctes, coûtant entre 12 et 25 avec une médiane de 18,5. Seize est un petit nombre précisément parce que l'exemple est petit ; un parc réel de quelques milliers d'hôtes compte couramment plus de chemins d'attaque qu'il n'est raisonnable d'en compter, c'est pourquoi l'énumération est un outil pédagogique et les métriques ci-dessous la technique de production.

Compter combien de ces routes passent par chaque hôte produit un classement, et ce n'est pas celui que donnerait un rapport de périmètre.

Le serveur de fichiers se trouve sur 12 des 16 routes, les trois quarts. Le serveur web public, la machine la plus scrutée de la plupart des organisations, se trouve sur 3. Rien dans le serveur de fichiers n'attirerait l'attention lors d'un scan externe : il n'est pas exposé, il n'exécute rien d'exotique et il existe pour stocker des documents. Il est critique à cause de sa place dans le graphe, et seul un graphe peut le dire.

L'énumération est aussi le point où cette approche cesse de passer à l'échelle, et il vaut la peine de voir pourquoi. Seize routes sortent de dix hôtes et seize arcs. Ajoutez un second serveur de fichiers que les deux postes peuvent atteindre et le nombre double à peu près ; un parc réel de quelques milliers de machines avec un réseau interne à plat a un nombre de chemins comptant plus de chiffres que quiconque n'en lira jamais. Les métriques ci-dessous évitent toutes l'énumération, et c'est ce qui les rend utilisables sur un vrai réseau.

Cette mesure est une cousine, propre à la sécurité, de la centralité d'intermédiarité, introduite par Freeman en 1977, qui compte la fraction des plus courts chemins passant par un sommet. L'intermédiarité sur toutes les paires est la mesure standard de la science des réseaux, calculable en O(nm) par l'algorithme de Brandes. Pour la défense, compter les chemins entre la paire précise qui compte, le point d'entrée de l'attaquant et l'actif qui vous importe, est généralement plus exploitable : cela répond à « si je durcis une machine, combien de routes je perturbe » plutôt qu'à « à quel point est-elle centrale en général ».

Noel et Jajodia ont fait le même raisonnement pour le placement des sondes en 2008 : placez la détection là où les chemins d'attaque se concentrent, pas là où les actifs ont le plus de valeur, car les points de concentration offrent la meilleure couverture par sonde.

6. Couper toutes les routes : la coupe minimale

Classer les hôtes vous dit où regarder. La question plus forte est de savoir quel ensemble de contrôles couperait toutes les routes à la fois, et pour combien peu.

Attribuez à chaque arc le coût du contrôle qui le supprime, puis calculez la coupe minimale entre internet et le contrôleur de domaine. Le théorème flot maximum coupe minimum garantit que l'ensemble le moins cher est exactement la coupe minimale, et l'algorithme la renvoie en temps polynomial. La même mécanique est traitée dans flots dans les réseaux, flot maximum et coupe minimale.

La réponse est trois contrôles totalisant 7 : empêcher le serveur web de la DMZ d'appeler la couche applicative (3), empêcher l'exécution des pièces jointes sur les postes de travail (2), et faire arriver les utilisateurs VPN dans un segment restreint plutôt qu'à côté des postes (2). Réénumérer les chemins après les avoir appliqués renvoie zéro.

Remarquez où tombe la coupe. Les trois contrôles se situent à la frontière entre le périmètre et l'intérieur, et aucun ne touche le contrôleur de domaine, la base de données ou le serveur de fichiers. L'instinct qui pousse à durcir d'abord les joyaux de la couronne n'est pas ce que recommandent les mathématiques : la correction complète la moins chère se trouve au point le plus étroit du graphe, et ici c'est le premier pas vers l'intérieur.

La même question, pour des machines plutôt que des liens, utilise l'astuce du dédoublement des nœuds. Remplacez chaque hôte par une copie d'entrée et une copie de sortie reliées par un arc de capacité 1, donnez une capacité infinie aux vrais arcs, et la coupe minimale compte alors des hôtes au lieu de liens. La réponse ici est 3 hôtes : web01, mail01 et vpn, exactement les trois qui font face à internet. Sur un petit exemple, c'est une vérification rassurante ; sur un grand, c'est un calcul réellement utile, car l'ensemble équivalent y est rarement évident.

7. Ce qu'un seul contrôle apporte vraiment

Les budgets financent rarement trois contrôles à la fois, donc la question pratique est de savoir lequel acheter en premier. Supprimer chaque arc tour à tour et relancer la résolution donne une réponse, et elle a de quoi refroidir.

Le meilleur contrôle unique fait passer l'effort de l'attaquant de 12 à 14. C'est tout. Aucune mesure isolée sur ce réseau n'apporte plus de deux points de difficulté, car le graphe est richement connecté et l'attaquant se rabat simplement sur la route suivante la moins chère. C'est la version quantitative d'une vérité bien connue en sécurité : la défense en profondeur n'est pas un slogan, c'est une conséquence du fait que des coupes isolées dans un graphe dense font très peu.

Le tableau montre aussi que la métrique choisie change le classement. Bloquer la transition de la passerelle mail vers le poste de travail divise par deux le nombre de routes, de 16 à 8, et laisse totalement intacte la route la plus facile de l'attaquant, à 12. Si votre conseil d'administration suit les « chemins d'attaque éliminés », vous qualifierez ce contrôle de succès ; s'il suit « l'effort de l'attaquant », vous le qualifierez d'inutile. Les deux nombres sont réels, ils mesurent des choses différentes, et n'en citer qu'un est la façon dont les programmes de sécurité finissent par optimiser la mauvaise grandeur.

Le meilleur rapport qualité-prix du tableau consiste à bloquer la route de la base de données vers le contrôleur de domaine : coût 5, effort porté à 14 et routes ramenées à 7. C'est le seul contrôle qui améliore sensiblement les deux métriques, ce qu'aucune intuition n'aurait permis d'identifier.

8. Rayon d'impact : ce qu'atteint une compromission

Les chemins d'attaque demandent comment un intrus entre. La question complémentaire est ce qui se passe une fois qu'il est quelque part, et c'est un simple calcul d'accessibilité : depuis un hôte compromis, quels actifs peut-on finir par atteindre ? Un parcours par hôte y répond en temps linéaire.

Le classement inverse celui de l'exposition. Le serveur web public, la machine la plus exposée du parc, atteint 4 actifs. La passerelle mail en atteint 6. Un poste de travail en atteint 5. L'exposition mesure qui peut vous atteindre ; le rayon d'impact mesure qui vous pouvez atteindre, et les deux produisent des listes de priorités différentes à partir du même graphe.

Le nombre qui devrait arrêter une réunion est celui-ci : neuf des dix hôtes peuvent finir par atteindre le contrôleur de domaine. Seul le contrôleur de domaine lui-même ne le peut pas, car rien ne se trouve au-delà. Sur un parc réel, ce chiffre est le résultat le plus utile de tout l'exercice, parce qu'il transforme « notre réseau est à plat » d'une opinion en une mesure.

Le rayon d'impact rend aussi les décisions de confinement gérables pendant un incident. Quand un hôte est confirmé compromis, l'ensemble des machines à examiner est son ensemble accessible en aval, et l'ensemble de celles qui ont pu l'infecter est son ensemble accessible en amont, calculé sur le graphe inversé. Les deux se calculent en un seul parcours, et tous deux sont bien plus précis que l'isolement d'un sous-réseau entier à l'instinct.

9. À quelle vitesse cela se propage : le seuil épidémique

Les rançongiciels et les vers ne suivent pas un seul chemin ; ils se propagent. Les modéliser exige une autre question : étant donné un réseau et une infection qui se transmet entre voisins et se nettoie à un certain rythme, s'éteint-elle ou envahit-elle le parc ?

La réponse est l'un des résultats les plus utiles de la science des réseaux, et elle est exacte. Pour une très large classe de modèles de propagation, le point de bascule dépend d'un seul nombre : la plus grande valeur propre de la matrice d'adjacence, notée λ₁. Une infection dont le rapport propagation sur nettoyage est inférieur à 1 / λ₁ s'éteint d'elle-même ; au-dessus, elle devient endémique. Wang, Chakrabarti, Wang et Faloutsos l'ont démontré en 2003, et Chakrabarti et ses collègues l'ont généralisé en 2008.

Sur le graphe de mouvement latéral de cet exemple, neuf hôtes et treize liens, λ₁ vaut 3,573, donc le seuil vaut 0,280. En simulant une infection à 40 % de ce rapport, en moyenne sur 600 exécutions, elle s'éteint au pas 21. À quatre fois ce rapport, elle se stabilise à 5,5 des 9 hôtes et y reste indéfiniment. Le seuil a prédit les deux issues avant qu'aucune simulation ne tourne.

Ce qui rend cela intéressant en pratique, c'est que λ₁ est une grandeur que vous pouvez modifier. Isoler le serveur de fichiers des postes de travail et de la couche applicative supprime trois liens et fait passer λ₁ de 3,573 à 2,570, ce qui relève le seuil de 0,280 à 0,389. C'est une marge 39 % plus grande : les infections qui se seraient installées s'éteignent désormais.

Deux faits rendent la valeur propre plus facile à raisonner qu'il n'y paraît. Elle se situe toujours entre le degré moyen et le degré maximal du graphe, ici entre 2,889 et 5, et 3,573 tombe bien entre les deux. Et elle est dominée par la partie la plus dense du réseau, donc le moyen le plus rapide de la faire baisser est de réduire la connectivité de l'hôte le plus connecté. C'est exactement ce que fait la segmentation ci-dessus : le serveur de fichiers a le degré 5, le plus élevé du parc, et couper trois de ses liens le ramène à 2 et fait passer le degré maximal de tout le graphe de 5 à 3. La machine la plus connectée est celle qu'il faut isoler, et le degré est un calcul d'une ligne que vous pouvez faire avant de toucher au moindre code de valeurs propres.

Cela change le regard sur la segmentation. « Segmentez le réseau » se justifie d'ordinaire par une histoire ; ici, c'est une intervention sur une grandeur calculable, avec un avant et un après. L'idée remonte à Kephart et White, qui ont construit en 1991 pour l'IEEE Security and Privacy des modèles épidémiologiques de virus informatiques sur graphes orientés, et à Staniford, Paxson et Weaver, dont l'analyse de 2002 sur la propagation des vers a montré à quelle vitesse la courbe bouge quand le graphe est dense.

10. Active Directory : le graphe que les attaquants utilisent déjà

Tout ce qui précède était un modèle construit par un défenseur. Le graphe le plus lourd de conséquences en sécurité d'entreprise existe déjà, personne ne l'a conçu délibérément, et les attaquants l'interrogent depuis des années : Active Directory.

Un environnement AD est un graphe, que quelqu'un le dessine ou non. Les utilisateurs sont des sommets, les groupes sont des sommets, les ordinateurs sont des sommets, et les arcs sont les relations que l'annuaire stocke déjà : est membre de, est administrateur de, peut réinitialiser le mot de passe de, a une session sur, est propriétaire de, a GenericWrite sur. Chacune de ces relations est une transition qu'un attaquant peut emprunter.

En 2016, Robbins, Vazarkar et Schroeder ont publié BloodHound et donné la conférence qui a nommé la technique, « Six Degrees of Domain Admin ». Son idée est exactement celle de cet article : les faits individuellement inoffensifs se composent. Un groupe de support qui peut réinitialiser les mots de passe d'un groupe contenant un utilisateur qui se trouve avoir une session active sur un serveur où un administrateur de domaine s'est connecté mardi dernier forme un chemin de quatre sauts vers la compromission totale, et aucun maillon pris isolément ne ressemble à une erreur de configuration.

BloodHound collecte ces relations et y lance une requête de plus court chemin. C'est Dijkstra, sur un graphe que personne n'avait pensé à dessiner. Le résultat a changé la pratique défensive, car les chemins qu'il révélait étaient à la fois réels et invisibles pour tous les autres outils en usage.

Trois leçons se transposent à n'importe quel environnement :

• Les données existent déjà. Les relations d'annuaire, les politiques IAM du cloud, les role bindings Kubernetes et les permissions de partage SaaS sont tous des graphes stockés dans une base de données, qui n'attendent que d'être interrogés comme tels.
• Les sessions sont aussi des arcs. Une session ouverte crée une arête temporaire de cette machine vers les privilèges de cette identité, c'est pourquoi « qui est connecté où » est une question de sécurité et non d'inventaire.
• Le nettoyage est une modification du graphe. Supprimer une seule appartenance imbriquée à un groupe peut effacer des milliers de chemins, et il est impossible de le voir sans le graphe.

11. Détection : graphes de provenance et culpabilité par association

Les graphes d'attaque servent la prévention. Deux autres techniques de graphes opèrent côté détection, et elles utilisent des graphes entièrement différents.

Les graphes de provenance enregistrent ce qui s'est réellement passé sur un système : processus, fichiers, sockets et les relations causales entre eux. Un processus lit un fichier, en écrit un autre, lance un enfant, ouvre une connexion. King et Chen ont introduit le retour arrière avec leur système BackTracker à SOSP en 2003 : à partir d'un point de détection, comme un fichier suspect, on remonte à rebours le graphe causal pour découvrir comment il est arrivé là. Le parcours en aval depuis un point d'entrée révèle les dégâts ; le parcours en amont depuis un symptôme révèle la cause racine. Ce sont deux parcours de graphe sur la même structure enregistrée.

La version moderne corrèle ces flux avec les comportements connus des attaquants. HOLMES, publié à l'IEEE Security and Privacy en 2019, associe les flux d'information suspects d'un graphe de provenance aux tactiques et techniques du cycle de vie d'une attaque et lève une alerte quand le motif des flux ressemble à une intrusion plutôt qu'à une activité ordinaire. La difficulté d'ingénierie est l'échelle : les graphes de provenance croissent de millions d'arêtes par heure sur un seul hôte chargé, ce qui fait de leur réduction et de leur interrogation efficaces tout le problème de recherche.

La culpabilité par association est la seconde technique, et c'est de l'inférence sur graphe plutôt qu'un parcours. On construit un graphe biparti de machines et de fichiers : une machine est reliée à chaque fichier qu'elle a vu. La plupart des fichiers et des machines n'ont pas d'étiquette, mais quelques-uns sont connus comme sains et quelques-uns comme malveillants. La propagation de croyances (belief propagation) diffuse alors ces étiquettes le long des arêtes, en supposant que les fichiers présents sur de nombreuses machines infectées sont suspects et que les machines contenant de nombreux fichiers malveillants sont compromises.

C'est ce que Chau, Nachenberg, Wilhelm, Wright et Faloutsos ont construit sous le nom de Polonium en 2011, sur un graphe d'environ 60 milliards d'arêtes machine-fichier issues de la télémétrie de Symantec, avec un taux de vrais positifs d'environ 85 %. La technique compte parce qu'elle ne demande ni signature ni bac à sable : un fichier que personne n'a jamais analysé peut être jugé à ses fréquentations. La même forme de calcul, un graphe biparti plus une propagation d'étiquettes, alimente la détection de fraude dans les paiements et la détection d'abus sur les plateformes sociales.

12. Le graphe de la chaîne d'approvisionnement logicielle

Le dernier graphe est celui que parcourt votre système de build. Une application moderne déclare une poignée de dépendances directes, dont chacune déclare les siennes, et la fermeture transitive atteint couramment des centaines ou des milliers de paquets. Cette fermeture est un graphe orienté acyclique, et c'est une surface d'attaque.

La question de sécurité est une question d'accessibilité. Si un paquet profond dans le graphe est compromis, lesquelles de vos applications exécutent son code ? C'est l'accessibilité en aval depuis le nœud compromis dans le graphe de dépendances inversé, et c'est la requête à laquelle chaque organisation se démène pour répondre dans la première heure d'un incident de chaîne d'approvisionnement. Les équipes qui tiennent une nomenclature logicielle (SBOM) y répondent en quelques secondes ; les autres passent des jours à coups de grep.

Deux propriétés du graphe rendent cela dangereux d'une façon qu'une liste ne révélerait pas. La profondeur cache le risque : un paquet que vous n'avez jamais choisi, trois niveaux sous un paquet que vous avez choisi, s'exécute avec les mêmes privilèges que votre propre code. La popularité le concentre : les paquets au degré entrant le plus élevé sont les cibles les plus précieuses, car en compromettre un atteint d'un coup des milliers de projets en aval, ce qui est précisément le schéma documenté dans l'étude des attaques réelles de la chaîne d'approvisionnement open source menée par Ohm, Plate, Sykosch et Meier en 2020.

Les métriques défensives utiles sont des métriques de graphe. Comptez la taille de la fermeture transitive, pas le nombre de dépendances directes. Classez les dépendances selon le nombre de vos applications qui les atteignent. Surveillez les paquets ayant un seul mainteneur et un fort degré entrant, soit exactement le profil de risque qui a produit plusieurs des incidents les plus connus. La technique est identique au calcul du rayon d'impact de la section 8, appliquée à un autre graphe.

13. Ce qui est facile, ce qui est difficile

L'analyse de graphes d'attaque a ceci d'inhabituel parmi les techniques de sécurité qu'elle a une histoire de complexité nette, et savoir de quel côté de la ligne tombe une question évite beaucoup d'efforts perdus.

Le schéma est familier : les questions sur le flot et la connexité sont bon marché, les questions sur les éléments discrets à changer sont coûteuses. L'énumération est le piège du milieu. Elle est intuitive, toutes les démonstrations la font, et le nombre de chemins simples peut croître exponentiellement avec la taille du réseau, c'est pourquoi les outils sérieux calculent des métriques sur le graphe au lieu de lister ses chemins. Ammann, Wijesekera et Kaushik ont avancé exactement cet argument en 2002 en proposant une représentation compacte et monotone qui passe à l'échelle de façon polynomiale au lieu d'énumérer.

Une métrique à connaître par son nom est la k-zero day safety, proposée par Wang, Jajodia, Singhal, Cheng et Noel en 2014. Elle demande combien de vulnérabilités inconnues distinctes un attaquant devrait exploiter pour atteindre un actif, ce qui contourne la question insoluble de la probabilité de chaque exploit. C'est une distance dans le graphe sous une autre pondération, et un bon exemple du meilleur instinct du domaine : mesurer la structure, pas la probabilité.

14. Erreurs de modélisation

Un graphe d'attaque faux est pire que pas de graphe du tout, car il produit des priorités assurées, précises et erronées. Voici les échecs qui reviennent.

• Se tromper de sens pour les arcs. Un poste de travail qui monte un partage crée un arc vers le partage. L'inverser fait paraître le serveur de fichiers sûr et le poste critique, et rien dans le résultat ne semble cassé.
• Modéliser des hôtes quand le risque tient aux identités. Si la vraie transition est un identifiant qui fonctionne à trois endroits, un arc entre deux machines ne la capture pas. C'est pourquoi le graphe Active Directory de la section 10 est un modèle à part et non un raffinement de celui-ci.
• Traiter les scores comme des mesures. Les nombres d'effort sont des jugements. Faites confiance à l'ordre, méfiez-vous de la troisième décimale, et vérifiez si la conclusion résiste à une perturbation des scores. Si le contrôle recommandé change quand un 3 devient un 4, dites-le.
• Oublier que le graphe est un instantané. Un portable qui rejoint le VPN ajoute des arcs ; un serveur décommissionné en retire ; une exception temporaire du pare-feu pendant une migration peut ouvrir une route qu'aucun schéma n'a jamais enregistrée. Un graphe d'attaque n'est à jour que dans la mesure où l'inventaire qui le sous-tend l'est.
• Énumérer les chemins sur un parc réel. Cela marche à merveille sur dix hôtes et ne termine jamais sur dix mille. Calculez plutôt des coupes, de la centralité et de l'accessibilité, qui sont toutes polynomiales.
• Ne présenter qu'une seule métrique. La section 7 a montré un contrôle qui divise par deux le nombre de chemins d'attaque sans ralentir le moins du monde l'attaquant. Publiez ensemble l'effort de l'attaquant et le nombre de routes, sinon le programme optimisera celle qui figure sur la diapositive.
• Ignorer les arcs qu'on ne peut pas supprimer. Certaines transitions sont le métier lui-même : l'application doit interroger la base de données. Le modèle devrait les marquer comme fixes, pour que l'optimiseur cesse de proposer des contrôles qui ne seront jamais approuvés.

15. Du modèle à la pratique

Quatre choses séparent un schéma qui impressionne en réunion d'un modèle qui change les décisions.

Construisez le graphe à partir de données que vous avez déjà. Les jeux de règles de pare-feu, les définitions de groupes de sécurité cloud, les résultats de scans de vulnérabilités, les relations Active Directory et la télémétrie EDR décrivent tous des arêtes. Un modèle assemblé à la main en atelier est périmé la semaine suivante ; un modèle généré à partir de la configuration est régénéré chaque nuit.

Commencez par l'accessibilité, pas par les chemins d'attaque. Le résultat utile le moins cher est le tableau du rayon d'impact de la section 8, car il n'exige aucune notation d'exploit, seulement la connectivité. « Neuf de nos dix hôtes peuvent atteindre le contrôleur de domaine » est un constat qui porte, et vous pouvez le produire avant que quiconque ne discute de CVSS.

Utilisez les outils qui existent. MulVAL, le générateur de graphes d'attaque évolutif publié par Ou, Boyer et McQueen en 2006, reste l'implémentation de référence en recherche. BloodHound couvre le graphe des identités. NetworkX ou une base de données orientée graphe s'occupe de l'analyse une fois les arêtes disponibles. Aucun des algorithmes de cet article n'est à écrire de zéro, et les chapitres sur les graphes de n'importe quel manuel d'algorithmique couvrent ceux qui le seraient.

Relancez la résolution plutôt que de débattre. Chaque affirmation de cet article a été tranchée par le modèle en quelques millisecondes : que la route la plus facile évite les postes de travail, que le serveur de fichiers porte quatre fois plus de routes que le serveur web, que le meilleur contrôle unique apporte deux points d'effort, que la segmentation relève le seuil épidémique de 39 %. L'intuition sur les réseaux est peu fiable justement dans les cas qui comptent, et toute la valeur du graphe est de ne plus en avoir besoin.

16. Pour aller plus loin

Le moyen le plus rapide d'intérioriser ce contenu est de construire un graphe plutôt que de lire à son sujet, et la barrière est plus basse qu'elle n'en a l'air. Dix hôtes et seize arcs, tout ce qu'a utilisé cet article, tiennent dans un fichier texte, et chaque résultat ci-dessus est sorti de quelques dizaines de lignes de code ordinaire.

Un ordre raisonnable pour apprendre les briques : familiarisez-vous avec le parcours en largeur et en profondeur, puisque l'accessibilité et le rayon d'impact ne sont qu'un parcours assorti de comptabilité. Puis les algorithmes de plus court chemin, qui vous donnent l'analyse de la route la plus facile et, avec des logarithmes négatifs sur les arcs, celle de la route la plus probable. Puis le flot maximum et la coupe minimale, qui forment tout le contenu des sections 6 et 7 et constituent le résultat le plus sous-utilisé de la sécurité défensive.

Ensuite, la direction utile est structurelle plutôt qu'algorithmique : la distinction entre graphes orientés et non orientés tranche un nombre surprenant de débats de modélisation, et la représentation des graphes décide si votre analyse prend une seconde ou une heure une fois le parc devenu grand. Les frontières de complexité de la section 13 sont présentées de façon plus générale dans algorithmes de graphes et complexité.

Si vous préférez partir du côté sécurité, le chemin le plus court vers un vrai résultat est d'exporter vos relations Active Directory et de les interroger, car ce graphe existe déjà et personne n'a eu à le modéliser. Le constat qui suit est généralement celui sur lequel se termine cet article : le nombre de machines qui peuvent finir par atteindre le contrôleur de domaine est bien plus élevé que quiconque dans la salle ne l'imaginait.

18. Références

Les articles qui ont établi ces techniques, par ordre chronologique.

1. Ford, L. R. et Fulkerson, D. R. (1956). “Maximal flow through a network.” Canadian Journal of Mathematics, 8, 399–404.
2. Freeman, L. C. (1977). “A set of measures of centrality based upon betweenness.” Sociometry, 40(1), 35–41.
3. Kephart, J. O. et White, S. R. (1991). “Directed-graph epidemiological models of computer viruses.” Proceedings of the IEEE Symposium on Security and Privacy, 343–359.
4. Phillips, C. et Swiler, L. P. (1998). “A graph-based system for network-vulnerability analysis.” Proceedings of the New Security Paradigms Workshop, 71–79.
5. Ammann, P., Wijesekera, D. et Kaushik, S. (2002). “Scalable, graph-based network vulnerability analysis.” Proceedings of the 9th ACM Conference on Computer and Communications Security, 217–224.
6. Sheyner, O., Haines, J., Jha, S., Lippmann, R. et Wing, J. M. (2002). “Automated generation and analysis of attack graphs.” Proceedings of the IEEE Symposium on Security and Privacy, 273–284.
7. Jha, S., Sheyner, O. et Wing, J. (2002). “Two formal analyses of attack graphs.” Proceedings of the 15th IEEE Computer Security Foundations Workshop, 49–63.
8. Staniford, S., Paxson, V. et Weaver, N. (2002). “How to own the Internet in your spare time.” Proceedings of the 11th USENIX Security Symposium, 149–167.
9. King, S. T. et Chen, P. M. (2003). “Backtracking intrusions.” Proceedings of the 19th ACM Symposium on Operating Systems Principles, 223–236.
10. Wang, Y., Chakrabarti, D., Wang, C. et Faloutsos, C. (2003). “Epidemic spreading in real networks: an eigenvalue viewpoint.” Proceedings of the 22nd International Symposium on Reliable Distributed Systems, 25–34.
11. Ou, X., Boyer, W. F. et McQueen, M. A. (2006). “A scalable approach to attack graph generation.” Proceedings of the 13th ACM Conference on Computer and Communications Security, 336–345.
12. Chakrabarti, D., Wang, Y., Wang, C., Leskovec, J. et Faloutsos, C. (2008). “Epidemic thresholds in real networks.” ACM Transactions on Information and System Security, 10(4), 1–26.
13. Noel, S. et Jajodia, S. (2008). “Optimal IDS sensor placement and alert prioritization using attack graphs.” Journal of Network and Systems Management, 16(3), 259–275.
14. Chau, D. H., Nachenberg, C., Wilhelm, J., Wright, A. et Faloutsos, C. (2011). “Polonium: tera-scale graph mining and inference for malware detection.” Proceedings of the SIAM International Conference on Data Mining, 131–142.
15. Wang, L., Jajodia, S., Singhal, A., Cheng, P. et Noel, S. (2014). “k-zero day safety: a network security metric for measuring the risk of unknown vulnerabilities.” IEEE Transactions on Dependable and Secure Computing, 11(1), 30–44.
16. Robbins, A., Vazarkar, R. et Schroeder, W. (2016). “Six degrees of Domain Admin.” DEF CON 24.
17. Milajerdi, S. M., Gjomemo, R., Eshete, B., Sekar, R. et Venkatakrishnan, V. N. (2019). “HOLMES: real-time APT detection through correlation of suspicious information flows.” Proceedings of the IEEE Symposium on Security and Privacy, 1137–1152.
18. Ohm, M., Plate, H., Sykosch, A. et Meier, M. (2020). “Backstabber's knife collection: a review of open source software supply chain attacks.” Detection of Intrusions and Malware, and Vulnerability Assessment (DIMVA), 23–43.