Exploiting Security Punctuations to Preserve Privacy in Data Stream Management Systems Rimma V Nehme Department of Computer Science Purdue University rnehme cs purdue edu December 3 2005 Data Stream Environments Streaming Data Data Stream There is increasing need for streaming systems that Data Stream Management protect the privacy and ownership of information Management System System Streaming Results no access privileges Register Continuous Queries Making Things Concrete Patient Monitoring Patient 1 John Continuously retrieve health information about all of the patients in this hospital with income 200K Patient 2 Mary Continuously retrieve heart rate for all of the patients I am responsible for No access privileges to streaming data Nurse on duty Continuously monitor all of my patients for heart rate abnormalities e g rate 80 bpm Dr Evil Doctor Data Streams Examples Hippocratic Databases Hippocratic Oath 8 circa 400 BC And about whatever I may see or hear in treatment or even without treatment in the life of human beings things that should not ever be blurted out outside I will remain silent holding such things to be unutterable What if the database systems were to embrace the Hippocratic Oath Agrawal Kiernan Srikant Xu VLDB 2002 Databases that take responsibility for the privacy of data Specific to relational data model Challenges Specific to Streaming Massive amounts of data Real time response obligation Security restrictions may be evolving in real time Continuous query evaluation Limited Resources Memory CPU The challenge is to preserve privacy and enforce security in update intensive environments while guaranteeing fast query response Proposed Solution Real time flexible low overhead access control mechanism with wide range of protection object granularities Security Punctuation SP Meta knowledge with security semantics embedded inside data streams Security Punctuation Meta knowledge with security semantics embedded inside data streams DDP An ordered set of patterns corresponding to attributes of tuples SRP Access Control Model s Claim Can interop with mixed models Don t explore it in this work Security Punctuations DDP Part Punctuation attribute Matches tuple attribute x y x y value in this range x y z value in this list x this value only wildcard Examples Using a possible structure for the data streams sid hour minute temp 1 All tuples for hour 1 A B C 2 5 All tuples from sensors A B and C between hours 2 and 5 RBAC and PBAC Examples Role Hierarchy Flat R C D DM E GP ND support both Purpose Hierarchy Flat P A AA AD DM HM GP SA TP Security Punctuation more formally Let 1 S be a set of data streams S s1 si 2 T a set of tuples in a data stream T t1 tj 3 A a set of attributes in a data tuple A a1 ak 4 R the set of roles R r1 rm 5 P a set of purposes P p1 pn of a system A security punctuation sp of the form S T A R P determines the access control associated with a particular set of objects O O is a set of triples o s t a s S t T a A The interpretation of security punctuation sp is that a subject with role r R may access an object o O for purpose p P Different Restriction Granularities Stream level restriction S R P Tuple level restriction T R P Only queries registered by a general physician GP with purpose AD i e abnormalities detection can query the stream BodyTemperature S2 Attribute level restriction A R P Example S2 S2 120 96 6 Nov 15 05 11 02 00 S2 311 100 00 Nov 15 05 11 05 00 S2 180 96 9 Nov 15 05 11 14 00 316 S2 316 97 3 Nov 15 05 11 36 00 Timestamp S2 316 97 3 Nov 15 05 11 36 00 GP AD D ND HM E GP Only queries registered by a doctor D or a nurse on duty ND with purpose HM i e health monitoring can access data tuples from any data streams for patient John id employee 316 OnlySmith a hospital E can continuously query the timestamps of streaming data for general purpose GP on all patients data streams Combining Multiple Security Punctuations match t sp a function that identifies what tuples are related to a security punctuation returns True if t belongs to the subset described by sp union corresponds to the union of all applicable sps SP1 SP2 match t union SP1 SP 2 match t SP1 match t SP 2 intersect corresponds to the intersection of all applicable sps SP1 SP2 match t union SP1 SP 2 match t SP1 match t SP2 Example Union SP1 S1 T1 R1 P1 SP2 S1 R2 P2 SP3 R3 P3 SP1 SP2 SP3 All streams R3 P3 S1 R2 R3 P2 P3 S1 T1 R1 R2 R3 P1 P2 P3 Example Intersect SP1 S1 T1 R1 R4 R7 P1 P2 P7 SP2 S1 R1 R2 R5 P1 P2 P5 SP3 R1 R2 R3 P1 P2 P3 SP1 SP2 SP3 All streams R1 R2R3 P1 P2 P3 S1 R1 R2 P1 P2 S1 T1 R1 P1 P2 How Do Security Punctuations Get Embedded Into Data Streams Data source settings Data source e g sensor or GPS device may have the security preferences pre set by the user Knowledge of the data source DSMS may know something about the source of the data or an application semantics that it executes queries for Auxiliary information SPs may be generated from sources other than the input data stream such as relational tables or other files System Administration System administrator can set specify security restrictions on incoming data which are embedded into data streams Executing Queries SELECT S1 Patient id FROM S1 Range 10 Min S2 Range 10 Min S3 Range 10 Min WHERE S1 Patient id S2 Patient id AND S2 Patient id S3 Patient id AND S1 BPM 80 AND S2 Temp 103 FOR AD Role is inferred from the user registering the query in the streaming system Query Plan S1 Select BPM 80 S2 Select Temp 103 Join Range 10min Project Patient id S3 The operators may be shared with other query plans ciat o s s a has ed R rpose u P d ole an Proposed Solution Security Shield Operator SS operator SS SS operator serves to multiple streaming operators integrated with the rest of the query plan without affecting the functionalities of other continuous query operators e g select project filters tuples based on arriving security punctuations and the SS operator state Query Plan Network Join needs special handling Our Proposed Solution SCJoin Security Compliant Join Features of SCJoin Sliding window join Recognizes security restrictions on arriving tuples specified by security punctuations Joins tuples based on associated roles and purposes Supports hierarchical restrictions HRBAC HPBAC Generates security restrictions for result tuples Supports combinations merge union of multiple security punctuations Utilizes the notion of hot buckets to optimize the join execution SCJoin Data Structures TimeLine Table TLT Security