Template-based automated program repair fixes bugs by applying fix templates to a suspicious location. Such approaches have been successful, but a patch is generally limited to what a template can express and which templates are available. This thesis asks whether templates can be used as the rules of a grammar instead. We present Find2Fix, which turns templates mined by Cardumen into a typed, probabilistic grammar for program synthesis.

On 140 single-line-substitution bugs from Defects4J 2.1, Find2Fix patches 33 bugs against Cardumen's 24, a 37.5% increase, with five bugs it gains requiring nested templates. Weighting the grammar by frequency and locality fixes 3 more bugs than an uninformed BFS enumeration, but the effect is not significant (p=0.25). Correct (not overfit) patches rise only from 2 to 5. Pattern-based grammars are thus effective for constructing a repair search space, but not (yet?) as a complete repair technique when used as in this thesis without a stronger patch-acceptance criterion. ... Read more

Sequential regression has many real-world applications, including energy consumption forecasting and traffic prediction. In this paper, the use of extended regression automata for sequential regression is investigated. The automata are learned using an MSE-based approach with the Akaike Information Criterion (AIC) and the Bayesian Information Criterion (BIC) to score merge and split operations, where the use of BIC is a novel contribution of this work. The approach is evaluated on three datasets and compared against persistence, a regression tree, and a random forest. The automata perform comparably on the small dataset, but on the larger datasets, they do not outperform the regression tree and random forest baselines. This is mainly caused by a bias towards splitting during learning, which prevents the automata from making use of loops and causes them to resemble trees. We further found that BIC produced smaller automata and ran faster, but its accuracy was mixed relative to AIC for our datasets. ... Read more

Automata learning is a powerful technique for obtaining system models from observed behavior and is often used in software testing, verification, and reverse engineering. However, most algorithms used today either require interaction with that system or suffer from poor scaling due to memory limitations. A relatively new approach in automata learning algorithms has been to store the dataset in a database and interact with it through custom database queries. This thesis uses this approach to develop a novel algorithm based on regular expression queries and custom data structures. Upon evaluation on generated datasets of binary sequences and the Abbadingo benchmarks, this approach was found to scale linearly to much larger dataset sizes than EDSM and to use orders of magnitude fewer queries than L*. It is also accompanied by a formal proof of correctness. Ultimately, this work provides a highly scalable algorithm and a self-contained, comprehensive theoretical framework. ... Read more

Inferring a minimal Deterministic Finite Automaton (DFA) from a set of labelled traces is an NP-complete problem, making heuristic search strategies necessary. The red-blue framework addresses this inference process by sequentially applying merge and extend refinements to a prefix tree acceptor, with the ordering of these refinements determining the compactness of the final automaton. This paper investigates the use of Monte Carlo Tree Search (MCTS) as a heuristic for finding higher-quality refinement orderings. The problem is first formalised as a Markov Decision Process, enabling MCTS to serve as a solver. We evaluate four action-selection policies and two reward metrics across several datasets from the StaMiNa competition. Results show that the uniform-merge-first, weighted-merge-first and weighted-minimal policies outperform the uniform policy, although none of these policies dominates the others. The weighted-minimal sub-policy produces a more compact automaton than the weighted-average sub-policy, confirming that favouring merge over extend refinements during simulation is beneficial. Two reward metrics are compared: the final simulated DFA size and the number of rollout steps. Both perform similarly overall; however, the rollout steps metric has the structural advantage of being immune to reward stagnation, since the reward improves monotonically as the search tree grows. Correlation analysis further reveals that the EDSM scoring function provides no directional signal towards smaller DFAs. ... Read more

