Implement Difference attack #34
Description
For this issue, implement the difference attack described in section 5.2.2 of the Extended Diffix paper (https://aircloak.com/wp-content/uploads/Complete-Diffix.pdf). The criteria is singling out. You can see an example of a singling out attack at https://github.com/gda-score/code/blob/master/attacks/dumbList_SingOut.py.
This attack has two parts.
- The attacker must find a user that can be isolated.
- The attacker must make the set of queries that isolates the user.
To isolate a user, the attacker must find two queries where the counts of distinct users differs by exactly 1. The easiest way to do that is with not equals condition (<>). What we do is find a column that is likely to have many user-unique values. This could be any column where the number of distinct users is say 50% or more than the number of distinct values. The uid column is always such a column, and so is lastname.
You can use the function getTableCharacteristics() to determine which columns apply.
https://gda-score.github.io/gdaScore.m.html#gdaScore.gdaAttack.getTableCharacteristics
After selecting one such column, do an askKnowledge() query to get the contents of that column. Then select values in the column that for which there is only one user. Call these col_iso and val_iso.
For every other column (other than col_iso), we make two queries using ask_attack(). One query looks like this:
select col_other, count(distinct uid)
from table
where col_iso <> val_iso
group by 1
And the other query like this:
select col_other, count(distinct uid)
from table
group by 1
We are looking for the col_other value where the user (the victim) is not in the first query but is in the second. We'll assume that the value where the difference between the second count and the first count is largest will be that value.
Then we make a claim using ask_claim() based on this value.
For each col_other make 20 attack pairs (i.e. use 20 different val_iso values) and 20 corresponding claims.