PowerShell: Recursion And Finding Loops In A Hierarchy With Active Directory Example

Recently, a friend of mine asked me about the best way to find loops in a hierarchy, specifically with Active Directory groups that may be nested (either by design or by mistake) thereby causing loops and this recursion based solution was my recommended answer for him.

The Problem:

Here is the example he gave me:

I am looking for a way to detect recursion loops in a specified AD Group.  Take this example of groups and members. I started with Group1, and found Group2, with group member Group2. Group2 has a group member Group3. Enumerating Group3 finds Group1, and loop!

Group Name Member Member Member Member
Group1 User1 User2 Group2
Group2 User1 User2 User3 Group3
Group3 User3 User8 Group1

He also said: Some groups are nested many levels down, and a single top level group can have more than one recursive loop. The script should be able to not only identify Group1>Group3>Group1, but also Group1>Group8>Group5>Group15>Group1.

The Goals:

  • Find Loops (nested hierarchies that loop back up to form a closed circuit)
  • Find all the loops in a hierarchy given a top level parent group
  • Need to also get the flat list of all members and groups involved in the hierarchy

The Simplified Solution:

Simplifying the problem is the first step I took. It can be tedious to create and rearrange various loops in AD for testing quickly. So, I used simple arrays instead.  This solution uses recursion.

Assuming the groups are setup like this:

        "Group1" = "User1,User2,Group2,Group8";
        "Group2" = "User1,User2,User3,Group3"
        "Group3" = "User3,User8,Group1"
        "Group4" = "Group8,User1"
        "Group5" = "User10,Group15"
        "Group6" = "User10, User11"
        "Group7" = "User11"
        "Group8" = "Group5"
        "Group15" = "Group1"

Starting with Group4 above, if I ran the simplified example (second part of the sample code below), it should return the output here

#----------------------------------------
#Sample code to test the function
#----------------------------------------
$startGroup = 'Group4'
[System.Collections.Specialized.OrderedDictionary] $tempWorkHashTable = (New-Object System.Collections.Specialized.OrderedDictionary)
[System.Collections.Specialized.OrderedDictionary] $groupsReturnHashTable = (New-Object System.Collections.Specialized.OrderedDictionary)
[System.Collections.Specialized.OrderedDictionary] $loopsReturnHashTable = (New-Object System.Collections.Specialized.OrderedDictionary)
[System.Collections.Specialized.OrderedDictionary] $membersReturnHashTable = (New-Object System.Collections.Specialized.OrderedDictionary)
Get-GroupLoops `
    -Identity $startGroup `
    -TempWorkHashTable ([ref]$tempWorkHashTable) `
    -GroupsReturnHashTable ([ref]$groupsReturnHashTable) `
    -LoopsReturnHashTable ([ref]$loopsReturnHashTable) `
    -MembersReturnHashTable ([ref]$membersReturnHashTable) `
    -Verbose

"----Groups-------"
$groupsReturnHashTable

"----Members-------"
$membersReturnHashTable

"----Loops-------"
$loopsReturnHashTable

Output is below (notice the Groups, Members and Loops output):

----Groups-------
Name                           Value                                                                                                                                                                                                     
----                           -----                                                                                                                                                                                                     
Group4                         Group4                                                                                                                                                                                                    
Group8                         Group8                                                                                                                                                                                                    
Group5                         Group5                                                                                                                                                                                                    
Group15                        Group15                                                                                                                                                                                                   
Group1                         Group1                                                                                                                                                                                                    
Group2                         Group2                                                                                                                                                                                                    
Group3                         Group3
                                                                                                                                                                                                    
----Members-------
User10                         User10                                                                                                                                                                                                    
User1                          User1                                                                                                                                                                                                     
User2                          User2                                                                                                                                                                                                     
User3                          User3                                                                                                                                                                                                     
User8                          User8
                                                                                                                                                                                                     
----Loops-------
->Group4->Group8->Group5->Group15->Group1->Group2->Group3->Group1                                                                                                                                         
->Group4->Group8->Group5->Group15->Group1->Group8

