Integer underflow and buffer overrun in detail::count_rows on disconnected distance matrices

Đang mở Phù hợp với người mới
  • Có gì không ổn?
#3,192 0 bình luận 0 reaction 0 người được giao Xem trên GitHub

Maintainer thường phản hồi trong vòng 3 ngày

Chưa có ai nhận issue này.

Đánh giá

Độ khó
2/5
Thời gian dự kiến
1-3 giờ
Mức phù hợp với người mới
72/100
Loại issue
Lỗi
Độ rõ ràng
Đặc tả rõ ràng
Mức độ hoạt động
Sôi nổi
Công nghệ
cpp, postgresql
Lĩnh vực
backend

Hướng nghiên cứu

Bắt đầu từ src/cpp_common/to_postgres.cpp tại detail::count_rows, sau đó đọc matrix_to_tuple và lệnh gọi pgr_alloc(tupcount, tuples) dùng để xác định kích thước bộ đệm. Thay phép trừ kích thước bằng việc đếm tường minh các ô hữu hạn nằm ngoài đường chéo, như issue đề xuất. Hoàn thành khi một unit test với ma trận không liên thông (bao gồm đường chéo không thể truy cập) trả về đúng số dòng và không có tràn bộ đệm.

Do mô hình lập chỉ mục viết ra từ nội dung của issue.

Mô tả

Integer underflow and buffer overrun in detail::count_rows on disconnected or sparse distance matrices

Description

In src/cpp_common/to_postgres.cpp, detail::count_rows calculates the number of valid off-diagonal entries in an all-pairs distance matrix (pgr_johnson, pgr_floydWarshall):

size_t
count_rows(const std::vector<std::vector<double>> &matrix) {
    int64_t count = 0;
    for (size_t i = 0; i < matrix.size(); i++) {
        count += std::count_if(
                matrix[i].begin(), matrix[i].end(),
                [](double value) {
                return value != (std::numeric_limits<double>::max)();
                });
    }
    return static_cast<size_t>(count) - matrix.size();
}

This implementation assumes that every diagonal entry matrix[i][i] is non-infinity (!= max()) and is counted in count. However, on disconnected graphs, sparse inputs, or subgraphs with unreachable self-distances:

  1. Underallocation & Buffer Overrun: If any diagonal entry equals max(), count did not include that cell, yet matrix.size() is still subtracted. As a result, count_rows returns fewer rows than the actual number of valid off-diagonal pairs. matrix_to_tuple then iterates over all valid off-diagonal entries and writes past the end of the tuples buffer allocated by pgr_alloc(tupcount, tuples), resulting in memory corruption.

  2. Unsigned Integer Underflow: If count < matrix.size() (for example, on an empty or largely unreachable graph where fewer than N cells are finite), static_cast<size_t>(count) - matrix.size() underflows unsigned subtraction to a huge value (~1.84e19). pgr_alloc then attempts to allocate an astronomical amount of memory, terminating the PostgreSQL backend process with an out-of-memory error.

Expected Behavior

count_rows should count exactly the valid off-diagonal cells (i != j && matrix[i][j] != max()) without underflowing or underallocating.

Proposed Solution

Replace the subtraction assumption with an explicit off-diagonal count:

size_t
count_rows(const std::vector<std::vector<double>> &matrix) {
    size_t count = 0;
    for (size_t i = 0; i < matrix.size(); ++i) {
        for (size_t j = 0; j < matrix[i].size(); ++j) {
            if (i != j && matrix[i][j] != (std::numeric_limits<double>::max)()) {
                ++count;
            }
        }
    }
    return count;
}

I can open a PR with this fix and a unit test covering disconnected matrices.

Ngôn ngữ chính
C++
Star
1.4k
Fork
397
Merge trung bình
2 ngày 16 giờ
Pull request đã merge (30 ngày)
8

Chuẩn bị môi trường

Bắt đầu từ đâu

  1. Đọc hết issue, rồi đọc hướng dẫn đóng góp của dự án.
  2. Bình luận trên issue rằng bạn sẽ nhận — tránh hai người làm cùng một việc.
  3. Fork repository và làm thay đổi trên một nhánh.
  4. Mở pull request có tham chiếu số hiệu của issue.

Issue khác của pgRouting/pgrouting

Tất cả issue của pgRouting/pgrouting

Issue tương tự

Thêm issue về C++

Nhận issue mới trong hộp thư của bạn

Bản tóm tắt ngắn những issue GitHub phù hợp với người mới.