Skip to content

Kruskal: fixed 200-element arrays overflow on JS-supplied edge/vertex counts #9

Description

@bushidocodes

Problem
The Kruskal (devyani) module stores the entire graph in fixed 200-element global arrays and indexes them with counts supplied by the (JS/WASM) caller with no bounds checking. insertadjver writes edgearray[edgeCount] and increments edgeCount without limit; makeset writes parent[u]/rank[u] for u up to vertexCount. More than 200 edges, or any vertex id >= 200, is an out-of-bounds write.

Evidence
src/devyani/wasm/main.c:13-14,35-36,184-194

edgenode *edgearray[200];
edgenode *mst[200];
...
int parent[200];
int rank[200];
...
void insertadjver(int src, int des, int weight) {
    edgearray[edgeCount] = newedgenode(src, des, weight);  // edgeCount unbounded
    int max = src > des ? src : des;
    if (max > (vertexCount - 1)) vertexCount = (max + 1);
    edgeCount++;
}

And makeset (main.c:130-134) writes parent[u]/rank[u]; kruskal calls makeset(i) for i up to vertexCount (main.c:68-69). All malloc calls in this file (Buildheap main.c:90,93; newedgenode main.c:198; newheapnode main.c:207) are also unchecked.

Impact
Out-of-bounds writes / heap and global corruption once the input exceeds 200 edges or uses a vertex id >= 200; these functions are exported to JS so the bound is attacker/data controlled.

Recommendation
Allocate the arrays dynamically based on the actual edge/vertex counts (or enforce and document a hard cap with explicit bounds checks in insertadjver/makeset), and check every malloc.


Severity: high · Category: security · Filed by an automated multi-repo code review.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions