Recording my stupid roles system somewhere.

1 files changed, 110 insertions, 0 deletions

diff --git a/wiki/authnz/users-rolegraph-privs.md b/wiki/authnz/users-rolegraph-privs.md
new file mode 100644
index 0000000..fdbf52d
--- /dev/null
+++ b/wiki/authnz/users-rolegraph-privs.md
@@ -0,0 +1,110 @@
+# A Users, Roles & Privileges Scheme Using Graphs
+
+The basic elements:
+
+* Every agent that can interact with a system is represented by a **user**.
+* Every capability the system has is authorized by a distinct **privilege**.
+* Each user has a list of zero or more **roles**.
+    * Roles can **imply** further roles. This relationship is transitive: if
+      role A implies role B, then a member of role A is a member of role B; if
+      role B also implies role C, then a member of role A is also a member of
+      role C. It helps if the resulting role graph is acyclic, but it's not
+      necessary.
+    * Roles can **grant** privileges.
+
+A user's privileges are the union of the privileges granted by the transitive
+closure of their roles.
+
+## In SQL
+
+    create table "user" (
+        username varchar
+            primary key
+        -- credentials &c
+    );
+    
+    create table role (
+        name varchar
+            primary key
+    );
+    
+    create table role_member (
+        role varchar
+            not null
+            references role,
+        member varchar
+            not null
+            references "user",
+        primary key (role, member)
+    );
+    
+    create table role_implies (
+        role varchar
+            not null
+            references role,
+        implied_role varchar
+            not null
+    );
+    
+    create table privilege (
+        privilege varchar
+            primary key
+    );
+    
+    create table role_grants (
+        role varchar
+            not null
+            references role,
+        privilege varchar
+            not null
+            references privilege,
+        primary key (role, privilege)
+    );
+
+If your database supports recursive CTEs, querying this isn't awful, since we
+can have the database do all the graph-walking along roles:
+
+    with recursive user_roles (role) AS (
+        select
+            role
+        from
+            role_member
+        where
+            member = 'SOME USERNAME'
+        union
+        select
+            implied_role as role
+        from
+            user_roles
+            join role_implies on
+                user_roles.role = role_implies.role
+    )
+    select distinct
+        role_grants.privilege as privilege
+    from
+        user_roles
+        join role_grants on
+            user_roles.role = role_grants.role
+    order by privilege;
+
+If not, get a better database. Recursive graph walking with network round
+trips at each step is stupid and you shouldn't do it.
+
+Realistic uses should have fairly simple graphs: elemental privileges are
+grouped into abstract roles, which are in turn grouped into meaningful roles
+(by department, for example), which are in turn granted to users. In
+PostgreSQL, the above schema handles ~10k privileges and ~10k roles with
+randomly-generated graph relationships in around 100ms on my laptop, which is
+pretty slow but not intolerable. Perverse cases (interconnected total
+subgraphs, deeply-nested linear graphs) can take absurd time but do not
+reflect any likely permissions scheme.
+
+## What Sucks
+
+* Graph theory in my authorization system? It's more likely than you think.
+* There's no notion of revoking a privilege. If you have a privilege by any
+  path through your roles, then it cannot be revoked except by removing all of
+  the paths that lead back to that privilege.
+* Not every system has an efficient way to compute these graphs.
+    * PostgreSQL, as given above, has a hard time with unrealistically-deep
+      nested roles.