[Address Sanitizer] Heap buffer overflow in SparseLU::compute

Summary

There is a heap buffer overflow that can be triggered in SparseLU::compute

Environment

Operating System : Ubuntu 24.04
Architecture : x64
Eigen Version : 3.4.0, verified on master (d228bcdf) too
Compiler Version : g++ 13.3.0
Compile Flags : -g -fno-omit-frame-pointer -fsanitize=address
Vector Extension : None selected

Minimal Example

#include <Eigen/SparseLU>
#include <algorithm>
#include <fstream>
#include <iterator>
#include <stdio.h>
#include <vector>

int main(int argc, char *argv[]) {
    if (argc < 3) {
        printf("Usage: %s [num_nodes] [filename]\n", argv[0]);
        return 1;
    }

    std::size_t num_nodes; // Size of the matrix
    if (sscanf(argv[1], "%zd", &num_nodes) == 0) {
        printf("Failed to parse num_nodes value\n");
        return 1;
    }

    // Reserve space in the vector buffer
    std::ifstream file(argv[2]);

    if (!file.is_open()) {
        printf("Failed to open file\n");
        return 1;
    }

    std::size_t length = std::count(std::istreambuf_iterator<char>(file), std::istreambuf_iterator<char>(), '\n');

    file.close();

    FILE *fp = fopen(argv[2], "r");

    if (!fp) {
        printf("Failed to open file\n");
        return 1;
    }

    std::size_t i, j;
    double val;

    Eigen::SparseMatrix<double> G(num_nodes, num_nodes);
    std::vector<Eigen::Triplet<double>> values;

    values.reserve(length);

    while (fscanf(fp, "%zd, %zd, %le", &i, &j, &val) == 3) {
        values.emplace_back(i, j, val);
    }

    fclose(fp);

    G.setFromTriplets(values.begin(), values.end());
    values.clear();
    G.uncompress(); // Ensure that G is uncompressed to trigger the faulty code

    Eigen::SparseLU<Eigen::SparseMatrix<double>> eigen_solver;

    eigen_solver.compute(G); /// BUG HERE !

    if (eigen_solver.info() != Eigen::ComputationInfo::Success) {
        printf("Computation error\n");
        return 1;
    }

    return 0;
}

Steps to reproduce

Compile the given program with the given flags (g++ -g -fno-omit-frame-pointer -fsanitize=address -I /path/to/eigen)
Run the program, passing it 118052 as first argument (the size of the matrix) and psm_G.txt, a buggy matrix, as second argument: ./program 118052 psm_G.txt
ASAN complains

What is the current bug behavior?

ASAN detects a heap buffer overflow

What is the expected correct behavior?

There shouldn't be a heap buffer overflow

Relevant logs

