Skip to content

GEDCOM merge can spend quadratic CPU time on colliding identifiers #505

Description

@sodejm

Problem

A user-initiated merge of individually valid GEDCOM files with overlapping record identifiers can spend disproportionate CPU time allocating unique identifiers. Cancellation may be delayed while allocation is in progress. The established impact is local availability; the scan did not establish a public or unauthenticated merge endpoint.

Reproduction and validation

Use fictional, individually valid GEDCOM files with overlapping record identifiers. Compare merge time as the number of records grows and check cancellation latency. The finding is based on a static source trace; runtime scaling and cancellation have not yet been measured.

Cause

The unique-identifier allocator restarts its search at the first suffix for each collision while sharing the set of used identifiers across sources. Existing input limits do not bound the cumulative search work.

Proposed fix

Track the next available suffix per source and prefix, or use another collision-free allocation scheme. Bound fallback work and make cancellation responsive during a long search.

Acceptance criteria

  • Output identifiers remain unique and references resolve correctly for colliding inputs.
  • A scaling test demonstrates near-linear allocation work for increasing collisions.
  • Cancellation interrupts a long allocation promptly.

Release planning

Intended Feature Release iteration: v0.7. Repository milestone: 0.7.0 Genealogy Workflows. Project iteration assignment remains pending.

Source

Location (root_control): src/ancestryllm/gedcom/parser.py:99-107
Location (shared_state_and_call_site): src/ancestryllm/gedcom/parser.py:148-171
Location (affected_merge_operation): src/ancestryllm/gedcom/service.py:659-697
Location (resource_limit_context): src/ancestryllm/core/ingress.py:73-79
Location (validated_loader_call): src/ancestryllm/gedcom/service.py:377-382
Canonical finding ID: csf_3417a6ba206e1aa90319b93f
Primary fingerprint: codex-security/v1:sha256:711d5f6c1fd1ca5738e9dab2dbe3e918d5d6b4645f1ffa735cbee86ac5528e35

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    bugSomething isn't working

    Projects

    No projects

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions