This paper considers the quantitative measurementof information flow through a program -- the degree of influence a program's inputs can have over a set of specified program variables. This definition has been proposed as a refinement of taint analysis in the detection of a class of security flaws in programs. Unfortunately, the precise information flow by this definition is difficult to compute, and prior work has sacrificed precision, scalability, and/or automation. In this paper, we show how to compute this information flow (specifically, channel capacity) in a highly precise and automatic manner, and scale to much larger programs than previously possible. We build on recent advances in symbolic execution and SAT solving, and propose further novel improvements as well. We discover two previously-unknown buffer overflows using our tool. Experimentally, we demonstrate that our approach scales to over 10K lines of real C code.

Abstract Even if a web-based messaging service offered confidential channels, how would users know whether their keys, or indeed even their plaintext, was not being exfiltrated? What if a variety of applications offered confidentiality? How would a user gain trust in all of them? In this paper we argue that a platform for private web applications is the only practical way for users to gain assurance about the confidentiality claims of a large number of full-featured web-services.We introduce Beeswax, a client-side platform that allows confidential data to be exchanged between users at the behest of an application, through a narrow set of APIs. Beeswax installs in a modern browser to deliver a complete practical solution, from key distribution to isolation of private data from the applications, thereby making an analysis of application code unnecessary. This focuses scrutiny and trust on the platform itself, rather than on all the applications using it.

Users of hosted web-based applications implicitly trust that those applications, and the data that is within them, will remain active and available indefinitely into the future. When a service is terminated, for reasons such as the insolvency of the business that is providing it, users risk the immediate loss of software functionality and may face the permanent loss of their own data. This paper presents Micasa, a runtime for hosted applications that allows a significant subset of application logic and user data to remain available even in the event of the failure of a provider's business. By allowing users to audit application dependence on hosted components, and maintain externalized and private copies of their own data and the logic that allows access to it, we believe that Micasa is a first step in the direction of a more balanced degree of trust and investment between application providers and their users.

As hardware parallelism continues to increase, CPU caches can no longer be considered as a transparent, hardware-level performance optimization. Cache impact on performance, in particular in the face of false sharing, is completely dependent on the software that is executing. To effectively support parallel workloads on cache coherent hardware, the operating system must begin to treat the CPU cache like other shared hardware resources, and manage it appropriately.

The smart grid introduces concerns for the loss of consumer privacy; recently deployed smart meters retain and distribute highly accurate profiles of home energy use. These profiles can be mined by Non Intrusive Load Monitors (NILMs) to expose much of the human activity within the served site. This paper introduces a new class of algorithms and systems, called Non Intrusive Load Leveling (NILL) to combat potential invasions of privacy. NILL uses an in-residence battery to mask variance in load on the grid, thus eliminating exposure of the appliance-driven information used to compromise consumer privacy. We use real residential energy use profiles to drive four simulated deployments of NILL. The simulations show that NILL exposes only 1.1 to 5.9 useful energy events per day hidden amongst hundreds or thousands of similar battery-suppressed events. Thus, the energy profiles exhibited by NILL are largely useless for current NILM algorithms. Surprisingly, such privacy gains can be achieved using battery systems whose storage capacity is far lower than the residence's aggregate load average. We conclude by discussing how the costs of NILL can be offset by energy savings under tiered energy schedules.

Cloud computing uses virtualization to lease small slices of large-scale datacenter facilities to individual paying customers. These multi-tenant environments, on which numerous large and popular web-based applications run today, are founded on the belief that the virtualization platform is sufficiently secure to prevent breaches of isolation between different users who are co-located on the same host. Hypervisors are believed to be trustworthy in this role because of their small size and narrow interfaces.

The development and maintenance of network device configurations is one of the central challenges faced by large network providers. Current network management systems fail to meet this challenge primarily because of their inability to adapt to rapidly evolving customer and provider-network needs, and because of mismatches between the conceptual models of the tools and the services they must support. In this paper, we present the Presto configuration management system that attempts to address these failings in a comprehensive and flexible way. Developed for and used during the last 5 years within a large ISP network, Presto constructs device-native configurations based on the composition of configlets representing different services or service options. Configlets are compiled by extracting and manipulating data from external systems as directed by the Presto configuration scripting and template language. We outline the configuration management needs of large-scale network providers, introduce the PRESTO system and configuration language, and reflect upon our experiences developing PRESTO configured VPN and VoIP services. In doing so, we describe how PRESTO promotes healthy configuration management practices.

We consider buffer management policies for shared memory switches. We study the case of overloads resulting in packet loss, where the constraint is the limited shared memory capacity. The goal of the buffer management policy is that of maximizing the number of packets transmitted. The problem is online in nature, and thus we use competitive analysis to measure the performance of the buffer management policies. Our main result is to show that the well-known preemptive Longest Queue Drop ( LQD ) policy is at most 2-competitive and at least √2-competitive. We also demonstrate a general lower bound of 4/3 on the performance of any deterministic online policy. Finally, we consider some other popular non-preemptive policies including Complete Partition, Complete Sharing, Static Threshold and Dynamic Threshold and derive almost tight bounds on their performance.

In this paper, we devise a special 1-error-correcting code that enables us to embed the graph product of an $N/\log N$-node hypercube and a $\log N$-node complete graph into in an N-node hypercube with constant load, dilation, and congestion. We apply the result to construct improved embeddings of trees and other structures in a hypercube, and to design more efficient and robust algorithms for reconfiguring a hypercube around random or worst-case faults. The result has also been used subsequently by others to show that the N-node hypercube can emulate all N-node planar graphs with constant slowdown.

The Border Gateway Protocol (BGP) is the de facto interdomain routing protocol on the Internet. While the serious vulnerabilities of BGP are well known, no security solution has been widely deployed. The lack of adoption is largely caused by a failure to find a balance between deployability, cost, and security. In this paper, we consider the design and performance of BGP path authentication constructions that limit resource costs by exploiting route stability. Based on a year-long study of BGP traffic and indirectly supported by findings within the networking community, we observe that routing paths are highly stable. This observation leads to comprehensive and efficient constructions for path authentication. We empirically analyze the resource consumption of the proposed constructions via trace-based simulations. This latter study indicates that our constructions can reduce validation costs by as much as 97.3% over existing proposals while requiring nominal storage resources. We conclude by considering operational issues related to incremental deployment of our solution.

We describe Just Fast Keying (JFK), a new key-exchange protocol, primarily designed for use in the IP security architecture. It is simple, efficient, and secure; we sketch a proof of the latter property. JFK also has a number of novel engineering parameters that permit a variety of tradeoffs, most notably the ability to balance the need for perfect forward secrecy against susceptibility to denial-of-service attacks.

Attacks against Internet routing are increasing in number and severity. Contributing greatly to these attacks is the absence of origin authentication: there is no way to validate claims of address ownership or location. The lack of such services enables not only attacks by malicious entities, but indirectly allow seemingly inconsequential miconfigurations to disrupt large portions of the Internet. This paper considers the semantics, design, and costs of origin authentication in interdomain routing. We formalize the semantics of address delegation and use on the Internet, and develop and characterize broad classes of origin authentication proof systems. We estimate the address delegation graph representing the current use of IPv4 address space using available routing data. This effort reveals that current address delegation is dense and relatively static: as few as 16 entities perform 80% of the delegation on the Internet. We conclude by evaluating the proposed services via traced based simulation. Our simulation shows the enhanced proof systems can significantly reduce resource costs associated with origin authentication.

We describe JFK, a new key exchange protocol, primarily designed for use in the IP Security Architecture. It is simple, efficient, and secure; we sketch a proof of the latter property. JFK also has a number of novel engineering parameters that permit a variety of trade-offs, most notably the ability to balance the need for perfect forward secrecy against susceptibility to denial-of-service attacks.

Many massive graphs (such as the WWW graph and Call graphs) share certain universal characteristics which can be described by the so-called "power law." In this paper, we, examine three important aspects of power law graphs, (1) the evolution of power law graphs, (2) the asymmetry of in-degrees and out-degrees, (3) the "scale invariance" of power law graphs. In particular, we give three increasingly general directed graph models and one general undirected graph model for generating power law graphs by adding at most one node and possibly one or more edges at a time. We show that for any given edge density and desired power laws for in-degrees and out-degrees, not necessarily the same, the resulting graph will almost surely have the desired edge density and the power laws for the in-degrees and out-degrees. Our most general directed and undirected models include nearly all known power law evolution models as special cases. Finally, we show that our evolution models generate "scale invariant" graphs. We describe a method for scaling the time in our evolution model such that the power law of the degree sequences remains invariant.

This paper presents a simple atomic model of message-passing multicomputers. Within one synchronous time step each processor can receive one atomic message, perform local computation, and send one message. When several messages are destined to the same processor, then one is transmitted and the rest are blocked. Blocked messages cannot be retrieved by their sending processors; each processor must wait for its blocked message to clear before sending more messages into the network. Depending on the traffic pattern, messages can remain blocked for arbitrarily long periods. The model is conservative when compared with existing message-passing systems. Nonetheless, we prove linear message throughput when destinations are chosen at random; this rigorously justifies an instance of folklore. Based on this result we also prove linear speedup for backtrack and branch-and-bound searches using simple randomized algorithms.

We study four augmentations of ring networks which are intended to enhance a ring's efficiency as a communication medium significantly, while increasing its structural complexity only modestly. Chordal rings add "shortcut" edges, which can be viewed as chords, to the ring. Express rings are chordal rings whose chords are routed outside the ring. Multirings append subsidiary rings to edges of a ring and, recursively, to edges of appended subrings. Hierarchical ring networks (HRN's) append subsidiary rings to nodes of a ring and, recursively, to nodes of appended subrings. We show that these four modes of augmentation are very closely related: 1) Planar chordal rings, planar express rings, and multirings are topologically equivalent families of networks with the "cutwidth" of an express ring translating into the "tree depth" of its isomorphic multiring and vice versa. 2) Every depth-d HRN is a spanning subgraph of a depth-(2d-1) multiring. 3) Every depth-d multiring /spl Mscr/ can be embedded into a d-dimensional mesh with dilation 3 in such a way that some node of /spl Mscr/ resides at a corner of the mesh. 4) Every depth-d HRN /spl Hscr/ can be embedded into a d-dimensional mesh with dilation 2 in such a way that some node of /spl Hscr/ resides at a corner of the mesh. In addition to demonstrating that these four augmented ring networks are grid graphs, our embedding results afford us close bounds on how much decrease in diameter is achievable for a given increase in structural complexity for the networks. Specifically, we derive upper and lower bounds on the optimal diameters of N-node depth-d multirings and HRN's that are asymptotically tight for large N and d.

We consider the setting of a network providing differentiated services. As is often the case in differentiated services, we assume the packets are tagged as either being high- or low-priority packets. Outgoing links in the network are serviced by a single FIFO queue. Our model gives a benefit of /spl alpha//spl ges/1 to each high-priority packet and a benefit of 1 to each low-priority packet. A queue policy controls which of the arriving packets are dropped and which enter the queue. Once a packet enters the queue it is eventually sent. The aim of a queue policy is to maximize the sum of the benefits of all the packets it delivers. We analyze and compare different queue policies for this problem using the competitive analysis approach, where the benefit of the online policy is compared to the benefit of an optimal offline policy. We derive both upper and lower bounds for the policies we consider, and in most cases our bounds are tight. We believe that competitive analysis gives important insight into the performance of these simple queuing policies.

We propose a random graph model which is a special case of sparse random graphs with given degree sequences. This model involves only a small number of parameters, called logsize and log-log growth rate. These parameters capture some universal characteristics of massive graphs. Furthermore, from these parameters, various properties of the graph can be derived. For example, for certain ranges of the parameters, we will compute the expected distribution of the sizes of the connected components which almost surely occur with high probability. We will illustrate the consistency of our model with the behavior of some massive graphs derived from data in telecommunications. We will also discuss the threshold function, the giant component, and the evolution of random graphs in this model. 1 Introduction Is the World Wide Web completely connected? If not, how big is the largest component, the second largest component, etc.? Anyone who has "surfed" the Web for any length of time will come away ...

