Graphentheorie in der Cybersicherheit

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. Warum Sicherheitsfragen Graphenfragen sind

Ein Schwachstellenscanner erzeugt eine Liste. Sie sagt Ihnen, dass dieser Host eine veraltete Bibliothek nutzt, jener eine Verwaltungsoberfläche offenlegt und ein dritter ein schwaches Dienstkonto hat. Jeder Eintrag erhält einen Schweregrad, die Liste wird sortiert, und das obere Ende wird behoben.

Angreifer lesen diese Liste nicht so wie Verteidiger. Ein Eindringen ist eine Abfolge: ein Brückenkopf an einer unwichtigen Stelle, ein dort abgegriffenes Zugangsdatum, ein Dienst, der diesem Zugangsdatum vertraut, eine Freigabe, die diesem Dienst vertraut, und schließlich etwas, das zählt. Jeder Schritt kann für sich unauffällig sein. Die Kombination ist der Einbruch.

Dieser Unterschied ist genau der Unterschied zwischen einer Menge und einem Graphen. Eine Liste von Schwächen hat keine Struktur; eine Menge von Schwächen plus die Übergänge zwischen ihnen ist ein gerichteter Graph, und sobald er existiert, werden die Fragen der Verteidiger zu Standardalgorithmen. Welcher Weg ist am leichtesten? Kürzester Pfad. Welche Kontrollen unterbrechen jeden Weg? Minimaler Schnitt. Was erreicht eine Kompromittierung? Erreichbarkeit. Wann stirbt Schadsoftware nicht mehr von selbst aus? Der größte Eigenwert der Adjazenzmatrix.

Die Idee ist in der Literatur nicht neu. Phillips und Swiler schlugen 1998 eine graphbasierte Schwachstellenanalyse vor, Sheyner und Kollegen automatisierten 2002 die Erzeugung von Angriffsgraphen per Model Checking, und seitdem ist der Ansatz in der Forschung Standard. Neu ist, dass die Werkzeuge endlich aufgeholt haben: Heutige Umgebungen sind so groß, dass niemand die Pfade im Kopf behalten kann, und Graphen dieser Größe lassen sich in Millisekunden lösen.

Jede Zahl in diesem Artikel wurde durch Lösen des Modells berechnet, nicht geschätzt. Falls Ihnen das Graphenvokabular fremd ist, behandelt die Einführung in die Graphentheorie die hier verwendeten Definitionen.

2. Der Angriffsgraph: Knoten, Bögen und Gewichte

Drei Modellierungsentscheidungen tragen das Gewicht, und jede hat einen ehrlichen Zielkonflikt.

Was ist ein Knoten? Die einfachste nützliche Wahl ist ein Host, und das verwendet dieser Artikel. Forschungsmodelle sind oft feiner: Ein Knoten ist ein Zustand, ein Paar aus Maschine und Berechtigungsstufe, sodass „User auf web01“ und „Root auf web01“ verschiedene Knoten sind. Das ist genauer und viel größer, weil sich der Zustandsraum vervielfacht. Es gibt auch gröbere Modelle, in denen ein Knoten ein ganzes Subnetz ist. Wählen Sie die Granularität, auf der Ihre Kontrollen wirken, denn das Modell dient dem Vergleich von Kontrollen.

Was ist ein Bogen? Ein Übergang, den der Angreifer vollziehen kann: ein ausnutzbarer Dienst, eine Vertrauensbeziehung, ein wiederverwendetes Zugangsdatum, eine eingebundene Freigabe, ein Phishing-Ziel. Bögen sind gerichtet, weil die Kompromittierung in eine Richtung fließt. Ein Arbeitsplatz, der eine Dateifreigabe einbindet, liefert einen Bogen in die Freigabe hinein, nicht aus ihr heraus, und wer diese Richtung falsch setzt, kehrt jedes Ergebnis um.

Was steht auf dem Bogen? Mindestens eine Zahl, und die Wahl bestimmt, was „kürzester“ bedeutet:

• Aufwand des Angreifers, eine Schwierigkeitsbewertung. Der kürzeste Pfad bedeutet dann das leichteste Eindringen. Dieser Artikel verwendet den Aufwand.
• Erfolgswahrscheinlichkeit. Entlang des Pfads multiplizieren statt addieren, oder die negativen Logarithmen addieren und denselben Kürzeste-Wege-Algorithmus unverändert verwenden.
• Kontrollkosten. Der Preis der Maßnahme, die diesen Bogen entfernt. Der minimale Schnitt über diese Zahlen ist der billigste Weg, jeden Weg zu unterbrechen, und das ist Abschnitt 6.

Woher kommen die Zahlen? Meist aus einem Bewertungssystem wie der CVSS-Ausnutzbarkeit, kalibriert von jemandem, der die Umgebung kennt. Es sind Schätzungen, und die ehrliche Haltung ist, dass die Rangfolge weit robuster ist als die absoluten Werte. Wenn Sie eine 3 nicht gegen eine 4 verteidigen können, können Sie doch verteidigen, dass ein öffentlicher Web-Exploit leichter ist als der Diebstahl eines Domänenadmin-Zugangs, und genau diese Reihenfolge treibt die Ergebnisse unten.

