Linux kernel heap quarantine

2020 year. Quarantine is everywhere. And this article is also about quarantine, but it is of a different kind.

I will talk about experimenting with quarantine for Linux kernel heap… It is a safety mechanism that prevents use-after-free (UAF) memory in the Linux kernel. I will also summarize the discussion of my patch series on the Linux Kernel Mailing List (LKML).

image

Memory usage after free in Linux kernel

UAF in the Linux kernel is a very popular type of vulnerability to exploit. There are many public prototypes of nuclear exploits for the UAF:

To operate UAF, the technique is usually used heap spraying… The purpose of this technique is to place the data controlled by the attacker in a specific section of heap, also called the “heap”. The heap spraying technique for exploiting UAF in the Linux kernel is based on the fact that when kmalloc() The slab allocator returns the address of the region of memory that was recently freed:

image

That is, creating another nuclear object of the same size with controlled content allows you to overwrite the released vulnerable object:

image

Note: heap spraying to exploit buffer overflows on the heap is a separate technique that works differently.

Idea

In July 2020, I had an idea on how to counter the heap spraying technique to exploit UAF in the Linux kernel. In August, I found time to experiment. I have quarantined the slab allocator from functionality KASAN and called him SLAB_QUARANTINE

When this mechanism is activated, the released allocations are placed in the quarantine queue, where they are awaiting real release. Therefore, they cannot be instantly implemented and rewritten by UAF exploits. That is, upon activation SLAB_QUARANTINE the kernel allocator behaves like this:

image

13 august I’ve posted the first early prototype of quarantine in LKML and began a deeper study of the security parameters of this mechanism.

SLAB_QUARANTINE Security Properties

To investigate the quarantine security properties of kernel heap memory, I developed two tests lkdtm (published in a series of patches).

The first test is called lkdtm_HEAP_SPRAY… It allocates and frees one object from a separate kmem_cacheand then selects 400,000 similar objects. In other words, this test mimics the original heap spraying technique for UAF exploitation:

#define SPRAY_LENGTH 400000
    ...
    addr = kmem_cache_alloc(spray_cache, GFP_KERNEL);
    ...
    kmem_cache_free(spray_cache, addr);
    pr_info("Allocated and freed spray_cache object %p of size %dn",
                    addr, SPRAY_ITEM_SIZE);
    ...
    pr_info("Original heap spraying: allocate %d objects of size %d...n",
                    SPRAY_LENGTH, SPRAY_ITEM_SIZE);
    for (i = 0; i < SPRAY_LENGTH; i++) {
        spray_addrs[i] = kmem_cache_alloc(spray_cache, GFP_KERNEL);
        ...
        if (spray_addrs[i] == addr) {
            pr_info("FAIL: attempt %lu: freed object is reallocatedn", i);
            break;
        }
    }

    if (i == SPRAY_LENGTH)
        pr_info("OK: original heap spraying hasn't succeededn");

If you disable CONFIG_SLAB_QUARANTINE, the freed object is immediately implemented and rewritten:

  # echo HEAP_SPRAY > /sys/kernel/debug/provoke-crash/DIRECT
   lkdtm: Performing direct entry HEAP_SPRAY
   lkdtm: Allocated and freed spray_cache object 000000002b5b3ad4 of size 333
   lkdtm: Original heap spraying: allocate 400000 objects of size 333...
   lkdtm: FAIL: attempt 0: freed object is reallocated

If you include CONFIG_SLAB_QUARANTINE, 400,000 new allocations do not overwrite the freed object:

  # echo HEAP_SPRAY > /sys/kernel/debug/provoke-crash/DIRECT
   lkdtm: Performing direct entry HEAP_SPRAY
   lkdtm: Allocated and freed spray_cache object 000000009909e777 of size 333
   lkdtm: Original heap spraying: allocate 400000 objects of size 333...
   lkdtm: OK: original heap spraying hasn't succeeded

This is due to the fact that it requires both allocating and freeing memory… Objects are released from quarantine when new memory is allocated, but only if quarantine has exceeded its size limit. And the size of the quarantine increases when memory is released.

So I developed a second test called lkdtm_PUSH_THROUGH_QUARANTINE… It allocates and frees one object from a separate kmem_cache and then executes kmem_cache_alloc()+kmem_cache_free() for this cache 400,000 times.

    addr = kmem_cache_alloc(spray_cache, GFP_KERNEL);
    ...
    kmem_cache_free(spray_cache, addr);
    pr_info("Allocated and freed spray_cache object %p of size %dn",
                    addr, SPRAY_ITEM_SIZE);

    pr_info("Push through quarantine: allocate and free %d objects of size %d...n",
                    SPRAY_LENGTH, SPRAY_ITEM_SIZE);
    for (i = 0; i < SPRAY_LENGTH; i++) {
        push_addr = kmem_cache_alloc(spray_cache, GFP_KERNEL);
        ...
        kmem_cache_free(spray_cache, push_addr);

        if (push_addr == addr) {
            pr_info("Target object is reallocated at attempt %lun", i);
            break;
        }
    }

    if (i == SPRAY_LENGTH) {
        pr_info("Target object is NOT reallocated in %d attemptsn",
                    SPRAY_LENGTH);
    }

