Matching Items (1,098)
Filtering by
- All Subjects: Computer Science
Description
The world is filled with systems of entities that collaborate in motion, both natural and engineered. These cooperative distributed systems are capable of sophisticated emergent behavior arising from the comparatively simple interactions of their members. A model system for emergent collective behavior is programmable matter, a physical substance capable of autonomously changing its properties in response to user input or environmental stimuli. This dissertation studies distributed and stochastic algorithms that control the local behaviors of individual modules of programmable matter to induce complex collective behavior at the macroscale. It consists of four parts. In the first, the canonical amoebot model of programmable matter is proposed. A key goal of this model is to bring algorithmic theory closer to the physical realities of programmable matter hardware, especially with respect to concurrency and energy distribution. Two protocols are presented that together extend sequential, energy-agnostic algorithms to the more realistic concurrent, energy-constrained setting without sacrificing correctness, assuming the original algorithms satisfy certain conventions. In the second part, stateful distributed algorithms using amoebot memory and communication are presented for leader election, object coating, convex hull formation, and hexagon formation. The first three algorithms are proven to have linear runtimes when assuming a simplified sequential setting. The final algorithm for hexagon formation is instead proven to be correct under unfair asynchronous adversarial activation, the most general of all adversarial activation models. In the third part, distributed algorithms are combined with ideas from statistical physics and Markov chain design to replace algorithm reliance on memory and communication with biased random decisions, gaining inherent self-stabilizing and fault-tolerant properties. Using this stochastic approach, algorithms for compression, shortcut bridging, and separation are designed and analyzed. Finally, a two-pronged approach to "programming" physical ensembles is presented. This approach leverages the physics of local interactions to pair theoretical abstractions of self-organizing particle systems with experimental robot systems of active granular matter that intentionally lack digital computation and communication. By physically embodying the salient features of an algorithm in robot design, the algorithm's theoretical analysis can predict the robot ensemble's behavior. This approach is applied to phototaxing, aggregation, dispersion, and object transport.
ContributorsDaymude, Joshua (Author) / Richa, Andréa W (Thesis advisor) / Scheideler, Christian (Committee member) / Randall, Dana (Committee member) / Pavlic, Theodore (Committee member) / Gil, Stephanie (Committee member) / Arizona State University (Publisher)
Created2021
Description
Spatial data is fundamental in many applications like map services, land resource management, etc. Meanwhile, spatial data inherently comes with abundant context information because spatial entities themselves possess different properties, e.g., graph or textual information, etc. Among all these compound spatial data, geospatial graph data is one of the most challenging for the complexity of graph data. Graph data is commonly used to model real scenarios and searching for the matching subgraphs is fundamental in retrieving and analyzing graph data. With the ubiquity of spatial data, vertexes or edges in graphs are enriched with spatial location attributes side by side with other non-spatial attributes. Graph-based applications integrate spatial data into the graph model and provide more spatial-aware services. The co-existence of the graph and spatial data in the same geospatial graph triggers some new applications. To solve new problems in these applications, existing solutions develop an integrated system that incorporates the graph database and spatial database engines. However, existing approaches suffer from the architecture where graph data and spatial data are isolated. In this dissertation, I will explain two indexing frameworks, GeoReach and RisoTree, which can significantly accelerate the queries in geospatial graphs. GeoReach includes a query operator that adds spatial data awareness to a graph database management system. In GeoReach, the neighborhood spatial information is summarized and stored on each vertex in the graph. The summarization includes three different structures according to the location distribution. These spatial summaries are utilized to terminate the graph search early.RisoTree is a hierarchical tree structure where each node is represented by a minimum bounding rectangle (MBR). The MBR of a node is a rectangle that encloses all its children. A key difference between RisoTree and RTree is that RisoTree contains pre-materialized subgraph information to each index node. The subgraph information is utilized during the spatial index search phase to prune search paths that cannot satisfy the query graph pattern. The RisoTree index reduces the search space when the spatial filtering phase is performed with relatively light cost.
ContributorsSun, Yuhan (Author) / Sarwat, Mohamed (Thesis advisor) / Tong, Hanghang (Committee member) / Candan, Kasim S (Committee member) / Zhao, Ming (Committee member) / Arizona State University (Publisher)
Created2021
Description
Cyber-Physical Systems (CPS) are becoming increasingly prevalent around the world. Co-simulation of cyber and physical components has shown to be an effective way towards the development of time-sensitive and reliable CPS. Correctly combining continuous models with discrete models for co-simulation can often be challenging. In this thesis, the Functional Markup Interface (FMI) is used to develop an adapter called DEVS-FMI for the DEVS-Suite simulator. The adapter, implemented using JavaFMI 2.0, allows any Functional Mock-Up Unit (FMU) to be co-simulated with a Discrete Event System Specification (DEVS) model. This approach enables taking advantage of the parallel DEVS formalism to model cyber systems and using Modelica to model physical systems. An FMU serves as a slave simulator while the DEVS-Suite serves as a master simulator. The Four-Variable model is used as a guide to define the requirements for the inputs and outputs of actuator and sensor devices used in cyber and physical systems. The input and output data as non-functional abstractions of the sensor and actuator devices. Select cyber and physical parts of an electric scooter are chosen, modeled, simulated, and evaluated using the integrated OpenModelica and the DEVS-Suite simulators. Closely related research is briefly examined and expanding this work with support for implicit state-changes for continuous models and distributed co-simulation is noted.
ContributorsLin, Xuanli (Author) / Sarjoughian, Hessam S (Thesis advisor) / Pedrielli, Giulia (Committee member) / Xue, Guoliang (Committee member) / Arizona State University (Publisher)
Created2021
Description
Cyberspace has become a field where the competitive arms race between defenders and adversaries play out. Adaptive, intelligent adversaries are crafting new responses to the advanced defenses even though the arms race has resulted in a gradual improvement of the security posture. This dissertation aims to assess the evolving threat landscape and enhance state-of-the-art defenses by exploiting and mitigating two different types of emerging security vulnerabilities. I first design a new cache attack method named Prime+Count which features low noise and no shared memory needed.I use the method to construct fast data covert channels. Then, I propose a novel software-based approach, SmokeBomb, to prevent cache side-channel attacks for inclusive and non-inclusive caches based on the creation of a private space in the L1 cache. I demonstrate the effectiveness of SmokeBomb by applying it to two different ARM processors with different instruction set versions and cache models and carry out an in-depth evaluation. Next, I introduce an automated approach that exploits a stack-based information leak vulnerability in operating system kernels to obtain sensitive data. Also, I propose a lightweight and widely applicable runtime defense, ViK, for preventing temporal memory safety violations which can lead attackers to have arbitrary code execution or privilege escalation together with information leak vulnerabilities. The security impact of temporal memory safety vulnerabilities is critical, but,they are difficult to identify because of the complexity of real-world software and the spatial separation of allocation and deallocation code. Therefore, I focus on preventing not the vulnerabilities themselves, but their exploitation. ViK can effectively protect operating system kernels and user-space programs from temporal memory safety violations, imposing low runtime and memory overhead.
ContributorsCho, Haehyun (Author) / Ahn, Gail-Joon (Thesis advisor) / Doupe, Adam (Thesis advisor) / Shoshitaishvili, Yan (Committee member) / Wang, Ruoyu (Committee member) / Wu, Carole-Jean (Committee member) / Arizona State University (Publisher)
Created2021
Description
Many residences from student apartment units to family homes use a range of smart devices to make the day-to-day lives of the residents safer and more convenient. The ability to remotely access these devices has further increased their convenience, but it comes with the increased risk of vulnerable devices being exploited to achieve unauthorized access or to conduct surveillance on the users. This highlights the need for an access control system to securely restrict home device access to authorized users only. Existing approaches for securing smart homes use less secure authentication methods, do not allow for data ownership or fine-grained access control, and do not reliably store credential modification records, access records, or access policy modification records. These records can be a valuable resource to have available in the case of a security incident.In this thesis, a secure and efficient remote mutual authentication system with fine-grained access control integrating blockchain and digital signatures to authenticate users, authenticate the home gateway, and provide reliable auditing of the credential modifications, access history, and access policy modifications of the devices is presented. The immutability and verifiability properties of blockchain make it useful for securely storing these records. In this approach, a smart contract is created in the blockchain to keep track of authorized users, manage the access policy, and record requests for access or control of the home devices. A private blockchain is used to provide trust and privacy, which is necessary for a smart home system. Elliptic curve digital signatures are used to verify identities because the shorter key sizes and signature times are more adapted to Internet of Things contexts. The approach presented in this thesis is better than existing approaches because it provides fine-grained access control, and reliably stores credential modification records, access records, and access policy modification records. The approach was implemented and evaluated using Hyperledger, a private open-source blockchain, and the results show that this approach has significant additional security benefits with negligible additional overhead cost.
ContributorsVuong, Anna (Author) / Yau, Stephen S (Thesis advisor) / Doupe, Adam (Committee member) / Ghayekhloo, Samira (Committee member) / Arizona State University (Publisher)
Created2021
Description
In classification applications, such as medical disease diagnosis, the cost of one type of error (false negative) could greatly outweigh the other (false positive) enabling the need of asymmetric error control. Due to this unique nature of the problem, traditional machine learning techniques, even with much improved accuracy, may not be ideal as they do not provide a way to control the false negatives below a certain threshold. To address this need, a classification algorithm that can provide asymmetric error control is proposed. The theoretical foundation for this algorithm is based on Neyman-Pearson (NP) Lemma and it is complemented with sample splitting and order statistics to pick a threshold that enables an upper bound on the number of false negatives. Additionally, this classifier addresses the imbalance of the data, which is common in medical datasets, by using Hellinger distance as the splitting criterion. This eliminates the need of sampling methods, which add complexity and the need for parameter selection. This approach is used to create a novel tree-based classifier that enables asymmetric error control. Applications, such as prediction of the severity of cardiac arrhythmia, require classification over multiple classes. The NP oracle inequalities for binary classes are not immediately applicable for the multiclass NP classification, leading to a multi-step procedure proposed in this dissertation to extend the algorithm in the context of multiple classes. This classifier is used in predicting various forms of cardiac disease for both binary and multi-class classification problems with not only comparable accuracy metrics but also with full control over the number of false negatives. Moreover, this research allows us to pick the threshold for the classifier in a data adaptive way. This dissertation also shows that this methodology can be extended to non medical applications that require classification with asymmetric error control.
ContributorsBokhari, Wasif (Author) / Bansal, Ajay (Thesis advisor) / Zhang, Yu (Committee member) / Yang, Yezhou (Committee member) / Bahadur, Faisal (Committee member) / Arizona State University (Publisher)
Created2021
Description
REACT is a distributed resource allocation protocol that can be used to negotiate airtime among nodes in a wireless network. In this thesis, REACT is extended to support quality of service (QoS) airtime in an updated version called REACT QoS . Nodes can request the higher airtime class to receive priority in the network. This differentiated service is provided by using the access categories (ACs) provided by 802.11, where one AC represents the best effort (BE) class of airtime and another represents the QoS class. Airtime allocations computed by REACT QoS are realized using an updated tuning algorithm and REACT QoS is updated to allow for QoS airtime along multi-hop paths. Experimentation on the w-iLab.t wireless testbed in an ad-hoc setting shows that these extensions are effective. In a single-hop setting, nodes requesting the higher class of airtime are guaranteed their allocation, with the leftover airtime being divided fairly among the remaining nodes. In the multi-hop scenario, REACT QoS is shown to perform better in each of airtime allocation and delay, jitter, and throughput, when compared to 802.11. Finally, the most influential factors and 2-way interactions are identified through the use of a locating array based screening experiment for delay, jitter, and throughput responses. The screening experiment includes a factor on how the channel is partitioned into data and control traffic, and its effect on the responses is determined.
ContributorsKulenkamp, Daniel J (Author) / Syrotiuk, Violet R (Thesis advisor) / Colbourn, Charles J (Committee member) / Tinnirello, Ilenia (Committee member) / Arizona State University (Publisher)
Created2021
Description
Apache Spark is one of the most widely adopted open-source Big Data processing engines. High performance and ease of use for a wide class of users are some of the primary reasons for the wide adoption. Although data partitioning increases the performance of the analytics workload, its application to Apache Spark is very limited due to layered data abstractions. Once data is written to a stable storage system like Hadoop Distributed File System (HDFS), the data locality information is lost, and while reading the data back into Spark’s in-memory layer, the reading process is random which incurs shuffle overhead. This report investigates the use of metadata information that is stored along with the data itself for reducing shuffle overload in the join-based workloads. It explores the Hyperspace library to mitigate the shuffle overhead for Spark SQL applications. The article also introduces the Lachesis system to solve the shuffle overhead problem. The benchmark results show that the persistent partition and co-location techniques can be beneficial for matrix multiplication using SQL (Structured Query Language) operator along with the TPC-H analytical queries benchmark. The study concludes with a discussion about the trade-offs of using integrated stable storage to layered storage abstractions. It also discusses the feasibility of integration of the Machine Learning (ML) inference phase with the SQL operators along with cross-engine compatibility for employing data locality information.
ContributorsBarhate, Pratik Narhar (Author) / Zou, Jia (Thesis advisor) / Zhao, Ming (Committee member) / Elsayed, Mohamed Sarwat (Committee member) / Arizona State University (Publisher)
Created2021
Description
This work considers the task of vision-and-language inference (VLI): predicting whether an inputthe sentence is true for given images or videos and starts with an investigation of model robustness to
a set of 13 linguistic transformations, categorized as Semantics-Preserving or Semantics-Inverting
based on whether they change the meaning of the sentence. It is observed that existing VLI models
degenerate to close-to-random performance when tested on these linguistic transformations which
include simple phenomena such as synonyms, antonyms, negation, swap-ping of subject and object,
paraphrasing, and the substitutions of pronouns, comparatives, and numbers.
This observation is utilized to design STAT(Semantics-Transformed Adversarial Training) { a
model-agnostic and task-agnostic min-max optimization algorithm, with an inner maximization
that utilizes semantic perturbations of in-put sentences to nd adversarial samples and an outer
maximization that updates model parameters. Extensive experiments on three benchmark datasets
(NLVR2, VIOLIN, VQA \Yes-No") not only demonstrate large gains in robustness to adversarial
input sentences but also show model-agnostic performance improvements. This works also presents
the suite of linguistic transformations as a robustness benchmark that may benet future research
in vision and language robustness.
ContributorsChaudhary, Abhishek (Author) / Yang, Yezhou Dr. (Thesis advisor) / Li, Baoxin Dr. (Committee member) / Baral, Chitta Dr. (Committee member) / Arizona State University (Publisher)
Created2021
Description
A distributed wireless sensor network (WSN) is a network of a large number of lowcost,multi-functional sensors with power, bandwidth, and memory constraints, operating
in remote environments with sensing and communication capabilities. WSNs
are a source for a large amount of data and due to the inherent communication and
resource constraints, developing a distributed algorithms to perform statistical parameter
estimation and data analysis is necessary. In this work, consensus based
distributed algorithms are developed for distributed estimation and processing over
WSNs. Firstly, a distributed spectral clustering algorithm to group the sensors based
on the location attributes is developed. Next, a distributed max consensus algorithm
robust to additive noise in the network is designed. Furthermore, distributed spectral
radius estimation algorithms for analog, as well as, digital communication models
are developed. The proposed algorithms work for any connected graph topologies.
Theoretical bounds are derived and simulation results supporting the theory are also
presented.
ContributorsMuniraju, Gowtham (Author) / Tepedelenlioğlu, Cihan (Thesis advisor) / Spanias, Andreas (Thesis advisor) / Berisha, Visar (Committee member) / Jayasuriya, Suren (Committee member) / Arizona State University (Publisher)
Created2021