Computer Sciences Commons^™

Determining Solution Space Characteristics For Real-Time Strategy Games And Characterizing Winning Strategies, Gary B. Lamont, Kurt Weissgerber, Brett J. Borghetti, Gilbert L. Peterson

Faculty Publications

The underlying goal of a competing agent in a discrete real-time strategy (RTS) game is to defeat an adversary. Strategic agents or participants must define an a priori plan to maneuver their resources in order to destroy the adversary and the adversary's resources as well as secure physical regions of the environment. This a priori plan can be generated by leveraging collected historical knowledge about the environment. This knowledge is then employed in the generation of a classification model for real-time decision-making in the RTS domain. The best way to generate a classification model for a complex problem domain depends …

Enhance And "Mobilize" The Library Catalog With Cloud Services, Jolinda Thompson

Himmelfarb Library Faculty Publications

Explores new products and services that make it possible to enhance and mobilize traditional library catalogs.

Scalable Correct Memory Ordering Via Relativistic Programming, Josh Triplett, Philip William Howard, Paul E. Mckenney, Jonathan Walpole

Computer Science Faculty Publications and Presentations

We propose and document a new concurrent programming model, relativistic programming. This model allows readers to run concurrently with writers, without blocking or using expensive synchronization. Relativistic programming builds on existing synchronization primitives that allow writers to wait for current readers to finish with minimal reader overhead. Our methodology models data structures as graphs, and reader algorithms as traversals of these graphs; from this foundation we show how writers can implement arbitrarily strong ordering guarantees for the visibility of their writes, up to and including total ordering.

Generalized Construction Of Scalable Concurrent Data Structures Via Relativistic Programming, Josh Triplett, Paul E. Mckenney, Philip W. Howard, Jonathan Walpole

Computer Science Faculty Publications and Presentations

We present relativistic programming, a concurrent programming model based on shared addressing, which supports efficient, scalable operation on either uniform shared-memory or distributed shared- memory systems. Relativistic programming provides a strong causal ordering property, allowing a series of read operations to appear as an atomic transaction that occurs entirely between two ordered write operations. This preserves the simple immutable-memory programming model available via mutual exclusion or transactional memory. Furthermore, relativistic programming provides joint-access parallelism, allowing readers to run concurrently with a writer on the same data. We demonstrate a generalized construction technique for concurrent data structures based on relativistic programming, …

Amid The Vipers: Establishing Malware's Position Within The Information Ecosystem, Shawn Louis Everett Robertson

Computer Science and Software Engineering

The paper consists of a detailed examination of malware broken down into three main sections.

1. Introduction: Malware in the World Today. Begins with a definition of terms, examination of the types of malware, research into historical pieces of malicious code, a detailed analysis of the attackers, why malware is so prevalent, and why it is so hard to defend against. This section finishes with a comparison of reasons to create and not to create malware.
2. Background: "Good" Pieces of Malware. Examination of what makes malware effective. Analysis of the existing CVSS standard and proposal of the alternative VIPERS classification system. …

Analyses, Simulations, And Physical Modeling Validation Of Levee And Embankment Erosion, Zhongxian Chen, Christopher S. Stuetzle, Barbara Cutler, Jared Gross, W. Randolph Franklin, Thomas F. Zimmie

Computer and Data Science Faculty Publications

We present a computer simulation of hydraulic erosion on levees, dams, and earth embankments, with emphasis on rill and gully initiation and propagation. We focus on erosion features that occur after an earthen structure is overtopped. We have developed a 3D fluid and hydraulic erosion simulation engine using Smoothed Particle Hydrodynamics (SPH). We present the results of digital simulations for different soil types. Furthermore, small-scale physical models of levees composed of different soils were constructed and tested experimentally. The digital simulations are compared to physical experimental results to validate the computer models.

Recognition Situations Using Extended Dempster-Shafer Theory, Susan Mckeever

Other resources

Weiser’s [111] vision of pervasive computing describes a world where technology seamlessly integrates into the environment, automatically responding to peoples’ needs. Underpinning this vision is the ability of systems to automatically track the situation of a person. The task of situation recognition is critical and complex: noisy and unreliable sensor data, dynamic situations, unpredictable human behaviour and changes in the environment all contribute to the complexity. No single recognition technique is suitable in all environments. Factors such as availability of training data, ability to deal with uncertain information and transparency to the user will determine which technique to use in …

Advances In Software Engineering, Alban Krasniqi

Theses and Dissertations

Inxhinieria Softuerike është aplikimi i një qasje sistematike të disiplinuar, të matshme për zhvillimin, operimin dhe mirëmbajtjen e softuerit. Për rreth çdo aktivitet është një strukturë komplekse të cilat janë të mbështetura dhe të lidhura me aktivitetet dhe shqetësimet ekonomike, organizative, menaxheriale dhe një strukture komplekse të kufizuar. Ne ketë punim jemi munduar qe ti trajtojmë disa tema qe i gjejmë të trajtuara rrallë neper literaturat qe ofrohen sot ne fushën e inxhinierisë softuerike . Duke pas parasysh se Inxhinieria Softuerike përfshin një diapazon të gjere mirëpo nder pozitat me kryesore është ajo e menaxhimit te projekteve ne me ane …

Reactive Routing In Hidra Networks, Scott Michael Marshall

Computer Engineering

In recent years, the Internet has grown so large that the future scalability of the Internet has become a major concern. The two primary scalability concerns are the size of the forwarding table and the ability for BGP to converge while distributing hundreds of thousands of routes.

HIDRA is a new Internet routing architecture that is backwards-compatible with existing routing technologies and protocols that focuses on feasibility-of-implementation. HIDRA remedies the first Internet scalability concern by proposing a means to reduce the number of entries in the default-free zone (DFZ) forwarding table.

This project extends HIDRA by designing a complete reactive …

Certificateless Public Key Encryption: A New Generic Construction And Two Pairing-Free Schemes, Guomin Yang, Chik How Tan

Research Collection School Of Computing and Information Systems

The certificateless encryption (CLE) scheme proposed by Baek, Safavi-Naini and Susilo is computation-friendly since it does not require any pairing operation. Unfortunately, an error was later discovered in their security proof and so far the provable security of the scheme remains unknown. Recently, Fiore, Gennaro and Smart showed a generic way (referred to as the FGS transformation) to transform identity-based key agreement protocols to certificateless key encapsulation mechanisms (CL-KEMs). As a typical example, they showed that the pairing-free CL-KEM underlying Baek et al.’s CLE can be “generated” by applying their transformation to the Fiore–Gennaro (FG) identity-based key agreement (IB-KA) protocol.In …

Unified Framework For Development, Deployment And Robust Testing Of Neuroimaging Algorithms, Alark Joshi, Dustin Scheinost, Hirohito Okuda, Dominique Belhachemi, Isabella Murphy, Lawrence H. Staib, Xenophon Papademetris

Computer Science Faculty Publications and Presentations

Developing both graphical and commandline user interfaces for neuroimaging algorithms requires considerable effort. Neuroimaging algorithms can meet their potential only if they can be easily and frequently used by their intended users. Deployment of a large suite of such algorithms on multiple platforms requires consistency of user interface controls, consistent results across various platforms and thorough testing.

We present the design and implementation of a novel object-oriented framework that allows for rapid development of complex image analysis algorithms with many reusable components and the ability to easily add graphical user interface controls. Our framework also allows for simplified yet robust …

Identifying Unusual Days, Minkyong Kim, David Kotz

Dartmouth Scholarship

Pervasive applications such as digital memories or patient monitors collect a vast amount of data. One key challenge in these systems is how to extract interesting or unusual information. Because users cannot anticipate their future interests in the data when the data is stored, it is hard to provide appropriate indexes. As location-tracking technologies, such as global positioning system, have become ubiquitous, digital cameras or other pervasive systems record location information along with the data. In this paper, we present an automatic approach to identify unusual data using location information. Given the location information, our system identifies unusual days, that …