With this test, the object goes through quarantine and is implemented after it returns to the list of free objects of the allocator:

  # echo PUSH_THROUGH_QUARANTINE > /sys/kernel/debug/provoke-crash/
   lkdtm: Performing direct entry PUSH_THROUGH_QUARANTINE
   lkdtm: Allocated and freed spray_cache object 000000008fdb15c3 of size 333
   lkdtm: Push through quarantine: allocate and free 400000 objects of size 333...
   lkdtm: Target object is reallocated at attempt 182994
  # echo PUSH_THROUGH_QUARANTINE > /sys/kernel/debug/provoke-crash/
   lkdtm: Performing direct entry PUSH_THROUGH_QUARANTINE
   lkdtm: Allocated and freed spray_cache object 000000004e223cbe of size 333
   lkdtm: Push through quarantine: allocate and free 400000 objects of size 333...
   lkdtm: Target object is reallocated at attempt 186830
  # echo PUSH_THROUGH_QUARANTINE > /sys/kernel/debug/provoke-crash/
   lkdtm: Performing direct entry PUSH_THROUGH_QUARANTINE
   lkdtm: Allocated and freed spray_cache object 000000007663a058 of size 333
   lkdtm: Push through quarantine: allocate and free 400000 objects of size 333...
   lkdtm: Target object is reallocated at attempt 182010

As you can see, the number of allocations required to rewrite a vulnerable object remains almost unchanged. This is bad for defense and good for the attacker, as it allows for a stable bypass of the quarantine at the expense of a longer spray. So I developed randomization of quarantine… In essence, this is a tricky little tweak to the internal mechanism for working with the quarantine queue.

In quarantine, objects are stored in “bundles”. Randomization works like this: first, all packs are filled with nuclear objects. And then, when the quarantine has exceeded the size limit and must release unnecessary objects, an arbitrary batch is selected, from which about half of all nuclear objects are released, which are also randomly selected. Now the quarantine releases the released object at an unpredictable moment:

   lkdtm: Target object is reallocated at attempt 107884
   lkdtm: Target object is reallocated at attempt 265641
   lkdtm: Target object is reallocated at attempt 100030
   lkdtm: Target object is NOT reallocated in 400000 attempts
   lkdtm: Target object is reallocated at attempt 204731
   lkdtm: Target object is reallocated at attempt 359333
   lkdtm: Target object is reallocated at attempt 289349
   lkdtm: Target object is reallocated at attempt 119893
   lkdtm: Target object is reallocated at attempt 225202
   lkdtm: Target object is reallocated at attempt 87343

However, such randomization by itself will not prevent exploitation: objects in quarantine contain the attacker’s data (exploit payload). This means that the kernel target, implemented and rewritten by the spray, will contain the attacker’s data until the next implementation (very bad).

Therefore it is important clean up nuclear heap objects before quarantining them… Moreover, filling them with zeros in some cases allows detecting memory usage after release: a null pointer is dereferenced. This functionality already exists in the kernel and is called init_on_freeI integrated it from CONFIG_SLAB_QUARANTINE

In the course of this work, I discovered a bug in the kernel: in CONFIG_SLAB function init_on_free too late and nuclear facilities are quarantined without being cleaned. I have prepared a fix in a separate patch (adopted in the mainline).

For a deeper understanding of how it works CONFIG_SLAB_QUARANTINE with randomization, I prepared additional patch, with verbose debug output (patch not to be accepted in mainline). An example of such debug output:

quarantine: PUT 508992 to tail batch 123, whole sz 65118872, batch sz 508854
quarantine: whole sz exceed max by 494552, REDUCE head batch 0 by 415392, leave 396304
quarantine: data level in batches:
  0 - 77%
  1 - 108%
  2 - 83%
  3 - 21%
  ...
  125 - 75%
  126 - 12%
  127 - 108%
quarantine: whole sz exceed max by 79160, REDUCE head batch 12 by 14160, leave 17608
quarantine: whole sz exceed max by 65000, REDUCE head batch 75 by 218328, leave 195232
quarantine: PUT 508992 to tail batch 124, whole sz 64979984, batch sz 508854
...

