The Concept Lattice

A Hapi specification manipulates three data types:

  • Actors: entities, like users or groups of users, who can perform actions on resources.
  • Actions: the different ways in which actors can actuate on resources.
  • Resources: the data that can be accessed by different actors via actions.

These types are organized in a data-structure called a concept lattice. A concept lattice is a lattice, that is, an abstract data structure formed by a set, plus a partial order between the elements of the sets. We define a partial order as follows:

  • Given a set S, a partial order is a reflexive, transitive and antisymmetric relation that exists between some pairs of S.

With this in mind, we can now define our concept lattice:

Lattices have another property: every pair of elements has a minimum upper bound, and a maximum lower bound within the lattice. If there are two elements in this set, say, E1 and E2, then the lattice also contains an element E that is greater than E1 and E2. The smallest of these elements is called the least upper bound of E1 and E2. There is also an element E' that is less than E1 and E2. The greatest of these elements is called the greatest lower bound of E1 and E2.

It is possible to visualize lattices as graphs. Below we show three lattices that we use to define data types:

Lattices are fundamental to Hapi because they support the representation of orderings between the values of each attribute that is used in a program. If an attribute A1 is less than another attribute A2, then A1 either expands or constraints the access requirements of A1.

Data Dependency Graph

HAPI policies are checked at each node in the data dependency graph. Each graph node is labeled with the domain-specific attribute name and set of lattice values. Informally, an ALLOW clause permits graph nodes labeled with any subset of the attribute values listed in the clause, and a DENY clause forbids graph nodes labeled with any set that overlaps with the attribute values in the clause. The layering of clauses determines the context within which each clause is checked. For example, the graph below models a scenario where the actor Analyst is reading the resource IP.

[{'Actors': {"Analyst"}, 'Resources': {"IP"}, "Actions": {"Reads}}]