bluuebunny/crossref_metadata_2025 huggingface dataset:
A case study in building layered DHT applications
Authors: Chawathe Yatin , Ramabhadran Sriram , Ratnasamy Sylvia , LaMarca Anthony , Shenker Scott , Hellerstein Joseph
Published: November 2005

Recent research has shown that one can use Distributed Hash Tables (DHTs) to build scalable, robust and efficient applications. One question that is often left unanswered is that of simplicity of implementation and deployment. In this paper, we explore a case study of building an application for which ease of deployment dominated the need for high performance. The application we focus on is Place Lab, an end-user positioning system. We evaluate whether it is feasible to use DHTs as an application-independent building block to implement a key component of Place Lab: its "mapping infrastructure." We present Prefix Hash Trees, a data structure used by Place Lab for geographic range queries that is built entire on top of a standard DHT. By strictly layering Place Lab's data structures on top of a generic DHT service, we were able to decouple the deployment and management of Place Lab from that of the underlying DHT. We identify the characteristics of Place Lab that made it amenable for deploying in this layered manner, and comment on its effect on performance.
Using redundancy to cope with failures in a delay tolerant network
Authors: Jain Sushant , Demmer Michael , Patra Rabin , Fall Kevin
Published: November 2005

We consider the problem of routing in a delay tolerant network (DTN) in the presence of
path failures
. Previous work on DTN routing has focused on using precisely known network dynamics, which does not account for message losses due to link failures, buffer overruns, path selection errors, unscheduled delays, or other problems. We show how to split, replicate, and erasure code message fragments over multiple delivery paths to optimize the probability of successful message delivery. We provide a formulation of this problem and solve it for two cases: a 0/1 (Bernoulli) path delivery model where messages are either fully lost or delivered, and a Gaussian path delivery model where only a fraction of a message may be delivered. Ideas from the modern portfolio theory literature are borrowed to solve the underlying optimization problem. Our approach is directly relevant to solving similar problems that arise in replica placement in distributed file systems and virtual node placement in DHTs. In three different simulated DTN scenarios covering a wide range of applications, we show the effectiveness of our approach in handling failures.
Idle sense
Authors: Heusse Martin , Rousseau Franck , Guillier Romaric , Duda Andrzej
Published: November 2005

We consider wireless LANs such as IEEE 802.11 operating in the unlicensed radio spectrum. While their nominal bit rates have increased considerably, the MAC layer remains practically unchanged despite much research effort spent on improving its performance. We observe that most proposals for tuning the access method focus on a single aspect and disregard others. Our objective is to define an access method optimized for throughput and fairness, able to dynamically adapt to physical channel conditions, to operate near optimum for a wide range of error rates, and to provide equal time shares when hosts use different bit rates.We propose a novel access method derived from 802.11 DCF [2] (
Distributed Coordination Function
) in which all hosts use similar values of the contention window CW to benefit from good short-term access fairness. We call our method
Idle Sense
, because each host observes the mean number of idle slots between transmission attempts to dynamically control its contention window. Unlike other proposals,
Idle Sense
enables each host to estimate its frame error rate, which can be used for switching to the right bit rate. We present simulations showing how the method leads to high throughput, low collision overhead, and low delay. The method also features fast reactivity and time-fair channel allocation.
On the predictability of large transfer TCP throughput
Authors: He Qi , Dovrolis Constantine , Ammar Mostafa
Published: November 2005

Predicting the throughput of large TCP transfers is important for a broad class of applications. This paper focuses on the design, empirical evaluation, and analysis of TCP throughput predictors. We first classify TCP throughput prediction techniques into two categories: Formula-Based (FB) and History-Based (HB). Within each class, we develop representative prediction algorithms, which we then evaluate empirically over the RON testbed. FB prediction relies on mathematical models that express the TCP throughput as a function of the characteristics of the underlying network path. It does not rely on previous TCP transfers in the given path, and it can be performed with non-intrusive network measurements. We show, however, that the FB method is accurate only if the TCP transfer is window-limited to the point that it does not saturate the underlying path, and explain the main causes of the prediction errors. HB techniques predict the throughput of TCP flows from a time series of previous TCP throughput measurements on the same path, when such a history is available. We show that even simple HB predictors, such as Moving Average and Holt-Winters, using a history of few and sporadic samples, can be quite accurate. On the negative side, HB predictors are highly path-dependent. We explain the cause of such path dependencies based on two key factors: the load on the path and the degree of statistical multiplexing.
Improving accuracy in end-to-end packet loss measurement
Authors: Sommers Joel , Barford Paul , Duffield Nick , Ron Amos
Published: November 2005

Measurement and estimation of packet loss characteristics are challenging due to the relatively rare occurrence and typically short duration of packet loss episodes. While active probe tools are commonly used to measure packet loss on end-to-end paths, there has been little analysis of the accuracy of these tools or their impact on the network. The objective of our study is to understand how to measure packet loss episodes accurately with end-to-end probes. We begin by testing the capability of standard Poisson-modulated end-to-end measurements of loss in a controlled laboratory environment using IP routers and commodity end hosts. Our tests show that loss characteristics reported from such Poisson-modulated probe tools can be quite inaccurate over a range of traffic conditions. Motivated by these observations, we introduce a new algorithm for packet loss measurement that is designed to overcome the deficiencies in standard Poisson-based tools. Specifically, our method creates a probe process that (1) enables an explicit trade-off between accuracy and impact on the network, and (2) enables more accurate measurements than standard Poisson probing at the same rate. We evaluate the capabilities of our methodology experimentally by developing and implementing a prototype tool, called BADABING. The experiments demonstrate the trade-offs between impact on the network and measurement accuracy. We show that BADABING reports loss characteristics far more accurately than traditional loss measurement tools.
Algorithms for advanced packet classification with ternary CAMs
Authors: Lakshminarayanan Karthik , Rangarajan Anand , Venkatachary Srinivasan
Published: November 2005

Ternary content-addressable memories (TCAMs) have gained wide acceptance in the industry for storing and searching Access Control Lists (ACLs). In this paper, we propose algorithms for addressing two important problems that are encountered while using TCAMs:
reducing range expansion
and
multi-match classification
.Our first algorithm addresses the problem of expansion of rules with range fields to represent range rules in TCAMs, a single range rule is mapped to multiple TCAM entries, which reduces the utilization of TCAMs. We propose a new scheme called
Database Independent Range PreEncoding
(DIRPE) that, in comparison to earlier approaches, reduces the worst-case number of TCAM entries a single rule maps on to. DIRPE works without prior knowledge of the database, scales when a large number of ranges is present, and has good incremental update properties.Our second algorithm addresses the problem of finding multiple matches in a TCAM. When searched, TCAMs return the first matching entry; however, new applications require either the first few or all matching entries. We describe a novel algorithm, called
Multi-match Using Discriminators
(MUD), that finds multiple matches without storing any per-search state information in the TCAM, thus making it suitable for multi-threaded environments. MUD does not increase the number of TCAM entries needed, and hence scales to large databases.Our algorithms do not require any modifications to existing TCAMs and are hence relatively easy to deploy. We evaluate the algorithms using real-life and random databases.
Dynamic pipelining
Authors: Hasan Jahangir , Vijaykumar T. N.
Published: November 2005

A truly scalable IP-lookup scheme must address five challenges of scalability, namely: routing-table size, lookup throughput, implementation cost, power dissipation, and routing-table update cost. Though several IP-lookup schemes have been proposed in the past, none of them do well in all the five scalability requirements. Previous schemes pipeline tries by mapping trie levels to pipeline stages. We make the fundamental observation that because this mapping is static and oblivious of the prefix distribution, the schemes do not scale well when worst-case prefix distributions are considered. This paper is the first to meet all the five requirements in the worst case. We propose scalable dynamic pipelining (SDP) which includes three key innovations: (1) We map trie nodes to pipeline stages based on the node height. Because the node height is directly determined by the prefix distribution, the node height succinctly provides sufficient information about the distribution. Our mapping enables us to prove a worst-case per-stage memory bound which is significantly tighter than those of previous schemes. (2) We exploit our mapping to propose a novel scheme for incremental route-updates. In our scheme a route-update requires exactly and only one write dispatched into the pipeline. This route-update cost is obviously the optimum and our scheme achieves the optimum in the worst case. (3) We achieve scalability in throughput by simultaneously pipelining at the data-structure level and the hardware level. SDP naturally scales in power and implementation cost. We not only present a theoretical analysis but also evaluate SDP and a number of previous schemes using detailed hardware simulation. Compared to previous schemes, we show that SDP is the only scheme that scales well in all the five requirements.
Mining anomalies using traffic feature distributions
Authors: Lakhina Anukool , Crovella Mark , Diot Christophe
Published: November 2005

The increasing practicality of large-scale flow capture makes it possible to conceive of traffic analysis methods that detect and identify a large and diverse set of anomalies. However the challenge of effectively analyzing this massive data source for anomaly diagnosis is as yet unmet. We argue that the distributions of packet features (IP addresses and ports) observed in flow traces reveals both the presence and the structure of a wide range of anomalies. Using entropy as a summarization tool, we show that the analysis of feature distributions leads to significant advances on two fronts: (1) it enables highly sensitive detection of a wide range of anomalies, augmenting detections by volume-based methods, and (2) it enables automatic classification of anomalies via unsupervised learning. We show that using feature distributions, anomalies naturally fall into distinct and meaningful clusters. These clusters can be used to automatically classify anomalies and to uncover new anomaly types. We validate our claims on data from two backbone networks (Abilene and Geant) and conclude that feature distributions show promise as a key element of a fairly general network anomaly diagnosis framework.
BLINC
Authors: Karagiannis Thomas , Papagiannaki Konstantina , Faloutsos Michalis
Published: November 2005

We present a fundamentally different approach to classifying traffic flows according to the applications that generate them. In contrast to previous methods, our approach is based on observing and identifying patterns of host behavior at the transport layer. We analyze these patterns at three levels of increasing detail (i) the social, (ii) the functional and (iii) the application level. This multilevel approach of looking at traffic flow is probably the most important contribution of this paper. Furthermore, our approach has two important features. First, it operates
in the dark
, having (a) no access to packet payload, (b) no knowledge of port numbers and (c) no additional information other than what current flow collectors provide. These restrictions respect privacy, technological and practical constraints. Second, it can be tuned to balance the accuracy of the classification versus the number of successfully classified traffic flows. We demonstrate the effectiveness of our approach on three real traces. Our results show that we are able to classify 80%-90% of the traffic with more than 95% accuracy.
A DoS-limiting network architecture
Authors: Yang Xiaowei , Wetherall David , Anderson Thomas
Published: November 2005

We present the design and evaluation of TVA, a network architecture that limits the impact of Denial of Service (DoS) floods from the outset. Our work builds on earlier work on capabilities in which senders obtain short-term authorizations from receivers that they stamp on their packets. We address the full range of possible attacks against communication between pairs of hosts, including spoofed packet floods, network and host bottlenecks, and router state exhaustion. We use simulation to show that attack traffic can only degrade legitimate traffic to a limited extent, significantly outperforming previously proposed DoS solutions. We use a modified Linux kernel implementation to argue that our design can run on gigabit links using only inexpensive off-the-shelf hardware. Our design is also suitable for transition into practice, providing incremental benefit for incremental deployment.
Walking the tightrope
Authors: Kandula Srikanth , Katabi Dina , Davie Bruce , Charny Anna
Published: November 2005

Current intra-domain Traffic Engineering (TE) relies on
offline
methods, which use long term average traffic demands. It cannot react to realtime traffic changes caused by BGP reroutes, diurnal traffic variations, attacks, or flash crowds. Further, current TE deals with network failures by pre-computing alternative routings for a limited set of failures. It may fail to prevent congestion when unanticipated or combination failures occur, even though the network has enough capacity to handle the failure.This paper presents TeXCP, an
online
distributed TE protocol that balances load in realtime, responding to actual traffic demands and failures. TeXCP uses multiple paths to deliver demands from an ingress to an egress router, adaptively moving traffic from over-utilized to under-utilized paths. These adaptations are carefully designed such that, though done independently by each edge router based on local information, they balance load in the whole network without oscillations. We model TeXCP, prove the stability of the model, and show that it is easy to implement. Our extensive simulations show that, for the same traffic demands, a network using TeXCP supports the same utilization and failure resilience as a network that uses traditional offline TE, but with half or third the capacity.
Policing congestion response in an internetwork using re-feedback
Authors: Briscoe Bob , Jacquet Arnaud , Di Cairano-Gilfedder Carla , Salvatori Alessandro , Soppera Andrea , Koyabe Martin
Published: November 2005

This paper introduces a novel feedback arrangement, termed re-feedback. It ensures metrics in data headers such as time to live and congestion notification will arrive at each relay carrying a truthful prediction of the remainder of their path. We propose mechanisms at the network edge that ensure the dominant selfish strategy of both network domains and end-points will be to set these headers honestly and to respond correctly to path congestion and delay, despite conflicting interests. Although these mechanisms influence incentives, they don't involve tampering with end-user pricing. We describe a TCP rate policer as a specific example of this new capability. We show it can be generalised to police various qualities of service. We also sketch how a limited form of re-feedback could be deployed incrementally around unmodified routers without changing IP.
Towards a global IP anycast service
Authors: Ballani Hitesh , Francis Paul
Published: November 2005

IP anycast, with its innate ability to find nearby resources in a robust and efficient fashion, has long been considered an important means of service discovery. The growth of P2P applications presents appealing new uses for IP anycast. Unfortunately, IP anycast suffers from serious problems: it is very hard to deploy globally, it scales poorly by the number of anycast groups, and it lacks important features like load-balancing. As a result, its use is limited to a few critical infrastructure services such as DNS root servers. The primary contribution of this paper is a new IP anycast architecture, PIAS, that overcomes these problems while largely maintaining the strengths of IP anycast. PIAS makes use of a proxy overlay that advertises IP anycast addresses on behalf of group members and tunnels anycast packets to those members. The paper presents a detailed design of PIAS and evaluates its scalability and efficiency through simulation. We also present preliminary measurement results on anycasted DNS root servers that suggest that IP anycast provides good affinity. Finally, we describe how PIAS supports two important P2P and overlay applications.
Towards an evolvable internet architecture
Authors: Ratnasamy Sylvia , Shenker Scott , McCanne Steven
Published: November 2005

There is widespread agreement on the need for architectural change in the Internet, but very few believe that current ISPs will ever effect such changes. In this paper we ask what makes an architecture evolvable, by which we mean capable of gradual change led by the incumbent providers. This involves both technical and economic issues, since ISPs have to be able, and incented, to offer new architectures. Our study suggests that, with very minor modifications, the current Internet architecture could be evolvable.
Incremental maintenance of shortest distance and transitive closure in first-order logic and SQL
Authors: Pang Chaoyi , Dong Guozhu , Ramamohanarao Kotagiri
Published: November 2005

Given a database, the view maintenance problem is concerned with the efficient computation of the new contents of a given view when updates to the database happen. We consider the view maintenance problem for the situation when the database contains a weighted graph and the view is either the transitive closure or the answer to the all-pairs shortest-distance problem (
APSD
). We give incremental algorithms for
APSD
, which support both edge insertions and deletions. For transitive closure, the algorithm is applicable to a more general class of graphs than those previously explored. Our algorithms use first-order queries, along with addition (+) and less-than (<) operations (
FO
(+,<)); they store
O
(
n
2
) number of tuples, where
n
is the number of vertices, and have
AC
0
data complexity for integer weights. Since
FO
(+,<) is a sublanguage of SQL and is supported by almost all current database systems, our maintenance algorithms are more appropriate for database applications than nondatabase query types of maintenance algorithms.
Database repairing using updates
Authors: Wijsen Jef
Published: November 2005

Repairing a database means bringing the database in accordance with a given set of integrity constraints by applying some minimal change. If a database can be repaired in more than one way, then the consistent answer to a query is defined as the intersection of the query answers on all repaired versions of the database.Earlier approaches have confined the repair work to deletions and insertions of entire tuples. We propose a theoretical framework that also covers updates as a repair primitive. Update-based repairing is interesting in that it allows rectifying an error within a tuple without deleting the tuple, thereby preserving consistent values in the tuple. Another novel idea is the construct of nucleus: a single database that yields consistent answers to a class of queries, without the need for query rewriting. We show the construction of nuclei for full dependencies and conjunctive queries. Consistent query answering and constructing nuclei is generally intractable under update-based repairing. Nevertheless, we also show some tractable cases of practical interest.
LH*
RS
---a highly-available scalable distributed data structure
Authors: Litwin Witold , Moussa Rim , Schwarz Thomas
Published: November 2005

LH*
RS
is a high-availability scalable distributed data structure (SDDS). An LH*
RS
file is hash partitioned over the distributed RAM of a multicomputer, for example, a network of PCs, and supports the unavailability of any
k
≥ 1 of its server nodes. The value of
k
transparently grows with the file to offset the reliability decline. Only the number of the storage nodes potentially limits the file growth. The high-availability management uses a novel parity calculus that we have developed, based on Reed-Salomon erasure correcting coding. The resulting parity storage overhead is about the lowest possible. The parity encoding and decoding are faster than for any other candidate coding we are aware of. We present our scheme and its performance analysis, including experiments with a prototype implementation on Wintel PCs. The capabilities of LH*
RS
offer new perspectives to data intensive applications, including the emerging ones of grids and of P2P computing.
Proof nets for unit-free multiplicative-additive linear logic
Authors: Hughes Dominic J. D. , Van Glabbeek Rob J.
Published: November 2005

A cornerstone of the theory of proof nets for unit-free multiplicative linear logic (MLL) is the abstract representation of cut-free proofs modulo inessential rule commutation. The only known extension to additives, based on monomial weights, fails to preserve this key feature: a host of cut-free monomial proof nets can correspond to the same cut-free proof. Thus, the problem of finding a satisfactory notion of proof net for unit-free multiplicative-additive linear logic (MALL) has remained open since the inception of linear logic in 1986. We present a new definition of MALL proof net which remains faithful to the cornerstone of the MLL theory.
News 2.0
Authors: Maurer Jim
Published: November 2005

