Jump to content
Nytro

Inside the Size Overflow Plugin

Recommended Posts

Inside the Size Overflow Plugin

by 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://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:

#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:

gimple_call <malloc, D.4425_2, D.4421_15>

or a subtract (gimple_code: GIMPLE_ASSIGN) stmt:

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:

SSA - GNU Compiler Collection (GCC) Internals

GIMPLE - GNU Compiler Collection (GCC) Internals

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 attribute

Plugins can define new attributes. This plugin defines a new function attribute which 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:

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) { ... }

Further documentation about attributes:

Attributes - GNU Compiler Collection (GCC) Internals

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.5.1 2920 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/generate_size_overflow_hash.sh script from tools/gcc/size_overflow_hash.data 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

For example this is what the hash entry of the include/linux/slub_def.h:kmalloc function looks like:

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()).

Example:

struct size_overflow_hash *size_overflow_hash[65536] = {
[11268] = &_000008_hash,
};

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
  • .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. This also means that the current plugin version doesn't check if a function returns an overflowed value, see todo
  • 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:

Function %s is missing from the size_overflow hash table +%s+%d+%u+" (caller's name, 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 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:

  ---------------------------------
| from | to | lhs | rhs |
---------------------------------
| u32 | u32 | - | ! |
| u32 | s32 | TODO | *! |
| s32 | u32 | TODO | *! |
| s32 | s32 | - | ! |
| u32 | u64 | ! | ! |
| u32 | s64 | TODO | ! |
| s32 | u64 | TODO | ! |
| s32 | s64 | ! | ! |
| u64 | u32 | ! | ! |
| u64 | s32 | TODO | ! |
| s64 | u32 | TODO | ! |
| s64 | s32 | ! | ! |
| u64 | u64 | - | ! |
| u64 | s64 | TODO | *! |
| s64 | u64 | TODO | *! |
| 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
  • TODO: would be nice to insert an overflow check, see todo
  • *!: the plugin inserts an overflow check except when the stmt's def_stmt is a MINUS_EXPR (subtraction)
  • -: no overflow check is needed

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):

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 two strings are only debug information.

The report_size_overflow function's message looks like this (without PaX it uses SIZE_OVERFLOW instead of PAX):

PAX: size overflow detected in function main tests/main12.c:27 cicus.4_21 (max)

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):

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

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:

gcc  -I`gcc -print-file-name=plugin`/include/c-family -I`gcc  -print-file-name=plugin`/include -fPIC -shared -O2 -o  size_overflow_plugin.so size_overflow_plugin.c

Compile test.c with the plugin and dump its ssa representations:

gcc -fplugin=size_overflow_plugin.so 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*):

main (int argc, char * * argv)
{
long unsigned int c;
long unsigned int b;
long unsigned int a;
const char * restrict D.3291;
void * D.3290;
int D.3289;
long unsigned int D.3288;
const char * restrict D.3287;
char * D.3286;
char * * D.3285;
const char * restrict D.3284;
char * D.3283;
char * * D.3282;

<bb 2>:
c_1 = 10;
D.3282_3 = argv_2(D) + 4;
D.3283_4 = *D.3282_3;
D.3284_5 = (const char * restrict) D.3283_4;
a_6 = strtoul (D.3284_5, 0B, 0);
D.3285_7 = argv_2(D) + 8;
D.3286_8 = *D.3285_7;
D.3287_9 = (const char * restrict) D.3286_8;
b_10 = strtoul (D.3287_9, 0B, 0);
D.3288_11 = a_6 * b_10;
c_12 = D.3288_11 + c_1;
D.3290_13 = coolmalloc (c_12);
D.3291_14 = (const char * restrict) &"%p\n"[0];
D.3289_15 = printf (D.3291_14, D.3290_13);
return D.3289_15;
}

After the size_overflow pass on a 32 bit arch (test.c.*size_overflow*):

