libsolv “makeruledecisions” function two heap-overflow vulnerabilities

[yangjiageng]

There are two heap-overflow vulnerabilities in function:
static int makeruledecisions(Solver *solv, int disablerules)
at src/solver.c: line 147 & 307
if (!solv->decisionmap[vv]) // line 147
if (!solv->decisionmap[vv]) // line 307

These two bugs are same with the above heap-overflow bug, which is caused by the dangerous variable “decisionmap[]”.
If the value of index “vv” is bigger than the size of “decisionmap[]”, there will be two heap overflow bugs.
Our PoC files can trigger these two bugs.

Please reproduce this issue through the following PoC: /libsolvBuildDir/tools/testsolv makeruledecisions_147
If you configure CC with flag -fsanitize=address, you will get the following outputs:
setsolverflags: unknown flag 'ignorerecomm'
setsolverflags: unknown flag 'noarch'
testcase_read: system: unknown repo 'systdm'
str2job: bad line 'prkvides retracted-patch-package()'
testcase_read: cannot parse command 'r󿱰S"3K¬ŘQ򦡶
9捄¸m®𥃫^D¾]¨n+*𧥜.v&*먷o叐ɵ¤gv?䯺Ȓ¦f⤗A𹉧n¿>Nً¢ªwѧǧ
testcase_read: cannot parse command '布3Ҭµ)h­s䳅¥
򄧒»ZY6200a'

AddressSanitizer: heap-buffer-overflow on address 0x6020000000f8 at pc 0x7f3f01aa4a66 bp 0x7ffc9d4e9890 sp 0x7ffc9d4e9888
READ of size 4 at 0x6020000000f8 thread T0
#0 0x7f3f01aa4a65 in makeruledecisions (/root/projects/libsolv/build/src/libsolv.so.1+0x37a65)
#1 0x7f3f01aa11b4 in solver_run_sat (/root/projects/libsolv/build/src/libsolv.so.1+0x341b4)
#2 0x7f3f01aca047 in solver_solve (/root/projects/libsolv/build/src/libsolv.so.1+0x5d047)
#3 0x4ef73e in main (/root/projects/libsolv/build/tools/testsolv+0x4ef73e)
#4 0x7f3f00abcbf6 in __libc_start_main /build/glibc-S7xCS9/glibc-2.27/csu/../csu/libc-start.c:310
#5 0x41bc19 in _start (/root/projects/libsolv/build/tools/testsolv+0x41bc19)

0x6020000000f8 is located 0 bytes to the right of 8-byte region [0x6020000000f0,0x6020000000f8)
allocated by thread T0 here:
#0 0x4a9368 in calloc /root/Downloads/llvm-build/llvm/projects/compiler-rt/lib/asan/asan_malloc_linux.cpp:154
#1 0x7f3f01b93265 in solv_calloc (/root/projects/libsolv/build/src/libsolv.so.1+0x126265)
#2 0x7f3f01a9e8cc in solver_create (/root/projects/libsolv/build/src/libsolv.so.1+0x318cc)
#3 0x7f3f01f07f88 in testcase_read (/root/projects/libsolv/build/ext/libsolvext.so.1+0x25f88)
#4 0x4ee482 in main (/root/projects/libsolv/build/tools/testsolv+0x4ee482)
#5 0x7f3f00abcbf6 in __libc_start_main /build/glibc-S7xCS9/glibc-2.27/csu/../csu/libc-start.c:310

SUMMARY: AddressSanitizer: heap-buffer-overflow (/root/projects/libsolv/build/src/libsolv.so.1+0x37a65) in makeruledecisions
Shadow bytes around the buggy address:
0x0c047fff7fc0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0c047fff7fd0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0c047fff7fe0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0c047fff7ff0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0c047fff8000: fa fa fd fd fa fa 07 fa fa fa 00 00 fa fa 04 fa
=>0x0c047fff8010: fa fa 04 fa fa fa 01 fa fa fa 01 fa fa fa 00[fa]
0x0c047fff8020: fa fa 00 02 fa fa 00 00 fa fa 04 fa fa fa 04 fa
0x0c047fff8030: fa fa 00 00 fa fa fd fa fa fa fd fa fa fa 04 fa
0x0c047fff8040: fa fa fd fa fa fa fd fa fa fa fa fa fa fa fa fa
0x0c047fff8050: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c047fff8060: fa fa fa fa fa fa fa fa fa fa fa fa fa fa 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
==54939==ABORTING

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

str2job: unknown package 'B-1-1.x86_64@system'
===========================================================
==129073==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x6020000000a4 at pc 0x7f1d7544245e bp 0x7ffdd98ece30 sp 0x7ffdd98ece28
READ of size 4 at 0x6020000000a4 thread T0
#0 0x7f1d7544245d in makeruledecisions /root/Experiments/real-world/libsolv/src/solver.c:307:9
#1 0x7f1d7544245d in solver_run_sat /root/Experiments/real-world/libsolv/src/solver.c:2656:12
#2 0x7f1d7546865a 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 0x7f1d74444bf6 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)

0x6020000000a4 is located 12 bytes to the right of 8-byte region [0x602000000090,0x602000000098)
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 0x7f1d755a1f10 in solv_calloc /root/Experiments/real-world/libsolv/src/util.c:79:9
#2 0x7f1d75429b9a in solver_create /root/Experiments/real-world/libsolv/src/solver.c:1327:29
#3 0x7f1d7e9e12d4 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 0x7f1d74444bf6 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:307:9 in makeruledecisions
Shadow bytes around the buggy address:
0x0c047fff7fc0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0c047fff7fd0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0c047fff7fe0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0c047fff7ff0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0c047fff8000: fa fa fd fd fa fa 07 fa fa fa 01 fa fa fa 01 fa
=>0x0c047fff8010: fa fa 00 fa[fa]fa fd fd fa fa fd fa fa fa 00 fa
0x0c047fff8020: fa fa fd fd fa fa fd fa fa fa 00 02 fa fa 00 00
0x0c047fff8030: fa fa 04 fa fa fa 04 fa fa fa fd fa fa fa fd fa
0x0c047fff8040: fa fa 00 04 fa fa fd fa fa fa fd fa fa fa 02 fa
0x0c047fff8050: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c047fff8060: fa fa fa fa fa fa fa fa fa fa fa fa fa fa 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
==129073==ABORTING

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

[mlschroe]

Made testcase reader more robust.

[00xc]

This was assigned CVE-2021-44575.

[tcullum-rh]

@mlschroe Are these really two separate bugs or are they fixed by the same patch? I do not see a commit attached here, so wanted to confirm.

[mlschroe]

All of those are just one single bug in the testcase reader, which let to corrupted data structures which caused invalid memory accesses in multiple places. It was unfortunate that lots of CVEs were opened right away before contacting libsolv upstream first.