Digital Commons Network^™

An Empirical Study Of Fault Localization For End-User Programmers, Joseph R. Ruthruff, Margaret Burnett, Gregg Rothermel

School of Computing: Conference and Workshop Papers

End users develop more software than any other group of programmers, using software authoring devices such as e-mail filtering editors, by-demonstration macro builders, and spreadsheet environments. Despite this, there has been little research on finding ways to help these programmers with the dependability of their software. We have been addressing this problem in several ways, one of which includes supporting end-user debugging activities through fault localization techniques. This paper presents the results of an empirical study conducted in an end-user programming environment to examine the impact of two separate factors in fault localization techniques that affect technique effectiveness. Our results …

A Controlled Experiment Assessing Test Case Prioritization Techniques Via Mutation Faults, Hyunsook Do, Gregg Rothermel

School of Computing: Conference and Workshop Papers

Regression testing is an important part of software maintenance, but it can also be very expensive. To reduce this expense, software testers may prioritize their test cases so that those that are more important are run earlier in the regression testing process. Previous work has shown that prioritization can improve a test suite’s rate of fault detection, but the assessment of prioritization techniques has been limited to hand-seeded faults, primarily due to the belief that such faults are more realistic than automatically generated (mutation) faults. A recent empirical study, however, suggests that mutation faults can be representative of real faults. …

Helping End-Users “Engineer” Dependable Web Applications, Sebastian Elbaum, Kalyan-Ram Chilakamarri, Bhuvana Gopal, Gregg Rothermel

School of Computing: Conference and Workshop Papers

End-user programmers are increasingly relying on web authoring environments to create web applications. Although often consisting primarily of web pages, such applications are increasingly going further, harnessing the content available on the web through “programs” that query other web applications for information to drive other tasks. Unfortunately, errors can be pervasive in web applications, impacting their dependability. This paper reports the results of an exploratory study of end-user web application developers, performed with the aim of exposing prevalent classes of errors. The results suggest that end-users struggle the most with the identification and manipulation of variables when structuring requests to …

Balancing Exploration And Exploitation: A New Algorithm For Active Machine Learning, Thomas Osugi, Deng Kun, Stephen Scott

School of Computing: Conference and Workshop Papers

Active machine learning algorithms are used when large numbers of unlabeled examples are available and getting labels for them is costly (e.g. requiring consulting a human expert). Many conventional active learning algorithms focus on refining the decision boundary, at the expense of exploring new regions that the current hypothesis misclassifies. We propose a new active learning algorithm that balances such exploration with refining of the decision boundary by dynamically adjusting the probability to explore at each step. Our experimental results demonstrate improved performance on data sets that require extensive exploration while remaining competitive on data sets that do not. Our …

Neighborhood Interchangeability And Dynamic Bundling For Non-Binary Csps, Anagh Lal, Berthe Y. Choueiry, Eugene C. Freuder

School of Computing: Conference and Workshop Papers

1. Interchangeability: An algorithm for computing interchangeability in non-binary CSPs.

2. Dynamic bundling: Integration of the above with backtrack search for solving non-binary CSPs.

3. Experiments demonstrating the benefits of dynamic bundling

·Finding multiple, robust solutions.

·Decreasing computational cost of search.

On Finding Consecutive Test Vectors In A Random Sequence For Energy-Aware Bist Design, Sheng Zhang, Sharad C. Seth, Bhargab B. Bhattacharya

School of Computing: Conference and Workshop Papers

During pseudorandom testing, a significant amount of energy and test application time is wasted for generating and for applying “useless” test vectors that do not contribute to fault dropping. For low-power testing, modification logic/ROM may be used to skip the LFSR states that generate useless test patterns. The overhead of extra logic increases rapidly with the number of such jumps. Since identification of useless patterns strongly depends on the order in which incremental fault simulation is performed, an elegant solution to this problem would be to find a minimum set of segments in the LFSR sequence, where each segment corresponds …

Profiling Deployed Software: Strategic Probe Placement, Madeline Diep, Sebastian Elbaum, Myra B. Cohen

School of Computing: Technical Reports

Profiling deployed software provides valuable insights for quality improvement activities. The probes required for profiling, however, can cause an unacceptable performance overhead for users. In previous work we have shown that significant overhead reduction can be achieved, with limited information loss, through the distribution of probes across deployed instances. However, existing strategies for probe distribution do not account for several relevant factors: acceptable overheads may vary, the distributions to be deployed may be limited, profiled events may have different likelihoods, and the user pool composition may be unknown. This paper evaluates strategies for probe distribution while manipulating these factors through …

Disseminating Usability Design Knowledge Through Ontology-Based Pattern Languages, Scott Henninger, Padmapriya Ashokkumar

School of Computing: Technical Reports

Usability patterns represent knowledge about known ways to design graphical user interfaces that are usable and meet the needs and expectations of users. There is currently a plethora of usability patterns published in books, private repositories and the World-Wide Web. The dominance of pattern discovery efforts has neglected the emerging need to organize the patterns so they can become a proactive resource for developing interfaces. This paper presents an approach using Semantic Web concepts that turns informal patterns into formal representations capable of supporting systematic design methods. Through this method, loosely coupled pattern collections can be turned into strongly coupled …

Real-Time Divisible Load Scheduling For Cluster Computing, Xuan Lin, Ying Lu, Jitender S. Deogun, Steve Goddard

School of Computing: Technical Reports

Cluster Computing has emerged as a new paradigm for solving large-scale problems. To enhance QoS and provide performance guarantees in cluster computing environments, various workload models and real-time scheduling algorithms have been investigated. The divisible load model, propagated by divisible load theory, models computations that can be arbitrarily divided into independent pieces and provides a good approximation of many real-world applications. However, researchers have not yet investigated the problem of providing performance guarantees to divisible load applications. Two contributions are made in this paper: (1) divisible load theory is extended to compute the minimum number of processors required to meet …

Dgkd: Distributed Group Key Distribution With Authentication Capability, Pratima Adusumilli, Xukai Zou, Byrav Ramamurthy

School of Computing: Conference and Workshop Papers

Group key management (GKM} is the most important issue in secure group communication (SCC). The existing GKM protocols fall into three typical classes: centralized group key distribution (CGKD), decentralized group key management (DGKM), and distributed/contributory group key agreement (CGKA). Serious problems remains in these protocols, as they require existence of central trusted entities (such as group controller or subgroup controllers), relaying of messages (by subgroup controllers), or strict member synchronization (JOT multiple round stepwise key agreement), thus suffering from the single point of failure and attack, performance bottleneck, or mis-operations in the situation of transmission delay or network failure. In …

Crtdh: An Efficient Key Agreement Scheme For Secure Group Communications In Wireless Ad Hoc Networks, Ravi K Balachandran, Byrav Ramamurthy, Xukai Zou, N.V. Vinodchandran

School of Computing: Conference and Workshop Papers

As a result of the growing popularity of wireless networks, in particular ad hoc networks, security over such networks has become very important. In this paper, we study the problem of secure group communications (SGC) and key management over ad hoc networks. We identify the key features of any SGC protocol for such networks. We also propose an efficient key agreement scheme for SGC. The scheme solves two important problems that exist in most current SGC schemes: requirement of member serialization and existence of a central entity. Besides this, the protocol also has many highly desirable properties such as contributory …

Same-Destination-Intermediate Grouping Vs. End-To-End Grouping For Waveband Switching In Wdm Mesh Networks, Mengke Li, Wang Yao, Byrav Ramamurthy

School of Computing: Conference and Workshop Papers

We investigate waveband switching (WBS) with different grouping strategies in wavelength-division multiplexing (WDM) mesh networks. End-to-end waveband switching (ETEWBS) and same-destination-intermediate waveband switching (SD-IT-WBS) are analyzed and compared in terms of blocking probability and cost savings. First, an analytical model for ETEWBS is proposed to determine the network blocking probability in a mesh network. For SD-IT-WBS, a simple waveband switching algorithm is presented. An analytical model to determine the network blocking probability is proposed for SD-IT-WBS based on the algorithm. The analytical results are validated by comparing with simulation results. Both results match well and show that ETE-WBS slightly outperforms …

A Novel Cost-Efficient On-Line Intermediate Waveband-Switching Scheme In Wdm Mesh Networks, Mengke Li, Wang Yao, Byrav Ramamurthy

School of Computing: Conference and Workshop Papers

Waveband switching (WBS) is an important technique to save switching and transmission cost in wavelength -division multiplexed (WDM) optical networks. A cost-efficient WBS scheme would enable network carriers to increase the network throughput (revenue) while achieving significant cost savings. We identify the critical factors that determine the WBS network throughput and switching cost and propose a novel intermediate waveband switching (IT-WBS) algorithm, called the minimizing-weighted-cost (MWC) algorithm. The MWC algorithm defines a cost for each candidate route of a call. By selecting the route with the smallest weighted cost, MWC balances between minimizing the call blocking probability and minimizing the …

Pre-Computation Approach To Nonlinear Simulations Of Deformable Objects, Jernej Barbic

Link Foundation Modeling, Simulation and Training Fellowship Reports

My research area involves building real-time interactive simulations of solid deformable objects. For example, liver tissue should defo1m realistically during a vi1tual surgery simulation. A virtual assembly simulation can catch airplane construction design flaws early on during the manufacturing process. Deformable objects are also useful in computer games, for example to model the motion of trees in the wind. Researchers in computational physics, mechanics, and applied mathematics have been developing algorithms for simulations of deformable objects for the past 40 years. However, the partial differential equations of solid continuum mechanics that govern deformations of physical objects are very involved and …

