BUG: DBSCAN algorithms use an Epsilon of 0, negative or NaN when called without the filter #1887

Problem

The DBSCAN algorithm classes do not check Epsilon themselves. Only DBSCANFilter preflight checks it (-7584). When code calls DBSCAN (or DBSCANDirect / DBSCANScanline) directly, without the filter, an Epsilon of 0, a negative Epsilon or a NaN Epsilon is used to size the clustering grid. That conversion is undefined behavior.

• Expected: the algorithm returns an error Result for an Epsilon that is not finite and greater than 0.
• Actual: on macOS arm64 the algorithm returns a valid Result for Epsilon 0, -1 and NaN. The grid dimensions come from an undefined float-to-integer conversion, so the result on other platforms is not defined.

Seen on develop 31cfe8106.

Steps to Reproduce

1. Build the SimplnxCoreUnitTest target of develop 31cfe8106 (in-core build).
2. Add the test below to src/Plugins/SimplnxCore/test/DBSCANTest.cpp, and add #include <atomic> and #include <limits> to that file.
3. Run ctest -R "SimplnxCore::DBSCAN: Direct algorithm call rejects an invalid Epsilon" --verbose.

Cause

Each algorithm computes the grid cell size from Epsilon and divides by it:

• DBSCANDirect (DBSCANDirect.cpp lines 242-254):

  float32 sideLength = epsilon / std::sqrt(Dimensions);
  std::array<float32, 3> spacing = {sideLength, sideLength, sideLength};
  ...
  dims[0] = static_cast<usize>(((bounds[3] + buffer) - origin[0]) / spacing[0]) + 2;

  With Epsilon 0 the division gives an infinity, with a negative Epsilon a negative value, and with NaN a NaN. Converting any of these to usize is undefined behavior. The grid size is the product of dims, and std::vector<bool> is allocated with that size. The same computation is at DBSCANDirect.cpp line 452.

• DBSCANScanline does the same at DBSCANScanline.cpp line 2481 and line 2719 (in-memory stores), and at line 384 with the conversion at line 439 (out-of-core path). The out-of-core path checks MinPoints < 0 (line 337) but not Epsilon, and its documentation says "Filter preflight has validated positive Epsilon and MinPoints values" (line 314).

The filter rejects Epsilon <= 0.0f in preflight (DBSCANFilter.cpp lines 140-143). The algorithm classes are exported and can be called without the filter, so they cannot rely on that check.

Inferred, not confirmed: on x86-64 the conversion of an infinity or a NaN to usize usually gives a very large value, so the grid allocation would fail or use a very large amount of memory. Only macOS arm64 was run.

Verification Unit Test

File: src/Plugins/SimplnxCore/test/DBSCANTest.cpp (also add #include <atomic> and #include <limits>).

TEST_CASE("SimplnxCore::DBSCAN: Direct algorithm call rejects an invalid Epsilon", "[SimplnxCore][DBSCAN]")
{
  // DBSCAN is called without DBSCANFilter, so filter preflight (-7584) does not run.
  const float32 epsilon = GENERATE(0.0f, -1.0f, std::numeric_limits<float32>::quiet_NaN());
  CAPTURE(epsilon);

  DataStructure dataStructure;
  auto* points = Float32Array::CreateWithStore<DataStore<float32>>(dataStructure, "points", {4}, {2});
  REQUIRE(points != nullptr);
  auto& pointsStore = points->getDataStoreRef();
  const std::array<float32, 8> coordinates = {0.0f, 0.0f, 0.0f, 0.5f, 10.0f, 10.0f, 10.0f, 10.5f};
  for(usize index = 0; index < coordinates.size(); index++)
  {
    pointsStore[index] = coordinates[index];
  }
  REQUIRE(Int32Array::CreateWithStore<DataStore<int32>>(dataStructure, "cluster_ids", {4}, {1}) != nullptr);
  REQUIRE(AttributeMatrix::Create(dataStructure, "cluster_am", ShapeType{1}) != nullptr);

  DBSCANInputValues inputValues;
  inputValues.ClusteringArrayPath = DataPath({"points"});
  inputValues.UseMask = false;
  inputValues.FeatureIdsArrayPath = DataPath({"cluster_ids"});
  inputValues.Epsilon = epsilon;
  inputValues.MinPoints = 1;
  inputValues.DistanceMetric = ClusterUtilities::DistanceMetric::Euclidean;
  inputValues.FeatureAM = DataPath({"cluster_am"});
  inputValues.ParseOrder = to_underlying(DBSCAN::ParseOrder::LowDensityFirst);
  inputValues.Seed = 0;

  const std::atomic_bool shouldCancel = false;
  const Result<> result = DBSCAN(dataStructure, IFilter::MessageHandler{}, shouldCancel, &inputValues)();
  REQUIRE(result.invalid());
}

Command, from the build directory: ctest -R "SimplnxCore::DBSCAN: Direct algorithm call rejects an invalid Epsilon" --verbose

Failure output on develop 31cfe8106 (macOS arm64, Release, in-core build):

DBSCANTest.cpp:759: FAILED:
  REQUIRE( result.invalid() )
with expansion:
  epsilon := 0.0f
DBSCANTest.cpp:759: FAILED:
  REQUIRE( result.invalid() )
with expansion:
  epsilon := -1.0f
DBSCANTest.cpp:759: FAILED:
  REQUIRE( result.invalid() )
with expansion:
  epsilon := nanf
assertions: 12 | 9 passed | 3 failed

Proposed Fix

Check Epsilon in the algorithm, before the first use, and return an error when it is not finite and greater than 0:

• DBSCAN::operator()() in Algorithms/DBSCAN.cpp, before the dispatch, covers calls through DBSCAN. DBSCANDirect::operator()() and DBSCANScanline::operator()() also need the check, because both classes are exported and can be called directly.
• Use a comparison that rejects NaN, for example if(!(std::isfinite(epsilon) && epsilon > 0.0f)), and give the check its own error code.
• Change the @pre at DBSCANScanline.cpp line 314 to describe the input ("Epsilon and MinPoints are positive") instead of the filter.
• Run the verification test for both algorithm paths (UnitTest::SelectAlgorithmTestScenariosForInMemoryStores() with UnitTest::AlgorithmTestScope).

Notes

• MinPoints has the same gap: the out-of-core path rejects only MinPoints < 0, while the filter requires MinPoints > 0 (-7585). Not tested.
• The filter preflight check pEpsilonValue <= 0.0f lets NaN through, because every comparison with NaN is false. That is a separate preflight problem of the class tracked in BUG: C14: Parameter values not validated in preflight in 65 filters #1873. BUG: C14: Parameter values not validated in preflight in 65 filters #1873 leaves out the DBSCAN findings because DBSCAN has a V&V report, and handles them on a separate V&V branch.
• PR BUG: Enforce component shapes and types that filters read #1766 restores the out-of-core component-count and mask checks in DBSCANScanline for the same reason: the algorithm can be called without the filter.