main (int argc, char * * argv)
{
long unsigned int cicus.7;
long long unsigned int cicus.6;
long long unsigned int cicus.5;
long long unsigned int cicus.4;
long long unsigned int cicus.3;
long long unsigned int cicus.2;
long unsigned int c;
long unsigned int b;
long unsigned int a;
const char * restrict D.3291;
void * D.3290;
int D.3289;
long unsigned int D.3288;
const char * restrict D.3287;
char * D.3286;
char * * D.3285;
const char * restrict D.3284;
char * D.3283;
char * * D.3282;

<bb 2>:
c_1 = 10;
cicus.5_24 = (long long unsigned int) c_1;

D.3282_3 = argv_2(D) + 4;
D.3283_4 = *D.3282_3;
D.3284_5 = (const char * restrict) D.3283_4;

a_6 = strtoul (D.3284_5, 0B, 0);
cicus.2_21 = (long long unsigned int) a_6;

D.3285_7 = argv_2(D) + 8;
D.3286_8 = *D.3285_7;
D.3287_9 = (const char * restrict) D.3286_8;

b_10 = strtoul (D.3287_9, 0B, 0);
cicus.3_22 = (long long unsigned int) b_10;

D.3288_11 = a_6 * b_10;
cicus.4_23 = cicus.2_21 * cicus.3_22;

c_12 = D.3288_11 + c_1;
cicus.6_25 = cicus.4_23 + cicus.5_24;

cicus.7_26 = (long unsigned int) cicus.6_25;
if (cicus.6_25 > 4294967295)
goto <bb 3>;
else
goto <bb 4>;

<bb 3>:
report_size_overflow ("test.c", 28, "main", "cicus.6_25 (max)\n");

<bb 4>:
D.3290_13 = coolmalloc (cicus.7_26);

D.3291_14 = (const char * restrict) &"%p\n"[0];
D.3289_15 = printf (D.3291_14, D.3290_13);
return D.3289_15;
}

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 icon_wink.gif.
    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:
    coolmalloc(a * b - 1 + argc)


    before size_overflow plugin:...

    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:
    ...

    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://lock.cmpxchg8b.com/openssl-1.0.1-testcase-32bit.crt.gz

Download the plugin source (or use the ebuild) from here:

https://grsecurity.net/~ephox/overflow_plugin/

Download the openssl patch (that contains the report_size_overflow function):

http://grsecurity.net/~ephox/overflow_plugin/userland_patches/openssl-1.0.0/

Compile openssl with the plugin (see the README) after that we can reproduce the bug:

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:

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):

http://grsecurity.net/~ephox/overflow_plugin/gentoo/

Performance impact

hardware: quad core sandy bridge

kernel version: 3.5.1

patch: pax-linux-3.5.1-test16.patch

overflow checks after optimization (gcc-4.7.1): 931

With the size_overflow plugin disabled:

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

4345.283145 task-clock # 0.983 CPUs utilized ( +- 0.12% )
1,107 context-switches # 0.255 K/sec ( +- 0.09% )
0 CPU-migrations # 0.000 K/sec ( +-100.00% )
3,763 page-faults # 0.866 K/sec ( +- 0.13% )
14,641,126,270 cycles # 3.369 GHz ( +- 0.03% )
4,228,389,062 stalled-cycles-frontend # 28.88% frontend cycles idle ( +- 0.06% )
1,962,172,809 stalled-cycles-backend # 13.40% backend cycles idle ( +- 0.23% )
25,463,911,605 instructions # 1.74 insns per cycle
# 0.17 stalled cycles per insn ( +- 0.01% )
6,968,592,408 branches # 1603.714 M/sec ( +- 0.01% )
47,230,732 branch-misses # 0.68% of all branches ( +- 0.07% )

4.419888484 seconds time elapsed ( +- 0.12% )

With the size_overflow plugin enabled:

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

4291.088943 task-clock # 0.983 CPUs utilized ( +- 0.08% )
1,093 context-switches # 0.255 K/sec ( +- 0.08% )
0 CPU-migrations # 0.000 K/sec
3,761 page-faults # 0.877 K/sec ( +- 0.15% )
14,481,436,247 cycles # 3.375 GHz ( +- 0.05% )
4,155,959,526 stalled-cycles-frontend # 28.70% frontend cycles idle ( +- 0.15% )
2,003,994,250 stalled-cycles-backend # 13.84% backend cycles idle ( +- 0.54% )
25,436,031,783 instructions # 1.76 insns per cycle
# 0.16 stalled cycles per insn ( +- 0.00% )
6,960,975,325 branches # 1622.193 M/sec ( +- 0.00% )
47,125,984 branch-misses # 0.68% of all branches ( +- 0.07% )

4.365185965 seconds time elapsed ( +- 0.08% )

TODO: I don't know why it was faster with the plugin on these tests icon_smile.gif

During compilation it didn't cause too much slowdown (0.077s only).

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

3.5.0:

vmlinux_4.6.x_i386-yes: 2556

vmlinux_4.6.x_x86_64-yes: 2659

3.2.26:

vmlinux_4.6.x_i386-yes: 2657

vmlinux_4.6.x_x86_64-yes: 2756

2.6.32.59:

vmlinux_4.6.x_i386-yes: 1893

vmlinux_4.6.x_x86_64-yes: 2353

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 icon_wink.gif)
    • firefox
    • chromium
    • samba
    • apache
    • php
    • the Android kernel
    • anything with an integer overflow CVE icon_smile.gif

    [*]plugin internals plans:

    • print out overflowed value in the report message
    • comments icon_smile.gif
    • optimization: use unlikely/__builtin_expect for the inserted checks
    • if the expression can be tracked back to the result of a function call then the function's return value should be tracked back as well
    • 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
    • solve all the TODO items in the cast handling table

If anyone's interested in compiling other userland programs with the plugin then please send the hash table and the patch to me please

Sursa: grsecurity forums • View topic - Inside the Size Overflow Plugin

Edited by Nytro
Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.



×
×
  • Create New...