Dynamic Searchable Symmetric Encryption (DSSE) provides efficient techniques for securely searching and updating an encrypted database. However, efficient DSSE schemes leak some sensitive information to the server. Recent works have implemented forward and backward privacy as security properties to reduce the amount of information leaked during update operations. Many attacks have shown that leakage from search operations can be abused to compromise the privacy of client queries. However, the attack literature has not rigorously investigated techniques to abuse update leakage. In this work, we investigate update leakage under DSSE schemes with forward and backward privacy from the perspective of a passive adversary. We propose two attacks based on a maximum likelihood estimation approach, the UFID Attack and the UF Attack, which target forward-private DSSE schemes with no backward privacy and Level 2 backward privacy, respectively. These are the first attacks to show that it is possible to leverage the frequency and contents of updates to recover client queries. We propose a variant of each attack which allows the update leakage to be combined with search pattern leakage to achieve higher accuracy. We evaluate our attacks against a real-world dataset and show that using update leakage can improve the accuracy of attacks against DSSE schemes, especially those without backward privacy. / Master of Science / Remote data storage is a ubiquitous application made possible by the prevalence of cloud computing. Dynamic Symmetric Searchable Encryption (DSSE) is a privacy-preserving technique that allows a client to search and update a remote encrypted database while greatly restricting the information the server can learn about the client's data and queries. However, all efficient DSSE schemes have some information leakage that can allow an adversarial server to infringe upon the privacy of clients. Many prior works have studied the dangers of leakage caused by the search operation, but have neglected the leakage from update operations. As such, researchers have been unsure about whether update leakage poses a threat to user privacy. To address this research gap, we propose two new attacks which exploit leakage from DSSE update operations. Our attacks are aimed at learning what keywords a client is searching and updating, even in DSSE schemes with forward and backward privacy, two security properties implemented by the strongest DSSE schemes. Our UFID Attack compromises forward-private schemes while our UF Attack targets schemes with both forward privacy and Level 2 backward privacy. We evaluate our attacks on a real-world dataset and show that they efficiently compromise client query privacy under realistic conditions.

We study the inference of models of the analysis by reduction that forms an important tool for parsing natural language sentences. We prove that the inference of such models from positive and negative samples is NP-hard when requiring a small model. On the other hand, if only positive samples are considered, the problem is effectively solvable. We propose a new model of the analysis by reduction (the so-called single k-reversible restarting automaton) and propose a method for inferring it from positive samples of analyses by reduction. The power of the model lies between growing context-sensitive languages and context-sensitive languages. Benchmarks using targets based on grammars have several drawbacks. Therefore we propose a benchmark working with targets based on random automata, that can be used to evaluate inference algorithms. This benchmark is then used to evaluate our inference method. 1

A large software system is built by composing multiple programs, possibly developed independently. The component programs communicate by sharing data. Data sharing involves creation of instances of the shared data by one program, called the producer, and its interpretation by another program, called the consumer. Valid instances of shared data and their correct interpretation is usually specified by a protocol or a standard that governs the communication. If a consumer misinterprets or does not handle some instances of data produced by a producer, it is called as a data compatibility bug. Such bugs manifest as various forms of runtime errors that are difficult to find and fix. In this work, we define various compatibility relations, between both producer-consumer programs and version-related programs, that characterize various subtle requirements for correct sharing of data. We design and implement a static analysis to infer types and guards over elements of shared data and the results are used for automatic compatibility checking. As case studies, we consider two widely used shared data-the TIFF structure, used to store TIFF directory attributes in memory, and IEEE 802. 11 MAC frame header which forms the layer 2 header in Wireless LAN communication. We analyze and check compatibility of 6 pairs of producer-consumer programs drawn from the transmit-receive code of Linux WLAN drivers of 3 different vendors. In the setting of version-related programs, we analyze a total of 48 library and utility routines of 2 pairs of TIFF image library (libtiff) versions. We successfully identify 5 known bugs and 1 new bug. For two of known bugs, bug fixes are available and we verify that they resolve the compatibility issues.