Understanding Undefined Behavior

Session 407 WWDC 2017

Undefined behavior in programming languages can introduce difficult to diagnose bugs and even lead to security vulnerabilities in your App. Learn more about undefined behavior, the tools available in Xcode 9 that address it, and why Swift is safer by design.

[ Background voices ]

Good morning.

Welcome to the understanding undefined behavior session.

I know all of you have already spent countless hours debugging bugs that would just disappear when you switched from release to debug mode.

You might even have lost users because you couldn't reproduce the bugs that happened only on their device.

Those might be signs that you have undefined behavior in your code.

I'm Fred. I work on the client compiler team and today I'll start by explaining what undefined behavior is and why it exists.

Then we'll dive into the compiler and see how its interactions with undefined behavior cause those subtle bugs.

Those bugs might not only cost you a lot of debugging time.

They might have security implications.

Ryan, from our security team, will tell you more about this and how you can use our tools to avoid those issues.

Finally, my colleague Anna will come to the stage and tell you how SWF tackles this problem space.

So, what is undefined behavior?

Undefined behavior happens when your code has correct syntax but its behavior is not within the bounds of what the language allows.

The C and C++ standards have really similar definitions of undefined behavior in the standard.

Let's have a look at what the C++ standard says.

Undefined behavior: Behavior for which this international standard imposes no requirements.

Well, that's helpful, right?

To be fair, it comes with a note that gives more details but it's too long to put up on the screen so here's a summary.

So, what can the compiler do?

If you knew about undefined behavior before coming to this session, you might have heard that if you have undefined behavior, the compiler is allowed to wipe your disc.

I guarantee this is not going to happen.

So, what can I do?

The compiler can choose to diagnose the issues using warnings or errors.

This is by far our preferred solution and it is very actionable on your side and it prevents the issue and the source.

The compiler can also choose to act in a documented manner.

Basically, choosing to define what the standard left undefined.

We do not do this a lot but there are some kinds of undefined behavior, which are way to common not to support.

And finally, the compiler can produce unpredictable results.

This is the part we are going to focus on today.

Note that unpredictable includes behaving as you intended, which is why some of those bugs will be really evasive.

There is a lot of undefined behavior in the C family of languages.

This is just a small sample.

The C standard has a list in Annex J of all the known sources of undefined behavior.

There are around 200 of them.

At this point, you might be wondering why is undefined behavior even a thing?

Why is it defined in the standards?

Were people just lazy?

They didn't want to define everything?

Of course, not.

This is about tradeoffs.

C has been designed to favor performance, affordability, and ease of implementation over safety.

The C family of languages has inherited those tradeoffs.

Those were deliberate choices and they still make a lot of sense in many circumstances today.

Our OSs run fast thanks to them.

But as with every tradeoff, there is a price to pay and in this case it is you, the developers, who are paying it.

This is why it is really important that you know that it exists and how to deal with it.

As I said, there are way too many kinds of undefined behavior to go through all of them but let's just go through a few examples to make sure everybody's on the same page.

My first example is the use of an uninitialized value.

In this function, we have a local variable, value.

It is used in the return statement but it is initialized only if the condition to the if block is true.

If you pass any positive number to this function, it will invoke undefined behavior as value will be used and initialized.

In this simple case, the compiler will catch the issue and warn about it.

The static analyzer would give you that information too and it would catch more complex cases of the same kind.

My second example is about misaligned pointers.

In this function, we take a character pointer as an argument but inside the function, we use it as an integer pointer.

The issue is that not every character pointer is a valid integer pointer.

Integers have to be correctly aligned.

Usually this means their address needs to be a multiple of four.

This kind of code will often cause issues when porting code between different architectures, which have different alignment constraints at the hardware level.

This year, in Xcode 9 we introduced the new Runtime tool, the Undefined Behavior Sanitizer, which would catch this issue.

My last example is about lifetimes.

Variables are defined only within the scope our variables are valued only within the scope they are defined in.

Here, we take the address of the default value variable.

Default is defined within the if block and exists only there.

But by using this pointer outside of the block, we invoke undefined behavior.

Again, our tools will catch that.

Now that we have a better idea of the issues we are talking about, let's take a look at how they interact with the compiler and how they can produce those surprising bugs.

