The Third Bit

Poor Cousins

Four weeks left until the summer’s work on Hippo (formerly Helium)
winds down, and we’re starting to run into the 10% of cases that make
up 90% of the grief. For example, consider the problem of keeping
track of the relationships between users and projects. In SourceForge and other systems, this is a
simple pairwise relationship: projects are not related to one another,
and users do not belong to groups (other than the groups implicitly
formed by their membership in particular projects).

That’s not good enough for Hippo. Students are naturally grouped
by the courses they belong to; instructors must be able to do
groupwise operations (such as making all students in course C members
of project P) in a single step, or Hippo’s administrative overhead
will be prohibitive. Similarly, instructors must be able to manage
batches of projects at once, so that they can do things like delete
all projects associated with Exercise 3 of Course C with a single
command (after backing them up, of course).

To handle this, we’ve organized projects as a tree, and users/user
groups as a graph. A single root “super project” represents Hippo as
a whole; every other project must have a parent. Similarly, users can
belong to groups, which can also contain other groups (though cycles
are not permitted).

Now comes the tricky part. A user U’s relationship to a project P
is described by one of a small set of roles, such as “observer”,
“developer”, or “admin”. (A fourth role, “unaffiliated”, isn’t
explicitly represented, but is used when U has no other relationship
with P.) Relationships are inherited: if U has no relationship to P,
but does have a relationship R with P’s parent Q, U also has
relationship R with P. This means that if an instructor is an admin
of the project “/csc207″, then she is also automatically an admin of
“/csc207/exercise01″, “/csc207/exercise01/studentFred”, and so on.

Relationships are also inherited via group membership. If U has no
relationship with P, but U is a member of a group G, and G has a
relationship R with P, then U has relationship R with P as well. For
example, if a student is a member of the group “csc207Students”, and
“csc207Students” is an observer of “/csc207″, then the student is an
observer of “/csc207″.

Seems pretty simple—at least, it seemed pretty simple to
us. However, inheritance means that a user U can have several
different candidate relationships with a project P. For example, U
can be an explicit observer of P, but also be a member of a group G,
which is a developer for P’s grandparent. Which relationship should U
have with P? We decided two and a half months ago to use the
“strongest” relationship: we find all possible relationships via
transitive closure, and if any of them allow U to perform a requested
operation on P, the operation is permitted.

The problem is, that leads to Bug
#36:

Users are allowed to have multiple memberships to a single project,
both through inheritance and through user groups. When a user wants
to change something (ie mail settings), the getMemberships(user,
project) method has to decide which of these memberships to return.
Currently, it returns the user’s strongest membership, based on role.
The problem with this is that if the user’s strongest membership is an
implicit one, or if it is through a user group, the user is unable to
change the settings (unless an explicit membership is created for the
user and project).

Let’s go over that again. Hippo represents relationships between
users and projects using instances of the class Membership. If
membership is implied, rather than direct, then when we look up U’s
membership in P, we sometimes get back an object representing the
relationship between a group that U belongs to (directly or
indirectly) and a project that is a parent of P (directly or
indirectly). That’s fine if we just want to find out whether or not
some operation is permitted, but if we want to change U’s
relationship with P, what do we do? We can’t change that relationship
object, since that would potentially affect other users’ relationships
with other projects.

OK, so we don’t change that object; we add a new one representing
the more specific relationship. That solution fails to address Bug
#37:

Another problem with implicit memberships: users cannot be deleted
from projects (or have their roles changed etc.) when their membership
is via a user group, unless they are removed from the group. Removing
a user from a user group falls under user-user authorization, which
has been deferred.

And on, and on, and on. Representing all relationships
explicitly (no groups, no project tree) would make this problem go
away, but we believe it would make administration much more onerous.
Adopting Unix-style permissions (rwxr-xr–, anyone?) is tempting, but
we worked through that three months ago, and it doesn’t address all of
our use
cases either.

Which brings us to this posting’s title. HP’s marketing literature
describes the product I work on in terms of authentication,
authorization, and access control. Authentication means figuring out
who you are; authorization means figuring out what you’re allowed to
do; and access control means enforcing those rules. There’s a ton of
literature about authentication, and a fair bit in the operating
systems world about access control. By comparison, authorization is a
very poor cousin indeed: you can find detailed descriptions of the
schemes used in particular systems, like Unix permissions and Access
Control Lists (ACLs), but there doesn’t seem to be any “theory” behind
it all.

Authorization seems to be one of those things that is overlooked by mainstream computing, for no good reason. Think about it: parsing and code generation are part of the standard curriculum, but implementing byte code interpreters and debuggers are not; process scheduling is, but linking is not; and so on. I don’t know why some fields are “poor cousins”, while others are so heavily overfarmed that they suffer from the intellectual equivalent of salinization, but perhaps there is scope here for both innovative research, and for new languages or programming models to make some headway.