bluuebunny/crossref_metadata_2025 huggingface dataset:
Fast hash table lookup using extended bloom filter
Authors: Song Haoyu , Dharmapurikar Sarang , Turner Jonathan , Lockwood John
Published: November 2005

Hash tables are fundamental components of several network processing algorithms and applications, including route lookup, packet classification, per-flow state management and network monitoring. These applications, which typically occur in the data-path of high-speed routers, must process and forward packets with little or no buffer, making it important to maintain wire-speed throughout. A poorly designed hash table can critically affect the worst-case throughput of an application, since the number of memory accesses required for each lookup can vary. Hence, high throughput applications require hash tables with more predictable worst-case lookup performance. While published papers often assume that hash table lookups take constant time, there is significant variation in the number of items that must be accessed in a typical hash table search, leading to search times that vary by a factor of four or more.We present a novel hash table data structure and lookup algorithm which improves the performance over a naive hash table by reducing the number of memory accesses needed for the most time-consuming lookups. This allows designers to achieve higher lookup performance for a given memory bandwidth, without requiring large amounts of buffering in front of the lookup engine. Our algorithm extends the multiple-hashing Bloom Filter data structure to support exact matches and exploits recent advances in embedded memory technology. Through a combination of analysis and simulations we show that our algorithm is significantly faster than a naive hash table using the same amount of memory, hence it can support better throughput for router applications that use hash tables.
Rigorous specification and conformance testing techniques for network protocols, as applied to TCP, UDP, and sockets
Authors: Bishop Steve , Fairbairn Matthew , Norrish Michael , Sewell Peter , Smith Michael , Wansbrough Keith
Published: November 2005

Network protocols are hard to implement correctly. Despite the existence of RFCs and other standards, implementations often have subtle differences and bugs. One reason for this is that the specifications are typically informal, and hence inevitably contain ambiguities. Conformance testing against such specifications is challenging.In this paper we present a practical technique for rigorous protocol specification that supports specification-based testing. We have applied it to TCP, UDP, and the Sockets API, developing a detailed 'post-hoc' specification that accurately reflects the behaviour of several existing implementations (FreeBSD 4.6, Linux 2.4.20-8, and Windows XP SP1). The development process uncovered a number of differences between and infelicities in these implementations.Our experience shows for the first time that rigorous specification is feasible for protocols as complex as TCP@. We argue that the technique is also applicable 'pre-hoc', in the design phase of new protocols. We discuss how such a design-for-test approach should influence protocol development, leading to protocol specifications that are both unambiguous and clear, and to high-quality implementations that can be tested directly against those specifications.
Declarative routing
Authors: Loo Boon Thau , Hellerstein Joseph M. , Stoica Ion , Ramakrishnan Raghu
Published: November 2005

The Internet's core routing infrastructure, while arguably robust and efficient, has proven to be difficult to evolve to accommodate the needs of new applications. Prior research on this problem has included new hard-coded routing protocols on the one hand, and fully extensible Active Networks on the other. In this paper, we explore a new point in this design space that aims to strike a better balance between the extensibility and robustness of a routing infrastructure. The basic idea of our solution, which we call
declarative routing
, is to express routing protocols using a database query language. We show that our query language is a natural fit for routing, and can express a variety of well-known routing protocols in a compact and clean fashion. We discuss the security of our proposal in terms of its computational expressive power and language design. Via simulation, and deployment on PlanetLab, we demonstrate that our system imposes no fundamental limits relative to traditional protocols, is amenable to query optimizations, and can sustain long-lived routes under network churn and congestion.
Generalized multidimensional data mapping and query processing
Authors: Zhang Rui , Kalnis Panos , Ooi Beng Chin , Tan Kian-Lee
Published: November 2005

Multidimensional data points can be mapped to one-dimensional space to exploit single dimensional indexing structures such as the B
+
-tree. In this article we present a Generalized structure for data Mapping and query Processing (GiMP), which supports extensible mapping methods and query processing. GiMP can be easily customized to behave like many competent indexing mechanisms for multi-dimensional indexing, such as the UB-Tree, the Pyramid technique, the iMinMax, and the iDistance. Besides being an extendible indexing structure, GiMP also serves as a framework to study the characteristics of the mapping and hence the efficiency of the indexing scheme. Specifically, we introduce a metric called
mapping redundancy
to characterize the efficiency of a mapping method in terms of disk page accesses and analyze its behavior for point, range and kNN queries. We also address the fundamental problem of whether an efficient mapping exists and how to define such a mapping for a given data set.
Self-tuning cost modeling of user-defined functions in an object-relational DBMS
Authors: He Zhen , Lee Byung Suk , Snapp Robert
Published: November 2005

Query optimizers in object-relational database management systems typically require users to provide the execution cost models of user-defined functions (UDFs). Despite this need, however, there has been little work done to provide such a model. The existing approaches are static in that they require users to train the model a priori with pregenerated UDF execution cost data. Static approaches can not adapt to changing UDF execution patterns and thus degrade in accuracy when the UDF executions used for generating training data do not reflect the patterns of those performed during operation. This article proposes a new approach based on the recent trend of self-tuning DBMS by which the cost model is maintained dynamically and incrementally as UDFs are being executed online. In the context of UDF cost modeling, our approach faces a number of challenges, that is, it should work with limited memory, work with limited computation time, and adjust to the fluctuations in the execution costs (e.g., caching effect). In this article, we first provide a set of guidelines for developing techniques that meet these challenges, while achieving accurate and fast cost prediction with small overheads. Then, we present two concrete techniques developed under the guidelines. One is an instance-based technique based on the conventionalk-nearest neighbor (KNN) technique which uses a multidimensional index like the R*-tree. The other is a summary-based technique which uses the quadtree to store summary values at multiple resolutions. We have performed extensive performance evaluations comparing these two techniques against existing histogram-based techniques and the KNN technique, using both real and synthetic UDFs/data sets. The results show our techniques provide better performance in most situations considered.
Capturing summarizability with integrity constraints in OLAP
Authors: Hurtado Carlos A. , Gutierrez Claudio , Mendelzon Alberto O.
Published: November 2005

In multidimensional data models intended for online analytic processing (OLAP), data are viewed as points in a multidimensional space. Each dimension has structure, described by a directed graph of categories, a set of members for each category, and a child/parent relation between members. An important application of this structure is to use it to infer summarizability, that is, whether an aggregate view defined for some category can be correctly derived from a set of precomputed views defined for other categories. A dimension is called
structurally heterogeneous
if two members in a given category are allowed to have ancestors in different categories. In this article, we propose a class of integrity constraints,
dimension constraints
, that allow us to reason about summarizability in heterogeneous dimensions. We introduce the notion of frozen dimensions which are minimal homogeneous dimension instances representing the different structures that are implicitly combined in a heterogeneous dimension. Frozen dimensions provide the basis for efficiently testing the implication of dimension constraints and are a useful aid to understanding heterogeneous dimensions. We give a sound and complete algorithm for solving the implication of dimension constraints that uses heuristics based on the structure of the dimension and the constraints to speed up its execution. We study the intrinsic complexity of the implication problem and the running time of our algorithm.
Automatic linear orders and trees
Authors: Khoussainov Bakhadyr , Rubin Sasha , Stephan Frank
Published: November 2005

We investigate partial orders that are computable, in a precise sense, by finite automata. Our emphasis is on trees and linear orders. We study the relationship between automatic linear orders and trees in terms of rank functions that are related to Cantor--Bendixson rank. We prove that automatic linear orders and automatic trees have finite rank. As an application we provide a procedure for deciding the isomorphism problem for automatic ordinals. We also investigate the complexity and definability of infinite paths in automatic trees. In particular, we show that every infinite path in an automatic tree with countably many infinite paths is a regular language.
About the undecidability of program equivalence in finitary languages with state
Authors: Murawski Andrzej S.
Published: November 2005

We show how game semantics can be employed to prove that program equivalence in finitary Idealized Algol with active expressions is undecidable. We also investigate a notion of representability of languages by terms and show that finitary Idealized Algol terms of respectively second, third and higher orders define exactly regular, context-free and recursively enumerable languages.
Convergence law for random graphs with specified degree sequence
Authors: Lynch James F.
Published: November 2005

The degree sequence of an
n
-vertex graph is
d
0
,…,
d

n
−1

, where each
d

i

is the number of vertices of degree
i
in the graph. A random graph with degree sequence
d
0
,…,
d

n
−1

is a randomly selected member of the set of graphs on {1,…,
n
} with that degree sequence, all choices being equally likely. Let λ
0
,λ
1
,… be a sequence of nonnegative reals summing to 1. A class of finite graphs has degree sequences approximated by λ
0
,λ
1
,… if, for every
i
and
n
, the members of the class of size
n
have λ

i

n
+
o(n)
vertices of degree
i
. Our main result is a convergence law for random graphs with degree sequences approximated by some sequence λ
0
,λ
1
,…. With certain conditions on the sequence λ
0
,λ
1
,…, the probability of any first-order sentence on random graphs of size
n
converges to a limit as
n
grows.
A proof theory for generic judgments
Authors: Miller Dale , Tiu Alwen
Published: November 2005

The operational semantics of a computation system is often presented as inference rules or, equivalently, as logical theories. Specifications can be made more declarative and high level if syntactic details concerning bound variables and substitutions are encoded directly into the logic using term-level abstractions (λ-abstraction) and proof-level abstractions (eigenvariables). When one wishes to use such logical theories to support reasoning about properties of computation, the usual quantifiers and proof-level abstractions do not seem adequate: proof-level abstraction of variables with scope over sequents (
global
scope) as well as over only formulas (
local
scope) seem required for many examples. We will present a sequent calculus that provides this local notion of proof-level abstraction via
generic judgment
and a new quantifier, ∇, which explicitly manipulates such local scope. Intuitionistic logic extended with ∇ satisfies cut-elimination even when the logic is additionally strengthened with a proof theoretic notion of definitions. The resulting logic can be used to encode naturally a number of examples involving abstractions, and we illustrate the uses of ∇ with the π-calculus and an encoding of provability of an object-logic.
What’s on Your Hard Drive?
Authors: Maurer Jim
Published: November 2005

Tool I love! Python. I?m still a newbie to Python but I?m quite impressed with it thus far. As a scripting language, it can quickly test an idea or an algorithm, even if the project I?m working on doesn?t use Python. Also, with free tools such as wxPython and py2exe, a Python script can easily become a full-blown distributable application with a robust UI.
Extreme Software Scaling
Authors: McDougall Richard
Published: November 2005

The advent of SMP (symmetric multiprocessing) added a new degree of scalability to computer systems. Rather than deriving additional performance from an incrementally faster microprocessor, an SMP system leverages multiple processors to obtain large gains in total system performance. Parallelism in software allows multiple jobs to execute concurrently on the system, increasing system throughput accordingly. Given sufficient software parallelism, these systems have proved to scale to several hundred processors.
Permissive interfaces
Authors: Henzinger Thomas A. , Jhala Ranjit , Majumdar Rupak
Published: November 2005

A modular program analysis considers components independently and provides a succinct summary for each component, which is used when checking the rest of the system. Consider a system consisting of a library and a client. A temporal summary, or
interface
, of the library specifies legal sequences of library calls. The interface is
safe
if no call sequence violates the library's internal invariants; the interface is
permissive
if it contains every such sequence. Modular program analysis requires
full
interfaces, which are both safe and permissive: the client does not cause errors in the library if and only if it makes only sequences of library calls that are allowed by the full interface of the library.Previous interface-based methods have focused on safe interfaces, which may be too restrictive and thus reject good clients. We present an algorithm for automatically synthesizing software interfaces that are both safe and permissive. The algorithm generates interfaces as graphs whose vertices are labeled with predicates over the library's internal state, and whose edges are labeled with library calls. The interface state is refined incrementally until the full interface is constructed. In other words, the algorithm automatically synthesizes a typestate system for the library, against which any client can be checked for compatibility. We present an implementation of the algorithm which is based on the BLAST model checker, and we evaluate some case studies.
Detecting higher-level similarity patterns in programs
Authors: Basit Hamid Abdul , Jarzabek Stan
Published: November 2005

Cloning in software systems is known to create problems during software maintenance. Several techniques have been proposed to detect the same or similar code fragments in software, so-calledsimple clones. While the knowledge of simple clones is useful, detecting design-level similarities in software could ease maintenance even further, and also help us identify reuse opportunities. We observed that recurring patterns of simple clones - so-calledstructural clones- often indicate the presence of interesting design-level similarities. An example would be patterns of collaborating classes or components. Finding structural clones that signify potentially useful design information requires efficient techniques to analyze the bulk of simple clone data and making non-trivial inferences based on the abstracted information. In this paper, we describe a practical solution to the problem of detecting some basic, but useful, types of design-level similarities such as groups of highly similar classes or files. First, we detect simple clones by applying conventional token-based techniques. Then we find the patterns of co-occurring clones in different files using the Frequent Itemset Mining (FIM) technique. Finally, we perform file clustering to detect those clusters of highly similar files that are likely to contribute to a design-level similarity pattern. The novelty of our approach is application of data mining techniques to detect design level similarities. Experiments confirmed that our method finds many useful structural clones and scales up to big programs. The paper describes our method for structural clone detection, a prototype tool called Clone Miner that implements the method and experimental results.
Relational analysis of algebraic datatypes
Authors: Kuncak Viktor , Jackson Daniel
Published: November 2005

We present a technique that enables the use of finite model finding to check the satisfiability of certain formulas whose intended models are infinite. Such formulas arise when using the language of sets and relations to reason about structured values such as algebraic datatypes. The key idea of our technique is to identify a natural syntactic class of formulas in relational logic for which reasoning about infinite structures can be reduced to reasoning about finite structures. As a result, when a formula belongs to this class, we can use existing finite model finding tools to check whether the formula holds in the desired infinite model.
Parameterized unit tests
Authors: Tillmann Nikolai , Schulte Wolfram
Published: November 2005

Parameterized unit tests extend the current industry practice of using closed unit tests defined as parameterless methods. Parameterized unit tests separate two concerns: 1) They specify the external behavior of the involved methods for all test arguments. 2) Test cases can be re-obtained as traditional closed unit tests by instantiating the parameterized unit tests. Symbolic execution and constraint solving can be used to automatically choose a minimal set of inputs that exercise a parameterized unit test with respect to possible code paths of the implementation. In addition, parameterized unit tests can be used as symbolic summaries which allows symbolic execution to scale for arbitrary abstraction levels. We have developed a prototype tool which computes test cases from parameterized unit tests. We report on its first use testing parts of the .NET base class library.
SOBER
Authors: Liu Chao , Yan Xifeng , Fei Long , Han Jiawei , Midkiff Samuel P.
Published: November 2005

Automated localization of software bugs is one of the essential issues in debugging aids. Previous studies indicated that the evaluation history of program predicates may disclose important clues about underlying bugs. In this paper, we propose a new statistical model-based approach, called SOBER, which localizes software bugs without any prior knowledge of program semantics. Unlike existing
statistical debugging
approaches that select predicates correlated with program failures, SOBER models evaluation patterns of predicates in both correct and incorrect runs respectively and regards a predicate as bug-relevant if its evaluation pattern in incorrect runs differs significantly from that in correct ones. SOBER features a principled quantification of the pattern difference that measures the bug-relevance of program predicates.We systematically evaluated our approach under the same setting as previous studies. The result demonstrated the power of our approach in bug localization: SOBER can help programmers locate 68 out of 130 bugs in the Siemens suite when programmers are expected to examine no more than 10% of the code, whereas the best previously reported is 52 out of 130. Moreover, with the assistance of SOBER, we found two bugs in bc 1.06 (an arbitrary precision calculator on UNIX/Linux), one of which has never been reported before.
DynaMine
Authors: Livshits Benjamin , Zimmermann Thomas
Published: November 2005

A great deal of attention has lately been given to addressing software bugs such as errors in operating system drivers or security bugs. However, there are many other lesser known errors specific to individual applications or APIs and these violations of application-specific coding rules are responsible for a multitude of errors. In this paper we propose DynaMine, a tool that analyzes source code check-ins to find highly correlated method calls as well as common bug fixes in order to automatically discover application-specific coding patterns. Potential patterns discovered through mining are passed to a dynamic analysis tool for validation; finally, the results of dynamic analysis are presented to the user.The combination of revision history mining and dynamic analysis techniques leveraged in DynaMine proves effective for both discovering new application-specific patterns
and
for finding errors when applied to very large applications with many man-years of development and debugging effort behind them. We have analyzed Eclipse and jEdit, two widely-used, mature, highly extensible applications consisting of more than 3,600,000 lines of code combined. By mining revision histories, we have discovered 56 previously unknown, highly application-specific patterns. Out of these, 21 were dynamically confirmed as very likely valid patterns and a total of 263 pattern violations were found.
UPEX
Authors: Erfurth Ivonne , Rossak Wilhelm
Published: November 2005

The failure of projects is often based on difficulties in the direct and indirect communication between developer and customer teams. For the customer it is hard to understand the frequently used terms, process models, and technological concepts. Developers have a hard time to understand domain specific processes and structures, and exhibit a tendency to abstract concrete examples to higher level constructs. This makes it difficult for the customer team to understand the developing architecture and processes, and to match their needs and intentions, during evaluation phases, to seemingly unrelated generalised drawings and specifications. This set of problems is especially hard to avoid during the development of dynamic, distributed systems with multiple nodes and possibly asynchronous behaviour.Our research tries to mediate in this conflict by providing a customer-friendly reference model as basis of communication in early development phases. This model presents and simulates the dynamic aspects of (distributed) systems without immediate abstraction from examples and allows for a stepwise generalisation and evaluation with help of the customer team. In its final version the reference model will serve as a requirements statement for the professional developer.
A refinement calculus for software components and architectures
Authors: Barbosa Marco Antonio
Published: November 2005

The complexity and ubiquity achieved by software in the present world makes it imperative, more than ever, the availability of both technologies and sound methods to drive its development. Programming '
in--the--large
', component--based programming and software architecture are popular expressions which embody this concern and correspond to driving forces in current software engineering. In such a context, this paper reports on the research, which constitutes the PhD project of the author, on a formal calculus for reasoning about and transforming component--based architectures.
Realising evidence-based software engineering a report from the workshop held at ICSE 2005
Authors: Budgen David , Kitchenham Barbara
Published: November 2005

Context:
The workshop was held to explore the potential for adapting the ideas of evidence-based practices as used in medicine and other disciplines for use in software engineering.
Objectives:
To devise ways of developing suitable evidence-based practices and procedures, especially the use of structured literature reviews, and introducing these into software engineering research and practice.
Method:
Three sessions were dedicated to a mix of presentations based on position papers and interactive discussion, while the fourth focused upon the key issues as decided by the participants.
Results:
An initial scoping of the major issues, identification of useful parallels, and some plans for future development of an evidence-based software engineering community.
Conclusions:
While there are substantial challenges to introducing evidence-based practices, there are useful experiences to be drawn from a variety of other domains.
Modeling biological systems
Authors: Darbari Manuj , Saxena Vipin
Published: November 2005

In this paper we demonstrate the relevance of abstraction, reuse, objects, classes, component and inheritance hierarchies, multiplicity, visual modeling, and other current software development best practices. We show how it is possible to start with a direct diagrammatic representation of a biological structure such as a cell, using terminology familiar to biologists, and by following a process of gradually adding more and more detail, arrive at a system with structure and behavior of arbitrary complexity that can run and be observed on a computer. We will be discussing various tools of UML used to describe biological modeling.
Some agent theory for the semantic web
Authors: Fass Leona F.
Published: November 2005

We take the position that for any goal achievable on the Semantic Web, there will be a "best" system of Web-dwelling software agents to realize that goal, and that such a system may be discovered effectively. The process of determining the "best" agent system may be overseen by a distinguished Manager Agent. But with realistic time and space constraints, and the dynamic nature of the Semantic Web, finding an approximating system may be acceptable. The approximation then may be adapted iteratively, to approach the ideal. We show that very practical researchers have looked at software agents and Semantic Web problems in a similar way, determining approximating sub-optimal systems and subsequently adapting them. Their applied research confirms that theory provides a good foundation for practice.
A word from the editor
Authors: Lee Newton
Published: November 2005

Welcome to ACM Computers in Entertainment, a unique magazine featuring video interviews with leading professionals and interesting articles on entertainment technology and its applications.
Anna Marie Piersimoni
Authors: Lee Newton
Published: November 2005

Anna Marie Piersimoni, our distinguished editorial board advisor, is Director of Internet Communications and Director of Media & Technology at the American Film Institute. Previously, as Director of Enhanced TV for the AFI, she developed the acclaimed AFIIntel Enhanced TV Workshop, a unique hands-on R&D training environment for television professionals in the production of new convergent media.
Foreword to special issue on music visualization
Authors: Chew Elaine
Published: November 2005

This special issue on music visualization focuses on the visual conveyance of music structural information through the automated analysis of digital music and the graphical rendering of its analytical forms. Music can be described as highly organized sounds that exhibit time-varying structures in the pitch (frequency) and time domains. When we listen to music, our minds group pitch structures into horizontal streams (such as melodies) and vertical bunches (such as chords and keys). These pitch collections create musical contexts that situate and orient our hearing of the music. It is the visualization of these time-varying pitch contexts that forms the common theme among the contributions in this special issue.In music-theoretic terms, all four articles are concerned with the tonal structure of music. Tonal structure emerges in music that is tonal, music for which the pattern of notes generates the perception of varying levels of stability amongst the pitches. The term "tonal" applies to almost all of the music that we hear. Computer systems for music visualization that automatically capture and display such structures will enable people to see, and better understand, the tonal patterns that they hear.The large-scale availability of music in digital format, coupled with the rapid increase in computational prowess, has made the automatic visual rendering of musical structure more accessible than ever. According to Jeremy Strick, one of the organizers of the Visual Music exhibit (2005) at the Los Angeles Museum of Contemporary Art and Hirshhorn Museum of the Smithsonian Institute, "In digital media, ... music and visual art truly are united, ... They are created out of the same stuff, bits of electronic information, infinitely interchangeable. ... the aspiration to novel experience created by the compounding of sensation and association has never been more possible" [Strick 2005, p.20]. Even though scientific visualizations of musical structure do not pretend to be fine art, the interlocking of visual and musical sensations featured in this collection similarly seeks to evoke what might be illusive mental associations between music and its analytical structures through visual mediation.
The geometry of musical structure
Authors: Krumhansl Carol L.
Published: November 2005

