If You Love Something, Set It Free — But Only Once

In the recent Pown2Own contest, there was a local privilege escalation attack in Ubuntu desktop (Linux) using a double free bug (CWE-415: Double Free). Vincent Dehors earned $30,000 by forcing the Ubuntu desktop to call free twice on the same memory address.

One might wonder, how could freeing memory twice allow an attacker to do anything, let alone lead to modification of unexpected memory locations? When writing software or managing the writing of software, paying attention to this kind of weakness can prevent costly rewrites and save customers from compromise.

Double Free in Action

When a program frees allocated memory, a system called fastbins stores it in a list for subsequent reallocation. This saves time as the memory does not need to be freed and reallocated by the operating system to include removing it from heap storage. This list is implemented within a series of linked lists based on memory size. If a program frees the same address twice, that memory region is added to the available list twice. Later, two future allocations could point to the same memory address when pulled from that linked list, potentially allowing an attacker to over-write or read data to which they are unauthorized.

In glibc (Linux), the free function checks the first seven entries in the fastbins list and the last entry on the list so that most double frees will not happen (the program aborts) before allocating memory to another task. The function does not check the entire fastbins list, as this would require O(n) steps, where n = length of the list of available memory, slowing down allocation and significantly impacting performance.

In Windows, msvcrt only checks the first item for a duplicate on the list and aborts accordingly. Therefore, when a program frees one block of memory, frees a different block, and then frees the first one again, a problem arises. In the table below, the weakness shows that both C and E point to the same memory location originally held by A. This table gives a simplistic representation without all of the double free checks.

Here are some possible solutions to this weakness:

1. Use languages with memory management, whether a garbage-collected one, like Java or Go, or an ownership-enforced one, like Rust. The downside is that the code would need to be rewritten in a different language. Some languages interface with others, so you might be able to do this incrementally or in critical places.

2. Add a macro (this can’t be a function) to call the free function and null the variable. This new macro can be searched for and replaced, just like replacing strcpy with strlcpy for mitigating a buffer copy without checking size of input (CWE-120). As per the C99 standard, freeing a pointer to null does nothing. This would be the fastest option for runtime, but this has two downsides. First, it will not prevent use-after-frees (CWE-416) when two different variables hold the same pointer value in memory. Second, it would turn what was a use-after-free into a null pointer dereference (CWE-476), causing code to crash but preventing a confidentiality or integrity issue.

3. Disable the system that creates the list of quickly reusable memory, fastbins and other similar features such as tcache. This would slow down programs but remove the problem of the linked list entirely. Double frees would do nothing. It is unclear how this would affect performance, but it would be the easiest development method with no refactoring. Development language and operating system types and versions may affect this solution’s applicability.

4. If you are interested in rewriting the operating system: re-architect fastbins and other similar features to prevent multiple entries of the same pointer. This would prevent anyone from adding a duplicative entry to the list of free memory. If one keeps the linked list data structure, each add would be in O(n), where n is the length of the list. If one uses other data structures, one could make this O(ln) (red/black tree) or O(1) (hashtable). A good research project would be to implement this structure and see how much slower the code would be versus the standard fastbins code in storage and retrieval (see Win10 Segment Heap for red/black tree storage of heaps).

For a detailed look into fastbins and heaps, see the following resources: Guy in a Tuxedo, Feng’s Blog, and 0x00 Sec.