CPOL: High-Performance Policy EvaluationOverviewMotivation: Why High-Performance?Current Policy Evaluation SolutionsCPOL Design GoalsCPOL PoliciesCPOL Design OverviewDefining CPOL for an ApplicationCachingTesting MethodologySingle Request Processing TimeMemory UsageSimulated Privacy WorkloadFuture WorkConclusionQuestions?ACM CCS 2005CPOL: High-Performance Policy EvaluationKevin BordersXin ZhaoAtul PrakashUniversity of MichiganACM CCS 2005Overview•Motivation: Why High-Performance?•Current Solutions•CPOL Design•Evaluation of CPOL vs. Other Solutions•Conclusion and Future WorkACM CCS 2005Motivation: Why High-Performance?•Applications are emerging that require high-throughput policy evaluation–Example: Enforcing privacy policies for location-aware services•Large number of subscribers•Alice may want to give Bob access to her location only Monday through Friday 9 AM – 5 PM when she is in the computer science building–Example: Text messaging•Control who can send you information depending on the time and your locationACM CCS 2005Current Policy Evaluation Solutions•KeyNote Trust Management System–Delegation chains are used to grant trust–Not designed with performance in mind – very slow•SQL Database–More scalable than KeyNote, but throughput is still not good enough – approx. 2000 queries/secondACM CCS 2005CPOL Design Goals•Have expressiveness comparable to KeyNote–Express almost everything KeyNote can and some things that KeyNote cannot•Be able to handle a large volume of requests a single machine–Hundreds of thousands of requests/secondACM CCS 2005CPOL PoliciesCPOL Policy FieldsOwner: The owner is the entity whose resources are controlled by this rule.Licensee(s): The licensee is the entity or group that will receive privileges. Access token: The access token contains information about the rights assigned by this rule.Condition: CPOL verifies that the condition is true before granting the access token to the licensee(s).Sample PolicyOwner: AliceLicensee: BobAccessToken { LocationResolution = RoomLevel IdentityResolution = Name DelegationPrivileges = None}Condition { AfterTime = 9 AM BeforeTime = 5 PM InBuilding = {Library, CS} NotInRoom = {ConferenceRoom 1010 CS}}ACM CCS 2005CPOL Design Overview•CPOL takes advantage of the trend that the domain of policies for a particular application is usually fairly small–Instead of presenting a highly expressive interface at runtime, restrict the domain of policies at compile-time•Define access token and condition objects•CPOL also exploits caching to improve performanceACM CCS 2005Defining CPOL for an Application•Access Token–Define data members–Define Boolean AddAccess(newToken) – does this token have sufficient delegation privileges to add a new rule with newToken?•Condition–Define data members–Define Boolean Test(state) – is the condition true given an input state?ACM CCS 2005Caching•Correct invalidation is done using cache conditions–Cache Condition = Sum(Conditions)–Cache Condition is more compact than condition•Example: Calculate time-to-live and highest resolution of location conditions–Invalidated when Boolean StillGood(oldState, newState) is falseACM CCS 2005Testing Methodology•CPOL, KeyNote, and a MySQL database were all set up to evaluate privacy policies•Three experiments–Single request processing time (CPOL, KeyNote, MySQL)–Memory consumption (CPOL)–Simulated privacy request workload in a university environment (CPOL, MySQL)ACM CCS 2005Single Request Processing Time•CPOL and MySQL have O(1) processing time with respect to number of policies•KeyNote takes much longer to evaluate one policy with more policies in the systemACM CCS 2005Memory Usage•Important because CPOL is in memory system•Memory usage is per user, role, role membership, policy (rule), and cache entry•CPOL can store information for approximately 500,000 users with a 2,000,000 entry cache in 500 MB of memoryACM CCS 2005Simulated Privacy Workload•Movement data was generated using custom schedule-based generator for different numbers of users•Users’ privacy policies were created using information collected by surveying 30 potential users•Varying update frequency from one to thirty secondsACM CCS 2005Future Work•Distribute CPOL over multiple servers to further enhance scalability–Minimize state replication between servers•Deploy CPOL in a real location-aware environment–New computer science building at University of Michigan will use CPOL for privacy policy enforcement•Use CPOL in other application domains such as mobile messagingACM CCS 2005Conclusion•Applications are emerging that require high-performance policy evaluation•Current solutions (KeyNote and database server) are not efficient enough to handle a large workload•CPOL takes advantage of caching and compiled object attributes to deliver better performance•With 500 users and 5000 policies, CPOL is five to six orders of magnitude faster than KeyNote and two to three orders of magnitude faster than a MySQL implementation, depending on cache hit rateACM CCS 2005Questions?•Please contact me if you wish to obtain source code for CPOL or for the schedule-based movement generator – source code will be available online soon!•E-mail: