Graphs for security

Presenting the ACG datastructure

By Efraim Berkovich, JavaWorld.com, 09/13/04

Print
Email
Feedback
Resources
Discuss

Digg
Reddit
SlashDot
Stumble
del.icio.us
Technorati
dzone

Authorizing access is a vital part of most any system's security. But, for strong access control, simply asking "Where are you going?" is not enough. Asking "Where did you come from?" is also important. This question is standard practice at airports (one hopes), but usually not in software security.

The authorization or access-control component of the system security infrastructure protects system resources against inappropriate or undesired user access. A security architecture defines what it means by a "resource." A security architecture also decides what kinds of user entities are granted access. For example, in "role-based authorization," users are assigned roles or groups, and then the role or group is given access to a resource.

For instance, in the case of directory files, resources are files along with the actions that can be done to the files such as read, write, and delete. Access is controlled by individual user or, more properly, by role. So, File1 can be modified only by administrators, File2 can be read by everyone but modified by administrators and power users, and so on. Most people are familiar with this type of access control.

When controlling access to a directory of files, it does not usually matter which file a user accesses first, second, or last. Rather, the operating system authorizes access based only on the user's credentials and the file requested. That kind of "flat" structure is typically enforced by an access-control list (ACL). An ACL is a list of resources in the system and information about the types of users that can access each resource.

Unfortunately, most systems apply the same flat datastructure to more complex authorization requirements. Most computer security access-control mechanisms use an access-control list for authorization. Each secured resource has an entry in the list, and usually a combination of datastructures and business logic determines who has access to what resource. However, a list does not really capture the way most applications want to restrict access.

By asking "Where did you come from?" a system gives context to a user's request. In a computer system's access control, having a context for a user's request adds extra protection to the system.

I propose using an access-control graph (ACG) instead of an ACL for access control. A graph does everything an ACL can do, offers additional security, and provides other useful features not available in an ACL design.

Directed graphs

An ACL can be thought of as a matrix, where each resource corresponds to a row and each user (or role) corresponds to a column. A cell in this matrix is marked either TRUE, if the user (or role) is allowed access to the resource, or FALSE, if access for that user (or role) is disallowed.

An ACL is an appropriate security mechanism to use when the resources being secured are not particularly interdependent. One everyday example is a hallway in an office building. Each office is secured by its own locked door, entrance to which is obtained only from the hallway. Even if a single key happens to open multiple doors, having access to one office does not necessarily say anything about having access to another office. This type of flat structure is exactly what an ACL represents.