MAC Grady: Mandatory Access Control as a Graded Monad

  • MAC
  • Haskell
  • Graded Types
  • Security
  • Graded Monad

As I was learning how the Haskell library MAC: Static Mandatory Access Control in Haskell worked I got a bit curious. A few years ago Pritam Choudhury published the paper Monadic and comonadic aspects of dependency analysis that showed how to model dependency analysis in a graded type system called the Graded Monadic Calculus (GMC). The question I was curious about was, can I implement GMC in Haskell, and then use that to implement the MAC library?

Graded Monads in Haskell

It turns out you can! The first hurdle was implementing GMC, because it corresponds to an extension of the Simply Typed $\lambda$-calculus with a graded monad. The extension also requires the system be parameterized by a preordered monoid $(M,*,1,\leq)$. I’ll implement the preordered monoid as a type class:

class GrMonoid m where  
    type UnitGr :: m
    type family LessGr (g1 :: m) (g2 :: m) :: Constraint  
    type family ProdGr (g1 :: m) (g2 :: m) :: m

This class allows for one to define various monoids to instantiate our graded monad. Notice that this lives at the type level, where the preorder is a constraint. We need this at the type level, because the elements of m will label the graded monad, which is a type.

Next I define the graded monad I call GmcMonad in dedication to the paper that studied it.

class GrMonoid grmon => GmcMonad (m :: grmon -> Type -> Type) where
    -- Functor:
    lift :: (a -> b) -> m g a -> m g b        

    -- Preorder:
    up   :: LessGr g1 g2 => m g1 a -> m g2 a

    -- Graded Monad:
    ret  :: a -> m UnitGr a
    join :: m g1 (m g2 a) -> m (ProdGr g1 g2) a            

    -- Bind using join:
    bind :: m g1 a -> (a -> m g2 b) -> m (ProdGr g1 g2) b
    bind c f = join $ lift f c

This type class requires the definition of functions that correspond to each of the graded typing rules in GMC. The first requires m to be a functor, the second enforces that the monad respects the preorder, then we have the requirements for graded monads. The graded return allows pure computations to be injected into the monad, but only at the unit grade UnitGr. Then join composes nesting of m, but the result is graded by the product of the grades in the nesting. Finally, since Haskell is designed around monadic bind, I define the graded bind in terms of the graded join. We could have done the opposite.

Implementing MAC

Now I want to use GmcMonad to define a monad for MAC. First, we will need a monoid of security levels.

data Level = Pub | Priv

We have two levels Pub for public resources and Priv for private resources. We can easily define the GrMonoid instance:

instance GrMonoid Level where
    type UnitGr = 'Pub

    type LessGr 'Pub   'Priv = ()    
    type LessGr 'Pub   'Pub  = ()
    type LessGr 'Priv  'Priv = ()
    type LessGr 'Priv  'Pub  = TypeError ('Text "[ordering violation] Priv is never less than Pub")
    
    type ProdGr 'Pub 'Priv  = 'Priv
    type ProdGr 'Priv 'Pub  = 'Priv
    type ProdGr 'Priv 'Priv = 'Priv
    type ProdGr 'Pub  'Pub  = 'Pub

Pub is our lub and unit and Priv is our gub and is not less than anything but itself. The product is fairly easy to define where Priv is all consuming. That is, if a public resource interacts with a private resource, then that interaction is private. Now that we have a grades we can define the monad.

We actually define two graded monads: one for Haskell expressions and one for interacting with IO. An important detail needs to be made explicit, in order to provide a secure API we must define the monads in a untrustworthy “internal” module, then export the second API in a separate module. This is necessary, because the library user should not be able to make use of the constructors of our monads unless they are a trusted user.

We can define our level-graded expressions monad as follows:

newtype Grd (l :: Level) a 
    = Grd {unGrd :: a}

This essentially corresponds to the identity monad:

instance GmcMonad Grd where  
  ret :: a -> Grd UnitGr a
  ret = Grd 

  lift :: (a -> b) -> Grd g a -> Grd g b
  lift f = Grd . f . unGrd

  join :: Grd g1 (Grd g2 a) -> Grd (ProdGr g1 g2) a
  join = Grd . unGrd . unGrd

  up :: LessGr g1 g2 => Grd g1 a -> Grd g2 a
  up = Grd . unGrd

We can now label expressions with security levels. For example, I could have a private environment variable store full of secrets:

secretEnvs :: Grd 'Priv [(String,String)]

Now that we have security labeled expressions we might want them to interact with other monads, for example IO. However, we can’t just wrap our secure expressions in a monad, and expect everything to be secure. This is where MAC comes. It’s design lays out exactly how secure values should interact with an effect that produces secure resources.

MAC defines a means of creating secure resources, writing to secure resources, and reading from secure resources. First, I define the secure IO monad:

newtype SecIO (l :: Level) a 
    = SecIO (IO a)

I leave it’s definition as a GmcMonad as an exercise.

The MAC API is fairly easy to define, because of the Mac … library. I was able to import their identical implementations over to my setting:

create :: LessGr g1 g2 => IO a -> SecIO g1 (Grd g2 a)
create c = SecIO $ c >>= pure . Grd

writeup :: LessGr g1 g2 => (a -> IO ()) -> Grd g2 a -> SecIO g1 ()
writeup f (Grd a) = SecIO . f $ a

readdown :: LessGr g2 g1 => (a -> IO a) -> Grd g2 a -> SecIO g1 a
readdown f (Grd a) = SecIO . f $ a

The MAC library also defines two functions that combine reading and writing, but these were harder to implement, but only by a small margin:

rw_read :: forall l l' a.(LessGr l l', LessGr l' l,SLevelI l)          
         => (a -> IO a) 
         -> Grd l' a 
         -> SecIO l a
rw_read m r = withSLevel body
    where
        body :: SLevel l -> SecIO l a
        body s = gcastWith (prodIdem s) $ x `bind` (\_ -> y)
            where
                x = writeup (const (pure ())) r :: SecIO l ()
                y = readdown m r :: SecIO l a

rw_write :: forall l l' a.(LessGr l l', LessGr l' l, SLevelI l) 
         => (a -> IO ()) 
         -> Grd l' a 
         -> SecIO l ()
rw_write m r = withSLevel body
    where
        body :: SLevel l -> SecIO l ()
        body s = gcastWith (prodIdem s) $ x `bind` (\_ -> y)
            where
                x = readdown (const (pure undefined)) r :: SecIO l a
                y = writeup m r :: SecIO l ()

The actual computational content of the above implementation is identical to the MAC library, but my design has one difference compared to theirs.

They define their security lattice as a type class and I define mine as a type family. An interesting point about this, they needed to wrap their Less type class in an internal type class they call CanFlow to prevent people from making instances of Less (known as Pablo’s trick), but with a closed type family this is not necessary.

However, in my setting I may need to discharge constraints GHC can’t handle. This is why the above implementations of rw_read and rw_write are a little different than MAC’s.

In the above implementations GHC cannot figure out that ProdGr l l ~ l, but we know it’s true.

So….singletons to the rescue.

To prove this I first define a singleton version of Level:

data SLevel (l :: Level) where
    SPub  :: SLevel 'Pub
    SPriv :: SLevel 'Priv

and a type class for implicitly depending on a singleton:

class SLevelI (l :: Level) where levelSing :: SLevel l
instance SLevelI 'Pub where levelSing = SPub
instance SLevelI 'Priv where levelSing = SPriv

and a nice combinator to make writing functions that need to explicitly pattern match on a singleton:

withSLevel :: SLevelI l => (SLevel l -> a) -> a
withSLevel f = f levelSing

Finally, we can prove the constraint we need:

prodIdem :: SLevel l -> ProdGr l l :~: l
prodIdem SPub = Refl
prodIdem SPriv = Refl

Thus, the constraint we need is by definition of ProdGr. In the implementations for rw_read and rw_write I use gcastWith to supply the constraint to GHC.