Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

libsolv “resolve_installed” function two heap-overflow vulnerabilities #430

Closed
yangjiageng opened this issue Dec 13, 2020 · 8 comments
Closed

libsolv “resolve_installed” function two heap-overflow vulnerabilities #430

yangjiageng opened this issue Dec 13, 2020 · 8 comments

Comments

@yangjiageng
Copy link

yangjiageng commented Dec 13, 2020 •
edited
Loading

There are two heap overflow bugs in function:
static int resolve_installed(Solver *solv, int level, int disablerules, Queue *dq)
at src/solver.c: line 1728 & 1766

while ((p = pool->whatprovidesdata[d++]) != 0)
		    if (solv->decisionmap[p] >= 0)	// line 1728
		      queue_push(dq, p);

FOR_RULELITERALS(p, pp, rr)
		    {
		      if (solv->decisionmap[p] > 0)   // line 1766
			... ...
}

If the value of index “p” is bigger than the size of variable “decisionmap[]”, there will be two heap overflow bug.
Our PoC files could trigger these two bugs.

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

test 1:
Results differ:
+problem fc3d647e solution e5fc66c9 erase a-1-1.i686@system
test 2:
Results differ:
-problem fc3d647e solution 179b72ed allow a-1-1.i686@systeblem fc3d647e solution e5fc66c9 erase a-1-1.i686@system
+problem fc3d647e solution 179b72ed allow a-1-1.i686@system
+problem fc3d647e solution e5fc66c9 erase a-1-1.i686@system
test 3:
===========================================================
AddressSanitizer: heap-buffer-overflow on address 0x602000000660 at pc 0x7f135dada92a bp 0x7ffd0078bc30 sp 0x7ffd0078bc28
READ of size 4 at 0x602000000660 thread T0
#0 0x7f135dada929 in resolve_installed /root/Experiments/real-world/libsolv/src/solver.c:1728:11
#1 0x7f135dada929 in solver_run_sat /root/Experiments/real-world/libsolv/src/solver.c:2701:12
#2 0x7f135db0065a 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 0x7f135cadcbf6 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)

0x602000000660 is located 0 bytes to the right of 16-byte region [0x602000000650,0x602000000660)
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 0x7f135dc39f10 in solv_calloc /root/Experiments/real-world/libsolv/src/util.c:79:9
#2 0x7f135dac1b9a in solver_create /root/Experiments/real-world/libsolv/src/solver.c:1327:29
#3 0x7f13670792d4 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 0x7f135cadcbf6 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:1728:11 in resolve_installed
Shadow bytes around the buggy address:
0x0c047fff8070: fa fa fd fa fa fa fd fa fa fa fd fa fa fa fd fd
0x0c047fff8080: fa fa fd fa fa fa fd fa fa fa fd fa fa fa fd fa
0x0c047fff8090: fa fa fd fa fa fa fd fa fa fa fd fa fa fa fd fa
0x0c047fff80a0: fa fa fd fa fa fa fd fa fa fa fd fa fa fa fd fa
0x0c047fff80b0: fa fa fd fa fa fa fd fa fa fa fd fa fa fa 01 fa
=>0x0c047fff80c0: fa fa 01 fa fa fa 01 fa fa fa 00 00[fa]fa fd fd
0x0c047fff80d0: fa fa 07 fa fa fa 00 00 fa fa 04 fa fa fa 04 fa
0x0c047fff80e0: fa fa 00 00 fa fa 04 fa fa fa 04 fa fa fa 01 fa
0x0c047fff80f0: fa fa fd fa fa fa fd fa fa fa fd fa fa fa 04 fa
0x0c047fff8100: fa fa 00 04 fa fa fd fa fa fa fd fa fa fa fa fa
0x0c047fff8110: 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
==54216==ABORTING

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

testcase_read: cannot parse command 'resulg:'
==========================================================
AddressSanitizer: heap-buffer-overflow on address 0x602000000120 at pc 0x7fa0fcd99a0d bp 0x7ffe5be7f450 sp 0x7ffe5be7f448
READ of size 4 at 0x602000000120 thread T0
#0 0x7fa0fcd99a0c in resolve_installed /root/Experiments/real-world/libsolv/src/solver.c:1766:13
#1 0x7fa0fcd99a0c in solver_run_sat /root/Experiments/real-world/libsolv/src/solver.c:2701:12
#2 0x7fa0fcdbf65a 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 0x7fa0fbd9bbf6 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)

0x602000000120 is located 0 bytes to the right of 16-byte region [0x602000000110,0x602000000120)
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 0x7fa0fcef8f10 in solv_calloc /root/Experiments/real-world/libsolv/src/util.c:79:9
#2 0x7fa0fcd80b9a in solver_create /root/Experiments/real-world/libsolv/src/solver.c:1327:29
#3 0x7fa1063382d4 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 0x7fa0fbd9bbf6 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:1766:13 in resolve_installed
Shadow bytes around the buggy address:
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 01 fa
=>0x0c047fff8020: fa fa 00 00[fa]fa fd fd fa fa 00 02 fa fa 00 00
0x0c047fff8030: fa fa 04 fa fa fa 04 fa fa fa 00 00 fa fa 00 fa
0x0c047fff8040: fa fa 04 fa fa fa fd fa fa fa fd fa fa fa fd fa
0x0c047fff8050: fa fa 00 04 fa fa fd fa fa fa fd fa fa fa fa fa
0x0c047fff8060: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c047fff8070: 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
==42086==ABORTING

The ASAN outputs information about these overflow bugs.
And attacker can use these two bugs to achieve different DoS attacks.
Please reproduce and fix these two bugs.
@mlschroe
Copy link
Member

Ok, but the decisionmap really needs to include all packages. So maybe there's something wrong with the testcase reader.

@mlschroe
Copy link
Member

Oh, you're adding repos after a nextjob! The testcase reader should not accept this.

@mlschroe
Copy link
Member

Fixed with 0077ef2

@mlschroe
Copy link
Member

Could you please re-run your fuzzer the check if the commit fixes all issues? Thanks a lot!

@yangjiageng
Copy link
Author

Could you please re-run your fuzzer the check if the commit fixes all issues? Thanks a lot!

Yes, no problem. I will re-run the fuzzer to make sure all issues fixed.

@atoptsoglou
Copy link

Tried this specific POC in valgrind with the patched version and the invalid reads disappeared.

@yangjiageng
Copy link
Author

Tried this specific POC in valgrind with the patched version and the invalid reads disappeared.

Right. This bug have been fixed.

@00xc
Copy link

00xc commented Feb 22, 2022

This bug was assigned CVE-2021-44573.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
4 participants
@mlschroe @yangjiageng @atoptsoglou @00xc