At Google, fuzzing C/C++ libraries has discovered tens of thousands of security and robustness bugs. However, these bugs are often reported much after they were introduced. Developers are provided only with fault-inducing test inputs and replication instructions that highlight a crash, but additional debugging information may be needed to localize the cause of the bug. Hence, developers need to spend substantial time debugging the code and identifying commits that introduced the bug. In this paper, we discuss our experience with automating a fuzzing-enabled bisection that pinpoints the commit in which the crash first manifests itself. This ultimately reduces the time critical bugs stay open in our code base. We report on our experience over the past year, which shows that developers fix bugs on average 2.23 times faster when aided by this automated analysis.

CPU and device virtualization technology allows applications to be hosted on cloud platforms; some of the resulting benefits are lower cost and greater elasticity. In such cloud hosted applications, some components reside on the cloud while others, such as end users and components tied to physical devices, are located outside the cloud. Many applications, e.g., telecom services, have stringent latency requirements in terms of within how much time certain procedures must be completed. The application latency is strongly determined by the locations of all the interacting components that are both within and outside the cloud. In this paper, we study the problem of determining the optimal placement of the application components in the cloud so that the latency requirements of the application can be met. We present a precise formulation of the placement problem which includes a specification of the cloud platform, and collective latency expressions for application-level latency requirements. We show that Message Sequence Charts (MSCs), a widely-used mechanism for describing the execution of application procedures, can be naturally translated into our formalism of collective latency expressions. We present placement algorithms that exploit the Euclidean triangular inequality property of network topologies: (a) an exact algorithm for determining the most optimal placement but which has a worst-case exponential running time, and (b) an algorithm for determining a close to-optimal placement that has a fast polynomial running time. Additionally, we present an exact technique for partitioning a placement problem into smaller sub problems so that greater efficiency and accuracy can be achieved. We evaluate the performance of the algorithms on a representative telecom application --- a distributed deployment of the LTE Mobility Management Entity (MME). Our evaluation results show that our approximate algorithm can outperform a random placement by up to 49% for finding a successful placement.

Cloud platforms enable enterprises to lease computing power in the form of virtual machines. An important problem for such enterprise users is to understand how many and what kinds of virtual machines will be needed from clouds. We formulate demand for computing power and other resources as a resource allocation problem with multiplicity, where computations that have to be performed concurrently are represented as tasks and a later task can reuse resources released by an earlier task. We show that finding a minimized allocation is NP-complete. This paper presents an approximation algorithm with a proof of its approximation bound that can yield close to optimum solutions in polynomial time. Enterprise users can exploit the solution to reduce the leasing cost and amortize the administration overhead (e.g., setting up VPNs or configuring a cluster). Cloud providers may utilize the solution to share their resources among a larger number of users.

Batch resource allocation problem arises in the context of executing a sequence of automated system tests or distributed computations where resources are pooled together and flexibly matched with requests. Minimizing resource allocation for a batch of processes reduces the resource management (e.g., setup) cost for the batch while allowing more users to share the resource pool simultaneously. The salient characteristic of the batch resource allocation problem is that while resources can be reused across different processes they are subject to mutually exclusive use for any individual process. We show that resource allocation for a single process can be solved in polynomial time whereas the general optimization problem is NP-complete. This motivates us to consider heuristics that can yield close to optimum solutions in polynomial time. We design several such heuristics and present their experimental comparison. Our experiments show that a technique based on a min-cost max-flow algorithm combined with ranked removal yields the best solution while having smallest running time.

Passive monitoring or testing of complex systems and networks running in the field can provide valuable insights into their behavior in actual environments of use. In certain contexts, such as network management and intrusion detection for security, passive monitoring is the most applicable methodology for assuring correctness of the system's behavior. More generally, it can serve to complement and extend functional testing and fault detection efforts that take place during the software/product development lifecycle. Two distinguishing aspects of passive monitoring are that: (a) the fault detection process cannot influence the execution of the system by providing particular inputs to the system, and (b) observations are obtained mid-stream, from an unknown state in the middle of the execution of the system. In this paper, we present results on passively testing for real-time behavioral properties that can be applied to a large class of systems including those that can be modeled as timed automata. Our results provide a natural extension of the passive testing study conducted in [17] for untimed properties. We have implemented our approach using the real-time model checker UPPAAL, and we report on its application to passively test fault tolerance software in a telecommunications switch developed at Lucent Technologies.

