Tuesday, March 20, 2007

Transitive Link Value Filter Evaluation

I was speaking with Eric Fleischman at the MVP summit this year and he told me about a neat feature you will find in Window Server 2003 SP2 and Longhorn server.  It is a new type of matching rule ID filter that allows for transitive link value evaluation.  This is one filter type that is incredibly useful and you will want to know about.

First some background: a matching rule ID filter is a special syntax filter that allows for an arbitrary search behavior as defined by the matching rule.  Active Directory and ADAM only shipped with two matching rules until recently: LDAP_MATCHING_RULE_BIT_AND (1.2.840.113556.1.4.803) and LDAP_MATCHING_RULE_BIT_OR (1.2.840.113556.1.4.804).  We commonly used these matching rules to check our bitwise flag values.  For instance, here is the key portion of the filter that specifies an account is disabled:


Notice that we have the attribute name we are searching on, the rule OID we want to use (the AND rule), and the value to check (in decimal).  Pretty simple, right?

The new matching rule is called LDAP_MATCHING_RULE_IN_CHAIN and it has an OID of 1.2.840.113556.1.4.1941.  This new rule allows us to search across all DN-syntax attributes recursively and evaluate the entire tree of relationships (hence the transitive name).

Evaluating Group Membership

Where we will typically see this used is in group membership evaluation.  Specifically, it answers two questions that are constantly asked by developers:  What groups are my user a member of? and What users are in this group?

It is really simple to use this filter, so here we go.  The first question is, what groups is my user a member of?


The next question, what users are in this group?

(memberOf:1.2.840.113556.1.4.1941:=CN=A Group,OU=Y,DC=domain,DC=com)

If we place base this search on the main partition and use a subtree search, it will return for us all the matches across the domain.  However, if we scope the second search to a specific user object and use a base search, it is a quick and dirty way of telling us if the user is a member of the group.  Hence, this would also work for a type of IsInRole() function:

public bool IsUserMember(DirectoryEntry user, string groupDN)
    string filter = String.Format(
        "(memberOf:1.2.840.113556.1.4.1941:={0})", groupDN);

    DirectorySearcher ds = new DirectorySearcher(

    return (ds.FindOne() != null);

Now, I want to also point out that this sort of code also makes me cringe a little bit thinking about the abuse that can occur...  Remember, it is performing a search each and every time you want to check group membership.  It is still a better idea to build the entire group membership of a user and store it in one of the IPrincipal classes and use the .IsInRole() functionality to keep network access to a minimum.

Creating an Org Chart

The other area where we will find this filter being pretty handy is when we want to find all the users that directly and indirectly report to a single person.  This is the typical situation when building org charts or trying to find the users for a mailing list.  Here is one such example:

public static void GetOrgChart(DirectoryEntry entry, string bossDN)
    string filter = String.Format(

    DirectorySearcher ds = new DirectorySearcher(

    using (SearchResultCollection src = ds.FindAll())
        foreach (SearchResult sr in src)


The next question we will want to answer for this new filter type is the performance relative to the code required to process this recursively.  I will use the code I presented here to test the recursive case and compare it to a simple filter of:


So, to cut to the chase, how does the new filter compare to recursively chasing DN link pairs yourself?  Short answer... it doesn't.  The code I wrote for the book and here on the blog blows it away by a factor of 10.  I have to admit that before I ran the tests, I expected the new filter to run circles around my code and I was pretty shocked when the reverse was actually true.  I tested this using 3 nested groups each with 100 members and running both the recursive search and the transitive search 100 times and averaging the results.  To expand the lead group with 300 direct and indirect members took roughly half a second using a transitive filter (409ms) as compared to only (41ms) using the recursive search.  This would have a big impact on server apps serving many of these searches, but would probably not be a huge factor in client side apps or where a smallish number of these searches are performed.


The transitive filter is a great new addition and can greatly simplify the code that you have to write.  This new filter is not without pitfalls however.  Make sure you are cognizant of the performance tradeoffs that are inherent in choosing this filter as it is considerably slower to use.