Matei Ripeanu

The rapid increase in connected data from various sources such as the World Wide Web, social networks, and financial transactions has led to the widespread use of graph-based representations for data analysis of these networks. However, traditional high-performance computing (HPC) solutions designed for static graphs are inefficient and impractical for dynamic graphs that evolve over time. This approach leads to high overheads, loss of information between snapshots, and potential correctness issues.The demand for fast, real-time analytics on continuously evolving real-world systems at a massive scale has become critical for applications such as online recommendations, financial fraud detection, and counter-terrorism. For example, social media networks like Facebook handle potentially millions of interactions per second, and payment networks like Visa process thousands of transactions per second. To address these challenges, my dissertation focuses on the opportunities and challenges of analyzing dynamic graphs in real-time, offering an infrastructure-algorithm co-design for dynamic graph analytics at scale.To this end, I develop and present a pattern for dynamic graph algorithms, and a supporting software infrastructure architecture, that together form a cohesive real-time graph analysis model. My algorithm pattern is designed to be amenable to distributed systems with concepts such as message passing, asynchronicity, and termination, while considering the timeliness requirements for real-time analysis. The infrastructure architecture considers real-world properties of dynamic data generation and hardware constraints, aiming for versatility, performance, and scalability. It supports dynamic graph topology evolution and provides interfaces for expressing algorithms for dynamic graph analysis and collecting results during runtime.I demonstrate that many common static graph algorithms can be re-designed for dynamic processing and real-time analysis, and can be built and scaled efficiently. My dynamic graph model offers advantages over static designs, such as low-cost updates to the graph and the ability to observe algorithm results before or after topology modifications. The implementation of my model shows near-linear scalability in performance, and supports real-time analysis at potentially orders of magnitude higher evolution rates compared to alternative designs; providing a generic, scalable, and performant solution for dynamic graph analysis, addressing the challenges of analyzing large-scale, continuously evolving network data in real-time.

View record

Fueled by the massive amount of data and meta-data harvested by large-scale online service providers, two trends stand out: the broad adoption of machine learning particularly for cybersecurity defenses, and the growing pains of temporal graph analytics particularly for dynamically evolving systems.In this dissertation, my overarching goal is to explore novel ways: to effectively harness this harvested data to evidently improve the security of online platforms in general and their most vulnerable users in particular, and to explicitly model the temporal evolution of this data to efficiently enable business use cases that can not be served by existing graph analytics systems. To that end, I advocate for a paradigm shift across two high impact domains: cybersecurity and graph analytics.On the one hand, existing cybersecurity defenses are reactive, and victim-agnostic: they are predicated on identifying the attacks/attackers, and do not take user characteristics into account. In contrast, I propose a proactive approach based on identifying the vulnerable population, and leveraging this information to improve the security of the platform in general and the most vulnerable users in particular.To that end, I approach harnessing the vulnerable population under a victim-centric defense paradigm while contrasting against conventional defenses, and demonstrate its feasibility using four months of production data encompassing billions of events from hundreds of millions of users.To my knowledge, I am the first to propose and discuss such a defense paradigm.On the other hand, existing graph analytics systems are mostly static, and non-temporal: they are not fully able to support modeling systems that evolve dynamically over time while supporting the queries (including current state, historical, and audit queries) required by today's use cases. In contrast, I contend that future graph analytics systems should be: online, dynamic, and employ bitemporal modeling at their core. To that end, I examine the use cases that are an ideal match for an online bitemporal dynamic graph analytics system, explore the design trade-off space, and develop and characterize several designs targeting different points within that space.To my knowledge, I am the first to propose, develop, and characterize such a system end-to-end.

View record

Recent Edge applications (e.g., machine learning inference) are becoming more sophisticated and computationally demanding. To meet their Quality of Service (QoS) objectives, today’s heterogeneous Edge platforms (e.g., NVIDIA Jetson platform) incorporate several architectural innovations. One that stands out is the wide frequency configuration space (more than a dozen frequency levels per processing unit spanning a 10x max-min ratio). We postulate that this can be harnessed to better navigate the trade-off space between performance and power consumption. This dissertation makes progress towards harnessing frequency scaling on Edge platforms. We start by exploring the potential gains from frequency scaling on the NVIDIA Jetson platform. To this end, we develop an empirical methodology to characterize the performance and power consumption behavior of the Jetson platform under different frequency configurations. Our characterization indicates that indeed there is an opportunity to improve performance and/or energy-efficiency with careful frequency configuration selection. However, one challenge is to estimate the impact of the frequency configuration choice on performance and power consumption of the workload.To overcome this challenge, we employ machine learning techniques to build performance and power consumption models for the target workload. While developing these models, we find that the quality of their predictions depends on where the models are deployed (even if they are deployed on identical devices with identical software stacks). This leads us to postulate that variability in performance and power consumption among nominally identical Edge platforms exists and is sizeable. To investigate this hypothesis, we develop statistical tools that allow developers to detect, quantify, categorize, and compare variability. Then we present a set of actions one can take to mitigate the impact of variability. We evaluate all the techniques and approaches on two clusters of popular Edge platforms - the Jetson AGX and Nano.Finally, we focus on developing variability-aware performance and powerconsumption models. We show that not accounting for variability can severely impact the quality of predictions. The evaluation of the models shows that accounting for inter-node variability improves the Root Mean Square Error (RMSE) by 9.5% and 31.9% for runtime and power models respectively.

