Efficient way to get AD user membership recursively with PowerShell

The other day, one customer asked for a solution to get full user membership in Active Directory for audit purposes. The solution should retrieve not only direct group membership, but indirect (through group nesting) too. Although, the question is plain and simple, solution is very interesting from various perspectives.

At first, let illustrate a sample user and group membership diagram:

Active Directory group membership graph

Quick diagram observation suggests us that we have a directed graph (it is not a tree), where users and groups are vertexes and membership relations are directed edges. Arrows identify relationship direction.

Our graph contains two users, User1 and User2 and eight groups: G1G8. In a given case, User1 is direct member of groups G1, G2 and G3, User2 is direct member of G8 only. Group G1 is member of G4, G2 is direct member of G4 and G5 and so on. For description purposes I labeled all edges. This should be clear.

The algorithm

Our initial algorithm would be as follows:

    1. Initialize array to store current user group membership and assign to $UserGroups.
    2. Get direct groups for user. Assign them to $currentGroups;
    3. Loop over $currentGroups and assign each item to $currentGroup;
    4. Add $currentGroup to the $UserGroups variable;
    5. Retrieve direct groups for $currentGroup and assign them to $currentGroups and repeat steps 3-5.
    6. End loop.

Quick algorithm observation suggests that we will deal with recursive loop.

Potential issues

While it looks pretty legitimate, we may encounter the following issues (and we definitely will with the current diagram):

1) We will have a lot of duplicates. For example, G4 group will be listed twice, because we have two paths from User1 to G4: User1 → e2 → e5 → G4 and User1 → e3 → e6 → G4. The same thing is for G7. We have two paths through: User1 → e1 → e10 –> G7 and User1 → e2 → e4 → e7 → e8 → G7.

Of course, nothing prevents as to use Select-Object –Unique to get unique entries, but this wouldn’t be very efficient. Especially when there are a lot of duplicates.

2) Our logic may never end, because we have one closed walk: when starting from G2 vertex we will return to it through: G2 → e4 → e7 → e8 → e9 → G2. If we do not take additional steps, the code will enter into an infinity loop and eventually will fail with stack overflow exception.

To avoid both potential issues, we have to keep a separate array where we would store visited vertexes (groups). And during each group processing we will check whether the current vertex was already visited and skip if we did. By doing this we will implement a very basic spanning tree algorithm where we convert our graph into tree, so from each Group vertex only single path will exist down to a User vertex. At this point we do not care about which path is shortest, because edges have zero cost. An updated algorithm would look as follows:

  1. Initialize array to store current user group membership and assign to $UserGroups.
  2. Get direct groups for user. Assign them to $currentGroups;
  3. Loop over $currentGroups and assign each item to $currentGroup;
  4. If the $UserGroups contains $currentUser, skip this entry and return to step 3.
  5. Add $currentGroup to the $UserGroups variable;
  6. Retrieve direct groups for $currentGroup and assign them to $currentGroups and repeat steps 3-5.
  7. End loop.

Performance tuning

Step 4 of the updated algorithm suggests multiple searches in $UserGroups array. For small arrays (when user is a member of only few groups) it is acceptable to use linear search that will result in (where n is a total number of user groups) complexity in each iteration and for entire lookup it will take up to . For larger organizations when user is a member of a large number of groups, linear search will quickly become ineffective. To reduce lookup costs, $UserGroups array will be initialized as a hashtable which has complexity for each iteration and will be up to for entire lookup.

Another question is about steps 6 when we will retrieve parent groups for $currentGroup variable. Depending on a group membership complexity, we may encounter multiple identical (redundant) queries to domain controller. For single user lookups it is acceptable to issue separate queries to retrieve group object with memberOf attribute, because they all will be unique (due to step 4). However, when we do such lookup for a large number of users (or even for all users in Active Directory domain), we will get a lot of identical and redundant queries. There are two approaches that may solve this puzzle:

  1. Introduce another array to cache retrieved from Active Directory group objects. And during group object retrieval check if the current group is already cached and use cache information, otherwise issue a query to domain controller. This solution is effective when client has reliable connection to domain controller, but may fail if the connection is poor.
  2. Issue a single request to domain controller and retrieve *all* groups from Active Directory and use it as a local cache. This solution is effective from performance perspective when client is connected to domain controller over poor/unreliable connection, because only single query is issued. Additionally, it is effective when many users are processed. In other cases it may not be effective from memory consumption perspective. Another downside, domain controller will get increased workload to process the query.

