Stephen Pfohl
email: spfohl@stanford.edu

Ben Marafino
email: marafino@stanford.edu

Adrien Coulet
email: acoulet@stanford.edu

Fatima Rodriguez
email: frodrigu@stanford.edu

Latha Palaniappan
email: lathap@stanford.edu

Nigam H Shah

Creating Fair Models of Atherosclerotic Cardiovascular Disease

Keywords: Applied computing → Health informatics electronic health records, fairness, cardiovascular disease, adversarial learning, risk prediction, machine learning

Guidelines for the management of atherosclerotic cardiovascular disease (ASCVD) recommend the use of risk stratification models to identify patients most likely to benefit from cholesterollowering and other therapies. These models have differential performance across race and gender groups with inconsistent behavior across studies, potentially resulting in an inequitable distribution of beneficial therapy. In this work, we leverage adversarial learning and a large observational cohort extracted from electronic health records (EHRs) to develop a "fair" ASCVD risk prediction model with reduced variability in error rates across groups. We empirically demonstrate that our approach is capable of aligning the distribution of risk predictions conditioned on the outcome across several groups simultaneously for models built from high-dimensional EHR data. We also discuss the relevance of these results in the context of the empirical trade-off between fairness and model performance.

INTRODUCTION

Atherosclerotic cardiovascular disease (ASCVD), which includes heart attack, stroke, and fatal coronary heart disease, is a major cause of mortality and morbidity worldwide, as well as in the U.S., where it contributes to 1 in 3 of all deaths-many of which are preventable [START_REF] Benjamin | Heart disease and stroke statistics-2018 update: a report from the American Heart Association[END_REF]. In deciding whether to prescribe cholesterol-lowering therapies to prevent ASCVD, physicians are often guided by risk estimates yielded by the Pooled Cohort Equations (PCEs). PCEs provide a proportional hazards model [START_REF] David C Goff | ACC/AHA guideline on the assessment of cardiovascular risk: a report of the American College of Cardiology/American Heart Association Task Force on Practice Guidelines[END_REF] that leverages nine clinical measurements to predict the 10-year risk of a first ASCVD event. However this model has been found to overestimate risk for female patients [START_REF] Mora | Evaluation of the pooled cohort risk equations for cardiovascular risk prediction in a multiethnic cohort from the Women's Health Initiative[END_REF], Chinese patients [START_REF] Paul Defilippis | Risk score overestimation: the impact of individual cardiovascular risk factors and preventive therapies on the performance of the American Heart Association-American College of Cardiology-Atherosclerotic Cardiovascular Disease risk score in a modern multi-ethnic cohort[END_REF] or globally [START_REF] Yadlowsky | Clinical implications of revised pooled cohort equations for estimating atherosclerotic cardiovascular disease risk[END_REF], as well as also underestimate risk for other groups such as Korean women [START_REF] Keum | The ACC/AHA 2013 pooled cohort equations compared to a Korean Risk Prediction Model for atherosclerotic cardiovascular disease[END_REF]. Such mis-estimation results in an inequitable distribution of the benefits and harms of ASCVD risk scoring, because incorrect risk estimates can expose patients to substantial harm through both under-or over-treatment; potentially leading to preventable cardiovascular events or side effects from unnecessary therapy, respectively.

The inability of the PCEs to generalize to diverse cohorts likely owes to both under-representation of minority populations in the cohorts used to develop the PCEs and shifts in medical practice and lifestyle patterns in the decades since data collection for those cohorts. In attempting to correct for these patterns, one recent study [START_REF] Yadlowsky | Clinical implications of revised pooled cohort equations for estimating atherosclerotic cardiovascular disease risk[END_REF] updated the PCEs using data from contemporary cohorts and demonstrated that doing so reduced the number of minority patients incorrectly misclassified as being high or low risk. Similar results were observed in the same study with an approach using an elastic net classifier, rather than a proportional hazards model. However, neither approach is able to explicitly guarantee an equitable distribution of mis-estimation across relevant subgroups, particularly for race-and gender-based subgroups.

To account for under-represented minorities and to take advantage of the wider variety of variables made available in electronic health records (EHRs), we derive a large and diverse modern cohort from EHRs to learn a prediction model for ASCVD risk. Furthermore, we investigate the extent to which we can encode algorithmic notions of fairness, specifically equality of odds, [START_REF] Hardt | Equality of opportunity in supervised learning[END_REF] into the model to encourage an equitable distribution of performance across populations. To the best of our knowledge, our effort is the first to explore the extent to which this formal fairness metric is achievable for risk prediction models built using high-dimensional data from the EHR. We show that while it is feasible to develop models that achieve equality of odds, we emphasize that this process involves trade-offs that must be assessed in a broader social and medical context [START_REF] Verghese | What this computer needs is a physician: humanism and artificial intelligence[END_REF].

BACKGROUND AND RELATED WORK 2.1 ASCVD Risk Prediction and EHRs

The PCEs are based on age, gender, cholesterol levels, blood pressure, and smoking and diabetes status and were developed by pooling data from five large U.S. cohorts [START_REF] David C Goff | ACC/AHA guideline on the assessment of cardiovascular risk: a report of the American College of Cardiology/American Heart Association Task Force on Practice Guidelines[END_REF] composed of white and black patients, with white patients constituting a majority. Recently, attempts [START_REF] Yadlowsky | Clinical implications of revised pooled cohort equations for estimating atherosclerotic cardiovascular disease risk[END_REF] were made to update the PCEs to improve model performance for race-and gender-based subgroups using elastic net regression and data from modern prospective cohorts. However, this effort focused on demographic groups and variables already used to develop the PCEs and did not consider other populations or clinical measurements. The increasing adoption of EHRs offers opportunities to deploy and refine ASCVD risk models. Efforts have recently been undertaken to apply and refine existing models, including the PCEs and the Framingham score, to large EHR-derived cohorts and characterize their performance in certain subgroups [START_REF] Pike | Improvement in cardiovascular risk prediction with electronic health records[END_REF][START_REF] Jamal S Rana | Accuracy of the atherosclerotic cardiovascular risk equation in a large contemporary, multiethnic population[END_REF]. Beyond ASCVD risk prediction, there exist many recent works that develop prediction models with EHRs, which are reviewed in [START_REF] Benjamin A Goldstein | Opportunities and challenges in developing risk prediction models with electronic health records data: a systematic review[END_REF].

Fair Risk Prediction

We consider the case where supervised learning is used to estimate a function f (X ) that approximates the conditional distribution p(Y |X ), given N samples {x i , y i , z i } N i=1 drawn from the distribution p(X , Y , Z ). We take X ∈ X = R m to correspond to a vector representation of the medical history extracted from the EHR prior to a patient-specific index time t i ; Y ∈ Y = {0, 1} to be a binary label, which for patient i, indicates the presence of the outcome observed in the EHR in the time frame [t i , t i + w i ], where w i is a parameter specifying the amount of time following the index time used to derive the outcome; and Z ∈ Z = {0, . . . , k -1} indicates a sensitive attribute, such as race, gender, or age, with k groups. The output of the learned function f (X ) ∈ [0, 1] is then thresholded with respect to a value T to yield a prediction Ŷ ∈ {0, 1}.

One standard metric for assessing the fairness of a classifier with respect to a sensitive attribute Z is demographic parity [START_REF] Dwork | Fairness through awareness[END_REF], which evaluates the independence between Z and the prediction Ŷ .

Formally, the demographic parity criterion may be expressed as

p( Ŷ |Z = Z i ) = p( Ŷ |Z = Z j ) ∀ Z i , Z j ∈ Z. (1)
However, optimizing for demographic parity is of limited use for clinical risk prediction, because doing so may preclude the model from considering relevant clinical features associated with the sensitive attribute and the outcome, thus decreasing the performance of the model for all groups [START_REF] Kleinberg | Inherent trade-offs in the fair determination of risk scores[END_REF]. Another related metric is equality of odds [START_REF] Hardt | Equality of opportunity in supervised learning[END_REF], which stipulates that the prediction Ŷ be conditionally independent of Z , given the true label Y . Formally, satisfying equality of odds implies that

p( Ŷ |Z = Z i , Y = Y k ) = p( Ŷ |Z = Z j , Y = Y k ) ∀ Z i , Z j ∈ Z; Y k ∈ Y. (2)
From this, it can be seen that, if equality of odds is achieved, then for a fixed threshold T , both the false positive (FPR) and false negative rates (FNR) are equal across all pairs of groups defined by Z . Compared to demographic parity, equality of odds is more appropriate in a clinical setting, since it does not necessarily preclude the learning of the optimal predictor in the case that a true relationship between sensitive attribute and the outcome exists [START_REF] Hardt | Equality of opportunity in supervised learning[END_REF].

Furthermore, this definition can be extended to the case of a continuous risk score by requiring that

p(f (X )|Z = Z i , Y = Y k ) = p(f (X )|Z = Z j , Y = Y k ) ∀ Z i , Z j ∈ Z; Y k ∈ Y. (3)
In this case, the distribution of the predicted probability of the outcome conditioned on whether the event occurred or not should be matched across groups of a sensitive variable. Formulation 3 is stronger than 2 since it implies that equality of odds is achieved for all possible thresholds, thus requiring that the same ROC curve be attained for all groups. This is desirable since it provides the end-user the ability to freely adjust the decision threshold of the model without violating equality of odds.

Finally, we also note that satisfying equality of odds for a continuous risk score may be reduced to the problem of minimizing a divergence over each pair (Z i , Z j ) of distributions referenced in equation [START_REF] Brier | Verification of forecasts expressed in terms of probability[END_REF]. Adversarial learning procedures [START_REF] Goodfellow | Generative adversarial nets[END_REF] are well-suited to this problem in that they provide a flexible framework for minimizing the divergence over distributions parameterized by neural networks. As such, several related works [START_REF] Beutel | Data decisions and theoretical implications when adversarially learning fair representations[END_REF][START_REF] Edwards | Censoring representations with an adversary[END_REF][START_REF] Madras | Learning Adversarially Fair and Transferable Representations[END_REF][START_REF] Hu Zhang | Mitigating unwanted biases with adversarial learning[END_REF] have demonstrated the benefit of augmenting a classifier with an adversarial discriminator in order to align the distribution of predictions for satisfying fairness constraints.

