Computer Sciences Commons^™

Carving Differential Unit Test Cases From System Test Cases, Sebastian Elbaum, Hui Nee Chin, Matthew B. Dwyer, Jonathan Dokulil

School of Computing: Technical Reports

Unit test cases are focused and efficient. System tests are effective at exercising complex usage patterns. Differential unit tests (DUT) are a hybrid of unit and system tests. They are generated by carving the system components, while executing a system test case, that influence the behavior of the target unit, and then re-assembling those components so that the unit can be exercised as it was by the system test. We conjecture that DUTs retain some of the advantages of unit tests, can be automatically and inexpensively generated, and have the potential for revealing faults related to intricate system executions. In …

Sofya: A Flexible Framework For Development Of Dynamic Program Analyses For Java Software, Alex Kinneer, Matthew B. Dwyer, Gregg Rothermel

School of Computing: Technical Reports

Dynamic analysis techniques are well established in the software engineering community as methods for validating, understanding, maintaining, and improving programs. Generally, this class of techniques requires developers to instrument programs to generate events that capture, or observe, relevant features of program execution. Streams of these events are then processed to achieve the goals of the dynamic analysis. The lack of high-level tools for defining program observations, automating their mapping to efficient low-level implementations, and supporting the flexible combination of different event-stream-based processing components hampers the development and evaluation of new dynamic analysis techniques. For example, mapping non-trivial program observations to …

Interactive Fault Localization Techniques In A Spreadsheet Environment, Joseph R. Ruthruff, Margaret Burnett, Gregg Rothermel

School of Computing: Faculty Publications

End-user programmers develop more software than any other group of programmers, using software authoring devices such as multimedia simulation builders, e-mail filtering editors, by-demonstration macro builders, and spreadsheet environments. Despite this, there has been only a little research on finding ways to help these programmers with the dependability of the software they create. We have been working to address this problem in several ways, one of which includes supporting end-user debugging activities through interactive fault localization techniques. This paper investigates fault localization techniques in the spreadsheet domain, the most common type of end-user programming environment. We investigate a technique previously …

Computer Network Security And Arl Libraries, Deeann Allison, Scott Childers

University of Nebraska-Lincoln Libraries: Faculty Publications

This article reviews current recommendations for computer security practices for staff computing, summarizes current practices in United States Association of Research Libraries and proposes further areas to explore.

Idf: An Inconsistency Detection Framework – Performance Modeling And Guide To Its Design, Yijun Lu, Xueming Li, Hong Jiang

School of Computing: Technical Reports

With the increased popularity of replica-based services in distributed systems such as the Grid, consistency control among replicas becomes more and more important. To this end, IDF (Inconsistency Detection Framework), a two-layered overlay-based architecture, has been proposed as a new way to solve this problem—instead of enforcing a predefined protocol, IDF detects inconsistency in a timely manner when it occurs and resolves it based on applications’ semantics.
This paper presents a comprehensive analytical study of IDF to assess its performance and provide insight into its design. More specifically, it develops an analytical model to characterize IDF. Based on this model, …

Implementing Cs1 With Embedded Instructional Research Design In Laboratories, Jeff Lang, Gwen C. Nugent, Ashok Samal, Leen-Kiat Soh

School of Computing: Faculty Publications

Closed laboratories are becoming an increasingly popular approach to teaching introductory computer science courses. Unlike open laboratories that tend to be an informal environment provided for students to practice their skills with attendance optional, closed laboratories are structured meeting times that support the lecture component of the course, and attendance is required. This paper reports on an integrated approach to designing, implementing, and assessing laboratories with an embedded instructional research design. The activities reported here are parts of a department-wide effort not only to improve student learning in computer science and computer engineering (CE) but also to improve the agility …

Allocating Non-Real-Time And Soft Real-Time Jobs In Multiclusters, Ligang He, Stephen A. Jarvis, Daniel P. Spooner, Hong Jiang, Donna N. Dillenberger, Graham R. Nudd

School of Computing: Faculty Publications

This paper addresses workload allocation techniques for two types of sequential jobs that might be found in multicluster systems, namely, non-real-time jobs and soft real-time jobs. Two workload allocation strategies, the Optimized mean Response Time (ORT) and the Optimized mean Miss Rate (OMR), are developed by establishing and numerically solving two optimization equation sets. The ORT strategy achieves an optimized mean response time for non-real-time jobs, while the OMR strategy obtains an optimized mean miss rate for soft real-time jobs over multiple clusters. Both strategies take into account average system behaviors (such as the mean arrival rate of jobs) in …

Ceft: A Cost-Effective, Fault-Tolerant Parallel Virtual File System, Yifeng Zhu, Hong Jiang

School of Computing: Faculty Publications

The vulnerability of computer nodes due to component failures is a critical issue for cluster-based file systems. This paper studies the development and deployment of mirroring in cluster-based parallel virtual file systems to provide fault tolerance and analyzes the tradeoffs between the performance and the reliability in the mirroring scheme. It presents the design and implementation of CEFT, a scalable RAID-10 style file system based on PVFS, and proposes four novel mirroring protocols depending on whether the mirroring operations are server-driven or client-driven, whether they are asynchronous or synchronous. The comparisons of their write performances, measured in a real cluster, …

Exploiting Redundancy To Boost Performance In A Raid-10 Style Cluster-Based File System, Yifeng Zhu, Hong Jiang, Xiao Qin, Dan Feng, David Swanson

School of Computing: Faculty Publications

While aggregating the throughput of existing disks on cluster nodes is a cost-effective approach to alleviate the I/O bottleneck in cluster computing, this approach suffers from potential performance degradations due to contentions for shared resources on the same node between storage data processing and user task computation. This paper proposes to judiciously utilize the storage redundancy in the form of mirroring existed in a RAID-10 style file system to alleviate this performance degradation. More specifically, a heuristic scheduling algorithm is developed, motivated from the observations of a simple cluster configuration, to spatially schedule write operations on the nodes with less …

Web Application Characterization Through Directed Requests, Sebastian Elbaum, Kalyanram Chilakamarri, Marc Randall Fisher Ii, Gregg Rothermel

School of Computing: Technical Reports

Web applications are increasingly prominent in society, serving a wide variety of user needs. Engineers seeking to enhance, test, and maintain these applications must be able to understand and characterize their interfaces. Third-party programmers (professional or end user) wishing to incorporate the data provided by such services into their own applications would also benefit from such characterization when the target site does not provide adequate programmatic interfaces. In this paper, therefore, we present methodologies for characterizing the interfaces to web applications through a form of dynamic analysis, in which directed requests are sent to the application, and responses are analyzed …

Approximation Algorithms For Survivable Multicommodity Flow Problems With Applications To Network Design, Ajay Todimala, Byrav Ramamurthy

School of Computing: Conference and Workshop Papers

Multicommodity flow (MF) problems have a wide variety of applications in areas such as VLSI circuit design, network design, etc., and are therefore very well studied. The fractional MF problems are polynomial time solvable while integer versions are NP-complete. However, exact algorithms to solve the fractional MF problems have high computational complexity. Therefore approximation algorithms to solve the fractional MF problems have been explored in the literature to reduce their computational complexity. Using these approximation algorithms and the randomized rounding technique, polynomial time approximation algorithms have been explored in the literature.

In the design of high-speed networks, such as …

Scaling A Dataflow Testing Methodology To The Multiparadigm World Of Commercial Spreadsheets, Marc Randall Fisher Ii, Gregg Rothermel, Tyler Creelan, Margaret Burnett

School of Computing: Technical Reports

Spreadsheets are widely used but often contain faults. Thus, in prior work we presented a dataflow testing methodology for use with spreadsheets, which studies have shown can be used cost-effectively by end-user programmers. To date, however, the methodology has been investigated across a limited set of spreadsheet language features. Commercial spreadsheet environments are multiparadigm languages, utilizing features not accommodated by our prior approaches. In addition, most spreadsheets contain large numbers of replicated formulas that severely limit the efficiency of dataflow testing approaches. We show how to handle these two issues with a new dataflow adequacy criterion and automated detection of …

An Efficient Scheduling Scheme For On-Demand Lightpath Reservations In Reconfigurable Wdm Optical Networks, Xi Yang, Lu Shen, Ajay Todimala, Byrav Ramamurthy, Tom Lehman

School of Computing: Conference and Workshop Papers

We propose an efficient scheduling scheme that optimizes advance-reserved lightpath services in reconfigurable WDM networks. A re-optimization approach is devised to reallocate network resources for dynamic service demands while keeping determined schedule unchanged.

A Generic Autonomous Clustering-Based Heterogeneous Waveband Switching Architecture In Wdm Networks, Mengke Li, Byrav Ramamurthy

School of Computing: Conference and Workshop Papers

Heterogeneous waveband switching (HeteroWBS) in WDM networks reduces the network operational costs. We propose an autonomous clustering-based HeteroWBS architecture to support the design of efficient HeteroWBS algorithms under dynamic traffic requests in such a network.

Active Learning To Maximize Area Under The Roc Curve, Matt Culver, Deng Kun, Stephen Scott

School of Computing: Conference and Workshop Papers

In active learning, a machine learning algorithmis given an unlabeled set of examples U, and is allowed to request labels for a relatively small subset of U to use for training. The goal is then to judiciously choose which examples in U to have labeled in order to optimize some performance criterion, e.g. classification accuracy. We study how active learning affects AUC. We examine two existing algorithms from the literature and present our own active learning algorithms designed to maximize the AUC of the hypothesis. One of our algorithms was consistently the top performer, and Closest Sampling from the literature …

Scaling A Dataflow Testing Methodology To The Multiparadigmworld Of Commercial Spreadsheets, Marc Fisher Ii, Gregg Rothermel, Tyler Creelan, Margaret Burnett

School of Computing: Conference and Workshop Papers

Spreadsheets are widely used but often contain faults. Thus, in prior work we presented a data-flow testing methodology for use with spreadsheets, which studies have shown can be used cost-effectively by end-user programmers. To date, however, the methodology has been investigated across a limited set of spreadsheet language features. Commercial spreadsheet environments are multiparadigm languages, utilizing features not accommodated by our prior approaches. In addition, most spreadsheets contain large numbers of replicated formulas that severely limit the efficiency of data-flow testing approaches. We show how to handle these two issues with a new data-flow adequacy criterion and automated detection of …

An Ontology-Based Metamodel For Software Patterns, Scott Henninger, Padmapriya Ashokkumar

School of Computing: Technical Reports

Patterns have been successfully used in software design to reuse proven solutions. But the complex interconnections and the number of pattern collections is becoming a barrier for identifying relevant patterns and pattern combinations for a given design context. More formal representations of patterns are needed that allow machine processing and the creation of systematic pattern languages that guide composition of patterns into coherent design solutions. In this paper, we present a technique based on Description Logic and Semantic Web technologies to address these problems. A metamodel is presented for developing pattern languages using this technology. Usability patterns are used to …

An Interactive Constraint-Based Approach To Minesweeper, Ken Bayer, Josh Snyder, Berthe Y. Choueiry

School of Computing: Conference and Workshop Papers

We present a Java applet that uses Constraint Processing (CP) to assist a human in playing the popular game Minesweeper. Our goal is to illustrate the power of CP techniques to model and solve combinatorial problems in a context accessible to the general public.

Minesweeper is a video game that has been included with Microsoft Windows since 1989. In this game, the player is presented with a grid of squares. Each of these squares may conceal a mine. When the player clicks on a square, it is revealed. If the square is a mine, the game is over. If the …

Automated Generation Of Context-Aware Tests, Zhimin Wang, Sebastian Elbaum, David Rosenblum

School of Computing: Technical Reports

The incorporation of context-awareness capabilities into pervasive applications allows them to leverage contextual information to provide additional services while maintaining an acceptable quality of service. These added capabilities, however, introduce a distinct input space that can affect the behavior of these applications at any point during their execution, making their validation quite challenging. In this paper, we introduce an approach to improve the test suite of a context-aware application by identifying context-aware program points where context changes may affect the application’s behavior, and by systematically manipulating the context data fed into the application to increase its exposure to potentially valuable …

