"Strong" stack protection for GCC

Posted Feb 14, 2014 5:06 UTC (Fri) by ewimberley (guest, #95544)
In reply to: "Strong" stack protection for GCC by jtc
Parent article: "Strong" stack protection for GCC

Integer overflows/underflows are an example of a write-what-where that allows you to skip the canary completely. If your corruption target is referenced before function return then you can write over the canary without fear of triggering a stack check. In this case the target can be anywhere higher in memory than the overflow (even in another stack frame completely).

If you want a bunch of examples check the code in my github repo:
https://github.com/ewimberley/AdvancedMemoryChallenges

"Strong" stack protection for GCC

Posted Feb 14, 2014 16:31 UTC (Fri) by mathstuf (subscriber, #69389) [Link] (15 responses)

So the Mill CPU has "Not a Result" as a possible result of instructions. Using this, it has 4 variants of, e.g., "add": saturating, wrap-around, sum+overflow flag, and overflow-error (which returns a NaR, *not* a value, which errors upon use (and is tagged with information to help figure out where it came from)). I'd like to see the day where the CPU assists with over and underflow detection.

"Strong" stack protection for GCC

Posted Feb 14, 2014 17:06 UTC (Fri) by mpr22 (subscriber, #60784) [Link] (14 responses)

CPUs have offered some assistance with overflow detection for over half a century (System/360 (1964) had a branch-on-overflow insn). The primary responsibility for arithmetic overflow detection not being ubiquitous in real-world software lies not with CPU designers and implementers, but with the designers and implementers of languages that don't take advantage of that assistance and the programmers who chose not to use, or not to press for the creation of, languages that do.

"Strong" stack protection for GCC

Posted Feb 14, 2014 18:10 UTC (Fri) by mathstuf (subscriber, #69389) [Link]

So the difference here is that the Mill will only cause a failure on *use* of the result, not the *generation* of the result. If you overflow an integer but never use it…who cares? The nice thing about it is that it also doesn't increase code size or extra time, so there's no overhead for the check and you don't need an instrumented build to find the problem(s).

Really, I'd just like for a C compiler to use the error-on-overflow for signed addition and such so that the undefined behavior is able to be caught without extra cost instead of it just being "some random value".

"Strong" stack protection for GCC

Posted Feb 15, 2014 13:30 UTC (Sat) by renox (guest, #23785) [Link] (5 responses)

*some* CPU help for detecting cheaply under/over flow, but unfortunately except for the MIPS they are quite confidential: neither x86 or ARM provide it..

"Strong" stack protection for GCC

Posted Feb 15, 2014 14:23 UTC (Sat) by PaXTeam (guest, #24616) [Link] (4 responses)

so what do into/jo/jno/bvs/bvc do?

"Strong" stack protection for GCC

Posted Feb 15, 2014 22:39 UTC (Sat) by kleptog (subscriber, #1183) [Link] (3 responses)

It's always bugged me that CPUs have all sorts of flags (Carry, Overflow & Zero) yet they're not exposed at the C level. Not even as GCC builtins. There are tricks with pushf but they're workarounds.

To be fair, the C language doesn't make it easy since there's no nice syntax for returning multiple values. So you get alternatives like:

res = check_overflow_sadd(a, b, &overflow)
if(overflow)
    error();

if(check_overflow_sadd(a,b))
    error();
res = a+b;

neither of which are really nice. But there are many places where the carry and overflow bits could be used to simplify programs and make them more readable.

"Strong" stack protection for GCC

Posted Feb 16, 2014 1:46 UTC (Sun) by mathstuf (subscriber, #69389) [Link] (2 responses)

The problem with a C abstraction is that on CPU models without instructions or flags for it, your simple addition is now how many instructions even in release and -Os builds.

And this is what Mill offers you…sane behavior with zero code change. If the compiler detects custom overflow detection or whatever, just change the flavor of 'add' to use. There's nothing against such optimizations (and other targets could implement it too, but if you now have to stall the pipeline to fetch a flag, it might not really be worth it overall). *Detecting* them might be hard to Turing-complete, but that never stopped us from parsing Perl or C++, has it ;) .

"Strong" stack protection for GCC

Posted Feb 16, 2014 11:03 UTC (Sun) by paulj (subscriber, #341) [Link] (1 responses)

Well, even on CPUs with flags, adding branching checks for them after every arithmetical instruction would be a noticeable overhead. That said, I think it'd still be very worthwhile on certain lumps of code. Sometimes correctness and helping programmers guard against their own omniscience matters a lot more than performance!

"Strong" stack protection for GCC

Posted Feb 16, 2014 11:08 UTC (Sun) by paulj (subscriber, #341) [Link]

Sigh... guard against their own _lack_ of omniscience.

"Strong" stack protection for GCC

Posted Feb 16, 2014 10:25 UTC (Sun) by paulj (subscriber, #341) [Link] (6 responses)

And of course many popular CPUs (x86, MIPS, ARM), have overflow and carry-out flags in their ISA, which will be set appropriately by integer arithmetical instructions. These could also provide protection.

The problem is in the C implementations. Overflow is undefined behaviour in C, so implementations *could* have chosen to implement some kind of trap or exception (signal, etc) in response. Yet, AFAIK, most don't and silently allow overflow to occur. (I'd be curious to hear about any that do). When C runtimes generally don't provide a way to trap overflows, then it becomes very difficult for any other languages or runtimes to do so, unless they bypass C.

This is probably a lamentable state of affairs. Down to decisions made in the days when performance was king and other factors like correctness and security weren't really a consideration (relative to today). Decisions which, in my view, certainly don't serve us well anymore.

There's a longer argument about whether traps would have been more efficient than flags that have to be checked, and whether traps might have been more likely to be implemented. Still, there is surely lots of code where the security benefits of runtime overflow-checking would outweigh any performance costs? If there were a way to enable error/trap-on-overflow (with unhandled leading to termination), that could be quite useful. If it existed, it might possibly be nice to be able to enable/disable this just on a per-file or even function basis, to limit the overheads.

I'd be curious to read more about the relative costs of the overheads, and the effectiveness of overflow flag checking on current ISAs, if anyone knows.

GCC has an "-ftrapv" argument which I was hoping might do this, and use hardware flags when possible. Though, a trivial test-case (adding command-line arguments) doesn't behave any differently with overflow when compiled with ftrapv on x86-64 and happily runs past an overflow, so maybe I've misunderstood what it's meant to do (the trapv compiled code uses __addvdi3 for the addition, if -O isn't passed). ?? With -O it seems to be using leaq to generate the addition.

"Strong" stack protection for GCC

Posted Feb 16, 2014 10:47 UTC (Sun) by jem (subscriber, #24231) [Link] (1 responses)

"Overflow is undefined behaviour in C."

To be more precise, signed overflow is undefined behaviour in C. Unsigned integers are defined to wrap around.

"Strong" stack protection for GCC

Posted Feb 16, 2014 10:58 UTC (Sun) by paulj (subscriber, #341) [Link]

I wish LWN had +1 buttons, so I wouldn't have to make comments like this. :)

"Strong" stack protection for GCC

Posted Feb 16, 2014 11:06 UTC (Sun) by mchapman (subscriber, #66589) [Link] (3 responses)

> Though, a trivial test-case (adding command-line arguments) doesn't behave any differently with overflow when compiled with ftrapv on x86-64 and happily runs past an overflow

It needs to be a 64-bit signed integer. An int is likely to be only 32 bits.

"Strong" stack protection for GCC

Posted Feb 16, 2014 11:09 UTC (Sun) by mchapman (subscriber, #66589) [Link]

> It needs to be a 64-bit signed integer. An int is likely to be only 32 bits.

On second thoughts, that may be a compiler bug.

At any rate, I could only get it to work on GCC 4.8.2 if I used a 64-bit integer.

"Strong" stack protection for GCC

Posted Feb 16, 2014 11:13 UTC (Sun) by paulj (subscriber, #341) [Link] (1 responses)

Ah. Indeed, with longs instead and a 64bit overflow it core-dumps.

Hmm, that's pretty limited in usefulness so, and buggy with respect to what the documentation suggests it does (the docs don't qualify when overflow checks will actually be done). :(

"Strong" stack protection for GCC

Posted Feb 16, 2014 11:15 UTC (Sun) by mchapman (subscriber, #66589) [Link]

> and buggy with respect to what the documentation suggests it does

Yes, indeed: http://gcc.gnu.org/bugzilla/show_bug.cgi?id=52478