Reverse Engineering UndefinedBehaviorSanitizer (UBSan)

Introduction

While working on the Oracle Ksplice team, we have to adapt our code base to handle new features either in the Linux Kernel or user space programs so that we can continue to provide live patching to our customers. One of those features was UBSan (UndefinedBehaviorSanitizer) and the idea of this blog post is to share the investigation work that has been done as part of adding support for it in Ksplice for the Linux kernel.

As a precursor to reading this blog, I would recommend you first read the blog Improving Application Security with UndefinedBehaviourSanitzer(UBSan) and GCC, as it provides a good global overview and is a great introduction on how to use UBSan.

UBSan in user space

Build a test program to showcase UBSan

Let’s start by writing a small program and see how GCC detects that an array is accessed out-of-bounds at runtime. This program intentionally contains an error:

#define ARRAY_SIZE 4

int main(int argc, char *argv[])
{
    int array[ARRAY_SIZE];
    int i = 0;

    /* Access the array out of bounds. */
    for (i = 0; i <= ARRAY_SIZE; i++)
        array[i] = 0x42;

    return 0;
}

We can now compile it with the below option from GCC documentation:

-fsanitize=bounds
  
    This option enables instrumentation of array bounds. Various out of bounds accesses are detected. Flexible array members, flexible array member-like arrays, and initializers of variables with static storage are not instrumented, with the exception of flexible array member-like arrays for which -fstrict-flex-arrays or -fstrict-flex-arrays= options or strict_flex_array attributes say they shouldn’t be treated like flexible array member-like arrays.

$ gcc -o ubsan ubsan.c -fsanitize=bounds

Note that libusan must be installed otherwise it will fail with:

/usr/bin/ld: cannot find /usr/lib64/libubsan.so.1.0.0

And now we can start the program and see the output:

$ ./ubsan
ubsan.c:9:8: runtime error: index 4 out of bounds for type 'char [4]'

UBSan successfully detected the out-of-bounds access we intentionally introduced.

Analyze UBSan instrumented program

Now that we verified that UBSan is working fine in our test program, we can disassemble the program to understand what is happening under the hood:

$ objdump --disassemble=main  -r ubsan
...
0000000000401126 <main>:
  401126:       55                      push   %rbp
  401127:       48 89 e5                mov    %rsp,%rbp
  40112a:       53                      push   %rbx
  40112b:       48 83 ec 38             sub    $0x38,%rsp
  40112f:       89 7d cc                mov    %edi,-0x34(%rbp)
  401132:       48 89 75 c0             mov    %rsi,-0x40(%rbp)
  401136:       c7 45 ec 00 00 00 00    movl   $0x0,-0x14(%rbp)
  40113d:       c7 45 ec 00 00 00 00    movl   $0x0,-0x14(%rbp)
  401144:       eb 2b                   jmp    401171 <main+0x4b>
  401146:       8b 5d ec                mov    -0x14(%rbp),%ebx
  401149:       48 63 c3                movslq %ebx,%rax
  40114c:       48 83 f8 03             cmp    $0x3,%rax
  401150:       76 10                   jbe    401162 <main+0x3c>
  401152:       48 63 c3                movslq %ebx,%rax
  401155:       48 89 c6                mov    %rax,%rsi
  401158:       bf 60 40 40 00          mov    $0x404060,%edi
  40115d:       e8 ce fe ff ff          callq  401030 <__ubsan_handle_out_of_bounds@plt>
  401162:       48 63 c3                movslq %ebx,%rax
  401165:       c7 44 85 d0 42 00 00    movl   $0x42,-0x30(%rbp,%rax,4)
  40116c:       00
  40116d:       83 45 ec 01             addl   $0x1,-0x14(%rbp)
  401171:       83 7d ec 04             cmpl   $0x4,-0x14(%rbp)
  401175:       7e cf                   jle    401146 <main+0x20>
  401177:       b8 00 00 00 00          mov    $0x0,%eax
  40117c:       48 8b 5d f8             mov    -0x8(%rbp),%rbx
  401180:       c9                      leaveq
  401181:       c3                      retq   
...

GCC added some instrumentation in the .text section to check i which is used to iterate the array against the size of the array. The relevant instructions are from offset 0x401146 to 0x40115d:

  401146:       8b 5d ec                mov    -0x14(%rbp),%ebx
  401149:       48 63 c3                movslq %ebx,%rax
  40114c:       48 83 f8 03             cmp    $0x3,%rax
  401150:       76 10                   jbe    401162 <main+0x3c>
  401152:       48 63 c3                movslq %ebx,%rax
  401155:       48 89 c6                mov    %rax,%rsi
  401158:       bf 60 40 40 00          mov    $0x404060,%edi
  40115d:       e8 ce fe ff ff          callq  401030 <__ubsan_handle_out_of_bounds@plt>

It’s basically comparing %rax (the index) with 0x3 (which is the array size) and if it’s larger, it will call __ubsan_handle_out_of_bounds with a pointer to some data in %rdi (1st argument) and the index in %rsi (2nd argument).
__ubsan_handle_out_of_bounds is where all the magic happens and from where the runtime error we have seen earlier is generated.
Now we can check what is actually stored in %rdi and from where this function __ubsan_handle_out_of_bounds comes from.

%rdi contains the address 0x404060 which resides in .data section. Let’s dump the data present there:

$ objdump -s -z --section=.data --start-address=0x404060 ubsan
  
ubsan:     file format elf64-x86-64
  
Contents of section .data:
 404060 10204000 00000000 0a000000 08000000  . @.............
 404070 4a404000 00000000 40404000 00000000  J@@.....@@@.....

This is pretty hard to understand without knowing the actual signature of the function we are calling __ubsan_handle_out_of_bounds.

So let’s look at __ubsan_handle_out_of_bounds, but where? As objdump shows, this symbol is found at run time using the plt so maybe running ldd on the binary will give us an hint on where the function could reside.

$ ldd ubsan
        linux-vdso.so.1 (0x00007ffc3bfa6000)
        libubsan.so.1 => /lib64/libubsan.so.1 (0x00007f322b72a000)
        libc.so.6 => /lib64/libc.so.6 (0x00007f322b521000)
        libstdc++.so.6 => /lib64/libstdc++.so.6 (0x00007f322b2fa000)
        libm.so.6 => /lib64/libm.so.6 (0x00007f322b21f000)
        libgcc_s.so.1 => /lib64/libgcc_s.so.1 (0x00007f322b203000)
        /lib64/ld-linux-x86-64.so.2 (0x00007f322c0a5000)

libubsan.so.1 is obviously a good candidate, let’s check if the symbol is there:

$ readelf -W -s /lib64/libubsan.so.1 | grep ubsan_handle_out_of_bounds
   119: 000000000000e480    46 FUNC    GLOBAL DEFAULT   13 __ubsan_handle_out_of_bounds_abort
   199: 000000000000e450    43 FUNC    GLOBAL DEFAULT   13 __ubsan_handle_out_of_bounds

This is indeed where the symbol resides. Where can we find the source code for libusan though? After grepping in gcc source code git://gcc.gnu.org/git/gcc.git, we can find it’s defined in libsanitizer/ubsan/ubsan_handlers.cpp:

void __ubsan::__ubsan_handle_out_of_bounds(OutOfBoundsData *Data,
                                           ValueHandle Index) {
  GET_REPORT_OPTIONS(false);
  handleOutOfBoundsImpl(Data, Index, Opts);
}

Here we are only interested in the first argument (what is stored in %rdi) because the second one is obvious, so let’s look at the OutOfBoundsData definition and all other dependent definitions:

struct OutOfBoundsData {
  SourceLocation Loc;
  const TypeDescriptor &ArrayType;
  const TypeDescriptor &IndexType;
};

class SourceLocation {
  const char *Filename;
  u32 Line;
  u32 Column;
  ...
}

class TypeDescriptor {
  /// A value from the \c Kind enumeration, specifying what flavor of type we
  /// have.
  u16 TypeKind;

  /// A \c Type-specific value providing information which allows us to
  /// interpret the meaning of a ValueHandle of this type.
  u16 TypeInfo;

  /// The name of the type follows, in a format suitable for including in
  /// diagnostics.
  char TypeName[1];
  ...
}

Note that class TypeDescriptor and class SourceLocation have been stripped down for readability and to show only the data part of the class definition.

Back to the data we dumped, the first 8 bytes should be an address pointing to Filename based off the above. The first 8 bytes are 10204000 00000000 which is, once converted to Little Endian as we are working on X86, 0x402010. This address is part of .rodata section and contains the name of the file:

$ objdump -s -z  --section=.rodata --start-address=0x402010 ubsan

ubsan:     file format elf64-x86-64

Contents of section .rodata:
 402010 75627361 6e2e6300                    ubsan.c.

We can continue with the same logic and find Line and Column attributes of class SourceLocation. And also both ArrayType and IndexType elements of struct OutOfBoundsData

Now that we understand how GCC is instrumenting the program, we can have a look to the function called by __ubsan_handle_out_of_bounds which is called by our program:

static void handleOutOfBoundsImpl(OutOfBoundsData *Data, ValueHandle Index,
                                  ReportOptions Opts) {
  SourceLocation Loc = Data->Loc.acquire();
  ErrorType ET = ErrorType::OutOfBoundsIndex;

  if (ignoreReport(Loc, Opts, ET))
    return;

  ScopedReport R(Opts, Loc, ET);

  Value IndexVal(Data->IndexType, Index);
  Diag(Loc, DL_Error, ET, "index %0 out of bounds for type %1")
    << IndexVal << Data->ArrayType;
}

It’s now pretty straightforward and we can see it’s here that the runtime error is generated.

Note that different types of arguments are passed to different UBSan handlers depending on the type of undefined behavior but the logic is always the same. Having seen the instrumentation in details could give a rough idea of the overhead for having UBSan enabled in a program.

UBSAN in the Linux kernel

Now that we have seen show UBSan works in a program, let’s look at UBSan in the Linux kernel. Since it’s pretty similar, this section will be a lot shorter than the previous one.

To be able to understand how UBSan works in the kernel, we can compile the Linux kernel from source and enable CONFIG_UBSAN. By default it also enables CONFIG_UBSAN_BOUNDS which is the one we are interested in to compare with the previous user space program example. Thanks to this option -fsanitize=bounds will be passed to GCC when compiling.

Let’s create a kernel module which looks like the program we previously wrote:

#include <linux/module.h>

extern int foo(void);

#define UBSAN_ARRAY_SIZE 4
int array[UBSAN_ARRAY_SIZE];
int ubsan_probe(void)
{
        int i = 0;

        /* Access the array out of bounds. */
        for (i = 0; i < UBSAN_ARRAY_SIZE; i++)
                array[i] = foo();

        return 0;
}
module_init(ubsan_probe);
MODULE_LICENSE("");

It’s almost the same, only an external function has been added so that GCC can’t optimize our function and is forced to actually use our index i. Compiling the module will fail because foo() is defined nowhere but we are only interested in building this file without even linking the module. Here is the disassembly we get:

$ objdump --disassemble=init_module  -r ubsan.o

ubsan.o:     file format elf64-x86-64


Disassembly of section .text:

0000000000000010 <init_module>:
  10:   f3 0f 1e fa             endbr64
  14:   53                      push   %rbx
  15:   31 db                   xor    %ebx,%ebx
  17:   48 63 f3                movslq %ebx,%rsi
  1a:   48 83 fe 03             cmp    $0x3,%rsi
  1e:   77 1e                   ja     3e <init_module+0x2e>
  20:   e8 00 00 00 00          callq  25 <init_module+0x15>
                        21: R_X86_64_PLT32      foo-0x4
  25:   89 04 9d 00 00 00 00    mov    %eax,0x0(,%rbx,4)
                        28: R_X86_64_32S        array
  2c:   48 83 c3 01             add    $0x1,%rbx
  30:   48 83 fb 04             cmp    $0x4,%rbx
  34:   75 e1                   jne    17 <init_module+0x7>
  36:   31 c0                   xor    %eax,%eax
  38:   5b                      pop    %rbx
  39:   e9 00 00 00 00          jmpq   3e <init_module+0x2e>
                        3a: R_X86_64_PLT32      __x86_return_thunk-0x4
  3e:   48 c7 c7 00 00 00 00    mov    $0x0,%rdi
                        41: R_X86_64_32S        .data
  45:   e8 00 00 00 00          callq  4a <init_module+0x3a>
                        46: R_X86_64_PLT32      __ubsan_handle_out_of_bounds-0x4
  4a:   eb d4                   jmp    20 <init_module+0x10>

From the instruction at offset 0x1a, the same logic as in the user space program is present. First the index is compared to 0x3 and if it’s bigger __ubsan_handle_out_of_bounds is called after passing some data as the first argument and the index as the second argument. Now the question is from where __ubsan_handle_out_of_bounds comes from since libubsan.so can’t be used in the Linux kernel?

All UBSan handlers have been introduced from commit c6d308534aef ("UBSAN: run-time undefined behavior sanity checker") in the Linux kernel. So the logic is exactly the same as with userspace, it’s just that different handlers have been defined and built into the Linux kernel.

Conclusion

The Ksplice team often has to deal with kernel internals to either help livepatching or simply handle features from the kernel interfering with the livepatching process. If this kind of work sounds interesting to you, consider applying for a job with the Ksplice team! Feel free to drop us a line at ksplice-support_ww@oracle.com.