View record

Transient hardware faults have become one of the major concerns affecting the reliability of modern high-performance computing (HPC) systems. They can cause failure outcomes for applications, such as crashes and silent data corruptions (SDCs) (i.e. the application produces an incorrect output). To mitigate the impact of these failures, HPC applications need to adopt fault tolerance techniques.The most common practices of fault tolerance techniques include (i) characterization techniques, such as fault injection and architectural vulnerability factor (AVF)/program vulnerability factor (PVF) analysis; (ii) run-time error detection techniques; and (iii) error recovery techniques. However, these approaches have the following shortcomings: (i) fault injections are generally time-consuming andlack predictive power, while the AVF/PVF analysis offers low accuracy; (ii) prior techniques often do not fully exploit the program’s error resilience characteristics; and (iii) the application constantly pays a performance/storage overhead.This dissertation proposes comprehensive approaches to improve the above techniques in terms of effectiveness and efficiency. In particular, this dissertation makes the following contributions: First, it proposes ePVF, a methodology that distinguishes crash-causing bits from the architecturally correct execution (ACE) bits and obtains a closer estimate of the SDC rate than PVF analysis (by 45% to 67%). To reduce the overall analysis time, it samples representative patterns from ACE bits and obtains a good approximation (less than 1% error) for the overall prediction. This dissertation applies the ePVF methodology to error detection, which leads to a 30% lower SDC rate than well-accepted hot-path instruction duplication.Second, this dissertation combines the roll-forward recovery and the roll-back recovery schemes and demonstrates the improvement in the overall efficiency of the C/R with two systems: LetGo (for faults affecting computational components) and BonVoision (for faults affecting DRAM memory). Overall, LetGo is able to elide 62% of the crashes caused by computational faults and convert them to continued execution (out of these 80% result in correct output while a majority of the rest fall back on the traditional roll-back recovery technique). BonVoision is able to continue to completion 30% of the DRAM memory detectable but uncorrectable errors (DUEs).

View record

Pattern matching in graphs, that is finding subgraphs that match a smaller template graph within the large background graph is fundamental to graph analysis and serves a rich set of applications. Unfortunately, existing solutions have limited scalability, are difficult to parallelize, support only a limited set of search patterns, and/or focus on only a subset of the real-world problems. This dissertation explores avenues toward designing a scalable solution for subgraph pattern matching. In particular, this work targets practical pattern matching scenarios in large-scale metadata graphs (also known as property graphs) and designs solutions for distributed memory machines that address the two categories of matching problems, namely, exact and approximate matching. This work presents a novel algorithmic pipeline that bases pattern matching on constraint checking. The key intuition is that each vertex or edge participating in a match has to meet a set of constraints specified by the search template. The pipeline iterates over these constraints to eliminate all the vertices and edges that do not participate in any match, and reduces the background graph to the complete set of only the matching vertices and edges. Additional analysis can be performed on this reduced graph, such as full match enumeration. Furthermore, a vertex-centric formulation for this constraint checking algorithm exists, and this makes it possible to harness existing high-performance, vertex-centric graph processing frameworks.The key contributions of this dissertation are solution design following this constraint checking approach for exact and a class of edit-distance based approximate matching, and experimental evaluation to demonstrate effectiveness of the respective solutions. To this end, this work presents design and implementation of distributed vertex-centric, asynchronous algorithms that guarantee a solution with 100% precision and 100% recall for arbitrary search templates.Through comprehensive evaluation, this work provides evidence that the scalability and performance advantages of the proposed approach are significant. The highlights are scaling experiments on massive-scale real-world (up to 257 billion edges) and synthetic (up to 4.4 trillion edges) graphs, and at scales (1,024 compute nodes), orders of magnitude larger than used in the past for similar problems.

View record