First, let's look at what the compiler, what undefined behavior means to the compiler.

It is not actively looking for it to transform it in weird ways.

This is not happening.

But the compiler makes the assumption that there is no undefined behavior in your code because otherwise the semantics of your code wouldn't be well defined.

By making this assumption, the compiler gathers information to better optimize your code.

Here are a few examples.

As it is undefined to overflow assigned integer, if X is assigned integer, the compiler can assume that X is lower than X + 1.

This is a very simple but very powerful assumption to make when dealing, for example, with loop optimizations.

As I said, pointers need to be aligned.

And by making the assumption that they are, the compiler can use more powerful memory access instructions like vector instructions to make your code way faster.

And last example, it is undefined to dereference another pointer, so the compiler can assume that each pointer that is dereferenced cannot be now and use this information to further optimize your code.

So, let's get a little bit more concrete and look at how a compiler works.

At a very high level, the compiler takes your source code and transforms it into an intermediate representation.

It then applies a pipeline of optimizations to generate optimizations to generate the binary.

Each of those optimizations has one goal, generate a more efficient representation of its input while preserving the semantics.

But I introduced the session by talking about those bugs that would reproduce in release mode but not in debug mode.

So, how is that behavior preserving?

Let's look at a simple example.

Here we have our compiler at the top.

It has only one optimization - dead code elimination.

Dead code elimination looks for code that cannot be executed or that doesn't affect the result of your program in any way and it removes this code, thus making your apps smaller.

Let's apply this compiler to a simple function.

The function has only two statements, one variable assignment and a return statement.

We run dead code elimination.

The variable is not used so let's get rid of it.

And here, look at what we got.

What happens if we pass another pointer to this function?

The unoptimized version will crash but the optimized version will happily return 42.

So, we have a difference in behavior.

But by passing null to this function, you invoked undefined behavior as it is undefined to dereference another pointer.

I'll repeat that.

It is undefined to dereference another pointer.

It is not defined to crash.

If dereferencing another pointer was defined to crash or if for some other reason the compiler couldn't make the assumption that dereferenced pointers were valid, it would be really hard to make any transformations on the memory accesses.

Like, it couldn't reorder them.

It couldn't merge them or it couldn't remove the useless ones, like we just saw.

Dealing with memory access is a huge part of the compiler job.

So, here you have an example of how undefined behavior changes the behavior of your program between unoptimized and optimized code.

But there's more I want to show you.

Let's move to a slightly more complicated example.

Here again we have our compiler that's up and our source at the bottom.

This example is actually derived from a real issue that happened in our big open source code days a few years ago.

So, do not disregard it as completely theoretical.

When you have a big function that is modified by multiple people over a long period of time, it's easy to end up with artifacts from the past, like this unused variable at the top of the function.

Now, let's compile this code.

Our new compiler has one more optimization.

Redundant null check elimination.

This optimization is a specialized version of dead code elimination.

It will look for pointers compared against now and tries to decide if statically at this point of the program it can prove that the pointer is either null or nonnull.

And when it can do so, it just removes the code that can never be executed.

In this case, P is dereferenced in the first line of the function.

So, of course the pointer cannot be null.

Let's remove the null check.

We then move on to our second optimization.

We already know about dead code elimination.

Unused is unused.

It goes away.

And here's the result of our compilation.

Now, let's play the same game.

What happens if we pass null to this function?

The unoptimized version will crash.

The optimized version will crash too.

But note that they don't crash in the same spot.

The unoptimized version crashes on the first line.

The optimized version crashes on the last line.

Those could be hundreds of thousands of lines away.

This is a very important lesson to learn about undefined behavior.

When it causes an issue, whether it is another reference, an integer overflow, memory corruption due to an out of bound access or any other kind of undefined behavior, the symptom you see will often be very far away from the root cause of the issue.

There is one more thing I want to show you.

Let's restart the compilation with a slightly different compiler.

As you see, we just see swapped the two optimizations.

Let's compile the same code again.

Dead code elimination, unused is still unused.

It goes away.

Now we try to apply redundant null check elimination.

There is nothing to - there is nothing to reason anymore about the value of the P pointer so the optimization just does nothing.

And here's the result of our second compilation of the same code.

Note that in this case if you pass a null pointer to the optimized version, it will not crash.

