Category Archives: Bug Hunting Adventures

Bug Hunting Adventures #16: Lame Surveillance

“Under observation, we act less free, which means we effectively are less free.”
― Edward Snowden

Imagine a distributed surveillance system where recorded video files are uploaded to a central server at regular intervalls.

Due to limitations of the transport protocol, video files must be split up in chunks and no chunk may exceed 1 GB (10^9 bytes). On top of that, in high-load scenarios, the server might shorten a chunk even more, in which case instead of N bytes only K bytes are transmitted. Naturally, the N-K bytes that were not transmitted need to be sent with the next chunk upload.

Everything works fine, all unit and system tests passed. Once deployed, however, sysadmins from the central server team started lamenting that the video files were arriving at a glacial pace. What’s wrong with this code?


// Establishes a connection to a video upload server.
// Returns a handle to the server connection or -1 if no connection
// could be established.
int connectToServer(const char* url, int port);

// Uploads at most 'length' bytes of 'data' to an upload server connection.
// Returns the actual number of bytes uploaded (<= length) or a value <= 0 if
// the connection is broken.
int uploadToServer(int serverHandle, const char* data, int length);

// Waits for and retrieves the next stored video.
// Returns a pointer to a contiguous video blob or NULL if there is temporarily
// no video. The size of the video blob in bytes is stored in the 'length' out
// parameter.
const char* getNextVideo(int* length);

static const char* const serverUrl = "http://video.upload.server.com";
static const int serverPort = 1234;
static const int maxChunkSize = 10^9;

...

// Open connection to server.
int serverHandle = connectToServer(serverUrl, serverPort);
if (serverHandle >= 0) {
    bool continueToUpload = true;
    while (continueToUpload) {
        // Get next video.
        int remainingVideoLength = 0;
        const char* p = getNextVideo(&remainingVideoLength);
        // If there is a video.
        if (p != NULL) {
            // Upload video in chunks.
            while (remainingVideoLength > 0) {
                int bytesToUpload = remainingVideoLength;
                if (bytesToUpload > maxChunkSize) {
                    bytesToUpload = maxChunkSize;
                }
                int uploadedBytes = uploadToServer(serverHandle, p, bytesToUpload);
                if (uploadedBytes > 0) {
                    p += uploadedBytes;
                    remainingVideoLength -= uploadedBytes;
                } else {
                    fprintf(stderr, "Uploading failed, aborting");
                    continueToUpload = false;
                    break;
                }
            }
        }
    }
} else {
    fprintf(stderr, "Failed to connect to %s:%d", serverUrl, serverPort);
}

// Establishes a connection to a video upload server.

// Returns a handle to the server connection or -1 if no connection

// could be established.

int connectToServer(const char* url, int port);

// Uploads at most 'length' bytes of 'data' to an upload server connection.

// Returns the actual number of bytes uploaded (<= length) or a value <= 0 if

// the connection is broken.

int uploadToServer(int serverHandle, const char* data, int length);

// Waits for and retrieves the next stored video.

// Returns a pointer to a contiguous video blob or NULL if there is temporarily

// no video. The size of the video blob in bytes is stored in the 'length' out

// parameter.

const char* getNextVideo(int* length);

static const char* const serverUrl = "http://video.upload.server.com";

static const int serverPort = 1234;

static const int maxChunkSize = 10^9;

...

// Open connection to server.

int serverHandle = connectToServer(serverUrl, serverPort);