3. Das Netz, das den ganzen Artikel begleitet

Das durchgehende Beispiel ist ein kleines Unternehmen, bewusst gewöhnlich. Das Internet erreicht drei exponierte Systeme: einen öffentlichen Webserver, ein Mail-Gateway und einen VPN-Konzentrator. Dahinter liegen zwei Arbeitsplätze und ein Anwendungsserver, dann ein Dateiserver und eine Datenbank und schließlich der Domänencontroller, den der Angreifer will.

Jeder der sechzehn Bögen trägt einen Aufwandswert und Kontrollkosten. Die Aufwandswerte besagen, dass das Ausnutzen der öffentlichen Webanwendung 3 kostet, ein interner Dienstaufruf aus der DMZ in die App-Schicht 2 und das Stehlen zwischengespeicherter Domänenadmin-Zugangsdaten von einem Arbeitsplatz 8, was schwer, aber nicht unmöglich ist. Diese relativen Urteile sind die einzige echte Eingabe des Modells.

Eine strukturelle Anmerkung, bevor irgendein Algorithmus läuft: Dieser Graph hat keine Zyklen, weil jeder Bogen den Angreifer weiter nach innen bringt. Echte Angriffsgraphen haben Zyklen, weil ein Angreifer hin und her pivotieren kann, und jeder unten verwendete Algorithmus kommt damit zurecht. Der azyklische Fall macht die durchgerechneten Beispiele lediglich leichter von Hand prüfbar.

4. Der leichteste Weg hinein: kürzeste Angriffspfade

Die erste Frage ist die, die ein Penetrationstester in zwei Wochen von Hand beantwortet: Was ist der leichteste Weg vom Internet zum Domänencontroller? Mit dem Aufwand auf den Bögen ist das ein Kürzeste-Wege-Problem, und der Dijkstra-Algorithmus beantwortet es für jedes Asset auf einmal.

Die Antwort lautet internet → web01 → app01 → db01 → dc01 mit einem Gesamtaufwand von 12. Lesen Sie die Schritte: die öffentliche Webanwendung ausnutzen (3), den vertrauten internen Dienstaufruf in die App-Schicht nutzen (2), die Datenbank erreichen, die die Anwendung abfragen darf (3), und das Dienstkonto der Datenbank gegen den Domänencontroller missbrauchen (4).

Zwei Dinge an diesem Ergebnis zählen mehr als die Zahl.

Keiner dieser vier Schritte ist für sich alarmierend. Eine Schwachstelle in einer Webanwendung mit der Bewertung 3 von 10 steht nicht oben im Risikoregister. Ein Dienstaufruf zwischen zwei Systemen, die miteinander reden sollen, ebenso wenig. Der Weg ist als Komposition gefährlich, und kein Schweregrad pro Host kann eine Komposition ausdrücken. Das ist das grundlegende Argument für Angriffsgraphen, 1998 von Phillips und Swiler vorgebracht und seitdem in jeder Arbeit wiederholt.

Der leichteste Weg meidet die Menschen. Phishing ist der meistdiskutierte Erstzugang, und hier kostet der Phishing-Weg zum Domänencontroller 14, nicht 12. Das Modell sagt nicht, dass Phishing unwichtig ist; es sagt, dass in dieser Umgebung mit diesen Werten der Serverpfad billiger ist. Die billigste Option des Angreifers statt der meistgefürchteten Option des Verteidigers auszurechnen, ist genau das, wofür der Algorithmus da ist.

Dieselbe Berechnung liefert den Aufwand für jedes andere Asset: web01 kostet 3, app01 kostet 5, der Dateiserver 8, die Datenbank 8. Das sind die Zahlen für einen Prüfungsausschuss, der wissen will, wie weit der Perimeter wirklich von den Kronjuwelen entfernt ist.

5. Sechzehn Wege hinein, und welcher Host sie trägt

Der billigste Pfad ist eine Antwort. Ihn zu blockieren ist keine Strategie, weil der Angreifer einfach den nächsten nimmt. Die nützliche Frage ist, wie viele Wege es gibt und durch welche Assets sie führen.

Zählt man jeden einfachen Pfad vom Internet zum Domänencontroller auf diesem Graphen auf, erhält man 16 verschiedene Wege, mit Kosten zwischen 12 und 25 und einem Median von 18,5. Sechzehn ist eine kleine Zahl, gerade weil das Beispiel klein ist; eine reale Umgebung mit einigen Tausend Hosts hat routinemäßig mehr Angriffspfade, als sich sinnvoll zählen lassen, weshalb die Aufzählung ein Lehrmittel ist und die Metriken unten die Produktionstechnik.