IBM recently announced that it would discontinue support for its once-flagship operating system, OS/2, beginning in late 2006. Developed in the 1980s during an early alliance with Microsoft, OS/2 eventually became OS/2 Warp and had some success during the ’90s, particularly in the server market. But its desktop counterpart failed to take off, and IBM eventually ceded victory to Microsoft. IBM is now urging OS/2 users to switch to Linux, which it supports. Switch to Linux? If only it were that easy. Though gone from the spotlight, OS/2 continues to run on servers around the globe, especially on those linked to ATMs. Accordingly, there remains an active community of OS/2 users, many of whom believe that OS/2 is superior to more popular alternatives in some areas (e.g., security, file system). Emblematic of this support is a petition recently signed by nearly 10,000 OS/2 users, urging IBM to make OS/2 open source.
KV the Konqueror
Authors: Neville-Neil George
Published: November 2005

Suppose I’m a customer of Sincere-and-Authentic’s (“Kode Vicious Battles On,” April 2005:15-17), and suppose the sysadmin at my ISP is an unscrupulous, albeit music-loving, geek. He figured out that I have an account with Sincere-and-Authentic. He put in a filter in the access router to log all packets belonging to a session between me and S&A. He would later mine the logs and retrieve the music—without paying for it.
A Conversation with Roger Sessions and Terry Coatta
Authors: Maurer Jim
Published: November 2005

In the December/January 2004-2005 issue of Queue, Roger Sessions set off some fireworks with his article about objects, components, and Web services and which should be used when (“Fuzzy Boundaries,” 40-47). Sessions is on the board of directors of the International Association of Software Architects, the author of six books, writes the Architect Technology Advisory, and is CEO of ObjectWatch. He has a very object-oriented viewpoint, not necessarily shared by Queue editorial board member Terry Coatta, who disagreed with much of what Sessions had to say in his article. Coatta is an active developer who has worked extensively with component frameworks. He is vice president of products and strategy at Silicon Chalk, a startup software company in Vancouver, British Columbia. Silicon Chalk makes extensive use of Microsoft COM for building its application. Coatta previously worked at Open Text, where he architected CORBA-based infrastructures to support the company’s enterprise products.
The Future of Microprocessors
Authors: Olukotun Kunle , Hammond Lance
Published: November 2005

The performance of microprocessors that power modern computers has continued to increase exponentially over the years for two main reasons. First, the transistors that are the heart of the circuits in all processors and memory chips have simply become faster over time on a course described by Moore’s law, and this directly affects the performance of processors built with those transistors. Moreover, actual processor performance has increased faster than Moore’s law would predict, because processor designers have been able to harness the increasing numbers of transistors available on modern chips to extract more parallelism from software.
The Price of Performance
Authors: Barroso Luiz André
Published: November 2005

In the late 1990s, our research group at DEC was one of a growing number of teams advocating the CMP (chip multiprocessor) as an alternative to highly complex single-threaded CPUs. We were designing the Piranha system,1 which was a radical point in the CMP design space in that we used very simple cores (similar to the early RISC designs of the late ’80s) to provide a higher level of thread-level parallelism. Our main goal was to achieve the best commercial workload performance for a given silicon budget. Today, in developing Google’s computing infrastructure, our focus is broader than performance alone. The merits of a particular architecture are measured by answering the following question: Are you able to afford the computational capacity you need? The high-computational demands that are inherent in most of Google’s services have led us to develop a deep understanding of the overall cost of computing, and continually to look for hardware/software designs that optimize performance per unit of cost.
Software and the Concurrency Revolution
Authors: Sutter Herb , Larus James
Published: November 2005

Concurrency has long been touted as the "next big thing" and "the way of the future," but for the past 30 years, mainstream software development has been able to ignore it. Our parallel future has finally arrived: new machines will be parallel machines, and this will require major changes in the way we develop software. The introductory article in this issue describes the hardware imperatives behind this shift in computer architecture from uniprocessors to multicore processors, also known as CMPs.
Multicore CPUs for the Masses
Authors: Creeger Mache
Published: November 2005

Multicore is the new hot topic in the latest round of CPUs from Intel, AMD, Sun, etc. With clock speed increases becoming more and more difficult to achieve, vendors have turned to multicore CPUs as the best way to gain additional performance. Customers are excited about the promise of more performance through parallel processors for the same real estate investment.
The story of moose
Authors: Nierstrasz Oscar , Ducasse Stéphane , Gǐrba Tudor
Published: November 2005

MOOSE is a language-independent environment for reverse- and re-engineering complex software systems. MOOSE provides a set of services including a common meta-model, metrics evaluation and visualization, a model repository, and generic GUI support for querying, browsing and grouping. The development effort invested in MOOSE has paid off in precisely those research activities that benefit from applying a
combination
of complementary techniques. We describe how MOOSE has evolved over the years, we draw a number of lessons learned from our experience, and we outline the present and future of MOOSE.
Innovations in pervasive computing
Authors: Camara António S.
Published: November 2005

