More on unsafe C strings: A followup

Recently John Carmack, lead programmer of DOOM, wrote in a tweet: “Considering that 8 bit BASICs of the 70s had range checked and garbage collected strings, it is amazing how much damage C has done”. This is in line with my previous posts, and it's fairly remarkable that C stuck around so long without having this fixed. There have been many updates to the language, but this issue was simply not addressed — at least, not until C11. C11 includes the strcpy_s() and strcat_s() safe string functions. It feels a bit too little, too late but, at last, something has been done about it.

Are our troubles over now? Not really, C11 is still too new. My system does not have the new safe string functions so I can't use them. Adoption of the new standard takes time. Documentation (and school books) have to be updated. Next, the old strcpy() and strcat() have to be deprecated and finally, be eradicated from our source codes.

The bounds checking problem continues to exist for arrays.

Other than C11 I want to expand on two other possibilities for fixing the issue. The first solution is using an external library, the second is choosing a different programming language.

1. Using an external library

Rather than just supplying a safe string copying function, I mean using a library that supplies a safe string type and associated functions. As is often the case, this library would be written in C itself. One problem is that you have to rigorously adapt to using the library's string functions, and resist the temptation of using the old char* pointers for quick and dirty strings anyway.

Another problem is that system functions such as open(), write(), etcetera expect char* pointers, so you keep converting between the safe string type and the char* pointer.

Typical library solutions allocate strings on the heap, giving an extra performance hit. Using a library means marrying that library; your whole program source code will look different and be tightly coupled to it. Switching libraries will have a big impact and involve lots of work.

My github project liboco is a C library that implements a safe string type, as well as an array and a map type, and a few other things. It follows the Objective-C design principle that everything is a reference counted object. Like in Objective-C, this means manual reference counting. It isn't bad, but can be problematic if you are not used to it. Hard to track down memory leaks may happen. Other than that, liboco is pretty neat.

Comparably, I have written oolib for C++ which is much easier to use because it does automatic reference counting under the hood. This brings us to the next point.

2. Choosing a different programming language

It is fair to say that the problem of unsafe strings and having no bounds checks is intrinsic to C. It is a low-level language, after all. So if you want that extra bit of safety, you have to let go of C and choose a different language.

C++ fixes strings with std::string. Its interface annoys me, but anyway, C++ is a complicated language and it's really hard to learn. Even after thoroughly studying C++ I'm not sure I would recommend the language to anyone. Sure, classes are useful, but you almost have to be an academic to master C++.

Other languages more popular than C on github are: PHP, Python, Java, JavaScript — all byte code interpreted languages. JavaScript is a total mess, but anyway, these languages by design lack the punch that C can deliver in terms of performance. The process of byte code interpreting is essentially emulation, and emulation is slow. I bet that even the laziest, dumbest compiler would produce a faster running code than these byte code interpreters.
The argument of performance appears debatable, “do you really need that kind of performance?” The answer, in short, is: Yes. I have personally seen scripts run for hours, where the equivalent written in C ripped through it in half a minute. A speedup by a factor of 100 is no exception. Compiled languages offer vastly superior performance.

There is Objective-C, but it is different enough to say it changes everything. Choosing Objective-C in practice means marrying OpenStep's Foundation Kit. It is a good choice if you are Apple-only and intend to keep it that way. Objective-C has manual reference counting, which is alright but kind of tough to get right. Apple's compiler however, sports automatic referencing counting (ARC) which does some clever source code analysis.

Whatever happened to Pascal? Although a rather verbose language (consider PROCEDURE / BEGIN / END versus void { }), Pascal wasn't so bad — except from the fact that it has the worst string type of all (!). Although Pascal strings are safe, they have an absolute maximum length of 255 bytes. In modern times, with unicode encoding, this means that for some languages only 63 characters can be stored in a single Pascal string, making it a totally useless language by today's standards.

Go deserves honorable mention. It is an easy to learn language with cool core features, and it compiles to native code. Even though I'm not fond of its mandatory CamelCasing, golang is really great. Go was designed as a systems programming language, and it shows. There are some Plan9 peculiarities like the command-line flags parser not being GNU getopt()like, and the tar archiving module doesn't grok GNU tar extensions. Other than that, Go has great potential.

Truthfully, I don't want a language that strays too far from C. Interestingly, although many modern languages are depicted “C like”, none of them are plain C with an added safe string type. I suppose it is hard to change C. For one thing, a ‘string’ is a fairly high-level concept that doesn't fit nicely in a low-level language.

strcpy(): The safety of an unsafe string copy function

Last time I wrote about the strcpy() function and said that it's unsafe. But why exactly is it unsafe? Let us see the details of what is going on under the hood when strcpy() is called. To do so, we will dive down to the machine level and have a look at what is happening in the stack memory.

In the C language, strings have no explicit length. Instead, the length is determined by a terminating NUL character. Therefore, strcpy() copies bytes until it sees a zero byte:

 void strcpy(char *dst, char *src) {
     /* copy src to dst until src[0] == 0 */
     while(*src)
         *dst++ = *src++;
 }

Consider the following function, which includes the common programming mistake of assuming that the input will fit into the buffer:

 void func(char *input) {
    char buf[256];

    strcpy(buf, input);
 }

Now let's examine what happens at the machine level when this baby executes. When a subroutine is called, the CPU pushes the address of the next instruction onto the stack. This address is the return address. To return from a subroutine, the return address is popped off the stack and loaded as the current instruction pointer. Thus the program jumps back and resumes execution at the point right after the subroutine was called. Using a stack allows for nested subroutine calls.

Local variables and function parameters are placed on the stack as well. This is great because now when a subroutine ends, the local variables go out of scope as the stack frame is ‘cleaned up’ (in fact, the data is still there, but the stack pointer is moved).

This amounts to the following picture of a stack frame when we are executing the func:

 stack pointer ->
 +------------------------------+
 | local var:  char buf[256]    |
 |------------------------------|
 |        return address        |
 |------------------------------|
 | parameter:  char *input      |
 |------------------------------|
 | local vars       of caller   |
 |------------------------------|
 | return address   of caller   |
 |------------------------------|
 | parameters       of caller   |
 |------------------------------|
 | ...                          |
 end of stack

You can see that an attacker can overwrite the return address when he supplies an input string that is longer than buf. Not only can he overwrite the return address, he can insert a specially crafted mini-program into buf. What many exploits do is put the return address as the address of buf so that the program will jump back to execute the payload in buf.

To prove that this actually works, we can do a little experiment. Write a small program that fills a buffer with garbage and overwrites the return address as described above. Guess what, it doesn't work! The program gets killed by a run-time check, cleverly inserted by the compiler. Here is a postmortem stack trace:

(gdb) bt
#0  0x00007fff9a45cd46 in __kill ()
#1  0x00007fff9ad98ec0 in __abort ()
#2  0x00007fff9ad5a77d in __chk_fail ()
#3  0x00007fff9ad5aa4f in __strcpy_chk ()
#4  0x0000000100000de4 in func (input=0x7fff5fbff7e0 'x' , "\030??_") at hijack.c:19
#5  0x0000000100000e5e in main () at hijack.c:29

This is in OS X using clang. Googling turns up __memcpy_chk for gcc:

“GCC implements a limited buffer overflow protection mechanism that can prevent some buffer overflow attacks.”

void *
__memcpy_chk (void *__restrict__ dest,
              const void *__restrict__ src,
              size_t len, size_t slen)
{
    if (len > slen)
        __chk_fail ();
    return memcpy (dest, src, len);
}

As you can see, the compiler inserts a run-time check for the size of the buffer. On top of this, a second run-time check is made that checks the integrity of the stack. This technique is known as inserting a ‘stack canary’ and can be observed by studying a disassembly of our func below. Here you can see that 288 bytes (or in hexadecimal notation, 0x120) of space is taken from the stack for local variables. This is more than the 256 we actually requested. The remaining 32 bytes are used for the stack canary.

Then it calls strcpy_chk() rather than strcpy(). Finally, the stack canary is checked, and may result in stack_chk_fail() being called. Otherwise, the stack frame is cleaned up and the function returns normally.

0x0000000100000d90  push   %rbp
0x0000000100000d91  mov    %rsp,%rbp
0x0000000100000d94  sub    $0x120,%rsp
0x0000000100000d9b  mov    0x26e(%rip),%rax
0x0000000100000da2  mov    (%rax),%rax
0x0000000100000da5  mov    %rax,-0x8(%rbp)
0x0000000100000da9  mov    $0x100,%rdx
0x0000000100000db3  lea    -0x110(%rbp),%rax
0x0000000100000dba  mov    %rdi,-0x10(%rbp)
0x0000000100000dbe  mov    -0x10(%rbp),%rsi
0x0000000100000dc2  mov    %rax,%rdi
0x0000000100000dc5  callq  0x100000e8c <__strcpy_chk>
0x0000000100000dca  mov    0x23f(%rip),%rdx
0x0000000100000dd1  mov    (%rdx),%rdx
0x0000000100000dd4  mov    -0x8(%rbp),%rsi
0x0000000100000dd8  cmp    %rsi,%rdx
0x0000000100000ddb  mov    %rax,-0x118(%rbp)
0x0000000100000de2  jne    0x100000df1 <func+97>
0x0000000100000de8  add    $0x120,%rsp
0x0000000100000def  pop    %rbp
0x0000000100000df0  retq  
0x0000000100000df1  callq  0x100000e86 <__stack_chk_fail>

So, the compiler does a lot of work for us in order to prevent simple buffer overflows. The canary is initialized with a random value before main() runs, so it practically can not be defeated. But beware, an attacker may still influence the program behavior in different ways and deliberately not touch the canary.

Other techniques that help prevent buffer overflow attacks are ASLR (address space layout randomization) and DEP (data execution prevention) or NX pages (non-executable memory pages). Although they make it more difficult, these too can be circumvented by trickery.

Mind ye that all of this is plain impossible if only you (or the high-level language itself!) always properly check the size of the buffer and array bounds. It is something that C normally does not do for you, so be mindful that the compiler will not always be able to save you from writing insecure code.

strlcpy(): The unsafety of a safe string copy function

Every C programmer should know that the strcpy() function is insecure; if the destination buffer is too small to hold the string, strcpy() will happily overflow the buffer and copy over whatever was there in memory. Other than corrupting variables, it may overwrite return addresses in stack memory, which spells doom for system security because it allows an attacker to inject code into the running program, commonly known as ‘exploiting a vulnerability.’

Sure enough the strcpy() function is a very dangerous thing. OpenBSD thought up the strlcpy() and strlcat() safe string functions to counter the problem. With these, you always must supply the size of the destination buffer. Strings that are too long will not overflow the buffer, any attempts at buffer overflow are simply stopped. strlcpy() will terminate the copied string at the end of the buffer and thereby plugging the hole.

A remarkably simple but effective solution. The strlcpy() and strlcat() functions are widely used in OpenBSD and were adopted in other operating systems as well, like FreeBSD and Mac OS X. But I wouldn't have known about these functions in the first place if I hadn't run into a code that would not compile on Linux, where strlcpy() is missing from the GNU C library, and maybe righteously so.

However superficially brilliant strlcpy() seems, it is all too easy. The function may truncate the copy of the string, so ... It copies the string, except when it doesn't, then it only partially copies it. Many people consider this incorrect. It isn't logical to have a copy function that truncates the copy. You can get really weird things from this, for example when an UTF-8 string gets truncated in the wrong position, it will result in a corrupted string. What if the string is a file path or a URL that is truncated?
Of course, you should check the return value of the function. It's standard programming practice that also applies to the traditional string handling functions. But in a strange way, these safe string functions are actually unsafe. A false sense of security creeps in. Actually, not copying the string at all would have been better than truncating.

Nevertheless, strlcpy() remains in use in various codes (like OpenSSH and rsync). Wouldn't it be nice if these functions were available just for the sake of portability. In the Linux world, that argument just isn't good enough.

So, what are your options? For portability, you might want to use autoconf and ifdef HAVE_STRLCPY, but note that it doesn't really help you. It's sugar coating that looks advanced, but it doesn't make it any better. My advice is to steer clear of strlcpy(), just don't use it. Stick with the traditional string functions and keep checking those buffer lengths.
You might use an external string library that supports growable strings. Personally, I'm good with my_strcpy() function which is basically strlcpy() with a twist: call abort() when the destination buffer is too small. It's not user-friendly, but it gets you out of a bad situation quickly.
Other than that, accept that C is maybe not the best choice for implementing userland code written by mere mortals. Try a different language, like golang. It has very robust string handling.

Next time we'll have a look under the hood and examine how buffer overflows work.

OpenGL Pac-Man

Every once in a while I like to re-create an arcade classic game just for fun. Many arcade classics are simple enough to be built by a single person with a reasonable amount of spare time. The game of choice is Pac-Man.

When you think about it, Pac-Man is rather bizarre. You are a pill eating yellow mouth that is being chased through a maze by four ghosts. Their mission: KILL THE PAC-MAN! What makes the game fun is that you may temporarily turn the tables by swallowing down a power-pill, after which you can EAT the ghosts. The hunted becomes the hunter. Combined with cutesy graphics it becomes child's play. This is not an easy game though, Pac-Man is notoriously difficult. Personally, I still can't make it past level five.

Programming a Pac-Man clone isn't particularly hard, but it does take effort to perfect it. There are lots of little tweaks and details that make the original so good. For example, the corners in the maze are rounded. This allows Pac-Man to cut corners and stay ahead of the ghosts that are in close pursuit.

Graphics

Rather than using old-fashioned clunky bitmaps, I went for scalable vector graphics so it neatly scales to any screen resolution. Clearly Pac-Man is depicted as a yellow circle with a pizza slice missing. When you do it this way, you'll notice that it doesn't look as nice. The thing is, Pac-Man's mouth is larger than a clean-cut pizza slice. The center of the circle is slightly off, allowing for a bigger mouth. For OpenGL this is not a problem; the Pac-Man character can be drawn as a triangle fan with circle coordinates, but the first vertex is not at the center of the circle.

The ghosts are drawn with a rectangle and a number of circles and ellipses. Drawing ellipses is not easy, but since these are all perfectly symmetrical ellipses they can be drawn as stretched circles: scale the Y direction and draw a circle; the result is a symmetrical ellipse.

A simple trick for drawing circles in OpenGL: calculate the coordinates for a circle with a radius of 1.0. This we call the unit circle. When drawing a circle with radius r, scale X and Y by r and draw the unit circle.

Movement

In the classic Pac-Man game the ghosts move from tile to tile, and so do they in my implementation. But since we're using OpenGL anyway, it wouldn't be a bad choice to use OpenGL's world coordinates instead and move from corner to corner. This would theoretically allow for ultra-high speeds. Come to think of it, maybe it would be nice if the ghosts would accelerate and hit the brakes before taking a corner. This would subtly change the game, however.

In terms of AI, I always thought that the ghosts moved in predetermined patterns, which is not true. Nor do they turn at random. Each ghost has its own behavioural rules. You can read all about it at the Pac-Man Dossier. This page describes the game in enough detail to allow you to create your very own Pac-Man clone.