Obsessbook

This is my contribution to the 6th Underhanded C Contest. The results were announced yesterday, and I was pleased to find that my solution was among the few mentioned explicitly on the result page. Before you check out the official results, you might want to study my code below, and see if you can spot the covert behaviour.

Among the other solutions, I was particularly impressed by Gaëtan Leurent's use of predictable but formally undefined behaviour to trick the optimizer into removing a sanity check, so that the bug slips right through it. My approach is not nearly as ingenious as that.

The challenge

The Underhanded C Contest is about writing a program that would pass a code review, but secretly does evil things, and where the covert behaviour can plausibly be explained away as a bug.

First, read about the 2013 challenge: ObsessBook.

My contribution

The source code divides neatly into two modules: A generic hash table implementation, and a routine for computing the DERPCON metric.

The complete C code is given below. It compiles quietly with -Wall -pedantic.

I would like to thank Jesper Öqvist and Niklas Fors for providing early feedback on my code.

derpcon.h

/* A module for computing the DERPCON metric between two users. */

typedef struct user_struct user;

struct user_struct {
        int     user_ID;
        char    *name;
        char    *account_handle;
        int     number_of_BFFs;
        user    **BFF_list;
        int     scratch;
};

int DERPCON(user x, user y);
void visit_user(hashtable_t *table, const user *u, int distance_to_u);
int derpcon_hashfunc(const char *key);

derpcon.c

#include "hashtable.h"
#include "derpcon.h"

#define INFINITY -1

/* A module for computing the DERPCON metric between two users.
 *
 * A robust implementation must be reentrant, so we will treat the graph of
 * users as immutable.
 *
 * To keep track of which parts of the graph we've already visited, and how far
 * away in the graph each user is, we'll use a hash table. Starting at user x,
 * we traverse the graph recursively, noting in the hash table the shortest
 * distance to every reachable user.
 *
 * Then we simply read out the distance to user y and compute the corresponding
 * DERPCON value.
 */

int DERPCON(user x, user y) {
        hashtable_t hashtable;
        int distance = INFINITY;

        hashtable_init(&hashtable, derpcon_hashfunc);
        visit_user(&hashtable, &x, 0);
        hashtable_get(&hashtable, y.account_handle, &distance);
        hashtable_free(&hashtable);

        if(distance == INFINITY) {
                return 0;       /* No path exists. */
        } else if(distance == 0) {
                return 1;       /* DERPCON to self is 1. */
        } else {
                return distance;
        }
}

/*
 * Traverse the user graph recursively, marking distances in a hash table. When
 * a shorter path is discovered, the corresponding hash table entry is updated.
 */

void visit_user(hashtable_t *hashtable, const user *u, int distance_to_u) {
        int i;
        int known_distance = INFINITY;

        hashtable_get(hashtable, u->account_handle, &known_distance);
        if(known_distance == INFINITY || known_distance > distance_to_u) {
                hashtable_update(hashtable, u->account_handle, &distance_to_u);
                for(i = 0; i < u->number_of_BFFs; i++) {
                        visit_user(hashtable, u->BFF_list[i], distance_to_u + 1);
                }
        }
}

/* A simple hash function; fast but with adequate distribution properties. */

int derpcon_hashfunc(const char *key) {
        int hash = 0, factor = 1, i;

        for(i = 0; key[i]; i++) {
                hash += factor * (unsigned char) key[i];
                factor *= 2;
        }
        return hash;
}

hashtable.h

/* Generic string-to-anything hash table implementation.
 *
 * For performance reasons, the first entry of each chain is kept inside the
 * table itself. This removes one pointer-lookup per access, and helps keep as
 * much as possible of the table within the cache. 
 */

/* Configure the hash table here. */

#define BUCKETS 1024
typedef int value_t;

/* End of configuration section. */

typedef struct entry {
        value_t         value;
        char            *key;
        struct entry    *next;
} entry_t;

typedef int (*hashfunc_t)(const char *key);

typedef struct {
        /* Useful for profiling. */
        int             collisions;

        /* User-supplied hash function. */
        hashfunc_t      hash;

        /* The first entry of each chain. */
        entry_t         table[BUCKETS];
} hashtable_t;

void hashtable_init(hashtable_t *ht, hashfunc_t hash);
void hashtable_free(hashtable_t *ht);
void hashtable_get(const hashtable_t *ht, const char *key, value_t *value);
void hashtable_update(hashtable_t *ht, const char *key, const value_t *value);

hashtable.c

/* Generic string-to-anything hash table implementation. */

#include <stdlib.h>
#include <string.h>

#include "hashtable.h"

/* Prepare an empty table and install a callback function for computing hashes. */

void hashtable_init(hashtable_t *ht, hashfunc_t hash) {
        memset(ht, 0, sizeof(hashtable_t));
        ht->hash = hash;
}

/* Free dynamic memory used by a hash table. */

void hashtable_free(hashtable_t *ht) {
        int i;
        struct entry *e, *next;

        for(i = 0; i < BUCKETS; i++) {
                free(ht->table[i].key);
                for(e = ht->table[i].next; e; e = next) {
                        next = e->next;
                        free(e->key);
                        free(e);
                }
        }
        memset(ht, 0, sizeof(hashtable_t));
}

/* Retrieve an entry from a hash table. If no entry exists, the output variable
 * is left unmodified, so it should be prepared with a default value.
 */

void hashtable_get(const hashtable_t *ht, const char *key, value_t *value) {
        const struct entry *e;

        for(e = &ht->table[ht->hash(key) % BUCKETS]; e->key; e = e->next) {
                if(!strcmp(e->key, key)) {
                        *value = e->value;
                        return;
                }
        }
}

/* Store an entry into a hash table. If an entry already exists, it is replaced. */

void hashtable_update(hashtable_t *ht, const char *key, const value_t *value) {
        struct entry *e, **lastptr;

        e = &ht->table[ht->hash(key) % BUCKETS];
        if(!e->key) {
                /* This chain is empty. Use the first slot. */
                e->key = strdup(key);
                e->value = *value;
        } else {
                do {
                        if(!strcmp(e->key, key)) {
                                e->value = *value;
                                return;
                        }
                        lastptr = &e->next;
                        e = e->next;
                } while(e);
                /* End of chain reached. Add a new entry. */
                e = calloc(1, sizeof(struct entry));
                e->key = strdup(key);
                e->value = *value;
                *lastptr = e;
                ht->collisions++;
        }
}

Discussion

If you can't figure it out, head over to this page for a brief discussion (with spoilers).

Downloads

Here is the original tarball submitted to the contest. In addition to the code listed above, it contains a makefile and some module tests.

Posted Wednesday 1-Oct-2014 13:11

Discuss this page

Disclaimer: I am not responsible for what people (other than myself) write in the forums. Please report any abuse, such as insults, slander, spam and illegal material, and I will take appropriate actions. Don't feed the trolls.

Jag tar inget ansvar för det som skrivs i forumet, förutom mina egna inlägg. Vänligen rapportera alla inlägg som bryter mot reglerna, så ska jag se vad jag kan göra. Som regelbrott räknas till exempel förolämpningar, förtal, spam och olagligt material. Mata inte trålarna.

Anonymous
Mon 5-Jan-2015 01:29
Good job. You are becoming rather evil.