Unitialized boolean vectors make UBSan unhappy

[gergondet-woven]

Hello folks,

I have encountered a problem with the undefined behaviors sanitizer when running our test suite against it.

Here is a program that will trigger the issue (both in 0.6.5 and current main)

#include <iostream>
#include <optional>

#include <Eigen/Core>
#include <proxsuite/proxqp/dense/dense.hpp>
#include <proxsuite/proxqp/sparse/sparse.hpp>
#include <proxsuite/proxqp/utils/random_qp_problems.hpp>

using namespace proxsuite;
using namespace proxsuite::proxqp;
using T = double;

int main() {
  using SolverT = proxsuite::proxqp::dense::QP<double>;
  using HessianType = proxsuite::proxqp::HessianType;
  using DenseBackend = proxsuite::proxqp::DenseBackend;
  SolverT solver_ = SolverT(3, 0, 1, /* box constraints */ false, HessianType::Dense,
                            DenseBackend::PrimalDualLDLT);
  solver_.settings.compute_timings = true;
  Eigen::Vector3d desired_vel(1.2, 1.3, 1.7);
  Eigen::Vector3d w_ = Eigen::Vector3d{1, 1, 3.14};
  Eigen::Vector3d c_ = w_.cwiseProduct(-desired_vel);
  Eigen::Matrix<double, -1, 3> C_ = Eigen::Matrix<double, -1, 3>::Zero(1, 3);
  C_.row(0) = Eigen::Vector3d(-0.707107, -0.707107, 0.0);
  Eigen::VectorXd l_ = Eigen::VectorXd::Zero(1);
  solver_.init(w_.asDiagonal().toDenseMatrix(), c_, std::nullopt, std::nullopt, C_, l_,
               std::nullopt);
  solver_.solve(desired_vel, std::nullopt, std::nullopt);
  auto result = solver_.results.x;
  std::cout << "result: " << result.transpose() << "\n";
  return 0;
}

You can compile this with the following CMake:

cmake_minimum_required(VERSION 3.1)

set(CMAKE_CXX_STANDARD 17)

project(sample LANGUAGES CXX)

find_package(proxsuite REQUIRED)

add_library(sanitizers INTERFACE)
set(SANITIZERS_OPTIONS -fno-omit-frame-pointer
                       -fsanitize=address,undefined,leak)
target_compile_options(sanitizers INTERFACE ${SANITIZERS_OPTIONS})
target_link_options(sanitizers INTERFACE ${SANITIZERS_OPTIONS})

add_executable(sample sample.cpp)
target_link_libraries(sample PUBLIC proxsuite::proxsuite sanitizers)

This will output something like this:

