The shift to cloud-based APIs has made application security critically depend on understanding and reasoning about policies that regulate access to cloud resources.We present stratified predicate abstraction, a new approach that summarizes complex security policies into a compact set of positive and declarative statements that precisely state who has access to a resource.We have implemented stratified abstraction and deployed it as the engine powering AWS's IAM Access Analyzer service, and hence, demonstrate how formal methods and SMT can be used for security policy explanation.

Data stored in cloud services is highly sensitive and so access to it is controlled via policies written in domain-specific languages (DSLs). The expressiveness of these DSLs provides users flexibility to cover a wide variety of uses cases, however, unintended misconfigurations can lead to potential security issues. We introduce Block Public Access, a tool that formally verifies policies to ensure that they only allow access to trusted principals, i.e. that they prohibit access to the general public. To this end, we formalize the notion of Trust Safety that formally characterizes whether or not a policy allows unconstrained (public) access. Next, we present a method to compile the policy down to a logical formula whose unsatisfiability can be (1) checked by SMT and (2) ensures Trust Safety. The constructs of the policy DSLs render unsatisfiability checking PSPACE-complete, which precludes verifying the millions of requests per second seen at cloud scale. Hence, we present an approach that leverages the structure of the policy DSL to compute a much smaller residual policy that corresponds only to untrusted accesses. Our approach allows Block Public Access to, in the common case, syntactically verify Trust Safety without having to query the SMT solver. We have implemented Block Public Access and present an evaluation showing how the above optimization yields a low-latency policy verifier that the S3 team at AWS has integrated into their authorization system, where it is currently in production, analyzing millions of policies everyday to ensure that client buckets do not grant unintended public access.

Modeling human behavior requires vast quantities of accurately labeled training data, but for ubiquitous people-aware applications such data is rarely attainable. Even researchers make mistakes when labeling data, and consistent, reliable labels from low-commitment users are rare. In particular, users may give identical labels to activities with characteristically different signatures (e.g., labeling eating at home or at a restaurant as "dinner") or may give different labels to the same context (e.g., "work" vs. "office"). In this scenario, labels are unreliable but nonetheless contain valuable information for classification. To facilitate learning in such unconstrained labeling scenarios, we propose Community-Guided Learning (CGL), a framework that allows existing classifiers to learn robustly from unreliably-labeled user-submitted data. CGL exploits the underlying structure in the data and the unconstrained labels to intelligently group crowd-sourced data. We demonstrate how to use similarity measures to determine when and how to split and merge contributions from different labeled categories and present experimental results that demonstrate the effectiveness of our framework.

Personal mobile devices are increasingly equipped with the capability to sense the physical world (through cameras, microphones, and accelerometers, for example) and the, network world (with Wi-Fi and Bluetooth interfaces). Such devices offer many new opportunities for cooperative sensing applications. For example, users' mobile phones may contribute data to community-oriented information services, from city-wide pollution monitoring to enterprise-wide detection of unauthorized Wi-Fi access points. This people-centric mobile-sensing model introduces a new security challenge in the design of mobile systems: protecting the privacy of participants while allowing their devices to reliably contribute high-quality data to these large-scale applications.

We propose a simple active method for discovering facts about the chipset, the firmware or the driver of an 802.11 wireless device by observing its responses (or lack thereof) to a series of crafted non-standard or malformed 802.11 frames. We demonstrate that such responses can differ significantly enough to distinguish between a number of popular chipsets and drivers. We expect to significantly expand the number of recognized device types through community contributions of signature data for the proposed open fingerprinting framework. Our method complements known fingerprinting approaches, and can be used to interrogate and spot devices that may be spoofing their MAC addresses in order to conceal their true architecture from other stations, such as a fake AP seeking to engage clients in complex protocol frame exchange (e.g., in order to exploit a driver vulnerability). In particular, it can be used to distinguish rogue APs from legitimate APs before association.