Pervasive computing is a broad term that may have different meanings. In this talk, we will focus on its ubiquitous and persistent dimensions. Fundamental methods and conventional applications of pervasive computing are briefly reviewed considering the most common technologies (hardware and software) and user interfaces.Two innovative applications of pervasive computing are presented: Undercover2, a persistent world location based multi-player mobile game; and L-INK, a ubiquitous computing application based on photo-chemical principles.Undercover2 is an application that shows how to mix virtual and real worlds in a mobile environment. The design of its interface, game engine, messaging, positioning and billing system is described herein. Future developments of the game and related applications derived from the current market experience are also discussed.L-INK is an application where one attempts to escape traditional computation by either pre-programming or triggering a chain of photo-chemical reactions. One can then visualize the computing efforts in non-electronic surfaces such as textiles, wood and paper. L-INK is limited to pictorial calculus formulations. With this approach, images are not decoded numerically or verbally. It is shown that these formulations may be sufficient for a broad range of applications. They include interactive T-shirts, tables and paper maps.Innovation is invention translated into products that the consumer is willing to pay. The management of this translation for Undercover and L-INK, two pioneer applications of pervasive computing, is paradigmatic of the challenges facing a spin-off from university research. The log of the events that went from early brainstorms to products available in the market is presented for illustrative purposes.
Engineering distributed software
Authors: Kramer Jeff , Magee Jeff
Published: November 2005

The role of structure in specifying, designing, analysing, constructing and evolving software has been the central theme of our research in Distributed Software Engineering. This structural discipline dictates formalisms and techniques that are compositional, components that are context independent and systems that can be constructed and evolved incrementally. This extended abstract overviews our development of a structural approach to engineering distributed software and gives indications of our future work which moves from explicit to implicit structural specification. With the benefit of hindsight we attempt to give a "rational history" to our research.
Automatic generation of suggestions for program investigation
Authors: Robillard Martin P.
Published: November 2005

Before performing a modification task, a developer usually has to investigate the source code of a system to understand how to carry out the task. Discovering the code relevant to a change task is costly because it is an inherently human activity whose success depends on a large number of unpredictable factors, such as intuition and luck. Although studies have shown that effective developers tend to explore a program by following structural dependencies, no methodology is available to guide their navigation through the typically hundreds of dependency paths found in a non-trivial program. In this paper, we propose a technique to automatically propose and rank program elements that are potentially interesting to a developer investigating source code. Our technique is based on an analysis of the topology of structural dependencies in a program. It takes as input a set of program elements of interest to a developer and produces a fuzzy set describing other elements of potential interest. Empirical evaluation of our technique indicates that it can help developers quickly select program elements worthy of investigation while avoiding less interesting ones.
ASTEC
Authors: McCloskey Bill , Brewer Eric
Published: November 2005

The C language is among the most widely used in the world, particularly for critical infrastructure software. C programs depend upon macros processed using the C preprocessor, but these macros are difficult to analyze and are often error-prone[4]. Existing tools that analyze and transform C source code have rudimentary support for the preprocessor, leading to obscure error messages and difficulty refactoring. We present a three part solution: (1) a replacement macro language, ASTEC, that addresses the most important important deficiencies of the preprocessor and that eliminates many of the errors it introduces; (2) a translator, MACROSCOPE, that converts existing code into ASTEC semi-automatically; and (3), an ASTEC-aware refactoring tool that handles preprocessor constructs naturally.ASTEC's primary benefits are its analyzability and its refactorability. We present several refactorings that are enabled by ASTEC. Additionally, ASTEC eliminates many of the sources of errors that can plague C preprocessor macros; Ernst et al.[4] estimate that more than 20% of macros may contain errors. In this paper, we describe our translation and refactoring tools and evaluate them on a suite of programs including OpenSSH and the Linux kernel.
Fluent temporal logic for discrete-time event-based models
Authors: Letier Emmanuel , Kramer Jeff , Magee Jeff , Uchitel Sebastian
Published: November 2005

Fluent model checking is an automated technique for verifying that an event-based operational model satisfies some state-based declarative properties. The link between the event-based and state-based formalisms is defined through "fluents" which are state predicates whose value are determined by the occurrences of initiating and terminating events that make the fluents values become true or false, respectively.The existing fluent temporal logic is convenient for reasoning about untimed event-based models but difficult to use for timed models. The paper extends fluent temporal logic with temporal operators for modelling timed properties of discrete-time event-based models. It presents two approaches that differ on whether the properties model the system state after the occurrence of each event or at a fixed time rate. Model checking of timed properties is made possible by translating them into the existing untimed framework.
Towards a unified formal model for supporting mechanisms of dynamic component update
Authors: Shen Junrong , Sun Xi , Huang Gang , Jiao Wenpin , Sun Yanchun , Mei Hong
Published: November 2005

