Created attachment 259 [details]
sudoers file triggering the problem

If you run

visudo -q -c -f ./sudoers

on the attached sudoers file, visudo as of sudo-1.7.1 will enter an infinite loop.  This happens after

visudo.c::alias_remove_recursive

    a = alias_remove(name, type);
    if (a)
        rbinsert(alias_freelist, a)


in redblack.c::rbinsert


    while (node != rbnil(tree)) {
        parent = node;
        if ((res = tree->compar(data, node->data)) == 0)
            return(node);
        node = res < 0 ? node->left : node->right;
    }


For unknown reasons, the attached sudoers file appears to cause another sentinel node to get created, so that at this point the loop will continue:

After traversing the tree seemingly correctly for a while:

Run till exit from #0  alias_compare (v1=0x531580, v2=0x52e9a0) at
./alias.c:71
0x000000000040a933 in rbinsert (tree=0x522680, data=0x531580) at
./redblack.c:186
186     ./redblack.c: No such file or directory.
        in ./redblack.c
Value returned is $33 = 3


We get to a point, where:

186     in ./redblack.c
(gdb)
alias_compare (v1=0x531580, v2=0x0) at ./alias.c:67


Since we're looping until the node we're looking at is the "sentinel"
node initialized as

    /*
     * We use a self-referencing sentinel node called nil to simplify
     * the
     * code by avoiding the need to check for NULL pointers.
     */
    tree->nil.left = tree->nil.right = tree->nil.parent = &tree->nil;
    tree->nil.color = black;
    tree->nil.data = NULL;


but somehow we ended up with a *different* self-referential node:

(gdb) p tree->nil
$48 = {left = 0x5226b0, right = 0x5226b0, parent = 0x5226b0, data = 0x0,
color = black}
(gdb) p node->left
$49 = (struct rbnode *) 0x522630
(gdb) p node->right
$50 = (struct rbnode *) 0x522630
(gdb) p node->parent
$51 = (struct rbnode *) 0x522630

this loop continues forever, since "alias_compare" will now always
return a negative value (data is NULL), and the node will use its left
child to continue looping.  Since its left child == itself == its
right child == parent, we never break the loop.


Now here's the kicker:  the order in which the statements in the sudoers file occur matter.  That is, if I shuffle any of the statements, this bug won't be triggered.


This bug was confirmed on FreeBSD 6.4 amd64 as well as Mac OS X (Darwin 9.7.0, intel).

This bug does not exist in sudo-1.7.0 (since the recursion on checking was introduced in 1.7.1).

The attached file contains obviously useless aliases -- however, I had a file with the exact same directives with more meaningful names and actual userlists that caused this.


The alphabetical and logical order in the file appears to be related to triggering this bug, so it's conceivable that somewhere down the line this has something to do with string comparison?