AD via LDAP - How can I return all ancestor groups from a query?

Question

I am querying Active Directory via LDAP (from Java and PHP) to build a list of all groups that a user is a member of. This list must contain all least all groups (organizational-units optional) that contain groups the user is directly a member of. For example:

User1 is a member of GroupA, GroupB, and GroupC.

GroupA is a member of GroupD.

I am looking for a way to construct an LDAP query that will return GroupA, GroupB, GroupC, and GroupD all at once.

My current implementation is below, but I am looking for a more efficient way to gather this information.

Current Naive Implementation (In pseudo-code)

user = ldap_search('samaccountname=johndoe', baseDN);
allGroups = array();
foreach (user.getAttribute('memberOf') as groupDN) {
    allGroups.push(groupDN);
    allGroups = allGroups.merge(getAncestorGroups(groupDN));
}

function getAncestorGroups(groupDN) {
    allGroups = array();
    group = ldap_lookup(groupDN);
    parents = group.getAttribute('memberOf');
    foreach (parents as groupDN) {
        allGroups.push(groupDN);
        allGroups = allGroups.merge(getAncestorGroups(groupDN));
    }
    return allGroups;
}

Answer 1

You need to map the directory tree, as you move through it, so you can check to see if you have previously explored a DN, some Active Directories contain looped group inclusions. So you'll need to guard against it.

This solution also doesn't require recursion.

In some pseudo code

def getGroupsOfDN(userDN)

     groups = []
     groupsExplored = []
     groupsToExplore = []


     current = userDN
     groupsToExplore << userDN

     while(!groupsToExplore.empty?)


        ldapentry = ldap_lookup(current)

        if (!ldapentry.nil?)
           groups << current
           current_groups = ldapentry.getAttributes("memberOf")
           current_groups.each do |groupDN|
              if(groupsExplored.indexOf(groupDN) != -1)
                 groupsToExplore << groupDN
                 groupsExplored << groupDN
              end
           end
        end

        groupsToExplore.remove(current)
        if (!groupsToExplore.empty?)
           current = groupsToExplore.get(0)            
     end
     return groups
end