Modeling an Application Access System as a Directed Acyclic Graph

By Dan Applegate

Parsec gives you incredible control and access, allowing you to play games with friends remotely over the internet. With our cloud machines, you can even take the power of cloud gaming and share your cloud gaming machine with your friends. With that power, however, comes a set of challenges. We want to make sure that when you’re gaming with your friends on Parsec that you can do it safely, without giving your friends unlimited access to your machine. To ensure this, we designed and developed a flexible, extensible permissions system, so that you can specify exactly what your friends can and can’t do when they connect.

First, we considered what actions our users are likely to want to take in different Parsec use cases. Connecting and forwarding mouse and keyboard inputs to a remote Parsec machine immediately came to mind, but we also looked forward to what the system would need to handle in the future. For example, if we introduce a video screen capture feature, we’ll probably want to make that available not only to the host of the machine but also to visitors who are spectating. The ability to take screenshots and video is just one example of future permission settings that our system should be designed to handle.

Building A Permission Model To Handle Dependency—A Directed Acyclic Graph

Once we had some likely candidates for what behavior we’d want our permission system to govern, we began to realize that permissions are dependent upon one another. For example, in order to start taking screenshots of a game session in Parsec, you first need permission to connect to that session. We began modeling these permissions as a directed acyclic graph, with edges denoting dependency chains between different sets of permissions. In the most trivial case, a particular permission might have no dependencies. A good example might be the ability to start and stop a given machine (let’s call it the “manage” permission), which does not imply any additional access to the machine. This permission would be represented as an edgeless node in our permissions graph:

The simplest of permission graphs

In a marginally more complicated case, a series of permissions may be related to one another in a single-parent dependency hierarchy. As mentioned before, permission to screen capture depends on being able to connect to the machine in the first place. In turn, permission to share your screenshots to people beyond those in the gaming session would be dependent on first taking them. Our dependency graph might now look like this:

A slightly more complicated permissions graph, with a chain of dependent permissions

Permission dependency graphs get much more interesting once you actually begin to build them up from the vision you and your users have for your app. Thinking about user needs and expectations when they’re using your app should always be the first step of good application design, but because permissions and access are such a sensitive area, it should be required when modeling your access control structure. As a user, how would I expect granting the ability to take a screenshot to change other permissions? What behavior would surprise me? In a way, you can begin to express your vision for the product through the language of controlled levels of access of who can do what and when. Starting from this perspective can go a long way to make sure you’ve designed a secure yet accessible app from the ground up.

Expanding On The Basic Model To A Robust Permission Graph

Let’s return to our expanding permission graph. What would a Parsec host’s expectations be around visitors adding controllers for co-play, or granting access to the keyboard? We might decide that granting access to one of these does not imply permission to do the other, nor to capturing screenshots and sharing them. But it does still depend on being able to connect to the machine. Let’s modify our graph to represent this:

A complex permission dependency graph with multi-edge nodes

This is how it might look in the application:

This is a great conceptual tool to visualize how your users will interact with your app and what features you intend to offer, but it also provides a useful data structure for when you begin to build your app. Directed acyclic graphs (DAGs) have a number of useful properties that make them ideal for our use case. In particular, nodes in a DAG have a concept of reachability: Starting at a particular node, what is the set of all other nodes that can be reached by traversing along the edges? Expressed in terms of our permissions use case, we can start at a given permission for which we’re checking access, and by traversing the graph, determine all of the dependent permissions that must also be enabled in order to grant access.

This empowers our app to always know the complete set of permissions necessary to perform any given action. According to our graph, if a user wants to share a screenshot, our code knows that they must not only have the (share screenshot) permission, but also the (take screenshot) and (connect) permissions enabled. What happens when we want to deny connect access? We simply flip the direction of the edges and do our reachability check, and we know that we need to also deny (take screenshot), (share screenshot), (add controller), and any other nodes reachable from the ( connect ) permission in our flipped graph. The algorithm for determining this set of permissions never changes. When we need to add more permissions, we simply update our permission dependency graph, and the code will continue to work.

Defining Permission Levels

The final piece of our puzzle came in the form of defining permission levels. As a Parsec user, maintaining the set of permissions granted to each friend on each of my servers would quickly become an ordeal. It would be helpful to be able to assign permissions to groups of users and groups of servers, and manage them together. For example, we can lump all of our friends into one permission group (we call them “roles”) and give them all connect access to a set of our servers. But what happens when a user is a member of multiple permission groups? What happens if we trust most of our friends to connect, but we want to deny access to that one friend that we don’t know so well while still being able to connect to their servers? We need to define another hierarchy that determines which permission settings should override and in which cases. Here’s what it might look like:

Hierarchical list of permission levels, arranged in order of specificity and overriding

In this structure, if I’ve assigned a set of permissions to a particular user, our app should know that this assignment is more specific than any permissions assigned to the user as a friend, and so should override any conflicting permissions between the two friend groups. In this way, our app can have an unequivocal answer to the question “Is this user allowed to perform this action?”

We wanted to reduce the chance of logical errors in our code creating holes in our permission system, so we found it handy to coalesce all permission levels and actions. This makes our permission check a simple lookup: Is the connect permission set to True? If our permission actions are laid out along our X axis, and our permission levels are our Y axis, we can visualize this as a reduce operation that results in our nice, no-nonsense permission lookup for any given scenario:

Reducing several permission levels into a flat lookup structure

As we continue in our relentless drive to make Parsec the undisputed go to solution for accessing games remotely and playing together, we’ll develop our permissions model to keep our users’ machines and games firmly under their control, even as we add more and better features. By investing in an expressive yet unambiguous structure at the outset while our permissions model is still relatively simple, we hope to lay an unshakeable foundation for building trust and security between our users. Now, let’s get back to playing on Parsec!