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.

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

Tests: TestBitmap has heap-buffer-overflow in set_range test #7073

Closed
ADKaster opened this issue May 13, 2021 · 1 comment · Fixed by #7157
Closed

Tests: TestBitmap has heap-buffer-overflow in set_range test #7073

ADKaster opened this issue May 13, 2021 · 1 comment · Fixed by #7157
Labels
bug Something isn't working good first issue Good for newcomers

Comments

@ADKaster
Copy link
Member

The set_range test in TestBitmap overflows the allocated bitmap in AK::BitmapView::count_in_range

    {
        Bitmap bitmap(288, false);
        bitmap.set_range(48, 32, true);
        bitmap.set_range(94, 39, true);
        bitmap.set_range(190, 71, true);
        bitmap.set_range(190 + 71 - 7, 21, false); // slightly overlapping clear
        for (size_t i = 0; i < bitmap.size(); i++) {
            bool should_be_set = (i >= 48 && i < 48 + 32)
                || (i >= 94 && i < 94 + 39)
                || ((i >= 190 && i < 190 + 71) && !(i >= 190 + 71 - 7 && i < 190 + 71 - 7 + 21));
            EXPECT_EQ(bitmap.get(i), should_be_set);
        }
        EXPECT_EQ(bitmap.count_slow(true), 32u + 39u + 71u - 7u); ///<--- overflows here
    }
Test run with ASAN backtrace
28/87 Test #28: TestBitmap_lagom .....................***Failed    0.03 sec
Running test 'construct_empty'.
Completed test 'construct_empty' in 0ms
Running test 'find_first_set'.
Completed test 'find_first_set' in 0ms
Running test 'find_first_unset'.
Completed test 'find_first_unset' in 0ms
Running test 'find_one_anywhere_set'.
Completed test 'find_one_anywhere_set' in 0ms
Running test 'find_one_anywhere_unset'.
Completed test 'find_one_anywhere_unset' in 0ms
Running test 'find_first_range'.
Completed test 'find_first_range' in 0ms
Running test 'set_range'.
=================================================================
==15246==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x6040000002f4 at pc 0x556364bf7d49 bp 0x7ffe4d613460 sp 0x7ffe4d613450
READ of size 1 at 0x6040000002f4 thread T0
    #0 0x556364bf7d48 in AK::BitmapView::count_in_range(unsigned long, unsigned long, bool) const /home/andrew/serenity/Meta/Lagom/../../AK/BitmapView.h:67
    #1 0x556364c038c6 in AK::Bitmap::count_in_range(unsigned long, unsigned long, bool) const /home/andrew/serenity/Meta/Lagom/../../AK/Bitmap.h:83
    #2 0x556364c038c6 in AK::Bitmap::count_slow(bool) const /home/andrew/serenity/Meta/Lagom/../../AK/Bitmap.h:82
    #3 0x556364c038c6 in __test_set_range /home/andrew/serenity/Tests/AK/TestBitmap.cpp:148
    #4 0x556364ced2b3 in AK::Function<void ()>::operator()() const /home/andrew/serenity/Meta/Lagom/../../AK/Function.h:57
    #5 0x556364ced2b3 in Test::TestSuite::run(AK::NonnullRefPtrVector<Test::TestCase, 0ul> const&) /home/andrew/serenity/Userland/Libraries/LibTest/TestSuite.cpp:118
    #6 0x556364bd79d4 in Test::TestSuite::main(AK::String const&, int, char**) /home/andrew/serenity/Userland/Libraries/LibTest/TestSuite.cpp:81
    #7 0x556364bd4502 in main /home/andrew/serenity/Userland/Libraries/LibTest/TestMain.cpp:25
    #8 0x7fbc8c9350b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
    #9 0x556364bd859d in _start (/home/andrew/serenity/BuildLagom/TestBitmap_lagom+0x17b59d)

0x6040000002f4 is located 0 bytes to the right of 36-byte region [0x6040000002d0,0x6040000002f4)
allocated by thread T0 here:
    #0 0x7fbc8d719517 in malloc (/usr/lib/x86_64-linux-gnu/libasan.so.6+0xb0517)
    #1 0x556364c026a1 in AK::Bitmap::Bitmap(unsigned long, bool) /home/andrew/serenity/Meta/Lagom/../../AK/Bitmap.h:29
    #2 0x556364c026a1 in __test_set_range /home/andrew/serenity/Tests/AK/TestBitmap.cpp:137
    #3 0x556364ced2b3 in AK::Function<void ()>::operator()() const /home/andrew/serenity/Meta/Lagom/../../AK/Function.h:57
    #4 0x556364ced2b3 in Test::TestSuite::run(AK::NonnullRefPtrVector<Test::TestCase, 0ul> const&) /home/andrew/serenity/Userland/Libraries/LibTest/TestSuite.cpp:118
    #5 0x556364bd79d4 in Test::TestSuite::main(AK::String const&, int, char**) /home/andrew/serenity/Userland/Libraries/LibTest/TestSuite.cpp:81
    #6 0x556364bd4502 in main /home/andrew/serenity/Userland/Libraries/LibTest/TestMain.cpp:25
    #7 0x7fbc8c9350b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)

SUMMARY: AddressSanitizer: heap-buffer-overflow /home/andrew/serenity/Meta/Lagom/../../AK/BitmapView.h:67 in AK::BitmapView::count_in_range(unsigned long, unsigned long, bool) const
Shadow bytes around the buggy address:
  0x0c087fff8000: fa fa 00 00 00 00 00 fa fa fa fd fd fd fd fd fa
  0x0c087fff8010: fa fa 00 00 00 00 07 fa fa fa 00 00 00 00 00 01
  0x0c087fff8020: fa fa 00 00 00 00 00 06 fa fa 00 00 00 00 00 00
  0x0c087fff8030: fa fa 00 00 00 00 00 01 fa fa 00 00 00 00 02 fa
  0x0c087fff8040: fa fa 00 00 00 00 07 fa fa fa 00 00 00 00 07 fa
=>0x0c087fff8050: fa fa fd fd fd fd fd fa fa fa 00 00 00 00[04]fa
  0x0c087fff8060: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  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
  0x0c087fff8090: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c087fff80a0: 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
==15246==ABORTING
@bgianfo bgianfo added bug Something isn't working good first issue Good for newcomers labels May 13, 2021
@ADKaster
Copy link
Member Author

BitmapView::count_in_range() will return a last pointer that is invalid/out of range for 8-bit aligned bitmap sizes.

    size_t count_in_range(size_t start, size_t len, bool value) const
    {
        VERIFY(start < m_size);
        VERIFY(start + len <= m_size);
        if (len == 0)
            return 0;

        static const u8 bitmask_first_byte[8] = { 0xFF, 0xFE, 0xFC, 0xF8, 0xF0, 0xE0, 0xC0, 0x80 };
        static const u8 bitmask_last_byte[8] = { 0x0, 0x1, 0x3, 0x7, 0xF, 0x1F, 0x3F, 0x7F };

        size_t count;
        const u8* first = &m_data[start / 8];
        const u8* last = &m_data[(start + len) / 8];

If m_size == 24, and you do count_in_range(0, 24, true), for example, then the calculation of last will return &m_bitmap[3], which is one-past-the-end. So this bug affects all bitmaps with a size that is 8-byte-aligned (i.e. most of them, I would expect)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug Something isn't working good first issue Good for newcomers
Projects
None yet
Development

Successfully merging a pull request may close this issue.

2 participants