Now, imagine your app has the code on the left and the developer who added the null check to this function at some point added a few uses of the function with another argument.

You might have never realized that it is an issue because your compiler is acting like compiler 2.

But there is no guarantee that in the future it will not act like compiler 1 and break your code.

This is maybe the most important thing to remember about undefined behavior.

The fact that you don't have an issue today doesn't mean that that change in the compiler will not cause it to break in the future.

And your compiler might be changing behavior more than you think.

During a single day, each time you switch between debug and release mode or each time you change the optimization settings, you run a different instance of the compiler with a very different set of transformations applied to your code.

Maybe more surprisingly, each time you switch from a real device to a simulator or vice versa, you are targeting a different architecture, which might react differently to undefined behavior.

And, of course, each time you upgrade Xcode to a new major version, you get a brand new compiler.

And we work hard all year long to make the compiler better, generate faster, smaller code.

Many of those improvements could reveal undefined behavior in your code.

So, before moving along, just, let's just summarize what we learned about undefined behavior.

Undefined behavior will not trigger bugs reliably.

One of your configurations could be working while the other one breaks.

When undefined behavior breaks, when it breaks your code, the symptom you are seeing might be thousands of lines away or maybe even hours of executions away from the real root cause of the issue.

This could be really hard to debug if you are not prepared for it.

And lastly, the fact that you don't have any bugs today that you know of doesn't mean that you don't have any bugs due to undefined behavior.

And if you have undefined behavior, it will break at some point in the future.

When it breaks, it could cost you a lot of debugging time but it could also put your users' data at risk.

Here's Ryan to tell you more about the security implications of undefined behavior.

[ Applause ]

Thanks, Fred.

So, who here remembers the heartbleed vulnerability from a few years ago?

Well, if you're like me, you probably had to go and change your password on like 100 different websites or maybe patch some of your own backend servers.

Well, heartbleed was an out-of-bounds read in a widely used cryptographic library called open SSL.

By sending just one packet to an affected server, an attacker would receive in reply a few kilobytes of the server process's heap memory, which turned into a pretty significant privacy and security exposure.

Now, that out-of-bounds read in heartbleed is an example of undefined behavior and it turns out that undefined behavior is at the core of many different types of security vulnerabilities.

To name just a few, you could think of buffer overflows, uses of uninitialized variables, heat misuse bugs like use after free and double free.

And also race conditions.

So, keep in mind that your users trust your app and potentially with their personal information such as their photos or their private messages.

And so you should do everything you can to make sure that your app is as safe and secure as possible.

And if you're a framework developer, remember that your client apps inherit all of your bugs, just like all those websites inherited the heartbleed vulnerability.

But the good news that there are tools that could help you.

Now, too often we developers reach for our tools only after a bug has manifested some other way.

Maybe it showed up in our users' crash logs.

But by running tools early and often throughout development, we can catch these issues before they ever become a problem that affects our customers.

So, I wanted to relate a story of how one of these tools, Address Sanitizer, saved macOS Yosemite.

So, about one month before the macOS Yosemite public release, many new crashes started appearing throughout the system.

And we had a hunch that we had a heap corruption bug that was in one of the low-level system frameworks.

Well, we were having a really hard time reproducing the issue.

And without being able to reproduce it, we didn't have a smoking gun that was pointing to a specific function that was causing the heap corruption.

And so we turned to a tool that at the time was very new, called Address Sanitizer, and we thought it would help us catch this heap corruption bug.

So, we instrumented some of the system frameworks and we loaded it up.

And sure enough, Address Sanitizer did its job wonderfully and honed right in on this piece of code.

So, to summarize it briefly, we had a CF string and we were constructing a path to a file inside the user's library cache's directory.

And then we needed to convert this C string, sorry, convert this CF string into a C string.

And so, I mean, that's a pretty straightforward thing, right?

We have to measure the length of the CF string, allocate buffer on the heap of that many characters and copy the bytes into it.

And, oh yeah.

We forgot one thing which is that C strings need to be null terminated.

And so we have to add that too.

But we made a mistake, an off by one error.

Because we didn't include that null byte when we were computing the size of the allocation that we needed.

And so we actually overflowed our buffer.

But most of the time this didn't have any impact on the user.

And that's because the heap will round up the size of the allocation.

