Decision trees are integral to machine learning, with their robustness being a critical measure of effectiveness against adversarial data manipulations. Despite advancements in algorithms, current solutions are either optimal but lack scalability or scale well, but do not guarrantee optimality. This paper presents a novel adaptation of the Murtree algorithm to address these challenges in the pursuit of optimal robust decision trees. We introduce a new method for modeling an adversary as a network flow problem, and provide a dynamic programming approach to solve optimal robust decision trees beyond a depth of two. The performance of our proposed algorithm is compared with bruteforce solutions across varying decision tree depths, feature numbers, and data sizes. This research contributes a significant advancement towards obtaining efficient and effective solutions for optimal robust decision trees, potentially setting a new performance benchmark in this area.

Consensus algorithms, as well as distributed systems in general, are vulnerable to concurrency bugs due to non-determinism. Such bugs are hard to detect since it is necessary to test using a lot of different scenarios and even then, there is no guarantee to find one. Controlled concurrency testing is a proposed solution to that problem. Its main strength is allowing for more control over the order in which threads are executed, using controlled scheduling. In this paper, we utilize Coyote, a concurrency testing framework, to test for concurrency bugs in PBFT, the seminal consensus algorithm. Random Walk, Delay-Bounding, Probabilistic Concurrency Testing (PCT) and Q-Learning are the exploration strategies we performed experiments with. The goal is to find schedules that lead to concurrency bugs. We test for 2 bugs that are seeded by us into the algorithm. A comparison of the results shows that fair exploration strategies outperform their unfair variations. Finally, we conclude that PCT and fair PCT are the best-performing strategies for the benchmarks we use.

Decision trees make decisions in a way interpretable to humans, this is important when machines are increasingly used to aid in making high-stakes and socially sensitive decisions. While heuristics have been used for a long time to find decision trees with reasonable accuracy, recent approaches find fully optimal trees. Due to the computational hardness of finding fully optimal decision trees, it is only practically possible to find shallow trees for a limited dataset size. However, continuous algorithmic improvements keep pushing the scale of feasible solutions. Dynamic Programming approaches promise to find scalable optimal decision trees but need to be adapted for different objectives, such as regression. We combine and adapt the algorithmic techniques of two Dynamic Programming methods, creating a new method that improves the scalability of optimal regression trees. This new method often achieves an order of magnitude speed improvement over a previous state-of-the-art method.

In this paper, we tackle the problem of creating decision trees that are both optimal and individually fair. While decision trees are popular due to their interpretability, achieving optimality can be difficult. Existing approaches either lack scalability or fail to consider individual fairness. To address this, we define individual fairness as a separable optimization task by analyzing the fairness gained and lost within a sub-tree. Using the Streed framework, we implement an algorithm that constructs optimal decision trees with the lowest misclassification score and individual fairness value above a certain threshold. Our algorithm has been tested on various datasets, demonstrating its effectiveness and scalability. This research is a significant step towards creating fair decision trees that are optimal, fair, and scalable.

Machine learning is becoming more and more applied within business and academia alike. This has led researchers to look inwards and discuss whether the current way of teaching and learning machine learning is the right way. Within this train of thought, one must investigate the characteristics of teaching and learning. Namely, what are the competences required to learn, and in what order should these be learned. This research paper focuses on realizing the answer to that question by combining past research papers on how to define competences, how to establish an order of competences, and how to establish competences through the help of questionnaires answered by academics within the machine learning sector teaching Computer Science students. The results from the academic analysis and the resulting data from the questionnaires are combined to organize a result, established through two different methods used by researchers. To conclude, the paper is reflected upon, and its merits, demerits, and trade-offs are summarized, presenting a final recommendation for any future work done on this topic.

The Algorithm Selection Problem is a relevant question in computer science that would enable us to predict which algorithm would perform better on a given instance of a problem. Different solutions have been proposed, either using Mixed Integer Programming or machine learning models, but both suffer from either poor scalability, no guarantees of optimality, or not interpretable models that could be used to gain insights into the nature of the problem. In this work we propose a dynamic programming method to build Optimal Decision Trees to solve the Algorithm Selection Problem, giving us an interpretable model that is globally optimal over the training dataset. We also show that this method is orders of magnitude faster in training trees that are identical to the current state-of-the-art and propose possible improvements for future work.

Term-rewriting super-optimisation during compilation uses rewrite rules in order to restructure a provided code expression into the optimal form, comparing different expressions using a cost function. To reduce the compilation time taken by term-rewriting, the ruleset can be optimised by combining rules that were commonly chained during previous optimisation runs. With an any-time super-optimiser a specialised ruleset makes it possible to attain the optimal code expression, under the ruleset constraints, with a lower time requirement. We found rule chaining methods to be effective at reducing the time necessary to obtain the canonical form. The methods performed well on synthetic benchmarks, as well as ones representative of real C projects. The frequency of the chained rule use and their uniqueness compared to the other compound rules directly dictates how great of a performance improvement its addition provides. Optimised sets demonstrated poor generality, indicating over-specialisation.