Applying Scenario-Based Design And Claim Analysis To The Design Of A Digital Library Of Geography Examination Resources, Yin-Leng Theng, Dion Hoe-Lian Goh, Ee Peng Lim, Zehua Liu, Ming Yin, Natalie Lee-San Pang, Patricia Bao-Bao Wong

Research Collection School Of Computing and Information Systems

This paper describes the application of Carroll’s scenario-based design and claims analysis as a means of refinement to the initial design of a digital library of geographical resources (GeogDL) to prepare Singapore students to take a national examination in geography. GeogDL is built on top of G-Portal, a digital library providing services over geospatial and georeferenced Web content. Beyond improving the initial design of GeogDL, a main contribution of the paper is making explicit the use of Carroll’s strong theory-based but undercapitalized scenario-based design and claims analysis that inspired recommendations for the refinement of GeogDL. The paper concludes with an …

A Multi-Agent Approach For Solving Optimization Problems Involving Expensive Resources, Hoong Chuin Lau, H. Wang

Research Collection School Of Computing and Information Systems

In this paper, we propose a multi-agent approach for solving a class of optimization problems involving expensive resources, where monolithic local search schemes perform miserably. More specifically, we study the class of bin-packing problems. Under our proposed Fine-Grained Agent System scheme, rational agents work both collaboratively and selfishly based on local search and mimic physics-motivated systems. We apply our approach to a generalization of bin-packing - the Inventory Routing Problem with Time Windows - which is an important logistics problem, and demonstrate the efficiency and effectiveness of our approach.

Neural Network-Based Control Of Nonlinear Discrete-Time Systems In Non-Strict Form, Jagannathan Sarangapani, Zheng Chen, Pingan He

Electrical and Computer Engineering Faculty Research & Creative Works

A novel reinforcement learning-based adaptive neural network (NN) controller, also referred as the adaptive-critic NN controller, is developed to deliver a desired tracking performance for a class of non-strict feedback nonlinear discrete-time systems in the presence of bounded and unknown disturbances. The adaptive critic NN controller architecture includes a critic NN and two action NNs. The critic NN approximates certain strategic utility function whereas the action neural networks are used to minimize both the strategic utility function and the unknown dynamics estimation errors. The NN weights are tuned online so as to minimize certain performance index. By using gradient descent-based …

A Multi-Hypothesis Approach For Salient Object Tracking In Visual Surveillance, Filiz Bunyak, Ilker Ersoy, S. R. Subramanya

Electrical and Computer Engineering Faculty Research & Creative Works

In this paper, a multiple object tracking method for visual surveillance applications is presented. Moving objects are detected by adaptive background subtraction and tracked by using a multi-hypothesis testing approach. Object matching between frames is done based on proximity and appearance similarity. a new confidence measure is assigned to each possible match. This information is arranged into a graph structure where vertices represent blobs in consecutive frames and edges represent match confidence values. This graph is later used to prune and refine trajectories to obtain the salient object trajectories. Occlusions are handled through position prediction using Kalman filter and robust …

The Inns President's Welcome, Donald C. Wunsch

Electrical and Computer Engineering Faculty Research & Creative Works

No abstract provided.

A Brief History Of Bioperl, Colin Crossman, Arti K. Rai

Faculty Scholarship

Large-scale open-source projects face a litany of pitfalls and difficulties. Problems of contribution quality, credit for contributions, project coordination, funding, and mission-creep are ever-present. Of these, long-term funding and project coordination can interact to form a particularly difficult problem for open-source projects in an academic environment.

BioPerl was chosen as an example of a successful academic open-source project. Several of the roadblocks and hurdles encountered and overcome in the development of BioPerl are examined through the telling of the history of the project. Along the way, key points of open-source law are explained, such as license choice and copyright.

The …

Finding And Maintaining Rigid Components, Audrey Lee, Ileana Streinu, Louis Theran

Computer Science: Faculty Publications

We give the first complete analysis that the complexity of finding and maintaining rigid components of planar bar-and-joint frameworks and arbitrary d-dimensional body-and-bar frameworks, using a family of algorithms called pebble games, is O(n2). To this end, we intro- duce a new data structure problem called union pair- find, which maintains disjoint edge sets and supports pair-find queries of whether two vertices are spanned by a set. We present solutions that apply to generalizations of the pebble game algorithms, beyond the original rigidity motivation.

Pseudo-Triangulations, Rigidity And Motion Planning, Ileana Streinu

Computer Science: Faculty Publications