The continuous requirements of evolving a delivered software system and the rising cost of shutting down a running software system are forcing researchers and practitioners to find ways of updating software as it runs. Dynamic update is a kind of software evolution that updates a running program without interruption. This paper covers the fundamental issues of the mechanisms of dynamic update theoretically. Based on a similarity analysis of many typical approaches to dynamic update during the past decades, we propose a unified formal model (namely, Dynamic Update Connector) to specify mechanisms of updating an architectural component, and reason about its properties. The model borrows the concept of connectors from software architecture community and is specified using process algebra CSP. We also demonstrate the applications of our DUC model.
Arithmetic program paths
Authors: Renieris Manos , Ramaprasad Shashank , Reiss Steven P.
Published: November 2005

We present Arithmetic Program Paths, a novel, efficient way to compress program control-flow traces that reduces program bit traces to less than a fifth of their original size while being fast and memory efficient. In addition, our method supports online, selective tracing and compression of individual conditionals, trading off memory usage and compression rate. We achieve these properties by recording only the directions taken by conditional statements during program execution, and using arithmetic coding for compression. We provide the arithmetic coder with a probability distribution for each conditional that we obtain using branch prediction techniques. We implemented the technique and experimented on several SPEC 2000 programs. Our method matches the compression rate of state-of-the-art tools while being an order of magnitude faster.
Moose
Authors: Ducasse Stéphane , Gîrba Tudor , Nierstrasz Oscar
Published: November 2005

Software systems are complex and difficult to analyze. Reengineering is a complex activity that usually involves combining different techniques and tools. MOOSE is an reengineering environment designed to provide the necessary infrastructure for building new tools and for integrating them. MOOSE centers on a language independent meta-model, and offers services like grouping, querying, navigation, and meta-descriptions. Several tools have been built on top of MOOSE dealing with different aspects of reengineering like: visualization, evolution analysis, semantic analysis, concept analysis or dynamic analysis.
Dynamically discovering architectures with DiscoTect
Authors: Schmerl Bradley , Garlan David , Yan Hong
Published: November 2005

One of the challenges for software architects is ensuring that an implemented system faithfully represents its architecture. We describe and demonstrate a tool, called DiscoTect, that addresses this challenge by dynamically monitoring a running system and deriving the software architecture as that system runs. The derivation process is based on mappings that relate low level system-level events to higher-level architectural events. The resulting architecture is then fed into existing architectural design tools so that comparisons can be conducted with the design time architecture and architectural analyses can be re-run to ensure that they are still valid. In addition to the demonstration, we briefly describe the mapping language and formal definition of the language in terms of Colored Petri Nets.
HATARI
Authors: Śliwerski Jacek , Zimmermann Thomas , Zeller Andreas
Published: November 2005

As a software system evolves, programmers make changes which sometimes lead to problems. The risk of later problems significantly depends on the location of the change. Which are the locations where changes impose the greatest risk? Our HATARI prototype relates a version history (such as CVS) to a bug database (such as BUGZILLA) to detect those locations where changes have been risky in the past. HATARI makes this risk visible for developers by annotating source code with color bars. Furthermore, HATARI provides views to browse through the most risky locations and to analyze the risk history of a particular location.
CHARMY
Authors: Inverardi Paola , Muccini Henry , Pelliccione Patrizio
Published: November 2005

CHARMY is a framework for designing and validating architectural specifications. In the early stages of the software development process, the CHARMY framework assists the software architect in the design and validation phases. To increase its usability in an industrial context, the tool allows the use of UML-like notations to graphically design the system. Once the design is done, a formal prototype is automatically created for simulation and analysis purposes. The framework provides extensibility mechanisms to enable the introduction of new design and analysis features.
Context- and path-sensitive memory leak detection
Authors: Xie Yichen , Aiken Alex
Published: November 2005

We present a context- and path-sensitive algorithm for detecting memory leaks in programs with explicit memory management. Our leak detection algorithm is based on an underlying escape analysis: any allocated location in a procedure
P
that is not deallocated in
P
and does not escape from
P
is leaked. We achieve very precise context- and path-sensitivity by expressing our analysis using boolean constraints. In experiments with six large open source projects our analysis produced 510 warnings of which 455 were unique memory leaks, a false positive rate of only 10.8%. A parallel implementation improves performance by over an order of magnitude on large projects; over five million lines of code in the Linux kernel is analyzed in 50 minutes.
Performance data collection using a hybrid approach
Authors: Metz Edu , Lencevicius Raimondas , Gonzalez Teofilo F.
Published: November 2005

