libc:malloc meets ADIHEAP

Oracle Solaris 11.4 comes with ADIHEAP , a new security extension that acts as a management interface for allocators that implement ADI based defenses. In this blog entry we'll walk through the implementation of ADIHEAP within libc:malloc in Solaris.

Background

So why ADIHEAP at all? Shortly before the advent of libadimalloc, I started thinking about a better way to integrate ADI in the Solaris ecosystem. I love the technology and libadimalloc, while doing its job as a testing library, wasn't cutting it for production environments. LD_PRELOAD is a poor controlling interface and relinking existing applications just wasn't happening. It didn't really help that libadimalloc wasn't seen as a viable non-ADI allocator and hence had no consumer out of the box.

My vision for ADI was a bit different, involving the main Solaris allocators (libc:malloc, libumem and libmtmalloc) supporting ADI-based defenses and the Security Extensions Framework acting as a more advanced and coherent controlling interface. That's when ADIHEAP was born.

ADIHEAP brought all the usual security extensions goodness:

• progressive introduction to sensitive binaries, through the tagged-files model and binary tagging (ld -z sx=adiheap=enable)
• ease of switching between enabled/disabled state, especially system wide (capture different production scenarios)
• simplified/advanced testing through sxadm exec -i and the ability to unleash ADI checks over the entire system with model=all
• reporting through the Compliance framework 
• kernel and user process cooperation. The kernel knows whether the extension will be enabled on the target process and can do operations on its behalf. In particular, this vastly simplifies ADI support in brk-based allocators, since the kernel now pre enables ADI over the brk pages.

Of course, ADIHEAP by itself does very little without libraries support. The choice for the first ADIHEAP consumer (never introduce something without a consumer!) ended on libc:malloc, as it was/is small, self contained, (still) vastly used across the system and implemented as a non-slab, brk-based allocator, which provides an interesting alternative to the mmap-and-slab-based libadimalloc example.

libc:malloc

The implementation of libc:malloc hasn't changed much over the years and an older implementation can be found from the old open-source days. We'll use this public implementation as a reference, since the main goal of this entry is to show how an allocator can be evolved to incorporate ADI checks. Keep in mind that some of the code here described may not strictly apply to the 11.4 Oracle Solaris codebase.

libc:malloc is composed by two main files, mallint.h (which contains general definitions for the allocator) and malloc.c (which has the bulk of the implementation). It's a best fit allocator based on a self-adjusting tree of free elements grouped by size. Element information is contained inside the chunk itself and described by the TREE structure:

 110 /* structure of a node in the free tree */
 111 typedef struct _t_ {
 112         WORD    t_s;    /* size of this element */
 113         WORD    t_p;    /* parent node */
 114         WORD    t_l;    /* left child */
 115         WORD    t_r;    /* right child */
 116         WORD    t_n;    /* next in link list */
 117         WORD    t_d;    /* dummy to reserve space for self-pointer */
 118 } TREE;

Free objects use all the elements of the TREE structure and also have a pointer to the start of the chunk at the end of the buffer (which basically mimics the t_d member for chunks larger than sizeof(TREE)).

Allocated objects, instead, only use the first element, which contains the size of the chunk. The first element is ensured to be ALIGN bytes in size:

 103 /* the proto-word; size must be ALIGN bytes */
 104 typedef union _w_ {
 105         size_t          w_i;            /* an unsigned int */
 106         struct _t_      *w_p;           /* a pointer */
 107         char            w_a[ALIGN];     /* to force size */
 108 } WORD;

so that the data portion is guaranteed to start at the required alignment boundary, which is 16 bytes on 64-bit systems.

Since every chunk is guaranteed to be aligned to and a multiple of ALIGN, the last bits of the size member are equally guaranteed to be zero. libc:malloc exploits this to store further information in the last two bits, with BIT0 that specifies whether the block is in use (1) or not and BIT1 that specifies, for blocks in use, whether the preceding block is free. This information is used at free time to handle the coalescing of free blocks together (adjacent free blocks are always coalesced, in order to reduce fragmentation).

Allocations smaller than the TREE structure itself would waste a lot of space for the header, so the allocator provides a specialized path: ,smalloc(). Small allocations are based off on an array of linked lists of free chunks. Each entry of the array satisfies a multiple of WORDSIZE requirement, so that List[0] contains 16 bytes chunks, List[1] 32 bytes chunks and so forth up to sizeof(TREE).

libc:malloc grows its memory footprint through sbrk() in the _morecore() function, which extends the Bottom block, the last free block available. As it's common in this kind of allocators, the Bottom block is treated a bit specially.

Introducing ADI defenses to libc:malloc

Porting an allocator to use ADI requires to solve three main problems: buffer alignment/size, what versioning scheme to use and minimize performance degradation. The former two end up directly or indirectly affecting the latter. It's also paramount for the allocator to run with basically the same speed and memory consumption when the ADI protections are disabled, so that applications that do not have ADIHEAP enabled do not suffer of any potential regression.

The first step in opening the allocator to the ADI world is to change the minimum unit of operation to 64 bytes. Looking at the libc:malloc code, this means to move ALIGN to a value of 64. Unfortunately, in libc:malloc, ALIGN meaning is overloaded, since it's both the alignment that malloc() expects for the pointer and the alignment that chunks have in memory within the allocator. While this normally aligns (no pun intended), when it comes to ADI, it's decoupled: malloc() still lives happily with 16-bytes aligned pointers, but we need 64-byte aligned chunks that back them. This can be a common scenario in allocators, but is luckily also a fairly simple one to fix, by capturing the decoupling into different variables.

Actually, the best thing to do here is to rely as little as possible on static defines and have alignment and other requirements extracted at runtime, through an init function. The init function is also the best place to learn on whether we are going to enable ADI protections or not, by consuming the  sx_enabled(3C) interface from the security extensions framework:

    if (sx_enabled(SX_ADIHEAP)) {
         ...do ADI specific initialization...
         adi_enabled = B_TRUE;
    }

The ADI specific initialization should probably leverage the ADI API to collect information about the versioning space, the default block size, etc (see the examples in the mentioned blog entry).

Done with the alignment, we need to concentrate on the allocator metadata and how it affects chunks size and behavior. In the reference libc:malloc implementation, all the metadata concentrates into the TREE header, which is WORDSIZE * 6 = 16 * 6 = 92 bytes in size. This would dictate a minimum unit of allocation of 128 bytes, which is a bit scary for workloads that allocate lots of small objects. Ideally we'd like for the minimum unit to be 64 bytes and we can actually achieve that here with a more clever use of the data types. In fact only the very first member of the TREE structure needs to be 16 bytes in size, while all the others (with the exception of some implication for the last member as well) don't. This allows to get rid of the WORD union padding and just declare the members as struct pointers, which are 8 bytes in size. By keeping the first and last member as proto WORD and the rest as pointers we get to 16 * 2 + 8 * 4 = 64 bytes, which is exactly our goal.

Now that we have the minimum unit down to the cacheline size, we can start thinking about small allocations in the smalloc() path. There are basically two options: keep smaller buffers together under a common version, hoping to not have small controlled overflows between them or ditch the smalloc() algorithm altogether and declare that any allocation will at least get one 64 bytes chunk. Simplicity trumps memory usage by a fair bit here and we get the added benefit of a more secure implementation, so we say goodbye to smalloc() when ADIHEAP is enabled. With the proper adjustment at runtime for MINSIZE (another good candidate for a variable set up during the init path), smalloc() path is just never entered.

With the size/alignment solved, it's time for the versioning scheme, which again requires to evaluate the metadata behavior to make a decision. Either we isolate the header into its own 64 byte chunk, but de fact we end up extending the minimum allocation unit back to 128 bytes and that's not good, or just accept in the threat model that an underflow can target the size member. It's a tradeoff, but we can make a case for underflows to be significantly less common than overflows and that it has to be a controlled underflow (anything above 16 bytes would trap). It's not uncommon for security defenses to have to take tradeoffs and certainly we could provide a paranoid mode where the metadata is decoupled. I'm usually very complexity and knobs adverse, but that must not come with ineffective implementations. In this case, the major feature of ADI (detecting and invariantly preventing linear overflows) is maintained, so we can go for the simpler/faster implementation.

The versioning scheme is pretty standard for allocators that don't have isolated metadata, as we just need to reserve one version (1 is a popular choice) for free objects. At allocation time, instead, we're free to cycle to the rest of the versioning space. There are usually two different algorithms for versioning objects, which depend on whether the relative position between chunks is known and fixed at allocation time or not. For libc:malloc it clearly isn't, so we go for "randomization" plus verification. The fake randomization is based on RDTICK (the timestamp register) and improved with left and right verification.

Each time a version is selected, it is compared with the antecedent chunk and, if identical, it's incremented by one. The resulting value is then compared with the following chunk and, if identical, it's incremented again, taking care of looping back to 2 when hitting the end of the versioning space. This ensure the most important property for an ADIHEAP capable allocator to act as an invariant against linear overflows: no two adjacent allocated buffers should be found having the same version.

Run, Crash, Fix, Rinse and Repeat