=================================================================
==2261584==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x712882588ca0 at pc 0x64e72c20c25f bp 0x7ffee9de08f0 sp 0x7ffee9de08e0
WRITE of size 4 at 0x712882588ca0 thread T0
    #0 0x64e72c20c25e in Eigen::internal::assign_op<int, int>::assignCoeff(int&, int const&) const eigen/Eigen/src/Core/functors/AssignmentFunctors.h:26
    #1 0x64e72c20c0db in Eigen::internal::generic_dense_assignment_kernel<Eigen::internal::evaluator<Eigen::Map<Eigen::Matrix<int, -1, 1, 0, -1, 1>, 0, Eigen::Stride<0, 0> > >, Eigen::internal::evaluator<Eigen::Map<Eigen::Matrix<int, -1, 1, 0, -1, 1>, 0, Eigen::Stride<0, 0> > >, Eigen::internal::assign_op<int, int>, 0>::assignCoeff(long) eigen/Eigen/src/Core/AssignEvaluator.h:694
    #2 0x64e72c20246d in void Eigen::internal::unaligned_dense_assignment_loop<Eigen::internal::eigen_packet_wrapper<long long __vector(2), 0>, 16, 0, false, false>::run<Eigen::internal::generic_dense_assignment_kernel<Eigen::internal::evaluator<Eigen::Map<Eigen::Matrix<int, -1, 1, 0, -1, 1>, 0, Eigen::Stride<0, 0> > >, Eigen::internal::evaluator<Eigen::Map<Eigen::Matrix<int, -1, 1, 0, -1, 1>, 0, Eigen::Stride<0, 0> > >, Eigen::internal::assign_op<int, int>, 0> >(Eigen::internal::generic_dense_assignment_kernel<Eigen::internal::evaluator<Eigen::Map<Eigen::Matrix<int, -1, 1, 0, -1, 1>, 0, Eigen::Stride<0, 0> > >, Eigen::internal::evaluator<Eigen::Map<Eigen::Matrix<int, -1, 1, 0, -1, 1>, 0, Eigen::Stride<0, 0> > >, Eigen::internal::assign_op<int, int>, 0>&, long, long) eigen/Eigen/src/Core/AssignEvaluator.h:417
    #3 0x64e72c1f26d5 in Eigen::internal::dense_assignment_loop_impl<Eigen::internal::generic_dense_assignment_kernel<Eigen::internal::evaluator<Eigen::Map<Eigen::Matrix<int, -1, 1, 0, -1, 1>, 0, Eigen::Stride<0, 0> > >, Eigen::internal::evaluator<Eigen::Map<Eigen::Matrix<int, -1, 1, 0, -1, 1>, 0, Eigen::Stride<0, 0> > >, Eigen::internal::assign_op<int, int>, 0>, 3, 0>::run(Eigen::internal::generic_dense_assignment_kernel<Eigen::internal::evaluator<Eigen::Map<Eigen::Matrix<int, -1, 1, 0, -1, 1>, 0, Eigen::Stride<0, 0> > >, Eigen::internal::evaluator<Eigen::Map<Eigen::Matrix<int, -1, 1, 0, -1, 1>, 0, Eigen::Stride<0, 0> > >, Eigen::internal::assign_op<int, int>, 0>&) eigen/Eigen/src/Core/AssignEvaluator.h:497
    #4 0x64e72c1e6ceb in Eigen::internal::dense_assignment_loop<Eigen::internal::generic_dense_assignment_kernel<Eigen::internal::evaluator<Eigen::Map<Eigen::Matrix<int, -1, 1, 0, -1, 1>, 0, Eigen::Stride<0, 0> > >, Eigen::internal::evaluator<Eigen::Map<Eigen::Matrix<int, -1, 1, 0, -1, 1>, 0, Eigen::Stride<0, 0> > >, Eigen::internal::assign_op<int, int>, 0>, 3, 0>::run(Eigen::internal::generic_dense_assignment_kernel<Eigen::internal::evaluator<Eigen::Map<Eigen::Matrix<int, -1, 1, 0, -1, 1>, 0, Eigen::Stride<0, 0> > >, Eigen::internal::evaluator<Eigen::Map<Eigen::Matrix<int, -1, 1, 0, -1, 1>, 0, Eigen::Stride<0, 0> > >, Eigen::internal::assign_op<int, int>, 0>&) eigen/Eigen/src/Core/AssignEvaluator.h:324
    #5 0x64e72c1e38ea in void Eigen::internal::call_dense_assignment_loop<Eigen::Map<Eigen::Matrix<int, -1, 1, 0, -1, 1>, 0, Eigen::Stride<0, 0> >, Eigen::Map<Eigen::Matrix<int, -1, 1, 0, -1, 1>, 0, Eigen::Stride<0, 0> >, Eigen::internal::assign_op<int, int> >(Eigen::Map<Eigen::Matrix<int, -1, 1, 0, -1, 1>, 0, Eigen::Stride<0, 0> >&, Eigen::Map<Eigen::Matrix<int, -1, 1, 0, -1, 1>, 0, Eigen::Stride<0, 0> > const&, Eigen::internal::assign_op<int, int> const&) eigen/Eigen/src/Core/AssignEvaluator.h:828
    #6 0x64e72c1e0d87 in Eigen::internal::Assignment<Eigen::Map<Eigen::Matrix<int, -1, 1, 0, -1, 1>, 0, Eigen::Stride<0, 0> >, Eigen::Map<Eigen::Matrix<int, -1, 1, 0, -1, 1>, 0, Eigen::Stride<0, 0> >, Eigen::internal::assign_op<int, int>, Eigen::internal::Dense2Dense, void>::run(Eigen::Map<Eigen::Matrix<int, -1, 1, 0, -1, 1>, 0, Eigen::Stride<0, 0> >&, Eigen::Map<Eigen::Matrix<int, -1, 1, 0, -1, 1>, 0, Eigen::Stride<0, 0> > const&, Eigen::internal::assign_op<int, int> const&) eigen/Eigen/src/Core/AssignEvaluator.h:979
    #7 0x64e72c1dea58 in void Eigen::internal::call_assignment_no_alias<Eigen::Map<Eigen::Matrix<int, -1, 1, 0, -1, 1>, 0, Eigen::Stride<0, 0> >, Eigen::Map<Eigen::Matrix<int, -1, 1, 0, -1, 1>, 0, Eigen::Stride<0, 0> >, Eigen::internal::assign_op<int, int> >(Eigen::Map<Eigen::Matrix<int, -1, 1, 0, -1, 1>, 0, Eigen::Stride<0, 0> >&, Eigen::Map<Eigen::Matrix<int, -1, 1, 0, -1, 1>, 0, Eigen::Stride<0, 0> > const&, Eigen::internal::assign_op<int, int> const&) eigen/Eigen/src/Core/AssignEvaluator.h:920
    #8 0x64e72c1dbdc2 in void Eigen::internal::call_assignment<Eigen::Map<Eigen::Matrix<int, -1, 1, 0, -1, 1>, 0, Eigen::Stride<0, 0> >, Eigen::Map<Eigen::Matrix<int, -1, 1, 0, -1, 1>, 0, Eigen::Stride<0, 0> >, Eigen::internal::assign_op<int, int> >(Eigen::Map<Eigen::Matrix<int, -1, 1, 0, -1, 1>, 0, Eigen::Stride<0, 0> >&, Eigen::Map<Eigen::Matrix<int, -1, 1, 0, -1, 1>, 0, Eigen::Stride<0, 0> > const&, Eigen::internal::assign_op<int, int> const&, std::enable_if<!Eigen::internal::evaluator_assume_aliasing<Eigen::Map<Eigen::Matrix<int, -1, 1, 0, -1, 1>, 0, Eigen::Stride<0, 0> >, Eigen::internal::evaluator_traits<Eigen::Map<Eigen::Matrix<int, -1, 1, 0, -1, 1>, 0, Eigen::Stride<0, 0> > >::Shape>::value, void*>::type) eigen/Eigen/src/Core/AssignEvaluator.h:891
    #9 0x64e72c1d7625 in void Eigen::internal::call_assignment<Eigen::Map<Eigen::Matrix<int, -1, 1, 0, -1, 1>, 0, Eigen::Stride<0, 0> >, Eigen::Map<Eigen::Matrix<int, -1, 1, 0, -1, 1>, 0, Eigen::Stride<0, 0> > >(Eigen::Map<Eigen::Matrix<int, -1, 1, 0, -1, 1>, 0, Eigen::Stride<0, 0> >&, Eigen::Map<Eigen::Matrix<int, -1, 1, 0, -1, 1>, 0, Eigen::Stride<0, 0> > const&) eigen/Eigen/src/Core/AssignEvaluator.h:873
    #10 0x64e72c1d2692 in Eigen::MatrixBase<Eigen::Map<Eigen::Matrix<int, -1, 1, 0, -1, 1>, 0, Eigen::Stride<0, 0> > >::operator=(Eigen::MatrixBase<Eigen::Map<Eigen::Matrix<int, -1, 1, 0, -1, 1>, 0, Eigen::Stride<0, 0> > > const&) eigen/Eigen/src/Core/Assign.h:52
    #11 0x64e72c1c66f8 in Eigen::MapBase<Eigen::Map<Eigen::Matrix<int, -1, 1, 0, -1, 1>, 0, Eigen::Stride<0, 0> >, 1>::operator=(Eigen::MapBase<Eigen::Map<Eigen::Matrix<int, -1, 1, 0, -1, 1>, 0, Eigen::Stride<0, 0> >, 1> const&) eigen/Eigen/src/Core/MapBase.h:266
    #12 0x64e72c1b8dfa in Eigen::Map<Eigen::Matrix<int, -1, 1, 0, -1, 1>, 0, Eigen::Stride<0, 0> >::operator=(Eigen::Map<Eigen::Matrix<int, -1, 1, 0, -1, 1>, 0, Eigen::Stride<0, 0> > const&) eigen/Eigen/src/Core/Map.h:145
    #13 0x64e72c1b19cc in Eigen::SparseLU<Eigen::SparseMatrix<double, 0, int>, Eigen::COLAMDOrdering<int> >::analyzePattern(Eigen::SparseMatrix<double, 0, int> const&) eigen/Eigen/src/SparseLU/SparseLU.h:550
    #14 0x64e72c1adde2 in Eigen::SparseLU<Eigen::SparseMatrix<double, 0, int>, Eigen::COLAMDOrdering<int> >::compute(Eigen::SparseMatrix<double, 0, int> const&) eigen/Eigen/src/SparseLU/SparseLU.h:212
    #15 0x64e72c19f398 in main test.cpp:59
    #16 0x712883c2a1c9 in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58
    #17 0x712883c2a28a in __libc_start_main_impl ../csu/libc-start.c:360
    #18 0x64e72c19eae4 in _start (test+0xfae4) (BuildId: 4df9bf99194e1b33e8bd697da95e82bd5ee3bcee)

