Research On High Performance Engine For Evaluation Of Privacy And Security Policy

Policy-based computing is a critical component of many large-scale distributed systems because it enables dynamic adaptability of system behavior by changing policy configurations without reprogramming the systems. Policy evaluation, the process of checking whether a request satisfies a policy, is typically the performance bottleneck of policy-based systems. With the explosive growth of web applications deployed on the Internet, privacy and security policies grow rapidly in size and complexity, which leads to longer request processing time. Improving the performance of policy evaluation is a critical issue and so far has been overlooked by the research community. Most prior research on policies has focused on the correctness (i.e., testing, verification, design, and change impact analysis) of policies. While correctness is an important issue, the adoption of policy-based computing may be limited if the resulting systems are not implemented efficiently and thus perform poorly.In this dissertation, a scheme for efficient privacy and security policy evaluation is proposed, which is called Qengine. Qengine first converts a textual policy to a numerical policy, then it converts a numerical policy with complex structures to a numerical policy with a normalized structure, and finally it converts the normalized numerical policy to tree data structures for efficient processing of requests. The algorithm of Qengine can also be applied to network reachability, redundancy removal and so on. A prototype is designed and implemented to demonstrate the performance of Qengine. The experimental results show that Qengine is orders of magnitude faster than both IBM PDP and Sun PDP. The performance difference grows almost linearly with the number of rules in a policy.The major innovative contributions of the dissertation are as follows:1. Two unique approaches are used to speed up policy evaluation: policy numericalization and policy normalization. The idea of policy numericalization is to convert the string values in a policy into integer values. This numericalization technique enables Qengine to use efficient integer comparison, instead of inefficient string matching, in processing requests. The process of policy normalization is to convert a policy with a list of rules into an equivalent tree structure, the policy decision diagram(PDD). This normalization technique enables Qengine to process a request without comparing the request against all the rules until finding the rule that matches the request.2. After converting a policy to a semantically equivalent policy decision diagram, two efficient approaches are proposed to search for the decision of a given request using PDD: decision diagram approach and forwarding table approach. The decision diagram approach uses the policy decision diagram converted from a sequence of range rules to improve the efficiency of decision searching operation. The basic idea of the forwarding table approach is to convert a PDD to n forwarding tables, such that Qengine can search the decision for each single-valued request by traversing the forwarding tables in n steps.3. There are many technical challenges in policy numericalization and normalization: non-integer values, uncertainly valued requests, compound requests, and inefficient sequential searching. For each challenge, a solution is presented along with an illustrating example.