Approaches for Achieving Fairness

Despite considerable interest in the ethical implications of implementing machine learning in healthcare [START_REF] Danton S Char | Implementing machine learning in health care -addressing ethical challenges[END_REF][START_REF] I Glenn Cohen | The legal and ethical concerns that arise from using complex predictive analytics in health care[END_REF], relatively little work exists characterizing the extent to which risk prediction models developed with EHR data satisfy formal fairness constraints.

Adversarial approaches for satisfying fairness constraints (in the form of demographic parity) have been explored in several recent works in non-healthcare domains. One approach, [START_REF] Edwards | Censoring representations with an adversary[END_REF], in the context of image anonymization, demonstrated that representations satisfying demographic parity could be learned by augmenting a predictive model with both an autoencoder and an adversarial component. The adversarial approach to fairness was further investigated by [START_REF] Beutel | Data decisions and theoretical implications when adversarially learning fair representations[END_REF] with a gradient reversal objective for data that is imbalanced in the distribution of both the outcome and in the sensitive attribute.

In attempting to address the limitations of demographic parity as a metric, [START_REF] Hardt | Equality of opportunity in supervised learning[END_REF] introduced equality of odds as an alternative and devised post-processing methods to achieve it for fixed-threshold classifiers. Recently, [START_REF] Hu Zhang | Mitigating unwanted biases with adversarial learning[END_REF] and [START_REF] Madras | Learning Adversarially Fair and Transferable Representations[END_REF] generalized the adversarial framework to achieve equality of odds by providing the discriminator access to the value of the outcome.

Both demographic parity and equality of odds are referred to as group fairness metrics since they are concerned with encouraging an invariance of some property of a classifier over groups of a sensitive attribute. While straightforward to compute and reason about, optimizing for these metrics may produce models that are discriminatory over structured subgroups within and across groups of sensitive attributes, constituting a form of fairness gerrymandering [START_REF] Kearns | Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairness[END_REF]. The competing notion of individual fairness [START_REF] Dwork | Fairness through awareness[END_REF] and may be able to address these concerns by assessing whether a model produces similar outputs for similar individuals. However, this notion is often of limited practical use due to the challenges of developing a domain-specific similarity metric that encodes desired notions of fairness.

Recent efforts [START_REF] Hébert-Johnson | Multicalibration: Calibration for the (computationally-identifiable) masses[END_REF] have investigated an alternative to both group and individual fairness metrics with a process that audits a classifier to discover subgroups for which the model is under-performing and iteratively improve model performance for those groups, resulting in a non-negative change in model performance for all computationally-identifiable subgroups.

The closest related work examining the fairness of risk prediction models in healthcare is [START_REF] Chen | Why Is My Classifier Discriminatory?[END_REF], which, in the context of mortality prediction in intensive care units, argued that any trade-off between model performance and fairness across subgroups is undesirable. They propose that the prediction error should be decomposed in terms of bias, variance, and noise and that the relative contribution of these terms be used to guide additional data collection.

METHODS

The Dataset and Cohort Definition

We extract records from the Stanford Medicine Research Data Repository [START_REF] Henry J Lowe | STRIDE-An integrated standards-based translational research informatics platform[END_REF], a clinical data warehouse containing records on roughly three million patients from Stanford Hospital and Clinics and Lucile Packard Children's Hospital for clinical encounters occurring between 1990 and 2017. We define a prediction task that resembles the setting in which the PCEs were developed for the purpose of guiding physician decision-making in ASCVD prevention and construct a corresponding cohort. As a first step, we identify all patients with at least two clinical encounters over at least two years for which they are 40 years of age or older. Then, for each patient we select an index time t i uniformly at random from the interval that allows for at least one year of history and one year of follow-up. We exclude from the cohort patients that have an history of cardiovascular artery disease (including ASCVD and atrial fibrillation) or a prescription of an anti-hypertensive drug in the five years prior to the index time. Finally, we assign a positive ASCVD label for a patient if a diagnosis code for an ASCVD event is observed at any point in their record following the index time. The exclusion criteria (i.e. the list of cardiovascular-related diseases and medications) is provided as supplementary material, along with the list of clinical concepts used for defining ASCVD events. The patients are randomly partitioned such that 80%, 10%, 10% are used for training, validation, and testing, respectively.

Sensitive Attributes

We consider race, gender, and age as sensitive attributes and assess model performance and fairness with respect to them. For race, we use both race and ethnicity variables to partition the cohort into six disjoint groups: Asian, Black, Hispanic, Other, Unknown, and White. Patients not considered Hispanic thus have either a non-Hispanic or unknown ethnicity. For gender, we partition the cohort into male and female populations. For age, we discretize the age at the index time into four disjoint groups: 40-55, 55-65, 65-75, and 75+ years, where the intervals are inclusive on the lower bound and exclusive on the upper bound. A summary of these groups is presented in Table 1.

Feature Extraction

For feature extraction, we adopt a strategy similar to the one described in [START_REF] Reps | Design and implementation of a standardized framework to generate and evaluate patient-level prediction models using observational healthcare data[END_REF] to convert time-stamped sequences of clinical concepts across several domains (i.e., diagnoses, procedures, medication orders, lab tests, clinical encounter types, departments, and other observations) into a static representation suitable for modeling. For each extracted patient, we filter the historical record to include only those concepts occurring prior to the index time. We encode as a binary attribute each unique clinical concept observed in the dataset according to whether that concept was present anywhere in the patient's history prior to the prediction time; otherwise, it is absent or missing. Similarly, we do not use the numeric results of Table 2: Distribution alignment metrics. We report the coefficient of variation (CV; the ratio of the standard deviation to the mean) of the false positive rate (FPR, CV) and false negative rate (FNR, CV) at a fixed decision threshold of 0.075 across the race, gender, and age groups. Furthermore, we compute the pairwise earth mover's distance (EMD) between distributions of the predicted probabilities of having an ASCVD event, conditioned on the true ASCVD label y for each group of each sensitive attribute and take the mean.

Race

Adversarial Learning for Equality of Odds

Model Training and Evaluation

The training procedure is composed of four experiments and thus produces four prediction models. The first model is trained to predict the risk of ASCVD and does not use adversarial training. The other three models result from separate training runs in which each of the discrete race, gender, and age variables are considered as sensitive attributes in the adversarial training procedure. We refer to these four experiments as Standard, EQ race , EQ gender , and EQ age .

For all experiments, we employ fully-connected feedforward neural networks with a fixed set of hyperparameters. The ASCVD prediction model is composed of the sum over an embedding layer of dimension 100 followed by two hidden layers of dimension 128 and leaky ReLU nonlinearities. The adversarial network maintains a similar architecture, but with one hidden layer of dimension 64 and takes the prediction logit and ASCVD outcome as inputs. Training proceeds in a batch setting with the Adam optimizer [START_REF] Kingma | Adam: A method for stochastic optimization[END_REF] with learning rate 10 -3 , β 1 = 0.5, and β 2 = 0.9 with batch size 256 over the training set and early stopping based on the area under the receiver operating characteristic curve (AUC-ROC) for ASCVD [START_REF] Paszke | Automatic differentiation in PyTorch[END_REF].

For each model, we compute standard metrics on the entire test set and on each subgroup. Specifically, we report the AUC-ROC, the area under the precision-recall curve (AUC-PRC), the Brier score [START_REF] Brier | Verification of forecasts expressed in terms of probability[END_REF] as a measure of calibration, and the false positive and false negative rates (FPR, FNR) at a fixed threshold of T = 0.075, in keeping with current ASCVD guidelines for the prescription of statin therapy [START_REF] David C Goff | ACC/AHA guideline on the assessment of cardiovascular risk: a report of the American College of Cardiology/American Heart Association Task Force on Practice Guidelines[END_REF][START_REF] Yadlowsky | Clinical implications of revised pooled cohort equations for estimating atherosclerotic cardiovascular disease risk[END_REF]. To express adherence to the standard equality of odds definition in equation 2, we report the coefficient of variation (i.e. the ratio of the standard deviation to the mean) of the FPR and FNR at T = 0.075 across the groups of each sensitive attribute. To assess the distance between the distributions presented in (3), we compute the earth mover's distance (EMD, or first Wasserstein distance) between the empirical distributions of the predicted probability of ASCVD conditioned on whether ASCVD occurred or not for each group of each sensitive attribute in a pairwise fashion and take the mean within each strata.

RESULTS

Cohort Characteristics

The cohort extraction procedure produces a cohort of 253,547 patients having 71,554 features, with 5,886 patients labeled as positive for ASCVD (Table 1). We note that in this cohort, there are 135,438 white patients, constituting a majority, and 8,549 black patients. Across racial groups, ASCVD rates range from 2.0-3.0%, with the exception of patients with unknown race, who experience a reduced rate of 0.86%. Furthermore, we observe higher ASCVD rates for male patients compared to female patients. Finally, ASCVD rates appear to increase monotonically with age, with rates ranging from 0.95% for the 40-55 age group to 6.7% for patients age 75 or older.

Distribution Alignment with Adversarial Training

Applying the adversarial training procedure results in a alignment of the distributions of the predicted probability of ASCVD conditioned on the true outcome label (Figure 1). Without employing a adversarial discriminator, the center of mass of these distributions appears to depend significantly on the base ASCVD rate in the group. However, these differences largely disappear when training in an adversarial setting. This results in a substantial reduction in the mean pairwise EMD between each predictive distribution in both outcome strata for both gender and age, with a negligible effect for race (Table 2). Furthermore, we note that variability in the FPRs and FNRs at a fixed threshold of 0.075 is greatly reduced following adversarial training (Table 2), indicating that the approach successfully encourages the model predictions to satisfy equality of odds.

The relative lack of success in minimizing the mean pairwise EMD between the conditional predictive distributions across racial groups (Table 2) may be largely explained by the anomalous characteristics of the group of patients having unknown race. For instance, when using standard training (Standard), the predictive distribution conditioned on a positive ASCVD outcome for the unknown race group is clearly separated from that of the five groups while the distributions for those five are mostly aligned (Figure 1). However, when training the model in an adversarial setting, it appears that the primary effect is to align the predictive distribution for the unknown race group to the region inhabited by the distributions of the remaining groups while disturbing the relative alignment between the distributions for those groups.

The Cost of Fairness

Satisfying equality of odds with an adversarial objective incurs a reduction in AUC-ROC, AUC-PRC, and calibration for the population at large (Table 3), with the largest negative effects observed when training to adjust for the differences across age groups (Standard AUC-ROC = 0.793 vs. EQ age AUC-ROC = 0.743). However, for ranking metrics such as the AUC-ROC, the effects can be unintuitive following an adjustment of the subgroup predictive distributions. For instance, the adversarial training procedure for age actually leads to an increase in AUC-ROC for the majority 40-55 years group (Standard AUC-ROC = 0.713 vs. EQ age AUC-ROC = 0.727) (Table 4) despite the stark decline in the AUC-ROC observed on the population as a whole. Furthermore, several of the populations assessed experience a reduction in performance for some metrics with improvements in others following training for equality of odds. In other cases, the effect is largely positive. Notably, model performance improves on all metrics except for the fixed threshold FNR for the black population, a group for which the model attains the lowest AUC-ROC (0.753) and is the least well-calibrated (Brier Score = 0.034) for the standard setting.

It has been shown that developing a well-calibrated model is an objective that conflicts with that of satisfying equality of odds [START_REF] Kleinberg | Inherent trade-offs in the fair determination of risk scores[END_REF][START_REF] Pleiss | On fairness and calibration[END_REF]. In our case, we observed such a trade-off, but judged it to be minor due to a small increase in the Brier score for almost every subgroup following training for equality of odds (Table 2).

DISCUSSION

We have demonstrated the capabilities of adversarial training procedures to encourage the learning of models whose predictions satisfy equality of odds for high-dimensional EHR data with sensitive attributes of more than two groups. In a setting such as ASCVD risk prediction, with a clear clinical intervention associated with the prediction, this procedure ensures that no group bears a disparate burden of mistreatment due to misclassification. However, we note that this comes at a cost of a reduction in AUC-ROC and AUC-PRC for some subgroups.

Limitations of the Predictive Model

While using EHR data allowed a high-capacity ASCVD risk prediction model to be trained using a large and diverse cohort, this model should not be directly compared to the PCEs for several reasons. First, the PCEs estimate ten-year ASCVD risk, whereas our model estimates risk over a period of at least a year. Furthermore, we cannot rule out the existence of biases that may lead to differential rates of selection or censoring in our cohort across age, gender, and race based subgroups, nor can we establish whether the nature of these biases differ from those present in the prospective cohort studies used to derive the PCEs.

Moving Beyond Equality of Odds

While we have demonstrated empirically that adversarial learning procedures are capable of encouraging a model to satisfy equality of odds, the use of this metric as a measure of fairness should be approached with caution. In the case that there is insufficient information in the training dataset to learn a high performing model for at least one group, optimizing for this criteria will upper bound the group-level model performance by the performance obtained for the least-well performing group. In the adversarial learning setting, this reduction in performance for some groups may be offset by performance gains for groups for which the model performs poorly when trained naively. However, we observed that if such a benefit exists, it is smaller than the reduction in performance incurred for most groups.

We have not examined the relationship between the errors of the predictive model and notions of long-term utility when deploying the model clinically. To properly analyze the effect of these errors on utility requires careful causal modeling of the sequential decision-making process following ASCVD risk prediction while accounting for individual patient characteristics. We emphasize that while such a process is crucial to evaluate the long-term impact of any prediction model, it is not possible to properly identify and model that causal process with observational data in the EHR alone [START_REF] Kilbertus | Avoiding discrimination through causal reasoning[END_REF]. Additionally, it is unclear that satisfying fairness constraints for a single-step decision, as in ASCVD risk prediction, aligns with the goal of equitably maximizing long-term utility, as it has been shown that satisfying fairness constraints for a static decision may actually cause long-term harm in settings where an unconstrained objective would not [START_REF] Liu | Delayed Impact of Fair Machine Learning[END_REF], particularly if the outcome is measured with bias due to systematic censoring [START_REF] Kallus | Residual Unfairness in Fair Machine Learning from Prejudiced Data[END_REF]. We find those approaches [START_REF] Kusner | Counterfactual fairness[END_REF][START_REF] Nabi | Fair inference on outcomes[END_REF] that establish causal notions of fairness to be promising directions for future work, as they permit sequential decision making processes to be studied under the lens of fairness at both the group and individual level.

CONCLUSION

Existing approaches to ASCVD risk scoring perform poorly for the population at large, with more extreme risk mis-estimates for minority populations, inadvertently exposing those groups to excess harm. We develop an ASCVD prediction model using EHR data and show that we can encourage formal notions of fairness by reducing the variability in the FPR and FNR across groups. It is not yet known to what extent algorithmic notions of fairness align with other goals, including long-term utility maximization. We hope that our results will serve as an impetus for the community at large to investigate the fairness-utility trade-off during sequential clinical decision making resulting from fairness constraints imposed on clinical risk assessments.

A EXCLUSION CRITERIA:

CARDIOVASCULAR ARTERY DISEASES

B EXCLUSION CRITERIA: ANTIHYPERTENSIVE DRUGS

Here we list the medications from the Antomatical Therapeutic Chemical Classification System (ATC) used to exclude patients on the basis of a history of prescription of anti-hypertensive drugs at the prediction time. Rauwolfia alkaloids (C02AA); rescinnamine (C02AA01); reserpine (C02AA02); deserpidine (C02AA05); methoserpidine (C02AA06); methyldopa (levorotatory) (C02AB01); clonidine (C02AC01); guanfacine (C02AC02); moxonidine (C02AC05); rilmenidine (C02AC06); trimetaphan (C02BA01); mecamylamine (C02BB01); prazosin (C02CA01); indoramin (C02CA02); doxazosin (C02CA04); urapidil (C02CA06); betanidine (C02CC01); guanethidine (C02CC02); debrisoquine (C02CC04); diazoxide (C02DA01); dihydralazine (C02DB01); hydralazine (C02DB02); minoxidil (C02DC01); nitroprusside (C02DD01); pinacidil (C02DG01); metirosine (C02KB01); pargyline (C02KC01); ketanserin (C02KD01); bosentan (C02KX01); ambrisentan (C02KX02); macitentan (C02KX04); riociguat (C02KX05); alprenolol (C07AA01); oxprenolol (C07AA02); pindolol (C07AA03); propranolol (C07AA05); timolol (C07AA06); sotalol (C07AA07); nadolol (C07AA12); mepindolol (C07AA14); carteolol (C07AA15); tertatolol (C07AA16); bopindolol (C07AA17); bupranolol (C07AA19); penbutolol (C07AA23); practolol (C07AB01); metoprolol (C07AB02); atenolol (C07AB03); acebutolol (C07AB04); betaxolol (C07AB05); bisoprolol (C07AB07); celiprolol (C07AB08); esmolol (C07AB09); nebivolol (C07AB12); talinolol (C07AB13); labetalol (C07AG01); carvedilol (C07AG02); metoprolol and felodipine (C07FB02); atenolol and nifedipine (C07FB03).

C OUTCOME DEFINITION: ASCVD

  To develop an ASCVD risk prediction model that satisfies the definition of equality of odds in (3), we consider two fully-connected neural networks: a classifier f : R m → R ∈ [0, 1] parameterized by θ f that predicts the probability of the ASCVD outcome Y given data X ; and a discriminator д : R × {0, 1} → [0, 1] k parameterized by θ д that takes as input both the logit of the output of f and the value of the true label Y to predict a distribution over the groups of a sensitive attribute Z . If L cl s and L adv are the cross-entropy losses of the classifier predictions over Y and the discriminator predictions over Z , respectively, then the training procedure may be described by alternating between the steps min θ f L cl s -L adv and min θ д L adv .

Figure 1 :

 1 Figure 1: Empirical distribution of the predicted probability of developing ASCVD in the followup period conditioned on whether ASCVD occurred. Plots are stratified by experimental condition (Standard or EQ), true value of the ASCVD outcome (y = 0 or y = 1), and the variable treated as sensitive (race, gender, or age).

  Here we list the set of concepts from the Observational Medical Outcomes Partnership vocabulary version 5.3 used to define the presence of ASCVD in the followup period.Acute myocardial infarction (312327); Cerebral artery occlusion (372924); Acute ill-defined cerebrovascular disease (374060); Cerebral embolism (375557); Acute myocardial infarction of anterior wall (434376); Acute myocardial infarction of lateral wall (436706); Basilar artery occlusion (437308); Acute myocardial infarction of inferior wall (438170); Acute myocardial infarction of anterolateral wall (438438); Acute myocardial infarction of inferolateral wall (438447); Multiple and bilateral precerebral arterial occlusion (439295); True posterior myocardial infarction (439693); Acute myocardial infarction of inferoposterior wall (441579); Cerebral thrombosis (441874); Precerebral arterial occlusion (443239); Acute subendocardial infarction (444406); Infarction -precerebral (4043731); Cerebral infarction due to embolism of cerebral arteries (4108356); Acute myocardial infarction of atrium (4108669); Cerebral infarction due to thrombosis of cerebral arteries (4110192); Vertebral artery obstruction (4185117); Carotid artery obstruction (4288310).

Table 1 :

 1 Cohort characteristics. The number of patients extracted, the incidence of the ASCVD outcome and the average length of follow-up for each subgroup are shown.

	Group	Count	ASCVD Incidence (%)	Follow-up Length (years)
	Asian	30,294	2.3	3.2
	Black	8,549	3.0	3.2
	Hispanic	20,240	2.0	2.9
	Other	19,062	2.2	3.1
	Unknown	39,964	0.86	3.1
	White	135,438	2.8	3.6
	Female	149,594	1.9	3.4
	Male	103,953	2.9	3.3
	40-55	121,437	0.95	3.4
	55-65	61,214	2.1	3.5
	65-75	43,800	3.7	3.2
	75+	27,096	6.7	3.0
	All	253,547	2.8	3.4

