Towards Optimization-Safe Systems: Analyzing the Impact of Undefined Behavior

This is part of a week(-ish) blog series where I deep-dive on a cool technology. I am an investor at Dell Technologies Capital in Silicon Valley, and occasionally reminisce about my previous life in academia. Follow me on Twitter and LinkedIn.

This week, I’ll be writing about potential security issues that might occur in the code development cycle. This work was done by Xi Wang, who is an all-star computer science professor at University of Washington and a good friend. A lot of his work surrounds building secure and reliable systems, so if this article interests you, I encourage you to check out his other work.

There is a common belief that compilers like GCC are faithful translators of code to x86. However, this isn’t true if your code invokes undefined behavior, and there are serious security implications as result. For example, consider the piece of code below.

The C specification says that pointer overflow is undefined behavior. In GCC, (buf + off) cannot overflow, but that’s different from the hardware! From the compiler’s perspective,

if (buf + off < buf) == if (false)

So, it would delete that x86 code as an optimization. To attack this, an adversary would construct a large value for off and trigger a buffer overflow.

The fundamental problem is that undefined behavior allows such optimizations to happen. So, what exactly is undefined behavior? Undefined behavior is a spec that imposes no requirements. The original goal was to emit efficient. However, compilers assume a program never invokes undefined behavior. For example, if no bound checks are emitted, assume no buffer overflow.

Here are some examples of undefined behavior in C:

However, the problem is that undefined behavior confuses programmers. It produces unstable code, which is code that could be discarded by the compiler because of undefined behavior. As a result, security checks can be discarded, weaknesses are amplified, and system behavior becomes unpredictable.

Xi did a case study of unstable code in the real world, creates an algorithm for identifying unstable code, and wrote a static checker STACK, which found and fixed 160 previously unknown bugs.

Let’s take a look at another example of a broken check in Postgres. Say we want to implement 64-bit signed division x/y in SQL:

We place the check above, but some compiler optimize away the check. x86–64 idivq traps on overflow, leading to a DDoS attack.

This is Xi’s proposed fix, which is compiler-independent:

This is the developer’s fix:

However, that fix is still unstable code.

Here are some observations from his work:

• Compilers silently remove unstable code
• Different compiler behave in different ways, so changing /upgrading compilers could lead to a system crash
• Need a systematic approach to finding and fixing unstable code

Their approach is to precisely flag unstable code: C/C++ source → LLVM IR → STACK → warnings

Here is the design overview:

They were able to find 160 new bugs with low false positive rates. Similarly, STACK was able to scale to large code bases and generate warnings in a reasonable amount of time.

If you’re interested in the bugs they found or for technical details on their approach, I encourage you to check out their paper. You can also find his code here.

This is an interesting piece of work that shows sometimes security bugs occur unintentionally because compilers or language developers make incorrect assumptions about programmer’s behavior. It’s hard to avoid these bugs, but having development tools for detecting is important!

For those who have further interest, consider the following question:

If you have questions, comments, future topic suggestions, or just want to say hi, please send me a note at frank.y.wang@dell.com.