Social Network Analysis Plugin (Snap) For Mesh Networks, Soumendra Nanda, David Kotz

Dartmouth Scholarship

In a network, bridging nodes are those nodes that from a topological perspective, are strategically located between highly connected regions of nodes. Thus, they have high values of the Bridging Centrality (BC) metric. We recently introduced the Localized Bridging Centrality (LBC) metric, which can identify such nodes via distributed computation, yet has an accuracy equal to that of the centralized BC metric. The LBC and BC metrics are based on the Social Network Analysis (SNA) metric "betweenness centrality". We now introduce a new SNA metric that is more suitable for use in wireless mesh networks: the Localized Load-aware Bridging Centrality …

Abstract Answer Set Solvers With Backjumping And Learning, Yuliya Lierler

Computer Science Faculty Publications

Nieuwenhuis et al. (2006. Solving SAT and SAT modulo theories: From an abstract Davis-Putnam-Logemann-Loveland procedure to DPLL(T). Journal of the ACM 53(6), 937977 showed how to describe enhancements of the Davis–Putnam–Logemann–Loveland algorithm using transition systems, instead of pseudocode. We design a similar framework for several algorithms that generate answer sets for logic programs: SMODELS, SMODELS_cc, asp-sat with Learning (CMODELS), and a newly designed and implemented algorithm sup. This approach to describe answer set solvers makes it easier to prove their correctness, to compare them, and to design new systems.

An Approach To Nearest Neighboring Search For Multi-Dimensional Data, Yong Shi, Li Zhang, Lei Zhu

Faculty Articles

Finding nearest neighbors in large multi-dimensional data has always been one of the research interests in data mining field. In this paper, we present our continuous research on similarity search problems. Previously we have worked on exploring the meaning of K nearest neighbors from a new perspective in PanKNN [20]. It redefines the distances between data points and a given query point Q, efficiently and effectively selecting data points which are closest to Q. It can be applied in various data mining fields. A large amount of real data sets have irrelevant or obstacle information which greatly affects the effectiveness …

Characterizing The Arc, Paul Bankston

Mathematics, Statistics and Computer Science Faculty Research and Publications

We offer a mathematical logic framework for talking about when a given topological space is characterizable relative to a “class of its peers.” The framework involves a relational alphabet for which there is a natural way of assigning relational structures to spaces in the peer class; and a putative characterization of the given space consists of a set of first-order sentences over that alphabet, all true for the space. The attempted characterization is a success if any peer space satisfying all the sentences is inevitably homeomorphic to the given space.

For example, it has long been known that the arc …

Common Hypercyclic Vectors For The Conjugate Class Of A Hypercyclic Operator, Kit C. Chan, Rebecca Sanders

Mathematics, Statistics and Computer Science Faculty Research and Publications

Given a separable, infinite dimensional Hilbert space, it was recently shown by the authors that there is a path of chaotic operators, which is dense in the operator algebra with the strong operator topology, and along which every operator has the exact same dense G_δ set of hypercyclic vectors. In the present work, we show that the conjugate set of any hypercyclic operator on a separable, infinite dimensional Banach space always contains a path of operators which is dense with the strong operator topology, and yet the set of common hypercyclic vectors for the entire path is a dense …

Strongly Secure Certificateless Key Exchange Without Pairing, Guomin Yang, Chik How Tan

Research Collection School Of Computing and Information Systems

In certificateless cryptography, a user secret key is derived from two partial secrets: one is the identity-based secret key (corresponding to the user identity) generated by a Key Generation Center (KGC), and the other is the user selfgenerated secret key (corresponding to a user self-generated and uncertified public key). Two types of adversaries are considered for certificateless cryptography: a Type-I adversary who can replace the user self-generated public key (in transmission or in a public directory), and a Type-II adversary who is an honest-but-curious KGC. In this paper, we present a formal study on certificateless key exchange (CLKE). We show …

Signal And Noise In Complex-Valued Sense Mr Image Reconstruction, Daniel B. Rowe, Iain P. Bruce

Mathematics, Statistics and Computer Science Faculty Research and Publications

In fMRI, brain images are not measured instantaneously and a volume of images can take two seconds to acquire at a low 64x64 resolution. Significant effort has been put forth on many fronts to decrease image acquisition time including parallel imaging. In parallel imaging, sub-sampled spatial frequency points are measured in parallel and combined to form a single image. Measurement time is decreased at the expense of increased image reconstruction difficulty and time. One significant parallel imaging technique known as SENSE utilizes a complex-valued regression coefficient estimation process with transposes replaced by conjugate transposes. However, in SENSE the noise structure …

Semidistributive Inverse Semigroups, Ii, Kyeong Hee Cheong, Peter R. Jones

Mathematics, Statistics and Computer Science Faculty Research and Publications

The description by Johnston-Thom and the second author of the inverse semigroups S for which the lattice LJ(S) of full inverse subsemigroups of S is join semidistributive is used to describe those for which (a) the lattice L(S) of all inverse subsemigroups or (b) the lattice lo(S) of convex inverse subsemigroups have that property. In contrast with the methods used by the authors to investigate lower semimodularity, the methods are based on decompositions via G_S, the union of the subgroups of the semigroup (which is necessarily cryptic).

Authenticated Key Exchange Under Bad Randomness, Guomin Yang, Shanshan Duan, Duncan S. Wong, Chik How Tan, Huaxiong Wang

Research Collection School Of Computing and Information Systems

We initiate the formal study on authenticated key exchange (AKE) under bad randomness. This could happen when (1) an adversary compromises the randomness source and hence directly controls the randomness of each AKE session; and (2) the randomness repeats in different AKE sessions due to reset attacks. We construct two formal security models, Reset-1 and Reset-2, to capture these two bad randomness situations respectively, and investigate the security of some widely used AKE protocols in these models by showing that they become insecure when the adversary is able to manipulate the randomness. On the positive side, we propose simple but …

Advanced I/O Techniques For Efficient And Highly Available Process Crash Recovery Protocols, Jason Warren Cornwell

Theses and Dissertations

As the number of CPU cores in high-performance computing platforms continues to grow, the availability and reliability of these systems become a primary concern. As such, some solutions are physical (ie. power backup) and some are software driven. Lawrence Berkeley National Laboratory has created a system-level fault-tolerant checkpoint/restart implementation for Linux Clusters. This allows processes to restart computations at the last known checkpoint in the event the system crashes. The checkpoint data creation is highly dependent on system input and output operations. This paper proposes: (i) a technique to improve the efficiency of these I/O operations and (ii) an alternative …

Jshield: A Java Anti-Reversing Tool, Deepti Kundu

Master's Projects

Java is a platform independent language.    Java programs can be executed on any machine, irrespective of its hardware or the operating system, as long as a Java virtual machine for that platform is available. A Java compiler converts the source code into „bytecode‟ instead of native binary machine code. This bytecode contains a lot of information from and about the source code, which makes it easy to decompile, and hence, vulnerable to „reverse engineering attacks‟. In addition to the obvious security implications, businesses and the wider software engineering community also risk widespread IP theft - proprietary algorithms, for example, that …

Multi-Objective Zone Mapping In Large-Scale Distributed Virtual Environments, Nguyen Binh Duong Ta, Suiping Zhou, Wentong Cai, Xueyan Tang, Rassul Avani

Research Collection School Of Computing and Information Systems

In large-scale distributed virtual environments (DVEs), the NP-hard zone mapping problem concerns how to assign distinct zones of the virtual world to a number of distributed servers to improve overall interactivity. Previously, this problem has been formulated as a single-objective optimization problem, in which the objective is to minimize the total number of clients that are without QoS. This approach may cause considerable network traffic and processing overhead, as a large number of zones may need to be migrated across servers. In this paper, we introduce a multi-objective approach to the zone mapping problem, in which both the total number …

Proof System Representations Of Degrees Of Disjoint Np-Pairs, Liyu Zhang

Computer Science Faculty Publications

Let D be a set of many-one degrees of disjoint NP-pairs. We define a proof system representation of D to be a set of propositional proof systems P such that each degree in D contains the canonical NP-pair of a corresponding proof system in P and the degree structure of D is reflected by the simulation order among the corresponding proof systems in P. We also define a nesting representation of D to be a set of NP-pairs S such that each degree in D contains a representative NP-pair in S and the degree structure of D is reflected by …

Chameleon All-But-One Tdfs And Their Application To Chosen-Ciphertext Security, Junzuo Lai, Robert H. Deng, Shengli Liu

Research Collection School Of Computing and Information Systems

In STOC’08, Peikert and Waters introduced a new powerful primitive called lossy trapdoor functions (LTDFs) and a richer abstraction called all-but-one trapdoor functions (ABO-TDFs). They also presented a black-box construction of CCA-secure PKE from an LTDF and an ABO-TDF. An important component of their construction is the use of a strongly unforgeable one-time signature scheme for CCA-security.In this paper, we introduce the notion of chameleon ABO-TDFs, which is a special kind of ABO-TDFs. We give a generic as well as a concrete construction of chameleon ABO-TDFs. Based on an LTDF and a chameleon ABO-TDF, we presented a black-box construction, free …

Modeling Link Formation Behaviors In Dynamic Social Networks, Viet-An Nguyen, Cane Wing-Ki Leung, Ee Peng Lim

Research Collection School Of Computing and Information Systems

Online social networks are dynamic in nature. While links between users are seemingly formed and removed randomly, there exists some interested link formation behaviors demonstrated by users performing link creation and removal activities. Uncovering these behaviors not only allows us to gain deep insights of the users, but also pave the way to decipher how social links are formed. In this paper, we propose a general framework to define user link formation behaviors using well studied local link structures (i.e., triads and dyads) in a dynamic social network where links are formed at different timestamps. Depending on the role a …

An Energy Efficient Quality Adaptive Multi-Modal Sensor Framework For Context Recognition, Nirmalya Roy, Archan Misra, Christine Julien, Sajal K. Das, Jit Biswas

Research Collection School Of Computing and Information Systems

Proliferation of mobile applications in unpredictable and changing environments requires applications to sense and act on changing operational contexts. In such environments, understanding the context of an entity is essential for adaptability of the application behavior to changing situations. In our view, context is a high-level representation of a user or entity’s state and can capture activities, relationships, capabilities, etc. Inherently, however, these high-level context measures are difficult to sense directly and instead must be inferred through the combination of many data sources. In pervasive computing environments where this context is of significant importance, a multitude of sensors is already …

Restfs: The Filesystem As A Connector Abstraction For Flexible Resource And Service Composition, Joseph P. Kaylor, Konstantin Läufer, George K. Thiruvathukal

Computer Science: Faculty Publications and Other Works

The broader context for this chapter comprises business scenarios requiring resource and/or service composition, such as (intra-company) enterprise application integration (EAI) and (inter-company) web service orchestration. The resources and services involved vary widely in terms of the protocols they support, which typically fall into remote procedure call (RPC)~\citeBirrell84implementingremote, resource-oriented (HTTP~\citeFielding96hypertexttransfer and WEBDAV~\citewebdav) and message-oriented protocols. By recognizing the similarity between web-based resources and the kind of resources exposed in the form of filesystems in operating systems, we have found it feasible to map the former to the latter using a uniform, configurable connector layer. Once a remote resource has been …

Restfs: Resources And Services Are Filesystems, Too, Joseph P. Kaylor, Konstantin Läufer, George K. Thiruvathukal

Computer Science: Faculty Publications and Other Works

We have designed and implemented RestFS, a software frame-work that provides a uniform, configurable connector layerfor mapping remote web-based resources to local filesystem-based resources, recognizing the similarity between thesetwo types of resources. Such mappings enable programmaticaccess to a resource, as well as composition of two or moreresources, through the local operating system’s standardfilesystem application programming interface (API), script-able file-based command-line utilities, and inter-process com-munication (IPC) mechanisms. The framework supports au-tomatic and manual authentication. We include several ex-amples intended to show the utility and practicality of ourframework.