Computer Sciences Commons^™

Finding Irc-Like Meshes Sans Layer 7 Payloads, Akshay Dua, Jim Binkley, Suresh Singh

Computer Science Faculty Publications and Presentations

We present an algorithm for detecting IRC-like chat networks that does not rely on Layer 7 payload information. The goal is to extract only those meshes from conventional flows where long-term periodic data is being exchanged between an external server and multiple internal clients. Flow data is passed through a series of filters that reduce the memory requirements needed for final candidate mesh sorting. Final outputs consist of two sorted lists including the fanout list, sorted by the number of client hosts in the mesh, and a secondary list called the evil sort. The latter consists of meshes with any …

Squeak By Example, Andrew P. Black, Stéphane Ducasse, Oscar Nierstrasz, Damien Pollet, Damien Cassou, Marcus Denker

Computer Science Faculty Publications and Presentations

Squeak is a modern open-source development environment for the classic Smalltalk-80 programming language. This book, intended for both students and developers, will guide you gently through the language and tools by means of a series of examples and exercises.

Additional material is available from the book's web page at SqueakByExample.org.

Evaluating Similarity-Based Trace Reduction Techniques For Scalable Performance Analysis, Kathryn Marie Mohror, Karen L. Karavanic

Computer Science Faculty Publications and Presentations

Event traces are required to correctly diagnose a number of performance problems that arise on today’s highly parallel systems. Unfortunately, the collection of event traces can produce a large volume of data that is difficult, or even impossible, to store and analyze. One approach for compressing a trace is to identify repeating trace patterns and retain only one representative of each pattern. However, determining the similarity of sections of traces, i.e., identifying patterns, is not straightforward. In this paper, we investigate pattern-based methods for reducing traces that will be used for performance analysis. We evaluate the different methods against several …

Prostate Segmentation On Pelvic Ct Images Using A Genetic Algorithm, Payel Ghosh, Melanie Mitchell

Computer Science Faculty Publications and Presentations

A genetic algorithm (GA) for automating the segmentation of the prostate on pelvic computed tomography (CT) images is presented here. The images consist of slices from three-dimensional CT scans. Segmentation is typically performed manually on these images for treatment planning by an expert physician, who uses the “learned” knowledge of organ shapes, textures and locations to draw a contour around the prostate. Using a GA brings the flexibility to incorporate new “learned” information into the segmentation process without modifying the fitness function that is used to train the GA. Currently the GA uses prior knowledge in the form of texture …

Better Refactoring Tools For A Better Refactoring Strategy, Andrew P. Black

Computer Science Faculty Publications and Presentations

Refactoring tools can improve the speed and accuracy with which we create and maintain software – but only if they are used. In practice, tools are not used as much as they could be; this seems to be because they do not align with the refactoring strategy preferred by the majority of programmers: floss refactoring. We propose five principles that characterize successful floss refactoring tools – principles that can help programmers to choose the most appropriate refactoring tools and also help toolsmiths to design more usable tools.

A Framework For Relationship Pattern Languages, Sudarshan Murthy, David Maier

Computer Science Faculty Publications and Presentations

A relationship pattern is an abstraction of a recurring need when establishing relationships among information elements in specific contexts. By developing or leveraging a relationship pattern, modelers can solve a class of problems once and describe many relationship types at once. We have developed a framework for specifying relationship patterns and pattern languages (sets of patterns) in both modeling-language-independent and modeling-language-specific ways. We describe this framework both informally and formally. We provide examples of some commonly observed relationship patterns and show how to use them in ER with the help of a relationship pattern language called Exemplar. We also provide …

Scalable Concurrent Hash Tables Via Relativistic Programming, Josh Triplett

Computer Science Faculty Publications and Presentations

Existing approaches to concurrent programming often fail to account for synchronization costs on modern shared-memory multipro- cessor architectures. A new approach to concurrent programming, known as relativistic programming, can reduce or in some cases eliminate synchronization overhead on such architectures. This approach avoids the costs of inter-processor communication and memory access by permitting processors to operate from a relativistic view of memory provided by their own caches, rather than from an absolute reference frame of memory as seen by all processors. This research shows how relativistic programming techniques can provide the perceived advantages of optimistic synchronization without the useless parallelism …

Reconstructing Images As Piecewise Smooth Functions, Ralf Juengling

Computer Science Faculty Publications and Presentations

Leclerc’s approach to image reconstruction consists of finding the shortest description of the data (an image) as a model (reconstruction) plus noise [5]. The approach poses two design problems: 1. Define an appropriate description language for image models and noise, 2. Derive an objective function and conceive an optimization algorithm that finds good local minima. Leclerc proposed to model images as piecewise low order polynomials and to describe models in terms of region boundaries (discontinuity set) and polynomial coefficients.

