Out of bounds vector access

[jamesjer]

I'm working off the code in the README to understand how sassy works. Consider this simple bit of code:

#include <sassy/preprocessor.h>

static void
hook_function(int n, const int *p, int nsupp, const int *supp)
{
  static int symmetry = 0;
  std::cout << "Symmetry " << ++symmetry << '\n';
  for (int j = 0; j < nsupp; ++j) {
    const int i = supp[j];
    std::cout << i << " -> " << p[i] << '\n';
  }
}

int
main(int argc, char *argv[])
{
  // Create the sassy graph
  sassy::static_graph g;
  g.initialize_graph(8, 12); // 8 vertices, 12 edges
  const int v0 = g.add_vertex(0, 2);
  const int v1 = g.add_vertex(0, 2);
  const int v2 = g.add_vertex(0, 4);
  const int v3 = g.add_vertex(0, 4);
  const int v4 = g.add_vertex(0, 4);
  const int v5 = g.add_vertex(0, 4);
  const int v6 = g.add_vertex(0, 2);
  const int v7 = g.add_vertex(0, 2);
  g.add_edge(v0, v1);
  g.add_edge(v0, v2);
  g.add_edge(v1, v3);
  g.add_edge(v2, v3);
  g.add_edge(v2, v4);
  g.add_edge(v2, v5);
  g.add_edge(v3, v4);
  g.add_edge(v3, v5);
  g.add_edge(v4, v5);
  g.add_edge(v4, v6);
  g.add_edge(v5, v7);
  g.add_edge(v6, v7);

  // Prepare the hook function
  auto hook = sassy::sassy_hook(hook_function);

  // Preprocess the graph
  sassy::preprocessor p;
  p.reduce(&g, &hook);
  return 0;
}

If I build that on a Linux machine with C++ library assertions enable, like so:

g++ -O1 -g3 -pipe -D_GLIBCXX_ASSERTIONS -o test test.cxx

then we get an assertion due to an out-of-bounds vector access:

/usr/include/c++/14/bits/stl_vector.h:1127: std::vector<_Tp, _Alloc>::reference std::vector<_Tp, _Alloc>::operator[](size_type) [with _Tp = std::pair<int, int>; _Alloc = std::allocator<std::pair<int, int> >; reference = std::pair<int, int>&; size_type = long unsigned int]: Assertion '__n < this->size()' failed.
Aborted (core dumped)

Running under GDB shows:

Program received signal SIGABRT, Aborted.
__pthread_kill_implementation (threadid=<optimized out>, signo=signo@entry=6, no_tid=no_tid@entry=0)
    at pthread_kill.c:44
44            return INTERNAL_SYSCALL_ERROR_P (ret) ? INTERNAL_SYSCALL_ERRNO (ret) : 0;                                 
(gdb) bt
#0  __pthread_kill_implementation (threadid=<optimized out>, signo=signo@entry=6, no_tid=no_tid@entry=0)
    at pthread_kill.c:44
#1  0x00007ffff7aaa183 in __pthread_kill_internal (threadid=<optimized out>, signo=6) at pthread_kill.c:78
#2  0x00007ffff7a5267e in __GI_raise (sig=sig@entry=6) at ../sysdeps/posix/raise.c:26
#3  0x00007ffff7a3a93f in __GI_abort () at abort.c:79
#4  0x00007ffff7cd9da0 in std::__glibcxx_assert_fail (
    file=file@entry=0x425048 "/usr/include/c++/14/bits/stl_vector.h", line=line@entry=1127, 
    function=function@entry=0x4252b0 "std::vector<_Tp, _Alloc>::reference std::vector<_Tp, _Alloc>::operator[](size_type) [with _Tp = std::pair<int, int>; _Alloc = std::allocator<std::pair<int, int> >; reference = std::pair<int, int>&; si"..., condition=condition@entry=0x42419a "__n < this->size()") at ../../../../../libstdc++-v3/src/c++11/assert_fail.cc:41
#5  0x0000000000406dbf in std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > >::operator[] (
    this=<optimized out>, __n=<optimized out>) at /usr/include/c++/14/bits/stl_vector.h:1127
