Multithreaded programs are known to be difficult to analyze. A key reason is that they typically have an enormous number of execution interleavings, or schedules. Static analysis with respect to all schedules requires over-approximation, resulting in poor precision; dynamic analysis rarely covers more than a tiny fraction of all schedules, so its result may not hold for schedules not covered. To address this challenge, we propose a novel approach called schedule specialization that restricts the schedules of a program to make it easier to analyze. Schedule specialization combines static and dynamic analysis. It first statically analyzes a multithreaded program with respect to a small set of schedules for precision, and then enforces these schedules at runtime for soundness of the static analysis results. To demonstrate that this approach works, we build three systems. The first system is a specialization framework that specializes a program into a simpler program based on a schedule for precision. It allows stock analyses to automatically gain precision with only little modification. The second system is Peregrine, a deterministic multithreading system that collects and enforces schedules on future inputs. Peregrine reuses a small set of schedules on many inputs, ensuring our static analysis results to be sound for a wide range of inputs. It also enforces these schedules efficiently, making schedule specialization suitable for production usage. Although schedule specialization can make static concurrency error detection more precise, some concurrency errors such as races may still slip detection and enter production systems. To mitigate this limitation, we build Loom, a live-workaround system that protects a live multithreaded program from races that slip detection. It allows developers to easily write execution filters to safely and efficiently work around deployed races in live multithreaded programs without restarting them.

As cloud technology matures and trendsetters like Google, Amazon, Microsoft, Apple, and VMware have become the top-tier cloud services players, public cloud services have turned mainstream for individual users. In this work, I propose a set of techniques that can be used as the basis for alleviating cloud customers' privacy concerns and elevating their condence in using the cloud for security-sensitive operations as well as trusting it with their sensitive data. The main goal is to provide cloud customers' with a reliable mechanism that will cover the entire path of tracking their sensitive data, while they are collected and used by cloud-hosted services, to the presentation of the tracking results to the respective data owners. In particular, my design accomplishes this goal by retrofitting legacy applications with data flow tracking techniques and providing the cloud customers with comprehensive information flow auditing capabilities. For this purpose, we created CloudFence, a cloud-wide fine-grained data flow tracking (DFT) framework, that sensitive data in well-defined domains, offering additional protection against inadvertent leaks and unauthorized access.

Multi threaded programs have become pervasive and critical due to the rise of the multi core hardware and the accelerating computational demand. Unfortunately, despite decades of research and engineering effort, these programs remain notoriously difficult to get right, and they are plagued with harmful concurrency bugs that can cause wrong outputs, program crashes, security breaches, and so on. Our research reveals that a root cause of this difficulty is that multithreaded programs have too many possible thread interleavings (or schedules) at runtime. Even given only a single input, a program may run into a great number of schedules, depending on factors such as hardware timing and OS scheduling. Considering all inputs, the number of schedules is even much greater. It is extremely challenging to understand, test, analyze, or verify this huge number of schedules for a multi threaded program and make sure that all these schedules are free of concurrency bugs. Thus, multi threaded programs are extremely difficult to get right. To reduce the number of possible schedules for all inputs, we looked into the relation between inputs and schedules of real-world programs, and made an exciting discovery: many programs need only a small set of schedules to efficiently process a wide range of inputs! Leveraging this discovery, we have proposed a new idea called Stable Multithreading (or StableMT) that reuses each schedule on a wide range of inputs, greatly reducing the number of possible schedules for all inputs. By addressing the root cause that makes multithreading difficult to get right, StableMT makes understanding, testing, analyzing, and verification of multithreaded programs much easier. To realize StableMT, we have built three StableMT systems, TERN, PEREGRINE, and PARROT, with each addressing a distinct research challenge. Evaluation on a wide range of 108 popular multithreaded programs with our latest StableMT system, PARROT, shows that StableMT is simple, fast, and deployable. All PARROT's source code, entire benchmarks, and raw evaluation results are available at http://github.com/columbia/smt-mc. To encourage deployment, we have applied StableMT to improve several reliability techniques, including: (1) making reproducing real world concurrency bugs much easier; (2) greatly improving the precision of static program analysis, leading to the detection of several new harmful data races in heavily tested programs; and (3) greatly increasing the coverage of model checking, a systematic testing technique, by many orders of magnitudes. StableMT has attracted the research community's interests, and some techniques and ideas in our StableMT systems have been leveraged by other researchers to compute a small set of schedules to cover all or most inputs for multi threaded programs.

Return-oriented programming (ROP) has become the primary exploitation technique for system compromise in the presence of non-executable page protections. ROP exploits are facilitated mainly by the lack of complete address space randomization coverage or the presence of memory disclosure vulnerabilities, necessitating additional ROP-specific mitigations. Existing defenses against ROP exploits either require source code or symbolic debugging information, or impose a significant runtime overhead, which limits their applicability for the protection of third-party applications. We propose two novel techniques to prevent ROP exploits on third-party applications without requiring their source code or debug symbols, while at the same time incurring a minimal performance overhead. Their effectiveness is based on breaking an invariant of ROP attacks: knowledge of the code layout, and a common characteristic: unrestricted use of indirect branches. When combined, they still retain their applicability and efficiency, while maximizing the protection coverage against ROP. The first technique, in-place code randomization, uses narrow-scope code transformations that can be applied statically, without changing the location of basic blocks, allowing the safe randomization of stripped binaries even with partial disassembly coverage. These transformations effectively eliminate 10%, and probabilistically break 80% of the useful instruction sequences found in a large set of PE files. Since no additional code is inserted, in-place code randomization does not incur any measurable runtime overhead, enabling it to be easily used in tandem with existing exploit mitigations such as address space layout randomization. Our evaluation using publicly available ROP exploits and two ROP code generation toolkits demonstrates that our technique prevents the exploitation of the tested vulnerable Windows 7 applications, including Adobe Reader, as well as the automated construction of alternative ROP payloads that aim to circumvent in-place code randomization using solely any remaining unaffected instruction sequences. The second technique is based on the detection of abnormal control transfers that take place during ROP code execution. This is achieved using hardware features of commodity processors, which incur negligible runtime overhead and allow for completely transparent operation without requiring any modifications to the protected applications. Our implementation for Windows 7, named kBouncer, can be selectively enabled for installed programs in the same fashion as user-friendly mitigation toolkits like Microsoft's EMET. The results of our evaluation demonstrate that kBouncer has low runtime overhead of up to 4%, when stressed with specially crafted workloads that continuously trigger its core detection component, while it has negligible overhead for actual user applications. In our experiments with in-the-wild ROP exploits, kBouncer successfully protected all tested applications, including Internet Explorer, Adobe Flash Player, and Adobe Reader. In addition, we introduce a technique that enables ASLR for executables with stripped relocation information by incrementally adjusting stale absolute addresses at runtime. The technique relies on runtime monitoring of memory accesses and control flow transfers to the original location of a module using page table manipulation. We have implemented a prototype of the proposed technique for Windows 8, which is transparently applicable to third-party stripped binaries. Our results demonstrate that incremental runtime relocation patching is practical, incurs a runtime overhead of up to 83% in most of the cases for initial runs of protected programs, and has a low runtime overhead of 5% on subsequent runs.

Graphical models provide a flexible, powerful and compact way to model relationships between random variables, and have been applied with great success in many domains. Combining prior beliefs with observed evidence to form a prediction is called inference. Problems of great interest include finding a configuration with highest probability (MAP inference) or solving for the distribution over a subset of variables (marginal inference). Further, these methods are often critical subroutines for learning the relationships. However, inference is computationally intractable in general. Hence, much effort has focused on two themes: finding subdomains where exact inference is solvable efficiently, or identifying approximate methods that work well. We explore both these themes, restricting attention to undirected graphical models with discrete variables. First we address exact MAP inference by advancing the recent method of reducing the problem to finding a maximum weight stable set (MWSS) on a derived graph, which, if perfect, admits polynomial time inference. We derive new results for this approach, including a general decomposition theorem for models of any order and number of labels, extensions of results for binary pairwise models with submodular cost functions to higher order, and a characterization of which binary pairwise models can be efficiently solved with this method. This clarifies the power of the approach on this class of models, improves our toolbox and provides insight into the range of tractable models. Next we consider methods of approximate inference, with particular emphasis on the Bethe approximation, which is in widespread use and has proved remarkably effective, yet is still far from being completely understood. We derive new formulations and properties of the derivatives of the Bethe free energy, then use these to establish an algorithm to compute log of the optimum Bethe partition function to arbitrary epsilon-accuracy. Further, if the model is attractive, we demonstrate a fully polynomial-time approximation scheme (FPTAS), which is an important theoretical result, and demonstrate its practical applications. Next we explore ways to tease apart the two aspects of the Bethe approximation, i.e. the polytope relaxation and the entropy approximation. We derive analytic results, show how optimization may be explored over various polytopes in practice, even for large models, and remark on the observed performance compared to the true distribution and the tree-reweighted (TRW) approximation. This reveals important novel observations and helps guide inference in practice. Finally, we present results related to clamping a selection of variables in a model. We derive novel lower bounds on an array of approximate partition functions based only on the model's topology. Further, we show that in an attractive binary pairwise model, clamping any variable and summing over the approximate sub-partition functions can only increase (hence improve) the Bethe approximation, then use this to provide a new, short proof that the Bethe partition function lower bounds the true value for this class of models. The bulk of this work focuses on the class of binary, pairwise models, but several results apply more generally.

Given the wide range of successful statistical MT approaches that have emerged recently, it would be beneficial to take advantage of their individual strengths and avoid their individual weaknesses. Multi-Engine Machine Translation (MEMT) attempts to do so by either fusing the output of multiple translation engines or selecting the best translation among them, aiming to improve the overall translation quality. In this thesis, we propose to use the phrase or the sentence as our combination unit instead of the word; three new phrase-level models and one sentence-level model with novel features are proposed. This contrasts with the most popular system combination technique to date which relies on word-level confusion network decoding. Among the three new phrase-level models, the first one utilizes source sentences and target translation hypotheses to learn hierarchical phrases -- phrases that contain subphrases (Chiang 2007). It then re-decodes the source sentences using the hierarchical phrases to combine the results of multiple MT systems. The other two models we propose view combination as a paraphrasing process and use paraphrasing rules. The paraphrasing rules are composed of either string-to-string paraphrases or hierarchical paraphrases, learned from monolingual word alignments between a selected best translation hypothesis and other hypotheses. Our experimental results show that all of the three phrase-level models give superior performance in BLEU compared with the best single translation engine. The two paraphrasing models outperform the re-decoding model and the confusion network baseline model. The sentence-level model exploits more complex syntactic and semantic information than the phrase-level models. It uses consensus, argument alignment, a supertag-based structural language model and a syntactic error detector. We use our sentence-level model in two ways: the first selects a translated sentence from multiple MT systems as the best translation to serve as a backbone for paraphrasing process; the second makes the final decision among all fused translations generated by the phrase-level models and all translated sentences of multiple MT systems. We proposed two novel hybrid combination structures for the integration of phrase-level and sentence-level combination frameworks in order to utilize the advantages of both frameworks and provide a more diverse set of plausible fused translations to consider.

Structured representations are ubiquitous in natural language processing as both the product of text analysis tools and as a source of features for higher-level problems such as text generation. This dissertation explores the notion that different structured abstractions offer distinct but incomplete perspectives on the meaning encoded within a piece of text. We focus largely on monolingual text-to-text generation problems such as sentence compression and fusion, which present an opportunity to work toward general-purpose statistical models for text generation without strong assumptions on a domain or semantic representation. Systems that address these problems typically rely on a single structured representation of text to assemble a sentence; in contrast, we examine joint inference approaches which leverage the expressive power of heterogenous representations for these tasks. These ideas are introduced in the context of supervised sentence compression through a compact integer program to simultaneously recover ordered n-grams and dependency trees that specify an output sentence. Our inference approach avoids cyclic and disconnected structures through flow networks, generalizing over several established compression techniques and yielding significant performance gains on standard corpora. We then consider the tradeoff between optimal solutions, model flexibility and runtime efficiency by targeting the same objective with approximate inference techniques as well as polynomial-time variants which rely on mildly constrained interpretations of the compression task. While improving runtime is a matter of both theoretical and practical interest, the flexibility of our initial technique can be further exploited to examine the multi-structured hypothesis under new structured representations and tasks. We therefore investigate extensions to recover directed acyclic graphs which can represent various notions of predicate-argument structure and use this to experiment with frame-semantic formalisms in the context of sentence compression. In addition, we generalize the compression approach to accommodate multiple input sentences for the sentence fusion problem and construct a new dataset of natural sentence fusions which permits an examination of challenges in automated content selection. Finally, the notion of multi-structured inference is considered in a different context -- that of monolingual phrase-based alignment -- where we find additional support for a holistic approach to structured text representation.

Recently, due to the burst of online text data, much of the focus of natural language processing (NLP) research has shifted from long documents to shorter ones such as sentences and utterances. However, short texts posit significant challenges from an NLP perspective especially if the goal is to get at sentence level semantics in the absence of larger contexts. Motivated by this challenge, this thesis focuses on the problem of predicting the similarity between two short text samples by extracting the latent representation of the text data, and we apply the resulting models in various NLP tasks that involves short text similarity computation. The major challenge of computing short text similarity is insufficient information in the text snippets. In a sentence similarity benchmark [Agirre et al., 2012], on average a sentence has 10.8 words. Hence, there are very few overlapping words in a text pair even when they are semantically related, and the widely used bag-of-words representation fails to captures the semantics relatedness. To this end, we propose several weighted matrix factorization models for learning latent representation of texts , which induces meaningful similar scores: 1. Modeling Missing Words: To address the word sparsity issue, we propose to model the missing words (words that are not in the short text), a feature that is typically overlooked in the literature. We define the missing words of a text as the whole vocabulary in a corpus minus the observed words in the text. The model carefully handles the missing words that by assigning them a small weight in the matrix factorization framework. In the experiments, the new model {\it weighted matrix factorization} (WMF) achieves superior performance to Latent Dirichlet Allocation (LDA) [Blei et al., 2003], which does not use missing words, and latent semantic analysis (LSA) [Deerwester et al., 1990], which uses missing words but does not distinguish missing words from observed words. 2. Modeling Lexical Semantics: We improve the previous (WMF) model in terms of lexical semantics. For short text similarity, it is crucial to robustly model each word in the text to capture the complete semantic picture of the text, since there is very few repetitive information given the short context. To this end, we incorporate both corpus based (bigrams) and knowledge-based (similar words extracted from a dictionary) lexical semantics into the WMF model. The experiments show both additional information are helpful and complementary to each other. 3. Similarity Computing for Large-scale data sets: We tackle the short text similarity problem in large scale setting, i.e., given a query tweet, compute the similarity/distance with all other data point in a database, and rank them based on similarity/distance score. To reduce the computation time, we exploit binary coding to transform each data sample into a compact binary code, hence enables highly efficient similarity computations via Hamming distances between the generated codes. In order to preserve as much original data as possible in the binary bits, we restrict the projection directions to be nearly orthogonal hence reduce redundant information. The resulting model demonstrate better performance in both short text similarity task and a tweet retrieval task. We not only are interested in the short text similarity task itself, but also are concerned with how much the model could contribute to other NLP tasks. Accordingly, we adapt the short text similarity for several NLP tasks closely associated to semantics, which involve intensive similarity computation: 4. Text Summarization Evaluation: The pyramid method is one of the most popular methods for evaluating content selection in summarization, which requires manual inspection during evaluation. Recently some efforts have been made to automate the evaluation process: Harnly et al. (2005) searched for key facts/concepts covered in the summaries based on surface word matching. We apply WMF model to this task to enable more accurate key facts identification in summaries. The resulting automated pyramid scores correlate very well with manual pyramid scores. 5. Word Sense Disambiguation: The unsupervised Word Sense Disambiguation (WSD) systems highly rely on a sense similarity module that returns a similarity score given two senses. Currently the most popular sense similarity measure is Extended Lesk [Banerjee and Pedersen, 2003], which calculates the similarity score based on the number of overlapping words and phrases between two extended dictionary definitions. We propose a new sense similarity measure wmfvec by running WMF on the sense definition data and integrating WordNet [Fellbaum, 1998] features. The WSD system using wmfvec significantly outperforms traditional surface form based WSD algorithms as well as LDA based systems. 6. Linking Tweets to News: In this task we target at social media data and news data. We propose a new task of linking a tweet to a news article that is most relevant to the tweet. The motivation of the task is to argument the context of a tweet by a news article. We extend the WMF model and incorporate multiple Twitter/news specific features, i.e., hashtag, named entities and timestamps, in the new model. Our experiments show significant improvement of the new model over baselines in various evaluation metrics.

In this thesis I will show that, by leveraging efficient data structures and algorithms for indexing and secure computation, we can create practical systems for anonymous and private search, communication, and content distribution. I will improve and extend existing work in private search, which only addresses the problem where a client stores his own data encrypted on a server and wishes to be able to search his records remotely without revealing the their content. I do so by addressing a broader scenario, in which one or more servers store their own data, and a number of users wish to be able to issue queries across these records, without the server learning about the types of queries users are running, and without users learning anything about the remote databases besides the results of their searches. I also improve upon the field of anonymous communication systems, where prior systems focused on addressed communication in a unicast setting. I will discuss how we can create anonymous communication systems that work on a publish-subscribe basis, allowing communication to reach many people while solving the issue of how to establish communication without prior relationships. Next, I will discuss anonymous credential systems, and how to make them feasible for real-world scenarios. These systems can be useful for anonymously enforcing policies and managing privileges on a per-user basis. Our final challenge is to provide a scalable anonymous communication system that can deliver our queries while maintaining our privacy requirements. I will do this using a publish-subscribe architecture. I will show how all of these advancements can be accomlished by leveraging Bloom Filters, Onion Routing, Re-routable Encryption, and Yao Garbled Circuits to create anonymity preserving systems that operate in real time.

In this thesis, I investigate whether social power relations are manifested in the language and structure of social interactions, and if so, in what ways, and whether we can use the insights gained from this study to build computational systems that can automatically identify these power relations by analyzing social interactions. To further understand these manifestations, I extend this study in two ways. First, I investigate whether a person’s gender and the gender makeup of an interaction (e.g., are most participants female?) affect the manifestations of his/her power (or lack of it) and whether it can help improve the predictive performance of an automatic power prediction system. Second, I investigate whether different types of power manifest differently in interactions, and whether they exhibit different but predictable patterns. I perform this study on interactions from two different genres: organizational emails, which contain task oriented written interactions, and political debates, which contain discursive spoken interactions.