Who Can Do What? IAM Policy Evaluator

The story

Every cloud request ("may alice read this bucket?") is answered by an authorisation engine that looks at the attached policies. The rules are simple to say and easy to get wrong, and getting them wrong is how data leaks happen:

1. Everything is denied by default (an implicit deny).
2. A matching Allow statement can open a door.
3. A matching Deny statement always wins, wherever it is written and however many allows match.

You are going to build that engine for a tiny policy language.

The task

Read some policy statements, then a list of requests, and print the decision for each request.

Input:

• Lines starting with # and blank lines are ignored.
• Statements, one per line: EFFECT principal action resource, optionally followed by when key=pattern .... EFFECT is ALLOW or DENY. All tokens are separated by spaces.
• A line containing only --- ends the statements.
• Requests, one per line: principal action resource, optionally followed by attributes key=value ....

Patterns (principal, action, resource and condition values) are matched against the whole text, case-sensitively, with two wildcards: * matches any run of characters (including none, and including / and :), and ? matches exactly one character. Every other character is literal, including ., +, ( and [. Policies may contain many *, so your matcher must stay fast.

A statement applies to a request when its principal, action and resource patterns all match and every key=pattern condition is met: the request carries an attribute key and its value matches the pattern. A request without that attribute does not meet the condition.

Decision, per request, one line:

• DENY explicit: at least one applicable DENY statement;
• else ALLOW: at least one applicable ALLOW statement;
• else DENY implicit.

Example

ALLOW * s3:GetObject arn:aws:s3:::reports/*
ALLOW alice s3:PutObject arn:aws:s3:::reports/drafts/*
DENY * s3:* arn:aws:s3:::reports/secret/*
---
alice s3:GetObject arn:aws:s3:::reports/q1.csv
alice s3:GetObject arn:aws:s3:::reports/secret/plan.txt
bob s3:PutObject arn:aws:s3:::reports/drafts/a.txt

Output:

ALLOW
DENY explicit
DENY implicit

The first request matches the first allow. The second also matches the allow, but the DENY on reports/secret/* wins. The third is a PutObject by bob, and the only statement that covers it names alice, so nothing allows it.

ALLOW * s3:GetObject arn:aws:s3:::reports/*
ALLOW alice s3:PutObject arn:aws:s3:::reports/drafts/*
DENY * s3:* arn:aws:s3:::reports/secret/*
---
alice s3:GetObject arn:aws:s3:::reports/q1.csv
alice s3:GetObject arn:aws:s3:::reports/secret/plan.txt
bob s3:PutObject arn:aws:s3:::reports/drafts/a.txt