id,summary,reporter,owner,description,type,status,milestone,component,version,severity,resolution,keywords,cc
13210,Signed integer overflow in successive_shortest_path_nonnegative_weights(),grievejia@…,Jeremiah Willcock,"Buiding and running the following program with UndefinedBehaviorSanitizer will generate a report on signed integer overflow error:
{{{
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/read_dimacs.hpp>
#include <boost/graph/successive_shortest_path_nonnegative_weights.hpp>
#include <iostream>

using namespace boost;

using Traits = adjacency_list_traits<vecS, vecS, directedS>;
using Graph = adjacency_list<
    vecS, vecS, directedS, no_property,
    property<edge_capacity_t, int,
             property<edge_residual_capacity_t, int,
                      property<edge_reverse_t, Traits::edge_descriptor,
                               property<edge_weight_t, int>>>>>;

template <typename Map, typename Edge>
void fill_capacity(Map &m, Edge e, Edge er, int c) {
  put(m, e, c);
  put(m, er, 0);
}

template <typename Map, typename Edge> void fill_rev(Map &m, Edge e, Edge er) {
  put(m, e, er);
  put(m, er, e);
}

template <typename Map, typename Edge>
void fill_weight(Map &m, Edge e, Edge er, int w) {
  put(m, e, w);
  put(m, er, -w);
}

int main() {
  Graph g(4);
  auto capacity = get(edge_capacity, g);
  auto rev = get(edge_reverse, g);
  auto weight = get(edge_weight, g);

  auto e0 = add_edge(0, 1, g).first;
  auto e0r = add_edge(1, 0, g).first;
  auto e1 = add_edge(0, 2, g).first;
  auto e1r = add_edge(2, 0, g).first;
  auto e2 = add_edge(1, 2, g).first;
  auto e2r = add_edge(2, 1, g).first;

  // What the weights and capacities are don't really matter as long as they are all positive
  fill_capacity(capacity, e0, e0r, 1);
  fill_capacity(capacity, e1, e1r, 1);
  fill_capacity(capacity, e2, e2r, 1);
  fill_rev(rev, e0, e0r);
  fill_rev(rev, e1, e1r);
  fill_rev(rev, e2, e2r);
  fill_weight(weight, e0, e0r, 1);
  fill_weight(weight, e1, e1r, 1);
  fill_weight(weight, e2, e2r, 1);

  successive_shortest_path_nonnegative_weights(g, 0, 2);
}
}}}
Here's the stacktrace collected by UBSan (simplified for readability):
{{{
/usr/include/boost/graph/successive_shortest_path_nonnegative_weights.hpp:104:57: runtime error: signed integer overflow: 2147483647 + 2147483647 cannot be represented in type 'int'
    #0 0x43fccd in void boost::successive_shortest_path_nonnegative_weights<...>(...) /usr/include/boost/graph/successive_shortest_path_nonnegative_weights.hpp:104:57
    #1 0x43d7dc in void boost::detail::successive_shortest_path_nonnegative_weights_dispatch3<...>(...) /usr/include/boost/graph/successive_shortest_path_nonnegative_weights.hpp:148:5
    #2 0x43bf40 in void boost::detail::successive_shortest_path_nonnegative_weights_dispatch2<...>(...) /usr/include/boost/graph/successive_shortest_path_nonnegative_weights.hpp:186:5
    #3 0x43b2ba in void boost::detail::successive_shortest_path_nonnegative_weights_dispatch1<...>(...) /usr/include/boost/graph/successive_shortest_path_nonnegative_weights.hpp:223:5
    #4 0x43b018 in void boost::successive_shortest_path_nonnegative_weights<boost::adjacency_list<...>, int, boost::buffer_param_t, boost::no_property>(...) /usr/include/boost/graph/successive_shortest_path_nonnegative_weights.hpp:238:12
    #5 0x42b046 in void boost::successive_shortest_path_nonnegative_weights<...>(boost::adjacency_list<...>&, boost::graph_traits<...>::vertex_descriptor, boost::graph_traits<...>::vertex_descriptor) /usr/include/boost/graph/successive_shortest_path_nonnegative_weights.hpp:255:5
    #6 0x42a520 in main /home/grieve/Research/Testing/boost/reduced.cpp:56:3
    #7 0x7f7cb22e3f69 in __libc_start_main (/usr/lib/libc.so.6+0x20f69)
    #8 0x4039b9 in _start (/home/grieve/Research/Testing/boost/reduced+0x4039b9)
}}}
The problem here is that function successive_shortest_path_nonnegative_weights() does not take into account the fact that its input graph might be disconnected and therefore it is possible for some shortest path distances to be infinity.",Bugs,new,To Be Determined,graph,Boost Development Trunk,Problem,,,