The Code (2 Parts – Active Directory and Simplified Solution):

I have created a GIT gist and referenced the link to embed GitHub code in this blog post. If you do not see code, please try opening this blog post in a browser window.
The first code snippet finds loops in Active Directory and the second example is one you can play with, without the need for Active Directory.


# Author: Jana Sattainathan – https://sqljana.wordpress.com – September 1, 2020
#Gets all the loops (ie., at some point members of groups are groups already traversed in hierarchy)
function Get-ADGroupLoops
{
param (
[Parameter()]
[object]$Identity,
[Parameter()]
[System.Collections.Specialized.OrderedDictionary][ref] $TempWorkHashTable = (New-Object System.Collections.Specialized.OrderedDictionary),
[Parameter()]
[System.Collections.Specialized.OrderedDictionary][ref] $GroupsReturnHashTable = (New-Object System.Collections.Specialized.OrderedDictionary),
[Parameter()]
[System.Collections.Specialized.OrderedDictionary][ref] $MembersReturnHashTable = (New-Object System.Collections.Specialized.OrderedDictionary),
[Parameter()]
[System.Collections.Specialized.OrderedDictionary][ref] $LoopsReturnHashTable = (New-Object System.Collections.Specialized.OrderedDictionary)
)
[bool] $loopBeginning = $false
[string] $fullHierarchyString = ""
[string] $loopString = ""
$adObject = Get-ADObject -Identity $Identity
#If this is group and not an individual
if ($adObject.ObjectClass -eq 'group')
{
Write-Verbose "Working on: $Identity"
if (!$GroupsReturnHashTable.Contains($adObject.DistinguishedName))
{
$GroupsReturnHashTable.Add($adObject.DistinguishedName, $adObject)
}
#Get the members of the group
$members = Get-ADGroupMember -Identity $Identity
#If this we have not seen this group before
if (!$TempWorkHashTable.Contains($adObject.DistinguishedName))
{
$TempWorkHashTable.Add($adObject.DistinguishedName, $adObject) | Out-Null
$members | foreach {
#This is the recursive call to itself
$members = Get-ADGroupLoops `
-Identity (Get-ADObject -Identity $_) `
-TempWorkHashTable ([ref]$TempWorkHashTable) `
-GroupsReturnHashTable ([ref]$GroupsReturnHashTable) `
-MembersReturnHashTable ([ref]$MembersReturnHashTable) `
-LoopsReturnHashTable ([ref]$LoopsReturnHashTable)
}
}
else
{
#We have already seen this group before. That is the starting point of the loop
# and we have to print and remove all elements in the Ordered dictionary from that element that form the loop
[HashTable] $keysToRemove = @{}
foreach($key in $TempWorkHashTable.Keys)
{
if ($key -eq $adObject.DistinguishedName)
{
$loopBeginning = $true
}
$fullHierarchyString = $fullHierarchyString + "->" + $TempWorkHashTable[$key].Name
if ($loopBeginning -eq $true)
{
$keysToRemove.Add($key, $key)
$loopString = $loopString + "->" + $TempWorkHashTable[$key].Name
}
}
#The full hierarchy and loop
$fullHierarchyString = $fullHierarchyString + "->" + $adObject.Name
$loopString = $loopString + "->" + $adObject.Name
foreach($key in $keysToRemove.Keys)
{
$TempWorkHashTable.Remove($key)
}
#DN,oGroup
$TempWorkHashTable.Add($adObject.DistinguishedName, $adObject)
Write-Verbose "Hierarchy: $fullHierarchyString"
Write-Verbose "Loop: $loopString"
$LoopsReturnHashTable.Add($loopString, $fullHierarchyString) | Out-Null
$fullHierarchyString = ""
$loopString = ""
}
}
else
{
## It is not a group..just a regular user
if (!$MembersReturnHashTable.Contains($adObject.DistinguishedName))
{
$MembersReturnHashTable.Add($adObject.DistinguishedName, $adObject)
}
}
}
#—————————————-
#Sample code to test the function above
#—————————————-
$startGroup = Get-ADGroup 'YOUR-TOP-LEVEL-AD-GROUP_NAME'
[System.Collections.Specialized.OrderedDictionary] $tempWorkHashTable = (New-Object System.Collections.Specialized.OrderedDictionary)
[System.Collections.Specialized.OrderedDictionary] $groupsReturnHashTable = (New-Object System.Collections.Specialized.OrderedDictionary)
[System.Collections.Specialized.OrderedDictionary] $loopsReturnHashTable = (New-Object System.Collections.Specialized.OrderedDictionary)
[System.Collections.Specialized.OrderedDictionary] $membersReturnHashTable = (New-Object System.Collections.Specialized.OrderedDictionary)
Get-ADGroupLoops `
-Identity $startGroup `
-TempWorkHashTable ([ref]$tempWorkHashTable) `
-GroupsReturnHashTable ([ref]$groupsReturnHashTable) `
-LoopsReturnHashTable ([ref]$loopsReturnHashTable) `
-MembersReturnHashTable ([ref]$membersReturnHashTable) `
-Verbose
"—-Groups——-"
$groupsReturnHashTable
"—-Members——-"
$membersReturnHashTable
"—-Loops——-"
$loopsReturnHashTable

view raw

Get-ADGroupRecursive.ps1

hosted with ❤ by GitHub


# Author: Jana Sattainathan – https://sqljana.wordpress.com – September 1, 2020
#Returns all the groups
function Get-Group
{
#Notice the loops
# Group1 > Group3 > Group1
# Group1 > Group8 > Group5 > Group15 > Group1.
@{
"Group1" = "User1,User2,Group2,Group8";
"Group2" = "User1,User2,User3,Group3"
"Group3" = "User3,User8,Group1"
"Group4" = "Group8,User1"
"Group5" = "User10,Group15"
"Group6" = "User10, User11"
"Group7" = "User11"
"Group8" = "Group5"
"Group15" = "Group1"
}
}
#Returns all the members of a give group as an array
function Get-GroupMember
{
param (
[Parameter()]
[string]$Identity = 'Group1'
)
$groups = Get-Group
if ($groups.ContainsKey($Identity) -eq $true)
{
$groups[$Identity].Split(",")
}
else
{
@()
}
}
#Returns true if if parameter is a Group, else false
function Test-Group
{
param (
[Parameter()]
[string]$Identity = 'Group1'
)
$groups = Get-Group
$groups.ContainsKey($Identity)
}
#Gets all the loops (ie., at some point members of groups are groups already traversed in hierarchy)
function Get-GroupLoops
{
param (
[Parameter()]
[string]$Identity = 'Group1',
[Parameter()]
[System.Collections.Specialized.OrderedDictionary][ref] $TempWorkHashTable = (New-Object System.Collections.Specialized.OrderedDictionary),
[Parameter()]
[System.Collections.Specialized.OrderedDictionary][ref] $GroupsReturnHashTable = (New-Object System.Collections.Specialized.OrderedDictionary),
[Parameter()]
[System.Collections.Specialized.OrderedDictionary][ref] $MembersReturnHashTable = (New-Object System.Collections.Specialized.OrderedDictionary),
[Parameter()]
[System.Collections.Specialized.OrderedDictionary][ref] $LoopsReturnHashTable = (New-Object System.Collections.Specialized.OrderedDictionary)
)
[bool] $loopBeginning = $false
[string] $fullHierarchyString = ""
[string] $loopString = ""
#If this is group and not an individual
if (Test-Group -Identity $Identity)
{
Write-Verbose "Working on: $Identity"
if (!$GroupsReturnHashTable.Contains($Identity))
{
$GroupsReturnHashTable.Add($Identity, $Identity)
}
#Get the members of the group
$members = Get-GroupMember -Identity $Identity
#If this we have not seen this group before
if (!$TempWorkHashTable.Contains($Identity))
{
$TempWorkHashTable.Add($Identity, $Identity) | Out-Null
$members | foreach {
#This is the recursive call to itself
$members = Get-GroupLoops `
-Identity $_ `
-TempWorkHashTable ([ref]$TempWorkHashTable) `
-GroupsReturnHashTable ([ref]$GroupsReturnHashTable) `
-MembersReturnHashTable ([ref]$MembersReturnHashTable) `
-LoopsReturnHashTable ([ref]$LoopsReturnHashTable)
}
}
else
{
#We have already seen this group before. That is the starting point of the loop
# and we have to print and remove all elements in the Ordered dictionary from that element that form the loop
[HashTable] $keysToRemove = @{}
foreach($key in $TempWorkHashTable.Keys)
{
if ($key -eq $Identity)
{
$loopBeginning = $true
}
$fullHierarchyString = $fullHierarchyString + "->" + $key
if ($loopBeginning -eq $true)
{
$keysToRemove.Add($key, $key)
$loopString = $loopString + "->" + $key
}
}
#The full hierarchy and loop
$fullHierarchyString = $fullHierarchyString + "->" + $Identity
$loopString = $loopString + "->" + $Identity
foreach($key in $keysToRemove.Keys)
{
$TempWorkHashTable.Remove($key)
}
#DN,oGroup
$TempWorkHashTable.Add($Identity, $Identity)
Write-Verbose "Hierarchy: $fullHierarchyString"
Write-Verbose "Loop: $loopString"
$LoopsReturnHashTable.Add($loopString, $fullHierarchyString) | Out-Null
$fullHierarchyString = ""
$loopString = ""
}
}
else
{
## It is not a group..just a regular user
if (!$MembersReturnHashTable.Contains($Identity))
{
$MembersReturnHashTable.Add($Identity, $Identity)
}
}
}
#—————————————-
#Sample code to test the functions above
#—————————————-
$startGroup = 'Group1'
[System.Collections.Specialized.OrderedDictionary] $tempWorkHashTable = (New-Object System.Collections.Specialized.OrderedDictionary)
[System.Collections.Specialized.OrderedDictionary] $groupsReturnHashTable = (New-Object System.Collections.Specialized.OrderedDictionary)
[System.Collections.Specialized.OrderedDictionary] $loopsReturnHashTable = (New-Object System.Collections.Specialized.OrderedDictionary)
[System.Collections.Specialized.OrderedDictionary] $membersReturnHashTable = (New-Object System.Collections.Specialized.OrderedDictionary)
Get-GroupLoops `
-Identity $startGroup `
-TempWorkHashTable ([ref]$tempWorkHashTable) `
-GroupsReturnHashTable ([ref]$groupsReturnHashTable) `
-LoopsReturnHashTable ([ref]$loopsReturnHashTable) `
-MembersReturnHashTable ([ref]$membersReturnHashTable) `
-Verbose
"—-Groups——-"
$groupsReturnHashTable
"—-Members——-"
$membersReturnHashTable
"—-Loops——-"
$loopsReturnHashTable

view raw

Get-GroupRecursive.ps1

hosted with ❤ by GitHub

The sample usage code is at the bottom of the code too. Just replace the AD group name with the appropriate one and give it a try. The return values are “Loop strings” but since you have the source code change it as you please!

Lessons Learned:

  • Keep it simple, then extrapolate/decorate/complicate
  • Variables don’t retain their state when recursion winds or unwinds (pass by reference)
  •  Pass in the “work” and “return” HashTables as parameters so as to not worry about knowing beginning and end of recursion
  • Could return a single object as output but multiple “by reference” parameters work well too since they also output!

2 thoughts on “PowerShell: Recursion And Finding Loops In A Hierarchy With Active Directory Example”

  1. Pingback: Finding Loops in an Active Directory Hierarchy – Curated SQL

  2. Hello, I noticed that this script has an infinite loop for the group “Group2”
    startGroup = ‘Group2’

    As Group8 and Group2 are in same level.

    Reply

Leave a comment