In the field of software engineering, the speed of compilation plays a crucial role in enhancing development productivity. This thesis investigates the impact of optimising the memory layout of Abstract Syntax Trees (ASTs) on the performance of the type checking and code generation phases in the compilation process of strictly-typed procedural programming languages. Existing compilers often employ a traditional Object-Oriented (OO) approach to AST construction, leading to inefficiencies such as high memory overhead and suboptimal cache usage. We applied Data-Oriented Design (DOD) principles to restructure ASTs, aiming to enhance data locality and reduce memory access times. The study investigates various AST memory layouts, including a transition from a naive OO model to a Struct-of-Arrays (SoA) model. We evaluated the effect of these memory layouts on compiler performance using a set of benchmarks based on real-world code. We executed the benchmarks on diverse hardware platforms, measuring key performance metrics such as type checking time, code generation time, and cache miss rates. The results demonstrate that adopting an SoA model for ASTs significantly reduces the duration of the type checking and code generation phases, with improvements varying across different hardware architectures. We provide empirical evidence supporting the application of DOD principles and specifically SoA to ASTs for performance improvements. By highlighting and addressing the performance bottlenecks associated with traditional AST layouts, we contribute to the broader goal of advancing compiler design and optimisation.

With the increase of machine learning applications in our every-day life, high-quality datasets are becoming necessary to train accurate and reliable models. This research delves into the factors that contribute to a high quality dataset and examines how different dataset metrics affect the performance of machine learning models particularly focusing on Graph Neural Networks (GNNs) Tabular Transformers and Large Language Models (LLMs). The metrics, under scrutiny include graph sparsity, missing data cells, modularity and text length. Various datasets are adjusted to assess how these metrics impact model performance. The results of the experiments reveal that sparse graphs can preserve relational information. However increasing density does not necessarily lead to improved performance due to noise interference. The models demonstrated accuracy and low error rates in the presence of significant missing data indicating their ability to handle incomplete information effectively and generalize well based on imputation strategies and structural design. Higher modularity was found to aid in capturing patterns. Introduced complexity that could potentially hinder performance. Notably text length emerged as a factor influencing model performance by offering contextual details. These insights show the significance of considering attributes when designing machine learning models for intricate predictive tasks. Through experimentation and optimization of these metrics we can enhance model resilience and accuracy for applicability, in real world scenarios.

The rapid advancement of automated vehicles (AVs) can potentially improve transportation. However, ensuring the safety and reliability of Automated Driving Systems (ADS) remains a critical challenge, particularly when facing the expansion of Operational Design Domains (ODDs) and the continuous emergence of unknown hazardous scenarios. This thesis aims to address these challenges by developing a framework for monitoring the safety of multi-channel ADS and identifying hazardous scenarios using Safety Performance Indicators (SPIs) and Hazardous Scenario Identification (HSI) techniques. The proposed SPI framework, based on the principles outlined in the UL 4600 standard, encompasses a comprehensive set of metrics for assessing the safety and performance of ADS. These metrics cover various critical functionalities, such as ego localization, object detection, trajectory planning, and overall ADS behaviour. By defining appropriate thresholds for each SPI, the framework enables the identification of potential safety issues and supports the continuous monitoring and improvement of ADS. The HSI module, developed as part of this thesis, leverages the SPI framework and the NXP Daruma cross-channel analysis to detect hazardous scenarios. The HSI module's performance is evaluated using the CARLA simulator and advanced ADS software stacks (LAV and TFUSE) across diverse driving scenarios. The results demonstrate the HSI module's effectiveness in identifying hazardous scenarios such as ego vehicle tailgating, inconsistent ego localization, and ego vehicle being tailgated. However, our analysis also reveals challenges in terms of false positives and negatives, highlighting the need for further improvements in the ADS's perception and localization functionalities and in tuning the SPI thresholds appropriately based on testing as well as the characteristics of the ADS. This thesis contributes to advancing ADS safety by developing a comprehensive SPI framework and implementing a proof of concept HSI module. We propose an architecture that integrates these components in a closed-loop process involving vehicle fleet data collection, cloud-based analysis, and targeted software updates. This framework enables the identification of areas for improvement and supports generating OpenSCENARIO files for reproducing and analyzing hazardous scenarios ad hoc. The findings from the experimental evaluation provide valuable insights into the performance and limitations of the SPI safety monitoring and HSI techniques, guiding the safe deployment and continuous improvement of ADS. This research ultimately paves the way for the widespread adoption of automated vehicles (AVs) in driving environments.