#6  0x000000000041df2a in sassy::preprocessor::sparse_ir_probe_sz2_quotient_components(sassy::sgraph_t<int, int, int>*, int*, std::function<void (int, int const*, int, int const*)> const*, int) (this=this@entry=0x7fffffffddb0, 
    g=g@entry=0x7fffffffe2b0, colmap=colmap@entry=0x43e380, consume=consume@entry=0x7fffffffe290, 
    num_paths=num_paths@entry=8)
    at /builddir/build/BUILDROOT/sassy-0-1.20230610git9847fa1.fc41.x86_64/usr/include/sassy/preprocessor.h:3537
#7  0x00000000004239c7 in sassy::preprocessor::reduce(sassy::sgraph_t<int, int, int>*, int*, std::function<void (int, int const*, int, int const*)> const*, std::vector<sassy::preop, std::allocator<sassy::preop> > const*) (
    this=this@entry=0x7fffffffddb0, g=g@entry=0x7fffffffe2b0, colmap=0x43e380, hook=hook@entry=0x7fffffffe290, 
    schedule=0x7fffffffdc60, schedule@entry=0x0)
    at /builddir/build/BUILDROOT/sassy-0-1.20230610git9847fa1.fc41.x86_64/usr/include/sassy/preprocessor.h:4807
#8  0x0000000000402fd0 in sassy::preprocessor::reduce(sassy::static_graph*, std::function<void (int, int const*, int, int const*)> const*, std::vector<sassy::preop, std::allocator<sassy::preop> >*) (this=0x7fffffffddb0, g=0x7fffffffe2b0, 
    hook=0x7fffffffe290, schedule=0x0)
    at /builddir/build/BUILDROOT/sassy-0-1.20230610git9847fa1.fc41.x86_64/usr/include/sassy/preprocessor.h:4628
#9  main (argc=<optimized out>, argv=<optimized out>) at test.cxx:46

The out-of-bounds access appears to be in frame 6, so:

(gdb) frame 6
#6  0x000000000041df2a in sassy::preprocessor::sparse_ir_probe_sz2_quotient_components(sassy::sgraph_t<int, int, int>*, int*, std::function<void (int, int const*, int, int const*)> const*, int) (this=this@entry=0x7fffffffddb0, 
    g=g@entry=0x7fffffffe2b0, colmap=colmap@entry=0x43e380, consume=consume@entry=0x7fffffffe290, 
    num_paths=num_paths@entry=8)
    at /builddir/build/BUILDROOT/sassy-0-1.20230610git9847fa1.fc41.x86_64/usr/include/sassy/preprocessor.h:3537
3537	                    quotient_component_end_pos = quotient_component_worklist_boundary[component].first;
(gdb) print quotient_component_worklist_boundary
$1 = std::vector of length 1, capacity 64 = {{first = 2, second = 8}}
(gdb) print component
$2 = 1

The vector quotient_component_worklist_boundary has only 1 element, so only index 0 is valid, but the code tries to access index 1.

[markusa4]

Thanks a lot for catching this! It should be fixed. It appears to me this always occured in the last iteration of the surrounding while-loop, and the accessed value should have never been used.

In any case, I do want to mention that I am mostly planning on fixing issues in this repository, whereas the newest version of the preprocessor is contained over here:
https://github.com/markusa4/dejavu

(In particular, I removed the troublesome functions of this issue quite a while ago.)

[jamesjer]

Thank you for the rapid response. Let me fill you in on what's going on. I recently added SoPlex and SCIP as packages to the Fedora Linux distribution. They will be available when Fedora 40 is released in about a month. I'm working on updating SCIP from version 8.1.0 to 9.0.0. The Fedora project frowns on bundling one package inside another. Since SCIP 9.0.0 contains a copy of sassy, I am working to make sassy a package in its own right. We like to have tests to run for our packages, in case we break something during the packaging process. Since sassy does not have any tests, I am trying to write a few; nothing fancy, just simple sanity tests.

If SCIP switches to dejavu, then I will package that and retire the sassy package.

Thank you again for responding so quickly.

[markusa4]

I see, thank you for that! Feel free to contact me, I am happy to help out in the process.