ADIHEAP and the above prototype come along pretty nicely and seem to go through the most obvious testing of doing a bunch of malloc() and checking the returned version. It's with a lot of confidence that I type sxadm exec -s adiheap=enable /bin/ls, already imagining how the mail to showcase ADIHEAP to my colleagues would look like.

Segmentation Fault (core dump). Almost immediately and within libc:malloc.

Turns out that any non trivial sequence of memory operations requires coalescing and tree rebalancing, which do a heavy use of the LAST() and NEXT() macros.

 145 #define LAST(b)         (*((TREE **)(((uintptr_t)(b)) - WORDSIZE)))
 146 #define NEXT(b)         ((TREE *)(((uintptr_t)(b)) + SIZE(b) + WORDSIZE))

LAST() takes as an argument a TREE pointer and subtracts WORDSIZE. This effectively accesses the last 16 bytes of the previous chunk which, when free, contains the self pointer to the chunk itself. In other words, LAST() allows to reach back to the previous free chunk without knowing its size. NEXT() takes as a pointer a TREE structure, adds the size of the chunk and the extra WORDSIZE that corresponds to the size metadata at the start, effectively accessing the next adjacent chunk. This is generally fine and dandy, except that with ADIHEAP, the previous and next chunk most likely have mismatching versions and the segmentation fault is inevitable.

Once again we have two ways to fix this: we can either declare NEXT() and LAST() trusted paths and have them use non faulting loads that ignore ADI tagging, or we can read the previous/next ADI tag and fixup the pointer ourselves before accessing it. The first solution is a bit faster, but feels and looks more hackish in an allocator, so we go for the latter, rewrite NEXT() and LAST() as functions and wait to see how bad the performance numbers look like. Turns they are not that bad, so we go for it.

darkhelmet$ sxadm exec -s adiheap=enable /bin/ls
0_sun_studio_12.4  ssh-XXXX.xbadd     volatile-user
hmptemp            ssh-xauth-xSGDfd
darkhelmet$

Woot. I'm the coolest boy in town. Let's see what else we can run with ADIHEAP enabled. /bin/w ? Done. /sbin/ping ? Yeah. /bin/bash ?

Segmentation Fault (core dump). Once again within libc:malloc.

A few imprecations later, the fulguration on the road to Damascus. While our brk space is backed by ADI enabled pages, other adjacent memory isn't. Our versioning algorithm, when it allocates a new version, checks the previous and next chunk, but what if there is no previous or next chunk at all, because we are just at the start or at the end of the brk space (something that ASLR had hidden from previous tests)? We core dump attempting to use an ADI API over non ADI enabled pages.

libc:malloc only keeps track of where the brk ends, but we also need to know where brk started. In general, you may have to keep track of the boundaries of your allocated space, especially if you have it fragmented in memory. In this case, it's simple, we just store the starting address in our init function.

The above are just two examples of the many joy, segmentation fault, despair, debug, fix loops that touching an allocator brings. I spare you from many of the others, from off by one in the versioning code (that led to certain chunks getting adjacent ones retagged), to fixing and then fixing again memalign(), from discovering that emacs takes an entire copy of the lisp interpreter at build time, dumps its memory and restores it back when executed on another system and you've got to work around that to make it work (ignore free()s and replay any realloc() as if it was a new malloc() does the trick) and fixing python clever memory management code (see the objmalloc patch for an example of using a non faulting load in a performance sensitive code path).

Python, why you so slow?

The first performance numbers out of libc:malloc are encouraging, but while testing the objmalloc patch on Python things look ridiculously slow. A pkg solving operation that takes 30-40 seconds with the standard libc bumps up to minutes with ADIHEAP enabled, a 5x regression which is just as bad as unexpected.

Oracle Studio Performance Analyzer is a friend here and I start collecting samples to figure out where the problem lies. One outlier shows up: some PyList_Append() calls seem to spend an awful lot of time in realloc() compared to other paths that call into it as well, even other invocations of the function itself. Some DTrace allows to further isolate the realloc() sequences in PyList_Append(), identifying an interesting pattern, whereby PyList_Append() allocates a small amount of memory and reallocates it up multiple times in small chunks.

I take a long stare at the realloc() code, but nothing seems wrong and there aren't really any changes from the ADIHEAP code: adjacent blocks are checked and if one fitting is found, it is merged with the existing one and the rest is freed.

And then it hits me.

Some of this reallocation calls extend into the Bottom chunk, which is a couple of kilobytes in size.
Here is what happens:

• a small 64 byte chunk is allocated
• the chunk ends up being right next to the Bottom chunk
• the chunk is reallocated extending its size to 128/256 bytes
• the bottom chunk (which is 8/16K bytes) is splitted into two parts, the extra 64/192 bytes needed for the reallocation and the remaining 8/16K - 64/192 bytes
• the chunk version is extended into the extra 64/192 bytes
• the free version is stored on the remaining 8/16K bytes

multiply the above for a couple of incremental loops and we are doing kilobytes and kilobytes of unnecessary tagging! No kidding that this is killing performance.

I rewrite the free tagging code with an extra check, which evaluates the first and last chunk of the to-be-freed chunk: if both versions match the free version it means that we have been called on a split free block and so we have nothing to do and can just return. With this simple check alone, the 5x regression goes away and performance is almost on par with the non ADIHEAP case.

Almost, though. There is still a bit too much time spent in _morecore() compared to the vanilla libc case. The impact is significantly smaller, but notwithstanding this it's noticeable in the Studio analyzer output.

The lesson learned with realloc() sort of applies to _morecore() as well: when we extend the brk space, we ask for a couple of pages and mark them as free. Once again, we're tagging kilobytes and kilobytes of memory unnecessarily, because those pages come fresh (and empty) from the kernel. Just as we used as a sentinel in realloc() the presence of the free tag, we use as a sentinel here the presence of the universal tag, and limit ourselves to tag only the first and last 64 byte chunks of the freshly received memory.  Similarly, during a split, we check again for an underlying zero tag and convert the first chunk to the free tag.

This works because ADI allows to access with an arbitrary tag in the pointer memory that is physically tagged as universal match (0 or 0xF), which is what the kernel returns by virtue of zeroing the pages out. With this extra change there are more unexpected slowdowns and the pkg operation runs almost as fast as with the vanilla libc.

Debugging Easter Eggs

The ADIHEAP libc:malloc implementation is gathered towards production scenarios, but since I was there, I left a couple of debugging easter eggs that you might find interesting. You can turn these on through the following environment variables:

• _LIBC_ADI_PRECISE: when set, the application runs with ADI set to precise mode. This is handy when you have a store version mismatch and you want to pinpoint exactly where it happened. 
• _LIBC_MALLOC_ZEROFILL: when set, malloc() behaves just like calloc() and zeroes out a buffer before handing it out (useful in certain cases where memory is freed and later reused, but not initialized properly). This is implemented regardless of whether ADIHEAP is enabled, but is kind of cute with ADIHEAP, since we can use adi_memset() rather than adi_set_version() and get it basically for free.
• SXADM_EXTEND: ADIHEAP and ADISTACK can uncover a large number of latent bugs and hence bring disruption to software that otherwise "just works" (think of an off by one read outside of the allocated chunk, which is generally non fatal for an application, but immediately traps under ADIHEAP). For this reason, model=all is not exposed for ADIHEAP and ADISTACK. When this variable is set, model=all can be used there too, e.g. through SXADM_EXTEND=1 sxadm enable -c model=all adiheap. I'm a huge fan of model=all for testing and that's how I run my T7 environments, in order to catch bugs left and right (and it did catch many).

Final Words

I've been waiting to write this blog post for quite some time now and I'm glad this stuff is finally out. The most important message that should get conveyed is that, while there might be tricky corner cases, any default/system allocator can be converted to use ADI and benefit from the added security checks that come with it.

If you have a T7 and an Oracle Solaris 11.4 copy, you can now go out and play with sxadm and ADIHEAP (and ADISTACK, more about it coming), I look forward to hear from your experience!

Getting started with ADI

After a number of entries on different uses of ADI, it's time to get our hands dirty and walk through the C API that allows to experiment with it directly. The whole API set is quite simple and we'll use the Solaris implementation as a walkthrough. Linux is getting ADI support as well and while the interfaces are going to be a bit different (as an example, Linux is fond of mprotect() whereby Solaris prefers memcntl()), most of what we discuss here is going to apply there as well.

If you own or have access to a SPARC T7/M7 system running Solaris 11.3 or later, then, lucky you, you can get there and play. Otherwise, you may try the developer trial account on swisdev.oracle.com.

Enabling ADI on the current thread

Unless you're running in a Kernel Zone and haven't enabled the proper host compatibility (adi or native), if you are on proper hardware, ADI is supported by the kernel and available for every 64-bit process on the system. What this means is that your process can decide to start using ADI, but it still has to state that explicitly. This is provided by:

             int adi_set_enabled(int arg) 

arg is either ADI_ENABLE or ADI_DISABLE, to, respectively, enable and disable ADI. Under the covers, this has the kernel set/clear the MCDE bit in the PSTATE register, which stands for Memory Corruption Detection Enable, showing trace of the original name by which the technology was created.

At any point in time, a userland thread can inquiry on whether it has ADI enabled, and the interface is, not surprisingly:

            int adi_get_enabled(void)

which will return either ADI_ENABLE or ADI_DISABLE.

Learning about ADI properties

Magic numbers are the worst and, as much as possible, a well written piece of software should derive dynamically the properties of a running system and adjust accordingly. ADI API is not here to have you write poor software and hence we have:

           int adi_blksz(void)
           int adi_version_max(void)
           int adi_version_nbits(void)

adi_blksz() returns the granularity to which the versioning applies. Today, ADI operates on 64 byte cache lines, so 64 bytes is also the necessary alignment. adi_version_nbits() returns the number of bits, starting from the topmost bit in the 64-bit virtual address, that are used to represent the associated ADI version and adi_version_max() the largest color that is reliably usable on the architecture. A common initialization routine for a piece of software (e.g. a malloc() implementation) would collect these values to tune itself, with code along these lines:

void

initialize_adi(void)
{
        if (adi_set_enabled(ADI_ENABLE) < 0) {
                perror("ADI initialization failed");
                adi_enabled = B_FALSE;
                return;
        }

        adi_enabled = B_TRUE;

        alignment = adi_blksz();
        nbits = adi_version_nbits();
                
        if (alignment < 0 || nbits < 0) {
                adi_enabled = B_FALSE;
                return;
        }

        maxversion = (uint_t)adi_version_max();
}

If we build and run it on a M7 and dump the values we get something along these lines:

darkhelmet$ ./adi_base_test 
Block size and alignment: 64 bytes.
Available version bits: 4
Maximum usable version: 13
[...]
darkhelmet$

64 and 4 match what we know and expect about the ADI implementation. The maximum usable version is, instead, a tiny bit surprising: we know that "all zeroes" or "all ones" (so, 0 and 15) are universal matches which allow a load/store with any arbitrary tag, but that should still leave 14 as an usable version. The reason why it isn't comes from an architecture implementation detail.

On M7, we keep version bits separately protected in the L2$ (all 8 ways of a set in a check-word). If an Unrecoverable Error (UE) happens, they are flushed and if a dirty line is present, it's written back with version 14, regardless of the original version. Since a userland program might decide to rely on ADI for correctness, it would be cumbersome to figure out whether an exception raised on the 14 version was a consequence of a legit condition or a UE, so we simply restrict the versioning space.

The upcoming M8 architecture lifts this limitation by doing the right thing on UE and writing back the correct color. This is a good example of why one should never rely on magic numbers: by gathering the maximum version at runtime, your software is guaranteed to take advantage of all the available versioning space.

Setting/Getting Tags for VA ranges

Now that we have enabled ADI for the running thread (PSTATE.mcde) and have all the necessary information to produce and place a tag on a virtual address (alignment, number of version bits, maximum version), all that is left is to effectively start tagging memory.

The first mandatory step is to enable ADI onto the target pages. In fact, ADI is not implicitly enabled for a TTE (Translation Table Entry), but, instead, a new bit is introduced (TTE.mcd), that specifies whether it's on or off. The main reason for this is that the processor disables store merging for ADI enabled pages, which might translate in some (generally minimal) performance impact. Setting TTE.mcd is up to the kernel and Solaris offers two different API to gently ask for it:

              mmap(hint_addr, len, prot, MAP_ADI, ...)

              memcntl(addr, len, MC_ENABLE_ADI, ...)

