Science, Faculty of
Computer Science, Department of
DSpace
UBCV
Ulhoa Avelar Stolet, Matheus
Master of Science - MSc
University of British Columbia
This thesis presents two contributions. The first contribution deals with the problem of siloed data collection and prohibitive data acquisition costs. These costs limit the size and diversity of datasets used in health research. Access to larger and more diverse datasets improves the understanding of disease heterogeneity and facilitates inference of relationships between surgical and pathological findings with symptomatic indicators and outcomes. Unfortunately, freely enabling access to these datasets has the potential of leaking private information, such as medical records, even when these datasets have been stripped of personally identifiable information. In the first part of this thesis, we present LEAP, a data analytics platform with support for federated learning. LEAP allows users to analyze data distributed across multiple institutions in a private and secure manner, without leaking sensitive patient information. LEAP achieves this through an infrastructure that maintains privacy by design and brings the computation to the data, instead of bringing the data to the computation. LEAP adds an overhead of up to 2.5X, training Resnet-18 with 15 participating sites, when compared to a centralized model. Despite this overhead, LEAP achieves convergence of the model’s accuracy within 20% of the time taken for the centralized model to converge. One of the techniques used by LEAP to preserve the privacy of sensitive queries is differential privacy. Successive DP queries to a dataset depletes the privacy budget. When the privacy budget is depleted, data curators must block access to the underlying dataset to prevent private information from leaking. In the second part of this thesis, we present a system called the SmartCache. The SmartCache optimizes the use of the privacy budget by interpolating old query results to help answer new queries using a synthetic dataset. Queries answered from the synthetic dataset have a smaller privacy cost, so more queries can be answered before the budget runs out. For statistical queries, the SmartCache saved 30%-50% of the budget for threshold values of 0.99 and 0.999, and for gradient queries it consumed 70% less of the privacy budget when training a fully connected model.
Large Scale Federated Analytics and Differential PrivacyBudget PreservationbyMatheus Ulhoa Avelar StoletBA. Computer Science, The University of British Columbia, 2019A THESIS SUBMITTED IN PARTIAL FULFILLMENTOF THE REQUIREMENTS FOR THE DEGREE OFMaster of ScienceinTHE FACULTY OF GRADUATE AND POSTDOCTORALSTUDIES(Computer Science)The University of British Columbia(Vancouver)August 2021© Matheus Ulhoa Avelar Stolet, 2021The following individuals certify that they have read, and recommend to the Fac-ulty of Graduate and Postdoctoral Studies for acceptance, the thesis entitled:Large Scale Federated Analytics and Differential Privacy Budget Preser-vationsubmitted by Matheus Ulhoa Avelar Stolet in partial fulfillment of the require-ments for the degree of Master of Sciencein Computer Science.Examining Committee:Ivan Beschastnikh, Computer Science, UBCCo-SupervisorAline Talhouk, Medicine, UBCCo-SupervisoriiAbstractThis thesis presents two contributions. The first contribution deals with theproblem of siloed data collection and prohibitive data acquisition costs. These costslimit the size and diversity of datasets used in health research. Access to larger andmore diverse datasets improves the understanding of disease heterogeneity and fa-cilitates inference of relationships between surgical and pathological findings withsymptomatic indicators and outcomes. Unfortunately, freely enabling access tothese datasets has the potential of leaking private information, such as medicalrecords, even when these datasets have been stripped of personally identifiable in-formation.In the first part of this thesis, we present LEAP, a data analytics platform withsupport for federated learning. LEAP allows users to analyze data distributedacross multiple institutions in a private and secure manner, without leaking sen-sitive patient information. LEAP achieves this through an infrastructure that main-tains privacy by design and brings the computation to the data, instead of bringingthe data to the computation. LEAP adds an overhead of up to 2.5X, training Resnet-18 with 15 participating sites, when compared to a centralized model. Despite thisoverhead, LEAP achieves convergence of the model’s accuracy within 20% of thetime taken for the centralized model to converge.One of the techniques used by LEAP to preserve the privacy of sensitive queriesis differential privacy. Successive DP queries to a dataset depletes the privacybudget. When the privacy budget is depleted, data curators must block access tothe underlying dataset to prevent private information from leaking. In the secondpart of this thesis, we present a system called the SmartCache. The SmartCacheoptimizes the use of the privacy budget by interpolating old query results to helpiiianswer new queries using a synthetic dataset. Queries answered from the syntheticdataset have a smaller privacy cost, so more queries can be answered before thebudget runs out. For statistical queries, the SmartCache saved 30%-50% of thebudget for threshold values of 0.99 and 0.999, and for gradient queries it consumed70% less of the privacy budget when training a fully connected model.ivLay SummaryCollecting a large enough dataset that covers all forms of disease, includingrare variants is of utmost importance, but cannot be provided by a single healthcenter. More and better data leads to better medical research, which leads to bettermedicine and more lives saved. Furthermore, medical data is often sensitive andexisting techniques used to query sensitive data restrict the number of queries thatcan be made.We present two systems, LEAP and SmartCache, that deal with the challengesabove. LEAP allows researchers to query data distributed across multiple institu-tions, thus making more available to users, and the SmartCache solves the problemof querying sensitive data by allowing users to execute more queries on sensitivedatasets without a privacy risk.vPrefaceThe work presented here was conducted in the Systopia Lab at the University ofBritish Columbia. This thesis is an original, unpublished work by Matheus Stolet,written under the supervision of Ivan Beschastnikh and Aline Talhouk, with theguidance and collaboration of Mathias Le´cuyer.In addition to my work, several individuals helped in the implementation ofvarious features. Chris Yoon helped me with the initial LEAP prototype, AdityaChinchure implemented the REDCap connector, and Kalli Leung assisted in thedata generation for the SmartCache and in searching for systems similar to LEAP.viTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiLay Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiAcknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiv1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.1 Federated Learning . . . . . . . . . . . . . . . . . . . . . . . . . 52.2 Differential Privacy . . . . . . . . . . . . . . . . . . . . . . . . . 62.2.1 (ε , δ )-DP . . . . . . . . . . . . . . . . . . . . . . . . . . 83 LEAP Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93.1 Threat Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103.2 Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103.3 Data Flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123.3.1 Message Types . . . . . . . . . . . . . . . . . . . . . . . 13vii3.3.2 Coordinator . . . . . . . . . . . . . . . . . . . . . . . . . 143.3.3 Cloud Algo . . . . . . . . . . . . . . . . . . . . . . . . . 153.3.4 Site Connector . . . . . . . . . . . . . . . . . . . . . . . 153.3.5 Site Algo . . . . . . . . . . . . . . . . . . . . . . . . . . 154 LEAP Implementation . . . . . . . . . . . . . . . . . . . . . . . . . 174.1 Components . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174.2 Message Protocols . . . . . . . . . . . . . . . . . . . . . . . . . 184.3 Node Encryption and Authentication . . . . . . . . . . . . . . . . 194.4 Users . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204.4.1 User Interface . . . . . . . . . . . . . . . . . . . . . . . . 204.4.2 User Creation . . . . . . . . . . . . . . . . . . . . . . . . 204.4.3 User Authentication . . . . . . . . . . . . . . . . . . . . 215 LEAP Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225.1 Experimental Setup . . . . . . . . . . . . . . . . . . . . . . . . . 225.2 Performance Overhead . . . . . . . . . . . . . . . . . . . . . . . 235.3 Convergence Time . . . . . . . . . . . . . . . . . . . . . . . . . 276 LEAP Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . 306.1 CanDIG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306.2 DataShield . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316.3 COINSTAC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317 SmartCache . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 328 SmartCache Threat Model . . . . . . . . . . . . . . . . . . . . . . . 339 SmartCache Design . . . . . . . . . . . . . . . . . . . . . . . . . . . 349.1 Data Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . 379.2 Decision Mechanism . . . . . . . . . . . . . . . . . . . . . . . . 389.3 Query Extrapolation . . . . . . . . . . . . . . . . . . . . . . . . . 399.4 Quality check . . . . . . . . . . . . . . . . . . . . . . . . . . . . 429.5 Budget Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 45viii10 SmartCache Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . 4710.1 Budget Spent . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4810.2 Accuracy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5311 SmartCache Related Work . . . . . . . . . . . . . . . . . . . . . . . 5811.1 Multiplicative Weights . . . . . . . . . . . . . . . . . . . . . . . 5811.2 Sparse Vector Technique . . . . . . . . . . . . . . . . . . . . . . 5911.3 Other Budget Optimizing Systems . . . . . . . . . . . . . . . . . 6012 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62ixList of TablesTable 10.1 Average absolute error and average variance of queries answeredusing the SmartCache and the synthetic dataset with uniformweights. MAE is the mean absolute error and thresh is thethreshold used to determine hits for the SmartCache. . . . . . . 54xList of FiguresFigure 2.1 1. Centralized coordinator sends model to each site. 2. Sitescompute an update on the local data. 3. Sites send gradientsback to centralized coordinator. 4. Updated model is sent backto each site and the process is repeated for n iterations. . . . . 6Figure 3.1 The coordinator connects to the site connector module on eachsite. At each iteration the site algos compute a result on the lo-cal data which gets sent to the coordinator by the site connectorthrough a secure connection. Results are then aggregated in thecloud algo modules hosted in the cloud. . . . . . . . . . . . . 12Figure 3.2 Data flow for executing a query in LEAP. . . . . . . . . . . . 13Figure 4.1 Nodes send their certificates to a certificate authority. The cer-tificate authority signs and returns the certificate to the LEAPnode. Nodes establish mutual trust and open an encrypted con-nection by verifying the signed certificates against their copyof the root certificate. . . . . . . . . . . . . . . . . . . . . . . 20Figure 5.1 Time to train Resnet 18 using HAM10000 dataset on 1, 5, 10and 15 sites. . . . . . . . . . . . . . . . . . . . . . . . . . . . 25Figure 5.2 Time to train a Logistic Regression modelusing HAM10000dataset on 1, 5, 10 and 15 sites. . . . . . . . . . . . . . . . . . 26Figure 5.3 Time to perform a count query on different number of sites.Each site had a total of 10000 records . . . . . . . . . . . . . 27xiFigure 5.4 Convergence time and accuracy to train Resnet 18 measured innumber of total seconds. . . . . . . . . . . . . . . . . . . . . 28Figure 9.1 When the SmartCache is initialized, synthetic data is generatedat a cost of εg. A new query goes through three components:decision mechanism, quality check, and query extrapolation.These components decide whether results from the syntheticdataset rS or the real dataset rD are released. On top of εgbudget spent for data generation, the SmartCache consumes εqwhen a query from the real dataset is released and εc when thequality check is run. . . . . . . . . . . . . . . . . . . . . . . 36Figure 9.2 The real data is used to generate a synthetic dataset where eachrow is associated to a weight. . . . . . . . . . . . . . . . . . . 37Figure 9.3 The variance of the results between each sub dataset is used topredict whether we will have a hit or not. . . . . . . . . . . . 39Figure 10.1 Budget spent after answering 500 statistical queries on the av-ocado dataset. The 500 queries were a mix of mean, histogramand count queries. Each graph shows the results of using theSmartCache with a threshold of 0.9 (top left) 0.99 (top right),and 0.999 (bottom). . . . . . . . . . . . . . . . . . . . . . . . 49Figure 10.2 Budget spent after answering 500 statistical queries on the bank-marketing dataset. The 500 queries were a mix of mean, his-togram and count queries. Each graph shows the results ofusing the SmartCache with a threshold of 0.9 (top left) 0.99(top right), and 0.999 (bottom). . . . . . . . . . . . . . . . . . 50Figure 10.3 Budget spent after each query used to answer ridge regressionon the avocado dataset. . . . . . . . . . . . . . . . . . . . . . 51Figure 10.4 Budget spent after each query used to answer ridge regressionon the bank-marketing dataset. . . . . . . . . . . . . . . . . . 52Figure 10.5 Budget spent after each query used to answer fully connectedmodel on the avocado dataset. . . . . . . . . . . . . . . . . . 53xiiFigure 10.6 Budget spent after each query used to answer fully connectedmodel on the bank-marketing dataset. . . . . . . . . . . . . . 53Figure 10.7 Validation loss after each query used to answer ridge regres-sion on avocado dataset. . . . . . . . . . . . . . . . . . . . . 55Figure 10.8 Validation loss after each query used to answer ridge regres-sion on bank-marketing dataset. . . . . . . . . . . . . . . . . 55Figure 10.9 Validation loss after each query used to answer fully connectedmodel on avocado dataset. . . . . . . . . . . . . . . . . . . . 56Figure 10.10 Validation loss after each query used to answer fully connectedmodel on bank-marketing dataset. . . . . . . . . . . . . . . . 56xiiiAcknowledgmentsI want to thank Dr. Ivan Beschastnikh and Dr. Aline Talhouk for the helpfulguidance in the past years. The feedback and support I have received from themis invaluable and has helped me become a better researcher. I also want to thankDr. Mathias Le´cuyer for going above and beyond his duty and guiding me with theSmartCache work. The support of these three was paramount for the completionof this thesis.I am grateful for all the NSS/Systopia members and friends which I met duringmy six years at UBC. I appreciate the technical help, knowledge nuggets, andoverall good times we had together.In addition to the names mentioned above, I also want to thank my parents andfamily for their uncoditional love and support throughtout this adventure.This work was supported by NSERC USRA and Discovery grants and by theCascadia Data Alliance.xivChapter 1IntroductionArtificial intelligence (AI) and Machine Learning (ML) as well as improvementin networking speeds, computational ability, and cloud computing present unprece-dented opportunities to glean knowledge from health data, to improve patient care,clinical outcomes, and use health care resources more efficiently. However, to date,many of the benefits of AI remain unrealized in the health domain. This is becauseAI and ML require massive amounts of data to be effective. Even as vast amountsof health data are increasingly generated from traditional health care encounters,medical and consumer devices, wearables, and patient-reported outcomes, thesedata remain siloed due to privacy concerns.A large enough dataset that covers all forms of the disease, including rare vari-ants is of utmost importance, but cannot be provided by a single center. Tradition-ally, de-identified data from multiple institutions was centralized for the purpose ofanalysis. With patient records becoming richer and high-dimensional, moving thatdata to a central location causes both logistical and privacy concerns. Moreover,data transfer agreements between health institutions take a long time, and despiteseveral efforts, access and transfer remains a barrier [39].Federated Learning (FL) is a technical solution that does not require data tobe centralized for the development of AI/ML models. This can help both withscalability and privacy. FL can run a variety of ML tasks over a network; the datastays where it was originally collected and never transferred. One of the benefitsof federation is that it offers continuous control over the data access.1Federated data analysis does not guarantee privacy. For example, FL is sus-ceptible to a variety of attacks such as model inversion [40] [21], membershipinference [31] [36], and record re-identification [19] [30]. These attacks can becarried out by analyzing results from queries or predictions of a model.Differential privacy [13] [15] (DP) is a framework that provides privacy. DPprovides formal privact guarantees by ensuring that the removal or addition of adatabase record affects the outcome of a result by only a small amount. Thus, itprevents the identification of individuals and gives mathematical guarantees on therisk of being identified in the database. DP is achieved by adding random noisefrom a distribution to the result of a query, so that the real value is obfuscated butthe returned result still retains statistical significance. DP enables quantificationof privacy loss of a system through a parameter ε . For example, developers canenforce that a system will not have a privacy loss worse than ε by measuring theprivacy loss of individual queries and blocking further queries from being answeredwhen a limit is reached. Consequently, there has been much research into systemsthat use DP as efficiently as possible because of the constraints imposed by theaccumulated privacy loss [8] [24] [41] [34] [35].DP queries are composable, meaning that Successive queries to a dataset in-creases the privacy loss. Composition [18] [22] [12] [17] is one of the fundamentalproperties of differential privacy. With each query, privacy degrades, but it de-grades in a controlled fashion, allowing the total privacy loss of a system to bemeasured. The privacy budget determines the max privacy loss acceptable by asystem, so a data curator or system administrator can restrict queries to the systemwhen all the privacy budget has been spent. In other words, the budget sets theupper bound on the privacy loss. For instance, a data curator can specify that theprivacy budget of a dataset is ε = 3. If a user issues three queries, where each queryhas a privacy loss of ε = 1, the budget will be depleted and proceeding to querythe dataset further will result in a privacy risk for individuals in the dataset. Thisimposes a query limitation on systems using differential privacy. These restrictionsmake differential privacy unpalatable to those who want to extract the most outof their data or to those who are operating in scenarios with large query volumes.Tackling this issue is important to increase the adoption of privacy systems usingdifferential privacy.2Many techniques and relaxations of DP have been developed to reduce theprivacy loss of individual queries [27] [29] [24]. However, there is not much workon preserving the budget by re-using information and insights gathered from pastqueries. A few theorethical results exist, but they are not practical enough to bedeployed [20] [10].My contributions in this thesis are two-fold. One is the development of a gen-eral purpose data analytics system that can be used to query federated health dataacross sites. Privacy is a concern for healthcare systems because they deal withsensitive data. A solution to these privacy concerns is to issue queries with dif-ferential privacy guarantees. The problem is that differential privacy restricts thenumber of queries a user can perform. Therefore, my second contribution is thedevelopment of a technique that maximizes the amount of queries answered by asystem before running out of the privacy budget.In the first part of this thesis I present my first contribution, a Large scale feder-ated and privacy preserving Evaluation and Analysis Platform (LEAP) that allowsusers to analyze data distributed across multiple institutions in a private and securemanner, without leaking sensitive patient information. LEAP achieves this throughan infrastructure that maintains privacy by design and follows a federated philos-ophy of bringing the computation to the data, instead of bringing the data to thecomputation.The LEAP infrastructure is divided into two groups, the cloud infrastructureand the site infrastructure. Queries are distributed to different sites by the cloudinfrastructure and a LEAP module running on each site sends back the result afterrunning local computation on the local data. Optional noise can be added to resultsto provide differential privacy (DP) guarantees, when requested. These results arereturned from multiple sites to the LEAP infrastructure in the cloud, where theyare aggregated and returned to the end-user. The infrastructure also keeps track ofthe privacy loss from each query, safeguarding against information leakage fromrepeated queries. Our evaluations have shown that using LEAP incurs an overheadwhen compared to training a model or performing queries on a centralized dataset.Nonetheless, there are benefits to LEAP such as control over data (e.g. revokingaccess), simplified data agreements, and time saved in network IO from central-izing the data. For example, our evaluations have demonstrated that as more sites3join LEAP (and thus more data is available) the convergence time for the validationaccuracy decreases.In the second part of this thesis I present a system called SmartCache. Smart-Cache saves DP budget across queries by learning from each query and interpolat-ing old results to answer new queries without consuming much of the DP budget.SmartCache generates a DP synthetic dataset based on the real dataset, and answersincoming queries using both real and synthetic dataset. If the difference betweenresults is smaller than an acceptable threshold, results are returned from the syn-thetic dataset at a small privacy cost (cache hit). If the difference between resultsis above the threshold, results from the real dataset are returned at a larger privacycost (cache miss). Our cache initializes a vector of weights w, where each elementwi ∈ w is associated to a row in the synthetic dataset. With each miss, the cacheis improved by updating weights of the synthetic dataset to minimize differencesbetween results from the real and synthetic datasets. Our evaluations have shownthat the SmartCache is able to maintain the quality of queries answered, and savethe DP budget when answering gradient queries. For statistical queries the resultswere not as positive and we were not able to use less of the privacy budget than thereal dataset with DP.Given that federated learning and differential privacy are important for under-standing LEAP and the SmartCache, the next chapter will cover background ma-terial on both. For the federated learning section, the background chapter covershow a machine learning model is trained using federated learning. In the followingsection, I will review differential privacy and its basic properties.4Chapter 2BackgroundThis section covers some background material necessary to understand LEAPand the SmartCache. The following sections define and illustrate federated learningand differential privacy. LEAP performs computation in a federated setting wheredata never leaves the site holding the data. Below I go over how a machine learningalgorithm can be trained in these situations. Differential privacy is important forboth LEAP and the SmartCache. It gives a formal definition of privacy that lets usquantify how much privacy is lost with each query. In Section 2.2 I formally definedifferential privacy and some popular relaxations of the original definition.2.1 Federated LearningFederated learning [25] is a method for training machine learning models fromdecentralized data. In a traditional scenario, data is centralized on the machinewhere the learning takes places. Federated learning breaks this paradigm and en-ables different devices to contribute to training without ever exchanging the actualdata. As shown in Figure 2.1, a ML model can be trained using federated learningby having a central coordinator push an initial model to each participating device.Each device then computes an SGD update using the data available locally to them.Each device then sends the gradients from the SGD update back to the central co-ordinator. The coordinator aggregates the gradients from each device by summingthem together and then averaging the result. The averaged gradients are then ap-5plied to update the model weights, thus completing one SGD step. The updatedmodel is then pushed to each device and the steps are repeated until the modelreaches convergence.Figure 2.1: 1. Centralized coordinator sends model to each site. 2. Sitescompute an update on the local data. 3. Sites send gradients back tocentralized coordinator. 4. Updated model is sent back to each site andthe process is repeated for n iterations.2.2 Differential PrivacyDifferential privacy [13] [15] is a framework for privacy that provides strongformal guarantees. Differential privacy enables the use of datasets in any anal-ysis without adversely affecting data of individuals included in the dataset. Forexample, when differential privacy is upheld, with a certain probability the sameconclusions of a study will be derived, regardless of whether an individual is partof a dataset or not: the probability of any sequence of responses to queries on thedataset is essentially the same, independent of the presence or absence of an in-dividual. Presented formally, a randomized mechanism M satisfies ε-differential6privacy (also known as pure differential privacy), for any adjacent datasets 1 A, Band any set of possible outputs U ⊆ Range(M) ifPr[M(A) ∈U ]≤ eε Pr[M(B) ∈U ].As this definition shows, the probability of the output of a mechanism M whenan individual is added or removed from a dataset is bounded by eε . This translatesto the notion that a smaller value of ε provides stronger privacy guarantees and alarger value has weaker guarantees. A bigger ε increases the bound on how muchthe probability of the output of a mechanism may change when an individual isadded or removed from a dataset, potentially making it easier to draw conclusionsabout an individual, since one person has a larger influence on the output.There are different mechanisms that produce DP results, but the most commonmechanism for pure DP is the laplace mechanism, which is defined asML( f (x)) = f (x)+Lap(0,∇1 fε)where f is a non private query and ∇1 f is the max `1-sensitivity of query f takenover adjacent datasets A and B∇1 f = maxA,B|| f (A)− f (B)||1.Differential privacy has two properties that are of interest to our work: ro-bustness to post-processing and composability. The post-processing theorem ofdifferential privacy states that if the output of a mechanism M satisfies differentialprivacy, so does g(M(A)), where g is an mapping from the set of possible outputsof M to an arbitrary set. This allows a differentially private result, or a dataset inour case, to be released and modified without losing DP guarantees. Furthermore,even if a query is DP, privacy degrades with each query. One of the nice propertiesof differential privacy is that it degrades in a controlled fashion and the compos-ability theorem allows us to quantify the loss after n queries. For example, supposewe have a mechanism that is ε-DP. If we query this mechanism n times, the resultis nε-DP.1Adjacent datasets are datasets that differ by at most one row72.2.1 (ε , δ )-DPIn this thesis we deal with a relaxation of ε-DP (pure differential privacy) called(ε,δ )-DP [14]. A mechanism M is (ε,δ )-DP if for any adjacent datasets A and Band any set of possible outputs U ⊆ Range(M)Pr[M(A) ∈U ]≤ eε Pr[M(B) ∈U ]+δ .This relaxation means that the mechanism is ε-DP with probability 1−δ . Oneof the reasons that we opt for this relaxation is because it allows us to use theGaussian mechanism instead of the Laplace mechanism, since the Gaussian mech-anism does not satisfy ε-DP but it does satisfy (ε,δ )-DP guarantees. The Gaussianmechanism is defined as:MG( f (x)) = f (x)+Normal(0,σ2)where σ is equal to ∇2 fε√2ln(1.25δ ) and the `2 sensitivity of function f is∇2 f = maxA,B|| f (A)− f (B)||2.The Gaussian mechanism is preferrable in our case because the tails of theGaussian distribution decay faster than the tails of the Laplace distribution. Thismeans that when adding random noise there is a smaller chance of the noise comingfrom a large number on the tails of the distribution. The Gaussian distributionalso has convenient properties and is familiar to most data analysts and scientists,which makes it convenient when releasing DP results. Furthermore, it allows us touse advanced composition theorems [22] so that for small values of ε and a largenumber of queries, we have a tighter bound on the privacy loss. This means thatmore queries can be issued with a smaller privacy cost.Differential privacy is used by both LEAP and the SmartCache to give formalprivacy guarantees for sensitive queries, while federated learning is the basis forthe LEAP architecture. Given the background material on both these approaches,the next chapter will cover the design of LEAP, how the design in LEAP allows forfederated queries, and how differential privacy is used for sensitive queries.8Chapter 3LEAP DesignLEAP is a general purpose federated data analytics platform that enables usersto query data distributed among multiple sites. Participating sites register with theLEAP system and users send query requests that are distributed to each site. LEAPaggregates results from each site and sends the aggregated result back to the user.Three main design goals influenced the development of LEAP: flexibility, securityand cloud deployment. With respect to flexibility, LEAP is a data agnostic platformthat supports a large set of statistical queries used for exploratory data analysis inaddition to supporting training of ML models. LEAP provides a flexible interfacethat allows the addition of new query types to suit user needs. A user can either useone of the predefined queries available in the LEAP API, or they can create theirown custom queries by composing a set of primitive query building blocks.In terms of security, the LEAP system has multiple components to provide alayered defence. The LEAP infrastructure at each site has different modules thatare each responsible for either accessing the data, executing queries, or communi-cating with the infrastructure in the cloud. Furthermore, the federated nature of thesystem gives continuous control over data access to the data owners. The infras-tructure in the cloud also follows a similar design where different LEAP function-alities are divided into modules. For example, user access control, site coordinationand query execution reside in different services. Some participant sites may con-tain sensitive data, and even though federated queries might provide an initial layerof defense against attackers, it does not provide formal privacy guarantees. With9this in mind, LEAP was designed to allow for random noise to be added to queriesin order to provide differential privacy guarantees.The third design goal was to support cloud deployment for part of the infras-tructure. Namely, the aggregation and coordination are hosted in the cloud, whichfacilitates IT management, scalability, and gives us flexibility with different servertypes. This goal also goes hand in hand with security and flexibility. A clouddeployment allows us to use robust logging and monitoring tools from a cloudprovider to improve system security and use the scalability of the cloud to supportmore computationally intensive queries.In the rest of this chapter I will cover the threat model delineating the capabili-ties of different components and agents. I will also cover in more detail the LEAParchitecture and how data and requests flow through the system.3.1 Threat ModelSites: We model sites as honest but curious. We assume they will properlyfollow the protocols in the LEAP system. We trust sites to participate correctly inthe machine learning training process and use their local data to return a correctresult. Nonetheless, we do not trust a site with another site’s data. For example, ifa site gets hold of another site’s sensitive data, we do not trust them to not inspectthe data.Coordinator and Cloud Algo: The coordinator and cloud algo are hosted inthe cloud. We do not trust the coordinator and cloud algo with the raw data fromthe sites. However, we do trust these cloud-hosted services to honestly participatein the LEAP system and trust them with the query results from each site.User: Users of LEAP are not trusted with sensitive data from each site, but theyare allowed to have access to aggregated results for executed queries. Differenttypes of users have different levels of trust attached to them, as defined by thecapabilities associated with each role.3.2 ArchitectureThe LEAP infrastructure (Figure 3.1) is divided into two groups, the cloudinfrastructure and the site infrastructure. The cloud infrastructure forms the first10point of contact between a user and LEAP. Users send requests to the coordinator,which is responsible for managing connections to different sites and authenticatinguser credentials. Credentials are kept in a user database. With each request LEAPchecks whether the user is a valid LEAP user and has the capabilities to issue thequery. The other job of the coordinator is to orchestrate and send the request to thecorrect sites.The point of contact between the cloud and a site is the site connector. Thesite connector is responsible for registering with the coordinator, so that the cloudknows which sites are available, and it takes incoming requests from the coordina-tor and passes these down to the appropriate site algo. The site connector is alsoresponsible for detecting whether the site algo is down and returning the appropri-ate error to the coordinator. At the moment, LEAP runs only one site algo instanceat each site, but in the future the plan is to be able to scale the computational mod-ules up and down on demand at each site.The site algo is the main computational module at each site. With each requestthe site algo uses one of the data connectors such as the REDCap connector [6]or the OpenSpecimen connector [7] to fetch the appropriate data. This data isconsumed by the site algo, which performs the user requested computation andreturns a result back to the site connector which pipes it back to the cloud throughthe coordinator.The coordinator gets results from all the sites and pushes these results to thecloud algo, which is the computational module in the cloud. The cloud algo actsas an aggregator for all the results and can return the aggregated result back to theuser, and controls the logic of when to stop and return the result to the user if thequery is iterative, such as when training a model using federated learning. DP noisecan also be added at this step for global differential privacy or at the site algo levelfor local differential privacy.11Figure 3.1: The coordinator connects to the site connector module on eachsite. At each iteration the site algos compute a result on the local datawhich gets sent to the coordinator by the site connector through a se-cure connection. Results are then aggregated in the cloud algo moduleshosted in the cloud.3.3 Data FlowLEAP is designed so that raw data from a site does not leave the site. Namely,data is exchanged between different components in a site, such as the data connec-tors and site algo, but this data is never passed to the coordinator residing in the12cloud. LEAP only pipes the result of running a certain query on the local data tothe cloud for aggregation. Below is a description of the relevant remote procedurecalls issued by the different LEAP components when computing the result for aquery. A time-sequence diagram in Figure 3.2 visualizes the process.Figure 3.2: Data flow for executing a query in LEAP.3.3.1 Message TypesComputeRequest• AlgoCode: Specifies what algorithm to run• Sites: Specifies what sites to run the algorithm• Functions: Custom building block functions (custom algorithm)ComputeResponse• Response: Aggregated result from running algorithm13MapRequest• AlgoCode: Specifies what algorithm to run• Sites: Specifies what sites to run the algorithm• Functions: Custom building block functions (custom algorithm)MapResponse• Response: Individual map results from each site3.3.2 CoordinatorComputeResponse← Compute(ComputeRequest)• Caller: Client• Callee: Coordinator• Description: Client calls coordinator which starts the execution of the speci-fied algorithm.• Arg: ComputeRequest• Return: ComputeResponseMapResponses←Map(MapRequest)• Caller: Cloud algo• Callee: Coordinator• Description: Receives state from the cloud algo (can include model parame-ters) and collects results of map computation from each site.• Arg: MapRequest• Return: MapResponse143.3.3 Cloud AlgoComputeResponse← Compute(ComputeRequest)• Caller: Coordinator• Callee: Cloud Algo• Description: Coordinator makes RPC call to cloud algo to start the executionof the specified algorithm• Arg: ComputeRequest• Return: ComputeResponse3.3.4 Site ConnectorMapResponse←Map(MapRequest)• Caller: Coordinator• Callee: Site connector• Description: Sends a request to the local site algo service requesting for mapfunction to be computed on local data. Returns the result to the coordinator.• Args: MapRequest• Return: MapResponse3.3.5 Site AlgoMapResponse←Map(MapRequest)• Caller: Site connector• Callee: Site algo15• Description: Runs map function on local data and returns result to the siteconnector.• Args: MapRequest• Return: MapResponseThis chapter covered the different components and their roles in the LEAPsystem. It also covered the LEAP architecture and how a query from a client flowsthrough the system. The next chapter will go into implementation details, suchas the message protocols used, the programming languages used for the differentcomponents, how LEAP ensures security through authentication and encryption,and how users are represented in LEAP.16Chapter 4LEAP ImplementationLEAP was implemented as a series of modules that can be divided into twomain groups. The infrastructure modules implemented in Go, such as the coordina-tor and the site connector, and the computational modules implemented in Python,such as the cloud algo and the site algo. This chapter gives an overview of the im-plementation of the different components in LEAP. Furthermore, this chapter alsocovers implementation details of security protocols such as encryption, authentica-tion, and message protocols. Finally, the end of the chapter covers details on howusers interact with the system and are authenticated and created.4.1 ComponentsCloud Algo: The cloud algo is written in Python and is responsible for aggre-gating the data from the multiple sites and post-processing them before returningan aggregate to a user. To get a response from pre-selected sites, the cloud algouses GRPC to send a protobuf message to the coordinator, which handles all com-munication between the cloud and a local site.Coordinator: The coordinator, written in the Go programming language, is re-sponsible for managing all the sites available in the LEAP system. It is responsiblefor propagating the proper error messages to the cloud algo when a site is down,and for passing the computation requests issued by the cloud algo to the propersites. When a coordinator contacts a site, it serializes the request using protobuf17and uses grpc to issue a remote procedure call to each site. The coordinator hasa multithreaded design in which one goroutine (Go thread) listens for cloud algoconnections and another goroutine listens for site connector connections.Site Connector: The site connector runs a grpc server written in Go that listensto requests from the coordinator. Before showing up as available, the site-connectorsends a registration request to the coordinator. After this is done, the site connectorcan receive computation requests from the coordinator and delegates them to anode running the site algo. Communication between the site connector and the sitealgo also uses grpc and protobufs for serialization.Site Algo: The site algo is a Python program responsible for retrieving theappropriate data from a database and running some sort of computation on thedata. If differential privacy (DP) is turned on, the site algo is responsible for takingthe appropriate measures to make the result differentially private, such as addingLaplacian noise to the result. The site algo uses the REDCap API to retrieve thedata from a REDCap database or a REDCap external module that is optimized forcases where all the necessary computation can be done in a SQL query.User Database: The user database keeps a record of all the registered usersin the LEAP system. It keeps track of their username, password and the sites theuser has access. When a new request arrives at the coordinator from a user, thecoordinator checks whether the user has the permissions to perform the requestedcomputation on the selected sites.4.2 Message ProtocolsEach service in the LEAP infrastructure runs a server that listens to requestsfrom the appropriate services at a port specified in a configuration file. These ser-vices communicate using remote procedure calls and utilize TCP as the underlyingtransport protocol for reliable message transfer. We use Google’s Grpc [3] libraryas the remote procedure call implementation and protocol buffers as the serializa-tion method. Protocol buffers [5] provide us with faster serialization than JSON,although for some messages we still pass JSON blobs for convenience. TheseJSON blobs are used to pass Python functions that are executed in the LEAP in-frastructure. Each JSON blob is turned into a string that is then passed as a field18in the protobuf structure. The protobuf structure is deserialized at an endpoint, theJSON string is extracted, and the functions are executed accordingly.4.3 Node Encryption and AuthenticationLEAP uses mutual TLS/SSL [33] to encrypt connections between nodes andauthenticate the identity of nodes in the system. An internal certificate authority isused to authenticate connections between nodes. This internal certificate authoritygenerates a 2048 bit private RSA key that is used to generate a SHA256 self-signedroot certificate that is valid for a specified number of days. This root certificate isdistributed to the trusted nodes in the system (coordinator, cloud algo, site connec-tor, site algo). Each one of these nodes generates a private 2048 bit RSA key, and aSHA256 certificate signing request, which can be adjusted based on the certificateauthority being used. This certificate signing request is signed with the private keyof the node that generated it and is sent to the local LEAP certificate authority us-ing the administrative procedures in place. The signing request is signed with theprivate key of the certificate authority and is returned to the requesting node.Every connection established between nodes is authenticated by having thenodes on both sides of the connection send their certificates to each other. Thiscertificate is checked against the root certificate to ensure that it is coming fromone of the nodes trusted by the LEAP administrators. After authenticity is verified,the two nodes communicate using an encrypted connection as established by theSSL/TLS protocol.19Figure 4.1: Nodes send their certificates to a certificate authority. The certifi-cate authority signs and returns the certificate to the LEAP node. Nodesestablish mutual trust and open an encrypted connection by verifyingthe signed certificates against their copy of the root certificate.4.4 UsersUsers can issue queries to different locations based on their permissions. Eachuser is associated with a list of sites that they have access to based on their creden-tials, and they are only allowed to issue queries to those sites. This state is storedin the User DB shown in Figure 3.1.4.4.1 User InterfaceUsers interact with LEAP through a programming interface in Python. APython library exports the necessary functions to register and authenticate a user,which returns a token to be used in subsequent requests. The library also exportsthe functions available in LEAP and users can select the sites to send their queries.4.4.2 User CreationWhen new users are created, they pick a username that uniquely identifies themin the LEAP system and a password that is used to login. Only the hash of thepassword is stored to prevent an attacker from acquiring the password used by the20user. On top of that, user passwords are salted, so that a unique hash is created forevery input.In the salting process, a unique salt is created for each user and this salt isappended to the user password before hashing the password and storing it in thedatabase. For example, suppose a user chooses catdog as the password. Duringthe sign-up process we will generate a salt, such as b3ob, for that user. The salt isthen appended to the password before being hashed and stored. This means thatwhen the user signs up we store the hash of catdogb3ob. Salting is meant to preventrainbow table attacks, where an adversary uses a precomputed table of hashes torecover the original cleartext password of a user.4.4.3 User AuthenticationAfter a user is created, that user requires a token to send computation requeststo the LEAP system. This token is obtained by calling the LEAP API and passingthe username and password for that user. We append the salt stored for that user tothe password inputted and hash the appended input. If the input hash matches thehash stored in the database, LEAP returns a JWT token [4] to the user that expiresafter a certain amount of time. The user then has to attach this token to any requestsent to LEAP. This token is then validated and parsed at the coordinator and theclaims are checked to extract the user associated with the token. If the user exists,LEAP checks whether this user has permissions to query the selected sites.Capabilities are associated with users out-of-band, where a prospective usercontacts the person responsible for the LEAP system. The administrator will thenassociate the user with the appropriate query capabilities and access to sites.This chapter covered the implementation details of the LEAP system. Namely,the libraries and programming languages used to build the different componentsand ensure communication is properly encrypted and authenticated. We also cov-ered how users are represented in LEAP and how they interact with the system.The following chapter evaluates the design and implementation details provided inthis chapter. Namely, it evaluates the overhead of using LEAP with different typesof queries.21Chapter 5LEAP EvaluationIn this section, we aim to answer four research questions:1. What is the overhead of using LEAP?2. Where is most of the time spent during execution of a query?3. How does adding more sites affect execution time (distributed overhead)?4. How does having more data available affect the convergence time of a ma-chine learning model in the LEAP system?To answer these questions we designed a set of experiments where we com-pare LEAP to a centralized baseline that has all the data stored locally. We rundifferent types of queries and train different machine learning models using LEAPto measure the overhead incurred by the system. Our experiments reveal that thereis an overhead associated with using the LEAP system. This overhead is morepronounced when training more complex models such as Resnet-18 over runningsimple statistical queries such as count. Nonetheless, when enough sites join LEAPthe convergence time for a model becomes similar to the centralized baseline.5.1 Experimental SetupExperiments were conducted in a cluster of 17 nodes. Each node is an AzureStandard D4s v3 Ubuntu 18 virtual machine with 4 vcpus and 16 GB of memory.2215 out of the 17 nodes were used as LEAP sites and had the site algo and the siteconnector modules installed. Furthermore, a REDCap instance was installed oneach of the sites and populated with tabular data from the HAM10000 skin lesiondataset [37]. Skin lesion images were saved to the hard disk of the site virtualmachines. One of the 17 nodes was used for the cloud infrastructure and had thecloud algo and the coordinator modules deployed. One other node was used as aclient that issued query requests to the coordinator and waited for the result of aquery.The nodes in the cluster were deployed in different Azure regions. The clientand the cloud algo, along with three sites were deployed in the West US. Theother three sites were deployed in East Australia, East Asia, East US, and WestEurope. The sites were deployed in different regions to mimic a federated networkof hospitals and health centres distributed around the globe. Each experiment wasrun four times and the end to end training time was averaged.5.2 Performance OverheadThe results in this section help answer three out of the four proposed researchquestions, while the question on model convergence is answered in Section 5.3.Namely, this section discusses the overhead of using LEAP, the stages that causethe overhead, and how adding more sites affects the overhead. We first discussthe associated overhead to train machine learning models such as Resnet-18 and asimple logistic regression, and then we discuss the overhead associated to runninga statistical query, such as count.To evaluate the scalability of LEAP when training deep learning models theimages from the HAM10000 dataset were divided between each of the sites. Thisresulted in 8000 training images being equally distributed to the sites, so that eachsite contained a total of 533 images. Resnet was then trained to classify the type ofskin lesion from an image using the federated learning algorithm implemented inLEAP. Resnet was trained for a total of 1000 iterations, where 100 of those wereglobal iterations where the cloud algo aggregated the model updates for each siteand for each global iteration 10 local iterations were computed at each site. Thebaseline is a Resnet-18 model trained on 8000 images stored on disk. REDCap23does not support images well, so for the Resnet experiment, both on the baselineand site VMs, the training dataset was saved and retrieved from disk while train-ing. It is important to note that when training these machine learning models, theamount of data available on each site is not important for measuring the overheadof our system. At each federated learning iteration LEAP performs the same num-ber of local iterations. Therefore, even if a site has more or less data, the amountof computation done at each iteration is the same.As the bar chart in Figure 5.1 demonstrates, there is an overhead to trainingResnet using LEAP. Most of the time is spent in the site compute stage, which iswhere gradients are computed on the local data. Interestingly, more time is spentduring the site compute stage than in the total baseline time. In an ideal scenario,the time spent on both of these should be very similar, but LEAP ends up spendingextra time serializing and deserializing gradient and model parameters for sendingand receiving data from the coordinator. Despite being a smaller portion of thetotal running time, LEAP also spends time in the cloud compute stage. The cloudcompute stage is where gradient aggregation happens, which explains why the timespent on this stage increases as the number of participating sites incrases. Themore participating sites, the more gradients have to be aggregated. As the numberof participating sites continues to increase, the time spent in the site compute stagemay overshadow the site compute stage.24Figure 5.1: Time to train Resnet 18 using HAM10000 dataset on 1, 5, 10 and15 sites.Similar to the Resnet-18 experiment, the logistic regression experiment traineda logistic regression model on the HAM10000 dataset with the objective of clas-sifying the gender of the skin lesion from tabular data on the dataset. Since thisexperiment deals only with tabular data, the dataset was stored in REDCap and re-trieved during training using API calls sent to the REDCap database. The logisticregression was also trained for a total of 1000 iterations, where 100 of those wereglobal iterations where the cloud algo aggregated the model updates for each siteand for each global iteration 10 local iterations were computed at each site.As seen in Figure 5.2 the logistic regression experiment shows that LEAP hasa similar total running time to the centralized baseline when only one site is added,but this overhead becomes significantly higher when more sites are added. Thetime spent in the cloud compute stage is significantly larger than the time spent inthe site compute stage. This can be partly explained by the less compute inten-sive nature of the logistic regression when computing gradients. Nonetheless, the25overhead still seems higher than expected and it is not clear what is causing this.Figure 5.2: Time to train a Logistic Regression modelusing HAM10000dataset on 1, 5, 10 and 15 sites.On top of training machine learning models, we were also interested in under-standing the performance of LEAP when executing simple statistical queries. Oneof the big differences between these queries and the model training queries is thatthey are what we call single-shot queries, results get aggregated only once so thereis no iterative back and forth, and they are less computationally intensive.With the statistical queries we were concerned with understanding the perfor-mance of a query as more sites join LEAP and increase the size of the total dataavailable. The HAM10000 dataset was divided to each site, so that every site held10000 records. A count query that retrieved all of the data and then counted thenumber of records was then executed with different numbers of sites. The timefor the query to be returned to the client was averaged among four runs and isdisplayed in Figure 5.3.26In this experiment we can notice that the time to compute a count query in-creases when there are more participating sites in LEAP. The overhead seems toplateau when five sites are added and only slightly increases from 10 participatingsites to 15. This demonstrates that multi-site LEAP has an overhead when scalingthe size of the dataset. The increase in execution time is caused by more time beingspent aggregating the data from the different sites.Figure 5.3: Time to perform a count query on different number of sites. Eachsite had a total of 10000 records5.3 Convergence TimeAs the experiments above have shown, there is an overhead to using LEAP. Oneof the advantages of using LEAP is that by connecting different sites and researchcentres we have more data available for researchers. This brings us to our fourthresearch question: how does having more data available affect the convergence27time of a machine learning model in the LEAP system? How can the accuracyof a model improve as more data becomes available? To measure this we trainedResnet-18 using LEAP and increased the number of participating sites at differentruns. The 8000 training images from the dataset were divided to each site so thateach site had a total of 533 images. For example, in a run with one participatingsite the one site would have 533 images for a total of 533 images in the LEAPnetwork. With five participating sites, each site would have 533 images for a totalof 2665 images in the LEAP network.As seen in Figure 5.4, as more sites join the LEAP network, the convergencetime to train the model to convergence decreases. With only 533 images available,one participating site wasn’t even able to increase the validation accuracy of themodel. As more sites were added to the system, the convergence time improved.With 15 sites, and a total of 8000 images available in the network, LEAP was ableto make the convergence time similar to the centralized model with 8000 images.Essentially, despite the overhead incurred by using LEAP, the larger datasets avail-able in a deployment setting give benefits in the quality of the results.Figure 5.4: Convergence time and accuracy to train Resnet 18 measured innumber of total seconds.In this section we covered different experiments designed to measure the over-head of using LEAP, find where the overhead comes from, inspect how adding28more sites affects execution time, and answer how having more data available af-fects the quality of results, such as when training a machine learning model. Theseexperiments showed that there is an overhead to using LEAP, coming from timespent aggregating results from different sites and serializing and deserializing theseresults. Furthermore, as the number of participating sites increases, the overheadalso increases due to more time being spent in the aggregation. Nonetheless, LEAPshows gains in the quality of trained models, with better accuracy and faster con-vergence when more sites are added. Given these results, the next chapter willcompare LEAP to similar systems and will explore the similarities and differencesbetween them and LEAP.29Chapter 6LEAP Related WorkCoordinating health research with data distributed across several institutionsposes several important challenges including ensuring privacy without revealingconfidential patient information. Furthermore, different health organizations maycollect data with vastly differing representations requiring reconciliation beforefurther analysis can be carried out. Moreover, sending data to other sites for anal-ysis, especially high-dimensional imaging and genomic data, can incur significantcommunication and computation costs.Federated and distributed research networks are useful in facilitating cross-site research where privacy and security policies may prevent data from leavingthe governance of the data owner or health organization. These systems can alsoprovide gains in speed by foregoing data centralization.6.1 CanDIGCanDIG (Canadian Distributed Infrastructure for Genomics) [1] is a Canadianp2p-distributed, secure and private platform aiming to enable healthcare researchfor genomics data. CanDIG has similarities to LEAP. Namely, both are distributedand support differential privacy. Furthermore, local sites control access to the data.CanDIG differs from LEAP in its architecture, which is peer to peer. Furthermore,CanDIG offers limited support for machine learning tools. At the moment CanDIGonly supports a Decision Tree Classifier.306.2 DataShieldDataShield [2] is a free to download R library that allow for federated data anal-ysis using non-disclosive summary statistics from local sites. Queries are issuedthrough an Analysis Computer (AC) through secure web services to multiple DataComputers (DCs) and analysis at each local site is done simultaneously. DataShieldis popular in the healthcare community, but different from LEAP in that it does notprovide machine learning methods. Furthermore, it does not support differentialprivacy like LEAP and CanDIG.6.3 COINSTACThe Collaborative Informatics and Neuroimaging Suite Toolkit for AnonymousComputation (COINSTAC) [32] is a Cloud-based distributed platform for largescale analyses of brain imaging data with the intention to allow federation of neu-roimaging data motivated by privacy and data sharing concerns, and the size anddimensionality of neuroimaging data. COINSTAC’s data is kept private throughdifferential privacy algorithms. In addition, users are able to build pipelines foradditional steps such as feature generation, matrix factorization models, and pre-processing to their workflows (i.e. may want to convert file formats or applybatch transformations to imaging data) – this can be accomplished relatively sim-ply through config files and scripts. This system uses summary statistics of localnodes, which are then aggregated at a remote node and analyzed using global in-ference rules. Despite some similarities such as support for differential privacy anddeployment in the healthcare setting, COINSTAC is not a general purpose analysisplatform such as LEAP. For example, the COINSTAC toolkit seems mostly gearedtowards brain imaging data.This chapter covered the similarities and differences between LEAP and otherpopular data sharing systems, specially in healthcare. This wraps up the LEAPsection of this thesis. The following chapters will now delve into the SmartCacheand how it can be used to optimize the use of the privacy budget when answeringDP queries.31Chapter 7SmartCacheIn the differential privacy framework, each query issued spends a part of theprivacy budget. The budget presents an upper limit on how many queries can beissued before information leaks. This provides a practical problem to data analyticsystems because it restricts the number of queries that can be issued by users. Suc-cessive DP queries compose and incur a compounded privacy loss. For example,if a user issues five DP queries to the LEAP system, each with a privacy loss of ε ,the total privacy loss for the five queries is 5ε . This means that the privacy budgetmay be depleted if too many queries are issued, thus blocking users from using theLEAP system if only DP queries are allowed. A key challenge in LEAP will be tomaximize the utility of analysis queries (i.e., the accuracy of analysis results andmodels) over time, while maintaining DP guarantees.An analysis in LEAP is assigned a privacy budget, and each new query that runson the data spends a portion of that budget. To maintain DP guarantees, this budgetcannot be overspent. To maximize the value of this privacy budget we developed asystem called SmartCache, which works by generating a DP synthetic dataset andanswering queries from this dataset with a smaller privacy loss. If the answer fromthe synthetic dataset is not accurate, the SmartCache falls back to the real dataset.The following chapters cover synthetic data generation, improving the accuracyof results from the synthetic dataset, making better use of the privacy budget, andconcludes with an evaluation of the accuracy and privacy costs of the SmartCache.32Chapter 8SmartCache Threat ModelData Curator: We assume there is a data curator that controls access to adataset D with sensitive information. This data curator may have access to privacyleaking data and they provide data access to the SmartCache. We assume the datacurator will not leak information to other participants.SmartCache: We assume the SmartCache is honest and runs in a trusted en-vironment with permission from the data curator and access to the real dataset.Untrusted parties or programs do not have access to the internals of the Smart-Cache and cannot influence it in any way. The SmartCache provide an interfacethat allows queries to be issued to the system and only returns differentially privateresults. We assume this interface cannot be modified by a malicious agent so thatmore than the differentially private result of a query is released.Users: We assume users are malicious and will take advantage of informationdisclosure of sensitive information. Nonetheless, we also assume they only haveaccess to results of queries issued to the SmartCache. Users can collaborate witheach other to join query results to form a coordinated attack, but they cannot querythe dataset when the collective privacy budget has been depleted.33Chapter 9SmartCache DesignThe goal of the SmartCache is to mitigate the privacy loss from repeated querieswhile maintaining good accuracy. We achieve this by generating a DP syntheticdataset from the real data. Queries answered from the synthetic dataset use only asmall portion of the privacy budget, so the objective of the SmartCache is to max-imize the amount of times we can accurately answer a query using the syntheticdataset, and falling back to the real dataset when the query cannot be answeredwith precision from the synthetic dataset. This is done by using a three step pro-cess comprised of a decision mechanism, a query extrapolation procedure and aquality check. If a query can be answered using the synthetic dataset we considerthis to be a hit, and if it is answered from the real dataset we consider it a miss.When a query arrives, we use the decision mechanism to determine whether to usethe cache. This is done by comparing results from queries on subsets of the syn-thetic dataset. If the SmartCache is not confident in a hit, it returns the query resulton the real data with noise and consumes the query budget. On the other hand, ifthe SmartCache is confident in a hit then it runs the query extrapolation procedure.In this step, SmartCache queries a DP dataset generated from the real data. If theresult of the query in the synthetic dataset has low error SmartCache returns thesynthetic result. If the error is high SmartCache has a miss and return the resultfrom the real dataset with DP.The insight behind the SmartCache is that we use misses as an opportunity tomake our cache ”smarter”. Weight parameters are used to reweight the contribu-34tion of each example in the synthetic dataset, are updated with each miss with theobjective of minimizing a cost function that measures the difference between re-sults. The update procedure leads to more cache hits and allows us to consume lessof our privacy budget because the synthetic dataset is differentially private.Results from the SmartCache can be used to answer a variety of statisticalqueries or to train a machine learning model. In the case of statistical queries, wehave added support for different types of mean, histogram and count queries (theAPI can be extended to add more). The user issues a query to the SmartCache andthe result is returned using the heuristics described above. Statistical queries thatresult in a hit are computed using the synthetic dataset. Each query computed fromthe synthetic dataset uses the cache’s parameters to reweight the contribution ofeach row in the synthetic dataset.Gradient queries are used to train machine learning models. For instance, a usercan train a model by sending a gradient query to the SmartCache at each iterationof the training procedure. The query takes the model parameters and optimizeras input and the SmartCache returns a gradient update computed from either thesynthetic or real data. This gradient update can then be used to train a local model.The following sections will go deeper into how the SmartCache works. Namely,we detail how data is generated, how the decision mechanism decides whetherSmartCache should use the cache or not, how weights are updated in the syntheticdataset, and how we ensure that the SmartCache returns accurate results in a DPmanner.35Figure 9.1: When the SmartCache is initialized, synthetic data is generatedat a cost of εg. A new query goes through three components: decisionmechanism, quality check, and query extrapolation. These componentsdecide whether results from the synthetic dataset rS or the real dataset rDare released. On top of εg budget spent for data generation, the Smart-Cache consumes εq when a query from the real dataset is released andεc when the quality check is run.369.1 Data GenerationThe synthetic dataset is generated using an independent feature generator. Foreach numerical feature in the dataset the mean and variance of the feature is calcu-lated. DP noise is added to the mean and variance to guarantee differential privacy.Values are then randomly sampled from a normal distribution with the calculatedmean and variance. The synthetic dataset is populated with these random samplesfor each feature column in the dataset. For the categorical features the unique val-ues in each column are identified and a histogram is created with the frequency ofthese values. DP noise is then sampled and added to each frequency bin to guar-antee that the generation process is DP. The frequency of each value is then usedto randomly generate samples with the probability given by the frequency bins.After the synthetic data is generated, each row in the dataset is assigned a weight,as seen in Figure 9.2. Weights are uniformly initialized, so that each row has thesame weight.The independent feature generator will not pick up correlations between columns.Nonetheless, if enough samples are generated, the weight tuning process givesmore importance to rows that are able to more closely resemble the original dataset.The privacy cost of generating data using an independent feature generator is alsosmaller than using other methods such as VAEs and GANs.Figure 9.2: The real data is used to generate a synthetic dataset where eachrow is associated to a weight.379.2 Decision MechanismAfter data is generated the SmartCache is ready to receive queries. Nonethe-less, a good decision mechanism is important so that we only use the SmartCachewhen there is a high probability of a hit. To do that, we leverage the followinginsight: if a cache can learn the right answer from past queries, multiple version-s/initializations should agree; if it is extrapolating arbitrarily, they should disagree.Therefore, we divide the synthetic dataset into multiple smaller datasets, each withan independent set of parameters k and w that are used to reweight the contributionof each example in the dataset. When a query arrives, it is computed on each of thedatasets. The variance of query results is also computed to determine whether thereis a chance that the SmartCache will hit because it is unlikely that each dataset willconverge to the same poor result. On the other hand, if the variance is high, there isa high chance that the SmartCache will return a poor answer, so we return a resultfrom the real dataset with added DP noise. When a query is answered, the weightsare updated on a random subset of the original dataset. The reason behind this isso that there is more variability in the weights of the datasets, otherwise they willconverge to similar weights and there will be little difference between results fromthe different datasets.Formally, we have a set of n datasets S1 . . .Sn, each with an independent setof weights w1 . . .wn and k1 . . .kn. When a query q arrives it is answered on alldatasets individually. The appropriate set of weights w are used to reweight thecontribution of a row in the dataset to the query result and the k parameter is usedto rescale the result to the appropriate magnitude 1 For example, a weighted countis computed by k∑ni=0 wixi. The result from each dataset is then averaged andreturned as the final synthetic result. For example, if the SmartCache is initializedwith n datasets, queries q(S1,w1,k1) . . .q(Sn,wn,kn) will return results r1 . . .rn. Toget the final synthetic result we average the results by computing (r1+ . . .+ rn)/n.We also compute the variance of the results r1 . . .rn from each dataset and use thisvariance to make our decision. If the variance is above a certain threshold we deemthe chance of a hit to be low, so we simply return the answer from the real dataset.1The synthetic and real datasets are often not of the same size. For some queries, such as counts,the result will depend on the size of the dataset. Parameter k is used to rescale the result so that themagnitude of the answer from the synthetic and real datasets match.38Figure 9.3: The variance of the results between each sub dataset is used topredict whether we will have a hit or not.9.3 Query ExtrapolationThere are two optimization procedures used to update the parameters in theSmartCache and extrapolate results from previous queries. One of them deals withupdating parameters when general statistical queries such as mean, count, and his-tograms cause a miss, while the other deals with improving the weights to answergradient queries used to train a model. For both procedures we employ an onlinelearning setup that utilizes results from a recently executed query to update thecache’s parameters. The update reweights rows in the synthetic dataset. Rows thatrepresent good approximations of the real dataset are given more weight, whilerows that poorly represent the dataset are given less weight.For statistical queries we use the results of the queries executed on the syntheticand real dataset to compute the L1 loss. We minimize the loss by updating theweights w on each row of the dataset. In popular machine learning parlance, thetarget value is the result from the real data and the predicted value is the result from39the synthetic dataset.The results of queries such as counts and histograms are altered by the size ofthe dataset, so for some queries we also optimize a parameter k that is used to scalequeries on the synthetic dataset. For instance, a synthetic dataset with double thesize of the real dataset will produce a count query that is roughly double the samecount query on the real dataset. Since the size of the dataset can be privacy leaking,we use a small amount of the budget to initialize k with some random noise beforestarting the optimization procedure. For each miss we update w and k for multipleepochs E using the same result from the real dataset, but recomputing the queryfrom the synthetic dataset with the new parameters at each iteration. This processis described in Algorithm 1.Another technique used to alleviate the outsized effect of some query types isthe normalization of query results to values between 0 and 1. For example, formean queries we extracted a normalized result by getting the min and the max ofthe column that was used to compute the mean, and getting the following normal-ized result (r−min(col))/(max(col)−min(col)). For count queries we simplydivide by the parameter k so that we get r/k. Other queries will have their ownintuitive computations for normalizing the values between 0 and 1.During the development process we noticed that without normalization weoverfitted to queries with large results, which hindered the accuracy of other queries.Another potential solution is to standardize the dataset itself, but we chose not tofollow this route because our synthetic dataset would not be useful for analytictasks that do not use standardized or normalized datasets and we would still have aproblem with large count queries.40Algorithm 1: Parameter Update (Query) E is the number of epochs,q(S,w,k) is a query on the synthetic dataset, q(D) is a query on the realdataset.UpdateCacheParams(w, k, D, S):for t ≤ E dorD = Q(D)rS = Q(S,w,k)f = |rD− rS|∇ fw = f d fdw∇ fk = f d fdkwt+1 = wt −η∇ fwkt+1 = kt −η∇ fkendFor gradient queries we update the weights on the synthetic dataset each timethe SmartCache misses on a gradient query. The procedure for the update, de-scribed in Algorithm 2, takes the parameters of a machine learning model θ andthe gradient updates computed for this model when using the synthetic dataset andthe real dataset. The gradient updates are used to compute Lw, the normalized dotproduct of two gradient tensors.Lw =∇ f Sθ ·∇ f Dθ‖∇ f Sθ ‖2 · ‖∇ f Dθ ‖2(9.1)Furthermore, we take the gradient of Lw with respect to w and minimize thenormalized dot product between gradients from the two datasets. For each miss,we update w multiple times as denoted by the number of epochs E. We have foundthat this helps the cache warm-up faster and find better weights earlier.41Algorithm 2: Parameter Update (Gradient) E is the number of epochsfor each update, S is the synthetic dataset, D is the real dataset, θ is theparameters of the regression model trained using loss Lθ , and w is theweights of the synthetic dataset. Gradients w.r.t. to θ are returned fromthe synthetic dataset in Q(θ ,w,S) and the real dataset in Q(θ ,D).UpdateCacheParams(w, θ , D, S):for t ≤ E do∇ f Sθ = Q(θ ,w,S)∇ f Dθ = Q(θ ,D)g = Lw(∇ f Sθ ,∇ fDθ )∇gw = g dgdwwt+1 = wt −η∇gwend9.4 Quality checkThe quality check procedure is used to prevent the SmartCache from releasinglow quality results. The error between results from the synthetic and real datasetsare compared to a user-defined threshold with noise added to it, so that the processis DP. If the error is below the threshold, the synthetic result is released. If the erroris above the threshold, the real result with DP is released. For statistical queries webase the error threshold on the distribution of DP noise. A user can set a thresholdso that the difference between the real and synthetic result falls within x% of thevalues from the sampling distribution of the noise. A smaller value of x leads tomore precise queries, while a larger value may be less precise, but will lead to morehits. For example, a query is executed on the real dataset and noise is added to itby sampling from N(0,σ). The user wants a hit if the difference between the realand synthetic value is within 95% of the samples from the Gaussian distribution.The threshold is defined by setting T = φ−1(0.95), where φ is the inverse of thecumulative distribution function.For gradient queries we use the normalized dot product as the hit threshold.This is a good threshold because it returns a hit when the gradient computed onthe synthetic dataset is pointing in a similar direction as the gradient from the real42dataset. The user can decrease the threshold if they are comfortable with a greatervariation in the direction of the gradients, or they can increase the threshold, so thatthey only have hits when the direction of the two gradients is close together.To bound the sensitivity of the threshold for the gradient queries we slightlymodify the normalized dot product formula, so that the threshold isT =1lnn∑i=0l∑j=0gi jS · g˜i jD‖gi jS ‖2Cwhere gi jS is the gradient for the i-th example and l-th layer on the syntheticdataset and g˜i jD is the clipped gradient for the i-th example and l-th layer on the realdataset. This formula has a sensitivity of 1nProof: Assume the `1-sensitivity of function f taken over adjacent datasets Dand D′ is given by ∇1 f = maxD,D′ || f (D)− f (D′)||1.f (D) =1lnn∑i=0l∑j=0gi jS · g˜i jD‖gi jS ‖2C(9.2)=1ln(n−1∑i=0l∑j=0gi jS · g˜i jD‖gi jS ‖2C+l∑j=0gn jS · g˜n jD‖gn jS ‖2C)≤ 1ln(n−1∑i=0l∑j=0gi jS · g˜i jD‖gi jS ‖2C+l∑j=0‖gn jS ‖2‖g˜n jD ‖2‖gn jS ‖2C)=1ln(n−1∑i=0l∑j=0gi jS · g˜i jD‖gi jS ‖2C+l∑j=0‖gn jS ‖2C‖gn jS ‖2C)=1ln(n−1∑i=0l∑j=0gi jS · g˜i jD‖gi jS ‖2C+l∑j=01)=1ln(n−1∑i=0l∑j=0gi jS · g˜i jD‖gi jS ‖2C)+lln=1ln(n−1∑i=0l∑j=0gi jS · g˜i jD‖gi jS ‖2C)+1nSince adjacent datasets differ by at most one row assume without loss of gen-erality that43f (D) =1ln(n−1∑i=0l∑j=0gi jS · g˜i jD‖gi jS ‖2C)+1n(9.3)f (D′) =1ln(n−1∑i=0l∑j=0gi jS · g˜i jD‖gi jS ‖2C)This means thatmaxD,D′|| f (D)− f (D′)||1 = maxD,D′|| 1ln(n−1∑i=0l∑j=0gi jS · g˜i jD‖gi jS ‖2C)+1n− 1ln(n−1∑i=0l∑j=0gi jS · g˜i jD‖gi jS ‖2C)||1(9.4)= maxD,D′||1n||1=1nQEDIf the calculated value is within the stipulated threshold, the SmartCache willdeem the value to be accurate and will return the value from the synthetic dataset,thus minimizing the use of the privacy budget. On the other hand, if the value isnot within the threshold it will fail the quality check. In this case, the answer fromthe real dataset is returned and more of the privacy budget is consumed. We cancontrol the quality check to use a larger value of ε and thus consume less of thebudget. This allows us to find a balance where if there are enough hits we use lessof the budget than querying just from the real dataset. For example, in a regular DPsetup we will consume a part of the budget with every query. The value of ε cannotbe too small or else the accuracy of the query will suffer. In the SmartCache, if aquery is a cache miss we consume both εq, the privacy loss for the query, and εc,the privacy loss due to the added noise in the quality check mechanism. The trickis that we can use smaller values of ε for the threshold, since the accuracy of thequery depends less on it. If there is a hit we consume only εc. This means that ifthere are enough hits we end up with privacy savings.44Another option is to use the sparse vector mechanism as a quality check mecha-nism. The sparse vector technique lets us report queries such that privacy degradesonly with the number of queries above a threshold. In the basic formulation of thetechnique, noise is added to the result of a query and the answer is reported onlywhen the noisy value exceeds the threshold. Therefore, the total privacy loss of afunction is the number of queries above the threshold. In the SmartCache setting, ifthe error from a query exceeds the sparse vector technique threshold the real valueis returned and the threshold is renoised. If the error is below the threshold thenthe value from the synthetic dataset is returned.9.5 Budget AnalysisThe privacy budget in the SmartCache can be divided into three groups: datageneration, queries, and the quality check. The synthetic dataset used for theSmartCache has to be generated in a DP manner. This means that noise is addedduring the generation process and some of the privacy budget is consumed upfront.The more noise that is added to the generated dataset, the more private it becomes,but the less accurate it will be. We use εg to stand for the privacy loss stemmingfrom the data generation process. The budget from the generated data is only con-sumed once during the initialization of the SmartCache. The synthetic dataset canthen be used without any more budget penalties.After the initial data is generated the SmartCache is ready to receive queries.Queries only consume the privacy budget from the SmartCache if an answer fromthe real dataset is returned. We let εq to stand for the privacy loss stemming fromeach query that misses and that has to return an answer from the real dataset. Ontop of εq each query also consumes some budget from the quality check procedureεc. The total budget consumption for the SmartCache if there are n queries and mmisses isεt = εg+mεq+nεcIf the sparse vector mechanism is used for the quality check the quality checkbudget will be consumed only when there is a miss. The total budget consumptionwhen the sparse vector mechanism is used is given by45εt = εg+mεq+mεcThe budget accounting can look a bit different if Re´nyi differential privacy isused to account for the budget spent by the queries. In Re´nyi-DP, also known as(ε,α)−RDP, the budget expenditure can be given in terms of the best value ofalpha, which gives tighter bounds on the privacy loss of the queries.46Chapter 10SmartCache EvaluationThe goal of the SmartCache is to reduce the budget spent by a set of queries,thus allowing users to perform more queries without compromising the privacy ofindividuals in the dataset. On top of that, we also want the SmartCache to provideaccurate results. In this evalation we want to answer two research questions:1. How much budget is spent by using the SmartCache when compared to an-swering queries directly from the real dataset with DP?2. How does the SmartCache affect the accuracy of queries and how does itcompare to answering queries from a synthetic dataset with uniform weights?To evaluate the SmartCache we ran experiments on the bank-marketing [28]and the avocado prices [11] datasets. The bank-marketing dataset contains a com-bination of 16 categorical and numerical features and a total of 45211 rows. Theavocado prices dataset also contains a combination of categorical and numericalfeatures but with a total of 11 features and 18249 rows. These experiments mea-sured the accuracy of different statistical queries and gradient queries and calcu-lated the privacy cost of using the SmartCache against querying the real datasetwith differential privacy. Experiments were run on an Ubuntu 18 machine with32GB of RAM and an Intel Core i7-8700 CPU with six cores. A Nvidia GeForceGTX 1080 with 8GB of memory was used as the graphics processing unit.4710.1 Budget SpentWe evaluated the budget savings for statistical queries by executing 600 queriesagainst the SmartCache and recording the privacy loss after each query was exe-cuted. We compared the privacy loss of the SmartCache to the privacy loss ofdirectly querying the real dataset with noise added to the result of each query. Theblue line shows the budget spent by the SmartCache and the green line shows thebudget spent by our baseline (querying a real dataset with DP). The red line showsthe amount of budget spent by using just a synthetic dataset with DP guarantees,without the decision mechanism, quality check, and decision mechanism used inthe SmartCache. In short, the budget spent by the red line is equivalent to the bud-get spent in the data generation process. The SmartCache is considered succesfulif the blue line is below the green line, or in the case of gradient queries, if the blueline is below the green line before convergence. This means that the SmartCacheused less of the privacy budget than the baseline.When answering statistical queries for the avocado dataset (Figure 10.1), theSmartCache was able to yield privacy savings when using a threshold error of 0.99and 0.999, but it was not able to yield privacy savings when a more strict thresh-old of 0.9 was used. The reasons why the SmartCache is not able to yield privacysavings with a threshold of 0.9 are two-fold: there is an initial cost for generat-ing data and misses are more expensive because of the budget spent answeringthe query and performing the quality check. These results can be improved by ei-ther improving the query extrapolation process, so that the weights are better tunedand we have more hits, or by improving the decision mechanism so that we havefewer misses when we decide to use the cache. As seen in Figure 10.2 the Smart-Cache was not able to yield privacy savings when answering statistical querieson the bank-marketing dataset. It was close to breaking even with thresholds of0.99 and 0.999, but the initial cost for data generation added extra expenses to theprivacy budget that made the total budget consumed by the SmartCache highterthan the budget consumed by the DP baseline. There seems to be a dataset de-pendency in the results, as evidenced by the contrast in performance between thebank-marketing and avocado datasets. A possible reason for these differences isthat the hyperparameters chosen for the avocado dataset were better tuned to the48task than the hyperparameters chosen for the bank-marketing dataset.Figure 10.1: Budget spent after answering 500 statistical queries on the av-ocado dataset. The 500 queries were a mix of mean, histogram andcount queries. Each graph shows the results of using the SmartCachewith a threshold of 0.9 (top left) 0.99 (top right), and 0.999 (bottom).49Figure 10.2: Budget spent after answering 500 statistical queries on the bank-marketing dataset. The 500 queries were a mix of mean, histogram andcount queries. Each graph shows the results of using the SmartCachewith a threshold of 0.9 (top left) 0.99 (top right), and 0.999 (bottom).For gradient queries we trained both a fully connected model and a ridge re-gression to convergence by using the SmartCache and recorded the privacy lossafter each iteration in the training of the model. We compared the privacy loss ofthe SmartCache to the privacy loss of directly training a DP model on the real data.As seen in Figure 10.3 the SmartCache is able to consume a mininal amount ofbudget for the first 200 queries of the ridge regression. Afterwards, we see the bud-get consumed by the SmartCache rise rapidly and overtake the budget consumedby the model trained only on the real dataset with DP. This is because of the extraexpense in the quality check procedure. This rapid rise in budget consumption canbe mitigated by having the decision mechanism make more accurate predictions,but towards the middle of training it becomes innacurate. The budget spent by theSmartCache eventually overtakes the budget spent by the real dataset with DP, butthis happens only after the model converges as denoted by the dotted yellow line,50which leads to privacy savings. The results for the bank-marketing dataset (Figure10.4) was not as favourable as the results for the avocado dataset. As denoted bythe dotted convergence line, the budget consumed by the SmartCache surpassesthe budget consumed by the DP baseline before the model converges. Nonethe-less, the total budget consumed by both was similar and the SmartCache was ableto stay under the green line for close to three fifths of the queries. Once again, ifthe decision mechanism is able to identify that we have more misses when closerto convergence, we would be able to have budget savings in Figure 10.4.Figure 10.3: Budget spent after each query used to answer ridge regressionon the avocado dataset.51Figure 10.4: Budget spent after each query used to answer ridge regressionon the bank-marketing dataset.With the avocado dataset, the fully connected model performed significantlybetter than the ridge regression in terms of budget saved. Figure 10.5 shows thatthe fully connected model consumed a small amount of budget and most of thequeries hit the cache. It is not clear why the fully connected model performed somuch better than the ridge regression, but with better selection of thresholds andhyperparameters it is possible that the ridge regression can have similar perfor-mance. The results with the avocado dataset did not translate to the bank-marketingdataset (Figure 10.6). For the bank-marketing dataset the budget consumed alwaysstayed above the budget consumed by the DP baseline. Careful selection of hyper-parameters may help yield better results for other dataset types.52Figure 10.5: Budget spent after each query used to answer fully connectedmodel on the avocado dataset.Figure 10.6: Budget spent after each query used to answer fully connectedmodel on the bank-marketing dataset.10.2 AccuracyIt is important for the SmartCache to return accurate results for it to be prac-tical. We evaluate the accuracy of statistical queries executed on the SmartCacheby measuring the mean absolute error of queries executed using the SmartCacheto the DP values on the real dataset. We compare this error to the error of return-53ing queries using only a synthetic dataset without the weight parameters used bythe SmartCache. Before the absolute error was computed for statistical queries theresult from the query on the synthetic dataset and the SmartCache were dividedby the query threshold, which is based on the sensitivity of the query. This wasdone so that the results from different query types can be compared and analyzedtogether. For example, a= |(p/t)− (r/t)|, where a is the absolute error, p is eitherthe predicted value from the SmartCache or the synthetic dataset, r is the real valuewith DP and t is the query threshold.As seen in Table 10.1 the SmartCache significantly improves the accuracywhen compared to just using a synthetic dataset to answer queries. This showsthat it can maintain the quality of queries released to the user within the stipu-lated threshold. The SmartCache was run for different choices of threshold, so thatreleased queries fall within 90% 99% and 99.9% of DP noise.Type Dataset Thresh MAE MAE ScaledSmartCache Avocado 0.9 10749.53 0.39SmartCache Avocado 0.99 11951.83 0.35SmartCache Avocado 0.999 15354.082 0.10Synth Avocado - 259040.38 4.50SmartCache Bank-Marketing 0.9 43.19 0.24SmartCache Bank-Marketing 0.99 116.33 0.27SmartCache Bank-Marketing 0.999 150.81 0.28Synth Bank-Marketing - 1958.72 2.54Table 10.1: Average absolute error and average variance of queries answeredusing the SmartCache and the synthetic dataset with uniform weights.MAE is the mean absolute error and thresh is the threshold used to de-termine hits for the SmartCache.For gradient queries we trained a ridge regression and fully connected modelto convergence using the SmartCache and compared the final loss of the modeltrained using the SmartCache to a model trained using only the real data with DPguarantees and a model using only DP generated synthetic data.Figures 10.7 10.8 and Figures 10.9 10.10 show that both the fully connected54model and the ridge regression were trained to similar validation loss using theSmartCache as to using the real dataset with DP. The red line in both graphs showthe results of training the models with only the synthetic dataset and without anyof the weight update procedures used in the SmartCache (weights are uniform forevery row). These graphs show how the weight update procedure helps improvethe accuracy of the model.Figure 10.7: Validation loss after each query used to answer ridge regressionon avocado dataset.Figure 10.8: Validation loss after each query used to answer ridge regressionon bank-marketing dataset.55Figure 10.9: Validation loss after each query used to answer fully connectedmodel on avocado dataset.Figure 10.10: Validation loss after each query used to answer fully connectedmodel on bank-marketing dataset.Given the results in this section, we can see that the SmartCache was ableto optimize the use of the privacy budget when answering gradient queries andstatistical queries for some thresholds. Unfortunately, the results didn’t translate aswell for different dataset types, but with more careful hyperparameter tuning webelieve it is possible to improve these results. The second goal of the SmartCachewas to maintain good accuracy when answering queries. This goal was achieved56when answering both gradient queries, as evidenced by the low validation error ofthe model trained using the SmartCache, and the low absolute error of the statisticalqueries answered using the SmartCache.57Chapter 11SmartCache Related WorkOptimizing the use of the privacy budget is an active research area in differ-ential privacy. Without good mechanisms to control the amount of budget spentby successive queries, users may be blocked from issuing more queries. There-fore, maximizing the use of the privacy budget is important to make a system moreusable. Techniques such as the multiplicative weights mechanism and the sparsevector mechanism have provided interesting ways to improve the use of the privacybudget and influenced the design of the SmartCache. Nonetheless, in SmartCachewe have taken some of these ideas that work well in theory and in some restrictedscenarios and made them more practical.11.1 Multiplicative WeightsThe multiplicative weights mechanism [20] allows for a large number of in-teractive counting or linear queries to be answered. The multiplicative weightsmechanism views databases as distributions over the data universe. Each item inthe database is associated with a positive weight, where the initial weights are auniform distribution where each weight is 1/N. When the t-th query qt arrives anoisy answer is computed by adding Laplace noise to the true answer. The answerfrom round t is compared to the answer from round t−1. If the answers betweenthe rounds are close then the weights are kept the same as in the previous round.If the answers are far from each other the weights on the dataset are reweighted58by using multiplicative reweighting, so that the new updated database is closer toan accurate answer. This method is similar to what we do in the SmartCache. Infact, it is the inspiration to the weighted dataset approach used by the SmartCache.Nonetheless, the multiplicative weights mechanism deals with only linear queries,while the SmartCache is also able to deal with non-linear queries such as returningupdate gradients for neural networks. Another difference is that the SmartCacheis meant to support a varied number of queries, that more closely resembles theworkload of a real data analyst. This led to the implementation of the decisionmechanism and the quality check mechanism so that we can guarantee good accu-racy and better utilize the privacy budget.More recent work has shown that the multiplicative weights mechanism canalso be used to answer linear convex minimization queries [38]. This work hasshown that multiplicative weights can be used to answer a large number of queriesused to train a machine learning model as long as the optimization problem isconvex. This differs from the SmartCache approach where we are also able toanswer queries to train non-linear models with non-convex minimization, such aswith neural networks.11.2 Sparse Vector TechniqueThe sparse vector technique [16] [23] satisfies differential privacy and allowsa person to output some queries without an added privacy cost. The sparse vectortechnique works by setting a certain threshold T and outputing whether an answerfrom a query is above or below the threshold. The threshold has noise added to itand each query result is compared to this perturbed threshold. If a query result isbelow the threshold no budget is consumed. The privacy budget is only deductedwhen the outcome of a query is above the threshold. This means that as long asqueries are not above the threshold, queries can still be answered with no privacyrisk. This mechanism is useful in settings where results above the threshold aresparse. For example, if users only care about results that are above the thresholdand most queries issued by them are below the threshold, the sparse vector tech-nique becomes a good alternative to save the privacy budget.When compared to the SmartCache, the sparse vector technique is another59method to help privacy budget preservation. In fact, it can be slightly modifiedand used in the quality check to decide whether to release a query from the real orsynthetic dataset. Nonetheless, the sparse vector technique would require a hit-rateof above 50% for any budget gains, since there is a cost to renoise the thresholdwhen a query is above it, thus doubling the amount of privacy budget necessaryfor the system. In other words, if query results that are above the threshold are nottruly sparse, the sparse vector mechanism is not a good choice. This issue is miti-gated in the SmartCache by using the decision mechanism to reduce the amount oftimes we use the SmartCache and have a miss.11.3 Other Budget Optimizing SystemsThe above techniques have been adopted by various systems with the purposeof optimizing the use of the privacy budget. Honeycrisp [34] and Orchard [35]use the sparse vector technique to increase the number of times a query can beanswered before a budget runs out. Nonetheless, they do not focus on strict budgetoptimization and thus lack features in the SmartCache such as the weighted syn-thetic dataset and decision mechanism to help decide when it is viable to use thesparse vector technique.Other data analytics systems such as Airavat [9] for a MapReduce interface andPINQ [26] for SQL like queries exist. Despite the strong and mature querying ca-pabilities of these systems, they do not have the privacy budget optimization focusof the SmartCache. Nonetheless, many of the techniques used in the SmartCachecan be integrated into other data analytics systems.60Chapter 12ConclusionThis thesis presented two systems: LEAP and the SmartCache. LEAP solvesthe problem of performing data analytics on multiple sites. There is substantialoverhead to using LEAP (up to 2.5X slower when training a model such as Resnet-18), but it provide benefits when data sharing. Some of these benefits are controlover data (e.g revoking access), facilitating data agreements, and time saved notcentralizing data. These benefits are in large part achieved by the federated natureof the system: raw data does not need to be centralized to answer queries.The SmartCache, on the other hand, solves the issue of optimizing the privacybudget. It allows users to perform more queries before a dataset is at risk of leakingprivate information. The SmartCache was able to train models to the same valida-tion loss as a DP baseline on the real dataset and consumed close to 70% less of theprivacy budget when training a fully connected model on the avocado dataset. Forstatistical queries, results varied depending on the thresholds used. For thresholdsof 0.99 and 0.999 the SmartCache consumed approximately 30% and 50% less ofthe budget for the same amount of queries when compared to querying the realdataset with DP.Despite both systems standing on their own, they can also interact. LEAP,for example, can issue DP queries when dealing with sensitive datasets. In thisinstance, the SmartCache can be used on each site to answer queries from a weighttuned synthetic dataset, and thus allowing each site to answer more queries withoutputting individuals present in the datasets at risk.61Bibliography[1] URL https://www.distributedgenomics.ca/. → page 30[2] URL https://www.datashield.org/. → page 31[3] grpc. URL https://grpc.io/. → page 18[4] Jwt.io. URL https://jwt.io/. → page 21[5] Protocol buffers. URL https://developers.google.com/protocol-buffers. →page 18[6] Redcap. URL https://www.project-redcap.org/. → page 11[7] Aug 2021. URL https://www.openspecimen.org/? cf chl jschl tk =pmd024dcf3e278a0ae7fbabeca869d673b0eb0a7fb2-1629177294-0-gqNtZGzNAc2jcnBszQhi.→ page 11[8] M. Abadi, A. Chu, I. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar,and L. Zhang. Deep learning with differential privacy. In Proceedings of the2016 ACM SIGSAC Conference on Computer and Communications Security,CCS ’16, page 308–318, New York, NY, USA, 2016. Association forComputing Machinery. ISBN 9781450341394.doi:10.1145/2976749.2978318. URLhttps://doi.org/10.1145/2976749.2978318. → page 2[9] I. R. S. T. S. Ann and K. V. S. E. Witchel. Airavat: Security and privacy formapreduce. In Proc. Usenix Org, pages 297–312, 2011. → page 60[10] S. Aydore, W. Brown, M. Kearns, K. Kenthapadi, L. Melis, A. Roth, andA. Siva. Differentially private query release through adaptive projection,2021. → page 3[11] H. A. Board. Avocado prices, 06 2018. URLhttps://www.kaggle.com/neuromusic/avocado-prices. → page 4762[12] J. Dong, A. Roth, and W. J. Su. Gaussian differential privacy. arXiv preprintarXiv:1905.02383, 2019. → page 2[13] C. Dwork. Differential privacy: A survey of results. In Theory andApplications of Models of Computation””TAMC, volume 4978 of LectureNotes in Computer Science, pages 1–19. Springer Verlag, April 2008. URLhttps://www.microsoft.com/en-us/research/publication/differential-privacy-a-survey-of-results/. → pages 2, 6[14] C. Dwork, K. Kenthapadi, F. McSherry, I. Mironov, and M. Naor. Our data,ourselves: Privacy via distributed noise generation. In Advances inCryptology (EUROCRYPT 2006), volume 4004 of Lecture Notes inComputer Science, pages 486–503. Springer Verlag, May 2006. URLhttps://www.microsoft.com/en-us/research/publication/our-data-ourselves-privacy-via-distributed-noise-generation/. → page 8[15] C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise tosensitivity in private data analysis. In S. Halevi and T. Rabin, editors, Theoryof Cryptography, pages 265–284, Berlin, Heidelberg, 2006. Springer BerlinHeidelberg. ISBN 978-3-540-32732-5. → pages 2, 6[16] C. Dwork, M. Naor, O. Reingold, G. N. Rothblum, and S. Vadhan. On thecomplexity of differentially private data release: efficient algorithms andhardness results. In Proceedings of the forty-first annual ACM symposiumon Theory of computing, pages 381–390, 2009. → page 59[17] C. Dwork, G. N. Rothblum, and S. Vadhan. Boosting and differentialprivacy. In 2010 IEEE 51st Annual Symposium on Foundations of ComputerScience, pages 51–60, 2010. doi:10.1109/FOCS.2010.12. → page 2[18] C. Dwork, A. Roth, et al. The algorithmic foundations of differentialprivacy. Foundations and Trends in Theoretical Computer Science, 9(3-4):211–407, 2014. → page 2[19] K. Emam, D. Buckeridge, R. Tamblyn, A. Neisa, E. Jonker, and A. Verma.The re-identification risk of canadians from longitudinal demographics.BMC medical informatics and decision making, 11:46, 06 2011.doi:10.1186/1472-6947-11-46. → page 2[20] M. Hardt and G. N. Rothblum. A multiplicative weights mechanism forprivacy-preserving data analysis. In 2010 IEEE 51st Annual Symposium onFoundations of Computer Science, 2010. → pages 3, 5863[21] Z. He, T. Zhang, and R. B. Lee. Model inversion attacks againstcollaborative inference. In Proceedings of the 35th Annual ComputerSecurity Applications Conference, ACSAC ’19, page 148–162, New York,NY, USA, 2019. Association for Computing Machinery. ISBN9781450376280. doi:10.1145/3359789.3359824. URLhttps://doi.org/10.1145/3359789.3359824. → page 2[22] P. Kairouz, S. Oh, and P. Viswanath. The composition theorem fordifferential privacy. IEEE Transactions on Information Theory, 63(6):4037–4049, 2017. doi:10.1109/TIT.2017.2685505. → pages 2, 8[23] M. Lyu, D. Su, and N. Li. Understanding the sparse vector technique fordifferential privacy, 2016. → page 59[24] M. Le´cuyer, R. Spahn, K. Vodrahalli, R. Geambasu, and D. Hsu. Privacyaccounting and quality control in the sage differentially private ml platform.Proceedings of the 27th ACM Symposium on Operating Systems Principles,Oct 2019. doi:10.1145/3341301.3359639. URLhttp://dx.doi.org/10.1145/3341301.3359639. → pages 2, 3[25] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas.Communication-efficient learning of deep networks from decentralized data.In Artificial Intelligence and Statistics, pages 1273–1282. PMLR, 2017. →page 5[26] F. D. McSherry. Privacy integrated queries: an extensible platform forprivacy-preserving data analysis. In Proceedings of the 2009 ACM SIGMODInternational Conference on Management of data, pages 19–30, 2009. →page 60[27] I. Mironov. Re´nyi differential privacy. In 2017 IEEE 30th ComputerSecurity Foundations Symposium (CSF), pages 263–275, 2017. → page 3[28] S. Moro, P. Cortez, and P. Rita. A data-driven approach to predict thesuccess of bank telemarketing. Decision Support Systems, 62:22–31, 2014.ISSN 0167-9236. doi:https://doi.org/10.1016/j.dss.2014.03.001. URLhttps://www.sciencedirect.com/science/article/pii/S016792361400061X. →page 47[29] T. Murakami and Y. Kawamoto. Utility-optimized local differential privacymechanisms for distribution estimation. In 28th USENIX SecuritySymposium (USENIX Security 19), pages 1877–1894, Santa Clara, CA, Aug.2019. USENIX Association. ISBN 978-1-939133-06-9. URL https:64//www.usenix.org/conference/usenixsecurity19/presentation/murakami. →page 3[30] A. Narayanan and V. Shmatikov. Robust de-anonymization of large sparsedatasets. In 2008 IEEE Symposium on Security and Privacy (sp 2008), pages111–125, 2008. → page 2[31] M. Nasr, R. Shokri, and A. Houmansadr. Comprehensive privacy analysis ofdeep learning: Passive and active white-box inference attacks againstcentralized and federated learning. In 2019 IEEE Symposium on Securityand Privacy (SP), pages 739–753, 2019. doi:10.1109/SP.2019.00065. →page 2[32] S. M. Plis, A. D. Sarwate, D. Wood, C. Dieringer, D. Landis, C. Reed, S. R.Panta, J. A. Turner, J. M. Shoemaker, K. W. Carter, P. Thompson,K. Hutchison, and V. D. Calhoun. Coinstac: A privacy enabled model andprototype for leveraging and processing decentralized brain imaging data.Frontiers in Neuroscience, 10:365, 2016. ISSN 1662-453X.doi:10.3389/fnins.2016.00365. URLhttps://www.frontiersin.org/article/10.3389/fnins.2016.00365. → page 31[33] E. Rescorla. tls, Aug 2018. URLhttps://datatracker.ietf.org/doc/html/rfc8446. → page 19[34] E. Roth, D. Noble, B. H. Falk, and A. Haeberlen. Honeycrisp: Large-scaledifferentially private aggregation without a trusted core. In Proceedings ofthe 27th ACM Symposium on Operating Systems Principles, SOSP ’19, page196–210, New York, NY, USA, 2019. Association for ComputingMachinery. ISBN 9781450368735. doi:10.1145/3341301.3359660. URLhttps://doi.org/10.1145/3341301.3359660. → pages 2, 60[35] E. Roth, H. Zhang, A. Haeberlen, and B. C. Pierce. Orchard: Differentiallyprivate analytics at scale. In 14th USENIX Symposium on Operating SystemsDesign and Implementation (OSDI 20), pages 1065–1081. USENIXAssociation, Nov. 2020. ISBN 978-1-939133-19-9. URLhttps://www.usenix.org/conference/osdi20/presentation/roth. → pages 2, 60[36] R. Shokri, M. Stronati, and V. Shmatikov. Membership inference attacksagainst machine learning models. CoRR, abs/1610.05820, 2016. URLhttp://arxiv.org/abs/1610.05820. → page 265[37] P. Tschandl, C. Rosendahl, and H. Kittler. The ham10000 dataset, a largecollection of multi-source dermatoscopic images of common pigmented skinlesions. Scientific data, 5(1):1–9, 2018. → page 23[38] J. Ullman. Private multiplicative weights beyond linear queries, 2015. →page 59[39] W. G. Van Panhuis, P. Paul, C. Emerson, J. Grefenstette, R. Wilder, A. J.Herbst, D. Heymann, and D. S. Burke. A systematic review of barriers todata sharing in public health. BMC public health, 14(1):1–9, 2014. → page 1[40] Z. Yang, J. Zhang, E.-C. Chang, and Z. Liang. Neural network inversion inadversarial setting via background knowledge alignment. In Proceedings ofthe 2019 ACM SIGSAC Conference on Computer and CommunicationsSecurity, CCS ’19, page 225–240, New York, NY, USA, 2019. Associationfor Computing Machinery. ISBN 9781450367479.doi:10.1145/3319535.3354261. URLhttps://doi.org/10.1145/3319535.3354261. → page 2[41] D. Zhang, R. McKenna, I. Kotsogiannis, G. Bissias, M. Hay,A. Machanavajjhala, and G. Miklau. ektelo: A framework for definingdifferentially private computations. ACM Trans. Database Syst., 45(1), Feb.2020. ISSN 0362-5915. doi:10.1145/3362032. URLhttps://doi.org/10.1145/3362032. → page 266
Thesis/Dissertation
eng
Computer Science
Vancouver : University of British Columbia Library
Attribution-NonCommercial-NoDerivatives 4.0 International
Graduate
Beschastnikh, Ivan
Talhouk, Aline
Large scale federated analytics and differential privacy budget preservation
Text