Inside the Size Overflow Plugin

Security notes and analysis from the PaX Team and grsecurity

Moderators: spender, PaX Team, ephox

Inside the Size Overflow Plugin

Postby ephox » Tue Aug 28, 2012 5:30 pm

Hello everyone, my name is Emese (ephox). You may already know me for my previous project, the constify gcc plugin that pipacs took over and put into PaX.

This time I would like to introduce to you a 1-year-old project of mine that entered PaX a few months ago. It's another gcc plugin called size_overflow whose purpose is to detect a subset of the integer overflow security bugs at runtime.

On integer overflows briefly

In the C language integer types can represent a finite range of numbers. If the result of an arithmetic operation falls outside of the type's range (e.g., the largest representable value plus one) then the value overflows or underflows. This becomes a problem if the programmer didn't think of it, e.g., the size parameter of memory allocator function becomes smaller due to the overflow.

There is a very good description on integer overflow in Phrack: ... 10#article

The history of the plugin

The plugin is based on spender's idea, the intoverflow_t type found in older PaX versions. This was a 64 bit wide integer type on 32 bit archs and a 128 bit wide integer type on 64 bit archs.
There were wrapper macros for the important memory allocator functions (e.g., kmalloc) where the value to be put into the size argument (of size_t type) could be checked against overflow.
For example:
Code: Select all
#define kmalloc(size,flags)                                          \
({                                                                   \
        void *buffer = NULL;                                         \
        intoverflow_t overflow_size = (intoverflow_t)size;           \
        if (!WARN(overflow_size > ULONG_MAX, "kmalloc size overflow\n")) \
                buffer = kmalloc((size_t)overflow_size, (flags));    \
        buffer;                                                      \

This solution had a problem in that the size argument is usually the result of a longer computation that consists of several expressions. The intoverflow_t cast based check could only verify the last expression that was used as the argument to the allocator function and even then it only helped if the type cast of the leftmost operand affected the other operands as well. Therefore if there was an integer overflow during the evaluation of the other expressions then the remaining computation would use the overflowed value that the intoverflow_t cast cannot detect.
Second, only a few basic allocator functions had wrapper macros because wrapping every function with a size argument would have been a big job and resulted in an unmaintainable patch.

In contrast, the size_overflow plugin recomputes all subexpressions of the expression with a double wide integer type in order to detect overflows during the evaluation of the expression.

Internals of the size_overflow plugin

The compilation process is divided into passes in between or in place of which a plugin can insert its own. Each pass has a specific task (e.g., optimization, transformation, analysis) and they run in a specific order on a translation unit (some optimization passes may be skipped depending on the optimization level).
The plugin's pass (size_overflow_pass) executes after the "ssa" GIMPLE pass which is among the early GIMPLE passes. It's placed there to allow all the later optimization passes to properly optimize the code modified by the plugin.

Before I describe the plugin in more detail, let's look at some gcc terms

The gimple structure in gcc represents the statements (stmt) of the high level language.
For example this is what a function call (gimple_code: GIMPLE_CALL) looks like:
Code: Select all
gimple_call <malloc, D.4425_2, D.4421_15>

or a subtract (gimple_code: GIMPLE_ASSIGN) stmt:
Code: Select all
gimple_assign <minus_expr, D.4421_15, D.4464_12, a_5>

This stmt has 3 operands, one lhs (left hand side) and two rhs (right hand side) ones.
Each variable is of type "tree" and has a name (SSA_NAME) and version number (SSA_NAME_VERSION) while we are in SSA (static single assignment) mode.

As we can see the parameter of malloc is the variable D.4421_15 (SSA_NAME: 4421, SSA_NAME_VERSION: 15) which is also the lhs of the assignment, so we use-def relation between the two stmts, that is the defining statement (def_stmt) of the variable D.4421_15 is the D.4421_15 = D.4464_12 - a_5 stmt.
Further reading on SSA and GIMPLE:

The plugin gets called for each function and goes through their stmts looking for calls to marked functions.
In the kernel, functions can be marked two ways:
  • with a function attribute for fuctions at the bottom of the function call hierarchy (e.g., copy_user_generic, __copy_from_user, __copy_to_user, __kmalloc, __vmalloc_node_range, vread)
  • listed in a hash table (for functions calling the above basic functions)
In userland there is only a hash table (e.g., openssl). The present description covers the kernel.

The attributes

Plugins can define new attributes. This plugin defines two new attributes:
  • The __size_overflow attribute is used to mark the size parameters of interesting functions so that they can be tracked backwards.
    This is what the attribute looks like: __attribute__((size_overflow(1))) where the parameter (1) refers to the function argument (they are numbered from 1) that we want to check for overflow. In the kernel there is a #define for this attribute similarly to other attributes: __size_overflow(...).
    For example:
    Code: Select all
    unsigned long __must_check clear_user(void __user *mem, unsigned long len) __size_overflow(2);
    static inline void* __size_overflow(1,2) kcalloc(size_t n, size_t size, gfp_t flags) { ... }
  • The __intentional_overflow attribute is used to turn off overflow checking.
    • __intentional_overflow(-1) means that overflow checking is turned off inside the function and parameters aren't tracked backwards.
    • __intentional_overflow(4) means that overflow checking is turned off on the fourth parameter inside the function.
    • __intentional_overflow(0) means that overflow checking is turned off on all the parameters of the function in all callers.
    • __intentional_overflow(0) on a structure field means that overflow checking is turned off in all expressions involving the given field.
Further documentation about attributes:

The hash table

Originally we only had the attribute similarly to the constify plugin but in order to reduce the kernel patch size (e.g., in 3.8.5 5943 functions are marked) all functions except for the base ones are stored in a hash table.
The hash table is generated by the tools/gcc/ script from tools/gcc/ into tools/gcc/size_overflow_hash.h.
A hash table entry is described by the size_overflow_hash structure whose fields are the following:
  • next: the hash chain pointer to the next entry
  • name: name of the function
  • param: an integer with bits set corresponding to the size parameters, PARAM0 means the function return value.
For example this is what the hash entry of the include/linux/slub_def.h:kmalloc function looks like:
Code: Select all
const struct size_overflow_hash _000008_hash = {
    .next   = NULL,
    .name   = "kmalloc",
    .param  = PARAM1,

The hash table is indexed by a hash computed from numbers describing the function declarations (get_tree_code()).
Code: Select all
const struct size_overflow_hash * const size_overflow_hash[65536] = {
   [11268] = &_000008_hash,

The hash algorithm is CrapWow:

Enabling the size_overflow plugin in the kernel
  • in menuconfig (under PaX): Security options -> PaX -> Miscellaneous hardening features -> Prevent various integer overflows in function size parameters
  • .config (under PaX): CONFIG_PAX_SIZE_OVERFLOW
  • .config (without PaX): CONFIG_SIZE_OVERFLOW

stmt duplication with double wide integer types

When the plugin finds a marked function then it traces back the use-def chain of the parameter(s) defined by the function attribute. The stmts found recursively are duplicated using variables of double wide integer types.

In some cases duplication is not the right strategy. In these cases the plugin takes the lhs of the original stmt and casts it to the double wide type:
  • function calls (GIMPLE_CALL): they cannot be duplicated because they may have side effects. However the computation of the function return value will be duplicated if PARAM0 is set in the hash table for the given function.
  • inline asm (GIMPLE_ASM): it may have side effects too.
  • taking the address of an object (ADDR_EXPR): todo
  • pointers (MEM_REF, etc.): todo
  • division (RDIV_EXPR, etc.): special case for the kernel because it doesn't support division with double wide types
  • global variables: todo

If the marked function's parameter can be traced back to a parameter of the caller then the plugin checks if the caller is already in the hash table (or it is marked with the attribute). If it isn't then the plugin prints the following message:
Code: Select all
Function %s is missing from the size_overflow hash table +%s+%u+%u+" (caller's name, parameter's number, hash)

If anyone sees this message, please send it to me by e-mail ( so that I can put the caller into the hash table, otherwise the plugin will not apply the overflow check to it.

Inserting the overflow checks

The plugin inserts overflow checks in the following cases:
  • marked function parameters just before the function call
  • stmt with a constant operand, see gcc intentional overflow
  • negations (BIT_NOT_EXPR)
  • type cast stmts between these types:

Code: Select all
 |  rhs   |  lhs |  lhs  |  rhs   |
 | u32    | u32  |   -   |    !   |
 | u32    | s32  |   -   |    -   |
 | s32    | u32  |   -   |    !   |
 | s32    | s32  |   -   |    !   |
 | u32    | u64  |   -   |    !   |
 | u32    | s64  |   !   |    -   |
 | s32    | u64  |   !   |    !   |
 | s32    | s64  |   -   |    !   |
 | u64    | u32  |   !   |    !   |
 | u64    | s32  |   !   |    -   |
 | s64    | u32  |   !   |    !   |
 | s64    | s32  |   !   |    !   |
 | u64    | u64  |   -   |    !   |
 | u64    | s64  |   -   |    -   |
 | s64    | u64  |   -   |    !   |
 | s64    | s64  |   -   |    !   |

  • from: source type
  • to: destination type
  • lhs: is the lhs checked?
  • rhs: is the rhs checked?
  • !: the plugin inserts an overflow check
  • -: there is no overflow check

When the plugin finds one of the above cases then it will insert a range check against the double wide variable value (TYPE_MIN, TYPE_MAX of the original variable type). This guarantees that at runtime the value fits into the original variable's type range.

If the runtime check detects an overflow then the report_size_overflow function will be called instead of executing the following stmt.
The marked function's parameter is replaced with a variable cast down from its double wide clone so that gcc can potentially optimize out the stmts computing the original variable.

If we uncomment the print_the_code_insertions function call in the insert_check_size_overflow function then the plugin will print out this message during compilation:
"Integer size_overflow check applied here."
This message isn't too useful because later passes in gcc will optimize out about 6 out of 10 insertions. If anyone is interested in the insertion count after optimizations then try this command (on the kernel):
Code: Select all
objdump -drw vmlinux | grep "call.*report_size_overflow" | wc -l


The plugin creates the report_size_overflow declaration in the start_unit_callback, but the definition is always in the current program. The plugin inserts only the report_size_overflow calls. This is a no-return function.

This function prints out the file name, the function name and the line number of the detected overflow. If the stmt's line number is not available in gcc then it prints out the caller's start line number. The last three strings are only debug information.
The report_size_overflow function's message looks like this (without PaX it uses SIZE_OVERFLOW instead of PAX):
Code: Select all
PAX: size overflow detected in function main tests/main12.c:28 cicus.6_18 max, count: 1

In the kernel the report_size_overflow function is in fs/exec.c. The overflow message is sent to dmesg along with a stack backtrace and then it sends a SIGKILL to the process that tiggered the overflow.
In openssl the report_size_overflow function is in crypto/mem.c. The overflow message is sent to syslog and the triggering process is sent a SIGSEGV.

Plugin internals through a simple example

The source code (test.c):

Code: Select all
extern void *malloc(size_t size) __attribute__((size_overflow(1)));

void * __attribute__((size_overflow(1))) coolmalloc(size_t size)
        return malloc(size);

void report_size_overflow(const char *file, unsigned int line, const char *func, const char *ssa_name)
        printf("SIZE_OVERFLOW: size overflow detected in function %s %s:%u %s", func, file, line, ssa_name);

int main(int argc, char *argv[])
        unsigned long a;
        unsigned long b;
        unsigned long c = 10;

        a = strtoul(argv[1], NULL, 0);
        b = strtoul(argv[2], NULL, 0);
        c = c + a * b;
        return printf("%p\n", coolmalloc(c));

Compile the plugin:
Code: Select all
gcc -I`gcc -print-file-name=plugin`/include/c-family -I`gcc -print-file-name=plugin`/include -fPIC -shared -O2 -o size_overflow_plugin.c

Compile test.c with the plugin and dump its ssa representations:
Code: Select all
gcc test.c -O2 -fdump-tree-all

Each dumpable gcc pass is dumped by -fdump-tree-all. This blog post focuses on the ssa and the size_overflow passes.
The marked function is coolmalloc, the traced parameter is c_12. The main function's ssa representaton is below, just before executing the size_overflow pass (test.c.*.ssa*):
Code: Select all
main (int argc, char * * argv)
  long unsigned int c;
  long unsigned int b;
  long unsigned int a;
  void * D.3791;
  int D.3790;
  long unsigned int D.3789;
  char * D.3788;
  char * * D.3787;
  char * D.3786;
  char * * D.3785;

<bb 2>:
  c_1 = 10;
  a_5 = strtoul (D.3786_4, 0B, 0);
  b_8 = strtoul (D.3788_7, 0B, 0);
  D.3789_9 = a_5 * b_8;
  c_10 = D.3789_9 + c_1;
  D.3791_11 = coolmalloc (c_10);
  D.3790_12 = printf ("%p\n", D.3791_11);
  return D.3790_12;

After the size_overflow pass on a 64 bit arch (test.c.*size_overflow*):
Code: Select all
main (int argc, char * * argv)
  long unsigned int cicus.9;
  __int128 cicus.8;
  __int128 cicus.7;
  __int128 cicus.6;
  __int128 cicus.5;
  __int128 cicus.4;
  long unsigned int c;
  long unsigned int b;
  long unsigned int a;
  void * D.3791;
  int D.3790;
  long unsigned int D.3789;
  char * D.3788;
  char * * D.3787;                                                                                                                                                                                                                 
  char * D.3786;

<bb 2>:                                                                                                                                                                                                                           
  c_1 = 10;
  cicus.7_21 = (__int128) c_1;
  a_5 = strtoul (D.3786_4, 0B, 0);
  cicus.4_18 = (__int128) a_5;
  b_8 = strtoul (D.3788_7, 0B, 0);
  cicus.5_19 = (__int128) b_8;
  D.3789_9 = a_5 * b_8;
  cicus.6_20 = cicus.4_18 * cicus.5_19;
  c_10 = D.3789_9 + c_1;                                                                                                                                                                                                           
  cicus.8_22 = cicus.6_20 + cicus.7_21;

  cicus.9_23 = (long unsigned int) cicus.8_22;
  if (cicus.8_22 > 18446744073709551615)
    goto <bb 3>;
    goto <bb 4>;
<bb 3>:
  report_size_overflow ("tests/main27.c", 29, "main", "cicus.8_22 max, count: 1\n");
<bb 4>:                                                                                                                                                                                                                           
  if (cicus.8_22 < 0)
    goto <bb 5>;
    goto <bb 6>;
<bb 5>:                                                                                                                                                                                                                           
  report_size_overflow ("tests/main27.c", 29, "main", "cicus.8_22 min, count:2\n");
<bb 6>:                                                                                                                                                                                                                           
  D.3791_11 = coolmalloc (cicus.9_23);
  D.3790_12 = printf ("%p\n", D.3791_11);
  return D.3790_12;

Some problems encountered during development

  • gcc intentional overflow:
    Gcc can produce unsigned overflows while transforming expressions. e.g., it can transform constants that will produce the correct result with unsigned overflow on the given type. (e.g., a-1 -> a+4294967295) The plugin used to detect this (false positive) overflow at runtime ;).
    The solution is to not duplicate such stmts that contain constants. Instead, the plugin inserts an overflow check for the non-constant rhs before that stmt and uses its lhs (cast to the double wide type) in later duplication.
    For example on 32 bit:

    Code: Select all
    coolmalloc(a * b - 1 + argc)

    before size_overflow plugin:
    Code: Select all
      D.4416_10 = a_5 * b_9;
      D.4418_13 = D.4416_10 + argc.0_12;
      D.4419_14 = D.4418_13 + 4294967295;
      D.4420_15 = coolmalloc (D.4419_14);

    after size_overflow plugin:
    Code: Select all
       D.4416_10 = a_5 * b_9;
       cicus.7_25 = cicus.4_22 * cicus.6_24;
       D.4418_13 = D.4416_10 + argc.0_12;
       cicus.9_27 = cicus.7_25 + cicus.8_26;
       cicus.10_28 = (unsigned int) cicus.9_27;
       cicus.11_29 = (long long unsigned int) cicus.9_27;
       if (cicus.11_29 > 4294967295)
       goto <bb 3>;
       goto <bb 4>;

    <bb 3>:
       report_size_overflow ("test.c", 28, "main");

    <bb 4>:
       D.4419_14 = cicus.10_28 + 4294967295;
       cicus.12_30 = (long long int) D.4419_14;

  • when a size parameter is used for more than one purpose (not just for size):
    The plugin cannot recognize this case. When I get a false positive report I remove the function from the hash table.
  • type cast from gcc or the programmer causing intentional overflows. This is the reason for the TODOs in the table above

Detecting a real security issue

I'll demonstrate the plugin on an openssl 1.0.0 bug (CVE-2012-2110).

To reproduce the overflow with this:
Download the plugin source (or use the ebuild) from here:
Download the openssl patch (that contains the report_size_overflow function):

Compile openssl with the plugin (see the README) after that we can reproduce the bug:
Code: Select all
openssl-1.0.0.h/bin $ ./openssl version
OpenSSL 1.0.0h 12 Mar 2012
openssl-1.0.0.h/bin $ ./openssl x509 -in ../../openssl-1.0.1-testcase-32bit.crt -text -noout -inform DER
Segmentation fault

In syslog there is the plugins's message:
Code: Select all
SIZE_OVERFLOW: size overflow detected in function asn1_d2i_read_bio a_d2i_fp.c:228 cicus.69_205 (max)

I'll have more (gentoo) ebuilds if anyone wants to use the plugin in userland (for now only openssl):

A sample of real life bugs prevented by the size_overflow plugin:
  • Code: Select all
    PAX: size overflow detected in function ptr_to_compat /usr/src/linux-3.8.2/arch/x86/include/asm/compat.h:293 cicus.85_5 max, count: 33
    Pid: 3168, comm: skype Not tainted 3.8.2-grsec #3
    Call Trace:
    [<ffffffff81145054>]  report_size_overflow+0x24/0x30
    [<ffffffff81071f5d>]  sys32_rt_sigaction+0x2ad/0x3f0
    [<ffffffff8175fd3c>]  sysenter_dispatch+0x7/0x24

  • Code: Select all
    PAX: size overflow detected in function i915_gem_execbuffer_relocate_slow drivers/gpu/drm/i915/i915_gem_execbuffer.c:529 cicus.214_181 max, count: 57
    Pid: 3107, comm: a.out Not tainted 3.8.2-grsec #2
    Call Trace:
    [<ffffffff81145054>] report_size_overflow+0x24/0x30
    [<ffffffff81419bd2>] i915_gem_execbuffer_relocate_slow+0x692/0xc90
    [<ffffffff814191b6>] i915_gem_execbuffer_reserve_object.isra.13+0x126/0x190
    [<ffffffff8141a9ba>] i915_gem_do_execbuffer.isra.16+0x7ea/0xff0

    CVE-2013-0913: ... 8513589249 ... -2013-0913
  • Code: Select all
    SIZE_OVERFLOW: size overflow detected in function ptr_to_compat /home/build/linux-3.2.39/arch/x86/include/asm/compat.h:206 cicus.40_5 min, count: 4
    Pid: 2813, comm: gdbus Not tainted 3.2.39-cica3 #1
    Call Trace:
     [<ffffffff81100b2e>] report_size_overflow+0x22/0x2e
     [<ffffffff8103331d>] ptr_to_compat+0x42/0x61
     [<ffffffff810334d2>] copy_siginfo_to_user32+0xa7/0xd5
     [<ffffffff81033ae1>] ia32_setup_rt_frame+0xbe/0x249
     [<ffffffff8100ded0>] do_signal+0x12c/0x5c

    CVE-2013-2141: ... -2013-2141

Performance impact

hardware: quad core ivy bridge
kernel version: 3.8.5
patch: grsecurity-2.9.1-3.8.5-201303292018.patch
overflow checks after optimization (gcc-4.7.2): 4234

With the size_overflow plugin disabled:
Code: Select all
 Performance counter stats for 'du -s /gcc_git_trees/' (10 runs):

       1216.760593 task-clock                #    0.992 CPUs utilized            ( +-  0.54% )
               308 context-switches          #    0.253 K/sec                    ( +-  0.61% )
                 0 cpu-migrations            #    0.000 K/sec                 
              4741 page-faults               #    0.004 M/sec                    ( +-  0.03% )
        3731169367 cycles                    #    3.066 GHz                      ( +-  0.22% )
        1865733287 stalled-cycles-frontend   #   50.00% frontend cycles idle     ( +-  0.44% )
   <not supported> stalled-cycles-backend 
        4485987281 instructions              #    1.20  insns per cycle       
                                             #    0.42  stalled cycles per insn  ( +-  0.01% )
         845691497 branches                  #  695.035 M/sec                    ( +-  0.01% )
          12989739 branch-misses             #    1.54% of all branches          ( +-  0.59% )

       1.226934562 seconds time elapsed                                          ( +-  0.54% )

With the size_overflow plugin enabled:

Code: Select all
 Performance counter stats for 'du -s /gcc_git_trees/' (10 runs):

       1541.178810 task-clock                #    0.992 CPUs utilized            ( +-  3.10% )
               390 context-switches          #    0.253 K/sec                    ( +-  3.16% )
                 0 cpu-migrations            #    0.000 K/sec                 
              4741 page-faults               #    0.003 M/sec                    ( +-  0.05% )
        3804672866 cycles                    #    2.469 GHz                      ( +-  0.53% )
        1928553406 stalled-cycles-frontend   #   50.69% frontend cycles idle     ( +-  1.05% )
   <not supported> stalled-cycles-backend 
        4489668567 instructions              #    1.18  insns per cycle       
                                             #    0.43  stalled cycles per insn  ( +-  0.01% )
         846913036 branches                  #  549.523 M/sec                    ( +-  0.01% )
          12916154 branch-misses             #    1.53% of all branches          ( +-  0.47% )

       1.553941996 seconds time elapsed                                          ( +-  3.10% )

When the size_overflow plugin is enabled, it causes 2% slowdown.

Allyes kernel config statistics after optimization
(number of calls to report_size_overflow, gcc-4.7.2)

vmlinux_4.7.x_i386-yes: 6104
vmlinux_4.7.x_x86_64-yes: 7681

vmlinux_4.7.x_i386-yes: 5602
vmlinux_4.7.x_x86_64-yes: 5089

Future plans
  • enable the plugin to compile c++ sources
    • compile the following programs with the plugin
    • glibc: i tried to compile it already but the make system doesn't like my report_size_overflow function, so I'll try it later
    • glib
    • syslog-ng: I don't yet know where to report the overflow message (chicken and egg problem ;))
    • firefox
    • chromium
    • samba
    • apache
    • php
    • the Android kernel
    • anything with an integer overflow CVE :)
  • plugin internals plans:
    • print out overflowed value in the report message
    • comments :)
    • optimization: use unlikely/__builtin_expect for the inserted checks
    • handle ADDR_EXPR
    • make use of LTO (gcc 4.7+): could get rid of the hash table
    • llvm size_overflow plugin
    • an IPA pass to be able to track back across static functions in a translation unit, it would reduce the hash table
    • handle function pointers
    • handle struct fields
    • fix this side effect: warning: call to 'copy_to_user_overflow' declared with attribute warning: copy_to_user() buffer size is not provably correct

If anyone's interested in compiling other userland programs with the plugin then please send the hash table and the patch to me please :).
Posts: 62
Joined: Tue Mar 20, 2012 4:36 pm

Re: Inside the Size Overflow Plugin

Postby ephox » Sun Mar 31, 2013 7:48 pm

updated 2013 04 01, changed sections:
  • The attributes: __intentional_overflow()
  • The hash table: PARAM0
  • stmt duplication with double wide integer types: handling of function return values
  • Inserting the overflow checks: the table of the cast check was changed
  • Plugin internals through a simple example: duplicate with signed double size type
  • Detecting a real security issue: CVE-2013-0914, CVE-2013-0913
  • Performance impact: new tests with the latest (20130316) plugin
  • Allyes kernel config statistics after optimization: new code insertion statistics with the latest version
Posts: 62
Joined: Tue Mar 20, 2012 4:36 pm

Re: Inside the Size Overflow Plugin

Postby crd » Mon Apr 01, 2013 8:57 pm

Very nice work. Thank you!
Posts: 7
Joined: Mon Aug 29, 2011 1:04 pm
Location: Pittsburgh

Return to Blog