The Concept Lattice

A Hapi specification manipulates data types created by the user. These types are organized in a data-structure called 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.

Lattices have the following key property: every pair of elements has a minimum upper bound, and a maximum lower bound within the lattice. In other words, given two elements in the lattice, E1 and E2, the lattice must contain an element E' that is greater than both, and an element E" that is smaller than both. Any other element greater than both is also greater than E', and similarly, any other element smaller than both is also smaller than E". This property makes it easy 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 constrains the access requirements of A2.

Concept Lattice

In Hapi, users specify lattices using the notion of a Concept Lattice. A concept lattice lets users specify all the data types that can be mentioned in a policy specification. A concept lattice consists of data specifications. Below you can see an example of a concept lattice describing the following entities:

• 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.

data Actors = 
  Looker(Analyst),
  Analyst(Alice, Bob),
  Intern(Bob, Jeff),
  Alice, Bob, Jeff;

data Actions = Reads, Deletes, Updates;

data Resources = 
  Claims(Finance),
  Finance(Customers, Companies),
  Customers(CCN), Companies(EMAIL, SSN),
  CCN, EMAIL, SSN;

This example specifies groups of Actors, Actions and Resources. The syntax X(Y, Z) denotes ordering, meaning that Y < X and Z < X. Therefore, in this example, we have that Analyst < Looker, meaning that Analyst and Looker are both Actors, although Analyst is a subgroup within the group of Lookers. For those coming from an object oriented background, you can think of Analyst as a subclass of Looker. The grammar used to specify concept lattices is given below:

dataStmt: 'data' ID '=' elem (',' elem)* ;

elem: ID ('(' value (',' value)* ')')? ;

value: ID;