Zählt man, wie viele dieser Wege durch jeden Host führen, entsteht eine Rangfolge, und sie ist nicht die, die ein Perimeterbericht liefern würde.

Der Dateiserver liegt auf 12 der 16 Wege, drei Vierteln davon. Der öffentliche Webserver, in den meisten Organisationen die am genauesten beobachtete Maschine, liegt auf 3. Nichts am Dateiserver würde bei einem externen Scan auffallen: Er ist nicht exponiert, betreibt nichts Exotisches und ist dazu da, Dokumente zu halten. Er ist kritisch wegen seiner Lage im Graphen, und nur ein Graph kann das sagen.

Bei der Aufzählung hört dieser Ansatz auch auf zu skalieren, und es lohnt sich zu sehen, warum. Sechzehn Wege entstehen aus zehn Hosts und sechzehn Bögen. Fügen Sie einen zweiten Dateiserver hinzu, den beide Arbeitsplätze erreichen, und die Zahl verdoppelt sich ungefähr; eine reale Umgebung mit einigen Tausend Maschinen und einem flachen internen Netz hat eine Pfadzahl mit mehr Stellen, als je jemand lesen wird. Die Metriken unten vermeiden alle die Aufzählung, und das macht sie in einem realen Netz nutzbar.

Dieses Maß ist ein sicherheitsspezifischer Verwandter der Betweenness-Zentralität, 1977 von Freeman eingeführt, die den Anteil der kürzesten Wege zählt, die durch einen Knoten laufen. Betweenness über alle Paare ist das Standardmaß der Netzwerkwissenschaft und lässt sich in O(nm) mit dem Algorithmus von Brandes berechnen. Für die Verteidigung ist es meist handlungsnäher, die Pfade zwischen dem einen relevanten Paar zu zählen, dem Einstiegspunkt des Angreifers und dem Asset, das Ihnen wichtig ist: Das beantwortet „wenn ich eine Maschine härte, wie viele Wege störe ich“ statt „wie zentral ist sie im Allgemeinen“.

Noel und Jajodia argumentierten 2008 ebenso für die Platzierung von Sensoren: Setzen Sie die Erkennung dorthin, wo sich die Angriffspfade bündeln, nicht dorthin, wo die wertvollsten Assets stehen, denn an den Bündelungspunkten erhalten Sie die meiste Abdeckung pro Sensor.

6. Jeden Weg unterbrechen: der minimale Schnitt

Eine Rangfolge der Hosts sagt Ihnen, wo Sie hinsehen sollen. Die stärkere Frage ist, welche Menge von Kontrollen jeden Weg auf einmal unterbrechen würde und wie wenig das kosten könnte.

Geben Sie jedem Bogen die Kosten der Kontrolle, die ihn entfernt, und berechnen Sie dann den minimalen Schnitt zwischen dem Internet und dem Domänencontroller. Das Max-Flow-Min-Cut-Theorem garantiert, dass die billigste solche Menge genau der minimale Schnitt ist, und der Algorithmus liefert ihn in Polynomialzeit. Dieselbe Maschinerie behandelt Netzwerkfluss, Max-Flow und Min-Cut.

Die Antwort sind drei Kontrollen mit zusammen 7: verhindern, dass der Webserver in der DMZ in die App-Schicht aufruft (3), verhindern, dass Mail-Anhänge auf Arbeitsplätzen ausgeführt werden (2), und VPN-Nutzer in einem eingeschränkten Segment statt neben den Arbeitsplätzen landen lassen (2). Das erneute Aufzählen der Pfade nach ihrer Anwendung liefert null.

Beachten Sie, wo der Schnitt liegt. Alle drei Kontrollen sitzen an der Grenze zwischen Perimeter und Innenraum, und keine berührt den Domänencontroller, die Datenbank oder den Dateiserver. Der Instinkt, zuerst die Kronjuwelen zu härten, ist nicht das, was die Mathematik empfiehlt: Die billigste vollständige Lösung liegt an der engsten Stelle des Graphen, und das ist hier der erste Schritt nach innen.

Dieselbe Frage für Maschinen statt Verbindungen nutzt den Trick des Knotenaufteilens. Ersetzen Sie jeden Host durch eine Eingangs- und eine Ausgangskopie, verbunden durch einen Bogen der Kapazität 1, geben Sie den echten Bögen unendliche Kapazität, und der minimale Schnitt zählt nun Hosts statt Verbindungen. Die Antwort lautet hier 3 Hosts: web01, mail01 und vpn, genau die drei, die zum Internet zeigen. Auf einem kleinen Beispiel ist das eine beruhigende Plausibilitätsprüfung und auf einem großen eine wirklich nützliche Berechnung, weil die entsprechende Menge dort selten offensichtlich ist.

7. Was eine einzelne Kontrolle wirklich bringt

Budgets finanzieren selten drei Kontrollen auf einmal, also lautet die praktische Frage, welche einzelne man zuerst kauft. Jeden Bogen nacheinander zu entfernen und neu zu lösen, liefert eine Antwort, und die Antwort ist ernüchternd.

