HiGHS
HiGHS copied to clipboard
ERGO-Code
In CholeskyFactor.resize the index can exceed the vector length.
In src/qpsolver/factor.hpp in method resize (line 73), the indices used in the vectors L and L_old will exceed the vector length of the corresponding vector, for the case when new_k_max < current_k_max.
This case occurred e.g., in the simple example
# Minimize:
# -x_2 - 3x_3 + (1/2) * (2 x_1^2 - 2 x_1x_3 + 0.2 x_2^2 + 2 x_3^2)
# Subject to:
# x_1 + x_3 <= 2
# 0 <= x
and causes an container-overflow on address the full message can be found below
==2813085==ERROR: AddressSanitizer: container-overflow on address 0x603000024378 at pc 0x7fe02221bccf bp 0x7fff59dc5630 sp 0x7fff59dc5628
WRITE of size 8 at 0x603000024378 thread T0
#0 0x7fe02221bcce in CholeskyFactor::resize(int) /R/packages/incoming/highs.Rcheck/00_pkg_src/highs/inst/HiGHS/src/qpsolver/factor.hpp:79:32
...
0x603000024378 is located 8 bytes inside of 32-byte region [0x603000024370,0x603000024390)
allocated by thread T0 here:
#0 0x4f078d in operator new(unsigned long) /Sources2/LLVM/14.0.6/llvm-project-14.0.6.src/compiler-rt/lib/asan/asan_new_delete.cpp:95:3
#1 0x7fe021c431cf in void* std::__1::__libcpp_operator_new<unsigned long>(unsigned long) usr/local/bin../include/c++/v1/new:245:10
#2 0x7fe021c431cf in std::__1::__libcpp_allocate(unsigned long, unsigned long) usr/local/bin../include/c++/v1/new:271:10
#3 0x7fe021c431cf in std::__1::allocator<double>::allocate(unsigned long) usr/local/bin../include/c++/v1/__memory/allocator.h:105:38
#4 0x7fe021c431cf in std::__1::allocator_traits<std::__1::allocator<double> >::allocate(std::__1::allocator<double>&, unsigned long) usr/local/bin../include/c++/v1/__memory/allocator_traits.h:262:20
#5 0x7fe021c431cf in std::__1::__split_buffer<double, std::__1::allocator<double>&>::__split_buffer(unsigned long, unsigned long, std::__1::allocator<double>&) usr/local/bin../include/c++/v1/__split_buffer:306:29
#6 0x7fe021c77a2c in std::__1::vector<double, std::__1::allocator<double> >::__append(unsigned long) usr/local/bin../include/c++/v1/vector:1022:53
#7 0x7fe02221b786 in CholeskyFactor::resize(int) /R/packages/incoming/highs.Rcheck/00_pkg_src/highs/inst/HiGHS/src/qpsolver/factor.hpp:76:7
I am not sure what is the intended behavior for this resize function but I would guess something like the following
void resize(HighsInt new_k_max) {
std::vector<double> L_old = L;
L.clear();
L.resize((new_k_max) * (new_k_max));
HighsInt min_k_max = min(new_k_max, current_k_max);
for (HighsInt i = 0; i < min_k_max; i++) {
for (HighsInt j = 0; j < min_k_max; j++) {
L[i * (new_k_max) + j] = L_old[i * current_k_max + j];
}
}
current_k_max = new_k_max;
}
I also see that resize is also entered for cases where new_k_max is equal to current_k_max, I didn't test it but for this case an early exit might give a light speedup.
Form my perspective the issue was resolved for the index i but still persists for the index j.
See below the corresponding code chunk of the current version in ERGO-Code/HiGHS@master
void resize(HighsInt new_k_max) {
std::vector<double> L_old = L;
L.clear();
L.resize((new_k_max) * (new_k_max));
HighsInt min_k_max = min(new_k_max, current_k_max);
for (HighsInt i = 0; i < min_k_max; i++) {
for (HighsInt j = 0; j < current_k_max; j++) {
L[i * (new_k_max) + j] = L_old[i * current_k_max + j];
}
}
current_k_max = new_k_max;
}
The new sanatizer output.
==844101==ERROR: AddressSanitizer: container-overflow on address 0x603000023cb8 at pc 0x7f12de25bd3c bp 0x7ffe5eb92c90 sp 0x7ffe5eb92c88
WRITE of size 8 at 0x603000023cb8 thread T0
#0 0x7f12de25bd3b in CholeskyFactor::resize(int) /data/gannet/ripley/R/packages/tests-clang-SAN/highs/inst/HiGHS/src/qpsolver/factor.hpp:81:32
#1 0x7f12de259cb5 in CholeskyFactor::recompute() /data/gannet/ripley/R/packages/tests-clang-SAN/highs/inst/HiGHS/src/qpsolver/factor.hpp:35:5
#2 0x7f12de263569 in CholeskyFactor::solve(Vector&) /data/gannet/ripley/R/packages/tests-clang-SAN/highs/inst/HiGHS/src/qpsolver/factor.hpp:199:7
#3 0x7f12de242043 in computesearchdirection_minor(Runtime&, Basis&, CholeskyFactor&, ReducedGradient&, Vector&) /data/gannet/ripley/R/packages/tests-clang-SAN/highs/inst/HiGHS/src/qpsolver/quass.cpp:97:6
#4 0x7f12de242043 in Quass::solve(Vector const&, Vector const&, Basis&) /data/gannet/ripley/R/packages/tests-clang-SAN/highs/inst/HiGHS/src/qpsolver/quass.cpp:300:7
#5 0x7f12de24085d in Quass::solve() /data/gannet/ripley/R/packages/tests-clang-SAN/highs/inst/HiGHS/src/qpsolver/quass.cpp:36:3
#6 0x7f12ddbffb36 in Highs::callSolveQp() /data/gannet/ripley/R/packages/tests-clang-SAN/highs/inst/HiGHS/src/lp_data/Highs.cpp:2843:12
#7 0x7f12ddbf1c11 in Highs::run() /data/gannet/ripley/R/packages/tests-clang-SAN/highs/inst/HiGHS/src/lp_data/Highs.cpp:832:21
#8 0x7f12ddbc7b9a in solver_run(SEXPREC*) /data/gannet/ripley/R/packages/tests-clang-SAN/highs/src/highs_interface.cpp:227:40
#9 0x7f12ddb970b2 in _highs_solver_run /data/gannet/ripley/R/packages/tests-clang-SAN/highs/src/RcppExports.cpp:271:34
#10 0x55ca0356057c in R_doDotCall /data/gannet/ripley/R/svn/R-devel/src/main/dotcode.c:868:17
#11 0x55ca036c31df in bcEval /data/gannet/ripley/R/svn/R-devel/src/main/eval.c:7720:21
#12 0x55ca036a48e7 in Rf_eval /data/gannet/ripley/R/svn/R-devel/src/main/eval.c:786:8
#13 0x55ca03708936 in R_execClosure /data/gannet/ripley/R/svn/R-devel/src/main/eval.c
#14 0x55ca03704333 in Rf_applyClosure /data/gannet/ripley/R/svn/R-devel/src/main/eval.c:1882:16
#15 0x55ca036c9050 in bcEval /data/gannet/ripley/R/svn/R-devel/src/main/eval.c:7132:12
#16 0x55ca036a48e7 in Rf_eval /data/gannet/ripley/R/svn/R-devel/src/main/eval.c:786:8
#17 0x55ca03708936 in R_execClosure /data/gannet/ripley/R/svn/R-devel/src/main/eval.c
#18 0x55ca03704333 in Rf_applyClosure /data/gannet/ripley/R/svn/R-devel/src/main/eval.c:1882:16
#19 0x55ca036a51e3 in Rf_eval /data/gannet/ripley/R/svn/R-devel/src/main/eval.c:909:12
#20 0x55ca03714a6c in do_set /data/gannet/ripley/R/svn/R-devel/src/main/eval.c:3019:8
#21 0x55ca036a4c81 in Rf_eval /data/gannet/ripley/R/svn/R-devel/src/main/eval.c:861:12
#22 0x55ca037db126 in Rf_ReplIteration /data/gannet/ripley/R/svn/R-devel/src/main/main.c:262:2
#23 0x55ca037de7b0 in R_ReplConsole /data/gannet/ripley/R/svn/R-devel/src/main/main.c:314:11
#24 0x55ca037de5a6 in run_Rmainloop /data/gannet/ripley/R/svn/R-devel/src/main/main.c:1194:5
#25 0x55ca037de8f2 in Rf_mainloop /data/gannet/ripley/R/svn/R-devel/src/main/main.c:1201:5
#26 0x55ca0335c36c in main /data/gannet/ripley/R/svn/R-devel/src/main/Rmain.c:29:5
#27 0x7f12ef02950f in __libc_start_call_main (/lib64/libc.so.6+0x2950f) (BuildId: 85c438f4ff93e21675ff174371c9c583dca00b2c)
#28 0x7f12ef0295c8 in __libc_start_main@GLIBC_2.2.5 (/lib64/libc.so.6+0x295c8) (BuildId: 85c438f4ff93e21675ff174371c9c583dca00b2c)
#29 0x55ca0329a264 in _start (/data/gannet/ripley/R/R-clang-SAN/bin/exec/R+0x31e264)
