Skip to content
Tutorials Center
My learning

Topics

Lesson 37 of 38 ยท Projects and Practice

Project: Build an LDAP Filter Engine in Python

Build a small LDAP search filter parser and evaluator in Python: tokenise RFC 4515 syntax, handle AND, OR, NOT, substrings, comparisons and the bitwise matching rule, and query an in-memory directory.

The best way to understand LDAP search filters is to implement them. In this project you write a parser and evaluator for the filter language that Active Directory understands: (&(objectClass=user)(department=Finance)(!(userAccountControl:1.2.840.113556.1.4.803:=2))). By the end you can run real-looking queries against an in-memory directory, and you will know exactly why a filter matches or does not.

Everything here is a Python stand-in that runs in your browser. It is not an LDAP client and has no network access; it implements the filter semantics in the style of RFC 4515 for a useful subset. The real server uses the same ideas, with indexing and schema rules on top.

The grammar

A filter is always wrapped in parentheses and is one of:

Form Example Meaning
AND (&(a=1)(b=2)) All sub-filters must match
OR (|(a=1)(b=2)) At least one matches
NOT (!(a=1)) The sub-filter does not match
Equality (cn=Alice) Attribute equals value (case-insensitive for most attributes)
Presence (mail=*) The attribute has any value
Substring (cn=Al*ce*) Wildcards match any text
Greater or equal (age>=30) Comparison (numeric when both are numbers)
Less or equal (age<=30) Comparison
Extensible match (userAccountControl:1.2.840.113556.1.4.803:=2) Matching rule by OID: bitwise AND

Values escape special characters as \2a, \28, \29, \5c (escaping). Attribute names are case-insensitive, and attributes may be multi-valued (a list), such as memberOf. A filter matches an entry if the attribute has any value that satisfies the test.

Step 1: parse into a tree

A recursive descent parser reads one parenthesised filter at a time. Operators &, | and ! are followed by one or more filters; everything else is an attribute test. The parser returns nested tuples such as ("and", [...]), which the evaluator then walks.

Step 2: evaluate against an entry

Evaluation is a small recursive function. For each leaf test, it looks up the attribute (case-insensitively), then checks each value. For the extensible form it supports the two Active Directory rules you meet most often:

  • 1.2.840.113556.1.4.803 (LDAP_MATCHING_RULE_BIT_AND): the value matches if attribute & mask == mask.
  • 1.2.840.113556.1.4.804 (LDAP_MATCHING_RULE_BIT_OR): the value matches if attribute & mask != 0.

The in-chain rule 1.2.840.113556.1.4.1941 walks group nesting. The engine below does not implement it; adding it is one of the extension tasks at the end.

The full engine

Python LDAP filter parser and evaluator

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Check the results against what you expect. userAccountControl 514 is 512 (normal account) plus 2 (disabled), so Bob is excluded by the NOT-bit test. Carol's 66048 is 512 plus 65536 (the password never expires flag), so only she matches the last bitwise query.

Handling mistakes

A real server returns an error for a malformed filter. Your parser should do the same, with a useful message. Try these in the runner:

Python Bad filters and error messages

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Performance thinking

A real directory does not scan every entry. It uses indexes on attributes such as sAMAccountName, objectClass, mail and cn, picks the most selective one, and then checks remaining conditions on the candidates. That is why:

  • A filter starting with an unindexed attribute, or one with a leading wildcard ((cn=*son)), makes the server examine many entries.
  • Bitwise matching rules and in-chain evaluation cannot use an index and are expensive on big domains.
  • (!(attr=x)) conditions are evaluated after narrower conditions; write the selective test first in an AND, and keep NOT clauses inside an AND with a selective part.
  • Searches should always have a base DN, a scope and a size limit.

You can mimic the idea in your engine: add an index dictionary from sAMAccountName to entries, and let equality on indexed attributes skip the full scan.

Extension tasks

  1. Support ~= (approximate) with a simple phonetic or edit-distance rule.
  2. Implement IN_CHAIN for memberOf by adding nested groups to the directory and following parent groups recursively.
  3. Add scope (base, one, sub) by matching the entry's DN suffix.
  4. Add attributes so the search returns only selected attributes, and a size limit that raises sizeLimitExceeded.
  5. Count how many entries each query scans with and without an index.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does the filter (!(userAccountControl:1.2.840.113556.1.4.803:=2)) select in Active Directory?

    Bit 2 of userAccountControl means ACCOUNTDISABLE; the NOT inverts it.
  2. 2. Which filter matches entries that have any mail value?

    The presence filter uses an asterisk with equality.
  3. 3. Which is the correct form of an OR filter?

    LDAP filters use prefix notation: the operator comes first, followed by parenthesised sub-filters.
  4. 4. Why is (cn=*son) slower than (cn=Wilson)?

    An index can find a known prefix quickly, but not an unknown start.

Summary

  • LDAP filters are prefix-notation trees of &, |, ! and attribute tests in parentheses.
  • Presence, substring, comparison and extensible matching rules cover most queries; bitwise rules read flags such as userAccountControl.
  • A recursive parser plus a small evaluator reproduces the semantics, which makes debugging real filters much easier.
  • Real servers rely on indexes, base DNs, scopes and limits; write selective filters.

Next: Practice: Active Directory Scenarios