Katkat
Back

First-Match Login Policy Engine with a Boolean Expression DSL

StripeSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteSoftware Engineering Fundamentals

Last updated

Implement an ordered allow/deny policy evaluator for sign-in attempts whose conditions grow from symmetric string equality to boolean flags, and/or precedence, parentheses, not and !=. Tests tokenizing quoted literals, recursive-descent parsing, first-match semantics, and missing-field handling.

You are writing the policy engine behind a login-protection service. Each sign-in attempt arrives as a dict of attributes, and security admins write an ordered list of policies. Each policy has a verdict and a condition written in a tiny expression language.

def decide(attempt: dict, policies: list[tuple[str, str]]) -> str:
    ...
  • policies is a list of (verdict, condition) pairs, where verdict is "allow" or "deny".
  • Check the policies in order. The first policy whose condition is true decides the result.
  • If no condition is true, return "allow".
  • Policies are always syntactically valid.

Language

  • String literals use single quotes: 'BR'. Inside a literal, \' is a quote and \\ is a backslash.
  • Identifiers ([A-Za-z_][A-Za-z0-9_]*) are attribute names.
  • An attribute that is missing from attempt makes any comparison that uses it false, and makes it false when used as a flag.

Part 1: equality and order

Support conditions of the form operand = operand, where each side is either an attribute or a literal and either may come first. country = 'BR' and 'BR' = country mean the same thing.

attempt = {"country": "BR", "app": "mobile"}
policies = [("deny", "country = 'RU'"), ("allow", "'mobile' = app"), ("deny", "app = 'mobile'")]
decide(attempt, policies)  # "allow": the second policy is the first to match

Part 2: flags with and / or

Attributes can hold booleans. A bare attribute name is a condition that is true when the value is True. Combine conditions with and and or (lowercase keywords), where and binds tighter than or.

attempt = {"country": "BR", "new_device": True, "mfa_passed": False}
decide(attempt, [("deny", "new_device and mfa_passed or country = 'KP'"),
                 ("deny", "country = 'BR' and new_device")])   # "deny" (second policy)

The first condition reads as (new_device and mfa_passed) or country = 'KP', which is false.

Part 3: parentheses, not, !=

Add grouping with parentheses, a prefix not (which binds tighter than and), and !=. A != comparison is also false when either attribute is missing.

attempt = {"country": "DE", "new_device": True, "mfa_passed": False, "app": "web"}
decide(attempt, [
    ("deny", "new_device and not (mfa_passed or app = 'kiosk')"),
    ("allow", "true_flag"),
])  # "deny"
decide({"country": "DE", "app": "it\'s"}, [("deny", r"app = 'it\'s' and country != 'FR'")])  # "deny"

Each part must keep the behavior of the earlier ones. Expect up to 10^4 policies, each evaluated against a stream of attempts, so think about what you can compute just once.

Hints

Hint 1

Classify tokens (literal, identifier, operator, keyword) before parsing, so the side a constant appears on does not matter.

Hint 2

Write one parsing function per precedence level: or, then and, then not, then primary.

Hint 3

Represent a missing attribute with a sentinel that makes every comparison false.

Hint 4

Conditions don't change between attempts. Parse each one once and cache the tree.

Follow-up questions

  • Add numeric comparisons such as risk_score >= 70. How do you handle type mismatches?
  • How would you report a helpful error with a column position for a malformed policy?
  • With 10^4 policies and 50k attempts per second, how could you avoid evaluating every policy (indexing on equality predicates, for example)?
  • Admins want to know which policy matched and why. How would you produce an explanation trace?