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.

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.

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.

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.

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.

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) 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.

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.

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.

As our world has become increasingly digital and the number of tasks performed by software has grown, so too has the volume of software logs and the importance of cybersecurity. Anomaly detection on software logs is crucial for securing systems and identifying
the causes of past attacks. Extensive research has focused on developing effective log
parsers and anomaly detection methods. However, the process between obtaining parsed
logs and feeding them to the anomaly detection methods has remained unchanged for years.
Typically, logs are ordered by their generation time and split into fixed-length timeframes,
which are then analyzed for anomalies. This approach can group unrelated logs together
while splitting related logs across different timeframes, potentially missing critical context
for anomaly detection.
This research explores the concept of views, which are different perspectives used on input
data. For example, logs can be grouped by the computer they are generated on, allowing the comparison of computers instead of arbitrary timeframes. The study demonstrates
that the performance of anomaly detection methods can vary significantly depending on the
views used.
To validate this, two different anomaly detection methods were applied to two different
datasets, showing that the effect is not specific to any particular dataset or detection method.
The research discusses three methods for creating these views and proposes a method to
suggest the most useful view by using views that contain a lot of different log keys and log
values. Additionally, partial views, such as grouping logs by user, are examined. These
views, although missing some logs, prove valuable for detecting anomalous behaviour as
grouping all logs of a user together and comparing that to other users, helped find the
anomalous user within a dataset that contain more than 1400 users in total.
The study also investigates the cause of anomalous behavior in Windows event logs by analyzing the scores of individual logs to identify words present in anomalous logs but absent
in normal ones. While this approach has some false positives, it effectively highlighted the
timing and consequences of an attack.
Finally, the research explores various ways to combine scores from different views and their
effects. Combining all views of EVTX data provides a reliable middle ground, useful when
the most effective view is unknown. It was found that taking the highest score from all views
results in many false positives and should be avoided. However, using the highest x scores
from all views, as long as x is greater than one, does not significantly differ from taking the
average score.

The behavior of software systems can be modeled as state machines by looking at the log data from these systems. Conventional algorithms, such as L∗, however, require too much memory to process log data when it gets too large. These algorithms must first load all available data into memory, which is often way too much.
The approach investigated to deal with this large amount of data is to load the data instead in an on-disk database. The thesis researches the viability of this approach and proposes an algorithm for it.
When log data is present in a database, a state machine can be constructed iteratively by gradually querying more and more data from the database. Each time more data is gathered, partial data can be used to construct a hypothesis for the state machine in question. Such an approach is thus a combination of an active learning part that queries more data and an passive learning part that constructs the state machine from partial data.
Database technologies can contribute to what such an algorithm should look like. Given the vast landscape of different database technologies, some can shape what kinds of queries can be more efficiently executed. This should be taken into account when constructing an algorithm that queries data from a database to construct a state machine.
This thesis starts with an overview of the existing state machine learning algorithms and relevant database technologies. Then a new algorithm is roposed and it is tested on different datasets and compared with existing algorithms.

Most of the adversarial attacks suitable for attacking decision tree ensembles work by doing multiple local searches from randomly selected starting points, around the to be attacked victim. In this thesis we investigate the impact of these starting points on the performance of the attack, and find that the starting points significantly impact the performance: some do much better than others. However, we do find that this is not the case for all attacked points, as there are large differences between points in how difficult they are to attack and for all datasets some points are always optimally attacked.

We compare the baseline randomly selected points to three alternative strategies. First, we try alternate random distributions, playing with both the standard deviation, to create a more narrow cone around the victim point, and mean, creating bimodal distributions further away from the victim point. We find that for some datasets these can give up to $5$-$7\%$ improved performance on subsets of the dataset, but these improvements do not generalize to the remainder of the dataset. In general, as long as the distribution is wide enough to successfully find starting points we do not find a substantial performance change.

Secondly, we try to remove the randomness and attack from a fixed direction. For the simpler datasets we find it is possible for a starting direction to perform better than random starting points, but for larger datasets performance becomes much worse. We also try an attack from all main directions around the victim point, which we find performs much worse than $5$-$20$ times fewer random points.