The goal of DFA learning is to infer a target DFA from a set of positive and negative observations. Active learning methods allow a learner to hypothesize about the target DFA by querying a teacher. Constructing a teacher that can efficiently answer these queries can significantly speed up the learning process. A distinguish query allows the learner to provide two words for the teacher and the teacher responds with a distinguishing suffix (i.e. a suffix such that if it is concatenated to the two provided words, one of the newly formed words will be among the positive observations, and the other among the negatives).
In this thesis, our aim is to design different implementations of a data structure that supports distinguish queries (DistinguishQueryDataStructure), and compare them through theoretical and experimental analysis.
To this end, we introduce the double trie, and show that using this data structure, it is possible to reduce distinguish queries to set intersection queries.
Then we design three different implementations of DistinguishQueryDataStructure, one of which uses a trie based approach with depth-first search, and two of which are based on the double trie.
Our experimental analysis shows that a double trie-based method can compete with, and even outperform in some cases the trie and depth-first-search-based approach. ... Read more

Anomaly detection is very important in this day and age. Finding anomalies in
software can help fix bugs or prevent malicious intent from third parties. One way to detect these anomalies is by making use of pdfa’s. Pdfa learning an extension of dfa learning can be used to construct a model of an application given some logs of the application. To build a pdfa, a probabilistic deterministic finite automata, various algorithms in combination with extra parameters can be used. In this paper we will use the FlexFringe framework to look into these so called search orders to answer the question: What are good search orders in extended state machine learning for anomaly detection? We looked into the Alergia and RTI+ algorithm on data with and without time information. Our main conclusions are that Alergia together with the blueblue parameter works best for creating a model for anomaly detection. ... Read more

Learning Extended Deterministic Finite Automata (EDFAs) from traces provides an interpretable way to model sequential behavior, but the quality of the learned automaton strongly depends on the heuristic evaluation function used during state refinement. This paper investigates a new heuristic evaluation function for EDSM-based EDFA learning, inspired by the Gini impurity criterion used in CART decision trees. Three Gini-based variants are introduced: a local variant that evaluates impurity at the immediate split, a future-state variant that evaluates impurity over the affected future states, and a weighted variant that uses a parameter λ to balance the influence of final and intermediate tails.

The variants are implemented in FlexFringe and evaluated on several time-series classification datasets and the CTU-13 network traffic dataset. Hyperparameters are selected using validation data, and final performance is measured on test sets using accuracy, specificity, EDFA size, and final-state consistency. The results show that Gini-based refinement can improve the structural quality of learned EDFAs compared to RTI by producing smaller automata and more class-consistent final states while maintaining competitive accuracy. The weighted variant achieves the best average EDFA accuracy among the proposed variants, although among the Gini variants, higher consistency often comes at the cost of larger automata. These findings suggest that Gini impurity is a promising basis for heuristic evaluation in EDSM-based EDFA learning, especially when interpretable and class-consistent automata are desired ... Read more

Stateful learning techniques are crucial for the verification and validation of complex software systems. As the world becomes increasingly reliant on software, the need for secure and reliable applications continues to grow. Previous work on stateful learning has primarily focused on monolithic systems, leaving the application of these techniques to microservice architectures largely unexplored. This is despite their widespread use in modern software development.

This thesis investigates the challenges associated with learning systems based on microservice architectures. First, we present a framework for generating valid API requests across interacting services. Next, we address system flakiness during learning through the introduction of Two-Phase Equivalence Querying with adaptive sampling. Finally, to explain the non-deterministic behavior observed in microservice systems, we introduce the concept of State Drift, which captures state changes caused by internal communication between services.

To conclude this thesis, we apply the techniques developed throughout this work to a real-world software system. The system learned is an implementation of OAuth provided by Ubiqu. This case study demonstrates how our proposed techniques can be used in industry and highlights the practical challenges that remain when applying stateful learning to microservice architectures. ... Read more

Over the past decade, the microservice architectural style has gained immense popularity among software companies. Many adopt this architectural style to develop their web services due to its improved maintainability, reliability, and agility. These benefits enable companies to quickly develop and deploy their web services iteratively.

Despite its advantages, microservices are notoriously known to be difficult to debug when software failures occur. Developers often struggle to identify the underlying cause of a failure due to the distributed nature of microservices. In fact, certain software failures only emerge when complex interconnected interactions are triggered between microservices. Therefore, it is becoming increasingly important to develop monitoring tools to streamline the process of determining the underlying cause of problems detected within microservices.

