Android's filesystem access control provides a foundation for system integrity. It combines mandatory (e.g., SEAndroid)and discretionary (e.g., Unix permissions) access control, protecting both the Android platform from Android/OEM services and Android/OEM services from third-party applications. However, OEMs often introduce vulnerabilities when they add market-differentiating features and fail to correctly reconfigure this complex combination of policies. In this paper, we propose the PolyScope tool to triage Android systems for vulnerabilities using their filesystem access control policies by: (1) identifying the resources that subjects are authorized to use that may be modified by their adversaries, both with and without policy manipulations, and (2) determining the attack operations on those resources that are actually available to adversaries to reveal the specific cases that need vulnerability testing. A key insight is that adversaries may exploit discretionary elements in Android access control to expand the permissions available to themselves and/or victims to launch attack operations, which we call permission expansion. We apply PolyScope to five Google and five OEM Android releases and find that permission expansion increases the privilege available to launch attacks, sometimes by more than 10x, but a significant fraction (about 15-20%) cannot be converted into attack operations due to other system configurations. Based on this analysis, we describe two previously un-known vulnerabilities and show how PolyScope helps OEMs triage the complex combination of access control policies down to attack operations worthy of testing

ARM’s TrustZone technology is the basis for security of billions of devices worldwide, including Android smartphones and IoT devices. Because TrustZone has access to sensitive information such as cryptographic keys, access to TrustZone has been locked down on real-world devices: only code that is authenticated by a trusted party can run in TrustZone. A side-effect is that TrustZone software cannot be instrumented or monitored. Thus, recent advances in dynamic analysis techniques such as feedback-driven fuzz testing have not been applied to TrustZone software. To address the above problem, this work builds an emulator that runs four widely-used, real-world TrustZone operating systems (TZOSes) - Qualcomm’s QSEE, Trustonic’s Kinibi, Samsung’s TEEGRIS, and Linaro’s OP-TEE - and the trusted applications (TAs) that run on them. The traditional challenge for this approach is that the emulation effort required is often impractical. However, we find that TZOSes depend only on a limited subset of hardware and software components. By carefully choosing a subset of components to emulate, we find we are able to make the effort practical. We implement our emulation on PARTEMU, a modular framework we develop on QEMU and PANDA. We show the utility of PARTEMU by integrating feedback-driven fuzz-testing using AFL and use it to perform a large-scale study of 194 unique TAs from 12 different Android smartphone vendors and a leading IoT vendor, finding previously unknown vulnerabilities in 48 TAs, several of which are exploitable. We identify patterns of developer mistakes unique to TrustZone development that cause some of these vulnerabilities, highlighting the need for TrustZone-specific developer education. We also demonstrate using PARTEMU to test the QSEE TZOS itself, finding crashes in code paths that would not normally be exercised on a real device. Our work shows that dynamic analysis of real-world TrustZone software through emulation is both feasible and beneficial

Coverage-guided fuzz testing has gained prominence as a highly effective method of finding security vulnerabilities such as buffer overflows in programs that parse binary data. Recently, researchers have introduced various specializations to the coverage-guided fuzzing algorithm for different domain-specific testing goals, such as finding performance bottlenecks, generating valid inputs, handling magic-byte comparisons, etc. Each such solution can require non-trivial implementation effort and produces a distinct variant of a fuzzing tool. We observe that many of these domain-specific solutions follow a common solution pattern. In this paper, we present FuzzFactory, a framework for developing domain-specific fuzzing applications without requiring changes to mutation and search heuristics. FuzzFactory allows users to specify the collection of dynamic domain-specific feedback during test execution, as well as how such feedback should be aggregated. FuzzFactory uses this information to selectively save intermediate inputs, called waypoints, to augment coverage-guided fuzzing. Such waypoints always make progress towards domain-specific multi-dimensional objectives. We instantiate six domain-specific fuzzing applications using FuzzFactory: three re-implementations of prior work and three novel solutions, and evaluate their effectiveness on benchmarks from Google’s fuzzer test suite. We also show how multiple domains can be composed to perform better than the sum of their parts. For example, we combine domain-specific feedback about strict equality comparisons and dynamic memory allocations, to enable the automatic generation of ZIP bombs and PNG bombs.

AT commands, originally designed in the early 80s for controlling modems, are still in use in most modern smartphones to support telephony functions. The role of AT commands in these devices has vastly expanded through vendor-specific customizations, yet the extent of their functionality is unclear and poorly documented. In this paper, we systematically retrieve and extract 3,500 AT commands from over 2,000 Android smartphone firmware images across 11 vendors. We methodically test our corpus of AT commands against eight Android devices from four different vendors through their USB interface and characterize the powerful functionality ex- posed, including the ability to rewrite device firmware, bypass Android security mechanisms, exfiltrate sensitive device information, perform screen unlocks, and inject touch events solely through the use of AT commands. We demonstrate that the AT command interface contains an alarming amount of unconstrained functionality and rep- resents a broad attack surface on Android devices.

Hot-patches, easier to develop and faster to deploy than permanent patches, are used to timely (and temporarily) block exploits of newly discovered vulnerabilities while permanent patches are being developed and tested. Researchers recently proposed to apply hot-patching techniques to system programs on Android as a quick mitigation against critical vulnerabilities. However, existing hot-patching techniques, though widely used in conventional computers, are rarely adopted by Android OS or device vendors in reality. Our study uncovers a major hurdle that prevents existing hot-patching methods from being effective on mobile devices: after being developed, hot-patches for mobile devices have to go through lengthy compatibility tests that Android device partners impose on all system code updates. This testing and release process can take months, and therefore, erase the key benefit of hot-patches (i.e., quickly deployable). We propose InstaGuard, a new approach to hot-patch for mobile devices that allows for instant deployment of patches (i.e., “carrier-passthrough”) and fast patch development for device vendors. Unlike existing hot-patching techniques, InstaGuard avoids injecting new code to programs being patched. Instead, it enforces instantly updatable rules that contain no code (i.e., no carrier test is needed) to block exploits of unpatched vulnerabilities in a timely fashion. When designing InstaGuard, we overcame two major challenges that previous hot-patching methods did not face. First, since no code addition is allowed, InstaGuard needs a rule language that is expressive enough to mitigate various kinds of vulnerabilities and efficient to be enforced on mobile devices. Second, rule generation cannot require special skills or much efforts from human users. We designed a new language for hot-patches and an enforcement mechanism based on the basic debugging primitives supported by ARM CPUs. We also built RuleMaker, a tool for automatically generating rules for InstaGuard based on high-level, easy-to-write vulnerability descriptions. We have implemented InstaGuard on Google Nexus 5X phones. To demonstrate the coverage of InstaGuard, we show that InstaGuard can handle all critical CVEs from Android Security Bulletins reported in 2016. We also conduct unit tests using critical vulnerabilities from 4 different categories. On average, InstaGuard increases program memory footprint by 1.69% and slows down program execution by 2.70%, which are unnoticeable to device users in practice.

Code reuse attacks exploiting memory disclosure vulnerabilities can bypass all deployed mitigations. One promising defense against this class of attacks is to enable execute-only memory (XOM) protection on top of fine-grained address space layout randomization (ASLR). However, recent works implementing XOM, despite their efficacy, only protect programs that have been (re)built with new compiler support, leaving commercial-off-the-shelf (COTS) binaries and source-unavailable programs unprotected. We present the design and implementation of NORAX, a practical system that retrofits XOM into stripped COTS binaries on AArch64 platforms. Unlike previous techniques, NORAX requires neither source code nor debugging symbols. NORAX statically transforms existing binaries so that during runtime their code sections can be loaded into XOM memory pages with embedded data relocated and data references properly updated. NORAX allows transformed binaries to leverage the new hardware-based XOM support—a feature widely available on AArch64 platforms (e.g., recent mobile devices) yet virtually unused due to the incompatibility of existing binaries. Furthermore, NORAX is designed to co-exist with other COTS binary hardening techniques, such as in-place randomization (IPR). We apply NORAX to the commonly used Android system binaries running on SAMSUNG Galaxy S6 and LG Nexus 5X devices. The results show that NORAX on average slows down the execution of transformed binaries by 1.18% and increases their memory footprint by 2.21%, suggesting NORAX is practical for real-world adoption.

It is no surprise to say that attackers have the upper hand on security practitioners today when it comes to host security. There are several causes for this problem ranging from unsafe programming languages to the complexity of modern systems at large, but fundamentally, all of the parties involved in constructing and deploying systems lack a methodology for reasoning about the security impact of their design decisions. Previous position papers have focused on identifying particular parties as being “enemies” of security (e.g., users and application developers), and proposed removing their ability to make security relevant decisions. In this position paper, we take this approach a step further by “keeping the enemies closer,” whereby the security ramifications of design and deployment decisions of all parties must be evaluated to determine if they violate security requirements or are inconsistent with other party’s assumptions. We propose a methodology whereby application developers, OS distributors, and system administrators propose, evaluate, repair, and test their artifacts to provide a defensible attack surface, the set of entry points available to an attacker. We propose the use of a hierarchical state machine (HSM) model as a foundation for automatically evaluating attack surfaces for programs, OS access control policies, and network policies. We examine how the methodology tasks can be expressed as problems in the HSM model for each artifact, motivating the possibility of a comprehensive, coherent, and mostly-automated methodology for deploying systems to manage accessibility to attackers

Infrastructure-as-a-Service (IaaS) clouds can be viewed as distributed systems of cloud services that are entrusted to execute users' cloud commands to provision and manage clouds computing resources (e.g., VM). However, recent vulnerabilities found in cloud services show that this trust is often misplaced. By exploiting a vulnerability in a cloud service, an adversary can hijack or forge commands to modify user VMs, exfiltrate sensitive information, and even modify other service hosts. This paper introduces Cloud Armor, a system that detects and blocks the tampering of user commands without the need for modifications to cloud services. Our insight is that we can construct state machine models to limit the system call sequences executed by cloud services. By applying constraints over system call arguments, we can restrict the way user commands are executed, blocking unauthorized operations from compromised cloud services. We implemented a prototype Cloud Armor system for Open Stack, a widely adopted open source cloud platform. Results show that Cloud Armor can greatly limit attack options available for adversaries while imposing less than 1% overhead for user VMs. As a result, cloud users can leverage Cloud Armor to execute user commands safely even in presence of compromised cloud services.

Processes retrieve a variety of resources, such as files, from the operating system to function. However, securely accessing resources has proven to be a challenging task, accounting for 10-15% of vulnerabilities reported each year. Current defenses address only a subset of these vulnerabilities in ad-hoc and incomplete ways. In this paper, we provide a comprehensive defense against vulnerabilities during resource access. First, we identify a fundamental reason that resource access vulnerabilities exist – a mismatch between programmer expectations and the actual environment the program runs in. To address such mismatches, we propose JIGSAW, a system that can automatically derive programmer expectations and enforce it on the deployment. JIGSAW constructs programmer expectations as a name flow graph, which represents the data flows from the inputs used to construct file pathnames to the retrieval of system resources using those pathnames. We find that whether a program makes any attempt to filter such flows implies expectations about the threats the programmer expects during resource retrieval, the enabling JIGSAW to enforce those expectations. We evaluated JIGSAW on widely-used programs and found that programmers have many implicit expectations. These mismatches led us to discover two previously-unknown vulnerabilities and a default misconfiguration in the Apache webserver. JIGSAW enforces program expectations for approximately 5% overhead for Apache webservers, thus eliminating vulnerabilities due to resource access efficiently and in a principled manner.

Processes need a variety of resources from their operating environment in order to run properly, but adversary may control the inputs to resource retrieval or the end resource itself, leading to a variety of vulnerabilities. Conventional access control methods are not suitable to prevent such vulnerabilities because they use one set of permissions for all system call invocations. In this paper, we define a novel policy model for describing when resource retrievals are unsafe, so they can be blocked. This model highlights two contributions: (1) the explicit definition of adversary models as adversarial roles, which list the permissions that dictate whether one subject is an adversary of another, and (2) the application of data-flow to determine the adversary control of the names used to retrieve resources. An evaluation using multiple adversary models shows that while data-flow is necessary to authorize resource retrieval in over 90\% of system calls. By making adversary models and the adversary accessibility of all aspects of resource retrieval explicit, we can block resource access attacks system-wide.

Many smartphones now deploy conventional operating systems, so the rootkit attacks so prevalent on desktop and server systems are now a threat to smartphones. While researchers have advocated using virtualization to detect and prevent attacks on operating systems (e.g., VM introspection and trusted virtual domains), virtualization is not practical on smartphone systems due to the lack of virtualization support and/or the expense of virtualization. Current smartphone processors do have hardware support for running a protected environment, such as the ARM TrustZone extensions, but such hardware does not control the operating system operations sufficiently to enable VM introspection. In particular, a conventional operating system running with TrustZone still retains full control of memory management, which a rootkit can use to prevent traps on sensitive instructions or memory accesses necessary for effective introspection. In this paper, we present SPROBES, a novel primitive that enables introspection of operating systems running on ARM TrustZone hardware. Using SPROBES, an introspection mechanism protected by TrustZone can instrument individual operating system instructions of its choice, receiving an unforgeable trap whenever any SPROBE is executed. The key challenge in designing SPROBES is preventing the rootkit from removing them, but we identify a set of five invariants whose enforcement is sufficient to restrict rootkits to execute only approved, SPROBE-injected kernel code. We implemented a proof-of-concept version of SPROBES for the ARM Fast Models emulator, demonstrating that in Linux kernel 2.6.38, only 12 SPROBES are sufficient to enforce all five of these invariants. With SPROBES we show that it is possible to leverage the limited TrustZone extensions to limit conventional kernel execution to approved code comprehensively.

Cloud computing has commoditized compute, storage, and networking resources creating an on-demand utility. Despite the attractiveness of this new paradigm, its adoption has been stymied by cloud platform’s lack of transparency, which leaves customers unsure if their sensitive data and computation can be entrusted to the cloud. While techniques like encryption can protect customers’ data at rest, clouds still lack mechanisms for customers to verify that their computations are being executed as expected, a guarantee one could obtain if they were running the computation in their own data center. In this paper, we present the cloud verifier (CV), a flexible framework that cloud vendors can configure to provide cloud monitoring services for customers to validate that their computations are configured and being run as expected in Infrastructure as a Service (IaaS) clouds. The CV builds a chain of trust from the customer to their hosted virtual machine (VM) instances through the cloud platform, enabling it to check customer-specified requirements against a comprehensive view of both the VM’s load-time and run-time properties. In addition, the CV enables cloud vendors to provide more responsive remediation techniques than traditional attestation mechanisms. We built a proof of concept CV for the OpenStack cloud platform whose evaluation demonstrates that a single CV enables over 20,000 simultaneous customers to verify numerous properties with little impact on cloud application performance. As a result, the CV gives cloud customers a low-overhead method for assuring that their instances are running according to their requirements.

Processes retrieve a variety of resources from the operating system in order to execute properly, but adversaries have several ways to trick processes into retrieving resources of the adversaries' choosing. Such resource access attacks use name resolution, race conditions, and/or ambiguities regarding which resources are controlled by adversaries, accounting for 5-10\% of CVE entries over the last four years. programmers have found these attacks extremely hard to eliminate because resources are managed externally to the program, but the operating system does not provide a sufficiently rich system-call API to enable programs to block such attacks. In this paper, we present the Process Firewall, a kernel mechanism that protects processes in manner akin to a network firewall for the system-call interface. Because the Process Firewall only protects processes - rather than sandboxing them - it can examine their internal state to identify the protection rules necessary to block many of these attacks without the need for program modification or user configuration. We built a prototype Process Firewall for Linux demonstrating: (1) the prevention of several vulnerabilities, including two that were previously-unknown; (2) that this defense can be provided system-wide for less than 4\% overhead in a variety of macrobenchmarks; and (3) that it can also improve program performance, shown by Apache handling 38\% more requests when program resource access checks are replaced by Process Firewall rules. These results show that it is practical for the operating system to protect processes by preventing a variety of resource access attacks system-wide.

Many cloud vendors now provide pre-configured OS distributions and network firewall policies to simplify deployment for customers. However, even with this help, customers have little insight into the possible attack paths that adversaries may use to compromise the integrity of their computations on the cloud. In this paper, we leverage the pre-configured security policies for cloud instances to compute the integrity protection required to protect cloud deployments. In particular, we show that it is possible to compute security configurations for cloud instance deployments that can prevent information flow integrity errors and that these configurations can be measured into attestations using trusted computing hardware. We apply these proposed methods to the OpenStack cloud platform, showing how web server application instance can be configured to protect their integrity in the cloud and how integrity measurement can be used to validate such configurations for approximately 3\% overhead.

Programs fetch resources, such as files, from the operating system through the process of name resolution. However, name resolution can be subverted by adversaries to redirect victim processes to resources chosen by the adversaries, leading to a variety of attacks. These attacks are possible because traditional access control treats processes as black boxes, permitting all process permissions to all process system calls, enabling adversaries to trick victims into using resources that are not appropriate for particular system calls. Researchers have examined methods for enforcing distinct policies on individual system calls, but these methods are difficult to use because programmers must specify which permissions apply when manually. In this work, we examine the generation of system call-specific program policies to augment access control to defend against such name resolution attacks. Our insight in this paper is that system calls can be classified by the properties of the resources accessed to produce policies automatically. Given specific knowledge about name resolution attacks, such a classification may be refined further to prevent many name resolution attacks with little chance of false positives. In this paper, we produce a policy using runtime analysis for an Ubuntu 12.04 distribution, finding that 98.7\% of accesses can be restricted to prevent typical name resolution attacks and more than 65\% of accesses can be restricted to a single file without creating false positives. We also examine three programs in detail to evaluate the efficacy of using the provided package test suites to generate policies, finding that administrators can produce effective policies automatically.

Modern distributed systems are composed from several off-the-shelf components, including operating systems, virtualization infrastructure, and application packages, upon which some custom application software (e.g., web application) is often deployed. While several commodity systems now include mandatory access control (MAC) enforcement to protect the individual components, the complexity of such MAC policies and the myriad of possible interactions among individual hosts in distributed systems makes it difficult to identify the attack paths available to adversaries. As a result, security practitioners react to vulnerabilities as adversaries uncover them, rather than proactively protecting the system's data integrity. In this paper, we develop a mostly-automated method to transform a set of commodity MAC policies into a system-wide policy that proactively protects system integrity, approximating the Clark-Wilson integrity model. The method uses the insights from the Clark-Wilson model, which requires integrity verification of security-critical data and mediation at program entrypoints, to extend existing MAC policies with the proactive mediation necessary to protect system integrity. We demonstrate the practicality of producing Clark-Wilson policies for distributed systems on a web application running on virtualized Ubuntu SELinux hosts, where our method finds: (1) that only 27 additional entrypoint mediators are sufficient to mediate the threats of remote adversaries over the entire distributed system and (2) and only 20 additional local threats require mediation to approximate Clark-Wilson integrity comprehensively. As a result, available security policies can be used as a foundation for proactive integrity protection from both local and remote threats.

