bindiff icon indicating copy to clipboard operation
bindiff copied to clipboard

Use STL containers when requiring pointer/iterator stability

Open Muirey03 opened this issue 1 year ago • 1 comments

From https://abseil.io/about/design/btree:

When values are inserted or removed from a B-tree, nodes can be split or merged and values can be moved within and between nodes (for the purpose of maintaining tree balance). This means that when values are inserted or removed from a B-tree container, pointers and iterators to other values in the B-tree can be invalidated. Abseil B-trees therefore do not provide pointer stability or iterator stability - this is in contrast to STL sorted containers that do provide these guarantees.

BinDiff incorrectly relies on pointer stability and iterator stability when using btree data structures in a number of places:

  • indexed_fixed_points_ is a vector of pointers to FixedPointInfos held in a absl::btree_set
  • indexed_flow_graphs1_ and indexed_flow_graphs2_ are vectors of pointers to FlowGraphInfos held in a absl::btree_map
  • Results::DeleteMatches calls histogram_.erase while iterating over histogram_ which is a absl::btree_map, invalidating the iterator

You can see the effects of these incorrect assumptions by manually removing and adding matches in the IDA plugin. You will see duplicate matches appearing and functions being erased from the database entirely.

This PR fixes the issue by replacing the types that depend on pointer/iterator stability with their STL equivalents.

Muirey03 avatar Aug 04 '24 19:08 Muirey03

Thank you for your PR! While replacing Abseil maps/sets with their STL equivalents will fix the issues you mentioned, we deliberately removed all/most uses of STL maps/sets from the code base. It seems we did not read the API contracts carefully enough and there are not enough tests to catch these issues. Let's first fix the obvious deficiency in Results::DeleteMatches() and then debug the others. Switching back to std::map<>/std::set<> is not really a good option for us. We may need to add another indirection by having the containers store pointers instead.

cblichmann avatar Aug 12 '24 14:08 cblichmann