The AssureMOSS project, part of the EU Horizon 2020 Research Program, focuses on
delivering various tools or approaches to enhance security at various phases of the microservice development life-cycle. This dissertation, conducted as part of the AssureMOSS project, primarily investigates runtime monitoring of microservices to detect anomalies such as cyber-attacks and discrepancies between observed behaviors and the intended behaviors specified in the source code.

A key project requirement is using lightweight interpretable machine learning models to aid the understanding of detected software failures. State machines, also known
as Finite State Automata, have proven to be practical models for modeling behaviors of various software systems. Furthermore, these models are considered to be inherently interpretable as one can visualize the behaviors exhibited by a system. For this reason, state machines are a suitable choice for monitoring microservice applications. This dissertation explores how state machines can be applied to address challenges across various phases of the microservices development life-cycle.

Part I explores how state machines can be utilized to monitor the runtime of microservices for anomalies. In particular, the studies conducted in Part I focus on detecting network anomalies, such as network attacks, within microservice applications. Part I first introduces ENCODE in Chapter 2, an encoding algorithm designed to preprocess NetFlow records, making them suitable for learning state machine models. Chapter 3 demonstrates how state machines can be learned from NetFlow data collected from microservices and evaluate their effectiveness in detecting various network attacks targeting microservices deployed in a Kubernetes cluster. Finally, Chapter 4 introduces SEQUENT, a novel anomaly detection approach that dynamically uses state visit frequencies to compute anomaly scores for behaviors observed at test time. SEQUENT addresses several limitations within the approach employed in Chapter 3, offering practical applications such as ranking and clustering alerts to understand detected anomalies better. Results suggest that SEQUENT achieved considerably better performance than the approach presented in Chapter 3.

Part II of this dissertation explores how state machines can detect discrepancies (non-
conformances) between the observed runtime behaviors of microservices and the intended behaviors specified in the source code. Chapter 5 introduces CATMA, a lightweight tool for conducting conformance analysis on microservices applications. CATMA uses state machines to capture observed behaviors and compares them against insights derived from Dataflow Diagrams, representing the intended behaviors specified in the source code. This comparison reveals any non-conformances, and CATMA provides human-readable explanations for these non-conformances to aid developers with identifying potential starting points to debug their microservices applications. CATMA’s pilot study shows promising performance results and provides valuable insights to developers. Additionally, CATMA made a small impact in the open-source software community by identifying and fixing a
non-conformance detected in an open-source project.

Finally, Part III of this dissertation explores how state machines can guide an Evolutionary Algorithm in the automated generation of test cases for the REST APIs of microservices. Chapter 6 introduces MISH, a search heuristic that continuously learns a state machine model from log statements from microservices. These models are then used to generate more effective system-level test cases. MISH extracts various insights from the state machine to compute the fitness of test cases, which the Evolutionary Algorithm uses to generate better test cases. MISH demonstrates promising results in using state machines to guide an evolutionary algorithm toward generating more effective test cases, even outperforming a state-of-the-art search algorithm, MOSA, in specific scenarios. Additionally, a preliminary study suggests that integrating MISH as a part of MOSA could enhance the quality of system-level tests, creating an interesting future research direction.

This dissertation demonstrates the effectiveness of state machines in modeling the behavioral patterns of microservices across various practical applications, including monitoring, validation, and testing. Consequently, multiple toolchains and algorithms were developed to evaluate the models’ efficacy and to facilitate the use of state machines in representing the behavioral patterns of software systems. ... Read more

Deterministic Finite Automata (DFAs) are interpretable classification models, typically learned through merging states of a large tree-like automaton, an Augmented Prefix Tree Acceptor (APTA), according to heuristic suitability metrics. This paper introduces an ensembling approach for DFAs that does not depend on such heuristics. Starting from the APTA, we construct diverse automata by applying randomized sequences of state merges, while avoiding repetition of merges whenever possible. We also propose a novel graph-connectivity-based metric for inter-model variety. Experimental results on the STAMINA competition datasets yield improved predictive performance compared to models learned using state-of-the-art heuristics on sparse datasets, as well as a tight connection between inter-model variety and performance. ... Read more

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. ... Read more