In this report I describe Leclerc’s methodology, and, adopting his image model and description language, derive an objective function within this …

Traffic Analysis Of Udp-Based Flows In Ourmon, Jim Binkley, Divya Parekh

Computer Science Faculty Publications and Presentations

We present a custom UDP flow tuple with an IP address key and a set of simple related statistical attributes. Attributes are used to calculate a per host metric called the UDP work weight which roughly measures the amount of network noise caused by a host. The work weight is used to produce a near real-time sorted top N report for UDP host tuples. We also present a derived attribute based on an algorithm called the UDP guesstimator. The UDP guesstimator roughly classifies port report hosts into various traffic categories including security threats (DOS/scanning) or P2P hosts based on high …

Patterns Of Aspect-Oriented Design, Black P. Andrew, James Noble, David J. Pearce, Arno Scmidmeir

Computer Science Faculty Publications and Presentations

Aspect-oriented programming languages are becoming commonplace, and programmers are accumulating experience in building and maintaining aspect-oriented systems. This paper addresses how the use of these languages affects program design: how aspect-oriented languages change the design space, which designs should be emulated and which avoided, and the strengths and weaknesses of particular kinds of design. We identify five patterns of aspect-oriented design: Spectator, Regulator, Patch, Extension, and Heterarchical Design. For each pattern, we describe the problem it solves, show how aspect-oriented language features are used in the pattern, give characteristic examples of the pattern’s use, and assess its benefits and liabilities. …

Refactoring Tools: Fitness For Purpose, Emerson Murphy-Hill, Andrew P. Black

Computer Science Faculty Publications and Presentations

Refactoring tools can improve the speed and accuracy with which we create and maintain software -- but only if they are used. In practice, tools are not used as much as they could be: this seems to be because sometimes they do not align with the refactoring tactic preferred by the majority of programmers, a tactic we call floss refactoring. We propose five principles that characterize successful floss refactoring tools -- principles that can help programmers to choose the most appropriate refactoring tools and also help toolsmiths to design tools that fit the programmer's purpose.

Association-Based Image Retrieval For Automatic Target Recognition., Arun D. Kulkarni, H. Gunturu, S. Dalta

Computer Science Faculty Publications and Presentations

Model-based automatic target recognition (ATR)systems deal with recognizing three dimensional objects from two dimensional images. In order to recognizeand identify objects the ATRsystem must have one or more stored models. Multiple two dimensional views of each three dimensional objectthat may appear in the universe it deals withare stored in the database. During recognition, two dimensional view of atarget object is used a query image and the search is carried out to identify the corresponding three dimensional object. Stages of a model-based ATR system include preprocessing, segmentation, feature extraction, and searching thedatabase. One of the most important problems in a model-based …

What Is Rcu, Fundamentally?, Paul E. Mckenney, Jonathan Walpole

Computer Science Faculty Publications and Presentations

Read-copy update (RCU) is a synchronization mechanism that was added to the Linux kernel in October of 2002. RCU achieves scalability improvements by allowing reads to occur concurrently with updates. In contrast with conventional locking primitives that ensure mutual exclusion among concurrent threads regardless of whether they be readers or updaters, or with reader-writer locks that allow concurrent reads but not in the presence of updates, RCU supports concurrency between a single updater and multiple readers. RCU ensures that reads are coherent by maintaining multiple versions of objects and ensuring that they are not freed up until all pre-existing read-side …

Association-Based Image Retrieval, Arun D. Kulkarni, H. Gunturu, S. Dalta

Computer Science Faculty Publications and Presentations

With advances in the computer technology and the World Wide Web there has been an explosion in the amount and complexity of multimedia data that are generated, stored, transmitted, analyzed, and accessed. In order to extract useful information from this huge amount of data, many content-based image retrieval (CBIR) systems have been developed in the last decade. A typical CBIR system captures image features that represent image properties such as color, texture, or shape of objects in the query image and try to retrieve images from the database with similar features. Recent advances in CBIR systems include relevance feedback based …

Cache Coherence Protocol Verification Using Ωmega, Ki Yung Ahn

Computer Science Faculty Publications and Presentations

We verify some correctness properties of the DASH cache coherence protocol using Ωmega. Ωmega is a language with a rich type system featuring GADTs, type functions, and user-guided type checking rules. Cache coherence protocols have both safety properties and liveness properties. We show how to describe some of the safety properties of DASH cache coherence protocol in mega. Since liveness properties are not easily expressed by types, we investigate invariants sufficient to imply some of the liveness properties of concern, and assert those invariants as well in the type system of Ωmega. Using Ωmega, we can have both a working …

Protecting The Internet With Public Work, Ed Kaiser, Wu-Chang Feng

Computer Science Faculty Publications and Presentations

Distributed denial-of-service attacks represent a growing problem for networked systems. To tackle this problem, this paper explores the addition of a public work function to the service advertisement mechanisms used by such systems. When under attack, services advertise this function along with their location information and clients must attach a solution to the function with subsequent requests. The function, which can be made specific to the source of traffic, is publicly verifiable, allowing arbitrary network devices at the edges of the network to quickly verify that subsequent communication from the source will be accepted by the destination. We describe a …

Why Don’T People Use Refactoring Tools?, Andrew P. Black, Emerson Murphy-Hill

Computer Science Faculty Publications and Presentations

Tools that perform refactoring are currently under-utilized by programmers. As more advanced refactoring tools are designed, a great chasm widens between how the tools must be used and how programmers want to use them. In this position paper, we characterize the dominant process of refactoring, demonstrate that many research tools do not support this process, and initiate a call to action for designers of future refactoring tools.

Directflow: A Domain-Specific Language For Information-Flow Systems, Andrew P. Black, Chuan-Kai Lin

Computer Science Faculty Publications and Presentations

Programs that process streams of information are commonly built by assembling reusable information-flow components. In some systems the components must be chosen from a pre-defined set of primitives; in others the programmer can create new custom components using a general-purpose programming language. Neither approach is ideal: restricting programmers to a set of primitive components limits the expressivity of the system, while allowing programmers to define new components in a general-purpose language makes it difficult or impossible to reason about the composite system. We advocate defining information-flow components in a domain-specific language (DSL) that enables us to infer the properties of …

Content-Based Image Retrieval Using Associative Memories, Arun D. Kulkarni

Computer Science Faculty Publications and Presentations

The rapid growth in the number of large-scale repositories has brought the need for efficient and effective content-based image retrieval (CBIR) systems. The state of the art in the CBIR systems is to search images in database that are “close” to the query image using some similarity measure. The current CBIR systems capture image features that represent properties such as color, texture, and/or shape of the objects in the query image and try to retrieve images from the database with similar features. In this paper, we propose a new architecture for a CBIR system. We try to mimic the human …

Fuzzy Neural Network Models For Multispectral Image Analysis, Arun D. Kulkarni, Sara Mccaslin

Computer Science Faculty Publications and Presentations

Fuzzy neural networks (FNNs) provide a new approach for classification of multispectral data and to extract and optimize classification rules. Neural networks deal with issues on a numeric level, whereas fuzzy logic deals with them on a semantic or linguistic level. FNNs synthesize fuzzy logic and neural networks. Recently, there has been growing interest in the research community not only to understand how FNNs arrive at particular decisions but how to decode information stored in the form of connection strengths in the network. In this paper, we propose fuzzy neural network models for classification of pixels in multispectral images and …

A Pattern Language For Extensible Program Representation, Andrew P. Black, Daniel Vainsencher

Computer Science Faculty Publications and Presentations

For the last 15 years, implementors of multiple view programming environments have sought a single code model that would form a suitable basis for all of the program analyses and tools that might be applied to the code. They have been unsuccessful. The consequences are a tendency to build monolithic, single-purpose tools, each of which implements its own specialized analyses and optimized representation. This restricts the availability of the analyses, and also limits the reusability of the representation by other tools. Unintegrated tools also produce inconsistent views, which reduce the value of multiple views. This article describes a set of …

Can Infopipes Facilitate Reuse In A Traffic Application?, Emerson Murphy-Hill, Chuan-Kai Lin, Andrew P. Black, Jonathan Walpole

Computer Science Faculty Publications and Presentations

Infopipes are presented as reusable building blocks for streaming applications. To evaluate this claim, we have built a significant traffic application in Smalltalk using Infopipes. This poster presents a traffic problem and solution, a short introduction to Infopipes, and the types of reuse Infopipes facilitate in our implementation.

Rcu Semantics: A First Attempt, Paul E. Mckenney, Jonathan Walpole

Computer Science Faculty Publications and Presentations

There is not yet a formal statement of RCU (read-copy update) semantics. While this lack has thus far not been an impediment to adoption and use of RCU, it is quite possible that formal semantics would point the way towards tools that automatically validate uses of RCU or that permit RCU algorithms to be automatically generated by a parallel compiler. This paper is a first attempt to supply a formal definition of RCU. Or at least a semi-formal definition: although RCU does not yet wear a tux (though it does run in Linux), at least it might yet wear some …