The purpose of this article is to provide a general introduction to the idea that musical structure can be represented geometrically. It begins by defining those elements that appear in the models in the three papers that follow. A brief review is given of psychological results demonstrating that these music-theoretic definitions describe implicit knowledge that listeners have of tonal-harmonic music. This is followed by a brief historical summary of maps that were proposed previously of keys, tones, and chords, and a hybrid tone-chord map. The article then summarizes a number of issues that arise in connection with geometric representations. Finally, the innovations in the three proposed models are highlighted, particularly their contributions to visualizing the dynamics and temporal relationships that exist in extended musical pieces.
Pioneer
Authors: Seshadri Arvind , Luk Mark , Shi Elaine , Perrig Adrian , van Doorn Leendert , Khosla Pradeep
Published: November 2005

We propose a primitive, called Pioneer, as a first step towards verifiable code execution on untrusted legacy hosts. Pioneer does not require any hardware support such as secure co-processors or CPU-architecture extensions. We implement Pioneer on an Intel Pentium IV Xeon processor. Pioneer can be used as a basic building block to build security systems. We demonstrate this by building a kernel rootkit detector.
Fault-scalable Byzantine fault-tolerant services
Authors: Abd-El-Malek Michael , Ganger Gregory R. , Goodson Garth R. , Reiter Michael K. , Wylie Jay J.
Published: November 2005

A
fault-scalable
service can be configured to tolerate increasing numbers of faults without significant decreases in performance. The Query/Update (Q/U) protocol is a new tool that enables construction of fault-scalable Byzantine fault-tolerant services. The optimistic quorum-based nature of the Q/U protocol allows it to provide better throughput and fault-scalability than replicated state machines using agreement-based protocols. A prototype service built using the Q/U protocol outperforms the same service built using a popular replicated state machine implementation at all system sizes in experiments that permit an optimistic execution. Moreover, the performance of the Q/U protocol decreases by only 36% as the number of Byzantine faults tolerated increases from one to five, whereas the performance of the replicated state machine decreases by 83%.
Capturing, indexing, clustering, and retrieving system history
Authors: Cohen Ira , Zhang Steve , Goldszmidt Moises , Symons Julie , Kelly Terence , Fox Armando
Published: November 2005

We present a method for automatically extracting from a running system an indexable
signature
that distills the essential characteristic from a system state and that can be subjected to automated clustering and similarity-based retrieval to identify when an observed system state is similar to a previously-observed state. This allows operators to identify and quantify the frequency of recurrent problems, to leverage previous diagnostic efforts, and to establish whether problems seen at different installations of the same site are similar or distinct. We show that the naive approach to constructing these signatures based on simply recording the actual ``raw'' values of collected measurements is ineffective, leading us to a more sophisticated approach based on statistical modeling and inference. Our method requires only that the system's metric of merit (such as average transaction response time) as well as a collection of lower-level operational metrics be collected, as is done by existing commercial monitoring tools. Even if the traces have no annotations of prior diagnoses of observed incidents (as is typical), our technique successfully clusters system states corresponding to similar problems, allowing diagnosticians to identify recurring problems and to characterize the ``syndrome'' of a group of problems. We validate our approach on both synthetic traces and several weeks of production traces from a customer-facing geoplexed 24 x 7 system; in the latter case, our approach identified a recurring problem that had required extensive manual diagnosis, and also aided the operators in correcting a previous misdiagnosis of a different problem.
Connections
Authors: Soules Craig A. N. , Ganger Gregory R.
Published: November 2005

