Building scalable and consistent cloud applications is notoriously difficult due to the challenges of state management and execution consistency in distributed environments. Functions-as-a-Service (FaaS) platforms offer flexible scalability, but weak execution guarantees forces engineers to mix business logic with infrastructure concerns, adding error-handling code, retry mechanisms and consistency checks throughout their applications. At the same time, dataflow systems like Apache Flink offer exactly-once semantics, but their functional APIs often conflict with the imperative, object-oriented style preferred by mainstream developers.

This work aims to address this disconnect, arguing that modern transactional applications, from e-commerce to payment systems to business workflows, naturally form stateful dataflow graphs. By allowing developers to write familiar imperative code that executes on dataflow systems with strong consistency guarantees, we could eliminate the need to handle many infrastructure concerns explicitly.

To this end, we introduce Cascade, a compiler pipeline and intermediate representation that bridges the gap by translating imperative Python code into stateful, parallelizable dataflow graphs. Cascade extends prior work by providing a representation that is both expressive and optimizable, and we demonstrate optimizations including parallel execution via data dependency analysis and dynamic value prefetching. Our results show significant performance gains with these optimizations, all while maintaining the strong execution guarantees of the underlying execution target. Finally, we offer avenues for future research by discussing further optimization possibilities and extensions within our proposed framework.

Learning deterministic finite automata (DFAs) from labeled traces is a key problem with applications in software analysis and system modeling. SAT-based methods are effective but can be slow when dealing with large datasets. To address this, we propose a sampling method that selects a smaller, but still representative set of traces. Our approach groups traces with similar suffixes and uses edit distance to choose diverse examples. The proposed sampling performs better than random uniform sampling and significantly better than heuristic algorithms.

This paper investigates a hybrid approach to deterministic finite automata (DFA) identification by combining heuristic (EDSM) and exact (reduction to SAT) methods. The hybrid strategy implies first partially identifying the DFA heuristically and then minimizing it with an exact method. Two implementations of the hybrid approach are tested - one using binary search on the number of states of the intermediate model, and one that adjusts the SAT offset to control its search space. The results obtained on datasets from the STAMINA competition show that while the hybrid approach reduces the size of the inferred models compared to EDSM, this does not necessarily translate to better test performance. Nevertheless, the methods used in this work demonstrate how a hybrid approach can be applied to infer more compact models in DFA identification.

Deterministic finite automata (DFA) are interpretable models used for classification and prediction tasks based on sequence data. They often act as surrogate models for software systems. Plenty of methods exist for the purpose of DFA learning. Examples include optimal algorithms such as SAT-based encoding and various heuristic methods as the likes of the BlueFringe framework of the EDSM algorithm. By definition, optimal algorithms can guarantee a minimal DFA consistent with the training data, but this does not exclude the possibility of heuristics also finding the optimal solution. However, it is generally believed that optimal methods could always require strictly less data to learn such a minimal model than their counterparts. In our research, we provide mathematical proofs and counter-examples that show the above statement to be false. We further demonstrate that, unless formally defined, there exist numerous languages and settings where heuristics outperform optimal methods on data efficiency benchmarks. Finally, we prove that optimal methods are equal to the BlueFringe framework in terms of optimistic learning efficiency.

The Z3 SMT solver, a type of satisfiability solver used both in research and in industry, can give better performance by either improving the underlying
implementation or using domain-specific guidance. We present a way to simulate domain-specific help automatically by reducing the search space based on the model solution, and we use it to compare two implementations of Z3′s string solver – Z3str3 (weaker) and Z3-Noodler (stronger) – with and without domain-specific help. We find that Z3-Noodler sees significantly less improvement than Z3str3 because 1) the additional “helping” constraints are in fact occasionally counterproductive and 2) Z3-Noodler solves equivalent problems much faster than Z3str3, so the relative overhead of the additional constraints is more noticed.

Program synthesis is an important problem in computer science. One method often employed is enumerative program synthesis, which produces a sequence of programs in the target language until one solves the required input-output examples. This can yield undesirable runtimes for some problems that require complex programs to solve them. This research is about how simpler problem solutions can be used to build a library of useful helper functions and to use it for further synthesis in order to reduce the depth of the enumerative search for more complex problems. Drawing inspiration from the work by Ellis, et al on DreamCoder, this research describes ways of obtaining simpler programs, and extending the grammar using parts of the solutions. Experiments have been performed on the proposed synthesis algorithm, which is implemented using the Herb.jl framework, and results for each part of the synthesis algorithm being replaced by different strategies are provided. Allowing holes in the new grammar substitutions and using smaller size or frequency as their utility has proven superior. There needs to be more work done about the conciseness of the produced programs.

Program synthesis tackles the challenge of generating programs from user specifications, a task proven undecidable due to the exponential search space growth. In program synthesis the Divide and Conquer technique can be employed to prune this search. By decomposing specifications into individual examples, multiple programs are synthesized to solve them separately. Later these small programs are combined into a bigger program which should satisfy all input-output pairs by itself. There have been previous successful attempts at using Divide and Conquer, including combining programs using decision trees. However, a gap persists in the program synthesis community regarding comprehensive frameworks for integrating diverse implementation strategies. This project addresses this gap by incorporating a Divide and Conquer algorithm into a program synthesis library, enabling users to explore different ways of generating the small programs while abstracting the unification procedure. Moreover, we also discuss a "greedy" strategy to generate the programs that will be combined. We found that a Divide and Conquer manages to improve naive search, especially when given more than 10 examples.

Program synthesis is the process of constructing programs that provably satisfy a given high-level user specification. Recent work in this domain has focused on utilizing domain-specific languages to guide the search procedure. This study proposes a novel approach to enhance the efficiency of such search procedures. By utilizing anti-unification, which is the process of generating the least general pattern between two symbolic expressions, this work aims to find common sub-components to enhance the language used in program synthesis to reduce search depth and improve performance.

In the realm of machine learning (ML), the need for efficiency in training processes is paramount. The conventional first step in an ML workflow involves collecting data from various sources and merging them into a single table, a process known as materialization, which can introduce inefficiencies caused by redundant data. Factorized ML strives to reduce this by maintaining the original data forms and performing model training on the separate source tables. This approach can lead to significant increases in training efficiency.

However, factorized training does not always reduce cost compared to traditional materialized training. This research tackles this issue by examining the multidimensional cost optimization problem that emerges when deciding between factorized and traditional materialized learning methods. It fills in gaps left by prior research, which is focused on CPU-based training, by investigating the cost estimation landscape for factorized ML, with a special emphasis on GPU performance compared to CPUs. The used factorized ML framework is expanded to incorporate GPU training, a topic not explored in previous research. We demonstrate that GPU training exhibits significantly different cost characteristics than CPU training, which has substantial implications for the design of cost models and the optimization of factorized ML.

Through an empirical study, an ML-based cost model is developed that can accurately predict the faster training method for a wide range of scenarios. On an extensive evaluation with real-world datasets this model boasts an average speedup of 3.8x, versus the state-of-the-art's 0.9x. We also show that it generalizes to scenarios with datasets and hardware settings on which the model is not trained, keeping 82% of training set performance.

Our innovative cost model for factorized ML enables significant time savings in training-intensive scenarios and further underlines the benefits of factorized training. However, effort should be invested into incorporating factorized training into existing ML frameworks so this method of training a model, and our cost model, can be evaluated in a larger set of realistic scenarios.

The increasing demand for data-intensive applications such as artificial intelligence and big data analytics is hitting the limitations of traditional computing architectures. Near-memory processing architectures, like UPMEM's Data Processing Units (DPUs), offer a promising solution by integrating computation with memory, reducing data movement and energy consumption. However, UPMEM's scratchpad-centric design imposes some critical programming challenges, requiring explicit programmer intervention for efficient memory management, which increases program complexity and limits portability.

This thesis investigates a compiler-driven approach to automatically exploit scratchpad memory on UPMEM's DPUs, aiming to simplify programming and achieve performance comparable to hand-optimized code. A novel compilation pipeline is proposed that analyses loops in DMA-unaware C programs and optimizes them into efficient, DMA-aware machine code. The design leverages static analysis, including alias analysis and symbolic analysis, to insert DMA instructions efficiently.

To evaluate the compilation pipeline, the Processing-in-Memory Compiler Benchmarks, based on the Processing-in-Memory Benchmarks proposed by the SAFARI Research Group, are proposed. Experimental results demonstrate significant improvements, achieving an average of 75% of the runtime of hand-optimized programs and sometimes even exceeding the runtimes of the hand-optimized programs.

By automating scratchpad memory management, programmers can focus on high-level functionality while maintaining system performance and compatibility. Future research directions include extending optimizations beyond loops, improving global memory management, and extending the compiler benchmarks with application-based benchmarks.

Graph databases are systems to efficiently store and query large graphs. As graph databases grow in popularity, they are used to answer increasingly diverse and complex queries. However, graph databases typically have a very limited query language that cannot express arbitrary algorithms. As a result, many users treat the database as a storage layer to export data from and develop algorithms in external tools, wasting computation power and storage space.

We present graphalg, a high-level, domain-specific language for writing graph algorithms embedded into traditional graph queries. Our language is based on linear algebra, with a syntax resembling GraphBLAS, and implemented in the AvantGraph database.

We implement a compiler for graphalg that can target an interpreter built on top of a GraphBLAS implementation. Alternatively, our compiler can transform graphalg programs into a relational algebra with loops, unifying the representation of query and algorithm. We evaluate the programmability and performance of our system on the GAP Benchmark Suite for graph algorithms. Our language is expressive enough to concisely represent all GAP benchmark programs, with the majority of programs achieving performance comparable to an optimized C implementation.

We conclude that graph algorithm support can be integrated into graph databases to increase their programmability. Running graph algorithms inside of the database increases performance and reduces memory consumption compared to using external tools for the analysis. Rather than thinking of graph databases as limited tools for answering simple queries, we demonstrate that they can instead be a programmable framework for efficient large-scale data analysis.

The Maven Central Repository hosts over 11 million packages. As Maven itself is a build tool for Java, the majority of these packages are Java archives.
This research aims to analyze these packages and look into various build aspects of these projects (the research questions): are Java modules used, what Java versions are used and how is the compiler configured? This is done by downloading a subset of these packages and looking at both the final artifact and the attached Project Object Model (Maven configuration). Specifically, one version is randomly selected from each distinct package hosted on Maven Central and then analyzed.
This research helps inform Java language developers and library maintainers. It captures parts of the build system evolution over a span of more than a decade. Precisely, version adoption, reproducibility and desirable build features are all important metrics for project maintainers in any software ecosystem. In the end, 473352 packages were analyzed. Firstly, it was found that Java modules are rare: only 6919 (1.69% of the artifacts with an archive) of the packages use Java modules. Secondly, the most common Java version used is Java SE 8 (182476 packages) representing almost half of all analyzed packages. All long-term support versions (Java SE 8, 11, 17 and 21) make up roughly half of the available packages. Thirdly, only 54.98% of artifacts configure the Maven compiler plugin with the most used parameters being the source and target Java versions. The most common additional compiler flags are verbosity settings, providing more feedback and code analysis from both the linter and compiler.

Maven Central serves as the de-facto repository for distributing free and open-source Java libraries and components. Evaluating its present state and overall robustness is pivotal for enabling the community to make well-informed decisions concerning its future progression. Such informed decisions would undoubtedly benefit the collective community of developers. This study aims to empirically evaluate developer practices surrounding version control and package reproducibility on Maven Central by investigating (i) the reliability of repository links, (ii) preferences regarding repository hosting services, (iii) the utilization of tags/releases, and (iv) the reproducibility of packages. Our study revealed that 20.85% of packages had unreliable repository links, attributable to inconsistencies in field usage and missing data, highlighting lax submission guidelines. GitHub emerged as the dominant host, with a market share exceeding 90% most years, though regional alternatives, like Gitee, are gaining traction. 74.35% of packages used tags/releases; however, naming convention discrepancies between Maven Central and source code repositories were identified, hindering version tracing and reproducibility. Strikingly, only a 3.06% of packages were configured to attempt reproducibility. An even smaller subset was found to be fully reproducible.