Die beste einzelne Kontrolle hebt den Aufwand des Angreifers von 12 auf 14. Das ist alles. Keine einzelne Maßnahme in diesem Netz bringt mehr als zwei Punkte Schwierigkeit, weil der Graph reich verbunden ist und der Angreifer einfach auf den nächstbilligeren Weg ausweicht. Das ist die quantitative Fassung einer bekannten Sicherheitswahrheit: Defense in Depth ist kein Slogan, sondern eine Folge davon, dass einzelne Schnitte in einem dichten Graphen sehr wenig bewirken.

Die Tabelle zeigt auch, dass die gewählte Metrik die Rangfolge verändert. Den Übergang vom Mail-Gateway zum Arbeitsplatz zu blockieren, halbiert die Zahl der Wege von 16 auf 8 und lässt den leichtesten Pfad des Angreifers bei 12 völlig unberührt. Berichtet Ihr Vorstand „eliminierte Angriffspfade“, nennen Sie diese Kontrolle einen Erfolg; berichtet er „Aufwand des Angreifers“, nennen Sie sie nutzlos. Beide Zahlen sind echt, sie messen Verschiedenes, und nur eine davon zu zitieren ist der Weg, auf dem Sicherheitsprogramme die falsche Größe optimieren.

Das beste Preis-Leistungs-Verhältnis in dieser Tabelle hat das Blockieren des Wegs von der Datenbank zum Domänencontroller: Kosten 5, Aufwand steigt auf 14, Wege sinken auf 7. Es ist die einzige Kontrolle, die beide Metriken deutlich verbessert, und keine Intuition hätte sie gefunden.

8. Blast Radius: was eine Kompromittierung erreicht

Angriffspfade fragen, wie ein Eindringling hineinkommt. Die ergänzende Frage ist, was passiert, wenn er irgendwo drin ist, und das ist eine schlichte Erreichbarkeitsberechnung: Welche Assets kann man von einem kompromittierten Host aus letztlich erreichen? Eine Traversierung pro Host beantwortet das in linearer Zeit.

Die Rangfolge kehrt die Expositionsrangfolge um. Der öffentliche Webserver, die am stärksten exponierte Maschine der Umgebung, erreicht 4 Assets. Das Mail-Gateway erreicht 6. Ein Arbeitsplatz erreicht 5. Exposition misst, wer Sie erreichen kann; der Blast Radius misst, wen Sie erreichen können, und beide ergeben aus demselben Graphen verschiedene Prioritätenlisten.

Die Zahl, die ein Meeting zum Stillstand bringen sollte, ist diese: Neun der zehn Hosts können letztlich den Domänencontroller erreichen. Nur der Domänencontroller selbst nicht, weil hinter ihm nichts liegt. In einer realen Umgebung ist diese Zahl das nützlichste Ergebnis der ganzen Übung, weil sie „wir haben ein flaches Netz“ von einer Meinung in eine Messung verwandelt.

Der Blast Radius macht auch Eindämmungsentscheidungen während eines Vorfalls handhabbar. Ist ein Host als kompromittiert bestätigt, ist die Menge der zu untersuchenden Maschinen seine vorwärts erreichbare Menge, und die Menge, die ihn infiziert haben könnte, seine rückwärts erreichbare Menge, berechnet auf dem umgekehrten Graphen. Beides ist eine einzige Traversierung und weit präziser, als aus dem Bauch heraus ein ganzes Subnetz zu isolieren.

9. Wie schnell es sich ausbreitet: die Epidemieschwelle

Ransomware und Würmer folgen keinem einzelnen Pfad; sie breiten sich aus. Um das zu modellieren, braucht es eine andere Frage: Gegeben ein Netz und eine Infektion, die sich zwischen Nachbarn ausbreitet und mit einer gewissen Rate bereinigt wird, stirbt sie aus oder übernimmt sie die Umgebung?

Die Antwort ist eines der nützlichsten Ergebnisse der Netzwerkwissenschaft, und sie ist exakt. Für eine sehr breite Klasse von Ausbreitungsmodellen hängt der Kipppunkt von einer einzigen Zahl ab: dem größten Eigenwert der Adjazenzmatrix, geschrieben λ₁. Eine Infektion, deren Verhältnis von Ausbreitung zu Bereinigung unter 1 / λ₁ liegt, stirbt von selbst aus; darüber wird sie endemisch. Wang, Chakrabarti, Wang und Faloutsos bewiesen das 2003, und Chakrabarti und Kollegen verallgemeinerten es 2008.

Im Graphen der lateralen Bewegung hier, neun Hosts und dreizehn Links, beträgt λ₁ 3,573, also liegt die Schwelle bei 0,280. Simuliert man eine Infektion mit 40 % dieses Verhältnisses, gemittelt über 600 Läufe, ist sie bis Schritt 21 ausgestorben. Beim Vierfachen des Verhältnisses stabilisiert sie sich bei 5,5 der 9 Hosts und bleibt dort auf Dauer. Die Schwelle sagte beide Ergebnisse voraus, bevor eine der Simulationen lief.

Operativ interessant wird das dadurch, dass Sie λ₁ ändern können. Den Dateiserver von den Arbeitsplätzen und der Anwendungsschicht zu isolieren, entfernt drei Links und senkt λ₁ von 3,573 auf 2,570, womit die Schwelle von 0,280 auf 0,389 steigt. Das ist ein um 39 % größerer Spielraum: Infektionen, die sich vorher festgesetzt hätten, sterben jetzt aus.

Zwei Tatsachen machen den Eigenwert leichter zu durchschauen, als er zunächst wirkt. Er liegt immer zwischen dem mittleren und dem maximalen Grad des Graphen, hier also zwischen 2,889 und 5, und 3,573 liegt ordnungsgemäß dazwischen. Und er wird vom dichtesten Teil des Netzes dominiert, also senkt man ihn am schnellsten, indem man die Vernetzung des am stärksten vernetzten Hosts reduziert. Genau das tut die Segmentierung oben: Der Dateiserver hat Grad 5, den höchsten der Umgebung, und das Kappen von drei seiner Links bringt ihn auf 2 und senkt den maximalen Grad des ganzen Graphen von 5 auf 3. Die am stärksten vernetzte Maschine ist die, die man isolieren sollte, und der Grad ist eine einzeilige Rechnung, die Sie ausführen können, bevor Sie irgendeinen Eigenwertcode anfassen.

Das verändert den Blick auf Segmentierung. „Segmentieren Sie das Netz“ wird meist mit einer Geschichte begründet; hier ist es ein Eingriff in eine berechenbare Größe, mit einem Vorher und einem Nachher. Die Idee geht zurück auf Kephart und White, die 1991 für das IEEE Symposium on Security and Privacy epidemiologische Modelle von Computerviren auf gerichteten Graphen bauten, und auf Staniford, Paxson und Weaver, deren Analyse der Wurmausbreitung von 2002 zeigte, wie schnell sich die Kurve bewegt, wenn der Graph dicht ist.

10. Active Directory: der Graph, den Angreifer schon nutzen

Alles bisher war ein Modell, das ein Verteidiger gebaut hat. Der folgenreichste Graph der Unternehmenssicherheit existiert bereits, niemand hat ihn bewusst entworfen, und Angreifer fragen ihn seit Jahren ab: Active Directory.

Eine AD-Umgebung ist ein Graph, ob ihn jemand zeichnet oder nicht. Nutzer sind Knoten, Gruppen sind Knoten, Computer sind Knoten, und die Bögen sind die Beziehungen, die das Verzeichnis ohnehin speichert: ist Mitglied von, ist Admin auf, kann das Passwort zurücksetzen von, hat eine Sitzung auf, besitzt, hat GenericWrite auf. Jede dieser Beziehungen ist ein Übergang, den ein Angreifer nutzen kann.

2016 veröffentlichten Robbins, Vazarkar und Schroeder BloodHound und hielten den Vortrag, der der Technik ihren Namen gab: „Six Degrees of Domain Admin“. Seine Einsicht ist genau die Einsicht dieses Artikels: Die einzeln harmlosen Fakten setzen sich zusammen. Eine Helpdesk-Gruppe, die Passwörter für eine Gruppe zurücksetzen kann, in der ein Nutzer ist, der zufällig eine aktive Sitzung auf einem Server hat, auf dem sich letzten Dienstag ein Domänenadmin angemeldet hat, ist ein Pfad mit vier Schritten zur vollständigen Kompromittierung, und kein einzelnes Glied darin sieht wie eine Fehlkonfiguration aus.

BloodHound sammelt diese Beziehungen und führt eine Kürzeste-Wege-Abfrage darauf aus. Es ist Dijkstra, auf einem Graphen, an dessen Zeichnung niemand gedacht hatte. Das Ergebnis veränderte die defensive Praxis, weil die gefundenen Pfade sowohl real als auch für jedes andere eingesetzte Werkzeug unsichtbar waren.

Drei Lehren lassen sich auf jede Umgebung übertragen:

• Die Daten existieren bereits. Verzeichnisbeziehungen, Cloud-IAM-Richtlinien, Kubernetes-Rollenbindungen und SaaS-Freigaben sind allesamt Graphen, die in einer Datenbank liegen und darauf warten, als solche abgefragt zu werden.
• Sitzungen sind auch Bögen. Eine angemeldete Sitzung erzeugt eine vorübergehende Kante von dieser Maschine zu den Rechten dieser Identität, weshalb „wer ist wo angemeldet“ eine Sicherheitsfrage ist und keine Inventarfrage.
• Aufräumen ist eine Graphenbearbeitung. Eine einzige verschachtelte Gruppenmitgliedschaft zu entfernen, kann Tausende von Pfaden löschen, und ohne den Graphen lässt sich das nicht erkennen.