Connections is a file system search tool that combines traditional content-based search with context information gathered from user activity. By tracing file system calls, Connections can identify temporal relationships between files and use them to expand and reorder traditional content search results. Doing so improves both recall (reducing false-positives) and precision (reducing false-negatives). For example, Connections improves the average recall (from 13% to 22%) and precision (from 23% to 29%) on the first ten results. When averaged across all recall levels, Connections improves precision from 17% to 28%. Connections provides these benefits with only modest increases in average query time (2 seconds), indexing time (23 seconds daily), and index size(under 1% of the user's data set).
Scalability, fidelity, and containment in the potemkin virtual honeyfarm
Authors: Vrable Michael , Ma Justin , Chen Jay , Moore David , Vandekieft Erik , Snoeren Alex C. , Voelker Geoffrey M. , Savage Stefan
Published: November 2005

The rapid evolution of large-scale worms, viruses and bot-nets have made Internet malware a pressing concern. Such infections are at the root of modern scourges including DDoS extortion, on-line identity theft, SPAM, phishing, and piracy. However, the most widely used tools for gathering intelligence on new malware -- network honeypots -- have forced investigators to choose between monitoring activity at a large scale or capturing behavior with high fidelity. In this paper, we describe an approach to minimize this tension and improve honeypot scalability by up to six orders of magnitude while still closely emulating the execution behavior of individual Internet hosts. We have built a prototype honeyfarm system, called
Potemkin
, that exploits virtual machines, aggressive memory sharing, and late binding of resources to achieve this goal. While still an immature implementation, Potemkin has emulated over 64,000 Internet honeypots in live test runs, using only a handful of physical servers.
IRON file systems
Authors: Prabhakaran Vijayan , Bairavasundaram Lakshmi N. , Agrawal Nitin , Gunawi Haryadi S. , Arpaci-Dusseau Andrea C. , Arpaci-Dusseau Remzi H.
Published: November 2005

Commodity file systems trust disks to either work or fail completely, yet modern disks exhibit more complex failure modes. We suggest a new
fail-partial failure model
for disks, which incorporates realistic localized faults such as latent sector errors and block corruption. We then develop and apply a novel
failure-policy fingerprinting
framework, to investigate how commodity file systems react to a range of more realistic disk failures. We classify their failure policies in a new taxonomy that measures their
Internal RObustNess (IRON)
, which includes both failure detection and recovery techniques. We show that commodity file system failure policies are often inconsistent, sometimes buggy, and generally inadequate in their ability to recover from partial disk failures. Finally, we design, implement, and evaluate a prototype
IRON
file system, Linux ixt3, showing that techniques such as in-disk checksumming, replication, and parity greatly enhance file system robustness while incurring minimal time and space overheads.
Learning to crawl
Authors: Pant Gautam , Srinivasan Padmini
Published: November 2005

Topical crawling is a young and creative area of research that holds the promise of benefiting from several sophisticated data mining techniques. The use of classification algorithms to guide topical crawlers has been sporadically suggested in the literature. No systematic study, however, has been done on their relative merits. Using the lessons learned from our previous crawler evaluation studies, we experiment with multiple versions of different classification schemes. The crawling process is modeled as a parallel best-first search over a graph defined by the Web. The classifiers provide heuristics to the crawler thus biasing it towards certain portions of the Web graph. Our results show that Naive Bayes is a weak choice for guiding a topical crawler when compared with Support Vector Machine or Neural Network. Further, the weak performance of Naive Bayes can be partly explained by extreme skewness of posterior probabilities generated by it. We also observe that despite similar performances, different topical crawlers cover subspaces on the Web with low overlap.
Feature-based multiresolution modeling of solids
Authors: Lee Sang Hun
Published: November 2005

Recently, three-dimensional CAD systems based on feature-based solid modeling techniques have been widely used for product design. However, when part models associated with features are used in various downstream applications, simplified models at various levels of detail (LODs) are frequently more desirable than the full details of the parts. One challenge is to generate valid models at various LODs after an arbitrary rearrangement of features using a certain LOD criterion, because composite Boolean operations consisting of union and subtraction are not commutative. This article proposes an algorithm for feature-based multiresolution solid modeling based on the effective volumes of features. This algorithm guarantees the same resulting shape and the reasonable intermediate LOD models for an arbitrary rearrangement of the features, regardless of whether feature types are additive or subtractive. This characteristic enables various LOD criteria to be used for a wide range of applications including computer-aided design and analysis.
A procedural object distribution function
Authors: Lagae Ares , Dutré Philip
Published: November 2005

In this article, we present a procedural object distribution function, a new texture basis function that distributes procedurally generated objects over a procedurally generated texture. The objects are distributed uniformly over the texture, and are guaranteed not to overlap. The scale, size, and orientation of the objects can be easily manipulated. The texture basis function is efficient to evaluate, and is suited for real-time applications. The new texturing primitive we present extends the range of textures that can be generated procedurally.The procedural object distribution function we propose is based on Poisson disk tiles and a direct stochastic tiling algorithm for Wang tiles. Poisson disk tiles are square tiles filled with a precomputed set of Poisson disk distributed points, inspired by Wang tiles. A single set of Poisson disk tiles enables the real-time generation of an infinite amount of Poisson disk distributions of arbitrary size. With the direct stochastic tiling algorithm, these Poisson disk distributions can be evaluated locally, at any position in the Euclidean plane.Poisson disk tiles and the direct stochastic tiling algorithm have many other applications in computer graphics. We briefly explore applications in object distribution, primitive distribution for illustration, and environment map sampling.
Detection and prevention of stack buffer overflow attacks
Authors: Kuperman Benjamin A. , Brodley Carla E. , Ozdoganoglu Hilmi , Vijaykumar T. N. , Jalote Ankit
Published: November 2005

How to mitigate remote attacks that exploit buffer overflow vulnerabilities on the stack and enable attackers to take control of the program.
Business email
Authors: Tassabehji Rana , Vakola Maria
Published: November 2005

Workplace email is quickly evolving to keep up with those who use it---and perhaps to make way for the next killer app.
Maintaining enterprise software applications
Authors: Mookerjee Radha
Published: November 2005

The problem of maintaining integrated applications is by no means a simple one and requires an interdisciplinary approach.
Crisis and opportunity in computer science
Authors: Klawe Maria , Shneiderman Ben
Published: November 2005

The future of the field depends on winning back student enrollment, public interest in technology, and government research funding.
The main name system
Authors: Deegan Tim , Crowcroft Jon , Warfield Andrew
Published: November 2005

Naming is a critical component of the internet architecture, and one whose complexity is often overlooked. As a global system, the DNS must satisfy millions of requests per second, while allowing distributed, delegated administration and maintenance. In this paper, we consider the design of the DNS and the widely distributed manner in which DNS records are published. We propose that the robustness and performance of the existing DNS could be dramatically improved by moving towards a centralized architecture while maintaining the existing client interface and delegated administration.
Design choices for content distribution in P2P networks
Authors: Al Hamra Anwar , Felber Pascal A.
Published: November 2005

Content distribution using the P2P paradigm has become one of the most dominant services in the Internet today. Most of the research effort in this area focuses on developing new distribution architectures. However, little work has gone into identifying the principle design choices that draw the behavior of the system. In this paper, we identify these design choices and show how they in uence the performance of different P2P architectures. For example, we discuss how clients should organize and cooperate in the network. We believe that our findings can serve as guidelines in the design of efficient future architectures.
An internet routing forensics framework for discovering rules of abnormal BGP events
Authors: Li Jun , Dou Dejing , Wu Zhen , Kim Shiwoong , Agarwal Vikash
Published: November 2005

Abnormal BGP events such as attacks, misconfigurations, electricity failures, can cause anomalous or pathological routing behavior at either global level or prefix level, and thus must be detected in their early stages. Instead of using ad hoc methods to analyze BGP data, in this paper we introduce an Internet Routing Forensics framework to systematically process BGP routing data, discover rules of abnormal BGP events, and apply these rules to detect the occurrences of these events. In particular, we leverage data mining techniques to train the framework to learn rules of abnormal BGP events, and our results from two case studies show that these rules are effective. In one case study, rules of worm events discovered from the BGP data during the outbreaks of the CodeRed and Nimda worms were able to successfully detect worm impact on BGP when an independent worm, the Slammer, subsequently occurred. Similarly, in another case study, rules of electricity blackout events obtained using BGP data from the 2003 East Coast blackout were able to detect the BGP impact from the Florida blackout caused by Hurricane Frances in 2004.
Simplifying the synthesis of internet traffic matrices
Authors: Roughan Matthew
Published: November 2005

A recent paper [8] presented methods for several steps along the road to synthesis of realistic traffic matrices. Such synthesis is needed because traffic matrices are a crucial input for testing many new networking algorithms, but traffic matrices themselves are generally kept secret by providers. Furthermore, even given traffic matrices from a real network, it is difficult to realistically adjust these to generate a range of scenarios (for instance for different network sizes). This note is concerned with the first step presented in [8]: generation of a matrix with similar statistics to that of a real traffic matrix. The method applied in [8] is based on fitting a large number of distributions, and finding that the log-normal distribution appears to fit most consistently. Best fits (without some intuitive explanation for the fit) are fraught with problems. How general are the results? How do the distribution parameters relate? This note presents a simpler approach based on a gravity model. Its simplicity provides us with a better understanding of the origins of the results of [8], and this insight is useful, particularly because it allows one to adapt the synthesis process to different scenarios in a more intuitive manner. Additionally, [8] measures the quality of its fit to the distribution's body. This note shows that the tails of the distributions are less heavy than the log-normal distribution (a counterintuitive result for Internet traffic), and that the gravity model replicates these tails more accurately.