libsolv “solver_solve” function a heap-overflow vulnerability

[yangjiageng]

Description:
There is a heap-buffer overflow bug in function:
int solver_solve(Solver solv, Queue job) at src/solver.c: line 3445
if (solv->decisionq.count)
memset(solv->decisionmap, 0, pool->nsolvables * sizeof(Id));
The program calls function memset to reset the memory from solv->decisionmap to solv->decisionmap + pool->nsolvablessizeof(Id).
Obviously, if the size of “solv->decisionmap” is smaller than “pool->nsolvablessizeof(Id)” will cause an out-of-bounds WRITE vulnerability.
Our PoC file maked the size of “solv->decisionmap” is smaller than “pool -> nsolvables * sizeof(Id)” and triggered a heap-buffer overflow bug.

Please reproduce this issue through the following PoC: /libsolvBuildDir/tools/testsolv solver_solve-3445
If you configure CC with flag -fsanitize=address, you will get the following outputs:

test 1:
Results differ:
-instalk A-1-1.x86_64@available
+install A-1-1.x86_64@available
test 2:
===========================================================
AddressSanitizer: heap-buffer-overflow on address 0x603000000114 at pc 0x00000043ca14 bp 0x7fff2d1e14d0 sp 0x7fff2d1e0c80
WRITE of size 28 at 0x603000000114 thread T0
#0 0x43ca13 in __interceptor_memset.part.42 /root/Downloads/llvm-build/llvm/projects/compiler-rt/lib/asan/../sanitizer_common/sanitizer_common_interceptors.inc:778
#1 0x7fcf4fbf1ba3 in solver_solve /root/Experiments/real-world/libsolv/src/solver.c:3445:5
#2 0x4f1eea in main /root/Experiments/real-world/libsolv/tools/testsolv.c:241:8
#3 0x7fcf4ebe0bf6 in __libc_start_main /build/glibc-S7xCS9/glibc-2.27/csu/../csu/libc-start.c:310
#4 0x41e6f9 in _start (/root/Experiments/real-world/libsolv/build/tools/testsolv+0x41e6f9)

0x603000000114 is located 0 bytes to the right of 20-byte region [0x603000000100,0x603000000114)
allocated by thread T0 here:
#0 0x4abe48 in calloc /root/Downloads/llvm-build/llvm/projects/compiler-rt/lib/asan/asan_malloc_linux.cpp:154
#1 0x7fcf4fd3df10 in solv_calloc /root/Experiments/real-world/libsolv/src/util.c:79:9
#2 0x7fcf4fbc5b9a in solver_create /root/Experiments/real-world/libsolv/src/solver.c:1327:29
#3 0x7fcf59180bdb in testcase_read /root/Experiments/real-world/libsolv/ext/testcase.c:2435:14
#4 0x4f144b in main /root/Experiments/real-world/libsolv/tools/testsolv.c:159:11
#5 0x7fcf4ebe0bf6 in __libc_start_main /build/glibc-S7xCS9/glibc-2.27/csu/../csu/libc-start.c:310

SUMMARY: AddressSanitizer: heap-buffer-overflow /root/Downloads/llvm-build/llvm/projects/compiler-rt/lib/asan/../sanitizer_common/sanitizer_common_interceptors.inc:778 in __interceptor_memset.part.42
Shadow bytes around the buggy address:
0x0c067fff7fd0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0c067fff7fe0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0c067fff7ff0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0c067fff8000: fa fa fd fd fd fa fa fa fd fd fd fd fa fa fd fd
0x0c067fff8010: fd fd fa fa fd fd fd fd fa fa 00 00 00 00 fa fa
=>0x0c067fff8020: 00 00[04]fa fa fa 00 00 00 00 fa fa fd fd fd fd
0x0c067fff8030: fa fa 00 00 00 00 fa fa 00 00 00 00 fa fa 00 00
0x0c067fff8040: 00 00 fa fa 00 00 00 00 fa fa 00 00 00 00 fa fa
0x0c067fff8050: fd fd fd fd fa fa fd fd fd fd fa fa fd fd fd fd
0x0c067fff8060: fa fa fd fd fd fd fa fa fd fd fd fd fa fa fd fd
0x0c067fff8070: fd fa fa fa fd fd fd fa fa fa fd fd fd fd fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
Addressable: 00
Partially addressable: 01 02 03 04 05 06 07
Heap left redzone: fa
Freed heap region: fd
Stack left redzone: f1
Stack mid redzone: f2
Stack right redzone: f3
Stack after return: f5
Stack use after scope: f8
Global redzone: f9
Global init order: f6
Poisoned by user: f7
Container overflow: fc
Array cookie: ac
Intra object redzone: bb
ASan internal: fe
Left alloca redzone: ca
Right alloca redzone: cb
Shadow gap: cc
==92674==ABORTING

This heap overflow bug caused an out-of-bounds writing vulnerability, which is a dangerous operation.
Hacker even can exploit the bugs that are caused by this bug to achieve a RCE attacks.
Please reproduce and fix this bug.

[mlschroe]

Made testcase reader more robust.

[00xc]

This was assigned CVE-2021-44569.