GotW #102 Solution: Assertions and “UB” (Difficulty: 7/10)

This special Guru of the Week series focuses on contracts. Now that we have considered assertions, postconditions, and preconditions in GotWs #97-101, let’s pause and reflect: To what extent does a failed contract imply “UB”… either the Hidden Dragon of Undefined Behavior, or the Crouching Tiger of Unspecified Behavior?

1. Briefly, what is the difference among:

(a) undefined behavior

Undefined behavior is what happens when your program tries to do something whose meaning is not defined at all in the C++ standard language or library (illegal code and/or data). A compiler is allowed to generate an executable that does anything at all, from data corruption (objects not meeting the requirements of their types) to injecting new code to reformat your hard drive if the program is run on a Tuesday, even if there’s nothing in your source code that could possibly reformat anything. Note that undefined behavior is a global property — it always applies not only to the undefined operation, but to the whole program. [1]

(b) unspecified behavior

Unspecified behavior is what happens when your program does something for which the C++ standard doesn’t document the results. You’ll get some valid result, but you won’t know what the result is until your code looks at it. A compiler is not allowed to give you a corrupted object or to inject new code to reformat your hard drive, not even on Tuesdays.

(c) implementation-defined behavior

Implementation-defined behavior is like unspecified behavior, where the implementation additionally is required to document what the actual result will be on this particular implementation. You can’t rely on a particular answer in portable code because another implementation could choose to do something different, but you can rely on what it will be on this compiler and platform.

2. For each of the following, write a short function … where if the assertion is not checked and is false then the effect:

(a) is always undefined behavior

Easy peasy! Let’s dereference a null pointer:

// Example 2(a): If assert is violated, always undefined behavior

void deref_and_set( int* p ) {
    assert( p );
    *p = 42;
}

The function asserts that p is not null, and then on the next line unconditionally dereferences p and scribbles over the location it points to. If p is null and the assertion checking is off so that we can get to the next line, the compiler is allowed to make running the whole program format our hard drive.

(b) possibly results in undefined behavior

A general way to describe this class of program is that the call site has two bugs: first, it violates a precondition (so the callee’s results are always at least unspecified), and then it additionally then uses the unspecified result without checking it and/or in a dangerous way.

To make up an example, let’s bisect a numeric range:

// Example 2(b): If assert is violated, might lead to undefined behavior

int midpoint( int low, int high ) {
    assert( low <= high );
    return low + (high-low)/2;
        // less overflow-prone than “(low+high)/2”
        // more accurate than “low/2 + high/2”
}

The author of midpoint could have made the function more robust to take the values in either order, and thus eliminated the assertion, but assume they had a reason not to, as alluded to in the comments.

Violating the assertion does not result in undefined behavior directly. The function just doesn’t specify (ahem!) its results if call sites call it in a way that violates the precondition the assertion is testing. If the precondition is violated, then the function can add a negative number to low. But just calculating and returning some other int is not (yet) undefined behavior.

For many call sites, a bad call to midpoint won’t lead to later undefined behavior.

However, it’s possible that some call site might go on to use the unspecified result in a way that does end up being real undefined behavior, such as using it as an array index that performs an out-of-bounds access:

auto m = midpoint( low_index(arr1), high_index(arr2) );   // unspecified
   // here we expect m >= low_index(arr1) ...
stats[m-low_index(arr1)]++;                 // --> potentially undefined

This call site code has a typo, and accidentally mixes the low and high indexes of unrelated containers, which can violate the precondition and result in an index that is less than the “low” value. Then in the next line it tries to use it as an offset index into an instrumentation statistics array, which is undefined behavior for a negative number.

GUIDELINE: Remember that an unspecified result is not in itself undefined behavior, but a call site can run with it and end up with real undefined behavior later. This happen particularly when the calculated value is a pointer, or an integer used as an array index (which, remember, is basically the same thing; a pointer value is just an index into all available memory viewed as an array). If a program relies on unspecified behavior to avoid performing undefined behavior, then it has a path to undefined behavior, and so unspecified behavior is a Crouching Tiger, if you will… still dangerous, and can be turned into to the full dragon.

GUIDELINE: Don’t specify your function’s behavior (output postconditions) for invalid inputs (precondition violations), except for defense in depth (see Example 2(c)). By definition, if a function’s preconditions are violated, then the results are not specified. If you specify the outputs for precondition violations, then (a) callers will depend on the outputs, and (b) those “preconditions” aren’t really preconditions at all.

While we’re at it, here’s a second example: Let’s compare pointers in a way the C++ standard says is unspecified. This program attempts to use pointer comparisons to see whether a pointer points into the contiguous data stored in a vector, but this technique doesn’t work because today’s C++ standard only specifies the results of raw pointer comparison when the pointers point at (into, or one-past-the-end of) the same allocation, and so when ptr is not pointing into v’s buffer it’s unspecified whether either pointer comparison in this test evaluates to false:

// Example 2(b)(ii): If assert is violated, might lead to undefined behavior

// std::vector<int> v = ...;
assert(&v[0] <= ptr && ptr < (&v[0])+v.size());           // unspecified
*ptr = 42;                                  // --> potentially undefined

(c) is never undefined or unspecified behavior

An assertion violation is never undefined behavior if the function specifies what happens in every case even when the assertion is violated. Here’s an example mentioned in my paper P2064, distilled from real-world code:

// Example 2(c): If assert is violated, never undefined behavior
//               (function documents its result when x!=0)

some_result_value DoSomething( int x ) {
    assert( x != 0 );
    if    ( x == 0 ) { return error_value; }
    return sensible_result(x);
}

The function asserts that the parameter is not zero, to express that the call site shouldn’t do that, in a way the call site can check and test… but then it also immediately turns around and checks for the errant value and takes a well-defined fallback path anyway even if it does happen. Why? This is an example of “defense in depth,” and can be a useful technique for writing robust software. This means that even though the assertion may be violated, we are always still in a well-defined state and so this violation does not lead to undefined behavior.

GUIDELINE: Remember that violating an assertion does not necessarily lead to undefined behavior.

GUIDELINE: Function authors, always document your function’s requirements on inputs (preconditions). The caller needs to know what inputs are and aren’t valid. The requirements that are reasonably checkable should be written as code so that the caller can perform the checks when testing their code.

GUIDELINE: Always satisfy the requirements of a function you call. Otherwise, you are feeding “garbage in,” and the best you can hope for is “garbage out.” Make sure your code’s tests includes verifying all the reasonably checkable preconditions of functions that it calls.

Writing the above pattern has two problems: First, it repeats the condition, which invites copy/paste errors. Second, it makes life harder for static analysis tools, which often trust assertions to be true in order to reduce false positive results, but then will think the fallback path is unreachable and so won’t properly analyze that path. So it’s better to use a helper to express the “either assert this or check it and do a fallback operation” in one shot, which always avoids repeating the condition, and could in principle help static analysis tools that are aware of this macro (yes, it would be nicer to do it without resorting to a macro, but it’s annoyingly difficult to write the early return without a macro, because a return statement inside a lambda doesn’t mean the same thing):

// Using a helper that asserts the condition or performs the fallback

#define ASSERT_OR_FALLBACK(B, ACTION) { \
    bool b = B;                         \
    assert(b);                          \
    if(!b) ACTION;                      \
}

some_result_value DoSomething( int x ) {
    ASSERT_OR_FALLBACK( x != 0, return error_value; );
    return sensible_result(x);
}

3. Explain how your answers to Questions 1 and 2 do, or do not, correspond with each other.

In Example 2(a), violating the assertion leads to undefined behavior, 1(a).

In Example 2(b), violating the assertion leads to unspecified behavior, 1(b). At buggy call sites, this could subsequently lead to undefined behavior.

In Example 2(c), violating the assertion leads to implementation-defined behavior, 1(c), which never in itself leads to  undefined behavior.

4. BONUS: Describe a valuable service that a tool could perform for assertions that satisfy the requirement in 2(a), that is not possible for other assertions.

There are many. Here is just one example, that happens to be nice because it is perfectly accurate.

Let’s say we have all the code examples in question 2, written using C assert today (or even with those assertions missing!), and then at some future time we get a version of standard C++ that can express them as preconditions. Then only in Example 2(a), where we can see that the function body (and possibly transitively its further callees with the help of inlining) exercises undefined behavior, a tool can infer the precondition annotation and add it mechanically, and get the benefit of diagnosing existing bugs at call sites:

// What a precondition-aware tool could generate for Example 2(a)

auto f( int* p ) 
    [[pre( p )]]  // can add this automatically: because a violation
                  // leads to undefined behavior, this precondition
                  // is guaranteed to never cause a false positive
{
    assert( p );
    *p = 42;
}

For example, after some future C++2x ships with contracts, a vendor could write an automated tool that goes through every open source C++ project on GitHub and mechanically generates a pull request to insert preconditions for functions like Example 2(a) – but not (b) or (c) – whether or not the assertion already exists, just by noticing the undefined behavior. And it can inject those contract preconditions with complete confidence that none of them will ever cause a false positive, that they will purely expose existing bugs at call sites when that call site is built with contract checking enabled. I would expect such tool to identify a good number of (at least latent if not actual) bugs, and be a boon for C++ users, and it’s possible only for functions in the category of 2(a).

“Automated adoption” of at least part of a new C++ feature, combined with “automatically identifies existing bugs” in today’s code, is a pretty good value proposition.

Acknowledgments

Thank you to the following for their comments on this material: Joshua Berne, Gabriel Dos Reis, Gábor Horváth, Andrzej Krzemieński, Ville Voutilainen.

Notes

[1] In the standard, there are two flavors of undefined behavior. The basic “undefined behavior” is allowed to enter your program only once you actually try to execute the undefined part. But some code is so extremely ill-formed (with magical names like “IF-NDR”) that its very existence in the program makes the entire program invalid, whether you try to execute it or not.

10 thoughts on “GotW #102 Solution: Assertions and “UB” (Difficulty: 7/10)

  1. Can you explain how “midpoint” can lead to undefined behavior if low and high are swapped? My reading of the math is that the result is always defined.

    For example:

    Midpoint (10,20) -> 10+((20-10)/2) -> 15
    Midpoint (20,10) -> 20+((10-20)/2) -> 15

  2. (not sure how to answer comments here)
    @Joshua, this code can underflow, which is undefined behavior for signed integers. For example, if low is std::numeric_limits::max() and high is std::numeric_limits::min() then the (high – low) part will underflow.

  3. Maybe that example was just taken for the reason to show an easy to understand example, ok, but IMO it is a very bad example. C++ is better than that and doesn’t even need a `[[pre]]`, at least not for this example:

    auto f(int* p) [[pre( p )]] { … }

    Much better interface is:

    auto f(int& r) { … }

    Less writing, less error prone, self explaining interface, no precondition needed, no `assert` needed, the language has been good enough to handle that mistake since ever.

  4. @Joshua Lehrer

    There’s a whole talk on std::midpoint by Marshall Clow (I think I spelled that right?) at one of the C++ cons. It’s on YouTube, so if you put the appropriate words into the YT search, I’m sure you’ll find it.

    It’s very interesting and insightful as to just how complex these seemingly simple things can be.

  5. The truly frustrating thing about P2064 is how narrowly focused the compiler writers are on optimization at the expense of warnings.

    Optimizations arising from an Assume should purely be regarded as a second order “nice to have”.

    What I really care about are warnings that indicate the optimizer has spotted either….
    * A path by which the assumption may be false OR…
    * Code downstream of the Assume that is unreachable if the assumption holds OR
    * Upstream Code paths that can be inferred to be dead if the Assumption holds when it is reached OR
    * A missing Assume on the function preconditions required for the Assume downstream to always hold.

    THAT IS WHAT MATTERS!

    We want the compiler and optimizer to check our assumptions!

    Not optimizations!

    The optimizer implicitly has a lot of this knowledge which makes it the entity capable of creating these warnings.

    Once we have confidence in our assumptions… we may want to turn the assumptions into “check and die” and there after assume true if the optimizer cannot prove the assumption is true, or simply elide them and rely on them if it can.

    The MSVC story is also frustrating. Clearly the meaning of the facility was not well understood and agreed by the various programmers on the team. This very common. I have often encountered substantial disagreement on the meaning and purpose of these assert like facilities.

    However, it’s the entire point of standardization is define the meaning and purpose.

    And if there are multiple meanings and purposes then the standards committee should be clearly and unambiguously defining the meaning and purpose, even if it requires creating more than one facility to cover the required use cases.

  6. @Marco:
    auto f(int &r) is a _different_ function.
    While in a vacuum, the “f(int &r)” seems perfect, it won’t work if you actually receive the integer from somewhere else as a “pointer to integer”.
    Even working “C++ only”, you are sometime forced to interface to “C-only” headers/libraries, for which parameter passing by reference is impossible.
    The “auto f(int *p)” function will probably simply be the bridge/adapter/… to a C-style header – and, as “external” code to your own project, it should be under strict scrutiny (i.e. parameter/return values checking)

  7. @Calin: I see what you mean, but if it were a bridge/adapter/… to a C-style header, then the `[[pre]]` is just wrong because in exactly this situation there absolutely must be a runtime check `if(p) { … }`.

    Anyway, in the post was an example to show a new keyword of the language. I wrote my comment because from my experience examples should not just be good for a very narrow context, but perfect in all aspects, because examples are meant to be educational and tend to be copy/pasted. Every other day I have discussions with others who watch all the videos about good programming practices and see all these limited examples. The big picture in applications with millions of lines of C++ code is never considered when showing these small code snippets. You see what I mean, too?

  8. Thanks for your article.

    For tools part that can help to identify and possibly inject code to prevent UB or maybe some Unspecified behavior is a good point. But I think a tool has to be a helper for the programmer not a decider where to inject a code. In my opinion, It’s better to such a tool generate temp file containing this injections and the programmer can check and finally decide if it can keep this code or make some change and later relaunch again that tool to verify again. I think letting the programmer to decide what final state of his code can be is also a good point because it let the programmer to master the final state of the code.

    I think Mastering the behavior of your code (at least if no UB) is really important.

  9. > In my opinion, It’s better to such a tool generate temp file containing this injections and the programmer can check and finally decide if it can keep this code or make some change and later relaunch again that tool to verify again.

    I think that it should rather generate a patch file. With a decent editor you can apply only the parts that you like.

  10. Re question 4, “[…] it can inject those contract preconditions with complete confidence that none of them will ever cause a false positive, that they will purely expose existing bugs at call sites when that call site is built with contract checking enabled”: or expose existing bugs in the called function’s implementation, but unhelpfully turning those implementation errors into bogus preconditions

Comments are closed.