We introduce a technique for using an untrusted device, such as a hand-held personal digital assistant or a laptop to perform real financial transactions without a network. We utilize the tamper-resistant nature of smartcards to store value on them and perform probabilistic computations based on user input. We discuss an application of this to gambling. The technique has the properties that the user is guaranteed to make money when he wins and the house is guaranteed to make money when the user loses. 1 Introduction We are currently experiencing a proliferation of lightweight handheld devices, such as the 3Com palm pilot, windows CE devices, and even laptops that weigh under three pounds. Many of these devices are so portable that people have them in their pockets and use them at all times. Our goal is to enable people to utilize these devices during otherwise dead time perhaps at the doctor's office, or in line at the supermarket. We are interested in utilizing the time when the us...

One of the central tasks of networking is packet-routing when edge bandwidth is limited. Tremendous progress has been achieved by separating the issue of routing into two conceptual sub-problems: path selection and congestion resolution along the selected paths. However, this conceptual separation has a serious drawback: each packet’s path is fixed at the source and cannot be modified adaptively en-route. The problem is especially severe when packet injections are modeled by an adversary, whose goal is to cause “traffic-jams”. In this paper, we consider this adversarial setting, motivated by the “adversarial queuing theory ” model of Borodin et al. [BKR+]. More precisely, we consider an adversary who injects packets, with only their destinations specified, into network nodes in a continuous manner subject to certain limitations on the injection rate. The question whether it is possible to deal with such an adversary and to design protocols that would “discover ” routes which avoid “traffic jams ” so that nodes only store a bounded number of packets, was left as an open problem by Andrews et al. [AAF+] (who deal with the “non-adaptive ” case where the adversary provides routes for the packets). In the present paper, we resolve this open problem. In particular, we present a simple, deterministic, local-control protocol that applies to any network topology. Our protocol guarantees that, for any injection sequence generated by the adversary, the buffers at the nodes are polynomially-bounded and that each packet has a polynomiallybounded delivery time.

Article Knowledge on the average—perfect, statistical and logarithmic Share on Authors: William Aiello Math and Cryptography Research Group, Bellcore, 445 South St. Morristown, NJ Math and Cryptography Research Group, Bellcore, 445 South St. Morristown, NJView Profile , Mihir Bellare IBM T.J. Watson Research Center, PO Box 704, Yorktown Heights, NY IBM T.J. Watson Research Center, PO Box 704, Yorktown Heights, NYView Profile , Ramarathnam Venkatesan Math and Cryptography Research Group, Bellcore, 445 South St. Morristown, NJ Math and Cryptography Research Group, Bellcore, 445 South St. Morristown, NJView Profile Authors Info & Claims STOC '95: Proceedings of the twenty-seventh annual ACM symposium on Theory of computingMay 1995 Pages 469–478https://doi.org/10.1145/225058.225186Published:29 May 1995 6citation264DownloadsMetricsTotal Citations6Total Downloads264Last 12 Months3Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

A novel combinatorial approach to wait-free loadbalancing, counting, synchronization and buffer mancontention notion was only asymptotic (i.e., as achievable eventually).

Article Free Access Share on An atomic model for message-passing Authors: Pangfeng Liu View Profile , William Aiello View Profile , Sandeep Bhatt View Profile Authors Info & Claims SPAA '93: Proceedings of the fifth annual ACM symposium on Parallel Algorithms and ArchitecturesAugust 1993 Pages 154–163https://doi.org/10.1145/165231.165251Published:01 August 1993Publication History 25citation266DownloadsMetricsTotal Citations25Total Downloads266Last 12 Months11Last 6 weeks3 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

