Transcript Intelligent Intrusion Detection - EECS

CPOL: High-Performance
Policy Evaluation
Kevin Borders
Xin Zhao
Atul Prakash
University of Michigan
ACM CCS 2005
Overview
•
•
•
•
•
Motivation: Why High-Performance?
Current Solutions
CPOL Design
Evaluation of CPOL vs. Other Solutions
Conclusion and Future Work
ACM CCS 2005
Motivation: 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 location
ACM CCS 2005
Current 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/second
ACM CCS 2005
CPOL 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/second
ACM CCS 2005
CPOL Policies
CPOL Policy Fields
Sample Policy
Owner:
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).
Owner: Alice
Licensee: Bob
AccessToken {
LocationResolution = RoomLevel
IdentityResolution = Name
DelegationPrivileges = None
}
Condition {
AfterTime = 9 AM
BeforeTime = 5 PM
InBuilding = {Library, CS}
NotInRoom =
{ConferenceRoom 1010 CS}
}
ACM CCS 2005
CPOL 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
performance
ACM CCS 2005
Defining 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 2005
Caching
• 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 false
ACM CCS 2005
Testing 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 2005
Single 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 system
ACM CCS 2005
Memory 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
memory
ACM CCS 2005
Simulated 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 seconds
ACM CCS 2005
Future 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 messaging
ACM CCS 2005
Conclusion
• Applications are emerging that require highperformance 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 rate
ACM CCS 2005
Questions?
• Please contact me if you wish to obtain
source code for CPOL or for the schedulebased movement generator – source code
will be available online soon!
• E-mail: [email protected]
ACM CCS 2005