RMAC FTW (part 1)

once again into the breach

no, not Rambunctious Models Artfully Concealing Faded Temptress Wrinkles, it’s even better.

those of you who have been following the PermissionableBehavior know that the goal of the behavior is to help achieve a RBAC-like system to control not only access to specific parts of an application, but also row-level permissions on data in the application.  i released an initial prototype of the behavior a couple weeks ago, and it was fairly well-received.

i’ve refactored a little bit, and per popular demand, i’ll also be supplying a sample implementation for those of you who prefer learning by example.  first though, i thought i would take a step back and try to outline the overall design and how it works.

a shave and a haircut, 9 bits

bit(mask)s are a wonderful and compact way to keep track of multiple booleans.  i’m not even going to attempt to explain why, since wikipedia can do it so much better. until you get the hang of them they can be a little confusing, but they are really just a different (and far more basic) way of looking at what you are already used to.  let’s look at some examples, in which i’ll limit to be relevant to the PermissionableBehavior.

let’s set the parameters.  the bit definitions for the row action we want to limit are:

  • Owner
    • Read – 256
    • Write – 128
    • Delete – 64
  • Group
    • Read – 32
    • Write – 16
    • Delete – 8
  • Other
    • Read – 4
    • Write – 2
    • Delete – 1

notice that the numbers for the permissions increase in powers of 2.  i’ll not go into why this works, since it’s covered elsewhere, but sufficed to say that bitwise, each number is distinct and non-inclusive of the other numbers (256 does not contain 128, 128 does not contain 64, etc).

ok, now imagine the permissions that we want to assign to an item as a binary number.  trust me, it’s actually easier:

Owner Group Other Decimal
R W D R W D R W D Permission
0 0 0 0 0 0 0 0 0 000

this bitmask indicates that no one has any permission to a record with these bits set (or unset, actually).  now let’s look at a more real-world example:

Owner Group Other Decimal
R W D R W D R W D Permission
1 1 0 1 1 0 1 0 0 436

what’s going on here?  the binary number 110110100 == the decimal number 436 (256+128+32+16+4, according to the numbers i assigned above).  storing the number 436 as the permission bit on a record would reflect that the owner of the record can read/write, the group owner(s) of the record can read/write, and all others (non-owners) can read.  with bitwise operators, it’s trivial to see if a permission bit has required permissions.

for example, let’s use the “&” (AND) bitwise operator to see if the row’s permission bit contains the bit that says that the owner can delete the row (64).

$allowed = ((436 & 64) <> 0);
Owner Group Other Decimal
R W D R W D R W D Permission
Row 1 1 0 1 1 0 1 0 0 436
Requested 0 0 1 0 0 0 0 0 0 64

how does this work?  since (436 & 64) equals 0, then the request for owner to delete would be denied, as the row permission does not contain 64. the ‘&’ operator tests returns which bits are set in both numbers.  as you can see above, there is no column in which both have 1 set, thus returning ’0′.

NOTE:  you must enclose the bitwise operation in parentheses or you will get false positives.  due to the logical order in which the operation is processed, if you tried to do (426 & 64 <> 0), it would return true, since the “not 0″ portion is processed first.  additionally, unless you have a firm grip on your variable types, i recommend typecasting all your variables as integers, e.g. ((int) $x & (int) $y) <> 0), since if either variable is string, then you’ll get bizarre results.

now for an example where the request is allowed:

Owner Group Other Decimal
R W D R W D R W D Permission
Row 1 1 0 1 1 0 1 0 0 436
Requested 0 0 0 0 0 0 1 0 0 4

now, notice that in the Other Read column, both numbers have the bit set. and so (436 & 4) would return ’4′, indicating that both numbers have the ’4′ bit set.

NOTE: there are several ways to test using this operator. i use (x & y) <> 0, when you can also use (x & y) == y. the latter will work in most scenarios, but in the PermissionableBehavior i have some places where permissions are inherited, and so the returned number is sometimes a product of shared bits, meaning it returns neither 0 or the mask. in either case, <> will work.

2 bits walk into a |, and the operator says “2″

so far i’ve been using the permission bits for example, but all the above also applies to the group bits assigned to a row.  this works the same way permissions do, ala:

  • Root – 1
  • Global – 2
    • Internal – 4
      • Dept. A – 8
      • Dept. B – 16
    • External – 32
      • Client A – 64
      • Client B – 128

now, here is one of the drawbacks of this approach.  you are limited to the number of bits in an integer, whatever your architecture supports.  in the case of 32bit, this equates to 32 groups, and 64bit, 64 groups.  this isn’t a problem for me, and i’m sure there are ways to get around this (hashing, bribery, etc), but i’ll not address this until i actually have a polished version of the behavior (or need more than 32 groups!).

