Transcript Don`t Reveal My Intension: Protecting User Privacy using

Don’t Reveal My Intension: Protecting User
Privacy using Declarative Preferences
during Distributed Query Processing
Nicholas L Farnan, Adam J Lee, Panos K Chrysanthis
University of Pittsburgh
Ting Yu
North Carolina State University
Alice is Concerned her Employer Pollutes
SELECT * FROM Plants, Supplies, Polluted_Waters
WHERE Supplies.type = "solvent",
AND Supplies.name = Polluted_Waters.pollutant,
AND Polluted_Waters.location = Plants.location,
AND Plant.id = Supplies.plant_id;
ESORICS, 14 Sept. 2011
2
Our Goals for this Work
To empower users querying distributed database
system with declarative controls over their privacy that
are flexible enough to allow for a balance between
privacy and performance
ESORICS, 14 Sept. 2011
3
Roadmap
●
Overview of Distributed Query Processing
●
Privacy Definitions
●
Overview of Our Methodology
●
Proposed SQL Extensions
●
Overview of Related Work
●
Conclusion and Ongoing Work
ESORICS, 14 Sept. 2011
4
Distributed Query Processing
SELECT * FROM Plants, Supplies, Polluted_Waters
WHERE Supplies.type = "solvent",
AND Supplies.name = Polluted_Waters.pollutant,
AND Polluted_Waters.location = Plants.location,
AND Plant.id = Supplies.plant_id;
Alice
Inventory
Facilities
Querier
Trusted
ESORICS, 14 Sept. 2011
Untrusted
Pollution
Watch
5
How Does Optimization Affect Querier Privacy?
SELECT *
WHERE
AND
AND
AND
FROM Plants, Supplies, Polluted_Waters
Supplies.type = "solvent",
Supplies.name = Polluted_Waters.pollutant,
Polluted_Waters.location = Plants.location,
Plant.id = Supplies.plant_id;
Results ain
Strikes
balance
a large between
amount
of
privacy
network
andtraffic
performance
Reveals
sensitive
information
to Pollution
ManuCo
Watch
ESORICS, 14 Sept. 2011
6
Formalizing this Intensional Knowledge
Given a globally-expanded query plan Q = <N, E>
We denote by κp (Q) ⊆ N ∪ E the intensional knowledge that principal p ∈ P
has of the query encoded by the plan Q.
At a minimum, κp (Q) contains the set of all locally-expanded query plans for
each node n ∈ N annotated for execution by the principal p, and further all
edges leaving or entering such nodes.
κPollution_Watch
ESORICS, 14 Sept. 2011
κFacilities
κInventory
7
Our Approach
●
Have users to define intensional regions
●
Specify constraints on those regions
●
Construct a query plan that respects those constraints
SELECT * FROM Plants, Supplies, Polluted_Waters
WHERE Supplies.type = "solvent",
AND Supplies.name = Polluted_Waters.pollutant,
AND Polluted_Waters.location = Plants.location,
AND Plant.id = Supplies.plant_id;
Make sure all operations involving these
conditions are evaluated by a trusted server!
ESORICS, 14 Sept. 2011
8
A Formal Definition of Querier Privacy
Given an intensional region I,
And a set of colluding adversaries A ⊆ P,
A globally-expanded query plan Q is said to be (I, A)-private
iff κA (Q) ⊭ I
Where ⊨ denotes an inference procedure for extracting intensional
knowledge from a collection of query plans.
ESORICS, 14 Sept. 2011
9
Representing Query Plan Nodes
<select, {(type, =, “solvent”)}, inventory>
ESORICS, 14 Sept. 2011
10
Representing Query Plan Nodes
<op, params, p>
●
op - Relational algebra operation
●
params - Parameters to that operation
●
p - Principle where operation will be executed
ESORICS, 14 Sept. 2011
11
Matching Against Query Tree Nodes
<*, {(pollutant, =,
<*,name),
{('solvent')},
(location,
<scan,
*, *> *>=, location)}, *>
ESORICS, 14 Sept. 2011
12
Constraining Dissemination of Intensional Regions
Node descriptors can contain free variables
Users author constraints on these free variables
<*, {(pollutant)}, $l>
$l = Querier
ESORICS, 14 Sept. 2011
13
Extending SQL to Support Constraints
SELECT * FROM Plants, Supplies, Polluted_Waters
WHERE Supplies.type = "solvent",
AND Supplies.name = Polluted_Waters.pollutant,
AND Polluted_Waters.location = Plants.location,
AND Plant.id = Supplies.plant_id
REQUIRING $l = Querier HOLDS OVER <*,{(pollutant)},$l>;
ESORICS, 14 Sept. 2011
14
Balancing Privacy and Performance
All nodes operating on the pollutant attribute are evaluated by Querier &
( Query is estimated to take less than 2 minutes to run ⊗
All join operations are evaluated by Querier )
ESORICS, 14 Sept. 2011
W. Kießling. Foundations of preferences
in database systems. VLDB, 2002.
15
Expressing Preferences in SQL
SELECT * FROM Plants, Supplies, Polluted_Waters
WHERE Supplies.type = "solvent",
AND Supplies.name = Polluted_Waters.pollutant,
AND Polluted_Waters.location = Plants.location,
AND Plant.id = Supplies.plant_id
PREFERRING $l = Querier HOLDS OVER <*,{(pollutant)},$l>
CASCADE LESSTHAN(runtime, 2)
AND $l = Querier HOLDS OVER <join,*,$l>;
ESORICS, 14 Sept. 2011
W. Kießling and G. Köstler. Preference SQL: Design,
Implementation, Experiences. VLDB, 2002.
16
Related Work
●
●
k-anonymity, l-diversity, t-closeness, differential privacy...
●
All look at database privacy, though a compliment to our work
●
Protect the privacy of those whose data is stored in the database
Private Information Retrieval (PIR)
●
●
●
Server support required for privacy to be achieved
Our approach can utilize PIR techniques when they are available,
applicable, and efficient
Werner Kießling's work on partially ordered preferences
●
Express preferences over query results
●
We adapt his work to operate over query optimization
ESORICS, 14 Sept. 2011
17
Conclusions and Ongoing Work
●
●
●
●
How a query is evaluated in a distributed environment can drastically
affect querier privacy
We present a formalization of querier privacy,
(I, A)-privacy, and further mechanisms for users to express their
particular privacy preferences
We have adapted Kießling's work on partially ordered preferences to
query optimization as opposed to data retrieval
We are currently modifying the PostgreSQL query optimizer to
support (I, A)-privacy constraints.
ESORICS, 14 Sept. 2011
18
Thank you.
Questions?
[email protected]
This research was supported in part by the National Science
Foundation under awards CCF–0916015, CNS–0964295,
CNS–1017229, CNS–0914946, CNS–0747247, and CDI OIA–
1028162; and by the K. C. Wong Education Foundation.
ESORICS, 14 Sept. 2011
19