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.
http://www.grsecurity.net/~ephox/const_plugin/

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.
https://github.com/ephox-gcc-plugins/size_overflow
https://grsecurity.net/~ephox/overflow_plugin/

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:
http://www.phrack.org/issues.html?issue ... 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 has a GIMPLE and a regular IPA pass. The GIMPLE pass (insert_size_overflow_asm) marks the parameters (marked with a size_overflow attribute) with an asm statement. This is needed
because the IPA pass runs after inlining and all functions of interest get inlined thus losing the size_overflow attribute.
The IPA pass collects all decls of interest (generate_summary), prints out the missing functions (execute) and duplicates the necessary statements (transform). The plugin also supports LTO with gcc-4.9 (not public yet).

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, GIMPLE and IPA/LTO:
http://gcc.gnu.org/onlinedocs/gccint/SSA.html
https://gcc.gnu.org/onlinedocs/gccint/LTO.html
http://gcc.gnu.org/onlinedocs/gccint/GIMPLE.html


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:
http://gcc.gnu.org/onlinedocs/gccint/Attributes.html


The hash tables

Originally we only had the attribute similarly to the constify plugin but in order to reduce the kernel patch size all functions except for the base ones are stored in a hash table.

Size_overflow hash table

The hash table is generated by the tools/gcc/size_overflow_plugin/generate_size_overflow_hash.sh script from tools/gcc/size_overflow_plugin/size_overflow_hash.data into tools/gcc/size_overflow_plugin/size_overflow_hash.h.
The hash table stores functions, function pointers, struct fields and variable declarations.
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 declaration
  • param: an integer with bits set corresponding to the size parameters, PARAM0 means the function return value.
  • context: needed to improve the hash and also to differentiate the decl types as follows:
    • fields: the name of the encompassing struct
    • function pointers: the name of the encompassing struct if any
    • functions: "fndecl"
    • variables: "vardecl" and for static globals also the file name

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 enable_so___kmalloc_fndecl_1964 = {
    .next   = NULL,
    .name   = "__kmalloc",
    .context = "fndecl",
    .param  = PARAM1,
};

The hash table is indexed by a hash computed from the return type, the name of the function, the context and the type of the function parameters.
Example:
Code: Select all
const struct size_overflow_hash * const size_overflow_hash[65536] = {
       [1964] = &enable_so___kmalloc_fndecl_1964,
};

The size_overflow hash table for linux 4.1.7 has 30139 entries.

Hash table for disabled size_overflow functions

This hash table is generated by the tools/gcc/size_overflow_plugin/generate_size_overflow_hash.sh script from tools/gcc/size_overflow_plugin/disable_size_overflow_hash.data into tools/gcc/size_overflow_plugin/disable_size_overflow_hash.h.
The hash table stores functions that are of no interest for the size_overflow checks. For now these are functions returning an error code which are discovered in LTO mode.

The disable size_overflow hash table for linux 4.1.7 has 10017 entries.


The hash algorithm is CrapWow:
http://www.team5150.com/~andrew/noncryptohashzoo/CrapWow.html


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

stmt duplication with double wide integer types

The plugin handles data flows from the following declarations:
  • functions: return value (0) and parameters (1-32)
  • function pointers: return value (0), parameters (1-32) and all pointed-to functions which are discovered in LTO mode and stored in the hash table (for non-LTO mode use). Mostly implemented -> TODO
  • global variables: if the data flow reaches a global variable then all writes to the variable are traced back as well. Not fully implemented -> TODO
  • structure fields: if the data flow reaches a structure field then all writes to the field are traced back as well. Mostly implemented -> TODO

When the plugin finds a marked decl 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.
  • division (RDIV_EXPR, etc.): special case for the kernel because it doesn't support division with double wide types

If the marked decl's parameter can be traced back to a decl 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+%s+%u+%u+" (decl name, decl name, context, parameter's number, hash)

If anyone sees this message, please send it to me by e-mail (re.emese@gmail.com) 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/function pointer parameters just before the function call
  • writes to global variables
  • writes to structure fields
  • stmt with a constant operand, see gcc intentional overflow
  • negations (BIT_NOT_EXPR, NEGATE_EXPR)
  • comparison_codes
  • integer truncations in subtractions
  • 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  |   -   |    !   |
 ---------------------------------

Legend:
  • 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


report_size_overflow

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:
Code: Select all
PAX: size overflow detected in function main test.c:26 cicus.15_19 max, count: 3, decl: # size_overflow MARK_NO coolmalloc 1; num: 0; context: attr;


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
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

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);
        fflush(stdout);
        _exit(1);
}

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

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