Learning Deterministic Finite Automata (DFA) from given input data has been a central task in the field of Grammatical Inference, and progress in this area is of great interest from both theoretical and practical points of view. To address this challenge, several algorithms have been proposed and evaluated using established benchmarks. One such competition-winning algorithm, Evidence Driven State Merging (EDSM), uses a heuristic to learn a DFA from given data. However, improvements leveraging ensemble techniques from machine learning have yet to be explored. In this paper, we investigate ways to adapt the EDSM algorithm to fit into the ensemble learning framework and analyze the performance of such obtained models when applied to unseen data. To this end, we compare the performance of the ensembles to that of a standard EDSM-learned model, evaluating both their output quality and the diversity within each ensemble. The results indicate significant improvements in scenarios where the data is sparse. ... Read more

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. ... Read more

Learning a Deterministic Finite Automaton (DFA) from a language sample is an essential problem in grammatical inference, with applications in various fields, such as modeling and analyzing software systems. In this work, we propose approaches to create an ensemble of DFAs learned with the Evidence Driven State Merging algorithm. To produce varying models from the given data, we introduce two algorithms for manipulating the sequence orders. Additionally, we propose a similarity metric that allows for reducing the ensemble size by discarding similar models. The proposed approaches were analyzed and empirically evaluated using the dataset used during the StaMinA competition. Experimental results demonstrate that the methods for obtaining ensembles of DFAs presented in this work provide a number of advantages over the single DFA learned from the classical prefix tree acceptor using EDSM. ... Read more

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. ... Read more

Probabilistic deterministic Finite Automata (PDFA) learning is a machine learning method used for tasks requiring human understandability and more formal validation. In recent years we saw numerous applications of ensemble techniques with other machine learning models such as decision trees. Following the success of these attempts, in this paper, we aim to integrate ensemble methods into Alergia, which is a famous algorithm in the PDFA learning realm. We present a randomized variation of the Alergia algorithm and show how to build an ensemble out of it. Such an ensemble can visibly outperform a single Alergia model, which is documented by a series of experiments. Next, we present a custom distance metric measuring dissimilarity between a pair of Alergia models. We show how it can be used to build an Inter-Model Variety score quantifying the overall diversity of a group of models. Lastly, we analyze several methods that strive to select a well-performing diverse ensemble out of a big population of generated models. ... Read more

Deterministic Finite Automata (DFA) learning is the problem of reconstructing a DFA from its traces. For the development of methods for this problem, randomly sampled data is often used to train and test the performance of models. The choice of sampling technique can result in data sets with unforseen properties. The technique used in the STAMINA competition is such that that the number of final states and the size of alphabet were thought to potentially effect the test performance of resultant models. This was tested experimentally, by comparing the test performances of minimal models identified on traces from differently constructed DFAs. It was found that, although an increase in alphabet size results in overall longer traces that vary more with length, test performance still struggled. This shows that a DFA with a larger alphabet will need more traces than an equivalent smaller DFA. Additionally, it was found that the number of final states had a significant effect in the resulting test performance, and had a significant effect on the length of sampled traces. It was found that increased node count did not have an effect on sampled word length, and resulted in worse test performance. ... Read more

We increasingly encounter artificial intelligence-based technology in our daily lives, from smart home devices to self-driving cars to invisible systems running on our internet. Many artificial intelligence techniques use machine learning, algorithms that learn to predict or act based on collected data. Unfortunately, the most popular machine learning techniques, such as neural networks and ensembles, are so complex that humans cannot understand how they make predictions. Without understanding the prediction process, it is difficult to trust the model. Therefore, in this dissertation, we work on algorithms that learn models that are understandable to humans. The type of model we consider is a decision tree, a flowchart-like model that can easily be visualized so humans can understand it. These models ask a series of questions about an input and use the answers to derive a prediction.

Decision trees were popularized in the 1980s and extensively studied, but there is still room for improvement. The most popular algorithms for learning decision trees are fast but do not necessarily lead to the best performance. They are not robust, meaning tiny changes in the data can negatively influence the quality of their predictions. Also, the existing algorithms cannot be directly applied to problems where multiple sequential predictions have to be made. Therefore, this dissertation studies several techniques for learning decision trees for robustness and sequential decision making problems.

In Part I of the dissertation, we consider the problem of optimizing decision trees to make good predictions while being robust to small changes in the data. In Chapter 4, we tackle the problem of learning good decision trees quickly in this setting. We improved the runtime of an existing algorithm by speeding up one of the key operations. In Chapter 5, we solve the problem of finding the best possible robust decision tree. The idea is to formulate the problem as an Integer-Linear Program, a special mathematical problem that can be solved with highly optimized algorithms. In Chapter 6, we propose a method that allows learning of models that are more flexible in terms of robustness, i.e., by allowing data changes in different shapes. To create an efficient algorithm, we optimize only the model’s predictions, not the model’s question part. Finally, in Chapter 7, we use techniques for improving data privacy to enable robustness against another kind of data change: someone adding or removing data.

Part II of this dissertation is about sequential decision making problems. In these settings, we control a device or agent that tries to achieve some goal in a potentially uncertain environment. Sequential decision making problems are significantly different from the supervised learning problems considered in Part I since the data is not pre-collected. This class of problems encompasses many real-life problems; one of the simplest of those could be a thermostat that measures the temperature in a room and needs to decide whether to turn a heater on or off constantly. Highly complex problems such as self-driving cars can be modeled similarly. We aim to find a controller represented by a simple decision tree for such problems. Such a controller is called a policy, and by representing it with a small decision tree, humans can understand it. In Chapter 9, we assume that we have a perfect mathematical description of the problem and use it to find the best possible decision tree via Integer Programming techniques. Later in Chapter 10, we assume that we can only interact with the environment and do not have a mathematical description of the problem. In this setting, we find good policies by iteratively updating the tree to achieve better scores using gradient information.

In our research, we have developed various algorithms for learning decision trees in settings that are hard to optimize with existing methods: robust predictions and sequential decision making. We hope that our work on decision tree learning for these settings allows human-understandable machine learning to be used in more real applications in the future. By improving model understanding and robustness, we aim to enable machine learning systems that humans can trust.
... Read more

While artificial intelligence (AI) has undeniably ushered numerous solutions across various fields, the growing belief that AI can solve all problems overshadows their lack of transparency that comes along. Understanding how decisions are made and what has led to the output is crucial in critical systems to ensure accountability and trust.

This research proposes a complementary method leveraging inter-host distances that localise the outlying hosts, logs and the time frames, which require more advanced analysis. By relying on a variant of a prominent statistical method in the field of authorship attribution - Burrows Delta - the approach enhances transparency in identifying deviating hosts, logs and time frames. Hence, the proposed solution offers an understandable complementary method that preserves integrability by being a log-based method while enabling understandable pinpointing of the specific hosts, logs and time frames that warrant further advanced analysis. By providing insights into the behaviour of the hosts over time, a temporal summarisation for security analysts is provided, relaxing their need to go through all the log files to understand the hosts' behaviour.

The results show that a complementary method based on the textual content of the metadata of the logs provides alternative insight into the activities of the hosts than the attributes. Moreover, the behaviour defined by the proposed method requires less extensive lookup than the behaviour defined by attributes. The inter-host distances based on the textual content allow understandable localisation of the host behaviour over time. Hence, this research provides an understandable method that will summarise the behaviour of the hosts over time, which enables the localisation of the logs requiring more advanced, in-depth analysis, and thereby reducing the amount of logs security analists need to consider during a compromise. ... Read more