0x712882588ca1 is located 0 bytes after 472225-byte region [0x712882515800,0x712882588ca1)
allocated by thread T0 here:
    #0 0x7128844fd9c7 in malloc ../../../../src/libsanitizer/asan/asan_malloc_linux.cpp:69
    #1 0x64e72c1a790f in Eigen::internal::handmade_aligned_malloc(unsigned long, unsigned long) eigen/Eigen/src/Core/util/Memory.h:149
    #2 0x64e72c1a7d9d in Eigen::internal::aligned_malloc(unsigned long) eigen/Eigen/src/Core/util/Memory.h:217
    #3 0x64e72c1b17d3 in Eigen::SparseLU<Eigen::SparseMatrix<double, 0, int>, Eigen::COLAMDOrdering<int> >::analyzePattern(Eigen::SparseMatrix<double, 0, int> const&) eigen/Eigen/src/SparseLU/SparseLU.h:543
    #4 0x64e72c1adde2 in Eigen::SparseLU<Eigen::SparseMatrix<double, 0, int>, Eigen::COLAMDOrdering<int> >::compute(Eigen::SparseMatrix<double, 0, int> const&) eigen/Eigen/src/SparseLU/SparseLU.h:212
    #5 0x64e72c19f398 in main test.cpp:59
    #6 0x712883c2a1c9 in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58
    #7 0x712883c2a28a in __libc_start_main_impl ../csu/libc-start.c:360
    #8 0x64e72c19eae4 in _start (test+0xfae4) (BuildId: 4df9bf99194e1b33e8bd697da95e82bd5ee3bcee)

SUMMARY: AddressSanitizer: heap-buffer-overflow eigen/Eigen/src/Core/functors/AssignmentFunctors.h:26 in Eigen::internal::assign_op<int, int>::assignCoeff(int&, int const&) const
Shadow bytes around the buggy address:
  0x712882588a00: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x712882588a80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x712882588b00: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x712882588b80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x712882588c00: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x712882588c80: 00 00 00 00[01]fa fa fa fa fa fa fa fa fa fa fa
  0x712882588d00: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x712882588d80: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x712882588e00: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x712882588e80: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x712882588f00: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
==2261584==ABORTING

Anything else that might help

I managed to workaround this bug by manually doubling the size given to handmade_aligned_malloc, but this is very hacky and not a proper fix.