Operation PUT is carried out during the freeing of nuclear memory. Operation REDUCE is performed during the allocation of nuclear memory when the quarantine size is exceeded. Kernel objects released from quarantine are returned to the allocator’s free list. Also in this output you can see that when performing the operation REDUCE quarantine releases some of the objects from a randomly selected batch.

What about performance?

I have spent multiple tests performance of my prototype on real hardware and on virtual machines:

  1. Testing network bandwidth with iperf:
    server: iperf -s -f K

    customer: iperf -c 127.0.0.1 -t 60 -f K

  2. Load test of the nuclear task scheduler:
    hackbench -s 4000 -l 500 -g 15 -f 25 -P
  3. Building the kernel in default configuration:
    time make -j2

I have tested the vanilla Linux kernel in three modes:

  • init_on_free=off
  • init_on_free=on (mechanism from the official kernel)
  • CONFIG_SLAB_QUARANTINE=y (includes init_on_free)

Testing network bandwidth with iperf showed that:

  • init_on_free=on gives bandwidth to 28% less than init_on_free=off
  • CONFIG_SLAB_QUARANTINE gives bandwidth to 2% less than init_on_free=on

Load test of the nuclear task scheduler:

  • hackbench works for 5.3% slower with init_on_free=on compared with init_on_free=off
  • hackbench works for 91.7% slower with CONFIG_SLAB_QUARANTINE compared with init_on_free=on… At the same time, testing on a QEMU / KVM virtual machine showed a decrease in performance on 44%, which is significantly different from the test results on real hardware (Intel Core i7-6500U CPU).

Building the kernel in default configuration:

  • When init_on_free=on the kernel was assembled on 1.7% slower than with init_on_free=off
  • When CONFIG_SLAB_QUARANTINEthe kernel was assembled on 1.1% slower than with init_on_free=on

As you can see, the test results vary greatly and depend on the type of workload.

Note: No performance optimizations have been performed for this version of the quarantine prototype. My main task was to study the safety properties of the mechanism. I decided that it would be better to tackle performance optimization later if it becomes clear that the idea is good.

Counterattack

LKML got an interesting discussion CONFIG_SLAB_QUARANTINE… Thanks to the kernel developers who took the time to provide detailed feedback on my patch series. These are Kees Cook, Andrey Konovalov, Alexander Potapenko, Matthew Wilcox, Daniel Micay, Christopher Lameter, Pavel Machek and Eric W. Biederman …

I am especially grateful to Jann Horn of the team Google Project Zero… He came up with a counterattack, with the help of which he still manages to bypass CONFIG_SLAB_QUARANTINE and exploit UAF in the Linux kernel.

It is noteworthy that our discussion with Ian took place simultaneously with Case’s Twitch stream, during which he tested my patches (I recommend watching recording).

Quote from correspondence with the idea of ​​a counterattack:

On 06.10.2020 21:37, Jann Horn wrote:
> On Tue, Oct 6, 2020 at 7:56 PM Alexander Popov wrote:
>> So I think the control over the time of the use-after-free access doesn't help
>> attackers, if they don't have an "infinite spray" -- unlimited ability to store
>> controlled data in the kernelspace objects of the needed size without freeing them.
   [...]
>> Would you agree?
>
> But you have a single quarantine (per CPU) for all objects, right? So
> for a UAF on slab A, the attacker can just spam allocations and
> deallocations on slab B to almost deterministically flush everything
> in slab A back to the SLUB freelists?

Aaaahh! Nice shot Jann, I see.

Another slab cache can be used to flush the randomized quarantine, so eventually
the vulnerable object returns into the allocator freelist in its cache, and
original heap spraying can be used again.

For now I think the idea of a global quarantine for all slab objects is dead.

That is, an attacker can use another slab cache in the nuclear allocator, allocate and release a large number of objects in it, which will lead to preempting the target object from quarantine back to the free list. The attacker can then use the standard heap spraying technique to exploit the UAF.

I immediately shared this correspondence in the chat of Case’s stream on Twitch. He refined my test PUSH_THROUGH_QUARANTINE on the idea of ​​Jan and performed the attack. Babakh!

I highly recommend reading this correspondence in LKML entirely. It discusses new ideas for countering UAF exploitation in the kernel.

Conclusion

I have researched the Linux kernel heap quarantine security properties and conducted experiments showing its impact on the exploitation of use-after-free vulnerabilities. It turned out to be a quick and interesting project. We failed to create a reliable protection tool used in the mainline, but we got useful results and ideas that will be useful in further work on protecting the Linux kernel.

In the meantime, let me finish with a little poem that popped into my head before bed:

  Quarantine patch version three
  Won't appear. No need.
  Let's exploit use-after-free
  Like we always did ;)

    -- a13xp0p0v

Similar Posts

Leave a Reply