The process of name resolution, where names are resolved into resource references, is fundamental to computer science, but its use has resulted in several classes of vulnerabilities. These vulnerabilities are difficult for programmers to eliminate because their cause is external to the program: the adversary changes namespace bindings in the system to redirect victim programs to a resource of the adversary's choosing. Researchers have also found that these attacks are very difficult to prevent systematically. Any successful defense must have both knowledge about the system namespace and the program intent to eradicate such attacks. As a result, finding and fixing program vulnerabilities to such as attacks is our best defense. In this paper, we propose the STING~test engine, which finds name resolution vulnerabilities in programs by performing a dynamic analysis of name resolution processing to produce directed test cases whenever an attack may be possible. The key insight is that such name resolution attacks are possible whenever an adversary has write access to a directory shared with the victim, so STING~automatically identifies when such directories will be accessed in name resolution to produce test cases that are likely to indicate a true vulnerability if undefended. STING~utilizes a shadow resolution mechanism to identify the namespace bindings used in resolution and program-specific adversary models to identify those bindings that can be exploited by adversaries. Using this information, STING produces and runs directed test cases automatically, detecting vulnerabilities with few false positives. Using STING, we found 21 previously-unknown vulnerabilities in a variety of Linux programs on Ubuntu and Fedora systems, demonstrating that comprehensive testing for name resolution vulnerabilities is practical.

Users are increasingly turning to online services, but are concerned for the safety of their personal data and critical business tasks. While secure communication protocols like TLS authenticate and protect connections to these services, they cannot guarantee the correctness of the endpoint system. Users would like assurance that all the remote data they receive is from systems that satisfy the users' integrity requirements. Hardware-based integrity measurement (IM) protocols have long promised such guarantees, but have failed to deliver them in practice. Their reliance on non-performant devices that generate attestations as the basis for conveying integrity limits the efficiency, flexibility, and completeness of remote integrity verification. In this paper, we introduce the integrity verification proxy (IVP), a service that enforces integrity requirements over connections to remote systems. The IVP monitors changes to the unmodified system and immediately terminates connections to clients whose integrity requirements are not satisfied while eliminating the attestation reporting bottleneck imposed by current IM protocols. We implemented a proof-of-concept IVP that detects several classes of integrity violations on a Linux KVM system, while imposing less than 1.5\% overhead on two application benchmarks and no more than 8\% on I/O-bound micro-benchmarks.

Adding new programs or configuration options to a system often leads to new exploits because it provides adversaries with new ways to access possible vulnerabilities. As a result, application developers often must react to exploits as they are found. One proactive defense is to protect programs at their attack surfaces, the program entry points (e.g., system calls) accessible to adversaries. However, experience has shown that developers often fail to defend these entry points because they do not locate all such system calls where programs access system resources controlled by attackers. In this paper, we develop a runtime analysis method to compute program attack surfaces in system deployments, which uses a novel approach to computing program adversaries to determine which program entry points access adversary-controlled objects. We implemented our design as a Linux kernel mechanism capable of identifying entry points for both binary and interpreted programs. Using this mechanism, we computed the attack surfaces for all the programs in the Ubuntu Linux 10.04 Desktop distribution automatically. On examining located attack surfaces, we discovered previously unknown vulnerabilities in an X Windows startup script available since 2006 and the GNU Icecat web browser. Our tools enable developers to find attack surfaces for their programs quickly and to produce defenses prior to the emergence of attacks, potentially moving us away from the penetrate-and-patch rut.

Namespaces are fundamental to computing systems. Each namespace maps the names that clients use to retrieve resources to the actual resources themselves. However, the indirection that namespaces provide introduces avenues of attack through the name resolution process. Adversaries can trick programs into accessing unintended resources by changing the binding between names and resources and by using names whose target resources are ambiguous. In this paper, we explore whether a unified system approach may be found to prevent many name resolution attacks. For this, we examine attacks on various namespaces and use these to derive invariants to defend against these attacks. Four prior techniques are identified that enforce aspects of name resolution, so we explore how these techniques address the proposed invariants. We find that each of these techniques are incomplete in themselves, but a combination could provide effective enforcement of the invariants. We implement a prototype system that can implement these techniques for the Linux filesystem namespace, and show that invariant rules specific to each, individual program system call can be enforced with a small overhead (less than 3\%), indicating that fine-grained name resolution enforcement may be practical.

