Skip to content

Half-edge construction writes out of bounds on non-manifold input #102

Description

@GeneralPawz

Found by the corpus harness. Distinct from #101, which was an assertion
in pair_up; this is an out-of-bounds write during half-edge
construction, and it is by far the more common crash.

What happens

thread 'main' panicked at csg/manifold/hmesh.rs:80:16:
index out of bounds: the len is 252459 but the index is 252459

The index equals the length exactly, so ne has run one past the end of
e2v/e2f.

Cause

The edge table ett is sorted, then counted and rebuilt by two separate
loops that disagree about runs longer than two.

Counting (hmesh.rs:56):

let mut ne = 1;
for i in 0..ett.len() - 1 {
    if !(ett[i][0] == ett[i + 1][0] && ett[i][1] == ett[i + 1][1]) {
        ne += 1;
    }
}

A run of N equal edge rows increments ne once, so it counts one edge
per distinct edge key.

Building (hmesh.rs:68) consumes rows in pairs: the twin branch reads
ett[i] and ett[i + 1] and advances i by two, the border branch
advances by one. A run of three rows -- one edge shared by three faces --
is consumed as one pair plus one border, emitting TWO edges where the
count reserved ONE. ne then exceeds the allocated length and the write
at line 80 goes out of bounds.

This is exactly the non-manifold edge case: an edge with more than two
incident faces.

Distribution across the corpus

Panic sites over 240 models, 40 per defect class:

class hmesh boolean45
non_oriented 18 0
non_manifold 17 0
self_intersecting 13 0
open 10 0
multi_component 6 1

64 of the 65 remaining panics are this one site. It dominates every
damaged class; clean is unaffected at 40/40.

Why it matters

Same contract breach as #101: compute_boolean returns
Result<_, String>, but this aborts the process instead. A caller
feeding untrusted geometry cannot defend against it. Non-manifold input
is a documented corpus class (22% of Thingi10K), so this is expected
input for a repair or audit path, not a corrupt-file edge case.

Fix direction

The two loops need one shared notion of how a run is consumed. Either
count runs the same way the builder consumes them, or build from run
boundaries so the count cannot disagree. An edge with three or more
incident faces then needs a decision -- refuse with a typed error, or
represent it -- rather than silently overrunning.

Note the same structure exists upstream in crates.io boolmesh 0.1.9.

Reproduction

Any non-manifold corpus model, e.g. non_manifold 37366. A minimal
synthetic three-fin mesh does NOT reach this code: it is refused earlier
by the zero-signed-volume check, so the corpus models are currently the
only reproduction path.

Activity

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

Metadata

Metadata

Assignees

Labels

needs-triageFiled but not yet accepted, sized, or scheduled

Type

Projects

No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions