Query depth in relational databases : ensuring the legality of searches on business records metadata

Intelligence agencies worldwide have access to databases containing daily business records metadata, such as telephony metadata, with the aim of preventing and identifying terrorist activity. In 2013, the US Foreign Intelligence Surveillance Court (FISC) released a number of documents on the use of telephony metadata by the US National Security Agency (NSA). NSA claimed that they did not possess technical expertise on how to correctly conduct searches on the BR metadata. These documents revealed that the NSA was querying a larger set of identifiers than the one permitted in previous FISC orders. This motivates the need for an automated tool with the capability of analyzing the legality of queries on telephony metadata. This analysis would help to prevent the execution of queries which retrieve more identifiers than allowed. The aim of this thesis is to conceive a tool for such purpose, which, differently from the previous work on the subject, will conduct an analysis based only on the query itself and not on the output that the query produces on a specific database. The input queries will be checked against the guidelines specified in a 2013 Obama administration white paper on bulk collection of telephony metadata. To achieve this goal we propose two different notions of depth of a query: the graph-depth approach is a straightforward verification of the above guidelines while the cost-depth approach, although comparable to the previous one, is inspired by the theory of databases with access limitations and solves a more complex, although similar, problem. We will propose a number of algorithms for both approaches and we will implement them as part of the QueryAnalyzer system. Finally, we will compare the performances of the different algorithms.

Le agenzie di sicurezza governativa fanno spesso accesso ai metadati delle chiamate telefoniche, tra cui mittente e destinatario, allo scopo di identificare e prevenire attività terroristiche. Nel 2013, la Corte di Vigilanza sull’Intelligence Estera americana (FISC) ha rilasciato dei documenti riguardanti l’uso dei metadati telefonici da parte dell’ Agenzia di Sicurezza Nazionale americana (NSA). Questi documenti hanno rivelato che l’NSA ha condotto ricerche accedendo ad un numero di identificatori di numeri telefonici maggiore rispetto a quanto in precedenza stabilito dalla FISC. Un documento governativo, redatto dall’amministrazione Obama nel 2013, stabilisce che l’NSA è abilitata a interrogare i metadati telefonici partendo da una “lista nera” di id possedenti la qualifica di “reasonable articulable suspicion” (RAS) e accedendo a id distanti non più di tre hop dagli id RAS, col significato che due id sono distanti una hop quando tra essi è intercorsa una chiamata, due hop se sono connessi solo indirettamente attraverso una terza parte e così via. L’NSA ha risposto alle accuse della FISC dichiarando che “dal punto di vista tecnico, nessuno aveva una completa conoscenza del sistema di interrogazione dei metadati telefonici”. Lavori precedenti sul problema di prevenire l’accesso illegale dell’NSA ai suddetti metadati ha dimostrato che non solo è possibile filtrare il database nascondendo gli id distanti più di tre hop dagli id RAS, ma tale operazione è anche efficiente se si utilizza un database a grafi. Lo scopo della nostra ricerca è di quantificare il massimo numero di hop attraversate dalla query andando ad analizzare la struttura della query e non l’output prodotto dalla sua esecuzione. A questo scopo abbiamo definito uno schema di database relazionale e un sottoinsieme di SQL atti a rappresentare le query di interesse. Abbiamo quindi definito la graph-depth di una query come il massimo numero di hop espanse dalla query. Ad esempio, consideriamo la seguente query (espressa in linguaggio naturale) “Trova Alice, Bob e Carl tali che Alice ha chiamato qualche id RAS che ha chiamato Bob che, a sua volta, ha chiamato Carl”: in generale Alice e Bob non sono id RAS ma sono in diretto contatto con qualche RAS, per cui entrambi sono lontani una hop dagli id RAS. Carl invece, è in contatto con qualche RAS tramite Bob per cui esso dista due hop dalla lista nera. Da questo segue che il massimo numero di hops espanse dalla query è due. Siamo stati in grado di sviluppare un algoritmo che, in tempo polinomiale, calcola la graph-depth di una query, purchè essa sia minima. Il passo successivo della nostra ricerca è stato modificare leggermente il problema per considerare la direzione delle chiamate. Infatti la definizione di hop definita dai documenti legislativi statunitensi è informale e non specifica se il verso delle chiamate influenzi o meno la legalità della query. Per questo abbiamo sviluppato un concetto alternativo di profondità chiamato cost-depth. L’idea è basata intorno alla nozione di accesso, ovvero l’azione di fornire un elenco di id in input al database per estrarre o coloro che hanno ricevuto chiamate da tale elenco o coloro che hanno effettuato chiamate verso tale elenco. Questo concetto permette di distinguere la direzione delle chiamate. La cost-depth di una query è quindi il minimo numero di accessi richiesti per eseguire la query. Consideriamo nuovamente la query sopra che per praticità riscriviamo come “A, B, C tali che A chiama RAS chiama B chiama C”. Per eseguire un accesso occorre avere una lista nota di id, che nel nostro caso sono proprio i RAS. Dai RAS possiamo risalire a chi li ha chiamati ottenendo gli A (primo accesso). Usando gli stessi RAS risaliamo a chi hanno chiamato ottenendo B (secondo accesso). Ora i B sono noti e possiamo risalire a chi hanno chiamato ottenendo C (terzo accesso). Il primo e secondo accesso sono diversi perchè diversa è la direzione in cui andiamo ad estrarre i dati e sono entrambi diversi dal terzo che usa una lista di input diversa. La cost-depth della query è quindi tre. In generale ci sono vari piani di esecuzione possibili per una query. Abbiamo inoltre dimostrato che il problema di trovare il piano minimo è NP-difficile il che ci ha spinto a sviluppare un algoritmo esatto basato sul paradigma branch & bound e un algoritmo approssimato basato sul paradigma greedy. Abbiamo quindi realizzato il sistema Query- Analyzer che consente di calcolare la graph-depth e la cost-depth di una query e abbiamo confrontato le prestazioni dei due algoritmi per il calcolo della cost-depth.