if (serverHandle >= 0) {

bool continueToUpload = true;

while (continueToUpload) {

// Get next video.

int remainingVideoLength = 0;

const char* p = getNextVideo(&remainingVideoLength);

// If there is a video.

if (p != NULL) {

// Upload video in chunks.

while (remainingVideoLength > 0) {

int bytesToUpload = remainingVideoLength;

if (bytesToUpload > maxChunkSize) {

bytesToUpload = maxChunkSize;

}

int uploadedBytes = uploadToServer(serverHandle, p, bytesToUpload);

if (uploadedBytes > 0) {

p += uploadedBytes;

remainingVideoLength -= uploadedBytes;

} else {

fprintf(stderr, "Uploading failed, aborting");

continueToUpload = false;

break;

}

} else {

fprintf(stderr, "Failed to connect to %s:%d", serverUrl, serverPort);

}

Solution

Bug Hunting Adventures #15: Hex String Entanglements

“Don’t be drawn into any web of entanglement created by others.”
― Steven Redhead, Life Is Simply A Game

The following routine is from a real-world project. It’s supposed to convert binary data into a printable C-string of hexadecimal digits. Even though the developer diligently wrote some unit tests, he got complaints from his fellow coders a few days later. Can you find what’s wrong with it?


const char*
to_hexstring(const void* data, size_t data_len, char* out, size_t out_len) {
    if (data == NULL || data_len == 0 || out == NULL || out_len == 0) {
        return NULL;
    }
    //  Only proceed if output buffer is large enough:
    //  Two chars per byte + trailing string terminator.
    if (out_len < (data_len * 2) + 1) {
        return NULL;
    }
    const char* p = (const char*) data;
    for (size_t i = 0; i < data_len; ++i) {
        char hexbyte[2 + 1];
        snprintf(hexbyte, sizeof(hexbyte), "%02X", *p++);
        strcat(out, hexbyte);
    }
    return out;
}

const char*

to_hexstring(const void* data, size_t data_len, char* out, size_t out_len) {

if (data == NULL || data_len == 0 || out == NULL || out_len == 0) {

return NULL;

}

// Only proceed if output buffer is large enough:

// Two chars per byte + trailing string terminator.

if (out_len < (data_len * 2) + 1) {

return NULL;

}

const char* p = (const char*) data;

for (size_t i = 0; i < data_len; ++i) {

char hexbyte[2 + 1];

snprintf(hexbyte, sizeof(hexbyte), "%02X", *p++);

strcat(out, hexbyte);

}

return out;

}

Unit tests:


TEST(to_hexstring, some_tests) {
    const unsigned char TEST_DATA[] = { 0x00, 0x11, 0x22, 0x33, 0x1F };
    char hexstring[sizeof(TEST_DATA) * 2 + 1];

    // Typical case, output buffer large enough.
    hexstring[0] = '\0';
    EXPECT_STREQ("001122331F", to_hexstring(TEST_DATA, sizeof(TEST_DATA), 
        hexstring, sizeof(hexstring)));

    // Convert just a single byte.
    hexstring[0] = '\0';
    EXPECT_STREQ("00", to_hexstring(TEST_DATA, 1, hexstring,
        sizeof(hexstring)));

    // Convert two bytes.
    hexstring[0] = '\0';
    EXPECT_STREQ("0011", to_hexstring(TEST_DATA, 2, hexstring,
        sizeof(hexstring)));

    // Error: output buffer too small.
    hexstring[0] = '\0';
    EXPECT_STREQ(NULL, to_hexstring(TEST_DATA, sizeof(TEST_DATA),
        hexstring, 1));

    // Error: output buffer too small.
    hexstring[0] = '\0';
    EXPECT_STREQ(NULL, to_hexstring(TEST_DATA, 1, hexstring, 1));

    // Error: output buffer still too small.
    hexstring[0] = '\0';
    EXPECT_STREQ(NULL, to_hexstring(TEST_DATA, 1, hexstring, 1 + 1));
}

TEST(to_hexstring, some_tests) {

const unsigned char TEST_DATA[] = { 0x00, 0x11, 0x22, 0x33, 0x1F };

char hexstring[sizeof(TEST_DATA) * 2 + 1];

// Typical case, output buffer large enough.

hexstring[0] = '\0';

EXPECT_STREQ("001122331F", to_hexstring(TEST_DATA, sizeof(TEST_DATA),

hexstring, sizeof(hexstring)));

// Convert just a single byte.

hexstring[0] = '\0';

EXPECT_STREQ("00", to_hexstring(TEST_DATA, 1, hexstring,

sizeof(hexstring)));

// Convert two bytes.

hexstring[0] = '\0';

EXPECT_STREQ("0011", to_hexstring(TEST_DATA, 2, hexstring,

sizeof(hexstring)));

// Error: output buffer too small.

hexstring[0] = '\0';

EXPECT_STREQ(NULL, to_hexstring(TEST_DATA, sizeof(TEST_DATA),

hexstring, 1));

// Error: output buffer too small.

hexstring[0] = '\0';

EXPECT_STREQ(NULL, to_hexstring(TEST_DATA, 1, hexstring, 1));

// Error: output buffer still too small.

hexstring[0] = '\0';

EXPECT_STREQ(NULL, to_hexstring(TEST_DATA, 1, hexstring, 1 + 1));

}

Solution

Bug Hunting Adventures #14: Bitmap [BM]adness (Solution)

It’s a given fact of life that something that’s deemed totally safe in one environment may be totally unsafe in another. Every German who has ever used an American sauna knows what I’m talking about.

Similar (but far less embarrassing!) traps lurk in situations where you reuse perfectly working C++ code in a C environment. Some time ago, I integrated a little home-grown C++ library into a plain C project. However, instead of the expected, proven functionality I got plenty of core dumps. After some assembly-level debugging, I came to the conclusion that I had found a compiler bug. Code along these lines


    p += sizeof('A');
    return *p;

p += sizeof('A');

return *p;

was compiled to this:


    mov rax, QWORD PTR p[rip]
    add rax, 4                 ; 4?
    mov QWORD PTR p[rip], rax
    mov rax, QWORD PTR p[rip]

mov rax, QWORD PTR p[rip]

add rax, 4 ; 4?

mov QWORD PTR p[rip], rax

mov rax, QWORD PTR p[rip]

Why the heck did the compiler insert an offset of 4 instead of 1?

The answer to this question, which is also the answer to our bug hunting adventure, can be found here.

Bug Hunting Adventures #14: Bitmap [BM]adness

“What’s the meaning of goodness if there isn’t a little badness to overcome?”
― Anne Revere

The code below is part of a C graphics processing library, which parses data in the venerable bitmap (BMP) file format. A bitmap file consists of a two parts: a header and the pixel data block. More specifically, a bitmap file is laid-out like this:

Offset	Size	Content
0	1	Character ‘B’
1	1	Character ‘M’
2	4	Size of the bitmap file
6	4	Reserved
10	4	Offset to the first byte of the pixel data (ofs)
14	n	Info block
ofs	m	Pixel data

All multi-byte integer values (like the bitmap file size and the offset to the pixel data) are stored in little-endian format.

The function ‘bmp_pixel_data’ takes a pointer to a bitmap file data and returns a pointer to the bitmap’s pixel data area within the bitmap. The size of the pixel data area is returned via the ‘size’ out parameter. In case the provided bitmap file data is malformed, a NULL pointer is returned and the ‘size’ out parameter is set to zero.

As always, the code compiles cleanly without warnings (at ‘-W -Wall’), but when the function ‘bmp_pixel_data’ was put to use, it failed miserably. Where did the programmer goof?


/* First magic byte. */
#define BMP_MAGIC_BYTE1 'B'
/* Second magic byte. */
#define BMP_MAGIC_BYTE2 'M'
/* Offset of first magic byte. */
#define BMP_MAGIC_BYTE1_OFS 0
/* Offset of second magic byte. */
#define BMP_MAGIC_BYTE2_OFS (BMP_MAGIC_BYTE1_OFS + sizeof(BMP_MAGIC_BYTE1))
/* Offset to 4-byte bitmap file size, little-endian. */
#define BMP_FILE_SIZE_OFS (BMP_MAGIC_BYTE2_OFS + sizeof(BMP_MAGIC_BYTE2))
/* Offset to 4-byte pixel data offset, little-endian. */
#define BMP_OFFSET_OFS (BMP_FILE_SIZE_OFS + sizeof(uint32_t) + sizeof(uint32_t))
/* Offset to bitmap info block. */
#define BMP_OFFSET_INFO_BLOCK (BMP_OFFSET_OFS + sizeof(uint32_t))

static inline uint32_t uint32_from_little_endian(const uint8_t* data) {
    assert(data != NULL);
    return ((data[3] << 24U) + (data[2] << 16U) + (data[1] << 8U) + data[0]);
}

const uint8_t* bmp_pixel_data(const uint8_t* bitmap, uint32_t* size) {
    assert(bitmap != NULL);
    assert(size != NULL);

    const uint8_t* p = NULL;

    if (bitmap[BMP_MAGIC_BYTE1_OFS] == BMP_MAGIC_BYTE1 &&
        bitmap[BMP_MAGIC_BYTE2_OFS] == BMP_MAGIC_BYTE2) {
        uint32_t file_size = 
            uint32_from_little_endian(&bitmap[BMP_FILE_SIZE_OFS]);
        uint32_t offset = 
            uint32_from_little_endian(&bitmap[BMP_OFFSET_OFS]);
        if (offset <= file_size)
        {
            *size = file_size - offset;
            p = &bitmap[BMP_MAGIC_BYTE1_OFS + offset];
        }
    }
    if (p == NULL) {
        *size = 0;
    }
    return p;
}

/* First magic byte. */

#define BMP_MAGIC_BYTE1 'B'

/* Second magic byte. */

#define BMP_MAGIC_BYTE2 'M'

/* Offset of first magic byte. */

#define BMP_MAGIC_BYTE1_OFS 0

/* Offset of second magic byte. */

#define BMP_MAGIC_BYTE2_OFS (BMP_MAGIC_BYTE1_OFS + sizeof(BMP_MAGIC_BYTE1))

/* Offset to 4-byte bitmap file size, little-endian. */

#define BMP_FILE_SIZE_OFS (BMP_MAGIC_BYTE2_OFS + sizeof(BMP_MAGIC_BYTE2))

/* Offset to 4-byte pixel data offset, little-endian. */

#define BMP_OFFSET_OFS (BMP_FILE_SIZE_OFS + sizeof(uint32_t) + sizeof(uint32_t))

/* Offset to bitmap info block. */

#define BMP_OFFSET_INFO_BLOCK (BMP_OFFSET_OFS + sizeof(uint32_t))

static inline uint32_t uint32_from_little_endian(const uint8_t* data) {

assert(data != NULL);

return ((data[3] << 24U) + (data[2] << 16U) + (data[1] << 8U) + data[0]);

}

const uint8_t* bmp_pixel_data(const uint8_t* bitmap, uint32_t* size) {

assert(bitmap != NULL);

assert(size != NULL);

const uint8_t* p = NULL;

if (bitmap[BMP_MAGIC_BYTE1_OFS] == BMP_MAGIC_BYTE1 &&

bitmap[BMP_MAGIC_BYTE2_OFS] == BMP_MAGIC_BYTE2) {

uint32_t file_size =

uint32_from_little_endian(&bitmap[BMP_FILE_SIZE_OFS]);

uint32_t offset =

uint32_from_little_endian(&bitmap[BMP_OFFSET_OFS]);

if (offset <= file_size)

{

*size = file_size - offset;

p = &bitmap[BMP_MAGIC_BYTE1_OFS + offset];

}

if (p == NULL) {

*size = 0;

}

return p;

}

Solution

Bug Hunting Adventures #13: Prime Sums (Solution)

The challenge suffers from what I call a “chain of blunders”, where one blunder leads to another. Here are the exact details, in the traditional format.

The first who got close to the true nature of this bug was reader Shlomo who commented directly on the post, but I held back his comment in order not to spoil the fun for others. (Unfortunately, I couldn’t tell him, because he used a bogus email address—boo!). Christian Hujer, hacker extraordinaire, gave the most precise and extensive account on LinkedIn. While many found the blunder in the Makefile (Joe Nelson was the first), it was apparently such a good smokescreen that many people didn’t look any further. To me, the root blunder that started the chain of blunders is in the C language itself, which should have never allowed implicit zero-initialization of constants in the first place (which was corrected in C++).

Some believed that the preincrement of the loop-counter was the culprit as it would skip the first prime, but that’s not the case. The expression after the second semicolon gets evaluated always at the end of the loop body:


for (...; ...; <e>) {
    <body>
}

for (...; ...; <e>) {

<body>

}

is equivalent to


for (...; ...;) {
    <body>
    <e>;
}

for (...; ...;) {

<body>

<e>;

}

Substitute ++i or i++ for <e> — there’s no difference!

On a general note, guys, please register by entering your email address in the top right corner to ensure that you will get automatic notifications for new posts as soon as they’re published. I also (usually) announce new posts on LinkedIn, but mostly hours if not days later. Nevertheless, connecting with me on LinkedIn is always a good idea and highly encouraged. Your subscriptions, likes, praise, and criticism keep me motivated to carry on, so don’t hold back!

Bug Hunting Adventures #13: Prime Sums

“Why, yes; and not exactly that either. The fact is, we have all been a good deal puzzled because the affair is so simple, and yet baffles us altogether.”
― Edgar Allan Poe, The Purloined Letter

Below, you find a little C project that doesn’t do what it’s supposed to do, namely print the sum of the first 10 prime numbers. The program builds cleanly with gcc and clang; that is, without any warnings even when using -Wextra -Wall -pedantic -ansi as compiler options. It’s well-formed and doesn’t crash.

What’s the root cause of this bug? What’s the output of the program? Here are the files, you can also find them on GitHub:

prime_table.h:


#ifndef PRIME_TABLE_H
#define PRIME_TABLE_H

const unsigned int PRIME_TABLE[10];

#endif

#ifndef PRIME_TABLE_H

#define PRIME_TABLE_H

const unsigned int PRIME_TABLE[10];

#endif

prime_table.c:


#include "prime_table.h"

const unsigned int PRIME_TABLE[10] = {
    2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
};

#include "prime_table.h"

const unsigned int PRIME_TABLE[10] = {

2, 3, 5, 7, 11, 13, 17, 19, 23, 29,

};

prime_sum.c:


#include <stdio.h>
#include "prime_table.h"

#define ARRAY_SIZE(arr) (sizeof(arr) / sizeof(arr[0]))

int main(void) {
    unsigned int sum = 0, i;
    for (i = 0; i < ARRAY_SIZE(PRIME_TABLE); ++i) {
        sum += PRIME_TABLE[i];
    }
    printf("%u\n", sum);
    return 0;
}

#include <stdio.h>

#include "prime_table.h"

#define ARRAY_SIZE(arr) (sizeof(arr) / sizeof(arr[0]))

int main(void) {

unsigned int sum = 0, i;

for (i = 0; i < ARRAY_SIZE(PRIME_TABLE); ++i) {

sum += PRIME_TABLE[i];

}

printf("%u\n", sum);

return 0;

}

Makefile:


CFLAGS := -Wextra -Wall -pedantic -ansi

run: prime_sum
	./prime_sum

prime_sum.o : prime_sum.c prime_table.h
prime_table.o : prime_table.c prime_table.h
prime_sum : prime_sum.o prime_table.h

clean:
	rm -rf prime_sum *.o

CFLAGS := -Wextra -Wall -pedantic -ansi

run: prime_sum

./prime_sum

prime_sum.o : prime_sum.c prime_table.h

prime_table.o : prime_table.c prime_table.h

prime_sum : prime_sum.o prime_table.h

clean:

rm -rf prime_sum *.o

Solution

Approxion

Code – People – Everything

Category Archives: Bug Hunting Adventures

Bug Hunting Adventures #16: Lame Surveillance

Bug Hunting Adventures #15: Hex String Entanglements

Bug Hunting Adventures #14: Bitmap [BM]adness (Solution)

Bug Hunting Adventures #14: Bitmap [BM]adness

Bug Hunting Adventures #13: Prime Sums (Solution)

Bug Hunting Adventures #13: Prime Sums