Transcript Reflective Database Access Control

Reflective Database Access
Control
Lars Olson
Ph.D. Thesis Defense
Introduction
Alice
Bob
Carol
Database
David
ACM-Based Access Control
Employees
Name
Alice
SSN
123456789
Salary
80000
Dept
HR
Position
CPA
Bob
234567890
70000
Sales
Sales Rep
Carol
345678901
90000
Sales
Manager
David
456789012
90000
HR
Manager
ACM
Entries
Alice
David
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
ACM-Based Access Control
Sales_Employees
ACM
Entries
Bob
Sales
Bob
Sales Rep
Carol
Carol
Sales
Manager
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”
Motivation
• ACMs describe extent, rather than intent
• Decision support data is often already in
the database
– Redundancy
– Possibility of update anomalies
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)
• What is it useful for? (SPIMACS ’09)
Database
Thesis Statement
Datalog-based reflective database access
control can provide a flexible, scalable,
and efficient mechanism for defining,
enforcing, and formally reasoning about
fine-grained access control policies.
Outline
• Challenges for RDBAC
• Theory
– Formalism using Transaction Datalog
– Security analysis
• Implementation
– Prototype description
– Evaluation
• Case Studies
– Medical database
– Building automation system
• Future Work and Conclusion
Outline
• Challenges for RDBAC
• Theory
– Formalism using Transaction Datalog
– Security analysis
• Implementation
– Prototype description
– Evaluation
• Case Studies
– Medical database
– Building automation system
• Future Work and Conclusion
Application-Layer Security
User a
User b
User c
Application A
Access
Control Rules
A
Database
Oracle Virtual Private Database
• User-defined function as query filter
– Access to current user
– Access to other table data (excluding current
table)
– Non-omniscient— subject to policies
protecting other data
• Flexible— a little too flexible…
Pitfalls in Reflective AC
create or replace function leakInfoFilter
(p_schema varchar2, p_obj varchar2)
return varchar2 as
begin
for allowedVal in (select * from alice.employees)
loop
insert into logtable values (sysdate,
'name:' || allowedVal.name
|| ', ssn:' || allowedVal.ssn
|| ', salary:' || allowedVal.salary);
end loop;
commit;
return '';
end;
Not Necessarily a Problem
• Note:
– Only privileged users can define VPD policies.
– Using POLICY_INVOKER instead of SESSION_USER
in the employees table would solve this problem.
• Still, centralized policy definers not ideal
– Scalability
– Difficulty in understanding subtle policy interactions
…and you have to deal
with surly DB admins
Pitfalls in Reflective AC
• Queries within policies must be executed
under someone’s permissions.
• Cyclic policies cause infinite loop.
• Long chains of policies may use the
database inefficiently.
• Determining safety is undecidable, in
general.
Desirable Properties
• Policy can depend on user attributes or object
attributes in database
• Updates immediately affect policy evaluation
• Policies are fine-grained
• Policies may modify database
• Lower-privileged users may define privileges for
their own tables (non-omniscient policies)
• Model has formal mathematical basis
• System performance is comparable to current
technology
Outline
• Challenges for RDBAC
• Theory
– Formalism using Transaction Datalog
– Security analysis
• Implementation
– Prototype description
– Evaluation
• Case Studies
– Medical database
– Building automation system
• Future Work and Conclusion
Transaction Datalog
• Datalog extended with assertion and
retraction semantics
• Inference process extended to track
modifications
• Concurrency and atomicity
• Implicit rollback on failure
Transaction Datalog Example
• State:
emp(alice, 1234, 80000, hr, manager).
emp(bob, 2345, 60000, hr, accountant).
• Transaction Base:
changeSalary(Name, OldSalary, NewSalary) :emp(Name, SSN, OldSalary, Dept, Pos),
del.emp(Name, SSN, OldSalary, Dept, Pos),
ins.emp(Name, SSN, NewSalary, Dept, Pos).
• Runtime queries:
changeSalary(alice, 50000, 100000)?
changeSalary(alice, 80000, 100000)?
No.
Yes.
TD as a Policy Language
• Allow users to access their own records:
view.emp(User, Name, SSN, Salary, Dept,
Pos) :emp(Name, SSN, Salary, Dept, Pos),
User=Name.
• Allow users to view names of employees in their
own department:
view.emp(User, Name, null, null, Dept,
Pos) :emp(User, _, _, Dept, _),
emp(Name, _, _, Dept, Pos).
TD as a Policy Language
• Restrict and audit sensitive accesses:
view.emp(User, Name, SSN, Salary, Dept,
Pos) :- emp(User, _, _, hr, _),
emp(Name, SSN, Salary, Dept, Pos),
ins.auditLog(User, Name, cur_time).
• Chinese Wall policy:
view.bank1(User, Data1, Data2) :cwUsers(User, 1, OldValue),
bank1(Data1, Data2),
del.cwUsers(User, 1, OldValue),
ins.cwUsers(User, 1, 0).
Fixing the Leak
• Policies must always run under the
definer’s privileges:
view.a(User, ...) :- view.b(alice,
...), view.c(alice, ...).
• Basic table owner privileges can be
generated automatically.
view.a(alice, ...) :- a(...).
Formal Safety Analysis
• Efficiency of answering the question “Can
user u ever gain access right r to object
o?”
– Excludes actions taken by trusted users
• TD can implement HRU model
• Consequence: safety is undecidable in
general
Decidable Class #1
• Read-only policies
• Check whether subject s can access
object o initially
• Ignore irrelevant tables
• Infrequent updates
– Polynomial-time safety check
– Unsafe configurations can be rolled back
Decidable Class #2
• Retraction-free
• “Safe rewritability”
– Rewrite policies to calculate their effect on the
database, e.g.:
• Original policy rule:
p(X) :- q(X, Y), ins.r(X, Y), s(Y, Z).
• Rewritten rules:
r(X, Y) :- q(X, Y).
p(X) :- q(X, Y), r(X, Y), s(Y, Z).
– Rewritten rules must be range-restricted to ensure
efficient computation
Proving Safety Decidability
• Database never shrinks
• Rewritten rules provide upper bound on
database
• Every sequence of operations reaches fixed
point
• Finitely many operations
• Too ugly?
– Use upper bound as conservative estimate
– No negation semantics in TD
Outline
• Challenges for RDBAC
• Theory
– Formalism using Transaction Datalog
– Security analysis
• Implementation
– Prototype description
– Evaluation
• Case Studies
– Medical database
– Building automation system
• Future Work and Conclusion
System Architecture
Individual Userdefined Policies
TD
Policy
User queries
normally
Database
Policy
Compiler
SQL:1999
Recursive
View
Definitions
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
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
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 = 0 or (Assert_flag = 1
and assert_auditLog(Assert_param1,
Assert_param2) != 0)
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 = 0 or (Assert_flag = 1
and assert_auditLog(Assert_param1,
Assert_param2) != 0)
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;
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', _)
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
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
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
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
Database Size
100000
Outline
• Challenges for RDBAC
• Theory
– Formalism using Transaction Datalog
– Security analysis
• Implementation
– Prototype description
– Evaluation
• Case Studies
– Medical database
– Building automation system
• Future Work and Conclusion
Case Study: Medical Database
• HIPAA legislation
– Protects privacy of patients
– Access to electronic health records must be
restricted “based on the specific roles of the
members of their workforce.”
• Idealism meets reality: emergencies are
common
• Commonly implemented by Honor
System, e.g. sign a form yearly
Example Policies
• Patients may view their own medical data
• Primary care physicians may view their
own patients’ data
• Caregivers assigned to consult with a
patient may view that patient’s data
• Current employees may access any
patient’s record, but an audit record is
generated
Formal Security Analysis
• “No untrusted user can ever gain access to a
patient’s lab results.”
• Uses upper-bound estimate on append-only
policies
– Rules with retractions, rules not safely rewritable
omitted
– Sample database populated, verified with Prolog
– Omitted rules analyzed manually
• Analysis scalability
– Running time A: increased patients & doctors
– Running time B: increated patients only
Formal Security Analysis
100000
Execution Time (sec)
10000
1000
Running Time A
Running Time B
100
10
1
10,000
100,000
1,000,000
Number of patients
10,000,000
Case Study:
Building Automation System
Teaching
Assignments
Class
Registration
Local
Network
Firewall
to Internet
Building Resources
Building
Control
Network
Legacy BAS
Controller
and DB
Example Policies
• Users who are given delegation privileges over a
room may add or delete users that may access
the room
• Students enrolled in a class may unlock the
room where the class occurs during normal
class hours
– Attendance recorded
– Internet access disabled
• Anyone may purchase items from a vending
machine, with cost of items deducted from
their account
Outline
• Challenges for RDBAC
• Theory
– Formalism using Transaction Datalog
– Security analysis
• Implementation
– Prototype description
– Evaluation
• Case Studies
– Medical database
– Building automation system
• Future Work and Conclusion
Future Research Possibilities
• Improvements to TD
– Aggregation
– Negation
– Atomic policies for updates
• Improvements to analysis
– Retraction analysis
– State-independent analysis
– Information flow using delegated privileges
Future Research Possibilities
• Further DB integration
– Automatic checks for safety
– Pre-computing optimization
– Side-effects and ordering
• Development of Case Studies
– Discretionary access to patient records
• “Trusted users” no longer constant
• Specifying exceptions
– Firewall rules
Conclusion
• Reflective Database Access Control is a
more flexible model than View-Based
Access Control.
– Easier to model policy intent
– Subtle data interactions create new dangers
• Transaction Datalog provides a
reasonable theoretical basis for RDBAC.
– Expressive semantics for describing policy
intent
– Safety analysis
Conclusion
• 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.
• RDBAC provides benefits for real-world
scenarios.