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

オープン
  • 何か問題がありますか？
#2,249 コメント 0 件 リアクション 0 件 担当者 0 名 GitHub で見る

メンテナーはふだん 1 日以内に返信

まだ誰も着手していません。

評価

難易度
3/5
見積もり時間
半日
初心者へのやさしさ
55/100
issue の種類
バグ
明瞭さ
おおむね明確
活発さ
活発
技術スタック
python
領域
backend

調査の方向性

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.

索引モデルが issue の本文から書いたものです。

説明

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.

主要言語
Cuda
スター
1.1k
フォーク
249
平均マージ
1日 16時間
マージ済み PR（30日）
127

環境構築

はじめの一歩

  1. issue を最後まで読み、次にプロジェクトのコントリビューションガイドを読みます。
  2. 着手することを issue にコメントします — 二人が同じ作業をするのを防げます。
  3. リポジトリをフォークし、ブランチを切って変更します。
  4. issue 番号を参照したプルリクエストを送ります。

NVIDIA/cuopt のほかの issue

NVIDIA/cuopt の issue をすべて見る

似ている issue

Backend & API Design の issue をもっと見る

新しい issue をメールで受け取る

初心者向けの GitHub issue を短くまとめたダイジェスト。