The ever increasing complexity of networks dramatically increases the challenges faced by service providers to analyze network behavior and (re)provision resources to support multiple complex distributed applications. Accurate and scalable simulation tools are pivotal to this cause. The recently proposed hybrid systems model for data communication networks shows promise in achieving performance characteristics comparable to fluid models while retaining the accuracy of discrete models. Using the hybrid systems paradigm, this paper provides contributions to the modeling of TCP behavior and the analysis/simulation of data communication networks based on these models. An important distinguishing feature of our simulation framework is a faithful accounting of link propagation delays which has been ignored in previous work for the sake of simplicity. Other salient aspects of the work include a new finite state machine model for a drop-tail queue, a new model for fast recovery/fast retransmit mode, a revised sending rate model, and an embedded time-out mode transition mechanism all of which employ a time-stepped solution method to solve the hybrid system network models. Our simulation results are consistent with well-known packet based simulators such as ns-2, thus demonstrating the accuracy of our hybrid model. Our future efforts will be directed towards studying and improving the computational performance of hybrid model based simulations.

Border gateway protocol (BGP) is the de facto standard used for interdomain routing. Since packet forwarding may not be possible until stable routes are learned, it is not only critical for BGP to converge but it is important that the convergence be rapid. The distributed and asynchronous nature of BGP in conjunction with local policies makes it difficult to analyze with respect to convergence behavior. We present a novel model which, to our knowledge, is the first one to permit analysis of convergence in the aggregate (i.e., over all message exchange orders between routers regarding route advertisements), rather than worst case behavior. We introduce the notion of probabilistic safety as requiring the probability of convergence to be 1. We provide a necessary and sufficient condition characterizing probabilistic safety that shows that probabilistic safety accommodates BGP configurations whose potential divergence stems solely from pathological message sequences. More generally, we show how to compute for any BGP configuration its probability of convergence. For probabilistically safe configurations, we present procedures for computing their expected time to converge as well as the probability distribution on their convergence times. The ability to compute these quantitative characteristics makes our work "constructive" and provides the basis for further understanding and deriving procedures for optimizing network characteristics. Finally, we simulate several network examples and verify the consistency between our analysis and the simulations

Message ferrying (MF) (Wenrui Zhao and Ammar, M.H., Proc. IEEE Workshop on Future Trends in Distrib. Computing Syst., 2003), a viable solution for routing in highly partitioned ad-hoc networks, exploits message ferries to transfer packets between disconnected nodes. The paper studies the delivery quality of service (QoS) for certain urgent messages in the constrained and the relaxed constrained MF systems. Efficient algorithms to compute near-optimal ferry routes are proposed, delay analysis is conducted and the results are compared to the non-constrained scenario.

A new scheme for solving the Slepian-Wolf problem over noisy channels using serially concatenated codes is proposed. An outer low density parity check code is used to perform distributed source coding, and an inner convolutional code adds error protecting capability to the compressed data. A soft iterative joint source-channel decoder is performed, where the decoder side information is provided to the sub outer decoder instead of the sub inner decoder. The scheme is attractive since separate refining of compression rate (outer code) and error protection power (inner code) makes the design easy and the performance controllable, and joint iterative decoding exploits the power of the serial concatenated structure as much as possible. Simulations reveal encouraging joint decoding gain especially at low signal-to-noise ratios.

Many topology discovery systems rely on traceroute to discover path information in public networks. However, for some routers, traceroute detects their existence but not their address; we term such routers anonymous routers. This paper considers the problem of inferring the network topology in the presence of anonymous routers. We illustrate how obvious approaches to handle anonymous routers lead to incomplete, inflated, or inaccurate topologies. We formalize the topology inference problem and show that producing both exact and approximate solutions is intractable. Two heuristics are proposed and evaluated through simulation. These heuristics have been used to infer the topology of the 6Bone, and could be incorporated into existing tools to infer more comprehensive and accurate topologies.

Event correlation is a key functionality of a network management system that is used to determine the root cause of faults in a network, and to filter out redundant and spurious events. A number of event correlation systems have been proposed. The event correlation systems generally combine causal and temporal correlation models with the topology of a network. The power and robustness of the models used and the algorithms developed vary from system to system. However, in the absence of a simple, uniform, and precise presentation of the event-correlation problem, it is impossible to compare their relative power or even analyze them for their properties. In general, causal and temporal-based correlation models have not been rigorously presented or thoroughly investigated. In this paper we formalize the concepts of causal and temporal correlation using a single conceptual framework. We characterize various properties of the framework. We can characterize existing systems based on the formal properties of our framework, and we consider one system as an illustrative example.

