Access control deals with regulating the accesses principals have to resources, and is an important aspect of security. Intractable (NP-hard) problems arise frequently in access control. In this talk, I will discuss three such problems. Two are multi-dimensional optimization problems that arise in the context of access-enforcement, and the third is a policy-verification problem. I will discuss the manner in which we have addressed the intractability of each using well-founded techniques, particularly the use of constraint-solvers augmented with domain-knowledge.
(This is joint work with Nima Mousavi and Vijay Ganesh of the University of Waterloo, Karthick Jayaraman of Microsoft, Martin Rinard of MIT, and Steve Chapin of Syracuse University.)