Cryptographic algorithms, protocols, and applications are difficult to implement correctly, and errors and vulnerabilities in their code can remain undiscovered for long periods before they are exploited. Even highly-regarded cryptographic libraries suffer from bugs like buffer overruns, incorrect numerical computations, and timing side-channels, which can lead to the exposure of sensitive data and long-term secrets. We describe a tool chain and framework based on the F* programming language to formally specify, verify and compile high-performance cryptographic software that is secure by design. This tool chain has been used to build a verified cryptographic library called HACL*, and provably secure implementations of sophisticated secure communication protocols like Signal and TLS. We describe these case studies and conclude with ongoing work on using our framework to build verified implementations of privacy preserving machine learning software.

Logic vulnerabilities are an important class of programming flaws in web applications. These vulnerabilities occur when a desired property pertaining to an application's logic does not hold along certain paths in the application's code. Many analysis tools have been developed to find logic vulnerabilities in web applications. Given a web application with logic vulnerabilities, the question is whether one can design methods to patch application code and prevent these vulnerabilities from being exploited. We answer this question by developing an approach and tool called LogicPatcher for patching of logic vulnerabilities. We focus on correct patch placement, i.e. identifying the precise location in code where the patch code can be introduced, based on path profiling. As we show in this paper, finding the appropriate location as well as generating the right patch can get complicated and require deep code analysis. We demonstrate the utility of LogicPatcher by automatically fixing several critical parameter tampering and authorization vulnerabilities in large web applications.

We explore the problem of identifying unauthorized privilege escalation instances in a web application. These vulnerabilities are typically caused by missing or incorrect authorizations in the server side code of a web application. The problem of identifying these vulnerabilities is compounded by the lack of an access control policy specification in a typical web application, where the only supplied documentation is in fact its source code. This makes it challenging to infer missing checks that protect a web application's sensitive resources. To address this challenge, we develop a notion of authorization context consistency, which is satisfied when a web application consistently enforces its authorization checks across the code. We then present an approach based on program analysis to check for authorization state consistency in a web application. Our approach is implemented in a tool called MACE that uncovers vulnerabilities that could be exploited in the form of privilege escalation attacks. In particular, MACE is the first tool reported in the literature to identify a new class of web application vulnerabilities called Horizontal Privilege Escalation (HPE) vulnerabilities. MACE works on large codebases, and discovers serious, previously unknown, vulnerabilities in 5 out of 7 web applications tested. Without MACE, a comparable human-driven security audit would require weeks of effort in code inspection and testing.

Primal infon logic (PIL), introduced by Gurevich and Neeman in 2009, is a logic for authorization in distributed systems. It is a variant of the (and, implies)-fragment of intuitionistic modal logic. It presents many interesting technical challenges -- one of them is to determine the complexity of the derivability problem. Previously, some restrictions of propositional PIL were proved to have a linear time algorithm, and some extensions have been proved to be PSPACE-complete. In this paper, we provide an O(N^3) algorithm for derivability in propositional PIL. The solution involves an interesting interplay between the sequent calculus formulation (to prove the subformula property) and the natural deduction formulation of the logic (based on which we provide an algorithm for the derivability problem).

We present SEAL, a language for specification and analysis of safety properties for label-based access control systems. A SEAL program represents a possibly infinite-state non-deterministic transition system describing the dynamic behavior of entities and their relevant access control operations. The features of our language are derived directly from the need to model new access control features arising from state-of-the art models in Windows 7, Asbestos, HiStar and others. We show that the reachability problem for this class of models is undecidable even for simple SEAL programs, but a bounded model-checking algorithm is able to validate interesting properties and discover relevant attacks.

We present EON, a logic-programming language and tool that can be used to model and analyze dynamic access control systems. Our language extends Datalog with some carefully designed constructs that allow the introduction and transformation of new relations. For example, these constructs can model the creation of processes and objects, and the modification of their security labels at runtime. The information-flow properties of such systems can be analyzed by asking queries in this language. We show that query evaluation in EON can be reduced to decidable query satisfiability in a fragment of Datalog, and further, under some restrictions, to efficient query evaluation in Datalog.

Frequent itemsets mining is a popular framework for pattern discovery. In this framework, given a database of customer transactions, the task is to unearth all patterns in the form of sets of items appearing in a sizable number of transactions. We present a class of models called Itemset Generating Models (or IGMs) that can be used to formally connect the process of frequent item- sets discovery with the learning of generative models. IGMs are specified using simple probability mass functions (over the space of transactions), peaked at specific sets of items and uniform everywhere else. Under such a connection, it is possible to rigorously associate higher frequency patterns with generative models that have greater data likelihoods. This enables a generative model-learning interpretation of frequent itemsets mining. More importantly, it facilitates a statistical significance test which prescribes the minimum frequency needed for a pattern to be considered interesting. We illustrate the effectiveness of our analysis through experiments on standard benchmark data sets.

We investigate the cost of changing access control policies dynamically as a response action in computer network defense. We compare and contrast the use of access lists and capability lists in this regard, and develop a quantitative feel for the performance overheads and storage requirements. We also explore the issues related to preserving safety properties and trust assumptions during this process. We suggest augmentations to policy specifications that can guarantee these properties in spite of dynamic changes to system state. Using the lessons learned from this exercise, we apply these techniques in the design of dynamic access controls for dynamic environments.

Active Spaces are physical spaces augmented with heterogeneous computing and communication devices along with supporting software infrastructure. This integration facilitates collaboration between users, and promotes greater levels of interaction between users and devices. An Active Space can be configured for different types of applications at different times. We present an access control system that automates the creation and enforcement of access control policies for different configurations of an Active Space. Our system explicitly recognizes different modes of cooperation between groups of users, and the dependence between physical and virtual aspects of security in Active Spaces. Our model provides support for both discretionary and mandatory access control policies, and uses role-based access control techniques for easy administration of users and permissions. We dynamically assign permissions to user roles based on context information. We show how we can create dynamic protection domains. This allows administrators and application developers the ability to customize access control policies on a need-to-protect basis. We also provide a semi-formal specification and analysis of our model and show how we preserve safety properties in spite of dynamic changes to access control permissions.