For group cache I would recommend to use hashtable as well, because the code will extensively lookup at cache and efficient lookup will positively impact overall script performance. I’m not going to favor any of these solutions, you can select either at your choice. Though, in the code I’m going to use first approach.

Writing solution in PowerShell

In the solution, we will use PowerShell and Active Directory PowerShell module which is shipped with ADDS remote server administration tools (RSAT). Make sure if it is installed on your system. And here is a code with relevant comments:

function Get-UserGroupMembershipRecursive {
[CmdletBinding()]
    param(
        [Parameter(Mandatory = $true, ValueFromPipeline = $true)]
        [String[]]$UserName
    )
    begin {
        # introduce two lookup hashtables. First will contain cached AD groups,
        # second will contain user groups. We will reuse it for each user.
        # format: Key = group distinguished name, Value = ADGroup object
        $ADGroupCache = @{}
        $UserGroups = @{}
        # define recursive function to recursively process groups.
        function __findPath ([string]$currentGroup) {
            Write-Verbose "Processing group: $currentGroup"
            # we must do processing only if the group is not already processed.
            # otherwise we will get an infinity loop
            if (!$UserGroups.ContainsKey($currentGroup)) {
                # retrieve group object, either, from cache (if is already cached)
                # or from Active Directory
                $groupObject = if ($ADGroupCache.ContainsKey($currentGroup)) {
                    Write-Verbose "Found group in cache: $currentGroup"
                    $ADGroupCache[$currentGroup]
                } else {
                    Write-Verbose "Group: $currentGroup is not presented in cache. Retrieve and cache."
                    $g = Get-ADGroup -Identity $currentGroup -Property "MemberOf"
                    # immediately add group to local cache:
                    $ADGroupCache.Add($g.DistinguishedName, $g)
                    $g
                }
                # add current group to user groups
                $UserGroups.Add($currentGroup, $groupObject)
                Write-Verbose "Member of: $currentGroup"
                foreach ($p in $groupObject.MemberOf) {
                    __findPath $p
                }
            } else {Write-Verbose "Closed walk or duplicate on '$currentGroup'. Skipping."}
        }
    }
    process {
        foreach ($user in $UserName) {
            Write-Verbose "========== $user =========="
            # clear group membership prior to each user processing
            $UserObject = Get-ADUser -Identity $user -Property "MemberOf"
            $UserObject.MemberOf | ForEach-Object {__findPath $_}
            New-Object psobject -Property @{
                UserName = $UserObject.Name;
                MemberOf = $UserGroups.Values | % {$_}; # groups are added in no particular order
            }
            $UserGroups.Clear()
        }
    }
}

And example output with verbose tracing where we can track code logic:

PS C:\> $report = Get-UserGroupMembershipRecursive user1, user2 -Verbose
VERBOSE: ========== user1 ==========
VERBOSE: Processing group: CN=G3,OU=StubOU,DC=sysadmins,DC=lv
VERBOSE: Group: CN=G3,OU=StubOU,DC=sysadmins,DC=lv is not presented in cache. Retrieve and cache.
VERBOSE: Member of: CN=G3,OU=StubOU,DC=sysadmins,DC=lv
VERBOSE: Processing group: CN=G6,OU=StubOU,DC=sysadmins,DC=lv
VERBOSE: Group: CN=G6,OU=StubOU,DC=sysadmins,DC=lv is not presented in cache. Retrieve and cache.
VERBOSE: Member of: CN=G6,OU=StubOU,DC=sysadmins,DC=lv
VERBOSE: Processing group: CN=G7,OU=StubOU,DC=sysadmins,DC=lv
VERBOSE: Group: CN=G7,OU=StubOU,DC=sysadmins,DC=lv is not presented in cache. Retrieve and cache.
VERBOSE: Member of: CN=G7,OU=StubOU,DC=sysadmins,DC=lv
VERBOSE: Processing group: CN=G2,OU=StubOU,DC=sysadmins,DC=lv
VERBOSE: Group: CN=G2,OU=StubOU,DC=sysadmins,DC=lv is not presented in cache. Retrieve and cache.
VERBOSE: Member of: CN=G2,OU=StubOU,DC=sysadmins,DC=lv
VERBOSE: Processing group: CN=G5,OU=StubOU,DC=sysadmins,DC=lv
VERBOSE: Group: CN=G5,OU=StubOU,DC=sysadmins,DC=lv is not presented in cache. Retrieve and cache.
VERBOSE: Member of: CN=G5,OU=StubOU,DC=sysadmins,DC=lv
VERBOSE: Processing group: CN=G6,OU=StubOU,DC=sysadmins,DC=lv
VERBOSE: Closed walk or duplicate on 'CN=G6,OU=StubOU,DC=sysadmins,DC=lv'. Skipping.
VERBOSE: Processing group: CN=G4,OU=StubOU,DC=sysadmins,DC=lv
VERBOSE: Group: CN=G4,OU=StubOU,DC=sysadmins,DC=lv is not presented in cache. Retrieve and cache.
VERBOSE: Member of: CN=G4,OU=StubOU,DC=sysadmins,DC=lv
VERBOSE: Processing group: CN=G7,OU=StubOU,DC=sysadmins,DC=lv
VERBOSE: Closed walk or duplicate on 'CN=G7,OU=StubOU,DC=sysadmins,DC=lv'. Skipping.
VERBOSE: Processing group: CN=G2,OU=StubOU,DC=sysadmins,DC=lv
VERBOSE: Closed walk or duplicate on 'CN=G2,OU=StubOU,DC=sysadmins,DC=lv'. Skipping.
VERBOSE: Processing group: CN=G1,OU=StubOU,DC=sysadmins,DC=lv
VERBOSE: Group: CN=G1,OU=StubOU,DC=sysadmins,DC=lv is not presented in cache. Retrieve and cache.
VERBOSE: Member of: CN=G1,OU=StubOU,DC=sysadmins,DC=lv
VERBOSE: Processing group: CN=G4,OU=StubOU,DC=sysadmins,DC=lv
VERBOSE: Closed walk or duplicate on 'CN=G4,OU=StubOU,DC=sysadmins,DC=lv'. Skipping.
VERBOSE: ========== user2 ==========
VERBOSE: Processing group: CN=G8,OU=StubOU,DC=sysadmins,DC=lv
VERBOSE: Group: CN=G8,OU=StubOU,DC=sysadmins,DC=lv is not presented in cache. Retrieve and cache.
VERBOSE: Member of: CN=G8,OU=StubOU,DC=sysadmins,DC=lv
VERBOSE: Processing group: CN=G5,OU=StubOU,DC=sysadmins,DC=lv
VERBOSE: Found group in cache: CN=G5,OU=StubOU,DC=sysadmins,DC=lv
VERBOSE: Member of: CN=G5,OU=StubOU,DC=sysadmins,DC=lv
VERBOSE: Processing group: CN=G6,OU=StubOU,DC=sysadmins,DC=lv
VERBOSE: Found group in cache: CN=G6,OU=StubOU,DC=sysadmins,DC=lv
VERBOSE: Member of: CN=G6,OU=StubOU,DC=sysadmins,DC=lv
VERBOSE: Processing group: CN=G7,OU=StubOU,DC=sysadmins,DC=lv
VERBOSE: Found group in cache: CN=G7,OU=StubOU,DC=sysadmins,DC=lv
VERBOSE: Member of: CN=G7,OU=StubOU,DC=sysadmins,DC=lv
VERBOSE: Processing group: CN=G2,OU=StubOU,DC=sysadmins,DC=lv
VERBOSE: Found group in cache: CN=G2,OU=StubOU,DC=sysadmins,DC=lv
VERBOSE: Member of: CN=G2,OU=StubOU,DC=sysadmins,DC=lv
VERBOSE: Processing group: CN=G5,OU=StubOU,DC=sysadmins,DC=lv
VERBOSE: Closed walk or duplicate on 'CN=G5,OU=StubOU,DC=sysadmins,DC=lv'. Skipping.
VERBOSE: Processing group: CN=G4,OU=StubOU,DC=sysadmins,DC=lv
VERBOSE: Found group in cache: CN=G4,OU=StubOU,DC=sysadmins,DC=lv
VERBOSE: Member of: CN=G4,OU=StubOU,DC=sysadmins,DC=lv
PS C:\> $report

MemberOf                                                    UserName
--------                                                    --------
{CN=G5,OU=StubOU,DC=sysadmins,DC=lv, CN=G2,OU=StubOU,DC=... User1
{CN=G8,OU=StubOU,DC=sysadmins,DC=lv, CN=G2,OU=StubOU,DC=... User2


PS C:\> $report[0].MemberOf.name
G5
G2
G7
G3
G4
G1
G6
PS C:\> $report[1].MemberOf.name
G8
G2
G6
G4
G7
G5
PS C:\>

We can confirm that user membership information correctly reflect our diagram. In addition, we see that second user lookup actively uses AD group cache and only one query was issued to domain controller.

HTH

Comments:

Michael Graham
Michael Graham 26.10.2016 05:38 (GMT+3)

Very well thought out script. I appreciate that you posted it. I had recently created a recursive script myself, and was looking to increase it's performance. My previous script is here: https://github.com/mgraham-cracker/ADSearch if you would like to take a look at some features I built into it.

I went ahead and quickly created a modified version of your script to test a key feature I needed, an inheritance path field. It is often good for me to know how a person is in a group, not just that they are in a group. I put the code below if you were interested.

Thanks again,

--- Code Below ---

function Get-UserGroupMembershipRecursive {
[CmdletBinding()]
    param(
        [Parameter(Mandatory = $true, ValueFromPipeline = $true)]
        [String[]]$UserName
    )
    begin {
        # introduce two lookup hashtables. First will contain cached AD groups,
        # second will contain user groups. We will reuse it for each user.
        # format: Key = group distinguished name, Value = ADGroup object
        $ADGroupCache = @{}
        $UserGroups = @{}
        $OutObject = @()
        # define recursive function to recursively process groups.
        function __findPath ([string]$currentGroup, [string]$comment) {
            Write-Verbose "Processing group: $currentGroup"
            # we must do processing only if the group is not already processed.
            # otherwise we will get an infinity loop
            if (!$UserGroups.ContainsKey($currentGroup)) {
                # retrieve group object, either, from cache (if is already cached)
                # or from Active Directory
                $groupObject = if ($ADGroupCache.ContainsKey($currentGroup)) {
                    Write-Verbose "Found group in cache: $currentGroup"
                    $ADGroupCache[$currentGroup].Psobject.Copy()
                } else {
                    Write-Verbose "Group: $currentGroup is not presented in cache. Retrieve and cache."
                    $g = Get-ADGroup -Identity $currentGroup -Property objectclass,sid,whenchanged,whencreated,samaccountname,displayname,enabled,distinguishedname,memberof
                    # immediately add group to local cache:
                    $ADGroupCache.Add($g.DistinguishedName, $g)
                    $g
                }
                
                $c = $comment + "->" + $groupObject.SamAccountName
                
                $UserGroups.Add($c, $groupObject)
                                
                Write-Verbose "Membership Path:  $c"
                foreach ($p in $groupObject.MemberOf) {
                       __findPath $p $c
                }
            } else {Write-Verbose "Closed walk or duplicate on '$currentGroup'. Skipping."}
        }
    }
    process {
        foreach ($user in $UserName) {
            Write-Verbose "========== $user =========="
            # clear group membership prior to each user processing
            $UserObject = Get-ADUser -Identity $user -Property objectclass,sid,whenchanged,whencreated,samaccountname,displayname,enabled,distinguishedname,memberof
            $UserObject.MemberOf | ForEach-Object {__findPath $_ $UserObject.SamAccountName}
}
            foreach($g in $UserGroups.GetEnumerator())
            {
                $OutObject += [pscustomobject]@{
                    ObjectClass = $g.value.ObjectClass;
                    UserName = $UserObject.SamAccountName;
                    InheritancePath = $g.key;
                    MemberOf = $g.value.SamAccountName;
                    WhenChanged = $g.value.WhenChanged;
                    WhenCreated = $g.value.WhenCreated;
                }
            }
            $OutObject | Sort-Object -Property UserName,InheritancePath,MemberOf | Out-Gridview
            $UserGroups.Clear()
        }
    }

Captcha