[Boost-bugs] [Boost C++ Libraries] #13210: Signed integer overflow in successive_shortest_path_nonnegative_weights()

Subject: [Boost-bugs] [Boost C++ Libraries] #13210: Signed integer overflow in successive_shortest_path_nonnegative_weights()
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2017-09-13 20:33:09

#13210: Signed integer overflow in successive_shortest_path_nonnegative_weights()
-------------------------------------+-------------------------------
 Reporter:  grievejia@…              |      Owner:  Jeremiah Willcock
     Type:  Bugs                     |     Status:  new
Milestone:  To Be Determined         |  Component:  graph
  Version:  Boost Development Trunk  |   Severity:  Problem
 Keywords:                           |
-------------------------------------+-------------------------------
 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.

-- 
Ticket URL: <https://svn.boost.org/trac10/boost/ticket/13210>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.