Lastly, we create an attack strategy where we select the closest points that scored well on previously attacked victims. We find that on smaller test sets this gets outperformed by the baseline, but when we extend the attack and give more possible previously well performing starting points we match or outperform the baseline slightly.

This thesis offers a comprehensive exploration of log-based anomaly detection within the domain of cybersecurity incident response. The research describes a different approach and explores relevant log features for language model training, experimentation with different language models and training methodologies, and the investigation of the potential contribution of extra contextual features. The newly proposed approach is compared against an already implemented baseline in a finite-state classifier called FlexFringe, assessing their performance in detecting malicious anomalies across diverse datasets and hosts.

Key findings from this research underscore the importance of including human language for the generation of coherent clusters and a better performance of pretrained language models over models that were fine-tuned or built from scratch. Furthermore, the influence of clustering parameters on cluster quality proves to be crucial for cluster quality. Additionally, we gained insights into how extra contextual features are useful for log analysis.

In light of these findings, the study provides several recommendations for future research, including the expansion of the methodology to accommodate various log sources, the enhancement of preprocessing techniques, the integration of newer and more advanced language models, and the pursuit of efficient hyperparameter optimization. This work contributes to the continual advancement of log-based anomaly detection and its critical role in enhancing cybersecurity practices.

Current backdoor attacks against federated learning (FL) strongly rely on universal triggers or semantic patterns, which can be easily detected and filtered by certain defense mechanisms such as norm clipping, comparing parameter divergences among local updates. In this work, we propose a new stealthy and robust backdoor attack with flexible triggers against FL defenses. To achieve this, we build a generative trigger function that can learn to manipulate the benign samples with an imperceptible flexible trigger pattern and simultaneously make the trigger pattern include the most significant hidden features of the attacker-chosen label. Moreover, our trigger generator can keep learning and adapt across different rounds, allowing it to adjust to changes in the global model. By filling the distinguishable difference (the mapping between the trigger pattern and target label), we make our attack naturally stealthy. Extensive experiments on real-world datasets verify the effectiveness and stealthiness of our attack compared to prior attacks on decentralized learning framework with eight well-studied defenses.

Malware poses a serious security risk in today’s digital environment. The defense against malware mainly relies on proactive detection. However, antivirus products often fail to detect new malware when the signature is not yet available. In the event of a malware infection, the common remediation strategy is reinstalling the system. However, the user loses their personal data, and thus it is not an ideal solution.

The academic works on malware remediation focus on system replay and recovery-oriented computing, which relies on heavy monitoring and is not suitable for a normal user’s personal computer. The work from Paleari et al. [31] proposed a remediation methodology that can be used entirely after the infection. They run the malware sample in the sandbox to observe the behavior and generate a revert operation for each action that modifies the system state. However, the limitation of such an approach is unable to deal with the potentially different behaviors in the sandbox and on the real hosts.

In this work, we propose a system that can generate user-specific recovery procedures, without the need of any monitoring in advance. We extend the work from Paleari et al. [31] by combining information from the infected machine. We first extract the environment configuration from the infected computer and configure the same context to the sandbox virtual machine, in order to eliminate the environmental influence on the malware’s behavior. After getting the behavior from the sandbox, we combine forensic evidence to understand the exact actions that happened on the system and generate the user-specific recovery procedures.

We implement a prototype based on Windows 10 and CAPE sandbox and perform an evaluation on 894 malware samples. We are able to recover 51.3% of the changes made by malware, which doubles the recovery rate compared to directly matching the sandbox result. Additionally, our experiment result also demonstrates significantly different actual behavior from the user’s machine and sandbox result. Our system design maximizes the use of information displayed in the sandbox, but the unshown behavior still leads to the biggest limitation of behavior-based recovery.