In this case, let's say we rounded it up to the next multiple of 16 bytes.

And so when we write our null byte into that unused space at the end, that there's no consequence, right?

But let's see what happens when one of the variables in that buffer changes, and that's the username.

Well, if the length of the username changes, the amount of unused space would also change.

And it turned out that if the user's username was exactly 11 characters long, there wouldn't be any unused space and we would end up corrupting the adjacent object on the heap and causing some other part of the code to crash.

And so this was the secret to why it was so hard to catch normally but Address Sanitizer did a great job of finding it right away.

Now, in this case, this off by one probably didn't have many security consequences.

But many other similar bugs can result in exploitable vulnerabilities.

And remember that security flaws often don't manifest until they've been exploited.

So, running tools like Address Sanitizer early and throughout the development process can help you catch these before they ever reach your customer devices.

So, let's talk about the tools that you have at your disposal to catch undefined behavior.

First we'll talk about the compiler, the static analyzer in Xcode, and the Sanitizers - Address Sanitizer, Thread Sanitizer and the Undefined Behavior Sanitizer.

So, let's start with the compiler.

So, the compiler alerts you to parts of your code that might be a little suspicious and it does this in the form of compiler warnings.

Believe it or not, they're not just there to annoy you.

Now, every release of Xcode has better warnings and great features like fixits, so you can resolve them with just one click.

To learn what's new in the compiler this year, check out the What's New in LLDM talk which is later this afternoon.

Now, you might be wondering, do I have the recommended set of warnings turned on for my project?

Well, every time you upgrade Xcode, you'll be presented with the opportunity to modernize your project.

And you can also do this at any time using the validate settings option and that'll help you get into a good state again.

And there's one more build setting that I think you should know about which is treat warnings as errors.

And it does what it says on the tin.

If your project already compiles with relatively few warnings, consider turning that on and enforcing the self-discipline to keep that compiler count low.

Now, let's talk about the static analyzer.

The static analyzer can be thought of as a supercharged version of compiler warnings.

It explores your code and finds bugs that only happen in very particular conditions, maybe conditions that aren't being hit when you normally test your app.

So, what we recommend doing is analyzing during every build.

There's a build setting for this and when you turn it on, Xcode will run a fast analysis pass every time you build your project.

And that makes sure that you can find bugs that you've just introduced as quickly as possible.

But there's also a deeper mode that the analyzer can run in and you can use that at any time, and that's the mode that we recommend using under your continuous integration in order to make the most of the static analyzer's bug finding capabilities.

So, next I'm going to talk about the Sanitizers.

But first to note, the Sanitizers are Runtime tools.

Unlike the compiler or the static analyzer, to get the most out of the Sanitizers, you need to actually run an exerciser code that can only find bugs in code that's actually being executed.

So, keep that in mind.

But they offer a high degree of bug finding capabilities.

So, first as I mentioned before, there's Address Sanitizer.

Now, Address Sanitizer catches memory corruption bugs like buffer overflows and use-after-free bugs.

And these ones are highly correlated with security vulnerabilities.

Then there's Thread Sanitizer, which catches data races.

So, in your multithreaded app, if two threads tried to access the same piece of memory without proper synchronization, you have a data race.

But a cool thing about Thread Sanitizer is that it catches even potential data races.

So, even if in your execution of the app everything seems to be working great, Thread Sanitizer can tell you if two operations could potentially happen in a different order and cause your app to misbehave.

And new in Xcode 9 is the Undefined Behavior Sanitizer.

It catches over 15 different types of undefined behavior and it extends either Address Sanitizer or Thread Sanitizer so you get even more bug-finding power.

So, some of these types of undefined behavior that it catches include assigned integer overflows and tightness match bugs, which are also somewhat related to security vulnerabilities in some contexts.

All of the sanitizers provide you with really rich and informative diagnostics that help you hone in on the root cause of a bug.

You can find a lot of really helpful information in the Runtime Issue Navigator such as stack backtraces at important parts during the bug's execution.

So, we recommend turning on the sanitizers during development.

You can do this in the scheme editor under the diagnostics tab.

And this is where you can also turn it on for running your unit tests.

And remember that the sanitizers need good code coverage in order to find bugs throughout your program, and that's something that your unit test can provide.

