libsolv “solver_get_recommendations” function two heap-overflow vulnerabilities

[yangjiageng]

Description:
There are two heap-overflow bugs in function:
void solver_get_recommendations(Solver *solv, Queue *recommendationsq, Queue *suggestionsq, int noselected)
at src/solver.c: line 4286 & line 4305
FOR_PROVIDES(p, pp, rec)
if (solv->decisionmap[p] > 0) // line 4286

for (i = 1; i < pool->nsolvables; i++)
{
if (solv->decisionmap[i] < 0) // line 4305
continue;
... ...
}

These two bugs involve dangerous “available solvables map” decisionmap[].
In the first bug, if the index value of “p” is bigger than the size of “decisionmap[]”, there will be a heap overflow bug.
In the second bug, the index value “i” is dependent on “pool->nsolvables”.
If the index value “i” is bigger than the size of “decisionmap”, there will be a heap overflow bug.
Our PoC files can trigger these two bugs.

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

testcase_read: cannot parse command 'repoy'
testcase_read: system: unknown repo 'system'
testcase_read: cannot parse command '3'
testcase_read: system: unknown repo 'system'
===========================================================
==16593==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x603000000054 at pc 0x7f79618a22e7 bp 0x7ffef1c54250 sp 0x7ffef1c54248
READ of size 4 at 0x603000000054 thread T0
#0 0x7f79618a22e6 in solver_get_recommendations /root/Experiments/real-world/libsolv/src/solver.c:4286:11
#1 0x7f796adf75ec in testcase_solverresult /root/Experiments/real-world/libsolv/ext/testcase.c:1338:7
#2 0x4f23ad in main /root/Experiments/real-world/libsolv/tools/testsolv.c:246:19
#3 0x7f7960871bf6 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)

0x603000000054 is located 0 bytes to the right of 20-byte region [0x603000000040,0x603000000054)
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 0x7f79619cef10 in solv_calloc /root/Experiments/real-world/libsolv/src/util.c:79:9
#2 0x7f7961856b9a in solver_create /root/Experiments/real-world/libsolv/src/solver.c:1327:29
#3 0x7f796ae0e2d4 in testcase_read /root/Experiments/real-world/libsolv/ext/testcase.c:2268:15
#4 0x4f144b in main /root/Experiments/real-world/libsolv/tools/testsolv.c:159:11
#5 0x7f7960871bf6 in __libc_start_main /build/glibc-S7xCS9/glibc-2.27/csu/../csu/libc-start.c:310

SUMMARY: AddressSanitizer: heap-buffer-overflow /root/Experiments/real-world/libsolv/src/solver.c:4286:11 in solver_get_recommendations
Shadow bytes around the buggy address:
0x0c067fff7fb0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0c067fff7fc0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
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 00 00 00 00 fa fa 00 00[04]fa fa fa 00 00
0x0c067fff8010: 00 fa fa fa fd fd fd fd fa fa fd fd fd fd fa fa
0x0c067fff8020: 00 00 00 04 fa fa 00 00 00 00 fa fa 00 00 00 00
0x0c067fff8030: fa fa fd fd fd fd 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: 00 00 00 00 fa fa fd fd fd fd fa fa fd fd fd fd
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
==16593==ABORTING

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

testcase_read: system: unknown repo 'system'
testcase_read: cannot parse command 'systerch@available'
===========================================================
==44782==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x603000000088 at pc 0x7fdd979fe772 bp 0x7ffd5e3814f0 sp 0x7ffd5e3814e8
READ of size 4 at 0x603000000088 thread T0
#0 0x7fdd979fe771 in solver_get_recommendations /root/Experiments/real-world/libsolv/src/solver.c:4305:8
#1 0x7fdda0f535ec in testcase_solverresult /root/Experiments/real-world/libsolv/ext/testcase.c:1338:7
#2 0x4f23ad in main /root/Experiments/real-world/libsolv/tools/testsolv.c:246:19
#3 0x7fdd969cdbf6 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)

0x603000000088 is located 0 bytes to the right of 24-byte region [0x603000000070,0x603000000088)
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 0x7fdd97b2af10 in solv_calloc /root/Experiments/real-world/libsolv/src/util.c:79:9
#2 0x7fdd979b2b9a in solver_create /root/Experiments/real-world/libsolv/src/solver.c:1327:29
#3 0x7fdda0f6a2d4 in testcase_read /root/Experiments/real-world/libsolv/ext/testcase.c:2268:15
#4 0x4f144b in main /root/Experiments/real-world/libsolv/tools/testsolv.c:159:11
#5 0x7fdd969cdbf6 in __libc_start_main /build/glibc-S7xCS9/glibc-2.27/csu/../csu/libc-start.c:310

SUMMARY: AddressSanitizer: heap-buffer-overflow /root/Experiments/real-world/libsolv/src/solver.c:4305:8 in solver_get_recommendations
Shadow bytes around the buggy address:
0x0c067fff7fc0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
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 00 00 00 00 fa fa 00 00
=>0x0c067fff8010: 00[fa]fa fa fd fd fd fd fa fa fd fd fd fd fa fa
0x0c067fff8020: fd fd fd fa fa fa 00 00 00 00 fa fa 00 00 00 00
0x0c067fff8030: fa fa fd fd fd fd fa fa fd fd fd fd fa fa 00 00
0x0c067fff8040: 00 fa fa fa 00 00 00 00 fa fa fd fd fd fd fa fa
0x0c067fff8050: 00 00 00 00 fa fa 00 00 00 00 fa fa 00 00 00 00
0x0c067fff8060: fa fa 00 00 00 00 fa fa 00 00 00 00 fa fa fd fd
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
==44782==ABORTING

The ASAN outputs information about these two heap overflow bugs.
And attacker can use these bugs to achieve a DoS attack.
Please reproduce and fix these two bugs.

[mlschroe]

Made testcase reader more robust.

[00xc]

This was assigned CVE-2021-44570.

[wangkerong]

Hi, did you fix this CVE-2021-44570?
If so, in what commit?
Thanks !

[mlschroe]

All of those CVEs were fixed with one single commit 0077ef2 to the testcase reader. I have no clue why someone opened so many different CVEs for the same bug.