A New Cryptographic Scheme For Securing Dynamic Conferences In Data Networks, Sarang Deshpande, Ajay Todimala, Ravi K Balachandran, Byrav Ramamurthy, Xukai Zou, N. V. Vinodchandran

School of Computing: Conference and Workshop Papers

Dynamic conferencing refers to a scenario wherein any subset of users in a universe of users form a conference for sharing confidential information among themselves. The key distribution (KD) problem in dynamic conferencing is to compute a shared secret key for such a dynamically formed conference. In literature, the KD schemes for dynamic conferencing either are computationally unscalable or require communication among users, which is undesirable. The extended symmetric polynomial based dynamic conferencing scheme (ESPDCS) is one such KD scheme which has a high computational complexity that is universe size dependent. In this paper we present an enhancement to the …

Router And Firewall Redundancy With Openbsd And Carp, Garhan Attebury, Byrav Ramamurthy

School of Computing: Conference and Workshop Papers

As more reliance is placed on computing and networking systems, the need for redundancy increases. The Common Address Redundancy Protocol (CARP) protocol and OpenBSD’s pfsync utility provide a means by which to implement redundant routers and firewalls. This paper details how CARP and pfsync work together to provide this redundancy and explores the performance one can expect from the open source solutions. Two experiments were run: one showing the relationship between firewall state creation and state synchronization traffic and the other showing how TCP sessions are transparently maintained in the event of a router failure. Discussion of these simulations along …

Autonomous Clustering-Based Heterogeneous Waveband Switching In Wdm Networks, Mengke Li, Byrav Ramamurthy

School of Computing: Conference and Workshop Papers

Employing waveband switching (WBS) in WDM networks can reduce the network operational cost and the call blocking probability. However, upgrading the existing optical switching architecture requires time and money. It is expected that a heterogeneous waveband switching (HeteroWBS) architecture would be desirable, where some nodes can support WBS functions and some cannot. We study the performance of HeteroWBS networks in terms of call blocking probability and cost savings under dynamic traffic requests. We propose an autonomous clustering-based HeteroWBS (AS-HeteroWBS) architecture to clusters the network into multiple autonomous systems (ASs). An AS may contain some specific nodes that provide WBS functions …

Integrated Intermediate Waveband And Wavelength Switching For Optical Wdm Mesh Networks, Mengke Li, Byrav Ramamurthy

School of Computing: Conference and Workshop Papers

As wavelength-division multiplexing (WDM) evolves towards practical applications in optical transport networks, waveband switching (WBS) has been introduced to cut down the operational costs and to reduce the complexities and sizes of network components, e.g., optical cross-connects (OXCs). This paper considers the routing, wavelength assignment and waveband assignment (RWWBA) problem in a WDM network supporting mixed waveband and wavelength switching. First, the techniques supporting waveband switching are studied, where a node architecture enabling mixed waveband and wavelength switching is proposed. Second, to solve the RWWBA problem with reduced switching costs and improved network throughput, the cost savings and call blocking …

Dynamic Lightpath Scheduling In Next-Generation Wdm Optical Networks, Lu Shen, Ajay Todimala, Byrav Ramamurthy, Xi Yang

School of Computing: Conference and Workshop Papers

Lightpath scheduling is an important capability in next-generation wavelength-division multiplexing (WDM) optical networks to reserve resources in advance for a specified time period while provisioning end-to-end lightpaths. In this study, we propose an approach to support dynamic lightpath scheduling in such networks. To minimize blocking probability in a network that accommodates dynamic scheduled lightpath demands (DSLDs), resource allocation should be optimized in a dynamic manner. However, for the network users who desire deterministic services, resources must be reserved in advance and guaranteed for future use. These two objectives may be mutually incompatible. Therefore, we propose a two-phase dynamic lightpath scheduling …

A Survey Of Security Issues In Wireless Sensor Networks, Yong Wang, Garhan Attebury, Byrav Ramamurthy