Future high-performance computing systems will be hybrid; they will include processors optimized for sequential processing and massively-parallel accelerators. Platforms based on Graphics Processing Units (GPUs) are an example of this hybrid architecture, they integrate commodity CPUs and GPUs. This architecture promises intriguing opportunities: within the same dollar or energy budget, GPUs offer a significant increase in peak processing power and memory bandwidthcompared to traditional CPUs, and are, at the same time, generally-programmable.The adoption of GPU-based platforms, however, faces a number of challenges, including the characterization of time/space/power tradeoffs, the development of new algorithms that efficiently harness the platform and abstracting the accelerators in a generic yet efficient way to simplify the task of developing applications on such hybrid platforms.This dissertation explores solutions to the abovementioned challenges in the context of an important class of applications, namely irregular applications.Compared to regular applications, irregular applications have unpredictable memory access patterns and typically use reference-based data structures, such as trees or graphs; moreover, new applications in this class operate on massive datasets.Using novel workload partitioning techniques and by employing datastructures that better match the hybrid platform characteristics, this work demonstrates that significant performance gains, in terms of both time to solution and energy, can be obtained when partitioning the irregular workload to be processed concurrently on the CPU and the GPU.

View record

The open nature of the Web, online social networks (OSNs) in particular, makes it possible to design socialbots—automationsoftware that controls fake accounts in a target OSN, and has the ability to perform basic activities similar to those of real users. In the wrong hands, socialbots can be used to infiltrate online communities, build up trust over time, and then engage in various malicious activities.This dissertation presents an in-depth security analysis of malicious socialbots on the Web, OSNs in particular. The analysis focuses on two main goals: (1) to characterize and analyze the vulnerability of OSNs to cyber attacks by malicious socialbots, social infiltration in particular, and (2) to design and evaluate a countermeasure to efficiently and effectively defend against socialbots.To achieve these goals, we first studied social infiltration as an organized campaign operated by a socialbot network (SbN)—a group of programmable socialbots that are coordinated by an attacker in a botnet-like fashion. We implemented a prototypical SbN consisting of 100 socialbots and operated it on Facebook for 8 weeks. Among various findings, we observed that some users are more likely to become victims than others, depending on factors related to their social structure. Moreover, we found that traditional OSN defenses are not effective at identifying automated fake accounts or their social infiltration campaigns.Based on these findings, we designed Íntegro—an infiltration-resilient defense system that helps OSNs detect automated fake accounts via a user ranking scheme. In particular, Íntegro relies on a novel approach that leverages victim classification for robust graph-based fake account detection, with provable security guarantees. We implemented Íntegro on top of widely-used, open-source distributed systems, in which it scaled nearly linearly. We evaluated Íntegro against SybilRank—the state-of-the-art in graph-based fake account detection—using real-world datasets and a large-scale, production-class deployment at Tuenti, the largest OSN in Spain with more than 15 million users. We showed that Íntegro significantly outperforms SybilRank in ranking quality, allowing Tuenti to detect at least 10 times more fake accounts than their current abuse detection system.

View record

This dissertation focuses on supporting the provisioning and configuration of distributed storage systems in clusters of computers that are designed to provide a high performance computing platform for batch applications. These platforms typically offer a centralized persistent backend storage system. To avoid the potential bottleneck of accessing the platform's backend storage system, intermediate storage systems aggregate resources allocated to the application to provide a shared temporary storage space dedicated to the application execution. Configuring an intermediate storage system, however, becomes increasingly complex. As a distributed storage system, intermediate storage can employ a wide range of storage techniques that enable workload-dependent trade-offs over interrelated success metrics such as response time, throughput, storage space, and energy consumption. Because it is co-deployed with the application, it offers the user the opportunity to tailor its provisioning and configuration to extract the maximum performance from the infrastructure. For example, the user can optimize the performance by deciding the total number of nodes of an allocation, splitting these nodes, or not, between the application and the intermediate storage, and choosing the values for several configuration parameters for storage techniques with different trade-offs.This dissertation targets the problem of supporting the configuration and provisioning of intermediate storage systems in the context of workflow-based scientific applications that communicate via files -- also known as many-task computing -- as well as checkpointing applications. Specifically, this study proposes performance prediction mechanisms to estimate performance of overall application or storage operations (e.g., an application turn-around time, application's energy consumption, or response time of write operations). By relying on the target application's characteristics, the proposed mechanisms can accelerate the exploration of the configuration space. The mechanisms use monitoring information available at the application level, not requiring changes to the storage system nor specialized monitoring systems. The effectiveness of these mechanisms is evaluated in a number of scenarios -- including different system scale, hardware platforms, and configuration choices. Overall, the mechanisms provide accuracy high enough to support the user's decisions about configuration and provisioning the storage system, while being 200x to 2000x less resource-intensive than running the actual applications.

