Skip to content

Undefined behavior and missing edge-case guards in scaling_ratio_boundary_test #383

@Akash504-ai

Description

@Akash504-ai

Describe the bug
scaling_ratio_boundary_test in diagnostics/scaling_ratio.hpp can exhibit undefined behavior and incorrect diagnostic output due to uninitialized data and missing edge-case guards.
The issue is user-facing and occurs during normal execution of the sampling diagnostics.

This function is currently used by multiple executables (e.g. billiardshakeandbake.cpp and shakeandbake.cpp).

To Reproduce
1.Build and run either:

  • billiardshakeandbake.cpp, or
  • shakeandbake.cpp

2.Run the executable with a low dimension or sparse sampling, for example:

./billiardshakeandbake cube 1
./shakeandbake simplex 2

3.Observe the printed coverage matrix and deviation statistics.
Depending on the run, the output may contain:

  • NaNs
  • Inconsistent coverage values
  • Unstable deviation percentages

Expected behavior

  • Diagnostic outputs should be well-defined and deterministic.
  • All entries of the coverage matrix should be explicitly initialized.
  • Low-dimensional cases and empty facet sample sets should be handled or rejected explicitly, rather than relying on implicit assumptions.

Root cause analysis
1. Uninitialized coverage matrix (undefined behavior)

MT coverage(m, 10);
...
if (ratio < min_ratio) continue;
...
double d = std::abs(coverage(f, k) - scale[k]);

For facets whose sample ratio is below min_ratio, the corresponding entries of coverage are never written but are later read during deviation calculations.
This results in reading uninitialized memory.

2. Missing guards for low-dimensional cases

NT x = std::pow(step, 1.0 / dim);

No explicit guard exists for dim <= 1, although these values are reachable via the CLI.

3. Implicit assumption that facet sample sets are non-empty

p /= static_cast<double>(S.size());
coverage(f, k) = double(survivors) / double(S.size());

The code assumes S.size() > 0 indirectly via min_ratio, but this is not enforced explicitly.

4. Facet logic assumes full-dimensional polytopes
Skipping constraint j == f implicitly assumes a full-dimensional polytope.
In low dimensions, this can lead to incorrect survivor counts.

Affected files

  • diagnostics/scaling_ratio.hpp
  • billiardshakeandbake.cpp
  • shakeandbake.cpp

Impact

  • Undefined behavior due to uninitialized memory reads
  • Incorrect or misleading diagnostic results
  • Fragile behavior in low-dimensional or sparse-sampling cases
    Since this routine is used to assess sampling quality, incorrect diagnostics can lead to incorrect conclusions about algorithm behavior.

Environment

  • OS: Linux (WSL / Ubuntu)
  • Compiler: GCC
  • Eigen: project default
  • volesti: current development branch

Additional context
I’m happy to work on a fix for this issue if the current behavior is not intended.
I wanted to report it first to confirm the expected assumptions for this diagnostic routine.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions