libsolv “resolve_dependencies” function two heap-overflow vulnerability

[yangjiageng]

Description:
There is two heap-overflow vulnerability in function:
static int resolve_dependencies (Solver *solv, int level, int disablerules, Queue *dq)
at src/solver.c: line 1940 & line 1995
if (r->d == 0 || solv->decisionmap[-r->p] <= 0) // line 1940
if (solv->decisionmap[p] > 0) // line 1995

The first bug is caused by the dangerous variable “decisionmap[]”.
If the value of index “-r->p” is bigger than the size of “decisionmap[]”, there will be a heap-overflow bug.

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

str2job: bad line 'update A-2-2.badarch@available'
testcase_read: cannot parse command 'nall'
test 1:
Results differ:
-install k-3-6.x86_64@available
-install k-m-3-6.x86_64@available
test 2:
Results differ:
+install c-1-1.noarch@available
-install k-m-3-1.x86_64@availablestall c-1-1.noarch@available
+install k-m-3-6.x86_64@available
setsolverflags: unknown flag 'onlynamespacerecommendeddەsult'
setsolverflags: unknown flag 'transaction'
setsolverflags: unknown flag ''
test 3:
Results differ:
-install A-1-1.no
+install k-3-6.x86_64@available
+install k-m-3-6.x86_64@available
+problem ca7106eb info package c-1-1.noarch conflicts with k = 3-6 provided by k-3-6.x86_64
+problem ca7106eb solution 4d4bc71f allow k-1-0.x86_64@system
+problem ca7106eb solution 4d4bc71f allow k-2-0.x86_64@system
+problem ca7106eb solution 4d4bc71f allow k-3-0.x86_64@system
+problem ca7106eb solution 86764155 deljob install name c
testcase_read: cannot parse command 'solveflag>'
setsolverflags: unknown flag 'yumobsol6eb'
setsolverflags: unknown flag 'solution'
setsolverflags: unknown flag '86764155'
setsolverflags: unknown flag 'deljob'
setsolverflags: unknown flag 'install'
setsolverflags: unknown flag 'name'
setsolverflags: unknown flag 'c'
str2job: bad line 'update A-2-2.badarch@available'
testcase_read: cannot parse command 'nall'
test 4:
===========================================================
==92568==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x6060000021c0 at pc 0x7fab18a32a6c bp 0x7ffc16984f70 sp 0x7ffc16984f68
READ of size 4 at 0x6060000021c0 thread T0
#0 0x7fab18a32a6b in resolve_dependencies /root/Experiments/real-world/libsolv/src/solver.c:1940:21
#1 0x7fab18a17ba4 in solver_run_sat /root/Experiments/real-world/libsolv/src/solver.c:2722:15
#2 0x7fab18a4d65a 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 0x7fab17a29bf6 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)

0x6060000021c0 is located 4 bytes to the right of 60-byte region [0x606000002180,0x6060000021bc)
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 0x7fab18b86f10 in solv_calloc /root/Experiments/real-world/libsolv/src/util.c:79:9
#2 0x7fab18a0eb9a in solver_create /root/Experiments/real-world/libsolv/src/solver.c:1327:29
#3 0x7fab21fc62d4 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 0x7fab17a29bf6 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:1940:21 in resolve_dependencies
Shadow bytes around the buggy address:
0x0c0c7fff83e0: fd fd fd fd fa fa fa fa fd fd fd fd fd fd fd fd
0x0c0c7fff83f0: fa fa fa fa fd fd fd fd fd fd fd fa fa fa fa fa
0x0c0c7fff8400: fd fd fd fd fd fd fd fd fa fa fa fa fd fd fd fd
0x0c0c7fff8410: fd fd fd fd fa fa fa fa fd fd fd fd fd fd fd fd
0x0c0c7fff8420: fa fa fa fa fd fd fd fd fd fd fd fd fa fa fa fa
=>0x0c0c7fff8430: 00 00 00 00 00 00 00 04[fa]fa fa fa fd fd fd fd
0x0c0c7fff8440: fd fd fd fd fa fa fa fa fd fd fd fd fd fd fd fd
0x0c0c7fff8450: fa fa fa fa fd fd fd fd fd fd fd fd fa fa fa fa
0x0c0c7fff8460: fd fd fd fd fd fd fd fd fa fa fa fa fd fd fd fd
0x0c0c7fff8470: fd fd fd fd fa fa fa fa fd fd fd fd fd fd fd fd
0x0c0c7fff8480: fa fa fa fa fd fd fd fd fd fd fd fd 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
==92568==ABORTING

The second bug is same with the above heap-overflow bug, which is caused by the dangerous variable “decisionmap[]”.
The index “p” is dependent on variable “dp”, and variable “dp” is equal with pool->whatprovidesdata + r->d.
If the value of index “p” is bigger than the size of “decisionmap”, there will be a heap overflow vulnerability.
Our PoC file can make the value of index “p” is bigger than the size of “decisionmap”.

Please reproduce this issue through the following PoC: /libsolvBuildDir/tools/testsolv resolve_dependencies-1995
If you configure CC with flag -fsanitize=address, you will get the following outputs:
testcase_read: could not open 'FuzzDir/out/A-2-2.badarch@available'
test 1:
Transaction summary:

str2job: unknown job 'noable 0 testtags '
testcase_read: system: unknown repo 'system'
testcase_read: could not open 'FuzzDir/out/1'
testcase_read: system: unknown repo 'system'
str2job: bad line 'in'
testcase_read: cannot parse command 'H¶5ޒĸ,BU[¯ğ́]H䪮ÿ̚퐩rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrro+rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrules'
test 2:
===========================================================
==122904==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x6040000001b8 at pc 0x7f3afbc2eacd bp 0x7ffec47f9f90 sp 0x7ffec47f9f88
READ of size 4 at 0x6040000001b8 thread T0
#0 0x7f3afbc2eacc in resolve_dependencies /root/Experiments/real-world/libsolv/src/solver.c:1995:9
#1 0x7f3afbc13ba4 in solver_run_sat /root/Experiments/real-world/libsolv/src/solver.c:2722:15
#2 0x7f3afbc4965a 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 0x7f3afac25bf6 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)

0x6040000001b8 is located 4 bytes to the right of 36-byte region [0x604000000190,0x6040000001b4)
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 0x7f3afbd82f10 in solv_calloc /root/Experiments/real-world/libsolv/src/util.c:79:9
#2 0x7f3afbc0ab9a in solver_create /root/Experiments/real-world/libsolv/src/solver.c:1327:29
#3 0x7f3b051c22d4 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 0x7f3afac25bf6 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:1995:9 in resolve_dependencies
Shadow bytes around the buggy address:
0x0c087fff7fe0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0c087fff7ff0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0c087fff8000: fa fa fd fd fd fd fd fd fa fa 00 00 00 00 00 05
0x0c087fff8010: fa fa 00 00 00 00 02 fa fa fa 00 00 00 00 00 06
0x0c087fff8020: fa fa 00 00 00 00 00 01 fa fa fd fd fd fd fd fa
=>0x0c087fff8030: fa fa 00 00 00 00 04[fa]fa fa fd fd fd fd fd fa
0x0c087fff8040: fa fa 00 00 00 00 00 07 fa fa 00 00 00 00 03 fa
0x0c087fff8050: fa fa 00 00 00 00 00 fa fa fa 00 00 00 00 00 01
0x0c087fff8060: fa fa fd fd fd fd fd fa fa fa 00 00 00 00 00 00
0x0c087fff8070: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c087fff8080: 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
==122904==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-44568.

[tcullum-rh]

Why was one CVE assigned for both of these issues? If they are independently fixable (not independently committed, but fixable), then two separate CVEs should be assigned. See: https://www.cve.org/ResourcesSupport/AllResources/CNARules#section_7-2_how_many_vulnerabilities

[rossburton]

@mlschroe do you recall what commit fixed this?

[rossburton]

Never mind, found it.

[nilesh-akhade]

@rossburton Would you please share the commit that fixed this?

[rossburton]

As per #426 (comment), the slew of CVEs were all fixed by 0077ef2.