Table 3 :

 3 Model performance measured on the test set without stratification for each experimental condition.

		Standard EQ race EQ gender EQ age
	AUC-ROC	0.793	0.772	0.779	0.743
	AUC-PRC	0.133	0.125	0.13 0.0965
	Brier Score	0.0205 0.0207	0.0206 0.0211

prediction in the validation set. All training was performed on a single GPU with the PyTorch library

Table 4 :

 4 Model performance measured on the test set stratified by group and experimental condition. EQ corresponds to training for the sensitive attribute corresponding to the subgroup of interest. FPR and FNR are computed at a fixed decision threshold of 0.075.

		AUC-ROC	AUC-PRC	Brier Score	FNR		FPR
		Stand.	EQ Stand.	EQ Stand.	EQ Stand.	EQ Stand.	EQ
	Asian	0.819 0.771	0.138	0.155	0.0196	0.0197	0.683 0.587	0.0388 0.0903
	Black	0.753 0.756	0.162	0.2	0.034	0.0338	0.621	0.69	0.0781 0.0437
	Hispanic	0.811 0.803	0.117 0.0816	0.0142	0.015	0.667	0.6	0.0391 0.0945
	Other	0.813 0.822	0.13	0.113	0.0217	0.0219	0.711 0.556	0.0544	0.102
	Unknown	0.713 0.718	0.0619 0.0406 0.00766 0.00812	0.844 0.719 0.00944 0.0353
	White	0.774 0.766	0.146	0.155	0.0245	0.0245	0.6 0.619	0.0804 0.0714
	Female	0.8 0.786	0.12	0.122	0.0173	0.0174	0.684 0.625	0.0423 0.0567
	Male	0.775 0.769	0.148	0.143	0.0249	0.025	0.592	0.64	0.0818 0.0672
	40-55	0.713 0.727	0.0404 0.0275	0.0085 0.00922	0.952 0.817 0.00683 0.0573
	55-65	0.736 0.708	0.0919 0.0676	0.0195	0.0198	0.794 0.746	0.0409 0.0618
	65-75	0.736 0.739	0.128	0.141	0.0349	0.0347	0.608 0.669	0.115	0.088
	75+	0.776 0.763	0.228	0.224	0.053	0.0548	0.351 0.607	0.251 0.0806

  Dysarthria as late effects of cerebrovascular disease (43530687); Visual disturbance as sequela of cerebrovascular disease (43531583); Acute combined systolic and diastolic heart failure (44782718); Chronic combined systolic and diastolic heart failure (44782719); Acute on chronic combined systolic and diastolic heart failure (44782733).

	Moyamoya disease (378774); Cerebrovascular disease (381591); Sub-
	clavian steal syndrome (433505); Late effects of cerebrovascular dis-
	ease (434056); Acute myocardial infarction of anterior wall (434376);
	Vertebral artery syndrome (434656); Weakness of face muscles
	(434657); Acute myocardial infarction of lateral wall (436706); Basi-
	lar artery occlusion (437308); Ataxia (437584); Aneurysm of heart
	(438168); Acute myocardial infarction of inferior wall (438170);
	Acute myocardial infarction of anterolateral wall (438438); Acute
	myocardial infarction of inferolateral wall (438447); Multiple and
	bilateral precerebral arterial occlusion (439295); True posterior my-
	ocardial infarction (439693); Left heart failure (439846); Vertigo
	as late effect of stroke (440426); Acute myocardial infarction of
	inferoposterior wall (441579); Cerebral thrombosis (441874); Pre-
	cerebral arterial occlusion (443239); Dysphagia as a late effect of
	cerebrovascular accident (443465); Monoplegia of dominant upper
	limb as a late effect ofcerebrovascular accident (443525); Apraxia
	due to cerebrovascular accident (443551); Arteriosclerosis of coro-
	nary artery bypass graft (443563); Systolic heart failure (443580);
	Diastolic heart failure (443587); Paralytic syndrome of nondomi-
	nant side as late effect of stroke (443599); Paralytic syndrome of
	dominant side as late effect of stroke (443609); Acute subendocar-
	dial infarction (444406); Infarction -precerebral (4043731); Verte-
	brobasilar territory transient ischemic attack (4048785); Cerebral
	infarction due to embolism of cerebral arteries (4108356); Acute
	myocardial infarction of atrium (4108669); Cerebral infarction due
	to thrombosis of cerebral arteries (4110192); Occlusion of artery
	(4162038); Vertebral artery obstruction (4185117); Ischemic heart
	disease (4185932); Myocardial ischemia (4186397); Carotid artery ob-
	struction (4288310); Chronic systolic heart failure (40479192); Dys-
	phasia as late effect of cerebrovascular disease (40479575); Chronic
	diastolic heart failure (40479576); Aphasia as late effect of cere-
	brovascular disease (40480002); Sensory disorder as a late effect
	of cerebrovascular disease (40480449); Acute on chronic systolic
	heart failure (40480602); Acute systolic heart failure (40480603);
	Monoplegia of lower limb as late effect of cerebrovascular disease
	(40480938); Monoplegia of nondominant lower limb as a late effect
	of cerebrovascular accident (40480946); Acute diastolic heart failure
	(40481042); Acute on chronic diastolic heart failure (40481043); Ar-
	teriosclerosis of coronary artery bypass graft of transplanted heart	Here we list the set of concepts from the Observational Medical
	(40481132); Speech and language deficit as late effect of cerebrovas-	Outcomes Partnership vocabulary version 5.3 used to exclude pa-
	cular accident (40481354); Hemiplegia as late effect of cerebrovas-	tients on the basis of a history of cardiovascular artery disease at
	cular disease (40481762); Monoplegia of upper limb as late effect	the prediction time.
	of cerebrovascular disease (40481842); Coronary atherosclerosis	Monoplegia of dominant lower limb as a late effect of cerebrovas-
	(40481919); Monoplegia of nondominant upper limb as a late effect	cular accident (197303); Acute myocardial infarction (312327); Hy-
	of cerebrovascular accident (40482266); Residual cognitive deficit	pertensive encephalopathy (312938); Atrial fibrillation (313217);
	as late effect of cerebrovascular accident (40482301); Arterioscle-	Nonpyogenic thrombosis of intracranial venous sinus (314667);
	rosis of autologous vein coronary artery bypass graft (40482638);	Chronic ischemic heart disease (315286); Preinfarction syndrome
	Arteriosclerosis of nonautologous coronary artery bypass graft	(315296); Angina decubitus (315832); Heart failure (316139); Aneurysm
	(40482655); Combined systolic and diastolic dysfunction (40482727);	of coronary vessels (316427); Cerebral atherosclerosis (316437);
	Arteriosclerosis of arterial coronary artery bypass graft (40483189);	Coronary occlusion (316995); Coronary arteriosclerosis (317576);
	Hemiplegia of nondominant side as late effect of cerebrovascular	Postmyocardial infarction syndrome (319038); Congestive heart
	disease (40484513); Hemiplegia of dominant side as late effect of	failure (319835); Angina pectoris (321318); Dissecting aneurysm of
	cerebrovascular disease (40484522); Coronary arteriosclerosis in	coronary artery (321879); Paralytic syndrome as late effect of stroke
	native artery (42872402); Coronary arteriosclerosis in native artery	(372654); Cerebral artery occlusion (372924); Transient cerebral is-
	of transplanted heart (43021821);	chemia (373503); Basilar artery syndrome (374055); Acute ill-defined
		cerebrovascular disease (374060); Cerebral ischemia (374384); Cere-
		bral embolism (375557); Vertebrobasilar artery syndrome (376714);

ACKNOWLEDGMENTS

We would like to thank Sam Corbett-Davies, Julia Daniels, and Sebastian Le Bras for early advice and insightful discussion.

This material is based upon work supported by the National Science Foundation Graduate Research Fellowship Program DGE-1656518; NLM R01 LM011369-06; NLM T15 LM007033. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the funding bodies. We also thank the Widen Horizons program of the IDEX Lorraine Université d'Excellence (15-IDEX-0004) and the Snowball Associate Team funded by Inria.


Anoop Singhal

Jaideep Vaidya

Preface

This volume contains the papers selected for presentation at the 34th Annual IFIP WG11.3 Conference on Data and Applications Security and Privacy (DBSec 2020), that was supposed to be during June 25-26, 2020, in Regensburg. While the conference was held on the dates as scheduled, due to the COVID-19 situation it was held virtually (for the first time in the history of DBSec), instead of physically in Regensburg.

In response to the call for papers of this edition, 41 submissions were received, and all submissions were evaluated on the basis of their significance, novelty, and technical quality. The Program Committee, comprising 40 members, performed an excellent job, with the help of additional reviewers, of reviewing all submissions through a careful anonymous process (three or more reviews per submission). The Program Committee's work was carried out electronically, yielding intensive discussions. Of the submitted papers, 14 full papers and 8 short papers were selected for presentation at the conference.

The success of DBSec 2020 depended on the volunteering effort of many individuals, and there is a long list of people who deserve special thanks. We would like to thank all the members of the Program Committee and all the external reviewers, for all their hard work in evaluating the papers and for their active participation in the discussion and selection process. We are very grateful to all people who readily assisted and ensured a smooth organization process, in particular Günther Pernul for his efforts as DBSec 2020 general chair; Sara Foresti (IFIP WG11.3 chair) for her guidance and support; Yuan Hong and Benedikt Putz (publicity chairs) for helping with publicity; and Petra Sauer for helping with other arrangements for the conference. EasyChair made the conference review and proceedings process run very smoothly.

Last but certainly not least, thanks to all the authors who submitted papers and all the conference attendees. We hope you find the proceedings of DBSec 2020 interesting, stimulating, and inspiring for your future research.

April 2020

Anoop Singhal Jaideep Vaidya


Joachim Biskup
email: joachim.biskup@cs.tu-dortmund.de

Inference-Proof Monotonic Query Evaluation and View Generation Reconsidered

Keywords: Abstract data source, A priori knowledge, Best current view, Closed-query evaluation, Condentiality, Epistemic state, Inference-proofness, Interaction protocol, Lying, Prohibition, Security invariant, Simulated current view, View generation

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

High level security requirements like availability, integrity and condentiality have been rened in sophisticated guidelines for constructing and evaluating secure computing systems of various kinds and, correspondingly, a rich variety of specic security mechanisms have been developed. Accordingly, for each concrete class of applications, in the spirit of computing engineering in general, a comprehensive range of considerations is due, from a precise specication of the wanted system functionality and the explicit description of the in most cases conicting security interests of the expected user as well as of further attackers over mathematical models and their formal verication to nal actual implementations and their ongoing multi-literal inspections.

This work is devoted to contribute to such a comprehensive view of security by reconsidering a specic kind of security mechanisms proposed to support the condentiality interests as exceptions of the availability interests of an information owner while using an information system for query evaluation and view generation to communicate with some cooperation partner. Clearly, within this short article we again have to focus on aspects held to be particularly important, including the followings ones. What precisely is the object of protection? Who precisely is seen as an attacker and which precise means are exploited by him for violations? How to formally model the wanted kind of condentiality? What kind of enforcing security mechanisms have been designed? How to mathematically verify their actual achievements? More concretely, we treat these concern by reconsidering a specic fraction of the in the meantime highly ramied line of research about condentiality-preserving queryresponse interactions of a logicoriented information system like a suitably restricted relational database system.

Even more specically, our contributions can be summarized as follows, while the overall achievements and limitations are discussed in the conclusions:

On the layer of social cooperation mediated by computing agents, in Section 2, we identify the epistemic state of an information system agent as the actual object in need of protection against a class of most powerful attackers.

On the layer of computing agents, in Section 3, we further elaborate a formal model of abstract data sources, which captures the relevant features of monotonic and complete information systems.

On the layer of security specication, in Section 4, we adapt inferenceproofness as strong condentiality to the model of abstract data sources.

On the layer of security enforcement, in Section 5, we present unied expositions and verication of security mechanisms in terms of that model.

These contributions areunifying and partly extendingextracted from the seminal work [START_REF] Sicherman | Answering queries without revealing secrets[END_REF][START_REF] Bonatti | Foundations of secure deductive databases[END_REF] and further specic renements [START_REF] Biskup | Lying versus refusal for known potential secrets[END_REF][START_REF] Biskup | Controlled query evaluation for known policies by combining lying and refusal[END_REF][START_REF] Biskup | Controlled query evaluation for enforcing condentiality in complete information systems[END_REF][START_REF] Biskup | Optimality and complexity of inference-proof data ltering and CQE[END_REF][START_REF] Biskup | Inference-proof data ltering for a probabilistic setting[END_REF], which are part of larger eorts [START_REF] Biskup | Selected results and related issues of condentiality-preserving controlled interaction execution[END_REF]. Moreover, we note that our treatment of condentiality is in the spirit of various other work, e.g., already early ones on statistical database security [START_REF] Denning | Cryptography and Data Security[END_REF] and about non-interference of general program execution [START_REF] Goguen | Unwinding and inference control[END_REF], together with the rich elaborations of follow-up studies, which for example are concisely surveyed in [START_REF] Halpern | Secrecy in multiagent systems[END_REF]. In contrast to some other work, we do not aim at total condentiality but see condentiality as an exception from availability and, thus, allow specically declared information ows like for declassication [START_REF] Sabelfeld | Declassication: Dimensions and principles[END_REF] and, additionally, we want to construct enforcing mechanism in the sense of [START_REF] Schneider | Enforceable security policies[END_REF].

Function and Attack Scenario

Since ever, among many other activities, and in a closely intertwined manner, people reason as individuals by acquiring, structuring, keeping and exploiting information to make up their respective minds and behave as social creatures by communicating with others. With the advent of computing technologies, both individually dealing with information and socially communicating have been partly delegated to computing agents. On the one hand, the delegation should facilitate routine task or even enhance human capabilities. On the other hand, depending on the context, as delegators, individuals at their discretion or groups of them according to some socially accepted norm aim to still control the computing agents executing protocols as their delegatees, or at least the human delegators should appropriately congure the computing delegatees.

Being aware of the resulting reduction, we can simplifying map concepts of human reasoning and communication to the inference protocols and interaction protocols of their computing agents and, correspondingly, actually performed human activities to protocol-complying computing process executions. Under such a reduction, and even more simplifying, a group of human individuals is modeled to be complemented by a multi-agent computing conguration. In this model, each human individual controls a dedicated computing agent that, at least partly and by means of protocol executions, both deals with the information owned by that individual, in particular by internally deriving an epistemic state from a chosen information representation, and mediates the communications of that individual, in particular by sending and receiving messages according to one or more agreed interaction protocols.

Though, in principle, each individual can act in diverse roles and, correspondingly, each controlled computing agent can execute diverse protocols, we further specialize the model sketched above in focusing on only two individuals with their computing agents. One individual is seen as an information owner controlling an information system agent, and the other individual is treated as a cooperating communication partner employing a client agent. Moreover, to enable cooperation, in principle the information owner is willing to share information with the communication partner. However, complying with privacy issues or pursuing other condentiality requirements, as an exception from sharing, the information owner might want to hide some specic pieces of information.

Summarizing the simplied model, we assume an overall framework with the eight features outlined in the following and visualized in Figure 1.

1. [Epistemic state of information system agent as single object of protection.]

The human information owner does not deal with information processing and reasoning by himself but only provides the inputs to the information system agent under his control. At each point in time, that agent is internally deriving a formally dened epistemic state.

[Mediation of human communications by interacting computing agents.]

Once having agreed on cooperation, the human information owner and his human communication partner do not communicate directly with each other, but only mediated by the computing agents under their respective control.

[Dedicated access permissions for information sharing.]

As a normally initial input to his information system agent, independently of the actual epistemic state, the information owner has granted dedicated access permissions to his communication partner. That permissions declare that over the time the client agent of the partner may interact with the information system agent of the owner following some explicitly chosen interaction protocols that exclusively refer to the internal epistemic state of the information system agent (but, e.g., not to the physical mind of the information owner or any real world besides the multi-agent model). However, as a further normally initial input to his information system agent, also independently of the actual epistemic state, the information owner explicitly declares exceptions from the dedicated access permissions in the form of prohibitions. Each prohibition species a piece of information that the communication partner should not be able to learn. More precisely, each prohibition being expressed in terms of the information system agent and thus referring to possible epistemic states, the communication partner should never be able to become sure about the actual validity in the epistemic state of the information system agent. In other words, from the partner's point of view it should always appear to be possible that the prohibited piece of information is not valid in the epistemic state of the information system.

[Partner suspected to reason about validity of prohibitions.]

Though the client agent is restricted to exactly follow the interaction protocols mentioned in the dedicated access permissions, the human communication partner can choose any sequence of permitted commands. Moreover, the communication partner is assumed to have unlimited computational resources when rationally reasoning about the validity or non-validity of a prohibited piece of information, whether employing the client agent under his control or any other means.