anyway.  as i said, what applied for permission bits works the same for group bits.  let’s assume we have a user who is in Dept. B.  in the PermissionableBehavior, i traverse the groups tree and add up all the bits for the groups that the user is part of.  be careful, since you can’t just add up using arithmetic since any duplication of bits would produce inaccurate results.  the group bits for a user in Dept. B would be 22 (16 | 4 | 2).  note the use of the “|” (OR) operator.  this operator works by returning the bits that are set in both sets of numbers.  since none of the bits in the group path for Dept. B are inclusive (16 does not include 4 or 2, 4 does not contain 2), the result is the the bits added up and we get 22.  but what if the user was in multiple groups?  let’s say the user is in Dept. B and Client A groups.  if we iterated each group and added up it’s path, we’d get 120.  this would be wrong, as it includes the ‘Global’ bit (2) twice, thus skewing the resulting bits.  the right way would be to use bitwise OR, like so (64 | 32 | 2 | 16 | 4 | 2), which gives us a group bits of 118.  Now for the real-world example:

if a row in the database has a group bits of 96, we can test whether or not someone has access to the group owner permissions by comparing their cumulative group bits with the rows.

$is_group_owner = ((96 & 118) <> 0);

since (96 & 118) returns ’96′, that being the bits that are shared by both numbers, we know that the user in question has access to the group permissions, in that he is in at least one group that the row is also in.

group bits + permission bits == unix delicious

so, now that we’ve covered how the group and permission bits work, i’ll show how these method actually limit the results from a database query, so that a user is only able to perform allowed actions.

first off, let’s go for the simple case: selecting rows from a table.  let’s set the parameters first.  User A is in the groups Dept. A and Client B.  her ID in the users table is 100 (for example), and her group bits are 118.  she performs a query via $groupModel->find(‘all’).  without the Permissionable behavior, the query would look something like this:

SELECT `Group`.*
  FROM `groups` AS `Group`

with the PermissionableBehavior however, the same $groupModel->find(‘all’) would result in this query (and i apologize again for not having syntax formatting/highlighting… does anyone recommend a free webhost?):

SELECT `Group`.*, `PermissionModel`.*
  FROM `groups` AS `Group`
  INNER JOIN permissions AS `PermissionModel` ON (
    `PermissionModel`.`model` = 'Group'  AND -- since the PermissionModel is polymorphic, we need to limit to rows that have to do with the primary model
    `PermissionModel`.`foreign_key` = `Group`.`id` AND  
      (`PermissionModel`.`permission` & 4 <> 0) OR  -- first check for 'other read' permission
          (`PermissionModel`.`permission` & 32 <> 0) AND -- otherwise 'group read'
          (`PermissionModel`.`group_bits` & 118 <> 0) -- assuming the user and the row share a group
        ) OR (
          (`PermissionModel`.`permission` & 256 <> 0)  AND -- otherwise 'owner read'
          (`PermissionModel`.`user_id` = '100') -- assuming the user is the row owner

now, i’m sure several of you are looking at that and thinking “bleeding jesus h. christ on a pogostick, that’s a lot of parentheses”, but they are necessary and not really all that complex.  i should blog about the queries i had to write for a database that had +1 billion rows… but i digress; the query, while more than twice as “long” as the previous, really doesn’t incur any overhead, especially when your tables are properly indexed. what’s nice about this approach is that the original query was modified to filter out rows in the primary table that do not have the appropriate permissions. in this case we’ve specified “read” permissions (owner – 256, group – 32, other – 4) as our criteria. we’ve only applied the owner read permission condition if the user is indeed the owner, and the group permission only if the row and the user share at least one group, or if the row has an ‘other read’ bit set.  on my modest macbook pro, this takes less than a millisecond to query, and EXPLAIN tells me that the query is using only simple selects, constant and indexed references with only a WHERE for the inner join.

stop teaching me how to fish, just give me a fish dammit

alright, as promised, here’s the example application that you can just unarchive (over a fresh cake install) and play with: ZOMG Download ME!!!!1

a couple things i didn’t explain before, but bear mentioning:

  • the order in which you add the behavior to your models (most notably  Tree’d models) is very important.  i’d recommend putting Permissionable first, in most cases.
  • if you don’t use AuthComponent to authenticate your users, you’ll need to make sure that any query that it does on a permissioned model includes ‘permissions’ => false in it’s conditions
  • oh yeah, you can disable the behavior runtime by either:
    • including ‘permissions’ => false in your query conditions.
    • calling $model->disableChecks() to disable just permission checking.
    • calling $model->disableCreation() to disable, you guessed it, permission creation.
    • or by calling $model->disable() to shut the whole thing down.
    • to enable again, just call $model->disable(false), or write a method called ‘enable’.  i dare you.
  • you can add considerably more permissionable actions, so long as you keep incrementing the bits by the power of two.  please only do so if you understand what you are doing, since you’ll have to shift the permission bits around (at least i would, so they would remain pretty), and most likely re-test the whole thing since i didn’t really code with that in mind. although it should work.
  • i make no claims about this being perfect.  i haven’t tested in with all other core behaviors, and there still may be weirdness that may crop up.  YMMV, caveat emptor, amen.

<insert witty closing heading here>

so there you have it, folks.  as always, i welcome comments, questions, critique, praise, beer and naked pictures (ladies only please).  anyone who has suggestions on how to improve this code, please do so.  i am committed to making this the first step in a much larger plugin that can theoretically replace cake default ACLs.

speaking of which, stay tuned for the second part of this article, entitled “RBAC FTW (part 2)”, in which we will see how we still need the cake ACL structure to limit access to controller actions, thus rounding out this first effort towards our stated lofty goal.

About these ads

About this entry