User-specified policies may be efficiently implemented and enforced with a distributed set of policy enforcement components. User-specified policies may be transformed into a normal form. Sets of normal form policies may be optimized. The optimized policies may be indexed and/or divided and provided to the distributed set of policy enforcement components. The distributed policy enforcement may have a sandbox mode and/or verification mode enabling policy configuration verification. With appropriate authorization, substitute data may be used in verification mode to evaluate requests with respect to policies. Evaluation results, relevant policies, and decision data utilized during request evaluation may be collected, filtered and reported at a variety of levels of detail. Originating user-specified policies may be tracked during the policy normalization process to enable reference to user-specified policies in verification mode reports.