Tuesday, October 2, 2007

One bit masks for Access Control (setting permissions) in your asp.net applications.

In my previous post, i wrote about a brushup on four binary bitwise operators. In this post, i would like to cover how we can make use of binary bitwise operators to create 1 bit masks, working at the bit level, saving us lots of memory, while also being easy to read and maintain our code. First, lets see how the bitwise operators we covered previously can be used, specifially we shall be using :
  1. Binary OR(|) operator (our bucket for storing permissions)
  2. Binary AND(&) operator (our tester, to tell us what if an item is in the bucket)

The binary (|) operator

 If either bit stacked ontop of one another are 1 or both are 1, then the result is 1, otherwise the result is 0. So 1 on 1 = 1, 1 on 0 = 1 but 0 on 0 = 0.

128 64 32 16 8 4 2 1 Calculation Result
0 0 0 0 0 1 1 1 (4+2+1) 7
0 0 0 0 1 0 0 1 (8+1) 9
0 0 0 0 1 1 1 1 (8+4+2+1) 15

As you can see from the above, binary (|) is being performed on each pair of corresponding bits. If either bit stacked ontop of one another are 1 or both are 1, then the result is 1, otherwise the result is 0. So 1 on 1 = 1, 1 on 0 = 1 but 0 on 0 = 0.

In the above example 7 | 9 = 15. How is this useful with our bitmasks ? Not very useful indeed. The result 15 is not making sense as a candidate for our one bit mask but thats because we OR'ed two numbers that are not made of power of 2^ ; Had we used two numbers with the power of 2^, we could use the binary OR(|) operator to add masks.

Now, lets see what happens when we use numbers made up of power of 2^ like below 1 | 8;

128 64 32 16 8 4 2 1 Calculation Result
0 0 0 0 0 0 0 1 (1) 1
0 0 0 0 1 0 0 0 (1) 8
0 0 0 0 1 0 0 1 (8+1) 9

As you can note from the above, 1 | 8 is giving us 9. It's a simple addition, 0001 | 1000 = 1001. So in short, when we OR'd, we can actually think of this simply asif we were adding items to a bucket. In our case we added 1,8 to the bucket. we can add more items. Eg : 1|4|8|16...

128 64 32 16 8 4 2 1 Calculation Result
0 0 0 0 0 0 0 1 (1) 1
0 0 0 0 0 1 0 0 (4) 4
0 0 0 0 1 0 0 0 (8) 8
0 0 0 1 0 0 0 0 (16) 16
0 0 0 1 1 1 0 1 (16+8+4+1) 29

See, we just got a result of 11101(16+8+4+1) ; Our result 11101 contains all 4 items added(or OR'd) to our bucket. In a real application, such as the bitmask we are writing, this can be used to add 1 or more permissions. First lets create a simple permissions table in our database mapping users to permissions, a single int field is all we need.

UserID Permission
1 3
2 5
3 7

The remaining of the job can be done using bitmasks in our front end. But first, why are one bit masks composed of integers to the power of 2 ? Remember that when OR'ing, "If either bit stacked ontop of one another are 1 or both are 1, then the result is 1, otherwise 0". Well, that's pretty much why. Basically, when using integers to the power of 2, we get a sequential shift, look at the table below :

128 64 32 16 8 4 2 1 Calculation Result
0 0 0 0 0 0 0 1 (1) 1
0 0 0 0 0 0 1 0 (2) 2
0 0 0 0 0 1 0 0 (4) 4
0 0 0 0 1 0 0 0 (8) 8
0 0 0 1 0 0 0 0 (16) 16
0 0 1 0 0 0 0 0 (32) 32
0 1 0 0 0 0 0 0 (64) 64
1 0 0 0 0 0 0 0 (128) 128

In the table above, follow the 1'ones hilighted in red. As you can see, the 1's are in sequential shift order. Thanks to this pattern, we never end up with 1's stacked ontop of one another and our items get added, so if we OR'd integer 1 | 8 which are both to the power 2, we end up with a beautiful 9(1+8), while had we used integers that were'nt to the power of 2, eg 7 | 9 which gives us 15(8+4+2+1) <-- not exactly the bucket type functionality we want.(we get one's stacked ontop of one another and lose the bucket type functionality we are seeking). This is why, one bit masks are always composed of integers to the power of 2.

So, next, let's create a class that describes the available permissions we plan to have via public static fields in our AccessControl (static) class. It makes sense to make this a non instance class, since it's common to all of our users.
public static class AccessControl { // 0001 public static int View = 1; // 0010 public static int Post = 2; //0100 public static int Reply = 4; // 0001 public static int ViewOnly = View; // 0001 | 0010 = 0011(1+2=3) public static int ViewAndPost = View | Post; // 0001 | 0100 = 0101(4+1=5) public static int ViewAndReply = View | Reply; // 0001 | 0010 | 0100 = 0111(4+2+1=7) public static int ViewAndPostAndReply = View | Post | Reply; }

Note above how we made use of the binary (|) OR operator ? As you can see, ViewOnly = 0001(1), but the other 3 permissions are OR'd, ViewAndPost = 0011(3), ViewAndReply = 0101(5), ViewAndPostAndReply = 0111(7).

Now, how do we check the bucket ? ViewAndPost contains two permissions assigned to it, View+Post, and ViewAndReply have two permissions assigned to it too, while ViewAndPostAndReply has 3 permissions assigned to it. Checking this can be easily done using the binary AND(&) Operator.

The binary (&) operator

As we have seen in my previous post, this operator is being performed on each pair of corresponding bits. The comparision is made based on both bits stacked ontop of one another. if both are one's, then we have a 1, anything else is a 0. so 1 on 1 = 1, 1 on 0 = 0, 0 on 0 = 0.

128 64 32 16 8 4 2 1 Calculation Result
0 0 0 0 0 1 1 1 (7) 7
0 0 0 0 1 0 0 1 (9) 9
0 0 0 0 0 0 0 1 (1) 1

In the above example 7 & 9 = 1. How can we use this in our bitmasks for checking permissions ? Lets watch another example, except this time lets binary AND(&) the result of a binary OR(|). So, we already know that 1|4|8|16 has given us the result (16+8+4+1), which is 29. Recall also that we called this a bucket of items, and that in this bucket we have the items 16, 8, 4 and 1. Now lets check this bucket for the item 8  by binary AND'ing 29 & 8 ?

128 64 32 16 8 4 2 1 Calculation Result
0 0 0 1 1 1 0 1 (16+8+4+1) 29
0 0 0 0 1 0 0 0 (8) 8
0 0 0 0 1 0 0 0 (8) 8

As you can see from the above table, 29 & 8 = 8. The return value of 8 indicates that 8 is indeed in our bucket. This means we can use the binary (&) operator to check our bucket for items. A simple code example below :
if ((AccessControl.ViewAndPostAndReply &  AccessControl.View) == AccessControl.View) // View is in the bucket else // blah

In a real scenario, we'd have done the following though. Firstly, note that all we need is a single (permission) property added in our User class as per our example below or anywhere else you'd want to map a permission :
public class MyUser { public MyUser() { } private int permissionBucketValue; public int PermissionBucket {   get { return permissionBucketValue; }   set { permissionBucketValue = value; } } }

Then we need to fill it with the value from our database. Designing your db or retrieving a single value from your db is out of the scope of this post, however it's a nobrainer. So get the value and pass it to Permission property in your user class or where ever you need permissions. In your db, all you need is a single int field to hold the OR'd result. So if you planned on giving read access you would be storing the value of AccessControl.View, which is 1 in  your db. If you had planned to give the user ViewAndPost permission, then you will be storing the value of AccessControl.ViewAndPost, which is 3 in your db and so forth. This is just perfect.

Following is the static AccessControl class example we used earlier, with the addition of a new static method HasAccess. If you look at the HasAccess method a bit more closely you can see that the binary AND(&) operator is being used to test against a given permission :

public static class AccessControl { // 0001 public static int View = 1; // 0010 public static int Post = 2; //0100 public static int Reply = 4; // 0001 public static int ViewOnly = View; // 0001 | 0010 = 0011(1+2=3) public static int ViewAndPost = View | Post; // 0001 | 0100 = 0101(4+1=5) public static int ViewAndReply = View | Reply; // 0001 | 0010 | 0100 = 0111(4+2+1=7) public static int ViewAndPostAndReply = View | Post | Reply; public static bool HasAccess(int bucket, Permission p) {   switch (p)   {     case Permission.View:       return ((bucket & View) == View);     case Permission.Post:       return ((bucket & Post) == Post);     case Permission.Reply:        return ((bucket & Reply) == Reply);   }   return false; } }

And our Permissions enum. We want very readable code, so here it is :
public enum Permission { View, Post, Reply }

See, how we check access permissions using the binary AND(&) operator in the static HasAccess method above. It's that simple. We just need to know if the permission we are checking against is valid for the user. So later in our code we can call HasAccess like this :
MyUser u = new MyUser(); //retrieve permissions from db and pass them to u.Permission // later check access permission in your code anywhere eg : if (AccessControl.HasAccess(u.Permission, Permission.Post)) // user has access else // user does not have acess

So really, what's wrong with using normal boolean flags and storing permissions in individual bit fields in your database Versus using bitmasks. I mean whats the big deal really ? Well, here are my favourite 3 issues with that :
  1. You end up creating an individual field in your database for each access permission you want. In this code sample here i have just 3 access permissions(to simplify). You could have 10, 20 and many more fields..

  2. Building onto problem 1 mentioned above, it's not easy to make a change. Say tomorrow you needed to add a new permission, then you end up adding a new field in your database ? and preparing your frontend for this new change.

  3. Your access control in your database is quite legible and easy to understand, since you just used individual fields, that are basically true or false fields for each permission set, so not the best security. Had you used one bit masks, then you'd have been storing only the OR'd result in a single field(which basically means nothing to who ever is reading your database table). Even though, i'll agree that if your db has been compromised, then knowing someone is able to view and edit your access control table is going to be the last of your worries.
Using one bit masks is really quite simple and neat and readable to me. Normally people prefer to use plenty of boolean fields, which is not a big deal and not that much of a memory consumption in a non systems level application. However, using bitmasks as i have shown here is much  much easier, very very readable, and less code. Less code in your front end, less code in your database, since all you need is a single int field to keep track of the permission set. And you save precious memory and time.

Using bitmasks, you can avoid all the above issues and with style. It's up to you :-)

9 comments:

  1. How would you implement this using a Access Database?

    ReplyDelete
  2. You only need a single field to store you OR'ed bitmask value. Does not matter what database you use.

    ReplyDelete
  3. Hi - Great post :)



    Forgive me if I have missed something here - I see how you grant permissions by adding the values to the "bucket" but how do you revoke a permisson? Can you post an example of the code to remove the "post" permission from a user who has all 3 permissons? I have an application using bitmasks to control runtime options and there are quite a few. Assembling some static combinations just isn't possible.



    Help!

    ReplyDelete
  4. Great post :)



    I have one quick question. Can we use this with Code Security attributes (PrincipalPermissionAttributes)? Can you please share your thoughts on this.



    Thanks

    ReplyDelete
  5. You could replace the static ints with the following, correct?

    [Flags]

    public enum testing

    {

    View = 1,

    Post = 2,

    Reply = 4,

    ViewAndReply = 5

    }

    ReplyDelete
  6. Great post! Regarding Anon's question - assigning ViewAndReply = 5 - I think that won't work, since 5 is not a power of two. Am I correct?

    ReplyDelete
  7. Thanks for the clean and simple explanation.

    ReplyDelete
  8. Great post! Thank you. The comment about negating or revoking a permission was helpful as well, as my current project requires both.



    I do have to disagree with one point though. Us programmers tend to like our data stored in a way which closely mirrors what we intend to do with it, but it's always better to keep your data normalized even if you want to consume it in a flattened state.



    For instance:



    Let's say I have a Roles table:



    RoleId RoleName

    ------ --------

    1 View

    2 Edit



    And I have a linker table to a Users table called UserRoles



    UserId RoleId

    ------ ------



    In my code I have an enum for Roles:



    public enum Roles

    {

    View,

    Edit

    }



    Using Linq it's pretty easy to flatten my data into the "buckets" I prefer to work with:

    (assume userId was passed into this method)



    var userRoles = context.UserRoles

    .Where(ur => ur.UserId == userId)

    .Select(ur => new

    {

    UserId = ur.UserId,

    RoleName = ur.Role.RoleName

    })

    .ToList();



    return userRoles

    .GroupBy(ur => ur.UserId)

    .Select(s => new

    {

    UserId = s.Key.UserId,

    RolesBitMask = r

    .Select(m => Enum.Parse(typeof(Roles), m.RoleName))

    .Aggrigate((allRoles, role) => allRoles | role)

    })

    .ToList();



    //this returns a list of objects which each include the userId and the role bitmask. And my data is properly nomalized!!

    ReplyDelete
  9. If storing the flags is adding the integers of power 2, then removing should be the opposite i.e. subtracting the integers of power 2. We have OR ( | ) operator to add, however, we do not have any operator to remove. So I tried something like the following.
    void RemoveTheFlags()
    {
    //Adding the flags
    Flags flags = Flags.One | Flags.Four | Flags.Eight;

    //Removing the flag: Step 1. First test if the Flag already included
    if ((flags & Flags.Four) == Flags.Four)
    {
    //Removing the flag: Step 2. Then remove
    flags = (Flags)(int)flags - (int)Flags.Four;
    }
    }

    ReplyDelete