You can learn more about the sanitizers and other Runtime tools that are new this year in Xcode at the Finding Bugs Using Xcode Runtime Tools talk.

So, those are five powerful tools that you have at your disposal to track down undefined behavior and address some of the security vulnerabilities that they may create.

But before moving on, there's one more thing that I wanted to talk about, which is the language itself.

So, you can think of your use of the language as your first line of defense in writing safe and secure code.

And so with that in mind, you should prefer the safe constructs that your library and your language provide to you.

For instance, automatic reference counting in Objective C.

Or smart pointers in C++ free you from the burden of having to do a lot of the manual memory management that results in bugs.

And if your standard library provides you with container classes like NSarray from foundation, which check their bounds automatically, you don't have to worry so much about buffer overflows.

But it's just key to understand the tradeoffs that your language is making when it comes to safety and security.

And when these are very important factors in your code, consider using SWF, a language that was designed from the ground up to eliminate entire categories of undefined behavior.

And to tell you more about that, I'd like to invite up my colleague, Anna.

[ Applause ]

Thank you, Ryan.

Now let's talk about undefined behavior and SWF.

While you can write code fine-tuned for performance in SWF, this language makes different tradeoffs and was designed to be much safer by default.

As you've seen from the previous examples, undefined behavior can introduce very subtle bugs that in turn could lead to security exploits.

And this is simply summarized in this code from SWF.org.

Undefined behavior is the enemy of safety.

Safety in SWF is important on many levels.

Let's see how some of the major sources of undefined behavior that Ryan and Fred talked about are addressed in SWF using different techniques.

The stricter type system gives us optional types, which statically prevent null point of dereferences.

Use of an initialized variables is eliminated by guarantee of definite initialization.

Buffer and integer overflows are checked at runtime and just like in Objective C, automatic reference counting is the SWF answer to use after freeze as it allows the developer not to focus on manual memory management issues.

So, let's look into some of this in more detail.

Optional types is SWF answer to null point of dereferences.

SWF has two kinds of types.

Here we have a nonoptional cake and an optional cake, which you can think of as a box that may have a cake in it or might be empty.

Now, as SWF tools, I can assure you a bug that may have a cake in it is definitely not the same thing as this delicious triple chocolate delight.

So, before using a value of optional type, you need to check for it.

Suppose we have a function called receive package that is declared to return an optional cake type.

Don't jump for joy unless you check and know for sure that it will not return nil.

It's possible the cake is a lie.

Note that SWF's syntax provides affordances for easy checking of optional types, specifically to lessen the burden of using this types on the developer.

Another important reminder is that you should not abuse the fourth unwrap operator, which will stop execution of the program if the value is nil.

If the API has been declared to return an optional, it means that it might return nil so check for it.

Now, the fourth unwrap should only be used in rare cases when you, the developer, know for sure and can guarantee that the return value is never nil.

However, that cannot be encoded in the type system.

One example of that is when you're loading an image asset from the app bundle.

SWF also has a notion of implicitly unwrapped optional type.

This type is similar to optional.

However, here the compiler does not enforce that the values are used before, the values are checked before use, making no compile time guarantees.

However, note that this type is still much safer than the C pointer type because using it is defined behavior.

If the value's nil, the program is guaranteed to stop execution, making this model much more secure.

Now, this type should be used for properties that are guaranteed to have a value.

However, they cannot be initialized in the constructor.

Some of you might be using it for IB outlets.

However, another source of implicitly unwrapped optionals are pointered types coming from Objective C and C APIs.

And this source subverts the type safety of SWF optionals.

So, what can we do here?

At the time SWF was released, we've also added nullability annotations to the Apple LLDM compiler.

This annotation in C languages communicate the intent of the APIs but are also used to enhance their SWF interfaces.

They allow us to map the unsafe C pointers onto the optional types.

Let's look at this example.

Here we have ancestor shared with view method on NSview.

As you can see here, it takes a non-null argument because it does not make sense to look for an ancestor between a nil and a value.

On the other hand, its return value is nullable because it's possible the two views do not have the same ancestor.

Now, as you can see here, nullability directly maps onto the SWF interface.

Non-null maps into the nonoptional value and nullable is mapped to the optional value.

Good news is that most Apple APIs have been audited and annotated with nullability annotations.

