autonomous agents for software testing

I've been thinking about software testing quite a bit lately. I've been thinking about the artificial intelligence/algorithms used in game programming too. And so naturally, at some point it occurred to me that the same algorithms used to make all those characters, monsters, cars, or whatever meander in and out of the background scenery of our favorite games might be useful in software testing scenarios.

Imagine you need to test a particularly hard-to-pin down bug - one that only happens during periods of high usage. It seems to me that you have a couple of options. You can force your users to pitch in and help with testing (not likely, and certainly not popular). You can beg your fellow programmers to do their best to mimic users (also not likely or popular). Or lastly (wishful thinking) you could fire up some program which will spawn an army of autonomous agents to meander through common use cases and behave as normal users creating the necessary "background traffic" needed for testing.

This is currently just an idea in its infancy, I don't know of any actual implementations. But it does seem like an interesting area for some research and coding. One could imagine initial versions would need lists of steps that could be invoked at random intervals and sequences by many agents through some programming interface. However, far off future versions might know how to inspect user interfaces for menus, buttons, and dialog boxes - simulating mouse clicks and keyboard entry (valid or invalid) until something happens in response.

Although I haven't found anything this sophisticated yet, it occurs to me that areas of security research might already have made progress on similar tools. Black-box penetration testing usually involves sending random (or perhaps not so random) payloads in an attempt to illicit an unexpected error or otherwise interesting response.

So, any takers want to whip something like this up for me?

new required reading for programmers

starting now I'm putting this paper on my required reading list for all programmers I hire:

http://www.eecs.harvard.edu/~mdw/papers/seda-sosp01.pdf

thanks to the authors (obviously) and the guys at http://everythingsysadmin.com/ for pointing it out.

dfs == stack overflow

As usual, xkcd nails it!

Watch out for those nasty, down-the-rabbit-hole depth first searches, they can be real productivity drains.

do your trees lean left

I haven't found any concrete examples of the algorithms described by Sedwick.

So, below is my crack at it... maybe someday I'll get around to annotating it so this will be meaningful, for now you are on your own.

static int
__tree_node_is_red(tree_node_t *n)
{
    return n && n->color == RED;
}

static int
__tree_node_is_black(tree_node_t *n)
{
    return n && n->color == BLACK;
}

static tree_node_t *
__tree_node_rotate(tree_node_t *n, tree_node_link_t dir)
{
    tree_node_t *p;
    assert(dir == LEFT || dir == RIGHT);

    p = n->link[!dir];

    /* child of p -> child of n */
    n->link[!dir] = p->link[dir];
    if (n->link[!dir])
        n->link[!dir]->link[PARENT] = n;

    /* parent of n -> parent of p */
    p->link[PARENT] = n->link[PARENT];
    if (p->link[PARENT]) {
        if (n == p->link[PARENT]->link[dir]) {
            p->link[PARENT]->link[dir] = p;
        } else {
            p->link[PARENT]->link[!dir] = p;
        }
    }

    /* swap p and n */
    p->link[dir] = n;
    n->link[PARENT] = p;

    return p;
}

static tree_node_t *
__tree_node_split(tree_node_t *n)
{
    tree_node_t *p = __tree_node_rotate(n, RIGHT);
    p->link[LEFT]->color = BLACK;
    return p;
}

static tree_node_t *
__tree_node_lean(tree_node_t *n, tree_node_link_t dir)
{
    tree_node_t *p = __tree_node_rotate(n, dir);
    p->color = p->link[dir]->color;
    p->link[dir]->color = RED;
    return p;
}

void *
tree_insert(tree_t *t, void *key, void *val)
{
    int c;
    tree_node_t *n, *p;
    void *r = NULL;

    assert(t);

    for (p = NULL, n = t->root; n; p = n, n = n->link[c > 0]) {
#ifdef BALANCE
        /* split four nodes on the way down the path */
        if (__tree_node_is_red(n->link[LEFT]))
            if (__tree_node_is_red(n->link[LEFT]->link[LEFT]))
                n = __tree_node_split(n);
#endif

        /* replace an existing entry */
        if ((c = t->cmp(key, n->entry[KEY])) == 0) {
            r = n->entry[VALUE];
            n->entry[VALUE] = val;
            break;
        }
    }

    /* adding a new node */
    try {
        if (!r) {
            n = __tree_node_create(t, p, key, val);
            throw_unless(n) out_of_memory;

            if (p) {
                p->link[c > 0] = n;
            }
        }

#ifdef BALANCE
        /* lean red links left on the way up the path */
        for ( ; p; n = p, p = p->link[PARENT])
            if (__tree_node_is_red(p->link[RIGHT]))
                p = __tree_node_lean(p, LEFT);
#endif

        /* created (or rotated) a new root if parent is null */
        if (!n->link[PARENT]) {
            t->root = n;
            n->color = BLACK;
        }
        t->size++;
    } catch (out_of_memory) { }
    return NULL;
}

static tree_node_t *
__tree_node_move(tree_node_t *n, tree_node_link_t dir)
{
    n->color = BLACK;
    n->link[dir]->color = RED;
    if (__tree_node_is_red(n->link[!dir]->link[LEFT])) {
        if (dir) {
            n = __tree_node_rotate(n, dir);
            n->color = RED;
            n->link[!dir]->color = BLACK;
        } else {
            n->link[!dir] = __tree_node_rotate(n->link[!dir], !dir);
            n = __tree_node_rotate(n, dir);
        }
    } else {
        n->link[!dir]->color = RED;
    }
    return n;
}

void *
tree_remove(tree_t *t, void *key)
{
    int c = 1;
    tree_node_t *n, *p;
    void *r = NULL;

    assert(t);

    for (p = NULL, n = t->root; n && c; p = n, n = n->link[c > 0]) {
        c = t->cmp(key, n->entry[KEY]);
        if (c < 0) {
            /* push red right */
            if (__tree_node_is_black(n->link[LEFT]) &&
                    __tree_node_is_black(n->link[LEFT]->link[LEFT]))
                n = __tree_node_move(n, LEFT);
        } else if (c > 0) {
            if (__tree_node_is_red(n->link[LEFT]))
                n = __tree_node_lean(n, RIGHT);

            if (__tree_node_is_black(n->link[RIGHT]) &&
                    __tree_node_is_black(n->link[RIGHT]->link[LEFT]))
                n = __tree_node_move(n, RIGHT);
        } else {
            if (n->link[RIGHT]) {
                tree_node_t *m = n->link[RIGHT];
                /* find successor */
                while (m->link[LEFT])
                    m = m->link[LEFT];

                /* replace and continue search */
                n->entry[KEY] = m->entry[KEY];
                n->entry[VALUE] = m->entry[VALUE];
                key = m->entry[KEY];
                c = 1; /* force move right */
            } else if (n->link[PARENT]) {
                /* delete leaf, replace parent's pointer to this
                 * node with pointer to this node's left child */
                p->link[p->link[LEFT] != n] = n->link[LEFT];
                if (n->link[LEFT])
                    n->link[LEFT]->link[PARENT] = p;
            } else {
                /* delete root */
                t->root = n->link[LEFT];
                if (n->link[LEFT])
                    n->link[LEFT]->link[PARENT] = NULL;
            }
        }
    }

    for (n = p; n->link[PARENT]; n = n->link[PARENT])
        if (__tree_node_is_red(n->link[RIGHT]))
            n = __tree_node_lean(n, LEFT);

    __tree_node_delete(t, p);

    return r;
}