Transcript Reflective Database Access Control

Implementing Reflective
Access Control in SQL
Lars E. Olson1, Carl A. Gunter1,
William R. Cook2, and Marianne Winslett1
1University of Illinois at Urbana-Champaign
2University of Texas
Outline
• Motivation for RDBAC
• Transaction Datalog (TD) as a Logical Basis
and Policy Language
• Implementation Architecture and Description
• Evaluation
2
Introduction
Alice
Bob
Carol
David
Database
3
ACM-Based Access Control
Employees
Name
Alice
SSN
123456789
Salary
80000
Dept
HR
Position
CPA
ACM
Entries
Alice
Bob
234567890
70000
Sales
Sales Rep
Carol
345678901
90000
Sales
Manager
David
456789012
90000
HR
Manager
David
4
ACM-Based Access Control
Employees
Name
SSN
Salary
Dept
Position
Alice
123456789
80000
HR
CPA
Bob
234567890
70000
Sales
Sales Rep
Carol
345678901
90000
Sales
Manager
David
456789012
90000
HR
Manager
5
ACM-Based Access Control
Sales_Employees
ACM
Entries
Bob
Sales
Bob
Sales Rep
Carol
Carol
Sales
Manager
6
ACM Weaknesses
• Complicated policies can be awkward to
define
• “Every employee can access their own
records”
• “Every employee can view the name and
position of every other employee in their
department”
7
Motivation
• ACMs describe extent, rather than intent
• Decision support data is often already in the
database
– Redundancy
– Possibility of update anomalies
8
Reflective Database Access
Control
• Solution: access policies should contain queries
– Not limited to read-only operations
– Policies not assumed to be “omniscient”
• Is this a secure solution? (CCS ’08)
• Is this a practical solution? (DBSec ’09)
Database
9
System Architecture
Individual Userdefined Policies
TD
Policy
User queries
normally
Database
Policy
Compiler
SQL:1999
Recursive
View
Definitions
10
Transaction Datalog
• Datalog extended with assertion and
retraction semantics
• Inference process extended to track
modifications
• Concurrency and atomicity
• Implicit rollback on failure
11
TD as a Policy Language
• Running example: restrict and audit sensitive
accesses
view.emp(User, Name, SSN, Salary, Dept, Pos)
:view.emp('alice', User, _, _, 'hr', _),
view.emp('alice', Name, SSN, Salary, Dept,
Pos),
view.ins.auditLog('alice', User, Name,
cur_time).
12
Compilation to SQL Views
• Off-the-shelf SQL databases benefit from
years of query optimization research
• Datalog, SQL roughly equivalent
– User ID provided by CURRENT_USER system
variable
– Recursion requires SQL:1999
• Assertions and retractions
– SQL syntax does not permit insert or delete
within select statement
– Execution ordering is significant
13
Side-Effects Within Queries
• Ideally, part of the language
– Transaction control
– Variable bindings
• In practice, executed as UDF
– Execution ordering depends on query plan
• Executing UDF(s) last
• Forbids policies with mid-execution side-effects
– Requires separate connection setup in DBs that
do not support side-effects
14
Compilation Process (1st Pass)
view.emp(User, Name, SSN, Salary, Dept, Pos) :view.emp('alice', User, _, _, 'hr', _),
view.emp('alice', Name, SSN, Salary, Dept, Pos),
view.ins.auditLog('alice', User, Name, cur_time).
function assert_auditLog
(@User varchar,
@Name varchar)
...
Schema:
User, Name, SSN, Salary,
Dept, Pos,
Assert_flag, Assert_param1,
Assert_param2
with view_emp as (
...
union all
select e1.Name as User,
e2.Name as Name, ..., e2.Pos as Pos,
1 as Assert_flag,
e1.Name as Assert_param1,
e2.Name as Assert_param2
from view_emp e1, view_emp e2
where e1.Dept = 'hr' and e1.Name =
'alice' and e2.Name = 'alice'
union all
...)
select distinct User, Name, ..., Pos
from view_emp
where Assert_flag = 1
and assert_auditLog(Assert_param1,
Assert_param2) != 0
15
Compilation Process (2nd Pass)
view.emp(User, Name, SSN, Salary, Dept, Pos) :view.emp('alice', User, _, _, 'hr', _),
view.emp('alice', Name, SSN, Salary, Dept, Pos),
view.ins.auditLog('alice', User, Name, cur_time).
function assert_auditLog
(@User varchar,
@Name varchar)
...
Schema:
User, Name, SSN, Salary,
Dept, Pos,
Assert_flag, Assert_param1,
Assert_param2
with view_emp as (
...
union all
select e1.Name as User,
e2.Name as Name, ..., e2.Pos as Pos,
1 as Assert_flag,
e1.Name as Assert_param1,
e2.Name as Assert_param2
from view_emp e1, view_emp e2
where e1.Dept = 'hr' and e1.Name =
'alice' and e2.Name = 'alice'
union all
...)
select distinct User, Name, ..., Pos
from view_emp
where Assert_flag = 1
and assert_auditLog(Assert_param1,
Assert_param2) != 0
16
Compilation Process (cont.)
• Filter on user:
create view view_emp_public as
select Name, ..., Pos
from view_emp
where User = CURRENT_USER;
grant select on view_emp_public to public;
17
Optimizations
• Recursive views are expensive!
• Use predicate unfolding
view.emp('alice', Name, SSN, Salary, Dept,
Pos) :emp(Name, SSN, Salary, Dept, Pos).
…allows us to rewrite
view.emp('alice', User, _, _, 'hr', _)
…to
emp(User, _, _, 'hr', _)
18
Optimizations (cont.)
• union all is expensive (although not as bad
as recursion)
– Build query dynamically
– Pre-compute portions of rule
– If rule doesn’t apply, we can eliminate a union
– Simulated with stored procedure
19
Evaluation
• Baseline
– Custom-defined views
– ACM-based enforcement
– Two baselines for side-effect queries
• No side-effect
• Side-effect UDF called within view
• Compiled views
– Unoptimized, with recursion
– Optimized with predicate unfolding
• Simulated optimization with predicate unfolding and
union all elimination
20
Timing Results (fixed DB size)
100000
Avg. Execution Time (sec)
10000
1000
Baseline 1
Baseline 2
Recursive
Optimized
Target
100
10
1
0.1
0.01
HR
Manager
Insurance
Chinese
Wall
21
Timing Results (fixed query)
100000
Avg. Execution Time (sec)
10000
1000
100
Recursive
Optimized
Target
Baseline 1
10
1
0.1
0.01
0.001
0.0001
1000
10000
100000
Database Size
22
Future Research Possibilities
• Further DB integration
– Automatic checks for safety
– Implementation of pre-computing optimization
• Improvements to TD
– Aggregation
– Negation
– Atomic update policies
23
Work on RDBAC
• Olson, Gunter, Madhusudan, “A Framework
for Reflective Database Access Control
Policies,” CCS 2008
• Under review: case study for medical
database, formal policy analysis
• Research lab web page:
http://seclab.uiuc.edu/
24
Related Work
• Bonner, “Transaction Datalog: A Compositional
Language for Transaction Programming,” LNCS 1998
• Oracle Corporation, “Oracle Virtual Private
Database,” Technical report, 2005
• Draxler, “Accessing Relational and Higher Databases
Through Database Set Predicates in Logic
Programming Languages,” PhD thesis, Zürich
University, 1991
• Bossi, Cocco, Dulli, “A Method for Specializing Logic
Programs,” TOPLAS 1990
25
Conclusion
• RDBAC allows more robust access control.
• Compilation of TD rules to SQL views
implements RDBAC with current database
technology.
• Performance cost of compiled views is low
and can yet be improved.
26
Timing Results (fixed DB size and
query)
0.12
Running Time (sec)
0.1
0.08
0.06
0.04
0.02
0
Baseline 1
Optimized
Target
Query Algorithm
27
Timing Results– Franchise Scenario
(fixed DB size)
0.08
Running Time (sec)
0.07
0.06
0.05
0.04
0.03
0.02
0.01
0
Union
Baseline
App-Level
Baseline
Disj. Baseline Join Baseline
Optimized
Query Algorithm
28