11. Erkennung: Provenienzgraphen und Schuld durch Nähe

Angriffsgraphen dienen der Prävention. Zwei weitere Graphentechniken laufen auf der Erkennungsseite, und sie nutzen ganz andere Graphen.

Provenienzgraphen zeichnen auf, was auf einem System tatsächlich geschehen ist: Prozesse, Dateien, Sockets und die kausalen Beziehungen zwischen ihnen. Ein Prozess liest eine Datei, schreibt eine andere, startet ein Kind, öffnet eine Verbindung. King und Chen führten 2003 auf der SOSP mit ihrem System BackTracker die Rückverfolgung ein: Ausgehend von einem Erkennungspunkt, etwa einer verdächtigen Datei, geht man rückwärts durch den kausalen Graphen, um herauszufinden, wie sie dorthin kam. Die Vorwärtstraversierung von einem Einstiegspunkt zeigt den Schaden; die Rückwärtstraversierung von einem Symptom zeigt die Ursache. Beides sind Graphtraversierungen über dieselbe aufgezeichnete Struktur.

Die moderne Variante gleicht diese Flüsse mit bekanntem Angreiferverhalten ab. HOLMES, 2019 beim IEEE Symposium on Security and Privacy veröffentlicht, bildet verdächtige Informationsflüsse in einem Provenienzgraphen auf die Taktiken und Techniken eines Angriffslebenszyklus ab und schlägt Alarm, wenn das Muster der Flüsse eher einem Eindringen als normaler Aktivität ähnelt. Die technische Schwierigkeit ist die Größe: Provenienzgraphen wachsen auf einem einzigen ausgelasteten Host um Millionen Kanten pro Stunde, und effizientes Reduzieren und Abfragen ist das eigentliche Forschungsproblem.

Schuld durch Nähe ist die zweite Technik, und sie ist Inferenz auf einem Graphen statt Traversierung. Man baut einen bipartiten Graphen aus Maschinen und Dateien: Eine Maschine ist mit jeder Datei verbunden, die sie gesehen hat. Die meisten Dateien und Maschinen sind unmarkiert, einige wenige sind als gut und einige wenige als schlecht bekannt. Belief Propagation verbreitet diese Markierungen dann entlang der Kanten, unter der Annahme, dass Dateien, die auf vielen infizierten Maschinen auftauchen, verdächtig sind und Maschinen mit vielen schlechten Dateien kompromittiert.

Das bauten Chau, Nachenberg, Wilhelm, Wright und Faloutsos 2011 als Polonium, lauffähig auf einem Graphen mit rund 60 Milliarden Maschine-Datei-Kanten aus Symantec-Telemetrie, mit einer berichteten Trefferquote von etwa 85 %. Die Technik zählt, weil sie weder Signatur noch Sandbox braucht: Eine Datei, die noch nie jemand analysiert hat, lässt sich nach ihrer Gesellschaft beurteilen. Dieselbe Form der Berechnung, ein bipartiter Graph plus Label-Propagation, treibt die Betrugserkennung im Zahlungsverkehr und die Missbrauchserkennung auf sozialen Plattformen an.

12. Der Graph der Software-Lieferkette

Der letzte Graph ist der, den Ihr Build-System abläuft. Eine moderne Anwendung deklariert eine Handvoll direkter Abhängigkeiten, von denen jede ihre eigenen deklariert, und die transitive Hülle umfasst routinemäßig Hunderte oder Tausende von Paketen. Diese Hülle ist ein gerichteter azyklischer Graph, und sie ist eine Angriffsfläche.

Die Sicherheitsfrage ist eine Erreichbarkeitsfrage. Wenn ein Paket tief im Graphen kompromittiert ist, welche Ihrer Anwendungen führen seinen Code aus? Das ist Vorwärtserreichbarkeit vom kompromittierten Knoten im umgekehrten Abhängigkeitsgraphen, und es ist die Abfrage, die jede Organisation in der ersten Stunde eines Lieferkettenvorfalls hektisch zu beantworten versucht. Teams mit einer Software-Stückliste beantworten sie in Sekunden; Teams ohne verbringen Tage mit grep.

Zwei Eigenschaften des Graphen machen das auf eine Weise gefährlich, die eine Liste nicht zeigen würde. Tiefe verbirgt Risiko: Ein Paket, das Sie nie gewählt haben, drei Ebenen unter einem, das Sie gewählt haben, läuft mit denselben Rechten wie Ihr eigener Code. Beliebtheit bündelt es: Die Pakete mit dem höchsten Eingangsgrad sind die wertvollsten Ziele, weil die Kompromittierung eines einzigen Tausende nachgelagerter Projekte auf einmal erreicht, und genau dieses Muster dokumentiert die Übersicht über reale Open-Source-Lieferkettenangriffe von Ohm, Plate, Sykosch und Meier aus dem Jahr 2020.

