Skip to content

Commit de4aec9

Browse files
fix(cypher): bound OPTIONAL fallback in expand_pattern_rels to a single ceiling
Signed-off-by: SEPURI-SAI-KRISHNA <[email protected]>
1 parent 69599b7 commit de4aec9

2 files changed

Lines changed: 138 additions & 2 deletions

File tree

‎src/cypher/cypher.c‎

Lines changed: 11 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -3233,6 +3233,14 @@ static void expand_pattern_rels(cbm_store_t *store, cbm_pattern_t *pat, binding_
32333233

32343234
bool is_variable_length = (rel->min_hops != SKIP_ONE || rel->max_hops != SKIP_ONE);
32353235

3236+
/* One global output ceiling for this hop: at most max_new = bind_cap*10
3237+
* rows, whether produced by the expansion helpers or by the OPTIONAL
3238+
* fallback further down. The helpers already stop at max_new; the fallback
3239+
* is held to the SAME ceiling (its `new_count < max_new` guard), so a
3240+
* saturating hub followed by OPTIONAL (no-match) sources truncates at the
3241+
* ceiling instead of writing past this buffer. Leaving that fallback
3242+
* unguarded let a second fallback row after a saturated expansion run off
3243+
* the end (heap OOB write, CWE-787). */
32363244
size_t alloc_n = (size_t)*bind_cap * (size_t)CYP_GROWTH_10 + SKIP_ONE;
32373245
binding_t *new_bindings = malloc(alloc_n * sizeof(binding_t));
32383246
if (!new_bindings) {
@@ -3261,8 +3269,9 @@ static void expand_pattern_rels(cbm_store_t *store, cbm_pattern_t *pat, binding_
32613269
&new_count, max_new, &match_count);
32623270
}
32633271

3264-
/* OPTIONAL MATCH: keep binding with empty target if no matches */
3265-
if (is_optional && match_count == 0) {
3272+
/* OPTIONAL MATCH: keep the binding with the target unbound when there
3273+
* were no matches, held to the same global ceiling as the expansion. */
3274+
if (is_optional && match_count == 0 && new_count < max_new) {
32663275
binding_t nb = {0};
32673276
binding_copy(&nb, b);
32683277
/* Don't set to_var — it remains unbound; projection returns "" */

‎tests/test_cypher.c‎

Lines changed: 127 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -517,6 +517,68 @@ TEST(cypher_exec_optional_empty_label_no_overflow) {
517517
PASS();
518518
}
519519

520+
/* Regression: expand_pattern_rels sized its OPTIONAL-expansion output buffer as
521+
* bind_cap*10 + 1 — room for the bounded expansion (max_new = bind_cap*10) plus
522+
* a SINGLE OPTIONAL fallback row. When one source saturated the expansion to
523+
* max_new and two or more later sources took the OPTIONAL (no-match) path, the
524+
* second fallback write ran past the allocation (ASan: heap-buffer-overflow).
525+
*
526+
* The fix holds the OPTIONAL fallback to the SAME global ceiling (max_new) the
527+
* expansion helpers already respect, so the hop truncates at the ceiling instead
528+
* of growing the buffer. Defined behavior at the ceiling: the query still
529+
* succeeds (rc == 0) with a bounded result — it does not overflow or error.
530+
* Query text is agent-controlled via the MCP query tool. */
531+
TEST(cypher_exec_optional_rel_ceiling_truncates_no_overflow) {
532+
cbm_store_t *s = cbm_store_open_memory();
533+
cbm_store_upsert_project(s, "test", "/tmp/test");
534+
535+
/* 1 hub + 20 leaf Function nodes → bind_cap = 21, max_new = 210. The hub is
536+
* inserted first so it is expanded before the leaves; it saturates the
537+
* expansion to the ceiling, then each leaf reaches the OPTIONAL fallback —
538+
* under the old alloc (211 slots) the 2nd such write overflowed. */
539+
cbm_node_t hub = {
540+
.project = "test", .label = "Function", .name = "hub", .qualified_name = "test.hub"};
541+
int64_t hub_id = cbm_store_upsert_node(s, &hub);
542+
for (int i = 0; i < 20; i++) {
543+
char nm[32];
544+
char qn[48];
545+
snprintf(nm, sizeof(nm), "leaf%02d", i);
546+
snprintf(qn, sizeof(qn), "test.leaf%02d", i);
547+
cbm_node_t leaf = {
548+
.project = "test", .label = "Function", .name = nm, .qualified_name = qn};
549+
cbm_store_upsert_node(s, &leaf);
550+
}
551+
552+
/* Give the hub 300 CALLS edges (> max_new = 210) so its expansion saturates
553+
* the ceiling; targets are non-Function so they don't inflate bind_cap. */
554+
for (int i = 0; i < 300; i++) {
555+
char nm[32];
556+
char qn[48];
557+
snprintf(nm, sizeof(nm), "callee%d", i);
558+
snprintf(qn, sizeof(qn), "test.callee%d", i);
559+
cbm_node_t callee = {.project = "test", .label = "Var", .name = nm, .qualified_name = qn};
560+
int64_t cid = cbm_store_upsert_node(s, &callee);
561+
cbm_edge_t e = {.project = "test", .source_id = hub_id, .target_id = cid, .type = "CALLS"};
562+
cbm_store_insert_edge(s, &e);
563+
}
564+
565+
/* max_rows below the Function count (21) so bind_cap tracks scan_count (21)
566+
* rather than the 100000 result ceiling — the same regime a large repo
567+
* (> ceiling functions) or an agent-supplied small limit hits. */
568+
cbm_cypher_result_t r = {0};
569+
int rc = cbm_cypher_execute(
570+
s, "MATCH (a:Function) OPTIONAL MATCH (a)-[:CALLS]->(b) RETURN a.name", "test", 5, &r);
571+
/* Defined ceiling behavior: bounded success, no overflow (ASan proves the
572+
* latter), result truncated to the LIMIT rather than crashing. */
573+
ASSERT_EQ(rc, 0);
574+
ASSERT_GT(r.row_count, 0);
575+
ASSERT_TRUE(r.row_count <= 5);
576+
577+
cbm_cypher_result_free(&r);
578+
cbm_store_close(s);
579+
PASS();
580+
}
581+
520582
/* Arithmetic-boundary companion to the zero-label overflow above: the node
521583
* cross-join sizes its buffer from bind_count * extra_count. As a plain int that
522584
* product wraps past INT_MAX to a negative/garbage malloc size (the large-graph
@@ -546,6 +608,69 @@ TEST(cypher_cross_join_alloc_rejects_overflow) {
546608
PASS();
547609
}
548610

611+
/* Companion to the truncation regression: when the expansion does NOT saturate
612+
* the ceiling, every leaf's OPTIONAL fallback row must survive with its target
613+
* unbound. A `row_count > 0` check is too weak — it can pass on hub rows alone —
614+
* so this asserts a specific leaf appears with an empty b.name, and that a real
615+
* expanded hub row is present too. */
616+
TEST(cypher_exec_optional_rel_leaf_fallback_survives) {
617+
cbm_store_t *s = cbm_store_open_memory();
618+
cbm_store_upsert_project(s, "test", "/tmp/test");
619+
620+
/* 1 hub (2 CALLS edges) + 3 leaves (no edges). Ceiling is huge (default
621+
* max_rows → bind_cap = 100000), so nothing truncates. */
622+
cbm_node_t hub = {
623+
.project = "test", .label = "Function", .name = "hub", .qualified_name = "test.hub"};
624+
int64_t hub_id = cbm_store_upsert_node(s, &hub);
625+
for (int i = 0; i < 3; i++) {
626+
char nm[32];
627+
char qn[48];
628+
snprintf(nm, sizeof(nm), "leaf%d", i);
629+
snprintf(qn, sizeof(qn), "test.leaf%d", i);
630+
cbm_node_t leaf = {
631+
.project = "test", .label = "Function", .name = nm, .qualified_name = qn};
632+
cbm_store_upsert_node(s, &leaf);
633+
}
634+
for (int i = 0; i < 2; i++) {
635+
char nm[32];
636+
char qn[48];
637+
snprintf(nm, sizeof(nm), "callee%d", i);
638+
snprintf(qn, sizeof(qn), "test.callee%d", i);
639+
cbm_node_t callee = {.project = "test", .label = "Var", .name = nm, .qualified_name = qn};
640+
int64_t cid = cbm_store_upsert_node(s, &callee);
641+
cbm_edge_t e = {.project = "test", .source_id = hub_id, .target_id = cid, .type = "CALLS"};
642+
cbm_store_insert_edge(s, &e);
643+
}
644+
645+
cbm_cypher_result_t r = {0};
646+
int rc = cbm_cypher_execute(
647+
s, "MATCH (a:Function) OPTIONAL MATCH (a)-[:CALLS]->(b) RETURN a.name, b.name", "test", 0,
648+
&r);
649+
ASSERT_EQ(rc, 0);
650+
ASSERT_EQ(r.col_count, 2);
651+
652+
/* Scan for a leaf fallback row (a.name = "leaf0", b.name unbound = "") and a
653+
* real expanded hub row (a.name = "hub", b.name non-empty). */
654+
bool leaf_fallback = false;
655+
bool hub_expanded = false;
656+
for (int i = 0; i < r.row_count; i++) {
657+
const char *a = r.rows[i][0];
658+
const char *b = r.rows[i][1];
659+
if (strcmp(a, "leaf0") == 0 && b[0] == '\0') {
660+
leaf_fallback = true;
661+
}
662+
if (strcmp(a, "hub") == 0 && b[0] != '\0') {
663+
hub_expanded = true;
664+
}
665+
}
666+
ASSERT_TRUE(leaf_fallback); /* the OPTIONAL no-match row survived */
667+
ASSERT_TRUE(hub_expanded); /* the expansion still produced bound rows */
668+
669+
cbm_cypher_result_free(&r);
670+
cbm_store_close(s);
671+
PASS();
672+
}
673+
549674
TEST(cypher_exec_where_eq) {
550675
cbm_store_t *s = setup_cypher_store();
551676
cbm_cypher_result_t r = {0};
@@ -3294,6 +3419,8 @@ SUITE(cypher) {
32943419
RUN_TEST(cypher_exec_match_all_functions);
32953420
RUN_TEST(cypher_exec_optional_empty_label_no_overflow);
32963421
RUN_TEST(cypher_cross_join_alloc_rejects_overflow);
3422+
RUN_TEST(cypher_exec_optional_rel_ceiling_truncates_no_overflow);
3423+
RUN_TEST(cypher_exec_optional_rel_leaf_fallback_survives);
32973424
RUN_TEST(cypher_issue240_labels_function);
32983425
RUN_TEST(cypher_issue237_distinct_order_limit);
32993426
RUN_TEST(cypher_issue873_distinct_order_limit_dedupes_before_limit);

0 commit comments

Comments
 (0)