In both cases, assuming that everything is right, TTE.mcd will be set for all the pages that make up the requested len range. The kernel makes no promises on the versions that will be set for those pages initially (you might experience that,  e.g. for anonymous pages, they are zeroed out, but please don't rely on it) and leaves it up to the userland application.

Setting versions is a two steps process. First of all, we need to set the proper tag to the cache line bits, which are exposed through dedicated Address Space Identifiers (ASI) and then mirror the tag onto the pointer used to access the memory range. ASIs are basically the SPARC architecture swiss army knife: they allow to expose different address spaces (e.g. select between the primary or secondary context with a load/store), I/O ranges, internal registers or otherwise influence the load/store behavior. Alternate versions of load/store, identified by a 'a' in the mnemonic at the end of the name (e.g. stoa), allow to directly specify the ASI to operate on.

Two ASIs are of interest for ADI setting/getting of versions by unprivileged software:

• ASI_MCDP (0x90): Memory Corruption Detection Primary, takes the virtual address as relative to the primary context and sets/gets the specified version.
• ASI_MCDSBP (0x92): Memocry Corruption Detection Block Init Store Primary, which optimizes the operation of zero'ing a block (64 bytes) while also setting the version. 

Of course, one doesn't need to do any of this manually, but, instead, proper APIs are provided, that also deal correctly with misaligned addresses:

             caddr_t adi_clr_version(caddr_t addr, size_t size)
             int adi_get_version(caddr_t addr)
             caddr_t adi_set_version(caddr_t addr, size_t size, int version)
             caddr_t adi_memset(caddr_t addr, int c, size_t size, int version)

Their name is quite self-explanatory and so should be the behavior, given the introduction above (which might actually come back handy to you in case you find yourself willing to optimize some hot path). All the setting functions return an address which is already properly tagged, as we can see in the next example:

        caddr_t buffer;
        buffer = mmap(NULL, 8192, PROT_READ|PROT_WRITE,
            MAP_ANON|MAP_PRIVATE|MAP_ADI, -1, 0);
        if (buffer == (caddr_t)MAP_FAILED) {
                perror("mmap");
                exit(EXIT_FAILURE);
        }

        printf("Buffer address before versioning: %p\n", buffer);
        buffer = adi_set_version(buffer, 128, 7);
        printf("Versioned buffer address: %p\n", buffer);       

which, once run, gives us:

darkhelmet$ ./adi_base_test
[...]
Buffer address before versioning: ffffffff7f5ec000
Versioned buffer address: 7fffffff7f5ec000

[...]
darkhelmet$

with the topmost nbits properly set to reflect the ADI version we specified. If we attach and disassemble the call to add_set_version(), being careful to pick the symbol with the proper capability tag, eventually we see:

adi_base_test:580319*> ::nm ! grep adi_set_version
0x00000001001013c0|0x0000000000000000|FUNC |GLOB |0x0  |UNDEF   |adi_set_version
0xffffffff7ef289f0|0x00000000000001a8|FUNC |LOCL |0x0  |19      |adi_set_version%sun4v-adi
0xffffffff7edea9e0|0x000000000000001c|FUNC |GLOB |0x3  |19      |adi_set_version
adi_base_test:580319*> 0xffffffff7ef289f0::dis ! ggrep -B 2 stxa
libc.so.1`adi_set_version%sun4v-adi+0x108:      ldsb      [%l2], %o2
libc.so.1`adi_set_version%sun4v-adi+0x10c:      sra       %i2, 0x0, %o0
libc.so.1`adi_set_version%sun4v-adi+0x110:      stxa      %o0, [%i4] 0x90       
--
libc.so.1`adi_set_version%sun4v-adi+0x16c:      mov       %l5, %o5
libc.so.1`adi_set_version%sun4v-adi+0x170:      sra       %i2, 0x0, %o7
libc.so.1`adi_set_version%sun4v-adi+0x174:      stxa      %o7, [%o5] 0x90       
adi_base_test:580319*> 

with the calls to store-alternate with the expected ASI.

adi_memset() operates basically in the same way, although it is faster than just doing a memset() followed by an idi_set_version().

What happens on a ADI mismatch?

Let's trigger an ADI mismatch from within our code:

       /* Tag the first two cachelines */
        tagged_buffer = adi_set_version(buffer, 128, 7);
        printf("Versioned buffer address: %p\n", tagged_buffer);        

        /* Tag the next two cachelines with a different value */
        nextbuffer = adi_set_version(buffer + 128, 128, 8);
        printf("Versioned next buffer address: %p\n", nextbuffer);

        /* Access with correct version goes through */
        tagged_buffer[0] = 'a';
        printf("first store acces: %c\n", tagged_buffer[0]);
        /* Access with incorrect version traps */
        tagged_buffer[130] = 'b';
        /* segfault...*/        
        printf("second store access: %c\n", nextbuffer[2]);

The second access from tagged_buffer, performed with a pointer with version 7 over a memory line tagged with version 8 is detected by ADI, which nullifies the store (mismatching stores never go through) and raises an exception, whose final outcome is to send a SIGSEGV down to the process. Let's see it in action:

darkhelmet$ ./adi_base_test
[...]
Buffer address before versioning: ffffffff7f5ec000
Versioned buffer address: 7fffffff7f5ec000
Versioned next buffer address: 8fffffff7f5ec080
first store acces: a
Segmentation Fault (core dumped)
darkhelmet$

We got the expected Segmentation Fault and a nice core dump. Let's dig into it a little bit:

darkhelmet$ mdb ./core
Loading modules: [ libc.so.1 ld.so.1 ]
adi_base_test:core> ::status
debugging core file of adi_base_test (64-bit) from darkhelmet
file: /tmp/adi_base_test
initial argv: ./adi_base_test
threading model: raw lwps
status: process terminated by SIGSEGV (Segmentation Fault)
, ADI deferred mismatch, pc=100001188
adi_base_test:core> 100001188::dis
main+0x130:                     call      +0x100320     
[...]
main+0x158:                     stb       %l0, [%i4 + 0x82]
[...]
main+0x17c:                     restore
_init:                          save      %sp, -0xb0, %sp
adi_base_test:core> ::regs
%g0 = 0x0000000000000000                 %l0 = 0x0000000000000062 
%g1 = 0x0000000000000004                 %l1 = 0x0000000100000c80 
%g2 = 0x0000000000000000                 %l2 = 0x7fffffff7f5ec000 
%g3 = 0x0000000000000000                 %l3 = 0x0000000000000000 
%g4 = 0x00000000782f296a                 %l4 = 0x0000000000000061 
%g5 = 0xffffffff7f0486e4 libc.so.1`_sobuf+0x18 %l5 = 0x0000000100000cf0 
%g6 = 0x0000000000000000                 %l6 = 0x0000000000002800 
%g7 = 0xffffffff7f5c2a40                 %l7 = 0xffffffff7f548f08 
%o0 = 0x0000000100000d78                 %i0 = 0x0000000000000001 
%o1 = 0x0000000000000000                 %i1 = 0xffffffff7ffff808 
%o2 = 0x0000000000000000                 %i2 = 0xffffffff7ffff818 
%o3 = 0xffffffff7f030000                 %i3 = 0x8fffffff7f5ec080 
%o4 = 0x0000000000000000                 %i4 = 0x7fffffff7f5ec000 
%o5 = 0xffffffff7f037fdc libc.so.1`_iob+0xa4 %i5 = 0xffffffff7f5ec000 
%o6 = 0xffffffff7fffee71                 %i6 = 0xffffffff7fffef51 
%o7 = 0x0000000100001190      main+0x160 %i7 = 0x0000000100000ea8 _start+0x108

 %ccr = 0x99 xcc=NzvC icc=NzvC
   %y = 0x0000000000000000
  %pc = 0x0000000100101480 PLT=libc.so.1`printf
 %npc = 0x0000000100101484 PLT=libc.so.1`printf
  %sp = 0xffffffff7fffee71
  %fp = 0xffffffff7fffef51

 %asi = 0x82
%fprs = 0x07
adi_base_test:core> 

Two things are immediately evident:

• ADI tells us that a trap was raised by the execution at pc=100001188 (main+0x158), which is where we expected it to happen, at the store into the mismatching cache line.
• There is surprisingly scarce information about the trap: on what virtual address? because of what mismatching value? All we get reported is a program counter and that 'deferred' definition, which seems to be intuitively matched by the fact that %pc and %npc are not at the reported faulting instruction, but somewhere further down into the next printf() call.

For a feature that was born to be a debugging tool, this lack of details is fairly unexpected. So, what's going on here? There are two types of traps that can be risen by an ADI mismatch: a precise trap and a deferred trap. Precise trap stop the thread immediately and so the architecture and the kernel can conspire to send out to userland all the relevant information about the exception. Deferred traps happen some time later, based on a number of conditions that we'll see in a short.

Loads always raise a precise trap, stores, instead, a deferred one. This is because on SPARC we have a store buffer that queues (up to 64) stores on commit before they are performed by the L2$ and the version mismatch is not detected until the L2$ performs the store. This can happen on an explicit flush (membar) or when the buffer is full and goes through. There are a number of implicit situations that lead to a membar, e.g. the userland application performing a system call, but by the time the deferred trap is delivered (and the program stopped), some instructions have passed and the hardware has no ability to keep any information on the original condition beyond the PC at which it happened.

Disabling store buffering has a significant performance penalty and is recommended only on debugging scenarios, to further drill down the details of a bug. We offer an API to enable what we called precise mode that allows to control it:

          int adi_get_precise(void)
          int adi_set_precise(int mode)

where mode is either ADI_PRECISE_ENABLE or ADI_PRECISE_DISABLE. The simplest way when writing a memory allocator (or some other debugging/protection) with ADI is to provide a tweakable way (e.g. an environment variable or a security extension property) to control the ADI behavior. As mentioned, you'll want to run with precise mode disabled in production.

Let's see an example of the amount of information we can gather when we hit a precise trap. We'll do so by tweaking our code a little and and making it trap over a load, rather than a store.

       /*
         * Do a proper store access and modify the printf to read from
         * tagged_buffer, which has an incorrect version.
         */ 
        nextbuffer[2] = 'b';
        printf("second store access (correct): %c\n", nextbuffer[2]);
        printf("second store access (mismatch): %c\n", tagged_buffer[130]);

And run it, along with evaluating the expected core dump:

darkhelmet$ ./adi_base_test
[...]
first store acces: a
second store access (correct): b
Segmentation Fault (core dumped)
darkhelmet$ mdb ./core
Loading modules: [ libc.so.1 ld.so.1 ]
adi_base_test:core> ::status
debugging core file of adi_base_test (64-bit) from darkhelmet
file: /tmp/adi_base_test
initial argv: ./adi_base_test
threading model: raw lwps
status: process terminated by SIGSEGV (Segmentation Fault), pc=1000011e4
, ADI version 8 mismatch for VA ffffffff7f5ec082
adi_base_test:core> ::regs
%g0 = 0x0000000000000000                 %l0 = 0x0000000100101000 
%g1 = 0x0000000000000004                 %l1 = 0x0000000100000cf0 
%g2 = 0x0000000000000000                 %l2 = 0x8fffffff7f5ec082 
%g3 = 0x0000000000000000                 %l3 = 0x0000000000000062 
%g4 = 0x00000000222f2967                 %l4 = 0x0000000000000061 
%g5 = 0xffffffff7f0486f0 libc.so.1`_sobuf+0x24 %l5 = 0x0000000000002880 
%g6 = 0x0000000000000000                 %l6 = 0x0000000000002800 
%g7 = 0xffffffff7f5c2a40                 %l7 = 0xffffffff7f548f08 
%o0 = 0x0000000100000da0                 %i0 = 0x0000000000000001 
%o1 = 0x0000000000000021                 %i1 = 0xffffffff7ffff7f8 
%o2 = 0x0000000000000000                 %i2 = 0xffffffff7ffff808 
%o3 = 0xffffffff7f030000                 %i3 = 0x8fffffff7f5ec080 
%o4 = 0x0000000000000000                 %i4 = 0x7fffffff7f5ec000 
%o5 = 0xffffffff7f037fdc libc.so.1`_iob+0xa4 %i5 = 0xffffffff7f5ec000 
%o6 = 0xffffffff7fffee61                 %i6 = 0xffffffff7fffef41 
%o7 = 0x00000001000011e0      main+0x170 %i7 = 0x0000000100000ee8 _start+0x108

 %ccr = 0x99 xcc=NzvC icc=NzvC
   %y = 0x0000000000000000
  %pc = 0x00000001000011e4 main+0x174
 %npc = 0x0000000100101480 PLT=libc.so.1`printf
  %sp = 0xffffffff7fffee61
  %fp = 0xffffffff7fffef41

 %asi = 0x82
%fprs = 0x07
adi_base_test:core> 

We get all the nice debugging/detailed information that we expected: the instruction pointer, the ADI version mismatch that happened and for what virtual address. The virtual address is always reported normalized, although we can inquiry about the ADI version that was associated through the ::adviser command in mdb:

adi_base_test:core> ffffffff7f5ec082::adiver
addr: ffffffff7f5ec082 cache ver: 8
adi_base_test:core> ffffffff7f5ec070::adiver
addr: ffffffff7f5ec070 cache ver: 7
adi_base_test:core> 

Since we have an exact picture of the status of registers at the time of the trap, we can further look at the instruction pointer and registers to see from what virtual address and with what version the access was performed:

%o4 = 0x0000000000000000                 %i4 = 0x7fffffff7f5ec000 

adi_base_test:core> 0x00000001000011e4::dis
[...]
main+0x174:                     ldsb      [%i4 + 0x82], %o1

And, as expected, a version 7 address starting two cache lines before shows up.

Source Code Example

As a general reference, here is the full source code from the last example we discussed, with the mismatching trap on a load access.

#include 
#include 
#include 
#include 
#include 
#include 

/*
 * Global varaibles that control ADI behavior for the application.
 */
boolean_t       adi_enabled;
int             alignment;
int             nbits;
uint_t          maxversion;
uint_t          mask;

/*
 * Gather information at runtime about ADI
 */
void
initialize_adi(void)
{
        if (adi_set_enabled(ADI_ENABLE) < 0) {
                perror("ADI initialization failed");
                adi_enabled = B_FALSE;
                return;
        }

        adi_enabled = B_TRUE;

        alignment = adi_blksz();
        nbits = adi_version_nbits();
                
        if (alignment < 0 || nbits < 0) {
                adi_enabled = B_FALSE;
                return;
        }

        maxversion = (uint_t)adi_version_max();
        mask = (1 << nbits) - 1;
}

int main(int argc, char **argv)
{
        initialize_adi();

        if (adi_enabled) {
                printf("Block size and alignment: %d bytes.\n", alignment);
                printf("Available version bits: %d\n", nbits);
                printf("Maximum usable version: %d\n", maxversion);
        }

        caddr_t buffer;
        caddr_t nextbuffer;
        caddr_t tagged_buffer;

        buffer = mmap(NULL, 8192, PROT_READ|PROT_WRITE,
            MAP_ANON|MAP_PRIVATE|MAP_ADI, -1, 0);
        if (buffer == (caddr_t)MAP_FAILED) {
                perror("mmap");
                exit(EXIT_FAILURE);
        }

        printf("Buffer address before versioning: %p\n", buffer);
        /* Tag the first two cachelines */
        tagged_buffer = adi_set_version(buffer, 128, 7);
        printf("Versioned buffer address: %p\n", tagged_buffer);        

        /* Tag the next two cachelines with a different value */
        nextbuffer = adi_set_version(buffer + 128, 128, 8);
        printf("Versioned next buffer address: %p\n", nextbuffer);

        /* Access with correct version goes through */
        tagged_buffer[0] = 'a';
        printf("first store acces: %c\n", tagged_buffer[0]);
        
        /*
         * Do a proper store access and modify the printf to read from
         * tagged_buffer, which has an incorrect version.
         */ 
        nextbuffer[2] = 'b';
        printf("second store access (correct): %c\n", nextbuffer[2]);
        printf("second store access (mismatch): %c\n", tagged_buffer[130]);
}

ADI vs ROP

A couple entries ago, I've covered how we planned to use ADI to protect against heap attacks. If you've been following the stream of patches for the Solaris userland gate, you may have noticed this commit a few months ago. This commit added the necessary macros to the userland gate to enable ADIHEAP and ADISTACK, two new security defenses that will show up in the upcoming release of 11.4.

The ADIHEAP extension allows to extend system libraries (e.g. libc:malloc()) with ADI-based protections, while still retaining the ability to control whether the extension is enabled or not through binary tagging and sxadm exec (both covered in this previous blog entry). A more detailed discussion of the implementation for specific libraries is deferred to the release of 11.4.

The ADISTACK extension, instead, uses ADI transparently to any arbitrary process/binary to mitigate against Return Oriented Programming (ROP) attacks. While I'm deferring a detailed analysis of this one to the release of 11.4 as well, recently Steve Sistare (one of the folks behind our ADISTACK implementation, along with Anthony Yznaga, myself and Steve Chessin) commented around the stack defense on the sparclinux mailing list, so I figured it might be a good time to recap it a bit in a blog entry.

Lookin' Through The (Register) Windows

ROP attacks, as the name suggests, target the return address of a procedure and build a sequence of entry points to gadgets (brief instruction sequences in the process address space that conclude with a return instruction) that compose the attacker payload. ROP attacks are popular today and are the direct consequence of the defensive side taking away the ability to store an attacker controlled payload and jump to it, through what is traditionally known as W^X/DEP (ensure that no mapping that is simultaneously writeable and executable exists in the process address space).

ROP attacks on the SPARC architecture have been throughly covered back in 2008, by the "When Good Instructions Go Bad:Generalizing Return-Oriented Programming to RISC" paper. In this entry, I'm just going to briefly summarize the characteristics of the SPARC architecture that make them and the respective mitigation possible.

The whole function call/return model on SPARC is predicated around the concept of register windows. A register window consist of 24 directly accessible registers, divided in three parts: 8 local (private to the function), 8 in and 8 out registers. In and out registers are the heart of parameter passing and value returning across functions. In fact, register windows overlap: when function A calls function B, the out registers from function A become the in registers for function B, which also gets a fresh set of local and out registers. Later, when B returns, it can use its in registers to make the return values pop into the A register window. Some registers have special meanings: %i6 contains the frame pointer (%fp) and %i7 contains the return address. This document, although centered to the V8 architecture (remember to double the size of registers), nicely recaps the whole window registers design and operation and so does the aforementioned paper.

The number of physical registers cannot grow indefinitely, so there is an upper limit to the number of register windows. This means that an application can find itself about to do a call, but with no register window to shift to. This situation will generate a SPILL trap, transferring control to the operating system and asking to please save the existing register window somewhere and buy a new one for the process. This "somewhere" is, of course, the stack (partially defeating the original purpose of register windows), whereby enough space was conveniently left aside by the save instruction in the function prologue. If we ignore for a moment local variables and any other use of the stack (and just concentrate on register windows), it's easy to realize that the save instruction needs to reserve at least 16 * register_size (8 in and 8 local) bytes which, on SPARC V9 (register_size == 8 bytes), puts us conveniently to 128 bytes (two cache lines). The sister condition to a SPILL trap happens when the program tries to restore back to a previous register window, but such window is currently invalid. In this case, the OS receives a FILL trap and needs to recover the saved registers from the stack and "provide" them back to the caller.

The whole stream of FILL and SPILL traps happens transparently to the application.

Leveraging SPILL/FILL traps with ADI

SPILL and FILL traps provide something pretty unique in the OS/arch landscape: the Operating System has a chance to check the saved register values right at the prologue and right after the epilogue of a function. This possibility hasn't really gone unnoticed in the past and back in 2002 a stack protection known as StackGhost was presented for OpenBSD. It proposed two different approaches to more or less minimize the performance impact and more or less effectively defeat stack smashing attacks: 

• obfuscate the return address: the OS encrypts the return address on SPILL and decrypts it on FILL. XOR is the obvious choice for speed and simplicity, but has some significant limitation (a sufficiently large infoleak allows to recover the process cookie and it's easily subject to perturbation of lower bits), a more sophisticated algorithm may require more instructions (despite the speed improvement with the crypto instructions since 2002). In either case, this approach directly affects userland: debuggers and the like need to be extended in order to understand the 'encrypted' return address (an extra cost that is better to avoid for adoption). The frame pointer and the other register contents are not protected at all.
• create a shadow stack: the kernel keeps a in-kernel shadow stack and updates it at every SPILL/FILL event. This is a much more robust defense and one that has had a number of unfinished attempts (internally) also for Solaris. There are two tricky parts with it: the first one is the performance impact. SPILL/FILL traps are frequent and are hence hugely optimized, adding extra code to copy things to a shadow stack can impose a significant penalty. The second one is related to the well known CFI nightmares of longjmp(), setjmp() and makecontext(), which can create non linear modification to the control flow and require further complexity to clean the shadow stack properly. On top of this, also the memory management of the shadow stack space can add further food for thoughts, especially if one wants to protect all the saved registers. 

Enter ADI. Once again, it acts as a game changer, since it can defer to the architecture the ungrateful job of evaluating memory accesses. In particular, the kernel can tag with a dedicated (randomized) color the register save area on the stack on SPILL and clear it up on FILL. Any attempt to overflow from an existing buffer on the stack into the save area during program execution is then automatically caught and stopped, leading to a SIGSEGV. Similarly, attempts to infoleak the save area contents are detected and stopped as well.

Adding a color requires a significantly smaller amount of instructions then a full shadow stack and, through the ADISTACK security extension, we know whether we have to pre-enable ADI over the stack pages of a process. This further helps reducing the impact of the protection on binaries/processes that have it disabled. On top of that, Steve Sistare and Anthony Yznaga came up with a pretty cool trick to completely eliminate any overhead of ADISTACK specific instructions from unaffected processes (and speed up ADISTACK itself), but I'm leaving this one a to a future (perhaps from them) entry. For this blog post, just consider that ADISTACK has basically no impact when disabled, something that is, indeed, pretty nice for a lightweight CFI solution.

longjmp(), setjmp() and makecontext() are augmented with proper version-clearing paths and similar code is exposed, through APIs, to all those pieces of software (Java I'm looking at you) that want to do internal stack management. Lastly, through the use of non-faulting loads, trusted paths in userland (e.g. when issuing a system call with a variadic number of parameters, and hence arbitrarily hitting stack pieces or when inspecting the stack from within the process) can be created. The trusted path code doesn't need to know the color value in advance, nor needs to go through the dance of retrieving it from the pointer - fixing the accessing pointer - do the load, but can instead simply use the ASI_NOFAULT identifier when accessing the value with a single, direct, load. The ability to create a trusted path is an often overlooked property of a security feature and one that can prove crucial when trying to meet acceptable performance results (as an example of this, I've some time ago fixed Python to work nicely with ADI through the use of non-faulting loads).

The use of ADI doesn't come without some limitation, which doesn't permit to this protection to elevate to the holy grail of invariant. First of all, an ADI protected region can be subject to an arbitrary write attack, whereby the attacker is capable of constructing the target pointer with the proper version. Randomizing the saving area version helps a bit, but the randomization range is extremely small and easy to bruteforce/guess. Life would be fantastic if instead of being able to tag with a color, we were able to temporarily mark the region as read-only, but that's a different story, which I hope to tell one day.

Second, the SPARC ABI mandates a 16-byte alignment for the stack, which translates to the register save area not being always aligned to 64-byte on existing software. Since the save area is 128 bytes, we're always guaranteed to version at least one cacheline worth of space. this may mean that the two key pieces that we want to protect (%i6 and %i7), which sit at the top of the save area, end up exposed (but with a tagged cacheline that catches linear overflows in between). This limitation can be reduced by imposing a 64-byte alignment: the kernel, the compiler and the userland crt objects can conspire to not create (or reduce to a minimum, depending on performance requirements) misalignment.

Leveraging ADI through the Compiler

ADISTACK has a few characteristics that make me a huge fan of it: it's transparent to the target process (which means that it can be easily applied to third party software), has a very low performance impact when enabled and has zero performance impact when disabled. ADISTACK focuses on one specific target: the saved registers, in particular %fp and the return address. This is both really good (do one thing, but do it right) and "bad" (as it ignores, by design, stack smashing attacks that target other adjacent local variables.

A more complex, but more comprehensive, protection can be designed to include detection of linear overflows across local variables, by having the compiler either separate each one into dedicated cachelines or leave redzone "gaps" between them, and providing an entry point to each function to call into a tagging subroutine. This is not dissimilar, impact-wise, from other cookie-based stack protection solutions, like GCC StackGuard/-fstack-protector and can implement similar solutions to improve performance, for example through the identification of functions that truly need a protection and those that don't have any overflowing object in their frame. In the very same way, such compiler based protection do leave some performance impact also when disabled, by virtue of adding some extra code to some/all functions.

Hardware-based buffer overflow defenses compared: SSM/ADI vs MPX

One of the most common questions when discussing SPARC M7 SSM/ADI (Silicon Secured Memory/Application Data Integrity, from here on only referred to as ADI) is "how does it compare to XYZ?", where XYZ is some other architecture security feature. In this blog entry we'll see how ADI stacks against another buffer overflow protection security feature, Intel Memory Protection eXtensions (MPX).

Before starting, a somewhat obvious, but necessary, observation: these features do not provide security "by themselves", instead, they provide building blocks to develop protections on top. In other words, they are meant to, and need to, be (extensively) leveraged by software implementations to be in any way effective.

ADI

I've already covered ADI extensively in another blog entry, so I won't dwell too much into the details here and just provide a quick recap. ADI implements a form of memory tagging and checking: individual cache lines can be assigned a color (a numeric value ranging from 0 to 16) and at load/store time such color is checked against the color saved onto the 4 topmost unused bits of the target virtual address. If the color matches, the operation goes through; if it doesn't, an exception is raised and the instruction is ignored. 0 and 16 are universal matches: a cache line colored with either of those will not fault regardless of the color used in the virtual address. ADI only works on the data path, it has not effect on the instruction fetch and execute process.

Memory tagging is not a revolutionary concept: it has actually floated a lot across academia for a while. What really makes ADI stand out, though, is that for the first time tagging is both granular enough (64 bytes -- a cache line) and seamlessly integrated in the architecture to be used at large for general purpose scenarios (e.g. a memory allocator). Oh, and it's fairly performant, too. In this respect, SPARC is the first "mainstream" architecture to achieve that.

From a security perspective, ADI does one thing and does it great: detect linear overflows. A linear overflow happens when a program reads past the boundaries of a buffer. If we can guarantee that two adjacent buffers never share the same color, we can guarantee that a read starting from one will never successfully hit the other. If this doesn't seem like much, look at it as a way to put a definitive end to heap overflow exploitation.

ADI does reasonably well also for non malicious stray pointers: by randomizing the assigned colors at runtime, there is a fair chance that a stray pointer will not have a matching color. For malicious (read: attacker forged) stray pointers, the music changes. In fact ADI isn't particularly suited to protect against arbitrary read/write patterns. While it does add a deterrence (the attacker still needs to leak or guess the target color), the range is super small, just fourteen values, and easy to brute force/guess.

When used for system level defenses, e.g. inside memory allocators, ADI works well with lots of software, but still changes two main assumptions: (1) math can be exercised directly onto pointers and (2) the ability to access one byte into a page implies the ability to access any other byte in the page in the same way. (1) can be solved by normalizing pointers before any math operation, while (2) can be solved by either loading the version and adjusting the pointer accordingly or, only for reading, by using a non faulting load. Non faulting loads are particularly interesting because they provide an efficient way to implement trusted paths (portions of the program that have a legitimate reason to bypass ADI checking when accessing a given memory location). As an example of this, see this recent fix for Python to make it work well with an ADI enhanced memory allocator.

MPX

Another approach to detect buffer overflows is to add instrumentation where the buffer is accessed, to verify whether the read/write operation stays within the boundaries. This approach has two drawbacks that make it less suitable for production scenarios: (1) it adds some (non marginal) performance penalty, since extra instructions need to be executed and (2) it cannot be switched on/off when deploying a system or needing relief when hitting a false positive (if binary recompilation is used, then a problem arises if the package manager or some other entity relies on the hash of the binary). Intel proposed solution to the above two problems is the Memory Protection eXtensions technology.

MPX introduces a couple of new registers and a handful of instructions that operate on them. The new registers BND[0..3] are 128 bits long, with 64-bit used to store the upper bound and 64-bit used to store the lower bound of a buffer. Three new instructions allow to check a pointer against said bounds: BNDCL (Bound Check Lower Bound), BNDCU (Bound Check Upper Bound) and BNDCN (Bound Check Upper Bound not in 1s Complement). For example, bndcl (%rax), %bnd0 compares the contents of RAX against the lower bound set in BND0. If the check fails, a new #BR exception is raised. BNDC* instructions are very fast, to reduce the performance penalty.

Of course, 4 bound registers aren't enough for every buffer used in a program, so MPX supports a number of ways to swap back and forth the necessary upper/lower bound values: BNDMK (Bound Make) stores a pair of addresses into one of the BNDx registers, BNDMOV (Bound Move) loads a pair from a location in memory and BNDLDX/BNDSTX manage the Bound Table, which stores information about a pointer and its bounds. Bound Tables are arranged in a two-level directory in memory and the root address is stored in BNDCFGU (user land, CPL=3) or BNDCFGS (kernel land, CPL=0). BND*X and BNDMOV instructions simplify bounds management, but do logically introduce a larger performance hit.

MPX relies heavily on the compiler/instrumentation to be effective: while the programmer can add manual checks, it's the compiler that needs to identify the places where a check is necessary and introduce the proper instruction sequences there. The smarter this logic is, the better the performance is going to be. A quick analysis of MPX performance (and more) is available on the AddressSanitizer wiki.

MPX is fully retro compatible, as its instructions use prefixes that are treated as NOPs on older architectures. This allows to build one single binary and distribute it around. The same also happens when MPX is disabled, which allows admins to toggle on/off the protection on a binary basis. MPX interoperates well with existing code, allowing to mix instrumented and non instrumented components into the same process (with some caveat). The idea there is to allow MPX to be introduced gradually in large applications, starting with the sensitive modules.

MPX vs ADI

Both MPX and ADI aim at detecting buffer overflows, although they look at the buffer from two different angles. Intel MPX aims at providing instructions so that an about to be performed operation can check whether what it wants to do over/underflows the buffer boundaries, while ADI aims at letting the operation go, but detect, through color violations, whether it does something wrong as it happens. From this perspective, ADI scales better for long lived buffers that might be accessed in various places within an application, as you only have to to tag the buffer once at creation time and the hardware will do the rest. The chance of missing one access point, due to a particularly odd construct, is a non issue with ADI. This is a particularly nice property when looking at building an invariant on top of it.

Similarly, the above also means that ADI is simpler to retrofit into legacy applications. Where MPX would require a recompilation/translation, with ADI one can design system level defenses (e.g. at the allocator level, which is the only entity responsible of the tagging) that can be enabled on legacy applications. Of course, if an application uses its own memory allocator or if one is looking at protecting other data regions, code changes (or compiler support, e.g. to track .data segment or automatic variables) is necessary, just like with MPX.

ADI imposes more constraints on the programmer. Minimum granularity is 64 bytes and pointers need to be aligned to - or contained within - the cache line boundaries. MPX has much better precision, as it can detect up to 1-byte overflows in just about any scenario (e.g. buffer overflow across structure members). More generally, any type of erroneous pointer access can be detected, provided that the proper bounds are set. This makes MPX simpler to apply to an arbitrary part of an application, regardless of what kind of data it is operating on.

Both technologies are meant to mix well within an application (ADI use is for the most part implicit, as demonstrated by the ability to retrofit into legacy applications) and do not require a special binary to run on older architectures. When disabled, MPX still imposes some performance penalty, both directly (very minimal, the NOPs take space and need to be executed) and indirectly (side effect of disabling certain optimizations that collide with the instrumentation engine). With ADI, at least for the cases where no compiler support is needed, there is no impact when it is disabled.

Both technologies are meant to be fast, but interesting side effects show up with large applications. MPX memory consumption (for Bound Tables or BNDMOV backup storage) grows significantly if the application manipulates a large number of pointers and similarly performance drops down due to the large amount of swapping necessary to set BND[0..3] registers. Also, while it's true that MPX can be gradually introduced into an application (by limiting the places where it is used), it is still pretty much black and white, as all the introduced instructions are there in the .text segment. In other words, it's hard to create different defenses based on MPX and only selectively enable some of them on a target application (unless, of course, this is done at build time).

On the contrary, ADI makes the above much simpler, since only the producer of the memory region is involved in the tagging. This also makes it generally better performant for a system level defense, although certain applications (especially those that make a substantial use of small buffers) might experience slow downs, due to the larger memory footprint and the smaller amount of objects fitting into a single cache line. A tradeoff is possible there, by packing more objects under the same color, losing the ability to detect a small overflow between them.

Summing up (and feel free to look for bias here and call me out on it), ADI is a superior solution for system level defenses for production scenarios, while MPX is a much stronger debugging tool, showing all its Pointer Checker heritage.  Don't get me wrong: both can be used in both scenarios -- I can certainly envision adding MPX protections to binaries (and a security extension to control it) and Oracle Studio Discover does a great job of leveraging ADI to find bugs, but the trade offs in MPX (mandatory recompilation, significant compiler support, higher performance impact, higher precision) tilt the balance towards the debugging scenario, while ADI trade offs (more significant offload to hardware, possibility to design system level defenses that can be applied to legacy binaries, smaller performance impact, smaller precision geared towards more common cases) make it a better tool for production environments.

The Security Extensions Framework

Security defenses usually come with a cost. Such cost can be in terms of performance (added instrumentation, extra memory usage, different memory layout, etc.) and/or compatibility (the defense constrains some border line behavior the application relies on and the application breaks). If either of these costs is not marginal, the system level defense cannot be enabled at large. In particular, we try really hard to never break user systems and we know that many of those run legacy applications.

For these reasons, system level security protections need to be integrated gradually. There is a large number of sensitive security binaries, such as privileged/setuid binaries (e.g. /bin/su) and networking daemons (e.g. sshd) that tend to not be performance sensitive and that definitely would benefit from an hardening of their perimeter. Holding those hostage of some other breakage would just not be smart.

The Security Extensions Framework solves this problem by providing three different models for any userland security feature:

• "all" : the extension is enabled for all processes
• "tagged-files" : the extension is enabled only for binaries that explicitly opt-in
• "disabled" : the extension is disabled system wide

This is used in conjunction with binary tagging. At build time, we support the ability to mark the binary to explicitly state whether a given extension should be enabled or not, through the ld -z<extension>=[enabled|disabled] linker directive. Such settings end up into the ELF .dynamic section, where each security extension has a dedicated entry.

markuse$ elfdump -d /bin/su
Dynamic Section:  .dynamic
[...]
     [35]  SUNW_ASLR       0x2        ENABLE
     [36]  SUNW_NXHEAP     0x2        ENABLE
     [37]  SUNW_NXSTACK    0x2        ENABLE

 This leads to three main scenarios:

• Opt-in (enabled, model=tagged-files): only the binaries that are explicitly tagged as wanting the protection get it. This is by far the most common deployment model. Even for well established protections (e.g. ASLR), there are still certain applications that don't work well with it and prevent us from force enabling the protection system wide. For more recent defenses, the number of tagged binaries is usually smallish (in contrast, with ASLR is well over 90%).
• Opt-out (enabled, model=all): every process on the system gets the defense enabled, except those that are explicitly tagged to disable it. Only the NXSTACK (non-executable stack) security defense is delivered as such. We do run a number of systems with the all the extensions set to 'all', to proactively identify stuff that breaks. This effort also usually brings up a number of existing nasty bugs into various applications (the newer the defense, the more likely to find). We recently let loose internally a new defense, based on SSM/ADI, and found over 70 bugs in different (opensource and internal) applications.
• Disabled: the extension is fully disabled and binary tagging has no effect. This configuration is a last resort large hammer for administrators in case they would hit some pathological issue that we didn't anticipate. It also lets admins concerned by performance side effects to rule the defense completely out. 

Along with system level and binary level controls, the Security Extensions Framework offers process level control. Through sxadm exec -s <extension>=[enable|disable], one can run a process overriding any extension setting. The configuration is inherited by all child processes and, of course, standard security rules apply (a less privileged process cannot affect a more privileged process). This ends up being fairly useful during debugging, in both ways:

• sxadm exec -s aslr=disable /bin/bash creates a debugging environment where launching arbitrary processes gives repeatable results
• sxadm exec -s <somenewext>=enable /bin/bash creates a testing environment while developing/evaluating the effects of a new extension 

sxadm exec can also be wrapped around a third party application to run it with the extensions enabled (e.g. from within an SMF method script).

Administration and Deployment

From an administrative point of view, the Security Extensions Framework is managed through sxadm(1m). The command allows to configure extensions (sxadm enable/disable) and their properties (sxadm get/set), check the current configuration (sxadm status) and execute programs with arbitrary settings (sxadm exec). This offers a common and centralized interface for all the extensions. Learn once, use every time.

Under the cover, the configuration is stored into the svc://system/security/security-extensions SMF service, to which sxadm acts both as the frontend and as the start method. The start method is implemented through the private command sxadm apply, which consumes the secsys() system call. This call acts as the gate between the user and kernel portion of the framework and is used to make the kernel aware of the requested configuration.

Storing the configuration into SMF has a number of key advantages in terms of ease of deployment and integration.

From a deployment point of view, admins can customize the framework configuration through a site-profile and deploy it to an arbitrary number of systems (the SMF profile gets delivered by IPS and is applied on the first boot after installation). Admins do not need to learn a new special configuration lingo.

RAD SMF bindings can be used for remote administration. E.g. the following snippet of code gathers the model for the ASLR security extensions through RAD:

markuse$ cat rad_secext.py 
import rad.client as radcli
import rad.connect as radon
import rad.bindings.com.oracle.solaris.rad.smf_1 as sbind

# Create a connection
con = radcon.connect_unix()

# Retrieve a particular service
service = con.get_object(sbind.Service(), radcli.ADRGlobPattern({"service" : "system/security/security-extensions"}))
model = service.readProperty("aslr/model")

print "ASLR model is %s" % model.values

markuse$ python rad_secext.py
ASLR model is ['all']
markuse$

By connecting remotely (connect_tls()) rather than locally and using, for example, writeProperty() one could change the property setting on a number of different systems remotely.

In Solaris 11.3, the security-extensions service SMF properties haven't been committed yet. The framework is still somehow young and so we felt like retaining the flexibility of a few changes in light of upcoming improvements. Committing the properties is a mandatory step to provide full, mature, reliability beyond the sxadm interface (AI site profiles, RAD administration, etc.). We are working on it for the upcoming releases.

In terms of integration with the rest of the system, SMF is a central part of Solaris so every system wide feature that we offer is well integrated with it. Keeping a security angle on the discussion,  Immutable Zones and RBAC authorizations are fully supported by, and implemented in, SMF. For example, out of the box, just by virtue of having its configuration stored in SMF, the configuration of security extensions is prevented inside an Immutable Global Zone, unless the admin is on the Trusted Path.

On top of that, the Compliance Framework can easily parse SMF properties and hence gather information and report about any extension configuration or status.

TL;DR

Security defenses need an administrative interface in order to be successfully introduced in the operating system and really be taken advantage of. The Security Extensions Framework provides such interface, through process level, binary level (tagging) and system level support to manage security extensions.

Hardening Allocators with ADI

Memory allocators handle a crucial role in any modern application/operating system: satisfy arbitrary-sized dynamic memory requests. Errors by the consumer in handling such buffers can lead to a variety of vulnerabilities, which have been regularly exploited by attackers in the past 15 years. In this blog entry, we'll look at how the ADI (Application Data Integrity) feature of the new Oracle M7 SPARC processors can help in hardening allocators against most of these attacks.

A quick memory allocator primer

Writing memory allocators is a challenging task. An allocator must be performant, limit fragmentation to a bare minimum, scale up to multi-thread applications and handle efficiently both small and large allocations and frequent/unfrequent alloc/free cycles. Looking in depth at allocator designs is beyond the scope of this blog entry, so we'll focus here on only the features that are relevant from an exploitation (and defense) perspective.

Modern operating systems deal with memory in page-sized chunks (ranging from 8K up to 16G on M7). Imagine an application that needs to store a 10 characters string: handing out a 8K page is certainly doable, but is hardly an efficient way to satisfy the request. Memory allocators solve the problem by sitting between the OS physical page allocator and the consumer (being it the kernel itself or an application) and efficiently manage arbitrary sized allocations, dividing pages into smaller chunks when small buffers are needed.

Allocators are composed of three main entities:

• live buffers: a chunk of memory that has been assigned to the application and is guaranteed to hold at least the amount of bytes requested.
• free buffers: chunks of memory that the allocator can use to satisfy an application request. Depending on the allocation design, these are either fixed-size buffers or buffers that can be sliced in smaller portions.
• metadata: all the necessary information that the allocator must maintain in order to efficiently work. Again, depending on the allocator design, this information might be stored within the buffer itself (e.g. Oracle Solaris libc malloc stores most of the data along with the buffer) or separately (e.g. Oracle Solaris umem/kmem SLAB allocator keeps the majority of the metadata into dedicated structures placed outside the objects)

Since allocators divide a page in either fixed-size or arbitrary-size buffers, it's easy to see that, due to the natural flow of alloc/free requests, live buffers and free buffers end up living side by side in the linear memory space.

The period that goes from when a buffer is handed out to an application, up until is freed is generally referred to as the buffer lifetime. During this period, the application has full control of the buffer contents. After this period, the allocator regains control and the application is expected to not interfere.

Of course, bugs happen. Bugs can affect both the application working set of buffers or the allocator free set and metadata. If we exclude allocator intrinsic design errors (which, for long existing allocators, due to the amount of exercise they get, are basically zero), bugs always generate from the application mishandling of a buffer reference, so they always happen during the lifetime of a buffer and originate from a live buffer. It's no surprise that live buffer behavior is what both attackers and defenders start from.

Exploitation vectors and techniques

As we said, bugs originate from the application mishandling of allocated buffers:

• mishandling of buffer size: the classic case of buffer overflow. The application writes past the buffer boundaries into adjacent memory. Because buffers are intermixed with other live buffers, free buffers and, potentially, metadata, each one of those entities becomes a potential target and attackers will go for the most reliable one.
• mishandling of buffer references:  a buffer is relinquished back to the allocator, but the attacker still holds a reference to it. Traditionally, these attacks are known as use after free (UAF), although, since this is an industry that loves taxonomies, it's not uncommon to see them further qualified as use after realloc (the buffer is reallocated, but the attacker is capable of unexpectedly modifying it through the stale reference) and double free (the same reference is passed twice to the free path). Sometimes an attacker is also capable of constructing a fake object and passing it to a free call, for example if the application erroneously calls free of a buffer allocated onto the stack. The degree of exploitability of these vulnerabilities (if we exclude the use after realloc case, which is application-specific) varies depending on what the allocator does during the free path and how many consistency/hardening checks are present.

With the notable exception of double free and "vanilla" use after free, both the above classes are extremely hard to detect at runtime from an allocator perspective, as they originate (and potentially inflict all the necessary damage) during the object lifetime and the allocator has little to none practical control on the buffer. For this reason, the defense focus has been on the next best thing when bug classes cannot be eradicated: hamper/mitigate exploitation techniques. Over the years (and at various degrees in different allocators) this has taken the form of:

• entrypoint checks: add consistency check at the defined free and alloc entrypoints. As an example, an allocator could mark into the buffer associated metadata (or poison the buffer itself) that the buffer has been freed. It would then be able to check this information whenever the free path is entered and a double free could be easily detected. Many of the early days techniques to exploit heap overflows (~2000, w00w00 , PHRACK57 MaXX's and anonymous' articles) relied on modifying metadata that would then be leveraged during the free path. Over time, some allocators have added checks to detect some of those techniques.
• design mitigations: attackers crave for control of the heap layout: in what sequence are buffer allocated, where are they placed, how can a buffer containing sensitive data be conveniently allocated in a specific location. Allocators can introduce statistical mitigations to hamper some of the techniques to achieve this level of control. As an example, free object selection can be randomized (although it ends up being pretty ineffective against a variety of heap spraying techniques and/or if the attacker has quite some control on the allocation pattern), free patterns can be modified (Microsoft IE Memory Protector) or sensitive objects can be allocated from a different heap space (dedicated SLAB caches, Windows IE Isolated Heap, Chrome PartitionAlloc, etc). The bottom line goal of these (and other) design approaches is to either reduce the amount of predictability of the allocator or increase the amount of precise control that the attacker needs to have in order to create the successful heap layout conditions to exploit the bug.

Of course, more invasive defenses also exist, but they hardly qualify for large scale application, as users tend to (rightfully) be pretty concerned about the performance of their applications/operating systems. This becomes even more evident when we compare the amount of defenses that are today enabled and deployed at kernel level versus the amount of defenses enabled at user level (and in browsers): different components have different (and varying) performance requirements.

The practical result is that slab overflows are today probably the most reliable type of vulnerability at kernel level and use after free are a close second in kernel land, while extensively targeted in user land, with only the browsers being significantly more hardened than other components. Extensive work is going on towards automating and abstracting the development of exploits for such bugs (as recently presented by argp at Zeronights), which makes the design of efficient defenses even more compelling.

ADI to the rescue

Enter the Oracle SPARC M7 processor and ADI, Application Data Integrity, that were both unveiled at HotChips and Oracle OpenWorld 2014. At its core, ADI provides memory tagging. Whenever ADI is enabled on a page entry, dedicated non-privileged load/store instructions provide the ability to assign a 4-bit version to each 64-byte cacheline that is part of the page. This version is maintained by the hardware throughout the entire non-persistent memory hierarchy (basically, all the way down to DRAM and back).

The same version can then be mirrored onto the (previously) unused 4 topmost bits of each virtual address. Once this is done, each time a pointer is used to access a memory range, if ADI is enabled (both at the page and per-thread level), the tag stored in the pointer is checked by the hardware against the tag stored in the cache line. If the two match, all is peachy. If they don't, an exception is raised.

Since the check is done in hardware, the main burden is at buffer creation, rather than at each access, which means that ADI can be introduced in a memory allocator and its benefit extended to any application consuming it without the need of extra instrumentation or special instructions into the application itself. This is a significant difference from other hardware-based memory corruption detection options, like Intel MPX, and minimizes the performance impact of ADI while maximizing coverage. More importantly, this means we finally have a reliable way to detect live object mishandling: the hardware does it for us.

[ADI versioning at work. Picture taken from Oracle SPARC M7 presentation]

4 bits allow for a handful of possible values. There are two intuitive ways in which an ADI-aware allocator can invariantly detect a linear overflow from a buffer/object to the adjacent one:

• introduce a redzone with a special tag
• tag differently any two adjacent buffers

Introducing a redzone means wasting 64-byte per allocation, since 64-byte is the minimum granularity with ADI. Wasted memory scales up linearly with the number of allocations and might end up being a substantial amount. Also, the redzone entry must be 64-byte aligned as well, which practically translates in both buffers and the redzone to be 64-byte aligned. The advantage of this approach is that is fairly simple to implement: simply round up every allocation to 64-byte and add an extra complimentary 64-byte buffer. For this reason, it can be a good candidate for debugging scenarios or for applications that are not particularly performance sensitive and need a simple allocation strategy. For allocators that store metadata within the buffer itself, this redzone space could be used to store the metadata information. Mileage again varies depending on how big the metadata is and it's worth to point out that general purpose allocators usually strive to keep it small (e.g. Oracle Solaris libc uses 16 bytes for each allocated buffer) to reduce memory wastage.

Tagging differently two adjacent objects, instead, has the advantage of reducing memory wastage. In fact, the only induced wastage is the one from forcing the alignment to a 64-byte boundary. It also requires, though, to be able to uniquely pick a correct tag value at allocation time. Object-based allocators are a particularly good fit for this design because they already take some of the penalty for wasted memory (and larger caches are usually already 64-bit aligned) and their design (fixed size caches divided in a constant number of fixed size objects) allows to uniquely identify objects based on their address. This provides the ability to alternate between two different values (or range of values, e.g. odd/even tags, smaller/bigger than a median) based on the ibject position. For other allocators, the ability to properly tag the buffer depends on whether there is enough metadata to learn about the previous and next object tag. If there is, then this can still be implemented, if there isn't, one might decide to employ a statistical defense by randomizing the tag (note that the same point applies also to object-based allocators when we look at large caches, where effectively only a single object is present per cache).

A third interesting property of tagging is that it can be used to uniquely identify classes of objects, for example free objects. As we discussed previously, metadata and free objects are never the affector, but only the affectee of an attack, so one tag each suffices. The good side effect of devoting a tag each is that the allocator now has a fairly performant way to identify them and issues like double-frees can be easily detected. In the same way, it's also automatically guaranteed that a live object will never be able to overflow into metdata or free objects, even if a statistical defense (e.g. tag randomization) is employed.

Use-after-realloc and arbitrary writes

ADI does one thing and does it great: provides support to implement an invariant to detect linear overflows. Surely, this doesn't come without some constraints (64-byte granularity, 64-byte alignment, page-level granularity to enable it, 4-bit versioning range) and might be a more or less good fit (performance and design-wise) for an existing allocator, but this doesn't detract from its security potential. Heartbleed is just one example of a linear out-of-bound access and SLAB/heap overflow fixes have been in the commit logs of all major operating systems for years now. Invariantly detecting them is a significant win.

Use-after-realloc and arbitrary writes, instead, can't be invariantly stopped by ADI, although ADI can help in mitigating them. As we discussed, use-after-realloc rely on the ability, by the attacker, to hold a reference to a free-and-then-realloced object and then use this reference to modify some potentially sensitive content. ADI can introduce some statistical noise in this exploitation path, by looping/randomizing through different values for the same buffer/object. Note that this doesn't affect the invariant portion of, for example, alternate tagging in object-based allocators; it simply takes further advantage of the versioning space. Of course, if the attacker is in the position of performing a bruteforce attack, this mitigation would not hold much ground, but in certain scenarios, bruteforcing might be a limiting factor (kernel level exploitation) or leave some detectable noise.

Arbitrary writes, instead, depend on the ability of the attacker to forge an address and are not strictly related to allocator ranges only. Since the focus here is the allocator, the most interesting variant is when the attacker has the ability to write to an arbitrary offset from the current buffer. If metadata and free objects are specially tagged, they are unreachable, but other live objects with the same tag might be reached. Just as in the use-afte-realloc case, adding some randomization to the sequence of tags can help, with the very same limitations. In both cases, infoleaks would precisely guide the attacker, but this is basically a given for pretty much any statistical defense.

TL;DR

Oracle SPARC M7 processors come with ADI, Application Data Integrity, a feature that provides memory tagging. Memory allocators can take advantage of it both for debugging and security, in order to invariantly detect linear buffer overflows and statistically mitigate against use-after-free and offset-based arbitrary writes.