AUTHOR: @Marko Budiselic DATE: April 15, 2025

Intro

Graphs are invaluable in cybersecurity because they naturally model relationships among hosts, vulnerabilities, and attack paths. Nodes can represent systems or vulnerabilities, while edges capture interactions or exploitation routes. This structure helps security teams visualize and analyze how threats propagate through a network, pinpointing critical nodes or choke points. Attack graphs, for example, reveal potential steps an adversary could take to move laterally and access high-value assets. By leveraging graph algorithms—such as a shortest path or centrality measures—defenders can prioritize remediation, identify where to place monitoring tools and streamline incident response. Ultimately, graph-based insights enable more efficient and proactive cyber defense.

MATCH (n) DETACH DELETE n;

CREATE INDEX ON :Endpoint(name);
CREATE INDEX ON :Internal(name);
CREATE INDEX ON :Vulnerability(name);

CREATE 
    // NODES: Exposed endpoints
    (internet:Endpoint {name: "Internet"}),
    (vpn:Endpoint {name: "VPN Gateway"}),
    (web:Endpoint {name: "Web Server"}),
    (email:Endpoint {name: "Email Server"}),
    (rdp:Endpoint {name: "Remote Desktop Server"}),
    // NODES: Internal hosts/servers
    (db:Internal {name: "Database Server"}),
    (ws1:Internal {name: "Internal Workstation 1"}),
    (ws2:Internal {name: "Internal Workstation 2"}),
    (admin:Internal {name: "Admin Workstation"}),
    (backup:Internal {name: "Backup Server"}),
    // NODES: Vulnerabilities
    (v1:Vulnerability {name: "CVE-2023-4567", type: "Weak Authentication", severity: "High"}),
    (v2:Vulnerability {name: "CVE-2022-1234", type: "SQL Injection", severity: "Critical"}),
    (v3:Vulnerability {name: "CVE-2021-7890", type: "Brute-force RDP", severity: "High"}),
    (v4:Vulnerability {name: "Phishing Risk", type: "Social Engineering", severity: "Medium"}),
    (v5:Vulnerability {name: "SMB Exploit (CVE-2019-0708)", type: "Remote Code Execution", severity: "Critical"}),
    (v6:Vulnerability {name: "Weak Credentials", type: "Credential Attack", severity: "High"}),
    (v7:Vulnerability {name: "Ransomware Infection", type: "Malware", severity: "Critical"}),
    (v8:Vulnerability {name: "Misconfigured Access Controls", type: "Privilege Escalation", severity: "High"}),
    (v9:Vulnerability {name: "Default Credentials", type: "Unauthorized Access", severity: "High"}),
    // EDGES: Entry points to network
    (internet)-[:ATTACK {type: "Weak Authentication", cve: "CVE-2023-4567"}]->(vpn),
    (internet)-[:ATTACK {type: "SQL Injection", cve: "CVE-2022-1234"}]->(web),
    (internet)-[:ATTACK {type: "Phishing Attack"}]->(email),
    (internet)-[:ATTACK {type: "Brute-force RDP", cve: "CVE-2021-7890"}]->(rdp),
    // EDGES: Entry points to internal network
    (vpn)-[:ATTACK {type: "Credential Theft"}]->(ws1),
    (web)-[:ATTACK {type: "Weak Credentials"}]->(db),
    (email)-[:ATTACK {type: "Malware Payload"}]->(ws2),
    (rdp)-[:ATTACK {type: "Privilege Escalation"}]->(admin),
    // EDGES: Lateral movement
    (ws1)-[:ATTACK {type: "SMB Exploit", cve: "CVE-2019-0708"}]->(ws2),
    (ws2)-[:ATTACK {type: "Privilege Escalation"}]->(db),
    (db)-[:ATTACK {type: "Ransomware Infection"}]->(backup),
    (admin)-[:ATTACK {type: "Misconfigured Access Controls"}]->(backup),
    // EDGES: Alternative attack paths
    (email)-[:ATTACK {type: "Phishing Attack"}]->(admin),
    (backup)-[:ATTACK {type: "Default Credentials"}]->(admin),
    // EDGES: Vulnerabilities affecting endpoints & internal hosts
    (vpn)-[:HAS_VULNERABILITY]->(v1),
    (web)-[:HAS_VULNERABILITY]->(v2),
    (rdp)-[:HAS_VULNERABILITY]->(v3),
    (email)-[:HAS_VULNERABILITY]->(v4),
    (ws1)-[:HAS_VULNERABILITY]->(v5),
    (db)-[:HAS_VULNERABILITY]->(v6),
    (backup)-[:HAS_VULNERABILITY]->(v7),
    (admin)-[:HAS_VULNERABILITY]->(v8),
    (backup)-[:HAS_VULNERABILITY]->(v9);

MATCH (n)-[r]->(m) RETURN n, r, m;

Example Dataset

All Shortest Paths

The All Shortest Paths (ASP) algorithm has several valuable applications in cybersecurity, particularly in areas related to network security, threat analysis, and vulnerability assessment.

MATCH path=(n1 {name: "Internet"})
    -[:ATTACK *ALLSHORTEST (r, n | 1)
                           total_weight
                           (r, n | n.name != "Admin Workstation")]-
           (n2 {name: "Backup Server"})
RETURN path, total_weight;

Network Traffic Analysis and Anomaly Detection

• The ASP algorithm helps in analyzing network topology to detect the most efficient paths for data flow.
• By comparing expected shortest paths with actual traffic, security teams can identify anomalies (e.g., unexpected detours indicating possible man-in-the-middle attacks or routing attacks).

Attack Graph Analysis and Threat Propagation

• Security analysts construct attack graphs to model how threats can move through a system.
• The ASP algorithm identifies the most efficient paths attackers might take, helping in predicting and mitigating lateral movement within a network.
• It assists in determining the minimum steps required for an attacker to reach a critical asset.

Intrusion Detection and Incident Response

• ASP is used to identify optimal routes that attackers might take to move through a system, aiding in real-time intrusion detection.
• Helps in optimizing response strategies, ensuring that security teams block or disrupt critical paths used by attackers.