A main challenge of attribute-based access control (ABAC) is the handling of missing information.Several studies have shown that the way standard ABAC mechanisms,e.g.based on XACML,handle missing information is flawed,making ABAC policies vulnerable to attribute-hiding attacks.Recent work has addressed the problem of missing information in ABAC by introducing the notion of extended evaluation,where the evaluation of a query considers all queries that can be obtained by extending the initial query.This method counters attribute-hiding attacks,but a na(i)ve implementation is intractable,as it requires an evaluation of the whole query space.In this paper,we present a framework for the extended evaluation of ABAC policies.The framework relies on Binary Decision Diagram (BDDs) data structures for the efficient computation of the extended evaluation of ABAC policies.We also introduce the notion of query constraints and attribute value power to avoid evaluating queries that do not represent a valid state of the system and to identify which attribute values should be considered in the computation of the extended evaluation,respectively.We illustrate our framework using three real-world policies,which would be intractable with the original method but which are analyzed in seconds using our framework.