This study examines the differences between two modern linkers, LLD and mold, focusing on their efficiency during software development. Although the linking process, which combines multiple object files into a single executable, typically occupies a minor fraction of the total compilation time, optimizing it can significantly enhance the overall build efficiency - particularly during the development of large-scale projects. The research aims to determine codebase-level differences between these linkers and assess their performance across various metrics, including linking time, memory usage, and the time spent on different phases of the linking process, using CMake and Bitcoin Core as benchmarks. Furthermore, the study extends to examining the executables produced by both linkers from the HDiffPatch project, comparing their execution times and sizes. The findings consistently show that mold outperforms LLD in terms of speed and efficiency, which results from its comprehensive utilization of parallel processing techniques. Nonetheless, LLD offers broader applicability by supporting a wider range of file formats and being suitable for both embedded and kernel programming. Therefore, the selection of a linker ultimately depends on the specific requirements of the project and the characteristics of the target machine.

Over the past decades, Single Instruction, Multiple Data (SIMD) instructions have become common- place in conventional hardware. Lexical analysis, the first stage of compilation, can take advantage of this by splitting its workload across sub lexers that identify groups of tokens with similar structures. Each sub lexer can leverage SIMD to search for these structures across multiple characters in paral- lel and extract token positions efficiently. This pa- per presents a lexer with this architecture for the C programming language, along with implementation details for x86/x64 processors. Benchmark results show a 12x speed up in throughput compared to the lexer found in GCC, a state-of-the-art compiler.

Big Data is an expanding industry, yet exhaustive and automated testing of Big Data applications is still in its early stages. In the last few years, testing framework for Big Data applications have started appearing. BigFuzz is a program that uses fuzz testing for Big Data applications. Fuzz testing means generating random, potentially invalid or erroneous, inputs in attempt to find exceptions. This paper introduces TabFuzz, a tool that improves and extends the BigFuzz solution. TabFuzz reproduces the BigFuzz implementation and extends on it, by improving the generation of random input files. TabFuzz can generate a valid input file based on an input specification. It then mutates this file using high-level mutations. These mutations generate new test inputs that mimic real-world problems. This is an improvement over bit or byte level mutations. These mutations are supposed to mimic real-world problem, which is an improvement over random bit or byte level mutations. Most fuzzing programs start from a user-defined initial input file, called a seed file. TabFuzz offers the possibility to generate such a file. This research shows that these generated files are just as effective as starting from a seed file.

Concurrency bugs are easy to introduce but dif- ficult to detect, especially in implementations of distributed algorithms where concurrency non- determinism is an inherent problem. These bugs may only be identified under very specific order- ings of execution events, making them challenging to reproduce. Controlled concurrency testing tech- niques have been proposed to address the testing challenge, by taking over the scheduling of events, and effectively searching the state space of sched- ules to identify the concurrency bugs. In this paper, we investigate and compare the per- formance of two concurrency exploration algo- rithms, probabilistic concurrency testing (PCT) and delay bounding strategy on our implementation of the HotStuff consensus protocol, which has been quite popular and was adopted by Meta for its Diem blockchain project. Our results suggest that can in- deed find concurrency bugs more frequently in our HotStuff implementation than the baseline random strategy. However, using different bound parame- ters for PCT and delay bounding does not have sig- nificant effect on bug finding performance on our benchmarks.

Big data applications are becoming increasingly popular. The importance of testing these applications increases with it. A recently proposed work called BigFuzz applies automated testing. The big data fuzzing tool shows very promising results. The aim of this research is to inspect how coverage guidance affects the performance of big data fuzzing. The current coverage usage is first described, then an extension is proposed, which is compared to the original. This work extends the BigFuzz tool with branch coverage guidance. The existing black-box fuzzer is substituted for a grey-box fuzzer, which is then extended to a boosted grey-box fuzzer. The two extensions both allow branch discovery. Boosted grey-box fuzzing shows to be the most efficient branch exploration mechanic. Furthermore, both extensions outperform the original tool regarding error detection.

This papers examines an ant colony optimization approach for solving a specific variant of the Flexible Job Shop Problem faced by the Dutch chemistry company DSM. Jobs consisting of operations on a specific enzyme need to be scheduled as efficiently as possible on groups of available machines. The most interesting requirement upon the general FJSP are the sequence-dependent cleaning times a machine needs when it processes two different enzyme types consecutively. This can all be intuitively represented using a weighted disjunctive graph, which ACO uses as its input. The algorithm consists of a number of epochs for which multiple ants create a feasible schedule one operation at the time. Scheduling choices are made using pheromones and an heuristic visibility function based on earliest starting times. Pheromone amounts are updated using both a negative local updating rule and a positive global update for the best ant per epoch. Two hyperparameters, the initial pheromone amount τ0 and the cutting exploration parameter q0 are experimentally evaluated. Varying τ0 does not consistently impact the solution quality nor runtime, while the higher the value of q0, the better both measures. Performance evaluation of ACO is done using a provided MILP solver as baseline and the makespan as objective function for a range of different time limits. For the tested instances, ACO shows to significantly outperform MILP, finding good solutions exceptionally fast. Based on this, ACO is an efficient method to solve the production scheduling problem of DSM.