View record

Commons-based peer production systems are marked by three main characteristics, they are: radically decentralized, non-proprietary, and collaborative. Peer production is in stark contrast to market-based production and/or on a centralized organization (e.g., carpooling vs. car rental; couch surfing vs. hotels; Wikipedia vs. Encyclopedia Britannica). Social tagging systems represent a class of web systems, where peer production is central in their design. In these systems, decentralized users collect, share, and annotate (or tag) content collaboratively to produce a public pool of annotated content. This uncoordinated effort helps filling the demand for labeling an ever increasing amount of user-generated content on the web with textual information. Moreover, these labels (or simply tags) can be valuable as input to mechanisms such as personalized search or content promotion. Assessing the value of individuals contributions to peer production systems is key to design user incentives to bring high quality contributions. However, quantifying the value of peer-produced information such as tags is intrinsically challenging, as the value of information is inherently contextual and multidimensional. This research aims to address these two issues in the context of social tagging systems. To this end, this study sets forth the following hypothesis: assessing the value of peer-produced information in social tagging systems can be achieved by harnessing context and user behavior characteristics. The following questions guide the investigations. Characterization: (Q1). What are the characteristics of individual user activity? (Q2). What are the characteristics of social user activity? (Q3). What are the aspects that influence users perception of tag value? Design: (Q4). How to assess the value of tags for exploratory search? (Q5). What is the value of peer-produced information for content promotion? This study applies a mixed methods approach. The findings show that patterns of user activity can inform the design of supporting mechanisms for tagging systems. Moreover, the results suggest that the proposed method to assess value of tags is able to differentiate between valuable tags from less valuable tags, as perceived by users. Moreover, the analysis of the value of peer-produced informationfor content promotion shows that peer-produced sources can oftentimes outperform expert-produced sources.

View record

Distributed storage system middleware acts as a bridge between the upper layer applications, and the lower layer storage resources available in the deployment platform. Storage systems are expected to efficiently support the applications’ workloads while reducing the cost of the storage platform. In this context, two factors increase the complexity of the design of storage systems: First, the applications’ workloads are diverse among number of axes: read/write access patterns, data compressibility, and security requirements to mention only a few. Second, storage system should provide high performance within a certain dollar budget. This dissertation addresses two interrelated issues in this design space. First, can the computational power of the commodity massively multicore devices be exploited to accelerate storage system operations without increasing the platform cost? Second, is it possible to build a storage system that can support a diverse set of applications yet can be optimized for each one of them?This work provides evidence that, for some system designs and workloads, significant performance gains are brought by exploiting massively multicore devices and by optimizing the storage system for a specific application. Further, my work demonstrates that these gains are possible while still supporting the POSIX API and without requiring changes to the application. Finally, while these two issues can be addressed independently, a system that includes solutions to both of them enables significant synergies.

View record

Authorization protects application resources by allowing only authorized entities to access them. Existing authorization solutions are widely based on the request-response model, where a policy enforcement point intercepts application requests, obtains authorization decisions from a remote policy decision point, and enforces those decisions. This model enables sharing the decision point as an authorization service across multiple applications. But, with many requests and resources, using a remote shared decision point leads to increased latency and presents the risk of introducing a bottleneck and/or a single point of failure. This dissertation presents three approaches to addressing these problems.The first approach introduces and evaluates the mechanisms for authorization recycling in role-based access control systems. The algorithms that support these mechanisms allow a local secondary decision point to not only reuse previously-cached decisions but also infer new and correct decisions based on two simple rules, thereby masking possible failures of the central authorization service and reducing the network delays. Our evaluation results suggest that authorization recycling improves the availability and performance of distributed access control solutions.The second approach explores a cooperative authorization recycling system, where each secondary decision point shares its ability to make decisions with others through a discovery service. Our system does not require cooperating secondary decision points to trust each other. To maintain cache consistency at multiple secondary decision points, we propose alternative mechanisms for propagating update messages. Our evaluation results suggest that cooperation further improves the availability and performance of authorization infrastructures.The third approach examines the use of a publish-subscribe channel for delivering authorization requests and responses between policy decision points and enforcement points. By removing enforcement points' dependence on a particular decision point, this approach helps improve system availability, which is confirmed by our analytical analysis, and reduce system administration/development overhead. We also propose several subscription schemes for different deployment environments and study them using a prototype system.We finally show that combining these three approaches can further improve the authorization system availability and performance, for example, by achieving a unified cooperation framework and using speculative authorizations.

View record