Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Auditing Compliance with a Hippocratic DatabaseJavier Salinas MartínOutlineIntroductionSystem architecture:–Logs–Audits–Audit queriesPerformanceIntroductionResponsibly managing privacy sensitive data is mandatoryApproaches:–Physically logging the results of each query–New system to audit whether the database executed a query in the past that accessed private dataSystem propertiesNon-disruptiveFast and preciseFine-grainedConvenientSystem architectureLogsQuery log: timestamp, user IDTemporal extensions: for each table T, a backlog table Tb is created–Time stamped–Interval stampedTime stamped organizationA tuple in Tb has two additional columns:–TS: time of storage–OP: operation {‘insert’, ‘delete’, ‘update’}Triggers are used to capture updatesRecover state of T at time τ: take a snapshotInterval stamped organizationPeriod of time for wich each tuple was alive:–TS: time of storage–TE: end timeInsert trigger adds t to Tb, setting TE to nullUpdate trigger searches for tuple b such that b.P=t.P and b.TE=null and sets b.TE to the current time and inserts new tuple tDelete trigger searches for tuple b such that b.P=t.P and b.TE=null and sets b.TE to the current timeAudit expressionsIdentical to that of a select queryNo disctinct in the select list“Audit” replaces “Select”U: cross product of all the base tables in the databaseCells that satisfy the expression are marked in USchema used for examplesExample of audit expressionAudit if the disease information of anybody living in the ZIP code 95120 was diclosedCells corresponding to the disease column of those tuples in the Customer x Treatment table that have c.cid=t.pcid and c.zip = 95120 are markedSome definitionsTuple t, Query Q, Audit AIndispensable tuple: omitting t makes a difference on QCandidate query: Q accesses all columns A specifies in its audit listSuspicious query: Q and A share an indispensable tupleExample 1Q is a candidate query with respect to AQ is suspicious with respect to A if there is a customer who lived in the ZIP code 95120 and was treated for diabetesExample 2Q is not suspicious with respect to AAnyone who looks at the output of the query will not learn that Alice has cancerSystem architectureAudit query generationFull audit expressionTwo steps:–Static analysis: select candidate queries from the query log–Audit query generation: augment every candidate query with information from the audit expression and combine them into an audit query that unions their outputStatic analysisSelect candidate queriesFour steps:–Check whether Q is a candidate query–Check whether timestamp of Q is out of range–Check whether the purpose-recipient pair of Q matches any of the purpose-recipient specified in the otherthan clause of A–Check for contradictions between predicatesSet of candidate queries Q= {Q1,…,Qn}Audit Query GenerationAugment every Qi with AResult is another query AQi, defined against the backlog database at time τiτi is the timestamp of Qi as recorded in the query logAll AQi are combined into one AQ audit query whose output is the union of the output of the individual AQiAQ is executed against the backlog databaseAudit Query Generation exampleExample:Audit Query Generation exampleAudit Query Generation examplePerformanceCost of maintaining backlog tablesPerformanceExecution time of an audit