This paper presents a simple local algorithm for load balancing in a distributed network.The algorithm makes no assumption about the structure of the network.It can be executed on a synchronous network with fixed topology, a synchronous network with dynamically changing topology, or an asynchronous network.It works quickly and balances well when the network has an expansion property.In particular, we show that in an n-node network with maximum degree d whose live edges, at every time step, forma p-expander, the algorithm will balance the load to within an additive O(d log n/p) term in O(A log(nA)/p) time, where A is the initial imbalance.The algorithm improves upon previous approaches that yield O(n) time bounds in dynamic and asynchronous networks.

Article Coding theory, hypercube embeddings, and fault tolerance Share on Authors: Bill Aiello Bellcore, Morristown, NJ Bellcore, Morristown, NJView Profile , Tom Leighton Mathematics Department and Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA Mathematics Department and Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MAView Profile Authors Info & Claims SPAA '91: Proceedings of the third annual ACM symposium on Parallel algorithms and architecturesJune 1991 Pages 125–136https://doi.org/10.1145/113379.113391Online:01 June 1991Publication History 51citation402DownloadsMetricsTotal Citations51Total Downloads402Last 12 Months2Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

In this paper, we describe an O(log N) bit-step randomized algorithm for bit-serial message routing on a hypercube.The result is asymptotically optimal, and improves upon the best previously known algorithms by a logarithmic factor.The result also solves the problem of on-line circuit switching in an O(l)-dilated hypercube (i.e., partitioning the edges of a dilated hypercube so as to realize an arbitrary permutation of point-to-point connections between the nodes).Our algorithm is adaptive and we show that this is necessary to achieve the logarithmic speedup.We generalize the Borodin-Hopcroft lower bound on oblivious routing by proving that any oblivious randomized algorithm on a polylogarithmic degree network requires sZ(log' N/log log N) bit steps with high probability for almost all permutations.

A hierarchy of probabilistic complexity classes generalizing NP has recently emerged in the work of [Ba], [GMR], and [GS]. The IP hierarchy is defined through the notion of an interactive proof system, in which an all powerful prover tries to convince a probabilistic polynomial time verifier that a string w is in a language L. The verifier tosses coins and exchanges messages back and forth with the prover before he decides whether to accept w. This proof-system yields "probabilistic" proofs: the verifier may erroneously accept or reject w with small probability. In [GMR] such a protocol was defined to be a zero-knowledge protocol if at the end of the interaction the verifier has learned nothing except that w ∈ L. We study complexity theoretic implications of a language having this property. In particular we prove that if L admits a zeroknowledge proof then L can also be recognized by a two round interactive proof. This complements a result by Fortnow [F] where it is proved that the complement of L has a two round interactive proof protocol. The methods of proof are quite similar to those of Fortnow [F]. As in his case the proof works under the assumption that the original protocol is only zero-knowledge with respect to a specific verifier.

A hierarchy of probabilistic complexity classes generalizing NP has recently emerged in the work of [B], [GMR], and [GS]. The IP hierarchy is defined through the notion of an interactive proof system, in which an all powerful prover tries to convince a probabilistic polynomial time verifier that a string x is in a language L. The verifier tosses coins and exchanges messages back and forth with the prover before he decides whether to accept x. This proof-system yields "probabilistic" proofs: the verifier may erroneously accept or reject x with small probability. The class IP[f(|x|)] is said to contain L if, there exists an interactive proof system with f(|x|)- message exchanges (interactions) such that with high probability the verifier accepts x if and only if x ε L. Babai [B] showed that all languages recognized by interactive proof systems with bounded number of interactions, can be recognized by interactive proof systems with only two interactions. Namely, for every constant k, IP[k] collapses to Ip[2]. In this paper, we give evidence that interactive proof systems with unbounded number of interactions may be more powerful than interactive proof systems with bounded number of interactions. We show that for any unbounded function f(n) there exists an oracle B such that IPB [f(|x|)] ⊄ PHB. This implies that IPB[f(n)] ≠ IPB[2], since IPB[2] ⊆ Π2B for all oracles B. The techniques employed are extensions of the techniques for proving lower bounds on small depth circuits used in [FSS], [Y] and [H1].