A speedy algorithm for testing membership in nested ldap groups.

I just spent the better part of the day devising a speedy algorithm for testing if a given user is a member of an LDAP group.

All algorithms that I found while looking around the web looked something like this:

isMember parentGroup, user:
groupQueue.Enqueue parentGroup
while groupQueue is not empty:
currentGroup = groupQueue.Dequeue
if user is in currentGroup:
return true
else:
groupQueue.Enqueue all nested groups of currentGroup
end while
return false


I implemented that solution in C# using System.DirectoryServices and found it to be too slow (taking about 40 seconds to perform a membership test for the highest level group if the result was false). The slowness is the result of the network calls required by ‘all nested groups of currentGroup’ and ‘user is in currentGroup’.

Here is the new algorithm that is much faster (approx .1 seconds regardless of user or group).

isMember parentGroup, user:
// convert users memberships into a filter
SearchFilter = buildGroupSearchFilter(get all users groups)

// perform a subtree search starting from the parentGroup
return null != parentGroup.FindOne(SearchFilter)

buildGroupSearchFilter listOfGroups
filter = “(|”
foreach group in listOfGroups:
filter += “(distinguishedName=” + group + “)”
filter += “)”
return filter
My guess is that this is pretty standard but not posted on the web. It is about time someone did!

update: I thought about it last night and realized that in the above code the definition of the parent is based on a subtree within LDAP. This is not usual definition of parent/child membership for LDAP security. Here is a rough sketch of my newest algorithm which traverses the memberof properties and uses the correct definition:

* get all group the user is an immediate “memberof”
* get the “memberof” property for all the groups you have seen but not expanded (gotten the “memberof” property).
* if no new groups were discovered in the previous step return all the groups that you have seen; otherwise repeat previous step.

If the second step is performed in batches the above algorithm is very fast(approx .07 seconds)… otherwise, if a separate query is issued for each group, it takes 2-5 seconds. Batches can be done in similar fashion to the second algorithm above.

update: I just uploaded source code that implements checking group membership in ActiveDirectory as described in the update above. It is not complete but should be enough to get you started… please let me know if it has any errors.