Core graph Filter reads vector<bool>beyond boundaries

[mloskot]

Version: 5.12.0 and current master

During contraction step of the data processing, I observe situation which may indicate a bug, somewhere.
I'm hoping to explain it clearly enough:

The osrm::contractor::contractExcludableGraph function applies this filtering

shared_core_graph = contractor_graph.Filter(
            [&is_shared_core](const NodeID node) { return is_shared_core[node]; });

where the Filter is this

template <typename Pred> auto Filter(Pred filter) const &
{
    DynamicGraph other;

    other.number_of_nodes = number_of_nodes;
    other.number_of_edges = static_cast<std::uint32_t>(number_of_edges);
    other.edge_list.reserve(edge_list.size());
    other.node_array.resize(node_array.size());

    NodeID node_id = 0;
    std::transform(
        node_array.begin(), node_array.end(), other.node_array.begin(), [&](const Node &node) {
            const EdgeIterator first_edge = other.edge_list.size();
            if (filter(node_id++))
            {
            ...
            }
    ...

Inside Filter, I see

• is_shared_core.size() == 16142
• number_of_nodes == 16142
• node_array.size() == 16143

and eventually, if (filter(16142)) is tested leading to is_shared_core out of range access.

This can be easily reproduced with

BOOST_ASSERT(node_array.size() == number_of_nodes);

placed in the beginning of the Filter function.

So, with this print-based-debugging patch:

$ git diff
diff --git a/include/util/dynamic_graph.hpp b/include/util/dynamic_graph.hpp
index cfc661f..e39d16f 100644
--- a/include/util/dynamic_graph.hpp
+++ b/include/util/dynamic_graph.hpp
@@ -18,6 +18,8 @@
 #include <tuple>
 #include <vector>

+#include <iostream>
+
 namespace osrm
 {
 namespace util
@@ -191,6 +193,13 @@ template <typename EdgeDataT> class DynamicGraph
     // Removes all edges to and from nodes for which filter(node_id) returns false
     template <typename Pred> auto Filter(Pred filter) const &
     {
+        std::cout << "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX\n"
+            << node_array.size()
+            << ", "
+            << number_of_nodes
+            << std::endl;
+        BOOST_ASSERT(node_array.size() == number_of_nodes);
+
         DynamicGraph other;

         other.number_of_nodes = number_of_nodes;

I see the difference in sizes too:

~/dev/osrm-backend/build$ ./unit_tests/util-tests
Running 115 test cases...
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
6, 5

*** No errors detected

That is optimised build, so the assert does not make the test crash, but shouldn't it fail.

[TheMarex]

@mloskot You are right this is a off-by-one since the node_array will sometimes contain a (superfluous) sentinel node.

Apart from crashes I don't think this should trigger any bugs, since we never rely on the presence of that sentinel node. I will prepare a fix for this and include it in a bug fix release. Thanks for spotting this. 💯

[mloskot]

@TheMarex I see. Thanks for the fix anyway.