Memory Detection Tool KASAN in the Linux Kernel (8) – Implementation Based on Buddy System

Technical experience sharing, welcome to follow and provide guidance.

In “KASAN (7) – Implementation Based on Slab”, the slab situation has been analyzed, but there is still a part based on the buddy system. The implementation of KASAN on the buddy system is quite special, and this article analyzes the KASAN implementation under the buddy system.

Initial Buddy

When initializing the buddy system, all unallocated memory in the system is initialized by calling the buddy system’s free interface. The initialization code flow is as follows:

start_kernel
    mm_init
        mem_init
            memblock_free_all
                free_low_memory_core_early
                    __free_memory_core
                        __free_pages_memory
                            memblock_free_pages
                                __free_pages_core
                                    __free_pages_ok
                                        free_pages_prepare
                                            kernel_poison_pages

As seen in the code below, during the free process, the function <span>kernel_poison_pages</span> is called to poison the memory, and its implementation depends on CONFIG_PAGE_POISONING, which indicates whether to poison the page, as follows:

#ifdef CONFIG_PAGE_POISONING
static inline bool page_poisoning_enabled_static(void)
{
    return static_branch_unlikely(&amp;_page_poisoning_enabled);
}
static inline void kernel_poison_pages(struct page *page, int numpages)
{
    if (page_poisoning_enabled_static())
        __kernel_poison_pages(page, numpages);
}
#else
static inline bool page_poisoning_enabled_static(void) { return false; }
static inline void kernel_poison_pages(struct page *page, int numpages) { }
static inline void kernel_unpoison_pages(struct page *page, int numpages) { }
#endif

Unfortunately, my device does not have CONFIG_PAGE_POISONING enabled, so by default, the shadow area of the buddy system will not be poisoned. Moreover, based on previous analysis, we know that the default value of the shadow is 0 (KASAN_SHADOW_INIT=0), so we can conclude that there is no poisoning during the initialization of the buddy system.

This analysis is actually explained by the test case, as follows:

static void pagealloc_oob_right(struct kunit *test)
{
    char *ptr;
    struct page *pages;
    size_t order = 4;
    size_t size = (1UL &lt;&lt; (PAGE_SHIFT + order));

    /*
     * With generic KASAN page allocations have no redzones, thus
     * out-of-bounds detection is not guaranteed.
     * See https://bugzilla.kernel.org/show_bug.cgi?id=210503.
     */
    KASAN_TEST_NEEDS_CONFIG_OFF(test, CONFIG_KASAN_GENERIC);

    pages = alloc_pages(GFP_KERNEL, order);
    ptr = page_address(pages);
    KUNIT_ASSERT_NOT_ERR_OR_NULL(test, ptr);

    KUNIT_EXPECT_KASAN_FAIL(test, ptr[size] = 0);
    free_pages((unsignedlong)ptr, order);
}

Alloc Pages

According to the analysis, KASAN under CONFIG_KASAN_GENERIC cannot detect out-of-bounds (oob) issues in the buddy system. So can sw-tag/hw-tag detect it? Let’s continue analyzing the alloc_page code flow:

alloc_pages
    alloc_pages_current
        __alloc_pages_nodemask
            get_page_from_freelist
                prep_new_page
                    post_alloc_hook
                        kasan_alloc_pages

We check the implementation of kasan_alloc_pages as follows:

#ifdef CONFIG_KASAN_HW_TAGS

void kasan_alloc_pages(struct page *page, unsigned int order, gfp_t flags);
void kasan_free_pages(struct page *page, unsigned int order);

#else /* CONFIG_KASAN_HW_TAGS */

static __always_inline void kasan_alloc_pages(struct page *page,
                          unsigned int order, gfp_t flags)
{
    /* Only available for integrated init. */
    BUILD_BUG();
}

static __always_inline void kasan_free_pages(struct page *page,
                         unsigned int order)
{
    /* Only available for integrated init. */
    BUILD_BUG();
}

#endif /* CONFIG_KASAN_HW_TAGS */

This means that if KASAN is under HW_TAGS, it supports poisoning in the buddy system. Since my machine does not support hw tags, further analysis will not be conducted.

To summarize, the default kernel provides the CONFIG_PAGE_POISONING debugging interface to poison all pages of the buddy system, but this configuration is disabled by default. After the buddy system is initialized, its shadow pages are initialized to zero pages. Furthermore, through the pages called by alloc_pages, only CONFIG_KASAN_HW_TAGS provides tagging values for poisoning. Since my device is configured with CONFIG_KASAN_GENERIC, it can be concluded that KASAN effectively does nothing for the memory allocated by alloc_pages. This means that under CONFIG_KASAN_GENERIC, KASAN cannot detect oob issues in the buddy system.