Performance profiling consists of monitoring a software system during execution and then analyzing the obtained data. There are two ways to collect profiling data: event tracing through code instrumentation and statistical sampling. These two approaches have different advantages and drawbacks. This paper proposes a hybrid approach to data collection that combines the completeness of event tracing with the low cost of statistical sampling. We propose to maximize the weighted amount of information obtained during data collection, show that such maximization can be performed in linear time or is NP-hard depending on the data collected and the collection implementation. We propose an approximation algorithm for NP-hard case. Our paper also presents an application of the formal approach to an example use case.
Summarizing application performance from a components perspective
Authors: Srinivas Kavitha , Srinivasan Harini
Published: November 2005

In the era of distributed development, it is common for large applications to be assembled from multiple component layers that are developed by different development teams. Layered applications have deep call paths and numerous invocations (average call stack depth of up to 75, and upto 35 million invocations in the applications we studied) making summarization of performance problems a critical issue. Summarization of performance by classes, methods, invocations or packages is usually inadequate because they are often at the wrong level of granularity. We propose a technique that uses thresholding and filtering to identify a small set of interesting method invocations in components deemed interesting by the user. We show the utility of this technique with a set of 7 real-life applications, where the technique was used to identify a small set (10-93) of expensive invocations which accounted for 82-99% of the overall performance costs of the application. Our experience shows that this type of characterization can help quickly isolate the specific parts of a large system that can benefit most from performance tuning.
Applying classification techniques to remotely-collected program execution data
Authors: Haran Murali , Karr Alan , Orso Alessandro , Porter Adam , Sanil Ashish
Published: November 2005

There is an increasing interest in techniques that support measurement and analysis of fielded software systems. One of the main goals of these techniques is to better understand how software actually behaves in the field. In particular, many of these techniques require a way to distinguish, in the field, failing from passing executions. So far, researchers and practitioners have only partially addressed this problem: they have simply assumed that program failure status is either obvious (i.e., the program crashes) or provided by an external source (e.g., the users). In this paper, we propose a technique for automatically classifying execution data, collected in the field, as coming from either passing or failing program runs. (Failing program runs are executions that terminate with a failure, such as a wrong outcome.) We use statistical learning algorithms to build the classification models. Our approach builds the models by analyzing executions performed in a controlled environment (e.g., test cases run in-house) and then uses the models to predict whether execution data produced by a fielded instance were generated by a passing or failing program execution. We also present results from an initial feasibility study, based on multiple versions of a software subject, in which we investigate several issues vital to the applicability of the technique. Finally, we present some lessons learned regarding the interplay between the reliability of classification models and the amount and type of data collected.
Information hiding interfaces for aspect-oriented design
Authors: Sullivan Kevin , Griswold William G. , Song Yuanyuan , Cai Yuanfang , Shonle Macneil , Tewari Nishit , Rajan Hridesh
Published: November 2005

The growing popularity of aspect-oriented languages, such as AspectJ, and of corresponding design approaches, makes it important to learn how best to modularize programs in which aspect-oriented composition mechanisms are used. We contribute an approach to information hiding modularity in programs that use
quantified advising
as a module composition mechanism. Our approach rests on a new kind of interface: one that abstracts a crosscutting behavior, decouples the design of code that advises such a behavior from the design of the code to be advised, and that can stipulate behavioral contracts. Our interfaces establish
design rules
that govern how specific points in program execution are exposed through a given join point model and how conforming code on either side should behave. In a case study of the HyperCast overlay network middleware system, including a real options analysis, we compare the widely cited
oblivious
design approach with our own, showing significant weaknesses in the former and benefits in the latter.
Facilitating software evolution research with kenyon
Authors: Bevan Jennifer , Whitehead E. James , Kim Sunghun , Godfrey Michael
Published: November 2005

Software evolution research inherently has several resource-intensive logistical constraints. Archived project artifacts, such as those found in source code repositories and bug tracking systems, are the principal source of input data. Analysis-specific facts, such as commit metadata or the location of design patterns within the code, must be extracted for each change or configuration of interest. The results of this resource-intensive "fact extraction" phase must be stored efficiently, for later use by more experimental types of research tasks, such as algorithm or model refinement. In order to perform any type of software evolution research, each of these logistical issues must be addressed and an implementation to manage it created. In this paper, we introduce Kenyon, a system designed to facilitate software evolution research by providing a common set of solutions to these common logistical problems. We have used Kenyon for processing source code data from 12 systems of varying sizes and domains, archived in 3 different types of software configuration management systems. We present our experiences using Kenyon with these systems, and also describe Kenyon's usage by students in a graduate seminar class.