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). 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 retrieving more identifiers than those allowed by the law. 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 approaches: the graph-depth approach is a straightforward verification of those guidelines while the cost-depth approach, although comparable to the previous one, is inspired by the theory of databases with access limitations. 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 performance of the different algorithms.