[BUG] Out-of-bounds read when solving a DataModel with lower/upper constraint bounds

Open
  • Is something wrong?
#2,249 0 comments 0 reactions 0 assignees View on GitHub

Maintainers usually reply within 1 day

Nobody has claimed this yet.

Assessment

Difficulty
3/5
Estimated time
Half a day
Newbie friendliness
55/100
Issue type
Bug
Clarity
Mostly clear
Activity status
Active
Tech stack
python
Domain
backend

Research direction

Start with _compute_slack_csr, the function the report names as reading the rhs and sense arrays, and compare it with how a DataModel built through set_constraint_lower_bounds() and set_constraint_upper_bounds() fills those arrays. Run the reproducer in the issue, which should print slack near zero for x >= 1. Done means the slack is computed from the constraint bounds without reading the empty arrays, and the Cython bounds-checked run no longer reports an out-of-bounds access.

Written by the indexing model from the issue text.

Description

bug

(AI-assisted bug report)

cuopt.linear_programming.Solve accepts a DataModel whose constraints are supplied through set_constraint_lower_bounds() and set_constraint_upper_bounds(). When it constructs a Solution with a primal vector, its Python/Cython slack calculation instead reads the alternative RHS and row-sense arrays. Those arrays are empty for this valid DataModel representation. Because Cython bounds checking is disabled, the code reads outside both arrays. The read can produce an incorrect slack or terminate the process with SIGSEGV.

Reproducer:

import numpy as np
from cuopt.linear_programming.data_model import DataModel
from cuopt.linear_programming.solver import Solve
from cuopt.linear_programming.solver_settings import SolverMethod, SolverSettings

# Minimize x subject to x >= 1.
dm = DataModel()
dm.set_csr_constraint_matrix(
    np.array([1.0]),
    np.array([0], dtype=np.int32),
    np.array([0, 1], dtype=np.int32),
)
dm.set_objective_coefficients(np.array([1.0]))
dm.set_variable_lower_bounds(np.array([0.0]))
dm.set_variable_upper_bounds(np.array([np.inf]))
dm.set_variable_types(np.array(["C"], dtype="S1"))
dm.set_constraint_lower_bounds(np.array([1.0]))
dm.set_constraint_upper_bounds(np.array([np.inf]))

print(
    "rows=1",
    "rhs=", len(dm.get_constraint_bounds()),
    "sense=", len(dm.get_row_types()),
    "lower=", len(dm.get_constraint_lower_bounds()),
    "upper=", len(dm.get_constraint_upper_bounds()),
    flush=True,
)
settings = SolverSettings()
settings.set_parameter("method", SolverMethod.PDLP)
settings.set_parameter("log_to_console", False)
solution = Solve(dm, settings)
print(solution.get_termination_reason())
print("x=", solution.get_primal_solution())
print("slack=", solution.get_slack())

Observed locally:

rows=1 rhs= 0 sense= 0 lower= 1 upper= 1
Optimal
x= [1.]
slack= [-1.]

The constraint is x >= 1 so we'd expect the slack to be zero. I observed segfaults on other instances.

The source of the issue is _compute_slack_csr which reads from the rhs and sense vectors which aren't initialized in this DataModel code path. Running with bounds checking enabled in Cython confirms the out of bounds access.

Dominant language
Cuda
Stars
1.1k
Forks
249
Avg merge
1d 16h
Merged PRs (30d)
127

Getting set up

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

More from NVIDIA/cuopt

All issues in NVIDIA/cuopt

Similar issues

More Backend & API Design issues

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.