Arrays and strings · about 55 min

The string library and buffer overflows

Why this matters

Writing every string loop by hand gets old fast, so C provides a library of string functions in <string.h>. They are fast and everywhere, and several of them are also responsible for decades of security holes, because they write into your arrays without knowing how big those arrays are. The Morris worm of 1988, one of the first internet worms, spread through a buffer overflow in a program that used the function gets. This lesson covers the functions you will use every day, and the habits that keep them from writing past the end of a buffer.

The everyday functions

#include <stdio.h>
#include <string.h>

int main(void)
{
    char name[32];
    char greeting[64];

    strcpy(name, "Ada");
    strcat(name, " Lovelace");
    printf("name = \"%s\", strlen = %zu, sizeof = %zu\n", name, strlen(name), sizeof name);

    printf("strcmp(\"apple\", \"banana\") = %d\n", strcmp("apple", "banana") < 0 ? -1 : 1);
    printf("strcmp(\"cat\", \"cat\") = %d\n", strcmp("cat", "cat"));
    printf("strcmp(\"Zebra\", \"apple\") < 0: %s\n", strcmp("Zebra", "apple") < 0 ? "yes" : "no");

    int n = snprintf(greeting, sizeof greeting, "Hello, %s! You are %d.", name, 36);
    printf("%s (%d chars)\n", greeting, n);
    return 0;
}

name = "Ada Lovelace", strlen = 12, sizeof = 32
strcmp("apple", "banana") = -1
strcmp("cat", "cat") = 0
strcmp("Zebra", "apple") < 0: yes
Hello, Ada Lovelace! You are 36. (32 chars)

function	what it does	danger
`strlen(s)`	length, not counting `'\0'`; returns `size_t` (print with `%zu`)	reads past the end if `s` is unterminated
`strcpy(dst, src)`	copies `src` including its terminator into `dst`	writes past `dst` if `src` is too long
`strcat(dst, src)`	appends `src` after the text in `dst`	same, and `dst` must already be a string
`strcmp(a, b)`	compares: 0 if equal, negative if `a` sorts first, positive otherwise	the sign is all that is guaranteed, not -1/1
`strncmp(a, b, n)`	compares at most `n` chars (useful for prefixes)
`strcspn(s, set)`	index of the first char of `s` that is in `set` (or the length if none)
`memcpy(dst, src, n)`	copies exactly `n` bytes	you pick `n`, so you must get it right
`memset(dst, byte, n)`	sets `n` bytes to a value, e.g. zeroing a buffer
`snprintf(dst, size, fmt, ...)`	`printf` into a buffer, never more than `size` bytes, always terminated	none, when `size` is right

size_t is the unsigned integer type C uses for sizes and lengths; sizeof and strlen produce it. Several of these functions also return addresses (for example strchr, which finds a character); those make sense after the pointers module.

What a buffer overflow looks like

strcpy, strcat and scanf("%s") all copy until they reach the end of the source. They never look at the size of the destination, because, as you learned two lessons ago, a function receiving an array gets only its starting address. If the source is longer, they keep writing into whatever memory follows:

#include <stdio.h>
#include <string.h>

int main(void)
{
    int secret = 1234;
    char buf[8];
    char input[100];

    if (scanf("%99s", input) != 1) {
        return 1;
    }
    strcpy(buf, input);              /* no check that input fits in buf! */
    printf("buf = %s, secret = %d\n", buf, secret);
    return 0;
}

$ echo short | ./prog
buf = short, secret = 1234
$ echo abcdefghijk | ./prog
buf = abcdefghijk, secret = 7039593
$ echo abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstu | ./prog
Segmentation fault (core dumped)

Eleven characters plus a terminator is 12 bytes, 4 more than buf holds. In the sandbox's stack layout, secret sat right after buf, so the extra bytes i, j, k and '\0' overwrote it: 7039593 is 0x006b6a69, which is the codes of k, j, i read back as an int (the bytes come out reversed for reasons covered in the bit manipulation module). Nothing reported an error; a variable that the program never touched simply changed. With even longer input, the overflow reached the function's saved return address, and when main tried to return, it jumped into garbage and crashed.

  stack, low addresses on the left (layout as observed in the sandbox):

  before:   buf: [ ? ? ? ? ? ? ? ? ]  secret: [ 1234      ]  ... saved return address ...
  after:    buf: [ a b c d e f g h ]  secret: [ i j k \0  ]  ...
                                               ^ overwritten

An attacker who controls the input controls those bytes. Overwriting a return address with a chosen value is the textbook way to hijack a program, which is why modern systems add defenses (stack canaries, non-executable stacks, address randomization) and why careful code never relies on them.

Detecting overflows

AddressSanitizer pinpoints the line:

$ gcc -g -fsanitize=address -o prog main.c && echo abcdefghijk | ./prog
==19==ERROR: AddressSanitizer: stack-buffer-overflow on address 0x7f8afa300038 ...
WRITE of size 12 at 0x7f8afa300038 thread T0
    #0 0x7f8afc712680 in strcpy ...
    #1 0x562768f76290 in main /work/main.c:13