However, if you have APIs or just C or Objective C code that interoperates with SWF, you too can benefit from these annotations.

In addition, you can use tools such as the [inaudible] Static Analyzer, Warnings, and Undefined Behavior Sanitizer to find inconsistencies of how this these annotations are applied on your C code or Objective C code.

Now, I really, really like this example because it highlights how the improvements to the LLDM compiler, the SWF compiler, and the frameworks work all together to benefit the whole ecosystem.

SWF definite initialization is a diagnostic feature based on deep code analysis.

The SWF compiler guarantees that values are initialized before they are being used.

And this checking is done along all branches through your program.

Let's look at this example.

Here, the compiler will check that my instance is initialized on both the if and the else branch of this code snippet before it allows you to go on and use this value.

Now, let's talk about buffer and integer overflows, which are the biggest sources of security issues.

Overflows only raise an integer and SWF terminate the execution of the program.

You might ask this question.

Why is Runtime checking good?

Well, while your program will still stop if you have a bug and your buffer overflows, this behavior is much better than the alternative.

The behavior in SWF is much more consistent and debuggable than what you get in C and most importantly, it gives very high security guarantees.

The buffer overflow is not exploitable.

It will not lead to the attacker getting execution control of your program.

Note that if you need to use integer-wrapping behavior, you can still do it using overflow operators, which are also safe and just perform modular arithmetic.

Now, a question a lot of you might be thinking about now is does undefined behavior exist in SWF?

And the answer is yes, but this case is much rarer and often we know that we are opting into unsafe behavior.

So, for example we needed C interoperability.

So, we needed to traffic in these types.

Unsafe pointer, unsafe mutable raw buffer pointer.

Note that you can tell that these types are unsafe by just looking at their names.

So, if your applications use C or Objective C or otherwise they're using these types, I highly recommend using Address Sanitizer too.

It will find memory corruptions that this unsafety could bring to your code.

Now, another example of unsafety in SWF are simultaneous accesses.

And SWF is nailing the model down in this release with enforcement of exclusive memory access.

Let's look at a very simple example to understand what this is all about.

So, here we have a function that takes two in out arguments.

In out means that the function may change the value of these arguments.

Calling this function and passing it two values that point to the same memory could result in unpredictable behavior.

For those of you who are familiar with restrictive work in C, this is very similar.

But in SWF, this behavior is on by default.

Now, this one, this is a very simple and abstract example of this problem.

However, I highly encourage you to watch Watch New in SWF talk for more examples of how this could be visible in your code and how it relates to your code.

So, to address this problem, SWF could have chose to declare this to be undefined behavior.

However, instead it decided to follow its mantra, that undefined behavior is the enemy of safety and implement solutions in the language that provide stronger guarantees.

Coming up with the right solution here is a balancing act.

It's best to diagnose everything statically but often that's not possible without making the type system too difficult to use.

Another solution are Runtime checks.

However, the language Runtime has to be performant.

And efficient.

And the overhead of any extra checking cannot be too high.

So, the solution that the SWF Project came up with consists of tightening the language to follow a slightly stricter rule and using a combination of static and dynamic checks to ensure that unintended sharing does not happen within the same thread.

Unfortunately, checking for exclusivity of accesses across threads is too expensive.

And the tradeoff that was made here was to rely on tools, specifically Thread Sanitizer, to catch violations involving accesses from multiple threads.

In general, using Thread Sanitizer is very beneficial for your SWF code because data races and access races are undefined behavior in SWF and they could lead to memory corruptions.

For more information about this tool, watch the Finding Bugs Using Xcode Runtime Tools talk.

Now, safety is a design choice in SWF.

The language provides many solutions to avoid undefined behavior and prevent developers from introducing subtle and exploitable bugs.

Today we talked about undefined behavior and how different languages approach it.

C languages use undefined behavior for portability and optimizations.

However, we've seen that that could lead to very subtle and hard to debug bugs and even introduce security exploits.

SWF chose to follow a different path and was designed to be safer by default.

Finally, regardless of your language of choice, use all the tools at your disposal as part of your app release and testing process.

That will make your apps more secure and robust.

Here are some of the related sessions that we've mentioned today.

Thank you very much and enjoy the rest of your day.

[ Applause ]

Apple, Inc. AAPL
1 Infinite Loop Cupertino CA 95014 US