Die nützlichen defensiven Metriken sind Graphmetriken. Zählen Sie die Größe der transitiven Hülle, nicht die Zahl der direkten Abhängigkeiten. Ordnen Sie Abhängigkeiten danach, wie viele Ihrer Anwendungen sie erreichen. Achten Sie auf Pakete mit einem einzigen Maintainer und hohem Eingangsgrad, genau dem Risikoprofil, das mehrere der bekanntesten Vorfälle hervorgebracht hat. Die Technik ist identisch mit der Berechnung des Blast Radius aus Abschnitt 8, nur auf einem anderen Graphen.

13. Was leicht ist, was schwer ist

Die Angriffsgraphanalyse hat unter den Sicherheitstechniken ungewöhnlich klare Komplexitätsverhältnisse, und zu wissen, auf welcher Seite der Linie eine Frage liegt, spart viel vergeudete Mühe.

Das Muster ist das bekannte: Fragen über Fluss und Zusammenhang sind billig, Fragen darüber, welche diskreten Dinge man ändern soll, sind teuer. Die Aufzählung ist die Falle in der Mitte. Sie ist intuitiv, jede Demonstration macht sie, und die Zahl der einfachen Pfade kann exponentiell mit der Größe des Netzes wachsen, weshalb ernsthafte Werkzeuge Metriken über den Graphen berechnen, statt seine Pfade aufzulisten. Ammann, Wijesekera und Kaushik argumentierten 2002 genau so, als sie eine kompakte, monotone Darstellung vorschlugen, die polynomiell skaliert, statt aufzuzählen.

Eine Metrik, die man beim Namen kennen sollte, ist k-Zero-Day-Safety, 2014 von Wang, Jajodia, Singhal, Cheng und Noel vorgeschlagen. Sie fragt, wie viele verschiedene unbekannte Schwachstellen ein Angreifer bräuchte, um ein Asset zu erreichen, und umgeht so die unbeantwortbare Frage, wie wahrscheinlich jeder einzelne Exploit ist. Sie ist eine Graphdistanz unter einer anderen Gewichtung und ein gutes Beispiel für den besseren Instinkt des Fachs: Struktur messen, nicht Wahrscheinlichkeit.

14. Modellierungsfehler

Ein falscher Angriffsgraph ist schlimmer als keiner, weil er selbstsichere, konkrete, falsche Prioritäten erzeugt. Diese Fehler kehren immer wieder.

• Die Richtung der Bögen falsch setzen. Ein Arbeitsplatz, der eine Freigabe einbindet, erzeugt einen Bogen in die Freigabe hinein. Kehrt man ihn um, wirkt der Dateiserver sicher und der Arbeitsplatz kritisch, und nichts an der Ausgabe sieht kaputt aus.
• Hosts modellieren, wenn das Risiko in Identitäten liegt. Ist der eigentliche Übergang ein Zugangsdatum, das an drei Stellen funktioniert, erfasst ihn ein Bogen zwischen zwei Maschinen nicht. Deshalb ist der Active-Directory-Graph in Abschnitt 10 ein eigenes Modell und keine Verfeinerung dieses Modells.
• Bewertungen als Messungen behandeln. Die Aufwandszahlen sind Urteile. Vertrauen Sie der Reihenfolge, misstrauen Sie der dritten Nachkommastelle, und prüfen Sie, ob der Schluss eine Störung der Bewertungen übersteht. Wenn sich die empfohlene Kontrolle ändert, sobald aus einer 3 eine 4 wird, sagen Sie das.
• Vergessen, dass der Graph eine Momentaufnahme ist. Ein Laptop, der sich mit dem VPN verbindet, fügt Bögen hinzu; ein stillgelegter Server entfernt welche; eine vorübergehende Firewall-Ausnahme während einer Migration kann einen Weg öffnen, den kein Diagramm je verzeichnet hat. Ein Angriffsgraph ist nur so aktuell wie das Inventar dahinter.
• Pfade in einer realen Umgebung aufzählen. Bei zehn Hosts funktioniert das wunderbar, bei zehntausend wird es nie fertig. Berechnen Sie stattdessen Schnitte, Zentralität und Erreichbarkeit, die alle polynomiell sind.
• Eine einzige Metrik berichten. Abschnitt 7 zeigte eine Kontrolle, die die Zahl der Angriffspfade halbiert und den Angreifer überhaupt nicht bremst. Veröffentlichen Sie Aufwand des Angreifers und Zahl der Wege gemeinsam, sonst optimiert das Programm die Größe, die gerade auf der Folie steht.
• Die Bögen ignorieren, die sich nicht entfernen lassen. Manche Übergänge sind das Geschäft selbst: Die Anwendung muss die Datenbank abfragen. Das Modell sollte sie als fest markieren, damit der Optimierer keine Kontrollen mehr vorschlägt, die nie genehmigt werden.

15. Vom Modell zur Praxis