We are finding that customers with security-critical data processing needs are beginning to push back strongly against using cloud computing. In cloud computing, a vendor runs their computations upon cloud provided VM systems. Customers are worried that such host systems may not be able to protect themselves from attack, ensure isolation of customer processing, or load customer processing cor rectly. To provide assurance of data processing protection in clouds to customers, we advocate methods to improve cloud transparency using hardware-based attestation mechanisms. We find that the centralized management of cloud data centers is ideal for attesta tion frameworks, enabling the development of a practical approach for customers to trust in the cloud platform. Specifically, we pro pose a cloud verifier service that generates integrity proofs for customers to verify the integrity and access control enforcement abilities of the cloud platform that protect the integrity of customer’s application VMs in IaaS clouds. While a cloud-wide verifier service could present a significant system bottleneck, we demonstrate that aggregating proofs enables significant overhead reductions. As a result, transparency of data security protection can be verified at cloud-scale.

Computer security is currently fraught with fine-grained access control policies, in operating systems, applications and even programming languages. All this policy configuration means that too many decisions are left to administrators, developers and even users to some extent and as a result we do not get any comprehensive security guarantees. In this position paper, we take a stand for the idea that less policy is better and propose that limiting the choices given to parties along the development and deployment process leads to a more secure system. We argue that other systems processes like scheduling and memory management achieve their goals with minimal user input and access control configuration should also follow suit. We then suggest a technique to automate access control configuration using graph-cuts and show that this gets us closer to achieving our goal.

The recent emergence of mandatory access (MAC) enforcement for virtual machine monitors (VMMs) presents an opportunity to enforce a security goal over all its virtual machines (VMs). However, these VMs also have MAC enforcement, so to determine whether the overall system (VM-system) is secure requires an evaluation of whether this combination of MAC policies, as a whole, complies with a given security goal. Previous MAC policy analyses either consider a single policy at a time or do not represent the interaction between different policy layers (VMM and VM). We observe that we can analyze the VMM policy and the labels used for communications between VMs to create an inter-VM flow graph that we use to identify safe, unsafe, and ambiguous VM interactions. A VM with only safe interactions is compliant with the goal, a VM with any unsafe interaction violates the goal. For a VM with ambiguous interactions we analyze its local MAC policy to determine whether it is compliant or not with the goal. We used this observation to develop an analytical model of a VM-system, and evaluate if it is compliant with a security goal. We implemented the model and an evaluation tool in Prolog. We evaluate our implementation by checking whether a VM-system running XSM/Flask policy at the VMM layer and SELinux policies at the VM layer satisfies a given integrity goal. This work is the first step toward developing layered, multi-policy analyses.

We present a parallelization of the Floyd-Warshall all pairs shortest path algorithm for a distributed environment. A lot of versions of the Floyd-Warshall algorithm have been proposed for a uniprocessor environment, optimizing cache performance and register usage. However, in a distributed environment, communication costs between nodes have to be taken into consideration. We present a novel algorithm, Phased Floyd-Warshall, for a distributed environment, which optimally overlaps computation and communication. Our algorithm is compared with a register optimized version of the blocked all pairs shortest path algorithm [6, 4, 1] which is adapted for a distributed environment. We report speedups of 2.8 in a 16-node cluster and 1.2 in a 32-node cluster for a matrix size of 4096.

Packet classification is the problem of identifying which one of a set of rules maintained in a database is best matched by an incoming packet at a router and taking the action specified by the rule. This is a uniform enabler for many new network services like firewalls, quality of service and virtual private networks. These services require dynamic management of rules. While many algorithms recently proposed can perform packet classification at very high speeds, rule update times for these are not very fast. This paper presents an efficient classifier management algorithm, which effectively reduces the rule update time for the well known Grid-of-Tries classifier. To this end, we have devised a novel structure called Supervised Grid-of-Tries, which employs additional tracking pointers embedded into the trie to facilitate efficient rule updates.