UBsan reports bad downcast

[ryan0270]

Issue Details

When compiled with the clang UB sanitizer I get several reports similar to

/usr/include/CGAL/Arrangement_2/Arrangement_2_iterators.h:486:12: runtime error: downcast of address 0x55a750ad4560 which does not point to an object of type 'const CGAL::I_Filtered_const_iterator<CGAL::internal::In_place_list_const_iterator<CGAL::Arr_face<CGAL::Arr_vertex_base<CGAL::Point_2<CGAL::Epick>>, CGAL::Gps_halfedge_base<CGAL::Arr_segment_2<CGAL::Epick>>, CGAL::Gps_face_base>, std::allocator<CGAL::Arr_face<CGAL::Arr_vertex_base<CGAL::Point_2<CGAL::Epick>>, CGAL::Gps_halfedge_base<CGAL::Arr_segment_2<CGAL::Epick>>, CGAL::Gps_face_base>>>, CGAL::Arrangement_on_surface_2<CGAL::Gps_segment_traits_2<CGAL::Epick, std::vector<CGAL::Point_2<CGAL::Epick>, std::allocator<CGAL::Point_2<CGAL::Epick>>>, CGAL::Arr_segment_traits_2<CGAL::Epick>>, CGAL::Arr_bounded_planar_topology_traits_2<CGAL::Gps_segment_traits_2<CGAL::Epick, std::vector<CGAL::Point_2<CGAL::Epick>, std::allocator<CGAL::Point_2<CGAL::Epick>>>, CGAL::Arr_segment_traits_2<CGAL::Epick>>, CGAL::Gps_default_dcel<CGAL::Gps_segm0x55a750ad4560: note: object is of type 'CGAL::Arr_face<CGAL::Arr_vertex_base<CGAL::Point_2<CGAL::Epick> >, CGAL::Gps_halfedge_base<CGAL::Arr_segment_2<CGAL::Epick> >, CGAL::Gps_face_base>'
 00 00 00 00  d0 73 89 4e a7 55 00 00  01 00 00 00 00 00 00 00  70 45 ad 50 a7 55 00 00  70 45 ad 50

Source Code

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Polygon_2.h>
#include <CGAL/Polygon_with_holes_2.h>
#include <CGAL/Polygon_2_algorithms.h>
#include <CGAL/Boolean_set_operations_2.h>

using CGKernel = CGAL::Exact_predicates_inexact_constructions_kernel;
using CGPoint = CGKernel::Point_2;
using CGPolygon = CGAL::Polygon_2<CGKernel>;
using CGPolygonWithHoles = CGAL::Polygon_with_holes_2<CGKernel>;

auto create_poly_1() -> CGPolygon {
  CGPolygon poly;
  poly.push_back({0, 0});
  poly.push_back({4, 0});
  poly.push_back({4, 4});
  poly.push_back({0, 4});
  return poly;
}

auto create_poly_2() -> CGPolygon {
  CGPolygon poly;
  poly.push_back({2, 2});
  poly.push_back({6, 2});
  poly.push_back({6, 6});
  poly.push_back({2, 6});
  return poly;
}

int main(int, char **) { 
  const auto poly1 = create_poly_1();
  const auto poly2 = create_poly_2();

  CGPolygonWithHoles polyUnion;
  CGAL::join(poly1, poly2, polyUnion);
}

built and run with

clang++ -fsanitize=undefined -lgmp -lmpfr main.cpp && ./a.out

Environment

• Operating system (Windows/Mac/Linux, 32/64 bits): Arch Linux
• Compiler: clang 11.0.0
• Release or debug mode: debug
• Specific flags used (if any): -fsanitize=undefined
• CGAL version: 5.1.1
• Boost version: 1.72.0
• Other libraries versions if used (Eigen, TBB, etc.): gmp 6.2.0 mpfr 4.1.0

[lrineau]

Hi @ryan0270, we will look into that.

@sgiraudot Do you have clang-11 available on your machine?

[sgiraudot]

@lrineau no, sadly it only goes to clang-10 on Linux Mint 20.

[lrineau]

@lrineau no, sadly it only goes to clang-10 on Linux Mint 20.

Maybe UBSan from clang-10 will report the same issue.

[sgiraudot]

It does, I can reproduce the issue, I'm on it.

[sgiraudot]

Ok, so I think I identified the first problem, and it seems to be quite deep in the structure of Arrangement_2:

• the HDS is hold by the traits classes which instantiates objects of type Arr_face, Arr_vertex, etc.
• Arrangement_on_surface_2 defines derived classes in a mechanism that amount to do class Face : public Arr_face
• no object of these derived classes are actually instantiated, Arrangement_on_surface_2 just statically casts Arr_face* to Arrangement_on_surface_2::Arr_face* (the core of the problem is this line)
• in theory, this is undefined behavior as the objects casted are not actually of the casted type (they are from the base class)
• this is confirmed by replacing static_cast by dynamic_cast: the resulting pointer is nullptr
• in practise, it doesn't create problems/bugs because the derived classes only defines new functions, not new variables (so it just changes the behavior of the object, not its content - which could create a segfault)

A simplified example of what's going on:

#include <iostream>

struct A
{
  virtual ~A() { }
  int m_value = 42;
};

struct B : public A
{
  int value() const { return m_value; }
};

int main()
{
  A* a = new A;

  B* b_dynamic = dynamic_cast<B*>(a);
  if (b_dynamic)
    std::cerr << "b_dynamic->value() = " << b_dynamic->value() << std::endl;
  else
    std::cerr << "b_dynamic = nullptr" << std::endl;

  B* b_static = static_cast<B*>(a);
  std::cerr << "b_static->value() = " << b_static->value() << std::endl;

  return EXIT_SUCCESS;
}

The output of this program is:

b_dynamic = nullptr
b_static->value() = 42

So it does work in practise, but of course, if I run the UB sanitizer, an error is raised on the static cast.

@efifogel I'd like to have your opinion on this. Is there a reason why this mechanism (base class in traits + static cast to derived class in the Arrangement_on_surface_2) is used? I see that it allows you to block access to some functions of the base class from the public API: is this the only reason?

I can't see how we can pass the UB sanitizer without reorganizing the HDS in Arrangement quite deeply.

[MattC11]

What is the likelyhood of this getting fixed? We are going to have to have to suppress address sanitizer warning for this library, which isn't ideal because if there are true issues we will miss them.

[sloriot]

@efifogel did you see Simon's mention? do you have an opinion?

[sloriot]

Postponed to 6.0-beta. @efifogel could you look at SImon's comment and let us know if you see a fix?

[tylermorganwall]

I am also encountering this issue, which appears in several files:

Arrangement_2_iterators.h Arrangement_on_surface_2_impl.h Arr_construction_ss_visitor.h Gps_bfs_scanner.h Arr_walk_along_line_pl_impl.h

The compilation output (with warnings) is here:

https://www.stats.ox.ac.uk/pub/bdr/memtests/clang-UBSAN/raybevel/raybevel-Ex.Rout

[sloriot]

Should be fixed by https://github.com/CGAL/cgal/pull/7927 that is currently in master branch.

[lrineau]

Should be fixed by #7927 that is currently in master branch.

Should we close this issue, now that the PR #7927 is merged?