Undefined Integer Behaviors in Student Code, Part 1

[This post is based on material from Chad Brubaker, a really smart CS undergrad at Utah who did all the work getting these data. The integer undefined behavior checker was created by my student Peng Li.]

Integer undefined behaviors in C/C++, such as INT_MAX+1 or 1<<-1, create interesting opportunities for compiler optimizations and they also make programming in C/C++ not unlike crossing a minefield while blindfolded. This piece describes the results of running a checker for integer undefined behaviors on code submitted by several years’ worth of students in Utah’s CS 4400. The checker simply inserts checking logic in front of any potentially-undefined operation. Then, we ran each student’s code on the same inputs used by the test harness the students were given as part of the assignment. CS 4400 is based on Computer Systems: A Programmer’s Perspective, by Bryant and O’Hallaron. It’s great textbook and I think students get a lot out of the course. I taught it three times in the early/mid 2000s and others have taught it since then.

The assignment is to write C code solving various small “bit puzzles.” Each solution must be straight-line code and can only use C’s bitwise operators: ! ~ & ^ | + << >>. There are a few additional restrictions that are specific to individual problems, such as limiting the number of operations and further restrictions on operator choice.

Students are given reference solutions for the bit puzzles (written in C, but using loops and otherwise not following the rules) and also they are given a harness that runs their code against the reference solutions on some fixed test vectors.

The results below divide students’ solutions into four bins:

  • correct results and no undefined behavior
  • wrong results (for at least one input) and no undefined behavior
  • correct results but contains undefined behavior (for at least one input)
  • wrong results and contains undefined behavior

The most interesting case is where code gives the right answers despite executing undefined behaviors. These solutions are basically just lucky. In other words, the version of GCC installed on our lab machines, at the optimization level specified by the makefile, happens to have a particular behavior. But even the same code, on the same compiler, using the same optimization options, could break if called from a different context.

get_least_significant_byte

Extract the least significant byte from an int.

correct wrong
no undefined 105 0
undefined 0 0

is_equal

Return 1 if two ints are equal, and zero otherwise (note that == is not an allowed operator).

correct wrong
no undefined 97 0
undefined 8 0

All of the undefined behaviors were overflow of signed addition.

any_even_one

Return 1 if any even bit of an int is set, otherwise return 0.

correct wrong
no undefined 102 3
undefined 0 0

clear_all_but_lower_bits

Clear all but the N least significant bits of an int.

correct wrong
no undefined 67 1
undefined 34 3
  • 16 solutions contained signed addition overflows
  • 4 contained a signed right-shift by negative or past bitwidth
  • 17 contained a signed left-shift by negative or past bitwidth

rotate_right

Rotate the bits in an int to the right.

correct wrong
no undefined 7 3
undefined 87 8
  • 2 overflowed a signed addition
  • 8 contained an unsigned left-shift by negative or past bitwidth
  • 7 contained an unsigned right-shift by negative or past bitwidth
  • 8 contained a signed right-shift by negative or past bitwidth
  • 70 contained a signed left-shift by negative or past bitwidth

indicate_rightmost_one

Generate an int with a single set bit corresponding to the rightmost set bit in another int.

correct wrong
no undefined 1 11
undefined 93 0

93 solutions overflowed a signed addition — only a single student managed to avoid this problem and also return the right answers

divide_by_four

Divide an int by four, rounding towards zero.

correct wrong
no undefined 94 8
undefined 0 3

3 solutions overflowed a signed addition

fits_n_bits

Return 1 if a value can be represented as an N-bit 2’s complement integer.

correct wrong
no undefined 79 12
undefined 10 4
  • 9 solutions overflowed a signed addition
  • 2 solutions contained a signed right-shift by negative or past bitwidth
  • 3 solutions contained a signed left-shift by negative or past bitwidth

This puzzle was interesting because it was the only one where we found undefined behavior in the reference solution, which executes this code to compute the largest representable integer:

tmax_n = (1<<(n-1)) - 1;

1<<31 evaluates to 0x80000000, which is INT_MIN on a machine where int is 32 bits. Then, evaluating INT_MIN-1 is an operation with undefined behavior.

Moreover, in C99, evaluating 1<<31 is undefined.

is_greater

Return 1 if one int is larger than another, and zero otherwise.

correct wrong
no undefined 4 11
undefined 84 6

90 solutions overflowed a signed addition

subtract_overflows

Return 1 if subtracting one int from another overflows, and zero otherwise.

correct wrong
no undefined 0 13
undefined 89 3

92 solutions overflowed a signed addition — nobody avoided this hazard

What’s the Problem?

The problem is that a large fraction of our junior-level CS undergraduates are producing code that executes integer undefined behaviors. At best, this kind of code is not portable across compilers, platforms, or even changes in compiler version, optimization options, or calling context. At worst, undefined behaviors are time bombs that will lead to exploitable vulnerabilities or other serious malfunctions in software systems. I want our graduates to understand what undefined behavior means and how to avoid it, not because C/C++ programming is so great, but because the concepts are much more broadly applicable.

What’s the Solution?

Fixing the problem in the context of Utah’s CS 4400 course should be straightforward:

  • Include some lecture material on undefined behaviors
  • Make Peng’s undefined behavior checker part of the test suite that students are given as part of the assignment; since it gives nice clear error messages, the output should be directly actionable

I’ll see if Erin, the current instructor, is interested in working with me to implement this for Fall 2011. We’ll see how it goes.

[Note: I’ve deliberately left code solving the bit puzzles out of this post, and I will reject any comments containing solutions.]

6 Replies to “Undefined Integer Behaviors in Student Code, Part 1”

  1. So CS students, specifically aware of the pitfalls of C bit operations, could not produce correct code to implement very, very elementary operations?

    Instead of blaming this on the students’ ignorance, maybe this indicates that something is wrong with C semantics.

  2. Hi David,

    It’s not at all clear that the students are aware of these pitfalls.

    Anyway, C and C++ obviously represent pretty extreme design points, but many programming languages and library interfaces have similar “features.” The general concept that you can’t always just do anything that is syntactically permitted is a useful one for students to internalize.

  3. John,

    Is Peng’s undefined behavior checker available? It would be useful for me when combing through the gcc test suite to double check my tool for which ones overflow (there seems to be quite a few).

    And I have to ask, any news on when Csmith might be available? 🙂 I’m more than happy to work with an unpolished tool and could offer feedback. At this point I’m running out of test cases.

  4. David, let me try to give a slightly more nuanced answer.

    The first group of people to blame is us: the instructors. We haven’t educated the students about undefined behaviors. This will be fixed.

    The C language and its tools are also to blame, by making undefined behaviors silent. We’ll fix this too, by giving them the tools I have described.

    The 4400 students are not to blame: we’ve given them neither the information nor the tools they would need to write well-behaved C code.

    On the other hand (a post describing this in more details is in the works) in a different class I gave an entire lecture on undefined behaviors and also the class was forced to use an undefined behavior checking tool. And still, much of the class gave me code (for a really simple assignment) containing undefined behaviors.

Comments are closed.