Vier Dinge trennen ein Diagramm, das ein Meeting beeindruckt, von einem Modell, das Entscheidungen ändert.

Bauen Sie den Graphen aus Daten, die Sie schon haben. Firewall-Regelwerke, Definitionen von Cloud-Sicherheitsgruppen, Ausgaben von Schwachstellenscans, Active-Directory-Beziehungen und EDR-Telemetrie beschreiben allesamt Kanten. Ein in einem Workshop von Hand zusammengestelltes Modell ist eine Woche nach dem Workshop veraltet; ein aus der Konfiguration erzeugtes Modell wird jede Nacht neu erzeugt.

Beginnen Sie mit Erreichbarkeit, nicht mit Angriffspfaden. Das billigste wertvolle Ergebnis ist die Blast-Radius-Tabelle aus Abschnitt 8, weil sie überhaupt keine Exploit-Bewertung braucht, nur Konnektivität. „Neun unserer zehn Hosts können den Domänencontroller erreichen“ ist ein Befund, der ankommt, und Sie können ihn liefern, bevor jemand über CVSS streitet.

Nutzen Sie die vorhandenen Werkzeuge. MulVAL, der skalierbare Angriffsgraphgenerator, 2006 von Ou, Boyer und McQueen veröffentlicht, ist in der Forschung immer noch die Referenzimplementierung. BloodHound deckt den Identitätsgraphen ab. NetworkX oder eine Graphdatenbank übernimmt die Analyse, sobald die Kanten existieren. Keiner der Algorithmen in diesem Artikel muss von Grund auf geschrieben werden, und die Graphenkapitel jedes Algorithmenlehrbuchs behandeln die, bei denen es doch nötig ist.

Neu lösen statt streiten. Jede Behauptung in diesem Artikel hat das Modell in Millisekunden entschieden: dass der leichteste Weg die Arbeitsplätze meidet, dass der Dateiserver viermal so viele Wege trägt wie der Webserver, dass die beste einzelne Kontrolle zwei Punkte Aufwand bringt, dass Segmentierung die Epidemieschwelle um 39 % hebt. Die Intuition über Netze ist gerade in den Fällen unzuverlässig, auf die es ankommt, und der ganze Wert des Graphen liegt darin, dass man sie nicht mehr braucht.

16. Wie es weitergeht

Am schnellsten verinnerlicht man dieses Material, indem man einen Graphen baut, statt über einen zu lesen, und die Hürde ist niedriger, als sie aussieht. Zehn Hosts und sechzehn Bögen, mehr hat dieser Artikel nicht verwendet, passen in eine Textdatei, und jedes Ergebnis oben stammt aus ein paar Dutzend Zeilen gewöhnlichen Codes.

Eine sinnvolle Reihenfolge, um die Bausteine zu lernen: Machen Sie sich zuerst mit der Breiten- und Tiefensuche vertraut, denn Erreichbarkeit und Blast Radius sind nichts anderes als eine Traversierung mit Buchführung. Dann Kürzeste-Wege-Algorithmen, die Ihnen die Analyse des leichtesten Wegs liefern und, mit negativen Logarithmen auf den Bögen, auch die des wahrscheinlichsten Wegs. Dann Max-Flow und Min-Cut, das ist der gesamte Inhalt der Abschnitte 6 und 7 und das am wenigsten genutzte Ergebnis der defensiven Sicherheit.

Danach ist die nützliche Richtung eher strukturell als algorithmisch: gerichtete und ungerichtete Graphen entscheiden erstaunlich viele Modellierungsstreitigkeiten, und die Graphdarstellung entscheidet, ob Ihre Analyse bei einer großen Umgebung eine Sekunde oder eine Stunde läuft. Die Komplexitätsgrenzen aus Abschnitt 13 sind allgemeiner dargestellt unter Graphalgorithmen und Komplexität.

Wenn Sie lieber von der Sicherheitsseite her beginnen, ist der kürzeste Weg zu einem echten Ergebnis, Ihre Active-Directory-Beziehungen zu exportieren und abzufragen, denn dieser Graph existiert bereits und niemand musste ihn modellieren. Der Befund, der dann folgt, ist meist derselbe, mit dem dieser Artikel endet: Die Zahl der Maschinen, die letztlich den Domänencontroller erreichen können, ist weit höher, als irgendjemand im Raum erwartet hat.

18. Quellen

Die Arbeiten, die diese Techniken begründet haben, in chronologischer Reihenfolge.

1. Ford, L. R. und 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. und 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. und 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. und 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. und 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. und 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. und 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. und 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. und 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. und 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. und Faloutsos, C. (2008). “Epidemic thresholds in real networks.” ACM Transactions on Information and System Security, 10(4), 1–26.
13. Noel, S. und 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. und 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. und 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. und Schroeder, W. (2016). “Six degrees of Domain Admin.” DEF CON 24.
17. Milajerdi, S. M., Gjomemo, R., Eshete, B., Sekar, R. und 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. und 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.