/usr/include/eigen3/Eigen/src/Core/CoreEvaluators.h:1264:5: runtime error: load of value 190, which is not a valid value for type 'bool'
    #0 0x55c3dec7427e in Eigen::internal::evaluator<Eigen::Select<Eigen::Block<Eigen::Matrix<bool, -1, 1, 0, -1, 1>, -1, 1, false>, Eigen::Block<Eigen::Matrix<double, -1, 1, 0, -1, 1>, -1, 1, false>, Eigen::CwiseNullaryOp<Eigen::internal::scalar_constant_op<double>, Eigen::Matrix<double, -1, 1, 0, -1, 1> > > >::coeff(long, long) const /usr/include/eigen3/Eigen/src/Core/CoreEvaluators.h:1264
    #1 0x55c3dec12088 in Eigen::internal::binary_evaluator<Eigen::CwiseBinaryOp<Eigen::internal::scalar_conj_product_op<double, double>, Eigen::Select<Eigen::Block<Eigen::Matrix<bool, -1, 1, 0, -1, 1>, -1, 1, false>, Eigen::Block<Eigen::Matrix<double, -1, 1, 0, -1, 1>, -1, 1, false>, Eigen::CwiseNullaryOp<Eigen::internal::scalar_constant_op<double>, Eigen::Matrix<double, -1, 1, 0, -1, 1> > > const, Eigen::Select<Eigen::CwiseBinaryOp<Eigen::internal::scalar_cmp_op<double, double, (Eigen::internal::ComparisonName)1>, Eigen::ArrayWrapper<Eigen::Matrix<double, -1, 1, 0, -1, 1> const> const, Eigen::CwiseNullaryOp<Eigen::internal::scalar_constant_op<double>, Eigen::Array<double, -1, 1, 0, -1, 1> > const>, Eigen::Matrix<double, -1, 1, 0, -1, 1>, Eigen::CwiseNullaryOp<Eigen::internal::scalar_constant_op<double>, Eigen::Matrix<double, -1, 1, 0, -1, 1> > > const>, Eigen::internal::IndexBased, Eigen::internal::IndexBased, double, double>::coeff(long, long) const /usr/include/eigen3/Eigen/src/Core/CoreEvaluators.h:769
    #2 0x55c3debbcead in Eigen::internal::redux_evaluator<Eigen::CwiseBinaryOp<Eigen::internal::scalar_conj_product_op<double, double>, Eigen::Select<Eigen::Block<Eigen::Matrix<bool, -1, 1, 0, -1, 1>, -1, 1, false>, Eigen::Block<Eigen::Matrix<double, -1, 1, 0, -1, 1>, -1, 1, false>, Eigen::CwiseNullaryOp<Eigen::internal::scalar_constant_op<double>, Eigen::Matrix<double, -1, 1, 0, -1, 1> > > const, Eigen::Select<Eigen::CwiseBinaryOp<Eigen::internal::scalar_cmp_op<double, double, (Eigen::internal::ComparisonName)1>, Eigen::ArrayWrapper<Eigen::Matrix<double, -1, 1, 0, -1, 1> const> const, Eigen::CwiseNullaryOp<Eigen::internal::scalar_constant_op<double>, Eigen::Array<double, -1, 1, 0, -1, 1> > const>, Eigen::Matrix<double, -1, 1, 0, -1, 1>, Eigen::CwiseNullaryOp<Eigen::internal::scalar_constant_op<double>, Eigen::Matrix<double, -1, 1, 0, -1, 1> > > const> >::coeffByOuterInner(long, long) const /usr/include/eigen3/Eigen/src/Core/Redux.h:381
    #3 0x55c3deb82167 in double Eigen::internal::redux_impl<Eigen::internal::scalar_sum_op<double, double>, Eigen::internal::redux_evaluator<Eigen::CwiseBinaryOp<Eigen::internal::scalar_conj_product_op<double, double>, Eigen::Select<Eigen::Block<Eigen::Matrix<bool, -1, 1, 0, -1, 1>, -1, 1, false>, Eigen::Block<Eigen::Matrix<double, -1, 1, 0, -1, 1>, -1, 1, false>, Eigen::CwiseNullaryOp<Eigen::internal::scalar_constant_op<double>, Eigen::Matrix<double, -1, 1, 0, -1, 1> > > const, Eigen::Select<Eigen::CwiseBinaryOp<Eigen::internal::scalar_cmp_op<double, double, (Eigen::internal::ComparisonName)1>, Eigen::ArrayWrapper<Eigen::Matrix<double, -1, 1, 0, -1, 1> const> const, Eigen::CwiseNullaryOp<Eigen::internal::scalar_constant_op<double>, Eigen::Array<double, -1, 1, 0, -1, 1> > const>, Eigen::Matrix<double, -1, 1, 0, -1, 1>, Eigen::CwiseNullaryOp<Eigen::internal::scalar_constant_op<double>, Eigen::Matrix<double, -1, 1, 0, -1, 1> > > const> >, 0, 0>::run<Eigen::CwiseBinaryOp<Eigen::internal::scalar_conj_product_op<double, double>, Eigen::Select<Eigen::Block<Eigen::Matrix<bool, -1, 1, 0, -1, 1>, -1, 1, false>, Eigen::Block<Eigen::Matrix<double, -1, 1, 0, -1, 1>, -1, 1, false>, Eigen::CwiseNullaryOp<Eigen::internal::scalar_constant_op<double>, Eigen::Matrix<double, -1, 1, 0, -1, 1> > > const, Eigen::Select<Eigen::CwiseBinaryOp<Eigen::internal::scalar_cmp_op<double, double, (Eigen::internal::ComparisonName)1>, Eigen::ArrayWrapper<Eigen::Matrix<double, -1, 1, 0, -1, 1> const> const, Eigen::CwiseNullaryOp<Eigen::internal::scalar_constant_op<double>, Eigen::Array<double, -1, 1, 0, -1, 1> > const>, Eigen::Matrix<double, -1, 1, 0, -1, 1>, Eigen::CwiseNullaryOp<Eigen::internal::scalar_constant_op<double>, Eigen::Matrix<double, -1, 1, 0, -1, 1> > > const> >(Eigen::internal::redux_evaluator<Eigen::CwiseBinaryOp<Eigen::internal::scalar_conj_product_op<double, double>, Eigen::Select<Eigen::Block<Eigen::Matrix<bool, -1, 1, 0, -1, 1>, -1, 1, false>, Eigen::Block<Eigen::Matrix<double, -1, 1, 0, -1, 1>, -1, 1, false>, Eigen::CwiseNullaryOp<Eigen::internal::scalar_constant_op<double>, Eigen::Matrix<double, -1, 1, 0, -1, 1> > > const, Eigen::Select<Eigen::CwiseBinaryOp<Eigen::internal::scalar_cmp_op<double, double, (Eigen::internal::ComparisonName)1>, Eigen::ArrayWrapper<Eigen::Matrix<double, -1, 1, 0, -1, 1> const> const, Eigen::CwiseNullaryOp<Eigen::internal::scalar_constant_op<double>, Eigen::Array<double, -1, 1, 0, -1, 1> > const>, Eigen::Matrix<double, -1, 1, 0, -1, 1>, Eigen::CwiseNullaryOp<Eigen::internal::scalar_constant_op<double>, Eigen::Matrix<double, -1, 1, 0, -1, 1> > > const> > const&, Eigen::internal::scalar_sum_op<double, double> const&, Eigen::CwiseBinaryOp<Eigen::internal::scalar_conj_product_op<double, double>, Eigen::Select<Eigen::Block<Eigen::Matrix<bool, -1, 1, 0, -1, 1>, -1, 1, false>, Eigen::Block<Eigen::Matrix<double, -1, 1, 0, -1, 1>, -1, 1, false>, Eigen::CwiseNullaryOp<Eigen::internal::scalar_constant_op<double>, Eigen::Matrix<double, -1, 1, 0, -1, 1> > > const, Eigen::Select<Eigen::CwiseBinaryOp<Eigen::internal::scalar_cmp_op<double, double, (Eigen::internal::ComparisonName)1>, Eigen::ArrayWrapper<Eigen::Matrix<double, -1, 1, 0, -1, 1> const> const, Eigen::CwiseNullaryOp<Eigen::internal::scalar_constant_op<double>, Eigen::Array<double, -1, 1, 0, -1, 1> > const>, Eigen::Matrix<double, -1, 1, 0, -1, 1>, Eigen::CwiseNullaryOp<Eigen::internal::scalar_constant_op<double>, Eigen::Matrix<double, -1, 1, 0, -1, 1> > > const> const&) /usr/include/eigen3/Eigen/src/Core/Redux.h:202
    #4 0x55c3deb4f07a in double Eigen::DenseBase<Eigen::CwiseBinaryOp<Eigen::internal::scalar_conj_product_op<double, double>, Eigen::Select<Eigen::Block<Eigen::Matrix<bool, -1, 1, 0, -1, 1>, -1, 1, false>, Eigen::Block<Eigen::Matrix<double, -1, 1, 0, -1, 1>, -1, 1, false>, Eigen::CwiseNullaryOp<Eigen::internal::scalar_constant_op<double>, Eigen::Matrix<double, -1, 1, 0, -1, 1> > > const, Eigen::Select<Eigen::CwiseBinaryOp<Eigen::internal::scalar_cmp_op<double, double, (Eigen::internal::ComparisonName)1>, Eigen::ArrayWrapper<Eigen::Matrix<double, -1, 1, 0, -1, 1> const> const, Eigen::CwiseNullaryOp<Eigen::internal::scalar_constant_op<double>, Eigen::Array<double, -1, 1, 0, -1, 1> > const>, Eigen::Matrix<double, -1, 1, 0, -1, 1>, Eigen::CwiseNullaryOp<Eigen::internal::scalar_constant_op<double>, Eigen::Matrix<double, -1, 1, 0, -1, 1> > > const> >::redux<Eigen::internal::scalar_sum_op<double, double> >(Eigen::internal::scalar_sum_op<double, double> const&) const /usr/include/eigen3/Eigen/src/Core/Redux.h:418
    #5 0x55c3deb1dbba in Eigen::DenseBase<Eigen::CwiseBinaryOp<Eigen::internal::scalar_conj_product_op<double, double>, Eigen::Select<Eigen::Block<Eigen::Matrix<bool, -1, 1, 0, -1, 1>, -1, 1, false>, Eigen::Block<Eigen::Matrix<double, -1, 1, 0, -1, 1>, -1, 1, false>, Eigen::CwiseNullaryOp<Eigen::internal::scalar_constant_op<double>, Eigen::Matrix<double, -1, 1, 0, -1, 1> > > const, Eigen::Select<Eigen::CwiseBinaryOp<Eigen::internal::scalar_cmp_op<double, double, (Eigen::internal::ComparisonName)1>, Eigen::ArrayWrapper<Eigen::Matrix<double, -1, 1, 0, -1, 1> const> const, Eigen::CwiseNullaryOp<Eigen::internal::scalar_constant_op<double>, Eigen::Array<double, -1, 1, 0, -1, 1> > const>, Eigen::Matrix<double, -1, 1, 0, -1, 1>, Eigen::CwiseNullaryOp<Eigen::internal::scalar_constant_op<double>, Eigen::Matrix<double, -1, 1, 0, -1, 1> > > const> >::sum() const /usr/include/eigen3/Eigen/src/Core/Redux.h:463
    #6 0x55c3dead9ba3 in Eigen::internal::dot_nocheck<Eigen::Select<Eigen::Block<Eigen::Matrix<bool, -1, 1, 0, -1, 1>, -1, 1, false>, Eigen::Block<Eigen::Matrix<double, -1, 1, 0, -1, 1>, -1, 1, false>, Eigen::CwiseNullaryOp<Eigen::internal::scalar_constant_op<double>, Eigen::Matrix<double, -1, 1, 0, -1, 1> > >, Eigen::Select<Eigen::CwiseBinaryOp<Eigen::internal::scalar_cmp_op<double, double, (Eigen::internal::ComparisonName)1>, Eigen::ArrayWrapper<Eigen::Matrix<double, -1, 1, 0, -1, 1> const> const, Eigen::CwiseNullaryOp<Eigen::internal::scalar_constant_op<double>, Eigen::Array<double, -1, 1, 0, -1, 1> > const>, Eigen::Matrix<double, -1, 1, 0, -1, 1>, Eigen::CwiseNullaryOp<Eigen::internal::scalar_constant_op<double>, Eigen::Matrix<double, -1, 1, 0, -1, 1> > >, false>::run(Eigen::MatrixBase<Eigen::Select<Eigen::Block<Eigen::Matrix<bool, -1, 1, 0, -1, 1>, -1, 1, false>, Eigen::Block<Eigen::Matrix<double, -1, 1, 0, -1, 1>, -1, 1, false>, Eigen::CwiseNullaryOp<Eigen::internal::scalar_constant_op<double>, Eigen::Matrix<double, -1, 1, 0, -1, 1> > > > const&, Eigen::MatrixBase<Eigen::Select<Eigen::CwiseBinaryOp<Eigen::internal::scalar_cmp_op<double, double, (Eigen::internal::ComparisonName)1>, Eigen::ArrayWrapper<Eigen::Matrix<double, -1, 1, 0, -1, 1> const> const, Eigen::CwiseNullaryOp<Eigen::internal::scalar_constant_op<double>, Eigen::Array<double, -1, 1, 0, -1, 1> > const>, Eigen::Matrix<double, -1, 1, 0, -1, 1>, Eigen::CwiseNullaryOp<Eigen::internal::scalar_constant_op<double>, Eigen::Matrix<double, -1, 1, 0, -1, 1> > > > const&) /usr/include/eigen3/Eigen/src/Core/Dot.h:37
    #7 0x55c3dea8cee7 in Eigen::ScalarBinaryOpTraits<double, Eigen::internal::traits<Eigen::Select<Eigen::CwiseBinaryOp<Eigen::internal::scalar_cmp_op<double, double, (Eigen::internal::ComparisonName)1>, Eigen::ArrayWrapper<Eigen::Matrix<double, -1, 1, 0, -1, 1> const> const, Eigen::CwiseNullaryOp<Eigen::internal::scalar_constant_op<double>, Eigen::Array<double, -1, 1, 0, -1, 1> > const>, Eigen::Matrix<double, -1, 1, 0, -1, 1>, Eigen::CwiseNullaryOp<Eigen::internal::scalar_constant_op<double>, Eigen::Matrix<double, -1, 1, 0, -1, 1> > > >::Scalar, Eigen::internal::scalar_product_op<double, Eigen::internal::traits<Eigen::Select<Eigen::CwiseBinaryOp<Eigen::internal::scalar_cmp_op<double, double, (Eigen::internal::ComparisonName)1>, Eigen::ArrayWrapper<Eigen::Matrix<double, -1, 1, 0, -1, 1> const> const, Eigen::CwiseNullaryOp<Eigen::internal::scalar_constant_op<double>, Eigen::Array<double, -1, 1, 0, -1, 1> > const>, Eigen::Matrix<double, -1, 1, 0, -1, 1>, Eigen::CwiseNullaryOp<Eigen::internal::scalar_constant_op<double>, Eigen::Matrix<double, -1, 1, 0, -1, 1> > > >::Scalar> >::ReturnType Eigen::MatrixBase<Eigen::Select<Eigen::Block<Eigen::Matrix<bool, -1, 1, 0, -1, 1>, -1, 1, false>, Eigen::Block<Eigen::Matrix<double, -1, 1, 0, -1, 1>, -1, 1, false>, Eigen::CwiseNullaryOp<Eigen::internal::scalar_constant_op<double>, Eigen::Matrix<double, -1, 1, 0, -1, 1> > > >::dot<Eigen::Select<Eigen::CwiseBinaryOp<Eigen::internal::scalar_cmp_op<double, double, (Eigen::internal::ComparisonName)1>, Eigen::ArrayWrapper<Eigen::Matrix<double, -1, 1, 0, -1, 1> const> const, Eigen::CwiseNullaryOp<Eigen::internal::scalar_constant_op<double>, Eigen::Array<double, -1, 1, 0, -1, 1> > const>, Eigen::Matrix<double, -1, 1, 0, -1, 1>, Eigen::CwiseNullaryOp<Eigen::internal::scalar_constant_op<double>, Eigen::Matrix<double, -1, 1, 0, -1, 1> > > >(Eigen::MatrixBase<Eigen::Select<Eigen::CwiseBinaryOp<Eigen::internal::scalar_cmp_op<double, double, (Eigen::internal::ComparisonName)1>, Eigen::ArrayWrapper<Eigen::Matrix<double, -1, 1, 0, -1, 1> const> const, Eigen::CwiseNullaryOp<Eigen::internal::scalar_constant_op<double>, Eigen::Array<double, -1, 1, 0, -1, 1> > const>, Eigen::Matrix<double, -1, 1, 0, -1, 1>, Eigen::CwiseNullaryOp<Eigen::internal::scalar_constant_op<double>, Eigen::Matrix<double, -1, 1, 0, -1, 1> > > > const&) const /usr/include/eigen3/Eigen/src/Core/Dot.h:84
    #8 0x55c3dea529f4 in void proxsuite::proxqp::dense::global_dual_residual<double>(proxsuite::proxqp::Results<double>&, proxsuite::proxqp::dense::Workspace<double>&, proxsuite::proxqp::dense::Model<double> const&, bool, proxsuite::proxqp::dense::preconditioner::RuizEquilibration<double> const&, double&, double&, double&, double&, double&, double&, proxsuite::proxqp::HessianType const&) /opt/ros/humble/include/proxsuite/proxqp/dense/utils.hpp:549
    #9 0x55c3dea09de2 in void proxsuite::proxqp::dense::qp_solve<double>(proxsuite::proxqp::Settings<double> const&, proxsuite::proxqp::dense::Model<double> const&, proxsuite::proxqp::Results<double>&, proxsuite::proxqp::dense::Workspace<double>&, bool, proxsuite::proxqp::DenseBackend const&, proxsuite::proxqp::HessianType const&, proxsuite::proxqp::dense::preconditioner::RuizEquilibration<double>&) /opt/ros/humble/include/proxsuite/proxqp/dense/solver.hpp:1411
    #10 0x55c3de9e46e9 in proxsuite::proxqp::dense::QP<double>::solve(std::optional<Eigen::Ref<Eigen::Matrix<double, -1, 1, 0, -1, 1> const, 0, Eigen::InnerStride<1> > >, std::optional<Eigen::Ref<Eigen::Matrix<double, -1, 1, 0, -1, 1> const, 0, Eigen::InnerStride<1> > >, std::optional<Eigen::Ref<Eigen::Matrix<double, -1, 1, 0, -1, 1> const, 0, Eigen::InnerStride<1> > >) /opt/ros/humble/include/proxsuite/proxqp/dense/wrapper.hpp:945
    #11 0x55c3de9c32d3 in main /home/pierre-gergondet/devel/sanbox/proxsuite/sample.cpp:28
    #12 0x7fefd4629d8f in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58
    #13 0x7fefd4629e3f in __libc_start_main_impl ../csu/libc-start.c:392
    #14 0x55c3de9c1e64 in _start (/home/pierre-gergondet/devel/sanbox/proxsuite/build-debug/sample+0xa39e64)

