libsolv "resolve_jobrules" function a heap overflow vulnerability

[yangjiageng]

There is a heap-overflow vulnerability in function:
static int resolve_jobrules(Solver *solv, int level, int disablerules, Queue *dq)
at src/solver.c at line 1599
if (solv->decisionmap[l] > 0) // line 1599
If the value of index “l” is bigger than the size of variable “decisionmap[]”, there will be a heap overflow bug.
Our PoC file could trigger this bug.
Please reproduce this issue through the following PoC: /libsolvBuildDir/tools/testsolv resolve_jobrules-1599
If you configure CC with flag -fsanitize=address, you will get the following outputs:
--------------------------------------------------------------------------------------
str2job: bad line 'all packages-B is less than -A)'
str2job: bad line 'all packages-B is less than -A)'
testcase_read: could not open 'srcDir/libsolv/build/tools/FuzzDir/out/<inline'
testcase_read: could not open 'srcDir/libsolv/build/tools/FuzzDir/out/<inline'
testcase_read: could not open 'srcDir/libsolv/build/tools/FuzzDir/out/a-1-1.i686@system'
AddressSanitizer: heap-buffer-overflow on address 0x6030000001ac at pc 0x7f4ffc8f96ff bp 0x7ffe6915ed30 sp 0x7ffe6915ed28
READ of size 4 at 0x6030000001ac thread T0
#0 0x7f4ffc8f96fe in resolve_jobrules /root/Experiments/real-world/libsolv/src/solver.c:1599:12
#1 0x7f4ffc8f96fe in solver_run_sat /root/Experiments/real-world/libsolv/src/solver.c:2676:12
#2 0x7f4ffc91f65a in solver_solve /root/Experiments/real-world/libsolv/src/solver.c:4137:3
#3 0x4f1eea in main /root/Experiments/real-world/libsolv/tools/testsolv.c:241:8
#4 0x7f4ffb8fbbf6 in __libc_start_main /build/glibc-S7xCS9/glibc-2.27/csu/../csu/libc-start.c:310
#5 0x41e6f9 in _start (/root/Experiments/real-world/libsolv/build/tools/testsolv+0x41e6f9)

0x6030000001ac is located 0 bytes to the right of 28-byte region [0x603000000190,0x6030000001ac)
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 0x7f4ffca58f10 in solv_calloc /root/Experiments/real-world/libsolv/src/util.c:79:9
#2 0x7f4ffc8e0b9a in solver_create /root/Experiments/real-world/libsolv/src/solver.c:1327:29
#3 0x7f5005e982d4 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 0x7f4ffb8fbbf6 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:1599:12 in resolve_jobrules
Shadow bytes around the buggy address:
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 fd fa fa fd fd fd fd fa fa fd fd
0x0c067fff8010: fd fa fa fa fd fd fd fd fa fa fd fd fd fd fa fa
0x0c067fff8020: fd fd fd fa fa fa fd fd fd fd fa fa 00 00 00 00
=>0x0c067fff8030: fa fa 00 00 00[04]fa fa fd fd fd fd fa fa fd fd
0x0c067fff8040: fd fd fa fa fd fd fd fa 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 00 00 00 00 fa fa 00 00
0x0c067fff8070: 00 00 fa fa 00 00 00 00 fa fa fd fd fd fd fa fa
0x0c067fff8080: 00 00 00 00 fa fa 00 00 00 00 fa fa 00 00 00 00
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
==121289==ABORTING

The ASAN outputs information about this overflow bug.
And attacker can use this bug to achieve a DoS attack.
Please reproduce and fix this bug.

[mlschroe]

Made testcase reader more robust.

[00xc]

This was assigned CVE-2021-44574.

[tcullum-rh]

For purposes of establishing overall severity, under what real-world circumstance(s) might this out-of-bounds read bug be exploited? I see what is happening at a technical level, but this is a contrived example run against testsolv.

[rossburton]

@mlschroe do you recall what commit fixed this?