Speaker
Nima Mousavi
Title
Mitigating the Intractability of the User Authorization Query Problem in Role-Based Access Control
Abstract
We
address
the
User
Authorization
Query
problem
(UAQ)
in
Role-Based
Access
Control
(RBAC)
which
relates
to
sessions
that
a
user
creates
to
exercise
permissions.
Prior
work
has
shown
that
UAQ
is
intractable
(NP-hard).
We
give
a
precise
formulation
of
UAQ
as
a
joint
optimization
problem,
and
take
a
finer
look
at
the
complexity
of
UAQ.
We
study
the
computational
complexity
of
each
of
four
subcases
of
UAQ,
and
their
approximation
variants.
Our
results
show
how
each
input
parameter
contributes
into
the
complexity
of
UAQ.
We
also
prove
that
in
general,
UAQ
remains
in
NP.
We
then
investigate
two
techniques
to
mitigate
its
intractability.
(1) We efficiently reduce UAQ to boolean satisfiability in conjunctive normal form, a well-known NP-complete problem for which solvers exist that are efficient for large classes of instances. We point out that a prior attempt is not a reduction, is inefficient, and provides only limited support for joint optimization.
(2)
We
show
that
UAQ
is
fixed-parameter
polynomial
in
the
upper-bound
set
of
permissions
under
reasonable
assumptions.
We
discuss
an
open-source
implementation
of
(1)
and
(2),
based
on
which
we
have
conducted
an
empirical
assessment.