Free Pages

In addition to oob issues, there are also use-after-free (uaf) issues, so we need to analyze how free_pages supports uaf.

First, based on the code flow analysis, as follows:

free_pages
    __free_pages
        free_the_page
            __free_pages_ok
                free_pages_prepare

There is a piece of logic as follows:

static inline bool kasan_has_integrated_init(void)
{
    return kasan_hw_tags_enabled();
}
---------------------------------------------------
    if (kasan_has_integrated_init()) {
        if (!skip_kasan_poison)
            kasan_free_pages(page, order);
    } else {
        bool init = want_init_on_free();

        if (init)
            kernel_init_free_pages(page, 1 &lt;&lt; order, false);
        if (!skip_kasan_poison)
            kasan_poison_pages(page, order, init);
    }

The logic can be analyzed as follows:

  1. If it is hw tags, call kasan_free_pages.
  2. If it is not hw tags and the kernel is configured with init_on_free, then the page will be cleared upon free.
  3. By default, call kasan_poison_pages.

We check the code of kasan_poison_pages as follows:

static __always_inline void kasan_poison_pages(struct page *page,
                        unsigned int order, bool init)
{
    if (kasan_enabled())
        __kasan_poison_pages(page, order, init);
}
void __kasan_poison_pages(struct page *page, unsigned int order, bool init)
{
    if (likely(!PageHighMem(page)))
        kasan_poison(page_address(page), PAGE_SIZE &lt;&lt; order,
                 KASAN_FREE_PAGE, init);
}

It can be seen that although KASAN does nothing during the allocation in the buddy system, it still poisons the memory to KASAN_FREE_PAGE (0xff) during the free operation. This means that under CONFIG_KASAN_GENERIC, KASAN can detect uaf issues in the buddy system.

We can analyze the logs from the “KASAN (3) – Test Analysis” section regarding the <span>pagealloc api test uaf</span> as follows:

[ 5510.618665] BUG: KASAN: use-after-free in pagealloc_uaf+0xb4/0xcc [test_kasan_kylin]
[ 5510.618679] Write of size 1 at addr ffffff80a4080000 by task insmod/3253
[ 5510.619044] page:000000009a7015d6 refcount:0 mapcount:-128 mapping:0000000000000000 index:0x0 pfn:0xa4080
[ 5510.619058] flags: 0x0()
[ 5510.619133]  ffffff80a407ff00: ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff
[ 5510.619146]  ffffff80a407ff80: ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff
[ 5510.619159] &gt;ffffff80a4080000: ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff
[ 5510.619170]                    ^
[ 5510.619183]  ffffff80a4080080: ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff
[ 5510.619196]  ffffff80a4080100: ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff

It can be seen that if a page in the buddy system is freed, its value will be set to 0xff, with the purpose of detecting uaf issues in the buddy system.

Conclusion

This article introduces the KASAN implementation under the buddy system. Since the main discussion is about KASAN under CONFIG_KASAN_GENERIC, there is no poisoning during the initialization of the buddy system, and no poisoning occurs when calling alloc_pages. Therefore, KASAN under CONFIG_KASAN_GENERIC cannot detect oob issues in the buddy system.

However, KASAN will poison during free_pages, so KASAN under CONFIG_KASAN_GENERIC can still detect uaf issues.

Related posts

  1. Multithreaded Compression/Decompression of Files Using tar on Linux Servers
  2. Bus – CAN 2.0B/CAN
  3. Daily Linux Command: touch
  4. Practical File Encryption on Linux: OpenSSL and Secure Remote Transmission Guide
  5. Linux Virtual Machine Fails to Boot and Shuts Down Immediately
  6. Understanding linux-insides: A Comprehensive Guide to Linux Kernel Internals
  7. Complete Guide to Linux Directory Structure and Redirection Operations
  8. Comprehensive Guide to Linux Network Configuration
  9. Displaying Asterisks for Password Input in Linux Terminal
  10. How to Read MOESI State and Tag Information in Cache Line on ARMv8
  11. Using the Linux whois Command to Check Domain Information
  12. The Unorthodox Techniques of FPGA Development
  13. Understanding the USB Device Driver Framework
  14. Data-Driven: How to Empower Equipment Management with Data?
  15. Running Shell Scripts in Linux C Code to Retrieve Return Values
  16. Linux System Hacked! Do You Know How to Conduct an Intrusion Investigation? From Basics to Mastery, This Article is All You Need!
  17. Proper Ways to Clean Up Junk in Kali Linux
  18. Common Linux Commands for Java Development
  19. The Ultimate Guide to Disk IO Monitoring in Linux: From iostat to iotop

Leave a Comment