Locality, Network Control And Anomaly Detection, Jim Binkley

Computer Science Faculty Publications and Presentations

Ourmon is a near real-time network monitoring and anomaly detection system that captures packets using port-mirroring on Ethernet switches. It primarily displays data via web graphics using either RRDTOOL stripcharts or via histograms for top talker style graphs. We have developed a theory that network scanning launched primarily by worm programs including TCP and UDP scanners may be caught by monitoring network control data including TCP control packets (SYNS, FINS, RESETS) and ICMP errors, or by monitoring certain carefully chosen metadata such as the flow count itself. In this paper we concentrate on TCP and present a ”flow tuple” focused …

Toward A Sound Integration Of Isabelle With A Combined Decision Procedure, Tom Harke

Computer Science Faculty Publications and Presentations

I present work on a project to integrate Isabelle, an extremely versatile interactive proof assistant, with a combined decision procedure, the Cooperating Validity Checker (CVC). Isabelle is sound and flexible, however it is often tedious to use. CVC is fully automatic, but only handles decision problems expressible over a relatively weak set of theories including linear arithmetic, uninterpreted functions, data types, and firstorder quantifier-free logic. My goal is to increase the amount of automation in Isabelle, by making it use CVC as an oracle for such problems, but without compromising Isabelle’s soundness.

In this paper I report on the progress …

Using Dynamic Optimization For Control Of Real Rate Cpu Resource Management Applications, Varin Vahia, Ashvin Goel, David Steere, Jonathan Walpole, Molly H. Shor

Computer Science Faculty Publications and Presentations

In this paper we design a proportional-period optimal controller for allocating CPU to real rate multimedia applications on a general-purpose computer system. We model this computer system problem in to state space form. We design a controller based on dynamic optimization LQR tracking techniques to minimize short term and long term time deviation from the current time stamp and also CPU usage. Preliminary results on an experimental set up are encouraging.

A Browser For Incremental Programming, Andrew P. Black

Computer Science Faculty Publications and Presentations

Much of the elegance and power of Smalltalk comes from its programming environment and tools. First introduced more than 20 years ago, the Smalltalk browser enables programmers to “home in” on particular methods using a hierarchy of manually-defined classifications. By its nature, this classification scheme says a lot about the desired state of the code, but little about the actual state of the code as it is being developed. We have extended the Smalltalk browser with dynamically computed virtual categories that dramatically improve the browser’s support for incremental programming. We illustrate these improvements by example, and describe the algorithms used …

Adaptive Live Video Streaming By Priority Drop, Jie Huang, Charles Krasic, Jonathan Walpole

Computer Science Faculty Publications and Presentations

In this paper we explore the use of Priority-progress streaming (PPS) for video surveillance applications. PPS is an adaptive streaming technique for the delivery of continuous media over variable bit-rate channels. It is based on the simple idea of reordering media components within a time window into priority order before transmission. The main concern when using PPS for live video streaming is the time delay introduced by reordering. In this paper we describe how PPS can be extended to support live streaming and show that the delay inherent in the approach can be tuned to satisfy a wide range of …

Under The Plastic: A Quantitative Look At Dvd Video Encoding And Its Impact On Video Modeling, Wu-Chi Feng, Jin Choi, Wu-Chang Feng, Jonathan Walpole

Computer Science Faculty Publications and Presentations

In this paper, we examine the DVD encoding process and the implications this process has video modeling and network traffic analysis. We have assembled a system that allows us to extract the video data from the DVDs as they were encoded for distribution. Analyzing the resulting video trace data, we describe how DVD encodings have evolved over time. In addition, our findings show that the underlying video content is fundamentally different than those produced by basic consumer video capture boards. We demonstrate how this affects current video modeling proposals and their affect on network traffic characterization. This research is based …

Discovery Of Functional And Approximate Functional Dependencies In Relational Databases, Ronald S. King, James J. Legendre

Computer Science Faculty Publications and Presentations

This study develops the foundation for a simple, yet efficient method for uncovering functional and approximate functional dependencies in relational databases. The technique is based upon the mathematical theory of partitions defined over a relation's row identifiers. Using a levelwise algorithm the minimal non-trivial functional dependencies can be found using computations conducted on integers. Therefore, the required operations on partitions are both simple and fast. Additionally, the row identifiers provide the added advantage of nominally identifying the exceptions to approximate functional dependencies, which can be used effectively in practical data mining applications.