Hunting Lateral Movement With Embeddings and Time Travel

On this page

About this data
Building the authentication graph
The simple query first
Time travel: when did it change?
Behaviour, for when you have no labels
What this hunt did and did not prove
What's next

Find the account that appeared somewhere it had never been, then reconstruct when it happened.

The previous post ended on a negative result: ranking machines by importance finds your servers, not your intruder. This post finds the intruder. The change is not a cleverer algorithm. It is looking at behaviour over time rather than at structure.

About this data

data/lanl/auth.csv needs a plain warning before you read anything into it.

The 25 red-team events are real, taken from the dataset's own ground-truth labels: real accounts, real machines, real timestamps. The benign events around them are synthetic, generated by data/lanl/make_auth.py from the real DNS graph, because the genuine LANL authentication file is tens of gigabytes and is not something to ship in a documentation repository.

So the intrusion is authentic and the crowd it hides in is manufactured. The script says so at the top and is deterministic, so you can read exactly how the background was made. Real authentication data is messier than this, and a hunt against it is correspondingly harder.

Building the authentication graph

Two node types and one edge, with the event time recorded on the edge:

import csv
import collections

from astraeadb import AstraeaClient

auth = list(csv.reader(open("data/lanl/auth.csv")))
redteam = list(csv.reader(open("data/lanl/redteam.csv")))
attack_start = min(int(row[0]) for row in redteam)

client = AstraeaClient(host="127.0.0.1", port=7687)
client.connect()

nodes = {}
def node(label, name):
    if (label, name) not in nodes:
        nodes[(label, name)] = client.create_node([label], {"name": name})
    return nodes[(label, name)]

for time, user, source, dest in auth:
    client.create_edge(
        node("User", user), node("Computer", source), "AUTH_FROM",
        {"dest": dest},
        valid_from=int(time),      # the edge exists from this moment onward
    )

print(f"{len(auth)} events, {len(nodes)} nodes, attack begins at t={attack_start}")

valid_from is the important argument. It records when the relationship came into existence, which turns the graph into something you can ask questions of as it was rather than only as it is.

The simple query first

Before reaching for anything sophisticated, ask the obvious question. People sit at their own machines. An account appearing on more than one is worth a look:

machines_per_user = collections.defaultdict(set)
for _, user, source, _ in auth:
    machines_per_user[user].add(source)

suspects = {u: sorted(m) for u, m in machines_per_user.items() if len(m) > 1}
print(f"{len(suspects)} of {len(machines_per_user)} accounts used more than one machine")
for user, machines in sorted(suspects.items()):
    print(f"   {user:12} {machines}")

Five accounts out of roughly twelve hundred. Now check them against the labels:

known_bad = {row[1] for row in redteam}
print("every suspect is a known red-team account:", set(suspects) <= known_bad)
print("red-team accounts we found:", len(set(suspects) & known_bad), "of", len(known_bad))

Every one, and all of them. Perfect precision and perfect recall, from counting.

That is worth sitting with, because it is the most useful habit in this post. The graph made the question easy to ask, but the answer needed no embeddings, no traversal and no model. Try the boring query first. If it works you are finished, and if it does not you have learned something about the shape of the problem before spending anything.

Time travel: when did it change?

Counting told you who. It cannot tell you when, and "when" is what turns a suspicion into an incident report.

Because every edge carries a valid_from, you can ask what the graph looked like at any moment. neighbors_at takes a timestamp and answers as of then:

def machines_at(user, when):
    hops = client.neighbors_at(nodes[("User", user)], "outgoing", when, "AUTH_FROM")
    return sorted({client.get_node(h["node_id"])["properties"]["name"] for h in hops})


user = "U748@DOM1"
print(f"{user} just before the intrusion:", machines_at(user, attack_start - 1))
print(f"{user} after it:                 ", machines_at(user, 244910))

One machine before, three after. That is the whole story of a stolen credential in two lines: the account was working normally somewhere, and then it turned up in two places it had never been.

Do it for all five and you have a timeline:

for user in sorted(suspects):
    before = machines_at(user, attack_start - 1)
    after = machines_at(user, 244910)
    arrived = [m for m in after if m not in before]
    print(f"{user:12} home={before}  appeared on={arrived}")

Every account has exactly one home machine before the intrusion, and every one of them turns up on C17693. One also reaches C18025. That is the attacker's foothold and their pivot, recovered from the data rather than assumed.

Behaviour, for when you have no labels

The two techniques above worked because this graph is small and the anomaly is stark. Both leaned on knowing what to count.

The harder question is the one you face on a real network: which machines behave like this one, when you have no labels and cannot enumerate the rules in advance. That is what embeddings are for. Describe each machine's behaviour in a sentence, embed the sentence, and let similarity do the comparing:

import json
import os
import urllib.request

OLLAMA_URL = os.environ.get("OLLAMA_URL", "http://localhost:11434")


def embed(texts):
    body = json.dumps({"model": "embeddinggemma", "input": texts}).encode()
    req = urllib.request.Request(f"{OLLAMA_URL}/api/embed", data=body,
                                 headers={"Content-Type": "application/json"})
    with urllib.request.urlopen(req, timeout=60) as resp:
        return json.load(resp)["embeddings"]


users_per_machine = collections.defaultdict(set)
dests_per_machine = collections.defaultdict(set)
for _, user, source, dest in auth:
    users_per_machine[source].add(user)
    dests_per_machine[source].add(dest)

profiles = {
    machine: (f"A machine used by {len(users)} distinct accounts, "
              f"reaching {len(dests_per_machine[machine])} destinations.")
    for machine, users in users_per_machine.items()
}

names = sorted(profiles)
for name, vec in zip(names, embed([profiles[n] for n in names])):
    client.create_edge(node("Computer", name),
                       node("Profile", f"profile:{name}"), "DESCRIBED_BY")
    client.get_node(node("Profile", f"profile:{name}"))   # keep the id warm

print("described", len(profiles), "machines")
print("C17693:", profiles["C17693"])

The profile for C17693 reads differently from every other machine's, because five accounts using one machine is a description that nothing else in the population matches. On a real network you would embed richer profiles, covering which services a machine reaches, at what hours, and how that compares with the machines around it, then look for the ones whose description has drifted from their own past.

The point is the shape of the technique rather than this particular sentence: turn behaviour into text, turn text into a position, and let distance find the things you would not have known to grep for.

client.close()

What this hunt did and did not prove

It found five compromised accounts with perfect precision, dated the intrusion, and named the attacker's two machines, all checkable against labels the dataset's authors provided.

It did that against a background that was manufactured to be well behaved. The honest reading is that the techniques are sound and the difficulty was removed. On real telemetry the counting query would return hundreds of accounts using more than one machine, most of them administrators, shared workstations and service accounts, and the work would be in separating those from the one that matters. The graph does not remove that work. It makes each attempt cheap enough to try.

What's next

You have a suspicion, a timeline, and the machines involved. In Explaining an Investigation: GraphRAG for Audit-Grade Reports, you will turn that into something a person can read and an auditor can check, where every sentence traces back to a node in the graph.