result: -0.0499935  0.0500065        1.7

The issue here is that in the global_dual_residual function, the qpwork.active_set_up (resp. qpwork.active_set_low) is used unitialized to compute zu (resp. zl)

A simple work-around is to initialize these vectors when they are resized:

diff --git a/include/proxsuite/proxqp/dense/workspace.hpp b/include/proxsuite/proxqp/dense/workspace.hpp
index 2a4d77b61..465a8e17e 100644
--- a/include/proxsuite/proxqp/dense/workspace.hpp
+++ b/include/proxsuite/proxqp/dense/workspace.hpp
@@ -204,8 +204,11 @@ struct Workspace
         new_bijection_map(i) = i;
       }
       active_set_up.resize(n_in + dim);
+      active_set_up.setZero();
       active_set_low.resize(n_in + dim);
+      active_set_low.setZero();
       active_inequalities.resize(n_in + dim);
+      active_inequalities.setZero();
       active_part_z.resize(n_in + dim);
       dw_aug.resize(dim + n_eq + n_in + dim);
       rhs.resize(dim + n_eq + n_in + dim);
@@ -279,8 +282,11 @@ struct Workspace
         new_bijection_map(i) = i;
       }
       active_set_up.resize(n_in);
+      active_set_up.setZero();
       active_set_low.resize(n_in);
+      active_set_low.setZero();
       active_inequalities.resize(n_in);
+      active_inequalities.setZero();
       active_part_z.resize(n_in);
       dw_aug.resize(dim + n_eq + n_in);
       rhs.resize(dim + n_eq + n_in);

(I have added active_inequalities here for good measures but I'm not sure if it triggers anything). However, I'm unsure if it's the correct way to address this and I imagine there should be something similar to do with the sparse solver.

Thanks again for the work you've put into this library and please let me know if I can be of further assistance.

[fabinsch]

Hi @gergondet-woven,

thanks a lot for raising this issue and providing a fix for it. I compiled your example and verified that the solution works - the rest of the unittests is still passing, so I think we should integrate this.

It might be a good idea to compile all our unittests with the sanitizers and check for further problems.