MAC Grady: Mandatory Access Control as a Graded Monad
Posted: 06-11-2026As 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.