The increasing complexity and heterogeneity in distributed systems is drawing system administrators into applying usage and access control policy engines. Higher-level policy languages allow policy administrators to demarcate themselves from implementation details, thus focusing on business rule definition. More specifically, history-based policies allow the specification of rules based on events that occurred in the past, such as separation-of-duty related rules (e.g. an employee cannot both issue a voucher and approve the payment).

Several policy engines already support history-based semantics. However, they either provide limited expressiveness in policy rules or they neglect critical scalability issues. Individual policy definitions are disregarded in storage and lookup implementations, thus ignoring the potential for important performance optimizations. Furthermore, purging meta-policy semantics are not provided, inducing the growth of the past event repository until policy evaluation becomes unmanageable.

We present an extension to the Heimdall^1 system, a historyenabled policy engine which allows the definition, enforcement and auditing of history-based policies. This extension targets the scalability of Heimdall in practical environments, introducing an evaluation optimizer and the concept of purging meta-policy tags. An evaluation built on selected usage patterns corroborates the effectiveness of our approach, denoting encouraging performance results.