School of Computing: Faculty Publications

Wireless Sensor Networks (WSNs) are used in many applications in military, ecological, and health-related areas. These applications often include the monitoring of sensitive information such as enemy movement on the battlefield or the location of personnel in a building. Security is therefore important in WSNs. However, WSNs suffer from many constraints, including low computation capability, small memory, limited energy resources, susceptibility to physical capture, and the use of insecure wireless communication channels. These constraints make security in WSNs a challenge. In this article we present a survey of security issues in WSNs. First we outline the constraints, security requirements, and …

The Performance Of Elliptic Curve Based Group Diffie-Hellman Protocols For Secure Group Communication Over Ad Hoc Networks, Yong Wang, Byrav Ramamurthy, Xukai Zou

School of Computing: Conference and Workshop Papers

The security of the two party Diffie-Hellman key exchange protocol is currently based on the discrete logarithm problem (DLP). However, it can also be built upon the elliptic curve discrete logarithm problem (ECDLP). Most proposed secure group communication schemes employ the DLP-based Diffie-Hellman protocol. This paper proposes the ECDLP-based Diffie-Hellman protocols for secure group communication and evaluates their performance on wireless ad hoc networks. The proposed schemes are compared at the same security level with DLP-based group protocols under different channel conditions. Our experiments and analysis show that the Tree-based Group Elliptic Curve Diffie-Hellman (TGECDH) protocol is the best in …

Spatial Correlation-Based Collaborative Medium Access Control In Wireless Sensor Networks, Mehmet C. Vuran, Ian F. Akyildiz

School of Computing: Faculty Publications

Wireless Sensor Networks (WSN) are mainly characterized by dense deployment of sensor nodes which collectively transmit information about sensed events to the sink. Due to the spatial correlation between sensor nodes subject to observed events, it may not be necessary for every sensor node to transmit its data. This paper shows how the spatial correlation can be exploited on the Medium Access Control (MAC) layer. To the best of our knowledge, this is the first effort which exploits spatial correlation in WSN on the MAC layer. A theoretical framework is developed for transmission regulation of sensor nodes under a distortion …

Eraid: Conserving Energy In High Performance Raid Systems With Conventional Disks, Dong Li, Jun Wang

School of Computing: Technical Reports

Recently energy consumption becomes an ever critical concern for both low-end and high-end storage server and data centers. A majority of existing energy conservation solutions resort to multi-speed disks. However, current server systems are still built with conventional disks.
In this paper, we propose an energy saving policy, eRAID, for conventional disk based RAID-1 systems. eRAID saves energy by spinning down partial or entire mirror disk group with predictable performance degradation. The heart work of eRAID is to develop an accurate dynamic performance control (including disk power management) scheme. To guarantee service quality, the dynamic performance control works for two …

Helping End-User Programmers “Engineer” Dependable Software, Gregg Rothermel

School of Computing: Conference and Workshop Papers

Not long ago, most software was written by professional programmers, who could be presumed to have an interest in software engineering methodologies and in tools and techniques for improving software dependability. Today, however, a great deal of software is written not by professionals but by end-users, who create applications such as multimedia simulations, dynamic web pages, and spreadsheets. Applications such as these are often used to guide important decisions or aid in important tasks, and it is important that they be sufficiently dependable, but evidence shows that they frequently are not. For example, studies have shown that a large percentage …

Spatio-Temporal Characteristics Of Point And Field Sources In Wireless Sensor Networks, Mehmet C. Vuran, Ӧzgür B. Akan

School of Computing: Conference and Workshop Papers

Wireless Sensor Networks (WSN) are comprised of densely deployed sensor nodes collaboratively observing and communicating extracted information about a physical phenomenon. Dense deployment of sensor nodes makes the sensor observations highly correlated in the space domain. In addition, consecutive samples obtained by a sensor node are also temporally correlated for the applications involving the observation of the variation of a physical phenomenon. Based on the physical characteristics and dispersion pattern over the area, the phenomenon to be observed can be modeled as point source or field source. Clearly, understanding the spatio-temporal correlation characteristics of the point and field sources brings …