Compile the plugin (e.g., gcc-4.9):
Code: Select all
g++ -I`g++ -print-file-name=plugin`/include -I`g++-print-file-name=plugin`/include/c-family  -std=gnu++98 -fno-rtti -Wno-narrowing -Og -fPIC -shared -ggdb -Wall -W -o size_overflow_plugin.so insert_size_overflow_asm.c intentional_overflow.c size_overflow_misc.c remove_unnecessary_dup.c size_overflow_debug.c size_overflow_ipa.c size_overflow_lto.c size_overflow_plugin.c size_overflow_plugin_hash.c size_overflow_transform.c size_overflow_transform_core.c size_overflow_fnptrs.c

Compile test.c with the plugin and dump its ssa representations:
Code: Select all
gcc -fplugin=size_overflow_plugin.so test.c -o test -O2 -fdump-tree-all -fdump-ipa-all


Each dumpable gcc pass is dumped by -fdump-tree-all and -fdump-ipa-all. This blog post focuses on the ssa and the size_overflow passes.
The marked function is coolmalloc, the traced parameter is _9. The main function's ssa representaton is below, just before executing the size_overflow pass (test.c.*.size_overflow_functions*, before transform):
Code: Select all
main (int argc, char * * argv)
{
  long unsigned int cicus.5;
  long unsigned int b;
  long unsigned int a;
  char * _3;
  char * _6;
  long unsigned int _9;
  int _10;
  void * _13;

  <bb 2>:
  _3 = MEM[(char * *)argv_1(D) + 8B];
  a_5 = strtoul (_3, 0B, 0);
  _6 = MEM[(char * *)argv_1(D) + 16B];
  b_8 = strtoul (_6, 0B, 0);
  _9 = a_5 * b_8;
  __asm__ __volatile__("# size_overflow MARK_NO coolmalloc 1" : "=rm" cicus.5_12 : "0" _9);
  _13 = malloc (cicus.5_12);
  _10 = __printf_chk (1, "%p\n", _13);
  return _10;

}


After the size_overflow pass on a 64 bit arch (test.c.*size_overflow_function*):
Code: Select all
main (int argc, char * * argv)
{
  long unsigned int cicus.14;
  size_overflow_type_TI cicus.13;
  size_overflow_type_TI cicus.12;
  size_overflow_type_TI cicus.11;
  long unsigned int cicus.5;
  long unsigned int b;
  long unsigned int a;
  char * _3;
  char * _6;
  long unsigned int _9;
  int _10;
  void * _13;

  <bb 2>:
  _3 = MEM[(char * *)argv_1(D) + 8B];
  a_5 = strtoul (_3, 0B, 0);
  cicus.11_15 = (size_overflow_type_TI) a_5;

  _6 = MEM[(char * *)argv_1(D) + 16B];
  b_8 = strtoul (_6, 0B, 0);
  cicus.12_16 = (size_overflow_type_TI) b_8;

  _9 = a_5 * b_8;
  cicus.13_17 = cicus.11_15 * cicus.12_16;

  cicus.14_18 = (long unsigned int) cicus.13_17;
  if (cicus.13_17 > 18446744073709551615)
    goto <bb 4>;
  else
    goto <bb 3>;

  <bb 4>:
  report_size_overflow ("test.c", 26, "main", "cicus.13_17 max, count: 1, decl: # size_overflow MARK_NO coolmalloc 1; num: 0; context: attr;\n");

  <bb 3>:
  if (cicus.13_17 < 0)
    goto <bb 6>;
  else
    goto <bb 5>;

  <bb 6>:
  report_size_overflow ("test.c", 26, "main", "cicus.13_17 min, count: 2, decl: # size_overflow MARK_NO coolmalloc 1; num: 0; context: attr;\n");

  <bb 5>:
  cicus.5_12 = cicus.14_18;
  _13 = malloc (cicus.5_12);

  _10 = __printf_chk (1, "%p\n", _13);
  return _10;

}


After gcc optimization (test.c.*nrv*):
Code: Select all
main (int argc, char * * argv)
{
  long unsigned int cicus.14;
  size_overflow_type_TI cicus.13;
  size_overflow_type_TI cicus.12;
  size_overflow_type_TI cicus.11;
  long unsigned int cicus.5;
  long unsigned int b;
  long unsigned int a;
  char * _3;
  char * _6;
  int _10;
  void * _13;

  <bb 2>:
  _3 = MEM[(char * *)argv_1(D) + 8B];
  a_5 = strtoul (_3, 0B, 0);
  cicus.11_15 = (size_overflow_type_TI) a_5;   // an RTL pass will optimize it out (TODO: figure out why it doesn't happen earlier)

  _6 = MEM[(char * *)argv_1(D) + 16B];
  b_8 = strtoul (_6, 0B, 0);
  cicus.12_16 = (size_overflow_type_TI) b_8;

  cicus.13_17 = a_5 w* b_8;
  cicus.14_18 = (long unsigned int) cicus.13_17;
  if (cicus.13_17 > 18446744073709551615)
    goto <bb 3>;
  else
    goto <bb 4>;

  <bb 3>:
  report_size_overflow ("test.c", 26, "main", "cicus.13_17 max, count: 1, decl: # size_overflow MARK_NO coolmalloc 1; num: 0; context: attr;\n");

  <bb 4>:
  _13 = malloc (cicus.14_18);
  _10 = __printf_chk (1, "%p\n", _13); [tail call]
  return _10;

}


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>;
       else
       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:
http://www.grsecurity.net/~ephox/overflow_plugin/userland_patches/openssl-1.0.1-testcase-32bit.crt.gz

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)


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

    CVE-2013-0914:
    http://www.openwall.com/lists/oss-security/2013/03/11/8
  • 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:
    https://twitter.com/grsecurity/status/3 ... 8513589249
    http://web.nvd.nist.gov/view/vuln/detai ... -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:
    http://web.nvd.nist.gov/view/vuln/detai ... -2013-2141

Performance impact

hardware: quad core ivy bridge
kernel version: 4.1.7
patch: grsecurity-3.1-4.1.7-201509131604.patch
overflow checks after optimization (gcc-4.9.2): 6263
cmd: perf stat -r 10 du -s gcc_git_trees

With the size_overflow plugin disabled:
Code: Select all
30157580        gcc_git_trees

 Performance counter stats for 'du -s gcc_git_trees' (10 runs):

       2622.812843      task-clock (msec)         #    0.996 CPUs utilized            ( +-  0.10% )
               660      context-switches          #    0.252 K/sec                    ( +-  0.30% )
                 0      cpu-migrations            #    0.000 K/sec                    ( +-100.00% )
              4874      page-faults               #    0.002 M/sec                    ( +-  0.02% )
        8051630331      cycles                    #    3.070 GHz                      ( +-  0.09% )
        5331288950      stalled-cycles-frontend   #   66.21% frontend cycles idle     ( +-  0.09% )
   <not supported>      stalled-cycles-backend
        4635804679      instructions              #    0.58  insns per cycle
                                                  #    1.15  stalled cycles per insn  ( +-  0.03% )
         847369130      branches                  #  323.076 M/sec                    ( +-  0.03% )
          11450319      branch-misses             #    1.35% of all branches          ( +-  0.21% )

       2.634464019 seconds time elapsed                                          ( +-  0.10% )


With the size_overflow plugin enabled:

Code: Select all
30157580        gcc_git_trees

Performance counter stats for 'du -s gcc_git_trees' (10 runs):

       2646.751478      task-clock (msec)         #    0.995 CPUs utilized            ( +-  0.19% )
               667      context-switches          #    0.252 K/sec                    ( +-  0.31% )
                 0      cpu-migrations            #    0.000 K/sec                    ( +- 66.67% )
              4875      page-faults               #    0.002 M/sec                    ( +-  0.02% )
        8124691134      cycles                    #    3.070 GHz                      ( +-  0.15% )
        5390305425      stalled-cycles-frontend   #   66.34% frontend cycles idle     ( +-  0.20% )
   <not supported>      stalled-cycles-backend
        4674395417      instructions              #    0.58  insns per cycle
                                                  #    1.15  stalled cycles per insn  ( +-  0.02% )
         857245553      branches                  #  323.886 M/sec                    ( +-  0.02% )
          11552712      branch-misses             #    1.35% of all branches          ( +-  0.51% )

       2.658856416 seconds time elapsed                                          ( +-  0.19% )

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

Allyes kernel config statistics after optimization


number of calls to report_size_overflow, gcc-4.9.2:

4.1.7:
vmlinux_i386-yes: 10438
vmlinux_x86_64-yes: 11316
vmlinux_arm-allmod: 4207

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
    • llvm size_overflow plugin
    • 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 :).
ephox
 
Posts: 120
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
ephox
 
Posts: 120
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!
crd
 
Posts: 7
Joined: Mon Aug 29, 2011 1:04 pm
Location: Pittsburgh

Re: Inside the Size Overflow Plugin

Postby ephox » Thu Sep 17, 2015 6:31 pm

changed sections (size_overflow plugin version 20150917):
  • Internals of the size_overflow plugin: size_overflow plugin passes
  • The hash tables: three hash tables and their formats
  • stmt duplication with double wide integer types: function pointers, global variables and structure fields
  • Inserting the overflow checks: function pointers, global variables, integer truncations, comparison_codes and structure fields
  • Plugin internals through a simple example: completely rewritten
  • Performance impact: completely rewritten
ephox
 
Posts: 120
Joined: Tue Mar 20, 2012 4:36 pm


Return to Blog