This paper proposes a combinatorial approach to planning non-colliding trajectories for a polygonal bar-and-joint framework with n vertices. It is based on a new class of simple motions induced by expansive one-degree-of-freedom mechanisms, which guarantee noncollisions by moving all points away from each other. Their combinatorial structure is captured by pointed pseudo-triangulations, a class of embedded planar graphs for which we give several equivalent characterizations and exhibit rich rigidity theoretic properties. The main application is an efficient algorithm for the Carpenter's Rule Problem: convexify a simple bar-and-joint planar polygonal linkage using only non-self-intersecting planar motions. A step of the algorithm …

The Correlation Between Internal & External Markers For Abdominal Tumors: Implications For Respiratory Gating, David P. Gierga, Johanna Brewer, Gregory C. Sharp, Margrit Betke, Christopher G. Willett, George T.Y. Chen

Computer Science: Faculty Publications

Purpose: The correlation of the respiratory motion of external patient markers and abdominal tumors was examined. Data of this type are important for image-guided therapy techniques, such as respiratory gating, that monitor the movement of external fiducials.

Methods and Materials: Fluoroscopy sessions for 4 patients with internal, radiopaque tumor fiducial clips were analyzed by computer vision techniques. The motion of the internal clips and the external markers placed on the patient’s abdominal skin surface were quantified and correlated.

Results: In general, the motion of the tumor and external markers were well correlated. The maximum amount of peak-to-peak craniocaudal tumor motion …

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 …

Systems Analysis And Design: Should We Be Researching What We Teach?, A. Bajaj, D. Batra, A. Hevner, J. Parsons, Keng Siau

Research Collection School Of Computing and Information Systems

A guiding premise of academic scholarship is that knowledge gained from first-hand research experience is disseminated to students via the classroom. However, that valuable connection is lost when professors are not researching what they teach. In this paper, we explore issues of mismatch between teaching and research in the Information Systems (IS) discipline. Specifically, while systems analysis and design (SA&D) is an integral topic in IS curricula, this topic is the research specialty of few IS professors. This situation is reflected by the low number of research publications in this area; particularly in the leading mainstream IS journals. We characterize …

Robust Temporal Constraint Networks, Hoong Chuin Lau, Thomas Ou, Melvyn Sim

Research Collection School Of Computing and Information Systems

In this paper, we propose the Robust Temporal Constraint Network (RTCN) model for simple temporal constraint networks where activity durations are bounded by random variables. The problem is to determine whether such temporal network can be executed with failure probability less than a given 0 ≤ E ≤ 1 for each possible instantiation of the random variables, and if so. how one might find a feasible schedule with each given instantiation. The advantage of our model is that one can vary the value of ∊ to control the level of conservativeness of the solution. We present a computationally tractable and …

Exploring Bit-Difference For Approximate Knn Search In High-Dimensional Databases, Bin Cui, Heng Tao Shen, Jialie Shen, Kian-Lee Tan

Research Collection School Of Computing and Information Systems

In this paper, we develop a novel index structure to support effcient approximate k-nearest neighbor (KNN) query in high-dimensional databases. In high-dimensional spaces, the computational cost of the distance (e.g., Euclidean distance) between two points contributes a dominant portion of the overall query response time for memory processing. To reduce the distance computation, we first propose a structure (BID) using BIt-Difference to answer approximate KNN query. The BID employs one bit to represent each feature vector of point and the number of bit-difference is used to prune the further points. To facilitate real dataset which is typically skewed, we enhance …

Security Of An Ill-Posed Operator Based Scheme For Image Authentication, Yongdong Wu, Robert H. Deng

Research Collection School Of Computing and Information Systems

This letter analyzes the security of an image authentication scheme which exploits the instability of an ill-posed operator. Since the ill-posed operator produces only a limited number of authentic images regardless of the number of watermarks, an attacker can impersonate an image owner to generate authentic images at a high probability. Our experiments demonstrate that our attack is both practical and effective.

Measuring Community Consensus In Facial Characterization Using Spatial Databases And Fuzzy Logic, James Lee Mastros

Theses and Dissertations

Spatial databases store geometric objects and capture spatial relationships that can be used to represent key features of the human face. One can search spatial databases for these objects, and seek the relationships between them, using fuzzy logic to provide a natural way to describe the human face for the purposes of facial characterization. This study focuses on community perception of short, average, or long nose length. Three algorithms were used to update community opinion of nose length. All three methods showed similar trends in nose length classification which could indicate that the effort to extract spatial data from images …

Attribute-Level Versioning: A Relational Mechanism For Version Storage And Retrieval, Charles Andrew Bell

Theses and Dissertations

Data analysts today have at their disposal a seemingly endless supply of data and repositories hence, datasets from which to draw. New datasets become available daily thus making the choice of which dataset to use difficult. Furthermore, traditional data analysis has been conducted using structured data repositories such as relational database management systems (RDBMS). These systems, by their nature and design, prohibit duplication for indexed collections forcing analysts to choose one value for each of the available attributes for an item in the collection. Often analysts discover two or more datasets with information about the same entity. When combining this …