Two problems in the design and deployment of multimedia applications are the lack of design-time and run-time flexibility. In this paper we discuss a general methodology for tackling these issues. The work presented here is an extension of the AlphaOmega framework of [4]. In that framework we showed how the intuitive notion of an object representing its properties and capabilities to other objects differentially could be exploited to provide a powerful but easy way to change the behavior and interfaces of an application, dynamically if desired. In this paper, we develop a formal approach to the basic principles of the AlphaOmega framework. This leads to the definition of a formal system called the αω-calculus. The αω-calculus identifies a set of programming language abstractions that can be consistently added to any object-oriented language. While the calculus captures the intuitive notions underlying the AlphaOmega framework, it also goes beyond the original framework in power and flexibility. We demonstrate the generality of our approach by working with an example that shows how it provides unifying abstractions for such seemingly diverse domains as interactive distance learning and various issues in the area of multimedia documents.

We present a new interpretation of typed object-oriented concepts in terms of well-understood, purely procedural concepts, that preserves observational equivalence. More precisely, we give compositional translations of (a) Ob/sub 1/spl mu//, an object calculus supporting method invocation and functional method update with first-order object types and recursive types, and (b) Ob/sub 1<:/spl mu//, an extension of Ob/sub 1/spl mu// with subtyping, that are fully abstract on closed terms. The target of the translations are a first-order /spl lambda/-calculus with records and recursive types, with and without subtyping. The translation of the calculus with subtyping is subtype-preserving as well.

We present an interpretation of typed object-oriented concepts in terms of well-understood, purely procedural concepts. More precisely, we give a compositional subtype-preserving translation of a basic object calculus supporting method invocation, functional method update, and subtyping, into the polymorphic λ-calculus with recursive types and subtyping. The translation techniques apply also to an imperative version of the object calculus which includes in-place method update and object cloning. Finally, the translation easily extends to "Self types" and other interesting object-oriented constructs.

Standard ML of New Jersey (SML–NJ) uses “weak type variables” to restrict the polymorphic use of functions that may allocate reference cells, manipulate continuations, or use exceptions. However, the type system used in the SML–NJ compiler has not previously been presented in a form other than source code nor proved correct. We present a set of typing rules, based on analysis of the concepts underlying “weak polymorphism”, that appears to subsume the implemented algorithm and uses type variables of only a slightly more general nature than the compiler. One insight in the analysis is that allowing a variable to occur both “ordinarily” and “weakly” in a type permits a simpler and more flexible formulation of the typing rules. In particular, we are able to treat applications of polymorphic functions to imperative arguments with greater flexibility than SML–NJ. The soundness of the type system is proved for imperative code using operational semantics, by showing that evaluation preserves typability. By incorporating assumptions about memory addresses in the type system, we avoid proofs by co-induction.

It is well known that adding side effects to functional languages changes the operational equivalences of the language. We develop a new language construct, encap, that forces imperative pieces of code to behave purely functionally, i.e., without any visible side effects. The coercion operator encap provides a means of extending the simple reasoning principles for equivalences of code in a functional language to a language with side effects. In earlier work [36], similar coercion operators were developed, but their correctness required the underlying functional language to include parallel operations. The coercion operators developed here are simpler and are proven correct for purely sequential languages. The sequential setting requires the construction of fully abstract models for sequential call-by-value languages and the formulation of a weak form of "monad" suitable for expressing the semantics of call-by-value languages with side effects. 1 Introduction Two pieces of code are...

Standard ML of New Jersey (SML-NJ) uses weak-type variables to restrict the polymorphic use of functions that may allocate reference cells, manipulate continuations, or use exceptions. However, the type system used in the SML-NJ compiler has not been presented in a form other than source code and has not been proved correct. A type system, in the form of typing rules and an equivalent algorithm, that appears to subsume the implemented algorithm is presented. Both use type variables of only a slightly more general nature than the compiler. One insight in the analysis is that the indexed type of a free variable is used in two ways, once in describing the applicative behavior of the variable itself and once in describing the larger term containing the variable. Taking this into account, an application rule that is more general than SML-NJ is formulated for applications of polymorphic functions to imperative arguments. The soundness of the type system is proved for imperative code using operational semantics.>