Network Intrusion Detection Systems (NIDSs) defend our computer networks against malicious network attacks. Anomaly-based NIDSs use machine learning classifiers to categorise incoming traffic. Research has shown that classifiers are vulnerable to adversarial examples, perturbed inputs that lead the classifier into misclassifying the input. Existing work has shown weaknesses in classifiers for classifying network traffic, but none have shown the possibility of automatically recreating network attacks that can bypass existing anomaly-based NIDSs. Regular methods for generating black-box adversarial examples create packets that are invalid. We present AGONI, a Multi-Objective Genetic Algorithm for
generating network packets that are both valid packets and adversarial examples for NIDSs. AGONI can successfully generate valid adversarial examples in multiple attack scenarios. Against the NIDS Suricata, 99.93% of the generated adversarial examples can successfully bypass the defence. We compare the performance of AGONI against randomly generating network packets, the Boundary Attack and an adjusted version of the Boundary Attack which can better create valid adversarial examples. Only AGONI consistently generates valid adversarial examples when compared to the Random Attack (82%), the Boundary Attack (0%) and the Networking Boundary Attack (74%).

This research paper focuses on the complex domain of alert-driven attack graphs. SAGE is a tool which generates such attack graphs (AGs) by using a suffix-based probabilistic deterministic finite automaton (S-PDFA). One of the substantial properties of this algorithm is to detect infrequent severe alerts while maintaining the context of attacks via the help of sink states and state IDs. This is a modelling assumption that we validate by answering the question driving this research: How does allowing the sink states to merge with other sink states affect the generated alert-driven attack graphs? Our research used a transparent methodology to obtain size, complexity and completeness statistics of the two algorithms. Afterwards, outstanding values in size and complexity allow us to filter insightful attack graphs, subject to head-to-head comparisons concerning their interpretability. We discovered that many remarkable changes happen in the outputted attack graphs, leading to an evident decrease in interpretability and increased loss of context. Concurrently, we do not detect substantial changes in size, complexity and completeness, leading us to believe that it is possible to unlock SAGE's full potential by adding specific thresholds for merging sink states. One proposed constraint is allowing only the merges of sinks at equal distance to the victim node. This alteration leads to similar results in all metrics, including interpretability, where some AGs show improvements.

SAGE is a deterministic and unsupervised learning pipeline that can generate attack graphs from intrusion alerts without input knowledge from a security analyst. Using a suffix-based probabilistic deterministic finite automaton (S-PDFA), the system compresses over 1 million alerts into less than 500 attack graphs (AGs), which are concise and manageable. Unlike other frequency analysis methods, SAGE does not discard infrequent high-severity alerts, which are crucial for learning the penetration strategies of attackers. This paper compares the baseline algorithm (i.e. S-PDFA) with a modelling assumption generated by swapping the S-PDFA with a PDFA. The aim is to validate the quality of SAGE and propose possible solutions for PDFA usage, allowing the algorithm to generate AGs in real-time. We compare them both quantitatively and qualitatively using size, complexity, completeness and interpretability metrics. Our findings show that AGs generated by the PDFA are more readable and as complete while being slightly larger (i.e. 16% larger) than the baseline S-PDFA. In certain cases, it can also better capture different attack strategies, proving that, if further optimized, it can perform better than the baseline.

The interpretability of an attack graph is a key principle as it reflects the difficulty of a specialist to take insights into attacker strategies. However, the quantification of interpretability is considered to be a subjective manner and complex attack graphs can be challenging to read and interpret. In this research paper, we propose a new metric for quantifying the interpretability of attack graphs, aiming for comparable results between attack graphs regardless of the chosen drawing configuration or generation method. We address the gap in existing metrics by combining elements from the theory of cognitive chunks of information and user-experience-related fields to measure interpretability in terms of cognitive load. Our metric leverages Gestalt principles to formalize the quantification of interpretability based on cognitive overload. Compared to a similar approach, the proposed metric reveals a high level of similarity with the baseline, however, qualitative analysis revealed the proposed metric eliminates certain discrepancies with the expert's opinion that the baseline metric presented. Furthermore, a use case of the metric is presented and we evaluate our metric by comparing attack graphs generated using different methods, such as deterministic finite automaton (S-PDFA), Markov chain, and suffix tree. Finally, further work is proposed toward the goal of completing the metric by incorporating the remaining Gestalt principles.