Attribute-Based Access Control (ABAC) is emerging as the de facto paradigm for the specification and enforcement of access control policies. Nonetheless, ABAC is vulnerable to attribute hiding attacks where users can obtain a more favourable decision by hiding some of their attributes. The extended evaluation of an ABAC policy takes such attribute hiding into account and arguably allows to come to more precise decisions. An extended evaluation of a given query is calculated using the evaluation of all (sensible) queries that can be constructed from that query. Evidently, this approach may require exploring the state space for all possible queries; as such, evaluating a query may not be particularly efficient. In this talk we explore various techniques for computing the extended evaluation.