6. [Security mechanism implanted in owner's information system agent.]

To enforce the condentiality requirements of the information owner, the information system agent is enhanced by some security mechanism that should shield the underlying information processing from a direct contact with the client agent. That security mechanism rst inspects each message to be sent by the information system agent to the client agent according to the pertinent interaction protocol whether a violation of the information owner's condentiality requirements would be enabled on the side of the communication partner. If this is the case, the security mechanism then alters the message such that the message is still as informative as possible on the one hand but all options for a violation are blocked on the other hand.

7.

[Reasoning supported by a priori knowledge and background knowledge.]

First of all, the communication partner's rational reasoning about the internal epistemic state of the information system agent is based on the messages exchanged by the respective computing agents and, thus, completely known to both agents. Additionally, the partner's rational reasoning is presumed to be supported by some a priori knowledge about the application dealt with in the cooperation between the two individuals involved and additional background knowledge comprising both a complete specication of the interaction semantics and the full awareness of the security mechanism (possibly even including the prohibition declaration) and, most notably, nothing else.

[Principle inaccessibility of the partner.]

The internals of both the human communication partner and his client agent are considered to be principally inaccessible for the information owner and his system agent. This implies that the latter ones can only rely on assumptions about the details of the a priori knowledge and a postulation about the background knowledge available to the former ones.

We follow a somehow martial but common terminology of security in computing, which ignores that in many scenarios an individual involved as communication partner will primarily treated as cooperating in a friendly manner.

Partially trusted for consciously sharing information in principle and correctly executing the agreed interaction protocols, the communication partner with the client agent is denoted as a semi-honest attacker, suspected to potentially aiming to maliciously infer the actual validity of pieces of information that the information owner has declared to be kept condential.

Accordingly, the information owner together with the information system agent controlled by himis denoted as the defender.

The security mechanism implanted in the defending information system agent has to invariantly enforce a suitable version of the following still informally expressed security policy of inference-proofness, which also species the attacker model : For each prohibited piece of information ψ, the information content of messages sent to the attacking client agent will never enable the attacking receiver to rationally infer that ψ is valid in the epistemic state, even when inspecting the complete history of preceding interactions, considering some a priori knowledge about the possible epistemic states, applying the semantics of the agreed interaction protocols and being aware of the functionality of the security mechanism (possibly even including the prohibition declaration).

The concept of rationality on the side of the attacker is then captured by the following rephrasement of the still to be suitably versioned security policy of inference-proofness in terms of indistinguishability :

For each prohibited piece of information ψ, for each epistemic state d satisfying the a priori knowledge, for each sequence of messages exchanged during an interaction history and complying with the agreed interaction protocols but potentially altered by the security mechanism, there exists an alternative epistemic state d I such that (i) the same sequence of messages would be generated, in compliance with the agreed interaction protocols and subjected to the alterations by the security mechanism, but (ii) ψ is not valid in d I .

The epistemic state d is thought as actually be derived (or stored) by the information system agent and might satisfy the prohibited piece of information ψ or not. The former case implies that the alternative state d I required to exist is dierent from d; in the latter case, the actually stored state d and the alternative state d I might be the same. Accordingly, declaring ψ as a prohibition does not intent to block any option to infer the non-validity of ψ.

Condentiality as inference-proofness could be trivially achieved by granting no access permissions at all or altering the information content of all messages sent to the attacker to nothing, violating any conicting availability requirements and, thus, making the whole thing useless. Accordingly, condentiality requirements and availability requirements always have to be suitably balanced. We focus on the following three-level conict resolution strategy, which leads to a combination of a constraint solving problem and an optimization problem :

1. As a general rule, for the sake of availability, some dedicated access permissions are granted, as far as not conicting with level 2 of the strategy.

2. As exceptions, for the sake of condentiality specic prohibitions are declared that have to be enforced by alterations made by the security mechanism, but to comply with level 3 of the strategy only as far as denitely necessary.

3. Again for the sake of availability, as limitation for the eect of exceptions, the alterations made have to be minimal.

3

Abstract Data Sources as Epistemic States

The notion of an abstract information system is intended to capture common important features of information contents like at least semi-structured and logicoriented knowledge bases, including relational databases under suitable restrictions, and as far as they are complete regarding query answering under monotonic reasoning. A possibly occurring information content of such an abstract information system is seen as an epistemic state, though it is formally just an element of a pertinent nite or countably innite set. We call such an element an abstract data source , not assuming any internal properties.

However, we impose a set-algebraic structure with natural properties on the considered universe of all abstract data sources. These properties should reect the model-theoretic approach of various monotonic logics to dene semantics for the underlying syntax of a formal language by assigning truth-values to atomic sentences and then, by induction, to all sentences. In fact, if on the syntactic side the language provides means to express negation, conjunction and disjunction, then on the semantic side the corresponding sets of satisfying truth-value assignments (models, interpretations ) are treated by (set) complement, (set) intersection and (set) union, respectively. So, using sentences to syntactically express closed queries whose semantics are the respective sets of satisfying truth-value assignments, we may identify a syntactic query expression with its semantic evaluation. Accordingly, totally refraining from any syntax for abstract information systems, we dene queries as a particular sort of subsets of the universe.

For the case of an innite universe with countably innitely many queries, to deal with iteratively determined xpoints, we even consider countably innite intersections which, however, do not need to generate a query. Instead, we require compactness of the set of queries, which captures a straightforward corollary to the existence of a correct and complete proof system for classical rst-order logic, roughly saying that any (possibly innite) logical entailment implies a nite entailment (since formal proofs are nite by denition). Note that for the nite case this property trivially holds.

A (set) inclusion of the form q 1 q 2 corresponds to a logical entailment in the logics that motivated our abstract settings. In fact, thinking of q 1 and q 2 as the satisfying sets of truth-value assignments for some sentences χ 1 and χ 2 , respectively, then q 1 q 2 says that each truth-value assignment that makes χ 1 true also does so for χ 2 ; this is just the classical denition of logical entailment.

Denition 1 (abstract data sources and closed queries).

A universe of data sources is a (nite or innite) set U . A query set Q for a universe U satises the following properties:

1. tr, U u Q ℘U with Q being nite or countably innite;

2. Q is closed under complement, nite intersection and nite union;

3. Q is compact, i.e., for all Q I Q, for all q Q, if Q I q, then there exists a nite Q P Q I such that

Q P q.
Moreover, SeqpQq is the set of all (possibly) innite sequences of queries and IntpQq is the set of all (possibly) innite intersections of queries.

Following the explanations and the common intuitive understanding, query evaluation could be dened for a query q Q and a data source d U by the expression if d q then true else [if d U zq] false. However, for our formal investigations the following equivalent denition is more convenient.

Denition 2 (abstract (stepwise) query evaluation). Let Q be a query set for an universe U . Then the query evaluation function is dened by

quer : Q ¢ U ÝÑ Q with quer pq, dq if d q then q else U zq . (1)
The stepwise extension quer : SeqpQq ¢ U ÝÑ SeqpQq is dened by quer pxq 1 , q 2 , . . . y, dq xquerpq 1 , dq, quer pq 2 , dq, . . . y.

(2) Equation ( 1) immediately implies that for all data sources d U and d I U , for all queries q Q and q Q the following assertions hold:

d quer pq, dq ,

d I quer pq, dq i quer pq, d I q quer pq, dq ,

if d q and d I q then q quer pq, dq i q quer pq, d I q .

(5)

Besides being an element of the universe, the properties of a data source d U are only determined by its query evaluations. In particular, two data sources are indistinguishable if they are contained in exactly the same queries. Hence, imagining an enumeration q 1 , q 2 , .

4

Inference-Proofness for Known Prohibition Declaration

As explained and motivated in Section 2 we imagine an owner of the abstract information system who implants a security mechanism into the defending information system agent under his control, aiming to enforce inference-proofness of interactions as a sophisticated kind of condentiality regarding the messagebased interactions with an attacking client agent operated by some only semihonest communication partner. We study two interactions:

closed-query evaluation with response preparation: we see the queries as request messages sent from the attacking client agent and the corresponding responses as reaction messages returned by the defending system agent;

view generation : we image a (formally not represented) request message from the attacking client agent to obtain a best view and we see the generation result as the respond message returned by the defending system agent.

Besides the request messages and the respond messages, the formal notions of inference-proofness depend on two further parameters, to be declared by the information system owner specically for the attacking client agent: (i) a set of prohibitions, i.e., pieces of information that the rationally reasoning attacker

should not be able to learn; (ii) the a priori knowledge held by the attacker about the actually stored abstract data source, as assumed by the defender. The attacker is also implicitly postulated to be fully aware of the security mechanism employed by the defender and to even know the declared prohibitions.

The notion of the attacker's rationality is implicitly related to the semantics of query evaluation and view generation. Finally, our notions of inference-proofness include the following natural security preconditions :

The stored data source complies with the (assumed) a priori knowledge. The (assumed) a priori knowledge does not violate the pertinent condentiality requirement expressed by the prohibition declaration.

Denition 4 (abstract prohibitions and abstract a priori knowledge).

1. A prohibition is a query p Q, and a set of enforceable 1 prohibitions is denoted by P Q. A prohibition declaration is a nite set proh P .

2. An assumed a priori knowledge is a query prior Q, and a set of tolerable 1 (pieces of ) assumed a priori knowledge is denoted by A Q.

The following four versions of inference-proofness formally reect the intuitive assumption that the attacker knows the prohibition declaration by treating it being invariant under alternative data sources. Regarding controlled query evaluation, the wanted security mechanisms are naturally intended to operate stepwise and history-dependent but without a look-ahead.

Denition 5 (inference-proofness for closed-query evaluation). prior and proh only on the nite prex q 1 , q 2 , . . . , q t of the argument sequence and, thus, implicitly, also on the nite prex r 1 , r 2 , . . . , r t¡1 of the result sequence with r i con_quer pxq 1 , q 2 , . . . y, d st , prior , prohq i , such that we can dene con_quer pxq 1 , q 2 , . . . , q t y, d st , prior , prohq xr 1 , r 2 , . . . , r t y .

2. The function is inference-proof i for each prohibition declaration proh ℘P , for each a priori knowledge prior A such that prior p for all p proh, for each prohibition p proh, for each (stored) data source d st prior , for each sequence xq 1 , q 2 , . . . y of closed queries q i Q,

Denition 6 (inference-proofness for view generation).

1. con_view : U ¢ A ¢ ℘P ÝÑ IntpQq is a controlled view generation function.

2. The function is inference-proof or strongly inference-proof, respectively, i the corresponding condition, but without the clause for the sequence of queries, of Denition 5, part 2. or part 3, respectively, holds.

1 For each practical framework, the notions of enforceable and tolerable have to be appropriately dened to capture application needs and complexity issues.

Controlled Interactions

We study three fundamental approaches to provably achieve inference-proofness for interaction sequences of unlimited length only consisting of closed-query evaluations together with the respective response preparations for the case of abstract data sources as epistemic states. The achievement of inference-proofness for sequences of stepwise closed-query evaluations will be based on enforcing a pertinent security invariant for all points in time t, starting with some pertinent security precondition. In the denitions of inference-proofness, the latter assertions are already formally stated and the former assertions are suggested by requiring the existence of a harmless data source. In fact, the attacker's best current view bestcv on the defender's actual data source d st always consists of all those data sources d I that are indistinguishable from the actual one and, thus, constitutes the least uncertainty left to the attacker so far. Accordingly, the harmless data source d al required to exist has to be an element of the attacker's best current view.

Conceptually, at each point in time t, the best current view is determined as a kind of an inverse image of the interaction history performed so far, i.e., of the submitted queries q 1 , q 2 , . . . , q t under the a priori knowledge prior and the prohibition declaration proh together with the returned responses con_quer pxq 1 , q 2 , . . . , q t y, d st , prior , prohq xr 1 , r 2 , . . . , r t y . More formally, for the best current view we have the following: bestcv t t d | d U prior , and con_quer pxq 1 , q 2 , . . . , q t y, d st , prior , prohq con_quer pxq 1 , q 2 , . . . , q t y, d, prior , prohq u con_quer ¡1 rcon_querpxq 1 , q 2 , . . . , q t y, d st , prior , prohqs prior ; bestcv V t d | d U prior , and con_quer pxq 1 , q 2 , . . . y, d st , prior , prohq con_quer pxq 1 , q 2 , . . . y, d, prior , prohq u con_quer ¡1 rcon_querpxq 1 , q 2 , . . . y, d st , prior , prohqs prior .

As a technical means, however, a security mechanism might only maintain a simulated current view simcv still invariantly containing a harmless data source, which is employed for checking tentative updates of the attacker's uncertainty for violations of the security invariant. For studying abstract information systems refraining from representing syntax at all, we will use such a simulated current view directly as a kind of log le to keep the essence of the interaction history. Though we are literally speaking about technical means having machineexecutable programs in mind, we deal with abstract information systems as purely mathematical objects and, accordingly, do not actually care about computability. Nevertheless, by abuse of language, we will denote purely mathematical methods for controlled interactions as algorithms, since we have come up with even eciently computable procedures for suitable renements based on appropriate syntactic representations of the mathematical items.

Controlled Query Evaluation by Refusing

For the approach to alterations of a harmful query evaluation by refusing, the existence of an alternative harmless data source will explicitly be monitored by inspecting the assertion for all p proh: simcv p as part of the security invariant enforced for each response to a submitted query. In fact, if a (previously unknown) correct response is returned to the attacker, then the invariance of the assertion after updating simcv accordingly has been conrmed explicitly by a tentative update before.

However, to additionally enforce the indistinguishability property to avoid meta-inferences from the fact of observing a refusal, we have to strengthen the invariant such that it becomes independent of the actual results of the query evaluations. In fact, if a (previously unknown) correct response is returned and the simulated current view simcv has actually been updated accordingly, then not only the tentative update with that response but also with its complement has been inspected for harmlessness explicitly before. Consequently, if at least one alternative has been found to be harmful, the resulting refusal might be caused by the correct response or its complement, such that the attacker cannot nd out which alternative has actually occurred. For convenience, here refusing is signied be returning the universe U , which provides no new information, and, accordingly, no update of the simulated current view simcv is necessary.

As a special case, the correct response might already be known from the a priori knowledge together with the responses to previously inspected queries, as summarized in the value of the simulated current view simcv . To avoid an unnecessary refusal, this case is dealt with separately, by just conrming the correct query evaluation and, consequently, leaving simcv unchanged.

Theorem 1 (inference-proofness by refusing). The stepwise controlled query evaluation function with alterations by refusing for a known prohibition declaration, as computed by Algorithm 1, is inference-proof (and strongly inference-proof under the substitution of proh by t prohu). Theorem 2 (refusing provides best current view directly). Algorithm 1 executed for inputs xq 1 , q 2 , . . . y, d st , prior and proh satisfying the preconditions d st prior and prior p for all p proh for inference-proofness provides the best current view bestcv V by the xpoint simcv V of the simulated current view simcv , i.e., we have bestcv V simcv V .

Proof. In the proof of Theorem 1 we show that bestcv V simcv V . Conversely, assume d prior but d simcv V . Then executing the Algorithm 1 for d st and d, respectively, yields the same value for simcv at time 0 according to step 2 but dierent values for some later point in time. Consider the point in time min ¡ 0 such that for the rst time the executions dier for the value simcv . Accordingly, at time min for at least one of the data sources there was no refusing and, by the independence of the guarding expression in step 10, for both of them there was no refusing. Moreover, by the minimality of min, the query evaluations have been dierent, i.e., quer pquery min , d st q quer pquery min , dq, such that the executions can be distinguished. Hence d bestcv V .

Controlled Query Evaluation by Lying

For alterations by lying, the existence of an alternative harmless data source has to be ensured regarding a strengthen version of harmlessness that requires nonelementship in the union over the prohibition declaration. This version avoids the hopeless situation arising from lies on both that union and all its contributing prohibitions. The existence of such a data source will only partly explicitly be monitored, aiming to make the assertion simcv proh part of the security invariant. In fact, if a correct response is returned to the attacker, then the invariance of the assertion after updating simcv accordingly has been checked explicitly by a tentative update before. Otherwise, if a lied response is returned to the attacker, then no explicit additional inspection is necessary. Moreover, the indistinguishability property is also already implicitly be enforced, since a data source that satises each of the responses generated for the actual data sourcewhether correct or lied turns out to generate the same reactions.

Theorem 3 (strong inference-proofness by lying). The stepwise controlled query evaluation function with alterations by lying, as computed by Algorithm 2, is strongly inference-proof.

Proof. Structurally as for refusing, by an inductive argument that the correct response and the lied response are not both harmful for a single prohibition. Algorithm 2: Stepwise controlled query evaluation with alterations by lying for a known prohibition declaration

Controlled Query Evaluation by Combination

For alterations by a combination of refusing and lying, the existence of an alternative harmless data source will explicitly be monitored by inspecting the assertion for all p proh: simcv p as the security invariant. In fact, rst the correct response is explicitly inspected for harmlessness by a tentative update of simcv , and only in case of a failure, subsequently the lied response is also explicitly inspected for harmlessness. If both inspections fails, i.e., both the correct response and the lied response are harmful, then refusing is due. No further means are necessary to achieve the indistinguishability property as well.

Theorem 4 (inference-proofness by combination). The stepwise controlled query evaluation function with alterations by a combination of refusing and lying, as computed by Algorithm 3, is inference-proof (and strongly inference-proof under the substitution of proh by t prohu).

Proof. Similar as for the proof of Theorem 1, following its overall structure. Algorithm 3: Stepwise controlled query evaluation with alterations by a combination of refusing and lying for a known prohibition declaration

Controlled View Generation

So far, we have studied stepwise controlled query evaluation functions for abstract data sources as epistemic states, employing refusing or lying or the combination of refusing and lying, respectively, as alterations of a harmful query evaluation. These functions are proven to be inference-proof for any sequence of closed-query evaluation with response preparation. Each proof has been based on investigating the properties of the sequence of the simulated current views maintained by the pertinent algorithm to keep track of the interaction history and to enforce a suitable security invariant, together with the ctitious xpoint of that sequence. Essentially, this xpoint is the intersection of the (possibly) altered query responses.

We further exploit the three fundamental approaches for such an algorithm to deal with the interaction of view generation. A best view is abstractly dened as the intersection of the query evaluations of all queries in the considered query set.

Then, roughly outlined, we can form a queue of all such queries, or a suitably exhaustive part of it, submit it to the pertinent algorithm, and will (at least conceptually) obtain the xpoint as a (possibly) altered inference-proof view.

In an interaction of controlled view generation, that xpoint can be returned to the communication partner suspected to be only semi-honest and attacking the dedicated prohibition declaration.

Theorem 5 (inference-proofness by refusing, lying and the combination). The controlled view generation functions with alterations by refusing or lying or the combination of refusing and lying, respectively, for a known prohibition declaration, as computed by Algorithm 4, are weakly or strongly or weakly inference-proof, respectively.

Proof. The claim straightforwardly follows from the inference-proofness of the imported algorithms.

Some Comparisons

For refusing, we have d st simcv and simcv bestcv . Basically, this intuitively means that the literal claims of returned controlled responses are a correct and complete disjunctive weakening of the best view. In contrast, for lying and the combination, whenever a lied response has actually occurred, we have d st simcv and, consequently, simcv bestcv , in particular saying that literal claims do not directly reect the actual situation. The following theorem shows that this dierence disappears under the substitution of proh by t prohu, since then the occurrence of a refusal corresponds to a potential lie.

Theorem 6 (best current views for aggregated policy declaration). Under the substitution of proh by t prohu, the inverse functions of the controlled view generation functions with alterations by refusing or lying or the combination of refusing and lying, respectively, as computed by Algorithm 4, yield the same best current views.

Proof. The full proof, given in the appendix, shows that for the single aggregated prohibition in t prohu, the eect of the instance-independent check for harmfulness by refusing corresponds to the eect of instance-independently always returning a harmless response by lying. [START_REF] Biskup | Inference-proof data ltering for a probabilistic setting[END_REF] Conclusions

Enforcing inference-proofness as a sophisticated version of condentiality relies on crucial assumptions about the a priori knowledge of the specic attacker and further postulations about the overall attack scenario. Furthermore, the notion of a defender or an attacker, respectively, refers to both human individuals and the computing agents under their control. Accordingly, for coming up with formally provable assertions about condentiality the precise specication of the object to be protected by a security mechanism on the defender side as well as a precise specication of the capabilities on the attacker side are mandatory.

Our main contributions are complying with these requirements. On the defender side the epistemic state of the information system agent is identied as the basic protection object, independently of the actual syntactic representation and of any additional knowledge held by the human information owner. On the attacker side, our characterization of the attacker as a rational reasoner about message observations, a priori knowledge, the semantics of the agreed interactions and the functionality of the security mechanism refers to both the client agent and the human communication partner. Accordingly, the defender side is restricted by the possibilities of ecient algorithms, whereas the attacker side might employ unlimited resources. However, as far as the attacker relies on the computing resources of the client agent, refusing and lying essentially dier in determining the best current view: while for refusing the best current view is directly delivered by the returned accumulated information represented by the simulated current view, for lying the best current view has to be generated by a sophisticated function inversion procedure.

We have focused on conceptual and computational foundations rather than on specic applications. Regarding usability, our foundational results suggest that in each concrete practical situation we might be forced to admit relaxations and approximations. Regarding computational complexity, view generation as an o-line procedure might be preferred to closed-query evaluations as a dynamic and often time-constrained protocol. Moreover, in practice we are faced with structured epistemic states which allow more sophisticated interactions, e.g., open (SQL-like) queries and update transactions for relational databases.

Interactions might also refer to non-monotonic operations regarding a structured epistemic state seen as belief , e.g., a revision under suitable postulates.

So far, these and further issues have already been preliminarily studied for specic frameworks, as discussed in [START_REF] Biskup | Selected results and related issues of condentiality-preserving controlled interaction execution[END_REF]. It would be worthwhile to unify and further elaborate all these studies as an enhancement and extension of the present work.

This xpoint has the following properties:

1. simcv V IntpQq, according to Denition 1. 2. d st simcv V , by the construction during the execution of Algorithm 1, since for each time 0, 1, 2, . . . one of the following alternatives apply: d st prior in step 2; d st correct in step 8 or 12 by assertion (3); d st U in step 14. 3. simcv V p for all p proh, based on the compactness of the query set Q according to Denition 1, as veried below.

Let p proh. Assume indirectly that simcv V p. Then, by the compactness of the query set Q, there would exist a nite set F of values in the sequence (7) having a minimal element simcv F (with maximum index of time) such that simcv F F p. Let then min be the rst time such that simcv min p. By the precondition, min ¡ 0. Then, depending on the evaluation of the guarding expressions in step 7 and step 10, respectively, either simcv min simcv min¡1 correct min according to step 12 in the inner if-branch or simcv min simcv min ¡1 according to step 14 in the inner else-branch or simcv min simcv min ¡1 according to step 8 in the outer if-branch. However, the rst case contradicts the value of the inner guarding expression and the second case and third case contradict the denition of min. At time 0, for all of the three approaches we have simcv 0 bestcv 0 . At time ¡ 0, assume inductively that simcv time¡1 for refusing equals bestcv time¡1 for lying and the combination, respectively.

Case 1 : Refusing returns the correct response quer pquery time , d st q. Case 1.1 : simcv time¡1 quer pquery time , d st q, i.e., refusing conrms the correct response. This response is harmless, for otherwise simcv time¡1 would already be harmful, contradicting the security invariant. Then, for refusing, simcv time simcv time¡1 simcv time¡1 quer pquery time , d st q .

Case 1.2 : Otherwise, we have for all p proh: simcv query p and simcv pU zqueryq p and, again, for refusing, simcv time simcv time¡1 quer pquery time , d st q .

(10)

In both subcases, regarding lying, the correct response quer pquery time , d st q is returned for d st , as exactly for all d I quer pquery time , d st q, for each of which we quer pquery time , d I q quer pquery time , d st q by (4). The same reasoning applies for the combination. Accordingly, we have for both lying and the combination bestcv time bestcv time¡1 quer pquery time , d st q ,

together with ( 9), [START_REF] Halpern | Secrecy in multiagent systems[END_REF] and the induction assumption implying the claim.

Case 2 : Refusing returns U to signify a refusal and, thus, for refusing, simcv time simcv time¡1 U simcv time¡1 .

Then, according to the instance-independent guarding expression for refusing, there exists p I t prohu such that simcv time¡1 query time p I or simcv time¡1 pU zquery time q p I . This implies that we have either simcv time¡1 query time proh or simcv time¡1 pU zquery time q proh but not both.

For assume otherwise that both inclusions hold, then simcv time¡1 simcv time¡1 U simcv time¡1 pquery time pU zquery time qq psimcv time¡1 query time q psimcv time¡1 pU zquery time qq proh, contradicting that the security invariant for refusing has been enforced at time time ¡ 1.

Now, regarding lying, the strict alternative given above means that for all d I U the uniquely determined harmless version in the set tquery time , U zquery time u is returned, independently of whether it is correct or lied. The same observation applies for the combination. Accordingly, for both approaches we have bestcv time bestcv time¡1 U bestcv time¡1 , [START_REF] Sicherman | Answering queries without revealing secrets[END_REF] together with [START_REF] Schneider | Enforceable security policies[END_REF] and the induction assumption implying the claim.

Fig. 1 .

 1 Fig. 1. The framework of a defending information owner with his information system agent and an attacking communication partner with his client agent

  Proof. A full proof is given in the appendix. Here we only sketch the overall structure of the proof. An execution of Algorithm 1 determines a sequence of values for the simulated current view simcv with a xpoint, such thatprior simcv 0 simcv 1 simcv 2 . . . with simcv V £ t0,1,2,... simcv t .By the construction and by assertion (3), d st simcv V . By an inductive argument based on the compactness, and because of the explicit check of the security invariant in step 10, we have simcv V p for all p proh. Thus, for each p proh there exists a data source d p al simcv V zp, which satises the precondition and is harmless by the construction. Moreover, d p al is also indistinguishable (of the stored data source d st ), as is even any data source d simcv V . Basically, this claim follows from the inductive procedure to decide whether the value of simcv should be changed, based on the instance independent security invariant enforced by step 10.

  q2, . . . y queue of queries, submitted by attacker dst stored abstract data source prior a priori knowledge as query proh prohibition declaration as nite set of queries Output: xr1, r2, . . . y list of (possibly) altered responses, returned to attacker 1 time Ð 0 //initialize counter for discrete points in time;

  source prior a priori knowledge as query proh prohibition declaration as nite set of queries Output: view returned to attacker as controlled view 1 Import: Algorithm i for either i 1: refusing or i 2: lying or i 3: combination 2 form exhaustive queue xq1, q2, . . . y of closed queries; 3 apply Algorithm i to xq1, q2, . . . y and the inputs, using local variable simcv ; 4 on exit from the repeat-loop (actually or ctitiously) do 5 view Ð simcv ; 6 return view as outputAlgorithm 4: Controlled view generation with alterations by refusing, lying or the combination of refusing and lying based on Algorithm 1, Algorithm 2 or Algorithm 3, respectively, for a known prohibition declaration

  So, by simcv V p there exists a data source d p al simcv V zp. We claim that d p al is the alternative data source required to exist: 4. d p al satises the a priori knowledge, since d p al simcv V zp simcv V simcv 0 prior . 5. d p al is harmless (w.r.t. the prohibition p), i.e., d p al p, by the construction. 6. d p al is indistinguishable (of the stored data source d st ), since below we can show by induction that for each time 1, 2, . . . the repeat-loop of Algorithm 1 takes the same actions, in fact not only for d p al but even for all data sources d simcv V .

  . . , of all queries in Q, we can characterize a data source d as being in the intersection of its query evaluations. In this sense, the best view of d from outside is just this intersection, which always includes d itself but might also contain many further indistinguishable data sources. If the best view of d is a singleton, then it represents complete knowledge of d.

Denition 3 (abstract best view generation). Let Q be a query set for an universe U . Then the view generation function is dened by view : U ÝÑ IntpQq with view pdq £ qQ quer pq, dq .

  con_quer pxq 1 , q 2 , . . . y, d st , prior , prohq con_quer pxq 1 , q 2 , . . . y, d p al , prior , prohq; harmlessness of d al (w.r.t. the prohibition p): d p al p.3. The function is strongly inference-proof i it is inference-proof for proh sub-

	stituted by t	prohu.

there exists an (alternative) data source d p al prior such that indistinguishability of d st and d p al (w.r.t. the prohibition p):

  proh: simcv query p and simcv pUzqueryq p

		Input:	xq1, q2, . . . y queue of closed queries, submitted by attacker
			dst	stored abstract data source
			prior	a priori knowledge as query
		proh Output: xr1, r2, . . . y list of (possibly) altered responses, returned to attacker prohibition declaration as nite set of queries
	1 time Ð 0 2 simcv Ð prior	//initialize counter for discrete points in time; //initialize simulated current view;
	3 repeat 4 time Ð time 1; 5 query Ð receive next query qtime from input queue; 6 correct Ð quer pquery, dstq //determine correct query evaluation;
	7	if simcv correct then
	8	return correct to output list
			//conrm correct response; leave simcv unchanged
	9	else
	10	if for all p then
	11 12		return correct to output list simcv Ð simcv correct	//respond correctly;
			//update simulated current view accordingly
	13	else
	14		return U to output list
			//signify refusing; leave simcv unchanged
	15	end
	16	end
	17 until input queue has externally been closed, if ever ;
	Algorithm 1: Stepwise controlled query evaluation with alterations by
	refusing for a known prohibition declaration

Acknowledgements: I would like to sincerely thank Piero Bonatti very much for fruitful cooperation on the works underlying this article.

Appendix 1: Proof of Theorem 1

Consider the execution of Algorithm 1 for some inputs xq 1 , q 2 , . . . y, d st , prior and proh satisfying the preconditions d st prior and prior p for all p proh. Let xsimcv 0 , simcv 1 , simcv 2 , . . . y be the sequence of values obtained by the simulated current view simcv , with simcv 0 prior according to step 2, and with simcv time being the updated value at the end of the time-th iteration of the repeat-loop for time ¡ 0, according to either step 12, 14 or 8, respectively. Then we have simcv 0 simcv 1 simcv 2 . . . .

Dene the xpoint of this chain as So, consider any d simcv V and suppose inductively that the value simcv time¡1 of the simulated current view simcv is the same for the stored data source d st and the considered data source d.

Case 1 : simcv time¡1 quer pquery time , d st q.

Then, the outer guarding expression at step 7 is true for d st and, thus, the response quer pquery time , d st q is returned in step 8. Then we have d simcv V simcv time¡1 quer pq time , d st q and thus, by assertion (4), quer pq time , dq quer pq time , d st q. This equality implies that also simcv time¡1 quer pquery time , dq and, accordingly, that the outer guarding expression at step 7 is also true for d such that quer pquery time , dq is returned in step 8 as the same response.

Case 2 : simcv time¡1 quer pquery time , d st q. Case 2.1 : For all p I proh: simcv time¡1 query time p I and simcv time¡1 pU zquery time q p I . Then quer pquery time , d st q is returned in step 11 and simcv is updated accordingly in step 12, and we have d simcv V simcv time simcv time¡1 quer pq time , d st q quer pq time , d st q and thus, by assertion (4), quer pq time , dq quer pq time , d st q. This equality implies that also simcv time¡1 quer pquery time , dq and, accordingly, that the outer guarding expression at step 7 is also false for d and the inner guarding expression is checked in line 10. Being independent of the query evaluation, this expression is also true for d by the assumption of Case 2.1, such that quer pquery time , dq is returned in step 11 as the same response and the same update of simcv occurs in step 12.

Case 2.2 : For some p I proh: simcv time¡1 query time p I or simcv time¡1 pU zquery time q p I .

Then the universe U is returned in step 14, signifying a refusal for d st . Regarding d, since both d st simcv time¡1 and d simcv time¡1 , we have simcv time¡1 quer pquery time , dq by the assumption of Case 2 and assertion [START_REF] Biskup | Optimality and complexity of inference-proof data ltering and CQE[END_REF]. So, the outer guarding expression in step 7 is also false for d and the inner guarding expression is checked in line 10. Being independent of the query evaluation, this expression is also false for d by the assumption of Case 2.2, such that the universe U is returned in step 14, signifying a refusal as the same response.

Appendix 2: Proof of Theorem 6

By Theorem 2, we already know that for refusing with suitable inputs the simulated current view simcv V equals the best current view bestcv V . Thus it suces to show the following claim by induction:

For a single aggregated prohibition proh, the simulated current view simcv time of refusing equals the best current views bestcv time of lying and the combination, respectively.