<jupyter_start><jupyter_text>Database Reconstruction Attacks  Privacy[<NAME> (2003)](https://dl.acm.org/doi/abs/10.1145/773153.773173) roughly states that if too many queries on a database are answered too accurately, almost the entire database can be reconstructed from the answers to the queries. Before this fact was properly understood, statistical releases from databases were typically limited in ad-hoc ways. For example, an interactive querying system (in which analysts propose their own queries) may not allow queries that clearly single out individual elements of the data set. Similarly, in a one-shot release (e.g. the U.S. Census Bureau releasing statistical tables) the releasing party may decide not to release statistics on groups with fewer than some fixed number of elements. Releasing statistics in a differentially private manner has been posed as a principled way to ensure the privacy of individuals included in a database and prevent database reconstruction. Notably, the U.S. Census is moving to use differentially private algorithms to perform statistical releases for the 2020 Census, for fear that their old methods of privatization (a.k.a. statistical disclosure limitation) are not sufficient to prevent database reconstruction. See [<NAME> (2018)](https://dl.acm.org/ft_gateway.cfm?id=3295691&ftid=2020934&dwn=1) for more information. In this notebook we will focus on the one-shot release model and simulate the process of a data owner releasing aggregate statistics from a sensitive database, both with and without differential privacy. We will then attempt to reconstruct the original database from each set of releases.  Statistical Release SetupThe underlying sensitive data from which we are releasing is a partly-synthetic version of the PUMS data that are used in many other notebooks. The data are $(500 \times 6)$ with the columns taking values as follows:    - educ: {1, 2}    - race: {1, 2}    - agebinned: {'[20, 25)', '[25, 30)', ..., '[45, 50)'}    - sex: {0, 1}    - married: {0, 1}    - income: [0, 420,500]We will assume that `income` is the only sensitive variable in the database, and so the data owner is concerned only with whether or not an attacker can reconstruct the `income` variable.We will first calculate a number of statistics -- `mean`, `median`, `min`, and `max` by subgroup, where a subgroup is defined as a set of database elements that are equivalent with respect to some subset of variables. For example, valid subgroups include the set of all elements with `educ == 2`, and the set of all elements with `educ == 1 && race == 2 && married == 0`. The `income` variable is never included in these subgroup definitions, as it is the variable we are trying to reconstruct. Throughout the notebook, we will examine various cases in which the data owner releases different subsets of these statistics.<jupyter_code>import reconstruction_module as rec

# load data 
orig_data, data = rec.load_data()
non_income_data = data.drop('income', axis = 1)

# get plausible variable combinations and subset of length 5 plausible combinations 
plausible_variable_combinations = rec.get_plausible_variable_combinations(non_income_data)
plausible_variable_combinations_names = ['__'.join(combination) for combination in plausible_variable_combinations]

five_way_interactions = [combination for combination in plausible_variable_combinations if len(combination) == 5]
five_way_interactions_names = ['__'.join(combination) for combination in five_way_interactions]

# get dictionaries of private and non-private releases (up to 5-way interactions)
count_dict, priv_count_dict, mean_income_dict, priv_mean_income_dict, median_income_dict, priv_median_income_dict, min_income_dict, priv_min_income_dict, max_income_dict, priv_max_income_dict = rec.create_dicts(data, non_income_data, plausible_variable_combinations)

# get string representations of each element associated with each tuple representing the 5-way interactions
elem_dict, priv_elem_dict = rec.create_elem_dicts(count_dict, priv_count_dict, five_way_interactions, five_way_interactions_names)<jupyter_output><empty_output><jupyter_text>Statistical Release and Reconstruction AttackWe are nearly ready to consider an actual set of statistical releases and how this can enable a reconstruction attack, but it will be useful to first consider some details of our attacker.The attacker's goal is to reconstruct the `income` column as closely as possible (by some definition of closeness), using a combination of the statistical releases and pre-existing knowledge of the database. We will assume for now that the attacker has no pre-existing knowledge, and thus bases their reconstruction only on the statistical releases. Following [<NAME> (2018)](https://dl.acm.org/doi/pdf/10.1145/3291276.3295691), we attempt to construct a database that is consistent with the releases using a SAT/SMT solver. We will be using [Z3](https://github.com/Z3Prover/z3), but other SAT/SMT solvers could serve the same purpose.Z3 takes a boolean formula with associated variables and returns whether or not the formula is satisfiable; that is, whether or not there exists a set of variable values that makes the boolean formula `TRUE`. For example, let $A,B$ be boolean variables. The formula $A \land B$ is satisfiable because it is true if $A = B = TRUE$. The formula $A \land B \land \neg B$ is not satisfiable.This idea can be applied to finding a database that satisfies a set of statistical releases. Say we know that a subgroup has 3 elements, $\{i_1, i_2, i_3\}$ with median income $50,000$, mean income $60,000$, and min income $0$. Note that, because elements within a subgroup are equivalent with respect to the subset of variables that dedine the subset, we are free to index however we wish within the subset. We choose to enforce the element values to be montonically non-decreasing in the index. So, we can represent each statistical release as a statement we'll call an `application`: $$ (i_1 \leq i_2 \leq i_3) \land (i_1 = 0) \land (i_2 = 50,000) \land \left( (i_1 + i_2 + i_3)/3 = 60,000 \right). $$In this case, we get satisfying values of $i_1, i_2$ for free and can find $i_3 = 130,000$ by plugging in $i_1, i_2$ to the last equation. So $\{0, 50,000, 130,000\}$ is a database that is consistent with our statistical release.   Note that, as long as the set of statistical releases is internally consistent (results do not contradict one another), Z3 should be able to find at least one satisfying assignment.<jupyter_code>import z3

# single satisfying assignment
i_1, i_2, i_3 = z3.Ints('i_1 i_2 i_3')
z3.solve(i_1 <= i_2, i_2 <= i_3, i_1 == 0, i_2 == 50_000, z3.Sum(i_1, i_2, i_3) == 180_000)<jupyter_output>[i_3 = 130000, i_2 = 50000, i_1 = 0]<jupyter_text>In the case above there is only one satisfying assignment, and so the result that Z3 provided is the only database consistent with our statistical releases. Let's now imagine the same case, but without a released median.<jupyter_code># many satisfying assignments
i_1, i_2, i_3 = z3.Ints('i_1 i_2 i_3')

z3.solve(i_1 <= i_2, i_2 <= i_3, i_1 == 0, z3.Sum(i_1, i_2, i_3) == 180_000)
z3.solve(i_1 <= i_2, i_2 <= i_3, i_1 == 0, z3.Sum(i_1, i_2, i_3) == 180_000)
z3.solve(i_1 <= i_2, i_2 <= i_3, i_1 == 0, z3.Sum(i_1, i_2, i_3) == 180_000)<jupyter_output>[i_3 = 135102, i_2 = 44898, i_1 = 0]
[i_3 = 131018, i_2 = 48982, i_1 = 0]
[i_3 = 136039, i_2 = 43961, i_1 = 0]<jupyter_text>Again we get a satisfying assignment, but this time the assignment is not unique. That is, there are multiple databases consistent with our statistical releases (only one of which is the true underlying data). As a result, the attacker has not learned the entire underlying database with certainty. The more satisfying assignments exist, and the more variability between these assignments, the less the attacker is expected to learn from reconstructing the data.Now that we have a taste for Z3, we can move to the final stage of setting up the attack, encoding the statistical releases as applications. We treat each individual's income as its own variable and construct applications by asserting that the values of these variables must be consistent with statistical releases, much like we did above (but on a larger scale). For this example, we will assume that the mean and median of every subgroup is released, regardless of subgroup size.<jupyter_code># set applications
applications, priv_applications = rec.get_applications(five_way_interactions, five_way_interactions_names,
                                                plausible_variable_combinations, plausible_variable_combinations_names,
                                                count_dict, priv_count_dict, 
                                                mean_income_dict, priv_mean_income_dict,
                                                median_income_dict, priv_median_income_dict,
                                                min_income_dict, priv_min_income_dict,
                                                max_income_dict, priv_max_income_dict,
                                                elem_dict, priv_elem_dict, lowest_allowable_count = 1,
                                                use_medians = True, use_mins = False, use_maxes = False)
# remove duplicate applications
applications = list(set(applications))
priv_applications = list(set(priv_applications))<jupyter_output><empty_output><jupyter_text>Attack 1We start with an attack in a very basic scenario. As described above, the data curator releases the mean and median for each subgroup we defined (up to 5-way interactions between our variables). The attacker then uses only this information to attempt to reconstruct the private data.<jupyter_code># initialize solvers
solver_1, solver_list_1 = rec.applications_to_solver(applications)
priv_solver_1, priv_solver_list_1 = rec.applications_to_solver(priv_applications) 

# get results (models)
model_1 = rec.check_solution(solver_1) 
if model_1:
    print('non-private: sat')
else:
    print('non-private: unsat')

# attempt to resconstruct data
recon_data = rec.reconstruct_data(model_1, elem_dict)<jupyter_output>non-private: sat<jupyter_text>As expected, Z3 produces a satisfying assignment based on the non-private statistical releases.We mentioned earlier that there may exist multiple satisfying assignments and that we can consider the number and variability of these assignments to examine the extent to which an attacker can learn from a satisfying assignment. We will not do that here, instead opting to just compare the assignment to the true underlying data (a luxury the attacker will not have).<jupyter_code># compare original and reconstructed data
orig_data, recon_data, exact, within_2k, within_5k = rec.compare_data(orig_data, recon_data)

print('Of 500 total incomes:')
print('    {0} incomes reconstructed exactly'.format(exact))
print('    {0} incomes resconstructed within $2,000'.format(within_2k))
print('    {0} incomes resconstructed within $5,000'.format(within_5k))<jupyter_output>Of 500 total incomes:
    59 incomes reconstructed exactly
    161 incomes resconstructed within $2,000
    209 incomes resconstructed within $5,000<jupyter_text>Attack 2In the example above, we did not make any effort at statistical disclosure limitation. We can try the attack again, but in this case imagine that no information (counts, means, or medians) are released for subgroups of size $< 10$. As before, we assume that the attacker does not have access to any information about the data other than what was released by the data curator.<jupyter_code># set applications
applications_2, priv_applications_2 = rec.get_applications(five_way_interactions, five_way_interactions_names,
                                                plausible_variable_combinations, plausible_variable_combinations_names,
                                                count_dict, priv_count_dict, 
                                                mean_income_dict, priv_mean_income_dict,
                                                median_income_dict, priv_median_income_dict,
                                                min_income_dict, priv_min_income_dict,
                                                max_income_dict, priv_max_income_dict,
                                                elem_dict, priv_elem_dict, lowest_allowable_count = 10,
                                                use_medians = True, use_mins = False, use_maxes = False)
# remove duplicate applications
applications_2 = list(set(applications_2))
priv_applications_2 = list(set(priv_applications_2))

# initialize solvers
solver_2, solver_list_2 = rec.applications_to_solver(applications_2)
priv_solver_2, priv_solver_list_2 = rec.applications_to_solver(priv_applications_2) 

# get results (models)
model_2 = rec.check_solution(solver_2) 
if model_2:
    print('non-private: sat')
else:
    print('non-private: unsat')

# attempt to resconstruct data
recon_data_2 = rec.reconstruct_data(model_2, elem_dict)

# compare original and reconstructed data
orig_data, recon_data_2, exact_2, within_2k_2, within_5k_2 = rec.compare_data(orig_data, recon_data_2)

print('Of 500 total incomes:')
print('    {0} incomes reconstructed exactly'.format(exact_2))
print('    {0} incomes resconstructed within $2,000'.format(within_2k_2))
print('    {0} incomes resconstructed within $5,000'.format(within_5k_2))<jupyter_output>non-private: sat
Of 500 total incomes:
    47 incomes reconstructed exactly
    80 incomes resconstructed within $2,000
    116 incomes resconstructed within $5,000<jupyter_text>After suppressing all statistics from subgroups of size $< 10$, the attacker is able to reconstruct the data with some success (though less than in the setting with no suppression). Attack 3To this point, we have considered the setting in which the attacker knows only the values of the aggregate statistics released. However, it is possible that attackers have access to information not contained in this set of statistical releases. For example, perhaps they have access to statistical releases from another source, or they happen to already know exact values for some elements in the database.Imagine that the attacker has access to the following information outside of the statistical releases:- There is at least one person in the data with `educ == 2`, `race == 2`, `agebinned == [45, 50)`, `sex == 0`, and `married == 1` with an income of $95,000.- There is only one person in the data with `educ == 2`, `race == 2`, `agebinned == [45, 50)`, `sex == 1`, and `married == 1` and they have an income of $31,000.<jupyter_code># set applications
applications_3, priv_applications_3 = rec.get_applications(five_way_interactions, five_way_interactions_names,
                                                plausible_variable_combinations, plausible_variable_combinations_names,
                                                count_dict, priv_count_dict, 
                                                mean_income_dict, priv_mean_income_dict,
                                                median_income_dict, priv_median_income_dict,
                                                min_income_dict, priv_min_income_dict,
                                                max_income_dict, priv_max_income_dict,
                                                elem_dict, priv_elem_dict, lowest_allowable_count = 10,
                                                use_medians = True, use_mins = False, use_maxes = False)
# remove duplicate applications
applications_3 = list(set(applications_3))
priv_applications_3 = list(set(priv_applications_3))

# initialize solvers
solver_3, solver_list_3 = rec.applications_to_solver(applications_3)
priv_solver_3, priv_solver_list_3 = rec.applications_to_solver(priv_applications_3) 

# add applications encoding existing attacker knowledge
group_1_def = 'educ_2__race_2__agebinned_45,50__sex_0__married_1'
group_1_elems = [z3.Int('{0}_{1}'.format(group_1_def, i)) for i in range(count_dict[group_1_def])]
solver_3.add(z3.Or([elem == 95_000 for elem in group_1_elems]))

group_2_def = 'educ_2__race_2__agebinned_45,50__sex_1__married_1'
solver_3.add(z3.Int( '{0}_{1}'.format(group_2_def, 0)) == 31_000)

# get results (models)
model_3 = rec.check_solution(solver_3) 
if model_3:
    print('non-private: sat')
else:
    print('non-private: unsat')

# attempt to resconstruct data
recon_data_3 = rec.reconstruct_data(model_3, elem_dict)

# compare original and reconstructed data
orig_data, recon_data_3, exact_3, within_2k_3, within_5k_3 = rec.compare_data(orig_data, recon_data_3)

print('Of 500 total incomes:')
print('    {0} incomes reconstructed exactly'.format(exact_3))
print('    {0} incomes resconstructed within $2,000'.format(within_2k_3))
print('    {0} incomes resconstructed within $5,000'.format(within_5k_3))<jupyter_output>non-private: sat
Of 500 total incomes:
    59 incomes reconstructed exactly
    91 incomes resconstructed within $2,000
    130 incomes resconstructed within $5,000<jupyter_text>This looks much like the performance from Attack 2, but notice that what might appear to be two extra pieces of information can lead to reconstruction of more than two additional data elements.In each of the three scenarios above, we also set up (but did not test) reconstruction attempts with differentially private statistical releases. Let's now see what happens if we try to reconstruct the underlying data from the private statistics.<jupyter_code># get results (models)
priv_model_1 = rec.check_solution(priv_solver_1) 
if priv_model_1:
    print('model_1 private: sat')
else:
    print('model_1 private: unsat')

priv_model_2 = rec.check_solution(priv_solver_2) 
if priv_model_2:
    print('model_2 private: sat')
else:
    print('model_2 private: unsat')
    
priv_model_3 = rec.check_solution(priv_solver_3) 
if priv_model_3:
    print('model_3 private: sat')
else:
    print('model_3 private: unsat')<jupyter_output>model_1 private: unsat
model_2 private: unsat
model_3 private: unsat
{'fraction_non_alphanumeric': 0.06860143725815368, 'fraction_numerical': 0.03272526257600884, 'mean_word_length': 3.953723986856517, 'pattern_counts': {'":': 0, '<': 43, '<?xml version=': 0, '>': 33, 'https://': 4, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 48, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '9', 'dir': 'jupyter-structured-clean-dedup', 'id': '80840', 'license': 'MIT', 'n_tokens_mistral': 5376, 'n_tokens_neox': 4853, 'n_words': 1980, 'path': 'attacks/reconstruction/reconstruction.ipynb', 'repo_name': 'huwd/smartnoise-samples', 'size': '18142'}