And glibc's "fortify" checks, enabled with optimization plus -D_FORTIFY_SOURCE=2 (which many Linux distributions turn on for their packages), stop the program at the moment of overflow when the buffer size is known at compile time:

*** buffer overflow detected ***: terminated
Aborted (core dumped)

Safe habits

1. Know the size of every buffer you write into, and pass it. Functions that take a size are the safe ones. sizeof buf gives it when buf is an array in scope; inside a function that received the array, the size must be a parameter.

2. Build strings with snprintf. It replaces most uses of strcpy and strcat:

snprintf(dst, sizeof dst, "%s", src);            /* safe copy */
snprintf(path, sizeof path, "%s/%s", dir, file); /* safe concatenation */

It writes at most size bytes including the terminator, and returns the number of characters the full result would have had. If that is >= size, the output was truncated:

#include <stdio.h>
#include <string.h>

int main(void)
{
    char small[8];
    int n = snprintf(small, sizeof small, "%s", "a rather long string");
    printf("stored \"%s\", wanted %d chars\n", small, n);
    if (n >= (int)sizeof small) {
        printf("output was truncated\n");
    }
    return 0;
}

stored "a rathe", wanted 20 chars
output was truncated

gcc even saw this one coming at compile time: warning: '%s' directive output truncated writing 20 bytes into a region of size 8 [-Wformat-truncation=]. Truncation is not an overflow, but it can still be a bug (a truncated file path names a different file), so check the return value when it matters.

3. Check before strcpy/strcat. They are fine when you have proved the result fits: if (strlen(dst) + strlen(src) + 1 <= size) strcat(dst, src);

4. Be wary of strncpy. Its name suggests "safe strcpy", but if the source is at least n characters long it fills the buffer and writes no terminator. It was designed for fixed-width record fields, not strings.

5. Never use gets. It reads a line with no size limit at all. It was so dangerous that it was removed from the C language in C11; modern compilers refuse it or warn loudly.

Reading lines with fgets

fgets(buf, size, stdin) reads one line, including its '\n', but never more than size - 1 characters, and always terminates buf. It returns NULL at end of input. (NULL means "no address"; for now just compare against it.)

#include <stdio.h>
#include <string.h>

int main(void)
{
    char line[100];
    int number = 0;

    while (fgets(line, sizeof line, stdin) != NULL) {
        line[strcspn(line, "\n")] = '\0';
        number++;
        printf("%2d: [%s] (%zu chars)\n", number, line, strlen(line));
    }
    return 0;
}

$ printf 'first line\n\nthird, longer line\n' | ./prog
 1: [first line] (10 chars)
 2: [] (0 chars)
 3: [third, longer line] (18 chars)

strcspn(line, "\n") is the index of the first newline, or the string's length if there is none (the last line of a file may lack one). Writing '\0' there removes the newline in both cases. If a line is longer than the buffer, fgets returns the first part and the rest on the next call; the missing '\n' is how you can tell.

fgets is the recommended way to read text input. Unlike scanf("%s") it does not stop at spaces, and it can never overflow.

Common mistakes

if (strcmp(a, b)) to test equality. That is true when they differ. Write == 0.
sizeof versus strlen: sizeof buf is the buffer's capacity, strlen(buf) the text's length. Pass capacity to snprintf and fgets; use length to know how much text there is.
strcat on an uninitialized buffer: char out[50]; strcat(out, "x"); searches garbage for a terminator. Start with char out[50] = "";.
Forgetting the + 1 for the terminator when checking whether something fits.
Printing strlen with %d: size_t needs %zu. gcc warns format '%d' expects argument of type 'int', but argument 2 has type 'size_t'.
Leaving the newline from fgets in the string, so strcmp(line, "quit") == 0 never matches "quit\n".

Recap

<string.h> gives strlen, strcpy, strcat, strcmp, strcspn, memcpy, memset.
strcpy, strcat and scanf("%s") do not know the destination size; overflowing a buffer silently corrupts nearby memory and is a classic security hole.
Prefer size-aware functions: snprintf for building strings, fgets for reading lines. Check snprintf's return value for truncation.
strcmp returns 0 for equal. strncpy may not terminate. gets is gone; never use it.
Use -fsanitize=address to find overflows during development.

Going further: man 3 string lists the whole family. Read man 3 snprintf, section RETURN VALUE, and man 3 fgets.

Exercises

Exercise 1 · quiz

What strcmp returns

Which statements about strcmp(a, b) are true? Select all that apply.

It returns 0 when the two strings have the same characters
It returns a negative value when a sorts before b
It returns 1 (true) when the strings are equal, so if (strcmp(a, b)) means "if equal"
It compares character codes, so "Zebra" sorts before "apple"

Answer

It returns 0 when the two strings have the same characters
It returns a negative value when a sorts before b
It compares character codes, so "Zebra" sorts before "apple"

strcmp returns 0 for equal, negative if a < b, positive if a > b, comparing byte by byte by character code. Since 'Z' is 90 and 'a' is 97 in ASCII, every uppercase letter sorts before every lowercase one. The common bug is reading if (strcmp(a, b)) as "if equal": it is true when the strings DIFFER. Write if (strcmp(a, b) == 0) to test equality.

Exercise 2 · quiz

Copying untrusted text

input holds a string typed by a user, of unknown length. You want to put as much of it as fits into char name[16], always ending up with a valid string. Which call does that?

strcpy(name, input);
strncpy(name, input, sizeof name);
snprintf(name, sizeof name, "%s", input);
name = input;

Answer

snprintf(name, sizeof name, "%s", input);

snprintf never writes more than sizeof name bytes and always terminates the result (for a nonzero size), truncating if needed; its return value even tells you how long the full output would have been, so you can detect truncation. strcpy has no size limit at all. strncpy stops at the size but, when the input is 16 chars or longer, leaves name WITHOUT a terminator. name = input does not compile: arrays cannot be assigned.

Exercise 3 · write code

Line lengths and the longest line

Read lines from standard input until end of input using fgets with a char line[256] buffer (no line is longer than 200 characters). For each line, remove the trailing newline and print its length and the line in this format:

<length>: <line>

After the last line, print longest: <line> with the longest line (the first one if several are equally long). If there was no input at all, print nothing.

For the input

hello
a much longer line

end

the output is:

5: hello
18: a much longer line
0: 
3: end
longest: a much longer line

(Note the empty line: 0: is followed by nothing; trailing spaces are not compared.)

File: main.c

Starting point

#include <stdio.h>
#include <string.h>

int main(void)
{
    char line[256];
    char longest[256] = "";

    while (fgets(line, sizeof line, stdin) != NULL) {
        printf("%zu: %s", strlen(line), line);
    }
    return 0;
}

Example

input

hello
a much longer line

end

expected output

5: hello
18: a much longer line
0: 
3: end
longest: a much longer line

Example

input

abc
xyz
ab

expected output

3: abc
3: xyz
2: ab
longest: abc

Hint 1

fgets keeps the '\n' at the end of the line. line[strcspn(line, "\n")] = '\0'; removes it (and does nothing if there is none).

Hint 2

You cannot write longest = line;. Copy the text: snprintf(longest, sizeof longest, "%s", line); or strcpy (safe here because both buffers are the same size).

Hint 3

Use > when comparing lengths, so a later line of equal length does not replace the first. Keep a flag to know whether any line was read.

Reference solution

#include <stdio.h>
#include <string.h>

int main(void)
{
    char line[256];
    char longest[256] = "";
    int any = 0;

    while (fgets(line, sizeof line, stdin) != NULL) {
        line[strcspn(line, "\n")] = '\0';
        printf("%zu: %s\n", strlen(line), line);
        if (!any || strlen(line) > strlen(longest)) {
            snprintf(longest, sizeof longest, "%s", line);
        }
        any = 1;
    }
    if (any) {
        printf("longest: %s\n", longest);
    }
    return 0;
}

Exercise 4 · write code

Append only if it fits

Write

int append(char dest[], size_t size, const char src[])

where dest holds a string inside a buffer of size bytes. If the whole of src fits after the text already in dest (including the terminating '\0'), append it and return 1. Otherwise leave dest completely unchanged and return 0.

Example: with char buf[10] = "abc";, append(buf, sizeof buf, "def") returns 1 and buf is "abcdef"; then append(buf, sizeof buf, "ghij") returns 0 (that would need 11 bytes) and buf is still "abcdef"; append(buf, sizeof buf, "ghi") returns 1 (exactly 10 bytes).

The check calls your function with buffers sized exactly and runs it under AddressSanitizer, so writing even one byte past size is caught.

File: main.c

Starting point

#include <stdio.h>
#include <string.h>

int append(char dest[], size_t size, const char src[])
{
    strcat(dest, src);   /* unsafe: ignores size */
    return 1;
}

int main(void)
{
    char buf[10] = "abc";
    printf("%d [%s]\n", append(buf, sizeof buf, "def"), buf);
    printf("%d [%s]\n", append(buf, sizeof buf, "ghij"), buf);
    printf("%d [%s]\n", append(buf, sizeof buf, "ghi"), buf);
    return 0;
}

Hint 1

Work out how many bytes the result needs: strlen(dest) + strlen(src) + 1 for the terminator. Compare that with size before writing anything.

Hint 2

Once you know it fits, strcat(dest, src) is safe. (Or copy by index starting at dest[strlen(dest)], and do not forget the terminator.)

Hint 3

Careful with size_t: it is unsigned, so size - strlen(dest) - 1 can wrap around to a huge number. Adding on the left side, as in the first hint, avoids that.

Reference solution

#include <stdio.h>
#include <string.h>

int append(char dest[], size_t size, const char src[])
{
    size_t have = strlen(dest);
    size_t add = strlen(src);
    if (have + add + 1 > size) {
        return 0;
    }
    strcat(dest, src);   /* safe now: we checked that it fits */
    return 1;
}

int main(void)
{
    char buf[10] = "abc";
    printf("%d [%s]\n", append(buf, sizeof buf, "def"), buf);
    printf("%d [%s]\n", append(buf, sizeof buf, "ghij"), buf);
    printf("%d [%s]\n", append(buf, sizeof buf, "ghi"), buf);
    return 0;
}