Maven, a widely adopted software ecosystem for Java libraries, plays a critical role in the development and deployment of software applications. However, there exists a limited understanding of the composition and characteristics of the Maven repository, leaving users and contributors unaware of the contents they interact with. This research aims to address this knowledge gap by conducting a comprehensive analysis of Maven packaging and informing developers, library maintainers, security analysts, and the open-source community about Maven library practices. The research investigates the secrets of the Maven repository, focusing on Maven packaging. Using data from the POM file, Maven index file, and Maven repository, we analyze the distribution of packaging types, checksums, qualifiers, and file types within Maven libraries. The experiment involves examining 479,915 packages from the Maven repository, utilizing the POM file, the Maven index, the Maven repository and manual requests to the Maven repository. The results reveal that JAR is the packaging type in more than 75% packages across all sources, and inconsistencies are found among different data sources, highlighting the need for improved data consistency and reliability within the Maven ecosystem. Furthermore, the adoption of the sha256 and sha512 checksum algorithms remains limited, with only 1.4% of packages utilizing these secure hash functions. In terms of qualifiers, sources and Javadoc exhibit the highest prevalence, with adoption rates of 82% and 76% respectively. Moreover, class files and XML are identified as the most frequently packaged file types, encompassing 71% and 61% of the packages, respectively among a very diverse classification. These findings provide insights into Maven library characteristics and inform optimization of library usage.

As more and more aspects of our society and economy rely on software, security vulnerabilities in programs have become an increasingly significant threat. One such class of vulnerabilities are out-of-bounds writes, which are still one of the most widespread and dangerous types of security bugs in memory-unsafe programming languages five decades after their initial conceptualization.
Their discovery through automated methods like fuzzing, however, has gained substantial traction in the past years and facilitates their discovery in large numbers with minimal human intervention. On the other hand, the analysis following their initial discovery - triaging, root cause analysis, and patching - mostly requires human expertise and intuition. As this need for manual effort affects the time to assess a vulnerability's security implications and prioritize patching accordingly, partial automation of the triaging process is essential. A promising approach is the automatic extraction of vulnerability characteristics that provide vital clues for a bug's exploitability. Such characteristics, which typically require substantial effort to collect manually, can aid a human analyst in triaging and thereby speed up the process while, at the same time, making it more accessible.
In this work, we investigate how the set of affected source code-level objects, which is a decisive indicator of an out-of-bounds write vulnerability's exploitability, can be automatically distilled from a program and an input suspected of causing an out-of-bounds write. As this poses unique challenges with regard to invasiveness, we propose a novel approach for out-of-bounds write detection that facilitates monitoring a compiled program for spatial memory safety violations without the need for instrumentation. We implement a prototype of our design and evaluate it on benchmarks and real-world vulnerabilities, showing that its detection performance is largely on par with state-of-the-art instrumentation-based detection approaches and even outperforms them in several scenarios at the cost of increased performance overhead and a higher rate of false positives.

Dataflow analysis is a powerful tool used for program optimization, static analysis, and editor services for many programming languages. Spoofax, a language workbench, contains a domain-specific language called FlowSpec for the definition of control-flow and dataflow semantics that language developers can use to implement dataflow analyses for their language. FlowSpec however cannot be used to efficiently optimize programs. Other solutions are not suitable for language developers, or lack the ergonomics of a domain-specific language. In this thesis we present Flock: an incremental implementation of FlowSpec. We analyze the performance of Flock and show that it is efficient enough for use in optimization pipelines. Flock gives language developers the tools to succinctly write dataflow analyses for a wide variety of applications.