* **Computational Complexity:** The exponential increase in volume demands significantly more computational power and memory, making it challenging to process and analyze the data efficiently.

* **Overfitting:** High dimensionality increases the risk of overfitting, where a model learns the noise in the data rather than the actual pattern. Overfit models perform poorly on unseen data.

* **Statistical Significance:** As dimensions increase, the amount of data required to achieve statistical significance also increases exponentially, often making it impractical to collect sufficient data.

* **Visualization and Interpretability:** High-dimensional data are difficult to visualize and interpret, making it challenging to derive intuitive insights.

Due to these challenges, many dimensionality reduction techniques have been developed to transform high-dimensional data into a lower-dimensional form, aiming to preserve as much of the relevant information as possible. These techniques are discussed in the next section.

### 2.4.1.3 Feature Engineering techniques

The meticulous process of selecting the most relevant features, or constructing new features from existing ones, is known as *feature engineering*. This step can encompass normalization, transformation, and the creation of interaction terms among features. This complex process requires a deep understanding of the domain of study and the datasets, and is often a crucial step in the development of machine learning models [0].

In the context of Machine Learning, features essentially serve as the input variables *X* that a machine learning model employs to make predictions or inferences about the output variable *Y*. But not all features are equally informative. Some features may be redundant, irrelevant, or even detrimental to the model's performance. Irrelevant features are those that do not contribute to the predictive power of the model, while redundant features are those that are highly correlated with other features. Feature engineering techniques, can be used to build, transform or eliminate features, thereby reducing the dimensionality of the data and enhancing model performance [0].

* **Scaling and Normalization:** Scaling and normalization are techniques used to transform the features to a similar scale. This is particularly important for algorithms that rely on distance metrics, such as K-Nearest Neighbors (KNN) and Support Vector Machine (SVM). Scaling and normalization can also help accelerate the training process by reducing the number of iterations required for the model to converge. Some common techniques include min-max scaling, z-score normalization, and log transformation.

* **Feature Extraction:** This technique involves transforming the original set of features into a new set of features, which is usually of lower dimensionality. The new features are often combinations of the original features and aim to capture as much of the information in the original data as possible. Many methods exist, like Principal Component Analysis (PCA), Linear Discriminant Analysis (LDA) and t-distributed Stochastic Neighbor Embedding (t-SNE) are often employed to transform high-dimensional data into a lower-dimensional form are commonly used for feature extraction [0].

* **Feature Selection:** Unlike feature extraction, feature selection aims to pick a subset of the most important features from the original set, without changing them [0]. The goal is to
* **Computational Complexity:** The exponential increase in volume demands significantly more computational power and memory, making it challenging to process and analyze the data efficiently.

* **Overfitting:** High dimensionality increases the risk of overfitting, where a model learns the noise in the data rather than the actual pattern. Overfit models perform poorly on unseen data.

* **Statistical Significance:** As dimensions increase, the amount of data required to achieve statistical significance also increases exponentially, often making it impractical to collect sufficient data.

* **Visualization and Interpretability:** High-dimensional data are difficult to visualize and interpret, making it challenging to derive intuitive insights.

Due to these challenges, many dimensionality reduction techniques have been developed to transform high-dimensional data into a lower-dimensional form, aiming to preserve as much of the relevant information as possible. These techniques are discussed in the next section.

### 2.4.1.3 Feature Engineering techniques

The meticulous process of selecting the most relevant features, or constructing new features from existing ones, is known as *feature engineering*. This step can encompass normalization, transformation, and the creation of interaction terms among features. This complex process requires a deep understanding of the domain of study and the datasets, and is often a crucial step in the development of machine learning models [0].

In the context of Machine Learning, features essentially serve as the input variables *X* that a machine learning model employs to make predictions or inferences about the output variable *Y*. But not all features are equally informative. Some features may be redundant, irrelevant, or even detrimental to the model's performance. Irrelevant features are those that do not contribute to the predictive power of the model, while redundant features are those that are highly correlated with other features. Feature engineering techniques, can be used to build, transform or eliminate features, thereby reducing the dimensionality of the data and enhancing model performance [0].

* **Scaling and Normalization:** Scaling and normalization are techniques used to transform the features to a similar scale. This is particularly important for algorithms that rely on distance metrics, such as K-Nearest Neighbors (KNN) and Support Vector Machine (SVM). Scaling and normalization can also help accelerate the training process by reducing the number of iterations required for the model to converge. Some common techniques include min-max scaling, z-score normalization, and log transformation.

* **Feature Extraction:** This technique involves transforming the original set of features into a new set of features, which is usually of lower dimensionality. The new features are often combinations of the original features and aim to capture as much of the information in the original data as possible. Many methods exist, like Principal Component Analysis (PCA), Linear Discriminant Analysis (LDA) and t-distributed Stochastic Neighbor Embedding (t-SNE) are often employed to transform high-dimensional data into a lower-dimensional form are commonly used for feature extraction [0].

* **Feature Selection:** Unlike feature extraction, feature selection aims to pick a subset of the most important features from the original set, without changing them [0]. The goal is to
remove irrelevant or redundant features that do not contribute significantly to the model's performance. Techniques like Recursive Feature Elimination (RFE) and using importance scores from tree-based algorithms like Random Forest are popular methods for feature selection.

Both techniques have their own advantages and disadvantages, and the choice between the two often depends on the specific requirements of the task at hand. Feature extraction is generally more suitable when the original features do not have much interpretability to begin with, or when transforming features can lead to a more compact and effective representation. On the other hand, feature selection is often preferred when it is important to maintain the interpretability of the features, or when computational efficiency is a concern [0].

### 2.4.1.4 Evaluating Features with Correlation Tests

To assess the quality of features, various statistical measures can be employed. Correlation tests are statistical tests that measure the strength and direction of the relationship between two variables. Pearson, Kendall, and Spearman correlation coefficients are commonly used to quantify the linear or monotonic relationship between each feature and the target variable [0]. A high absolute value indicates a strong relationship, aiding in feature selection.

* **Pearson Correlation:** Measures the linear relationship between two variables. It ranges from -1 to 1, where -1 indicates a strong negative linear correlation, 1 indicates a strong positive linear correlation, and 0 indicates no linear correlation.

* **Kendall's Tau:** A non-parametric test that measures the strength and direction of a monotonic relationship between two variables.

* **Spearman's Rank:** Also a non-parametric test, it assesses how well an arbitrary monotonic function can describe the relationship between two variables without making any assumptions about the frequency distribution.

These techniques are useful for evaluating the relationship between each feature and allows generating correlation matrices, which can be used to identify redundant features. It's also possible to evaluate each feature independently through univariate feature selection techniques. In Python's Scikit-learn library [0], methods like *F-test* and the *p-value* are often used for this purpose. "

* **F-test value:** Measures the linear dependency between the feature variable and the target. A higher F-test value indicates a more useful feature.

* **p-value:** Indicates the probability of an F-test value this large arising if the null hypothesis is true. A smaller p-value suggests rejecting the null hypothesis, making the feature significant.

In summary, features are the foundational elements of any machine learning model. The quality of these features, along with how they are processed and utilized, can markedly impact the model's performance. The significance of feature engineering cannot be overstated. Properly engineered features can drastically reduce modeling errors, leading to more accurate and reliable predictions. It serves as a bridge between raw data and predictive models, ensuring that the models are fed with the most relevant and informative features.
remove irrelevant or redundant features that do not contribute significantly to the model's performance. Techniques like Recursive Feature Elimination (RFE) and using importance scores from tree-based algorithms like Random Forest are popular methods for feature selection.

Both techniques have their own advantages and disadvantages, and the choice between the two often depends on the specific requirements of the task at hand. Feature extraction is generally more suitable when the original features do not have much interpretability to begin with, or when transforming features can lead to a more compact and effective representation. On the other hand, feature selection is often preferred when it is important to maintain the interpretability of the features, or when computational efficiency is a concern [0].

### 2.4.1.4 Evaluating Features with Correlation Tests

To assess the quality of features, various statistical measures can be employed. Correlation tests are statistical tests that measure the strength and direction of the relationship between two variables. Pearson, Kendall, and Spearman correlation coefficients are commonly used to quantify the linear or monotonic relationship between each feature and the target variable [0]. A high absolute value indicates a strong relationship, aiding in feature selection.

* **Pearson Correlation:** Measures the linear relationship between two variables. It ranges from -1 to 1, where -1 indicates a strong negative linear correlation, 1 indicates a strong positive linear correlation, and 0 indicates no linear correlation.

* **Kendall's Tau:** A non-parametric test that measures the strength and direction of a monotonic relationship between two variables.

* **Spearman's Rank:** Also a non-parametric test, it assesses how well an arbitrary monotonic function can describe the relationship between two variables without making any assumptions about the frequency distribution.

These techniques are useful for evaluating the relationship between each feature and allows generating correlation matrices, which can be used to identify redundant features. It's also possible to evaluate each feature independently through univariate feature selection techniques. In Python's Scikit-learn library [0], methods like *F-test* and the *p-value* are often used for this purpose. "

* **F-test value:** Measures the linear dependency between the feature variable and the target. A higher F-test value indicates a more useful feature.

* **p-value:** Indicates the probability of an F-test value this large arising if the null hypothesis is true. A smaller p-value suggests rejecting the null hypothesis, making the feature significant.

In summary, features are the foundational elements of any machine learning model. The quality of these features, along with how they are processed and utilized, can markedly impact the model's performance. The significance of feature engineering cannot be overstated. Properly engineered features can drastically reduce modeling errors, leading to more accurate and reliable predictions. It serves as a bridge between raw data and predictive models, ensuring that the models are fed with the most relevant and informative features.
## 2.4.2 Embeddings

Embeddings are low-dimensional vector representations of high-dimensional objects. They are often used to capture complex relationships between objects and are particularly useful for machine learning tasks like clustering, classification, and link prediction. Embeddings are widely used in the field of natural language processing (NLP) to represent words, sentences, and documents [0]. In recent years, they have also been applied to graphs to learn node representations [0]. In this section, we will discuss the concept of embeddings and explore some common techniques for creating them.

### 2.4.2.1 Embedding Creation vs Feature Engineering

Both embedding creation and feature engineering are techniques used to transform data for machine learning models. However, they are different in terms of their goals and how they are achieved.

* **Embedding Creation:** Embedding creation is the process of learning a low-dimensional vector representation of a high-dimensional object. This involves mapping discrete objects, such as words in Natural Language Processing (NLP) or nodes in a graph in our case, to vectors of continuous values in a lower-dimensional space [0]. The goal is to capture the semantic or structural relationships between these objects. Specialized algorithms like Word2Vec for word embeddings or Node2Vec for graph embeddings are often used.

* **Feature Engineering:** As discussed before, it is a more general practice that involves creating new features or modifying existing ones to improve the performance of a machine learning model. While feature engineering can include creating embeddings, it also encompasses a wide range of other techniques like normalization, transformation, outlier detection, and handling missing values.

In general, feature engineering is a more manual process, while embedding creation is more automated. Feature engineering requires domain knowledge and understanding of the problem, while embedding creation can be done using a variety of machine learning techniques.

Thus, embedding creation is a specialized form of feature engineering aimed at mapping discrete objects to continuous vectors of numbers, usually for capturing complex relationships. Feature engineering, on the other hand, is a broader practice that can involve a variety of techniques, including but not limited to embedding creation.

### 2.4.2.2 Embeddings for graphs

Graph embedding techniques aim to map nodes and edges in a graph to vectors in a low-dimensional space [0]. The primary goal is to preserve the graph's structural properties, such as node connectivity and community structure, in the embedded space. These vectors can then be used for various machine learning tasks like clustering, classification, and link prediction. A quite complete overview of the different techniques can be found in "Knowledge Graphs" [0, Section 4.2]. Here are some common and advanced techniques:
## 2.4.2 Embeddings

Embeddings are low-dimensional vector representations of high-dimensional objects. They are often used to capture complex relationships between objects and are particularly useful for machine learning tasks like clustering, classification, and link prediction. Embeddings are widely used in the field of natural language processing (NLP) to represent words, sentences, and documents [0]. In recent years, they have also been applied to graphs to learn node representations [0]. In this section, we will discuss the concept of embeddings and explore some common techniques for creating them.

### 2.4.2.1 Embedding Creation vs Feature Engineering

Both embedding creation and feature engineering are techniques used to transform data for machine learning models. However, they are different in terms of their goals and how they are achieved.

* **Embedding Creation:** Embedding creation is the process of learning a low-dimensional vector representation of a high-dimensional object. This involves mapping discrete objects, such as words in Natural Language Processing (NLP) or nodes in a graph in our case, to vectors of continuous values in a lower-dimensional space [0]. The goal is to capture the semantic or structural relationships between these objects. Specialized algorithms like Word2Vec for word embeddings or Node2Vec for graph embeddings are often used.

* **Feature Engineering:** As discussed before, it is a more general practice that involves creating new features or modifying existing ones to improve the performance of a machine learning model. While feature engineering can include creating embeddings, it also encompasses a wide range of other techniques like normalization, transformation, outlier detection, and handling missing values.

In general, feature engineering is a more manual process, while embedding creation is more automated. Feature engineering requires domain knowledge and understanding of the problem, while embedding creation can be done using a variety of machine learning techniques.

Thus, embedding creation is a specialized form of feature engineering aimed at mapping discrete objects to continuous vectors of numbers, usually for capturing complex relationships. Feature engineering, on the other hand, is a broader practice that can involve a variety of techniques, including but not limited to embedding creation.

### 2.4.2.2 Embeddings for graphs

Graph embedding techniques aim to map nodes and edges in a graph to vectors in a low-dimensional space [0]. The primary goal is to preserve the graph's structural properties, such as node connectivity and community structure, in the embedded space. These vectors can then be used for various machine learning tasks like clustering, classification, and link prediction. A quite complete overview of the different techniques can be found in "Knowledge Graphs" [0, Section 4.2]. Here are some common and advanced techniques:
**Translational Models** The first type of graph embeddings techniques is based around using transactional models that interpret edge labels as transformations from subject nodes to object nodes „Knowledge Graphs“.

* **TransE**: is one of the earliest and most straightforward translational models. It represents entities as points in a vector space and relations as translations between these points. The primary idea is that for a valid triple (h, r, t), the equation $h+r=t$ should hold, where h stands for the head entity, r represents the relation, and t is the tail entity. This model is simple and computationally efficient but is limited in its ability to capture complex relationships [0].

* **TransH**: TransH extends TransE by introducing relation-specific hyperplanes. This allows the model to capture more complex relationships by projecting the entity embeddings onto these hyperplanes before performing translations [0].

* **TransR**: TransR goes a step further by not only introducing relation-specific hyperplanes but also relation-specific translations. This allows for a more flexible representation of relations, accommodating various types of complexities [0].

* Other improvements include *TransD* or *MuRP*, which shows that research in this domain is still very active.

**Tensor Decomposition Models** Tensor decomposition models represent entities and relations as vectors or matrices in a low-dimensional space. These models are based on the assumption that the relationship between entities can be represented by a bilinear function. They are computationally efficient and can capture complex relationships, but they are also limited in their ability to model asymmetric and reflexive relations.

* **RESCAL**: RESCAL employs a bilinear model where each relation is represented by a full-rank matrix. This allows for capturing asymmetric and reflexive relations but at the cost of increased computational complexity [0].

* **DistMult**: DistMult simplifies RESCAL by assuming that the relation matrices are diagonal. This reduces the number of parameters and computational complexity, making it more scalable [0] [0].

* **ComplEx**: ComplEx extends DistMult by introducing complex-valued embeddings. This allows the model to capture asymmetric relations effectively while maintaining computational efficiency [0] [0].

**Neural Models** Neural models employ neural networks to learn the features of entities and relations. This provides a more flexible and adaptive approach to graph embeddings.

* **ConvKB**: ConvKB employs a convolutional neural network to automatically learn the features of entities and relations. It is technically a translational model as introduced before, but uses a convolutional layer to capture the interactions between entities and relations. This provides a more flexible and adaptive approach to graph embeddings [0].

* **RotatE**: RotatE uses complex rotations in the embedding space to model relations. This neural model captures the semantics of relations in a more expressive manner [0].
**Translational Models** The first type of graph embeddings techniques is based around using transactional models that interpret edge labels as transformations from subject nodes to object nodes „Knowledge Graphs“.

* **TransE**: is one of the earliest and most straightforward translational models. It represents entities as points in a vector space and relations as translations between these points. The primary idea is that for a valid triple (h, r, t), the equation $h+r=t$ should hold, where h stands for the head entity, r represents the relation, and t is the tail entity. This model is simple and computationally efficient but is limited in its ability to capture complex relationships [0].

* **TransH**: TransH extends TransE by introducing relation-specific hyperplanes. This allows the model to capture more complex relationships by projecting the entity embeddings onto these hyperplanes before performing translations [0].

* **TransR**: TransR goes a step further by not only introducing relation-specific hyperplanes but also relation-specific translations. This allows for a more flexible representation of relations, accommodating various types of complexities [0].

* Other improvements include *TransD* or *MuRP*, which shows that research in this domain is still very active.

**Tensor Decomposition Models** Tensor decomposition models represent entities and relations as vectors or matrices in a low-dimensional space. These models are based on the assumption that the relationship between entities can be represented by a bilinear function. They are computationally efficient and can capture complex relationships, but they are also limited in their ability to model asymmetric and reflexive relations.

* **RESCAL**: RESCAL employs a bilinear model where each relation is represented by a full-rank matrix. This allows for capturing asymmetric and reflexive relations but at the cost of increased computational complexity [0].

* **DistMult**: DistMult simplifies RESCAL by assuming that the relation matrices are diagonal. This reduces the number of parameters and computational complexity, making it more scalable [0] [0].

* **ComplEx**: ComplEx extends DistMult by introducing complex-valued embeddings. This allows the model to capture asymmetric relations effectively while maintaining computational efficiency [0] [0].

**Neural Models** Neural models employ neural networks to learn the features of entities and relations. This provides a more flexible and adaptive approach to graph embeddings.

* **ConvKB**: ConvKB employs a convolutional neural network to automatically learn the features of entities and relations. It is technically a translational model as introduced before, but uses a convolutional layer to capture the interactions between entities and relations. This provides a more flexible and adaptive approach to graph embeddings [0].

* **RotatE**: RotatE uses complex rotations in the embedding space to model relations. This neural model captures the semantics of relations in a more expressive manner [0].
* **SDNE (Structural Deep Network Embedding):** SDNE employs a deep autoencoder to learn complex and non-linear node embeddings while preserving first-order and second-order proximities. It is particularly effective for capturing intricate patterns and structures in the graph [0].

* **R-GCN:** Relational Graph Convolutional Networks (R-GCNs) combine the strengths of GCNs and traditional embedding methods to capture both topological and semantic information [0]. A more recent study by Degraeve et al. argues that the main contribution of R-GCN lies in its message passing paradigm rather than the learned weights. This paper introduces a variant called Random R-GCN (RR-GCN) [0].

* **ConvE:** ConvE employs convolutional layers to capture local and global interactions between entities and relations, offering a more expressive representation [0].

**Language Models** Language models utilize pre-trained language models to enrich the embeddings with contextual information. This approach leverages the recent developments of language models to capture the semantics of entities and relations.

* **BERT for KGE:** Utilizing pre-trained BERT models, this approach leverages the power of language models to enrich the embeddings with contextual information [0].

* **BART KGE:** Bidirectional and Auto-Regressive Transformers (BART) is a denoising autoencoder that can be used for various NLP tasks. This approach utilizes BART to learn entity and relation embeddings. The paper introducing this also compares other LLM like GPT-2 [0].

* Due to the recent developments in NLP, this domain is still very active, and new approaches are being developed regularly.

### 2.4.2.3 Word Embeddings

Word embeddings are vector representations of words in a low-dimensional space. They are often used as input for machine learning models in natural language processing (NLP) tasks like text classification, sentiment analysis, and machine translation. Word embeddings are typically learned from large text corpora using unsupervised learning techniques like Word2Vec and GloVe. These embeddings can then be used to capture semantic relationships between words and phrases, which is particularly useful for NLP tasks [0].

* **Word2Vec:** Word2Vec is a popular algorithm for learning word embeddings from text data. It employs a shallow neural network to learn the embeddings and is often used as a pre-processing step for NLP tasks [0].

* **GloVe:** Global Vectors for Word Representation (GloVe) is another popular algorithm for learning word embeddings. It is based on the co-occurrence matrix of words and utilizes matrix factorization to learn the embeddings [0].

**Graph Embeddings** Graph embeddings are vector representations of nodes in a graph. Graph embeddings are typically learned using unsupervised learning techniques like Node2Vec and DeepWalk. These embeddings can then be used to capture structural relationships between nodes, which is particularly useful for graph analytics tasks [0].
* **SDNE (Structural Deep Network Embedding):** SDNE employs a deep autoencoder to learn complex and non-linear node embeddings while preserving first-order and second-order proximities. It is particularly effective for capturing intricate patterns and structures in the graph [0].

* **R-GCN:** Relational Graph Convolutional Networks (R-GCNs) combine the strengths of GCNs and traditional embedding methods to capture both topological and semantic information [0]. A more recent study by Degraeve et al. argues that the main contribution of R-GCN lies in its message passing paradigm rather than the learned weights. This paper introduces a variant called Random R-GCN (RR-GCN) [0].

* **ConvE:** ConvE employs convolutional layers to capture local and global interactions between entities and relations, offering a more expressive representation [0].

**Language Models** Language models utilize pre-trained language models to enrich the embeddings with contextual information. This approach leverages the recent developments of language models to capture the semantics of entities and relations.

* **BERT for KGE:** Utilizing pre-trained BERT models, this approach leverages the power of language models to enrich the embeddings with contextual information [0].

* **BART KGE:** Bidirectional and Auto-Regressive Transformers (BART) is a denoising autoencoder that can be used for various NLP tasks. This approach utilizes BART to learn entity and relation embeddings. The paper introducing this also compares other LLM like GPT-2 [0].

* Due to the recent developments in NLP, this domain is still very active, and new approaches are being developed regularly.

### 2.4.2.3 Word Embeddings

Word embeddings are vector representations of words in a low-dimensional space. They are often used as input for machine learning models in natural language processing (NLP) tasks like text classification, sentiment analysis, and machine translation. Word embeddings are typically learned from large text corpora using unsupervised learning techniques like Word2Vec and GloVe. These embeddings can then be used to capture semantic relationships between words and phrases, which is particularly useful for NLP tasks [0].

* **Word2Vec:** Word2Vec is a popular algorithm for learning word embeddings from text data. It employs a shallow neural network to learn the embeddings and is often used as a pre-processing step for NLP tasks [0].

* **GloVe:** Global Vectors for Word Representation (GloVe) is another popular algorithm for learning word embeddings. It is based on the co-occurrence matrix of words and utilizes matrix factorization to learn the embeddings [0].

**Graph Embeddings** Graph embeddings are vector representations of nodes in a graph. Graph embeddings are typically learned using unsupervised learning techniques like Node2Vec and DeepWalk. These embeddings can then be used to capture structural relationships between nodes, which is particularly useful for graph analytics tasks [0].
* **One-Hot Encoding**: This is a simple technique that represents each node as a vector of 0s and 1s, where the length of the vector is equal to the number of nodes in the graph. The vector contains a 1 at the index corresponding to the node and 0s everywhere else. As is, this method is not really suitable for large graphs as it results in a high-dimensional and sparse matrix representation [0].

* **Node2Vec**: This algorithm learns continuous feature representations for nodes by optimizing a neighborhood-preserving objective. It employs biased random walks and uses the Skip-gram model to generate embeddings. Node2Vec is particularly effective for capturing local structures and can be fine-tuned for specific tasks [0].

* **DeepWalk**: Similar to Node2Vec, DeepWalk uses random walks to generate node sequences. It employs the Skip-gram model from natural language processing to learn embeddings. Unlike Node2Vec, it does not use biased walks, making it more suitable for capturing global structures [0].

* **Spectral Clustering**: This technique is based on the spectral theory of graphs. It utilizes the eigenvalues and eigenvectors of the Laplacian matrix of the graph to find an optimal embedding. Spectral Clustering is particularly useful for community detection and can capture the global structure of the graph [0] [0].

* **LINE**: Large-scale Information Network Embedding (LINE) aims to preserve both local and global network structures. It optimizes two objectives: first-order and second-order proximities between nodes. LINE is scalable and can handle large graphs efficiently [0].

* **Graph Factorization**: This method directly factorizes the adjacency matrix of the graph to learn node embeddings, making it computationally efficient but less capable of capturing complex structures. It is often used for large-scale graphs where computational resources are limited [0].

### 2.4.3 Other preprocessing techniques for Machine Learning

When working with real-world data and datasets, it is common to find issues like missing values, outliers, and imbalanced classes that can adversely affect the performance of machine learning models. In this section, we will discuss some common preprocessing techniques used to improve the quality of data and ensure that the models can learn effectively.

#### 2.4.3.1 Data Cleaning

Data cleaning is the process of detecting and correcting errors in the data. It is a crucial step in data preprocessing and involves various techniques like outlier detection, handling missing values, and data normalization. Data cleaning is necessary to ensure that the data is accurate and consistent, which is essential for machine learning models to learn effectively.

* **Outlier Detection**: Outliers are data points that deviate significantly from the rest of the dataset. They can be caused by errors in data collection or genuine variations. Outliers can skew the model's learning and should be identified and handled appropriately, either by removal or transformation.
* **One-Hot Encoding**: This is a simple technique that represents each node as a vector of 0s and 1s, where the length of the vector is equal to the number of nodes in the graph. The vector contains a 1 at the index corresponding to the node and 0s everywhere else. As is, this method is not really suitable for large graphs as it results in a high-dimensional and sparse matrix representation [0].

* **Node2Vec**: This algorithm learns continuous feature representations for nodes by optimizing a neighborhood-preserving objective. It employs biased random walks and uses the Skip-gram model to generate embeddings. Node2Vec is particularly effective for capturing local structures and can be fine-tuned for specific tasks [0].

* **DeepWalk**: Similar to Node2Vec, DeepWalk uses random walks to generate node sequences. It employs the Skip-gram model from natural language processing to learn embeddings. Unlike Node2Vec, it does not use biased walks, making it more suitable for capturing global structures [0].

* **Spectral Clustering**: This technique is based on the spectral theory of graphs. It utilizes the eigenvalues and eigenvectors of the Laplacian matrix of the graph to find an optimal embedding. Spectral Clustering is particularly useful for community detection and can capture the global structure of the graph [0] [0].

* **LINE**: Large-scale Information Network Embedding (LINE) aims to preserve both local and global network structures. It optimizes two objectives: first-order and second-order proximities between nodes. LINE is scalable and can handle large graphs efficiently [0].

* **Graph Factorization**: This method directly factorizes the adjacency matrix of the graph to learn node embeddings, making it computationally efficient but less capable of capturing complex structures. It is often used for large-scale graphs where computational resources are limited [0].

### 2.4.3 Other preprocessing techniques for Machine Learning

When working with real-world data and datasets, it is common to find issues like missing values, outliers, and imbalanced classes that can adversely affect the performance of machine learning models. In this section, we will discuss some common preprocessing techniques used to improve the quality of data and ensure that the models can learn effectively.

#### 2.4.3.1 Data Cleaning

Data cleaning is the process of detecting and correcting errors in the data. It is a crucial step in data preprocessing and involves various techniques like outlier detection, handling missing values, and data normalization. Data cleaning is necessary to ensure that the data is accurate and consistent, which is essential for machine learning models to learn effectively.

* **Outlier Detection**: Outliers are data points that deviate significantly from the rest of the dataset. They can be caused by errors in data collection or genuine variations. Outliers can skew the model's learning and should be identified and handled appropriately, either by removal or transformation.
* **Handling Missing Values:** Missing data can lead to biased or incorrect model training. Techniques for handling missing values include imputation, where missing values are replaced with statistical measures like mean, median, or mode, and deletion, where rows with missing values are removed.

* **Data Normalization:** Features with different scales can affect the performance of machine learning algorithms. Normalization rescales the features to a standard range, usually [0, 1], or transforms them to have a mean of 0 and a standard deviation of 1.

* **Encoding Categorical Variables:** Many machine learning algorithms require numerical input and output variables. Categorical variables are converted to numerical format through techniques like one-hot encoding or label encoding.

* **Text Cleaning:** In natural language processing tasks, text data may require cleaning to remove irrelevant characters, correct typos, or standardize text format.

* **Duplicate Removal:** Duplicate entries can bias the model and should be identified and removed from the dataset.

* **Feature Engineering:** While not strictly data cleaning, feature engineering involves transforming existing features or creating new ones to improve model performance.

### 2.4.3.2 Dataset splitting and sampling

One other typical step is the division of the dataset into training and testing sets. This separation is crucial for evaluating the generalization performance of a model. The training set is used to train the model, while the testing set is used to evaluate its performance on unseen data. Failing to separate these sets can lead to overfitting, where the model performs well on the training data but poorly on new, unseen data.

Various techniques exist for dataset splitting and sampling, each with its own advantages and disadvantages:

* **Random Split:** The dataset is randomly divided into training and testing sets based on a given ratio, such as 70% for training and 30% for testing. This method is simple but may result in imbalanced classes in the splits.

* **Stratified Split:** Similar to random split, but ensures that the distribution of classes is the same in both training and testing sets. This is particularly useful for imbalanced datasets.

* **k-Fold Cross-Validation:** The dataset is divided into 'k' subsets or "folds." The model is trained on k-1 folds and tested on the remaining fold. This process is repeated k times, each time with a different fold as the testing set. The average performance metric is used for evaluation.

* **Leave-One-Out Cross-Validation (LOOCV):** A special case of k-Fold Cross-Validation where k is equal to the number of data points. Each data point is used once as the test set while the remaining points form the training set.

* **Bootstrapping:** Random samples are drawn with replacement from the dataset to create multiple training sets. The model is trained and tested on these sets, and the average performance is calculated.
* **Handling Missing Values:** Missing data can lead to biased or incorrect model training. Techniques for handling missing values include imputation, where missing values are replaced with statistical measures like mean, median, or mode, and deletion, where rows with missing values are removed.

* **Data Normalization:** Features with different scales can affect the performance of machine learning algorithms. Normalization rescales the features to a standard range, usually [0, 1], or transforms them to have a mean of 0 and a standard deviation of 1.

* **Encoding Categorical Variables:** Many machine learning algorithms require numerical input and output variables. Categorical variables are converted to numerical format through techniques like one-hot encoding or label encoding.

* **Text Cleaning:** In natural language processing tasks, text data may require cleaning to remove irrelevant characters, correct typos, or standardize text format.

* **Duplicate Removal:** Duplicate entries can bias the model and should be identified and removed from the dataset.

* **Feature Engineering:** While not strictly data cleaning, feature engineering involves transforming existing features or creating new ones to improve model performance.

### 2.4.3.2 Dataset splitting and sampling

One other typical step is the division of the dataset into training and testing sets. This separation is crucial for evaluating the generalization performance of a model. The training set is used to train the model, while the testing set is used to evaluate its performance on unseen data. Failing to separate these sets can lead to overfitting, where the model performs well on the training data but poorly on new, unseen data.

Various techniques exist for dataset splitting and sampling, each with its own advantages and disadvantages:

* **Random Split:** The dataset is randomly divided into training and testing sets based on a given ratio, such as 70% for training and 30% for testing. This method is simple but may result in imbalanced classes in the splits.

* **Stratified Split:** Similar to random split, but ensures that the distribution of classes is the same in both training and testing sets. This is particularly useful for imbalanced datasets.

* **k-Fold Cross-Validation:** The dataset is divided into 'k' subsets or "folds." The model is trained on k-1 folds and tested on the remaining fold. This process is repeated k times, each time with a different fold as the testing set. The average performance metric is used for evaluation.

* **Leave-One-Out Cross-Validation (LOOCV):** A special case of k-Fold Cross-Validation where k is equal to the number of data points. Each data point is used once as the test set while the remaining points form the training set.

* **Bootstrapping:** Random samples are drawn with replacement from the dataset to create multiple training sets. The model is trained and tested on these sets, and the average performance is calculated.
### 2.4.3.3 Dealing with Imbalanced Datasets

Imbalanced datasets are those where the classes are not represented equally. This is a common issue in machine learning, especially in classification problems. An imbalanced dataset can lead to a biased model that may not effectively predict the minority class. Therefore, it is crucial to address this issue during data preprocessing.

* **Why it is Necessary**: In imbalanced datasets, machine learning algorithms tend to be biased towards the majority class, ignoring the minority class. This results in poor classification performance for the minority class, which is often the class of interest in problems like fraud detection, medical diagnosis, etc.

* **Oversampling**: This involves adding more copies of the minority class. Oversampling can be random with replacement, or it can involve generating synthetic samples.

* **Undersampling**: This involves removing some of the samples of the majority class. This method is generally not preferred as it can lead to loss of data.

* **SMOTE (Synthetic Minority Over-sampling Technique)**: SMOTE is an oversampling method that creates synthetic samples in the feature space. It selects two or more similar instances (using a distance measure) and perturbing an instance one at a time by a random amount within the difference to the neighboring instances.

* **ADASYN (Adaptive Synthetic Sampling)**: Similar to SMOTE, but it uses a weighted distribution for different minority class examples according to their level of difficulty in learning.

* **Cost-sensitive Learning**: This involves modifying the algorithm to increase the weight of the minority class during training, thereby making the algorithm more sensitive to it.

* **Ensemble Methods**: Methods like Random Forest and Gradient Boosting can be used with techniques like bagging and boosting to handle imbalanced datasets effectively.

* **Resampling Methods**: These involve randomly partitioning the data into subsets, balancing each subset, and then aggregating the results.

To conclude this section, data preprocessing is a crucial step in machine learning. The number of concepts and techniques discussed here is by no means exhaustive, which further highlights the importance and complexity of data preprocessing.

## 2.5 Machine Learning and Deep Learning

In the preceding sections, we have discussed the importance of data preprocessing and feature engineering for machine learning. In this section, we will discuss the machine learning pipeline and explore some common machine learning algorithms. We will also discuss deep learning and neural networks especially in the context of graphs, since they have gained popularity in recent years due to their superior performance on many tasks.
### 2.4.3.3 Dealing with Imbalanced Datasets

Imbalanced datasets are those where the classes are not represented equally. This is a common issue in machine learning, especially in classification problems. An imbalanced dataset can lead to a biased model that may not effectively predict the minority class. Therefore, it is crucial to address this issue during data preprocessing.

* **Why it is Necessary**: In imbalanced datasets, machine learning algorithms tend to be biased towards the majority class, ignoring the minority class. This results in poor classification performance for the minority class, which is often the class of interest in problems like fraud detection, medical diagnosis, etc.

* **Oversampling**: This involves adding more copies of the minority class. Oversampling can be random with replacement, or it can involve generating synthetic samples.

* **Undersampling**: This involves removing some of the samples of the majority class. This method is generally not preferred as it can lead to loss of data.

* **SMOTE (Synthetic Minority Over-sampling Technique)**: SMOTE is an oversampling method that creates synthetic samples in the feature space. It selects two or more similar instances (using a distance measure) and perturbing an instance one at a time by a random amount within the difference to the neighboring instances.

* **ADASYN (Adaptive Synthetic Sampling)**: Similar to SMOTE, but it uses a weighted distribution for different minority class examples according to their level of difficulty in learning.

* **Cost-sensitive Learning**: This involves modifying the algorithm to increase the weight of the minority class during training, thereby making the algorithm more sensitive to it.

* **Ensemble Methods**: Methods like Random Forest and Gradient Boosting can be used with techniques like bagging and boosting to handle imbalanced datasets effectively.

* **Resampling Methods**: These involve randomly partitioning the data into subsets, balancing each subset, and then aggregating the results.

To conclude this section, data preprocessing is a crucial step in machine learning. The number of concepts and techniques discussed here is by no means exhaustive, which further highlights the importance and complexity of data preprocessing.

## 2.5 Machine Learning and Deep Learning

In the preceding sections, we have discussed the importance of data preprocessing and feature engineering for machine learning. In this section, we will discuss the machine learning pipeline and explore some common machine learning algorithms. We will also discuss deep learning and neural networks especially in the context of graphs, since they have gained popularity in recent years due to their superior performance on many tasks.
## 2.5.1 Machine Learning

Machine learning is a cornerstone in the field of artificial intelligence and has been instrumental in driving many of today's technological and scientific breakthroughs. From natural language processing to computer vision, machine learning algorithms play a critical role in making sense of large and complex data sets.

### 2.5.1.1 What is Machine Learning

Machine learning is a subfield of artificial intelligence that provides systems the ability to automatically learn and improve from experience without being explicitly programmed. This learning process is based on the recognition of complex patterns in data and the making of intelligent decisions based on them [0].

The machine learning pipeline typically involves several steps including some pre-steps like data collection, preprocessing, feature extraction that we have already discussed before, usually followed by model training, evaluation, and deployment. Algorithms are trained on a dataset, and the learned patterns are used to make predictions or decisions without human intervention. ML algorithms can be broadly classified into three categories [0]:

* **Supervised Learning:** Algorithms are trained on labeled data, and the aim is to make predictions or map inputs to outputs.

* **Unsupervised Learning:** Algorithms are trained on unlabeled data, focusing on the underlying structure or distribution in the data.

* **Reinforcement Learning:** Algorithms learn to perform an action from state to state to maximize some type of reward or objective function.

In the following, we will focus on supervised and unsupervised learning, as they are the most relevant to our work.

### 2.5.1.2 Model Evaluation

Evaluating the performance of a machine learning model is crucial for understanding its effectiveness and suitability for a given task. It is not a trivial task as it depends on various factors like the type of data, the problem at hand, and the model itself [0]. In this section, we will discuss some common evaluation metrics for classification and regression models.

**Precision** Precision is the ratio of correctly predicted positive observations to the total predicted positives. The formula for precision is:

$$ \text{Precision} = \frac{\text{True Positives}}{\text{True Positives} + \text{False Positives}} $$
## 2.5.1 Machine Learning

Machine learning is a cornerstone in the field of artificial intelligence and has been instrumental in driving many of today's technological and scientific breakthroughs. From natural language processing to computer vision, machine learning algorithms play a critical role in making sense of large and complex data sets.

### 2.5.1.1 What is Machine Learning

Machine learning is a subfield of artificial intelligence that provides systems the ability to automatically learn and improve from experience without being explicitly programmed. This learning process is based on the recognition of complex patterns in data and the making of intelligent decisions based on them [0].

The machine learning pipeline typically involves several steps including some pre-steps like data collection, preprocessing, feature extraction that we have already discussed before, usually followed by model training, evaluation, and deployment. Algorithms are trained on a dataset, and the learned patterns are used to make predictions or decisions without human intervention. ML algorithms can be broadly classified into three categories [0]:

* **Supervised Learning:** Algorithms are trained on labeled data, and the aim is to make predictions or map inputs to outputs.

* **Unsupervised Learning:** Algorithms are trained on unlabeled data, focusing on the underlying structure or distribution in the data.

* **Reinforcement Learning:** Algorithms learn to perform an action from state to state to maximize some type of reward or objective function.

In the following, we will focus on supervised and unsupervised learning, as they are the most relevant to our work.

### 2.5.1.2 Model Evaluation

Evaluating the performance of a machine learning model is crucial for understanding its effectiveness and suitability for a given task. It is not a trivial task as it depends on various factors like the type of data, the problem at hand, and the model itself [0]. In this section, we will discuss some common evaluation metrics for classification and regression models.

**Precision** Precision is the ratio of correctly predicted positive observations to the total predicted positives. The formula for precision is:

$$ \text{Precision} = \frac{\text{True Positives}}{\text{True Positives} + \text{False Positives}} $$
**Recall** Recall is the ratio of correctly predicted positive observations to all the observations in the actual class. The formula for recall is:

$$ \text{Recall} = \frac{\text{True Positives}}{\text{True Positives}+\text{False Negatives}} $$

**F-1 Score** The F-1 Score is the weighted average of Precision and Recall, and it ranges from 0 to 1. The formula for the F-1 Score is:

$$ \text{F-1 Score} = 2 \times \frac{\text{Precision} \times \text{Recall}}{\text{Precision}+\text{Recall}} $$

**Accuracy** Accuracy is the ratio of correctly predicted observations to the total observations. The formula for accuracy is:

$$ \text{Accuracy} = \frac{\text{True Positives}+\text{True Negatives}}{\text{Total Observations}} $$

These are the most common metrics used for evaluating classification models. Other metrics like the Area Under the Curve (AUC) and the Receiver Operating Characteristic (ROC) curve are also used for evaluating binary classification models. For regression models, metrics like Mean Squared Error (MSE), Root Mean Squared Error (RMSE), and Mean Absolute Error (MAE) are commonly used [0].

### 2.5.2 Machine Learning Models for Binary Classification

Binary classification is a supervised learning task where the goal is to predict a binary outcome, i.e., one of two possible classes (0 or 1). This is a truly classical task for a ML model, with a range of applicable algorithms. As such, we rely on Python's Scikit-learn library for implementation.

**Logistic Regression** A specialized form of regression tailored for predicting binary outcomes. It employs the logistic function to map predicted values between 0 and 1. While straightforward and interpretable, its performance may be limited on complex, non-linear data [0].

The logistic function is defined as:

$$ P(y = 1|x) = \frac{1}{1+e^{-(\beta_0+\beta_1 x)}} $$

Where $\beta_0$ is the intercept and $\beta_1$ is the coefficient for the predictor variable $x$.

**Decision Trees** These are versatile models used for both classification and regression. They partition the feature space into regions, making decisions at each node. While easy to visualize, they are susceptible to overfitting [0].
**Recall** Recall is the ratio of correctly predicted positive observations to all the observations in the actual class. The formula for recall is:

$$ \text{Recall} = \frac{\text{True Positives}}{\text{True Positives}+\text{False Negatives}} $$

**F-1 Score** The F-1 Score is the weighted average of Precision and Recall, and it ranges from 0 to 1. The formula for the F-1 Score is:

$$ \text{F-1 Score} = 2 \times \frac{\text{Precision} \times \text{Recall}}{\text{Precision}+\text{Recall}} $$

**Accuracy** Accuracy is the ratio of correctly predicted observations to the total observations. The formula for accuracy is:

$$ \text{Accuracy} = \frac{\text{True Positives}+\text{True Negatives}}{\text{Total Observations}} $$

These are the most common metrics used for evaluating classification models. Other metrics like the Area Under the Curve (AUC) and the Receiver Operating Characteristic (ROC) curve are also used for evaluating binary classification models. For regression models, metrics like Mean Squared Error (MSE), Root Mean Squared Error (RMSE), and Mean Absolute Error (MAE) are commonly used [0].

### 2.5.2 Machine Learning Models for Binary Classification

Binary classification is a supervised learning task where the goal is to predict a binary outcome, i.e., one of two possible classes (0 or 1). This is a truly classical task for a ML model, with a range of applicable algorithms. As such, we rely on Python's Scikit-learn library for implementation.

**Logistic Regression** A specialized form of regression tailored for predicting binary outcomes. It employs the logistic function to map predicted values between 0 and 1. While straightforward and interpretable, its performance may be limited on complex, non-linear data [0].

The logistic function is defined as:

$$ P(y = 1|x) = \frac{1}{1+e^{-(\beta_0+\beta_1 x)}} $$

Where $\beta_0$ is the intercept and $\beta_1$ is the coefficient for the predictor variable $x$.

**Decision Trees** These are versatile models used for both classification and regression. They partition the feature space into regions, making decisions at each node. While easy to visualize, they are susceptible to overfitting [0].
Decision Trees use metrics like Gini impurity or entropy to make splits:

$$Gini(T) = 1 - \sum_{i=1}^{C} p_{i}^{2}$$

Where T is a node and $p_i$ is the proportion of class i instances among the training instances in node T.

**Random Forest** An ensemble technique that aggregates predictions from multiple decision trees. Known for its robustness and ability to handle large, high-dimensional data [0].

The final prediction is an average or majority vote from all trees:

$$\hat{y} = \frac{1}{n} \sum_{i=1}^{n} \hat{y}_{i}$$

Where $\hat{y}$ is the final prediction and $\hat{y}_i$ is the prediction from the $i^{th}$ tree.

**Support Vector Machines (SVM)** Effective for both classification and regression, SVMs find the hyperplane that best separates the data into classes. They excel in high-dimensional spaces [0].

The objective is to maximize the margin between classes:

$$\max_{w,b} \frac{2}{\|w\|}$$

Where $w$ is the weight vector and $b$ is the bias term.

**k-Nearest Neighbors (k-NN)** An instance-based algorithm that classifies a new point based on the majority class among its 'k' nearest neighbors [0].

The distance between points is often calculated using Euclidean distance:

$$d(x, y) = \sqrt{\sum_{i=1}^{n} (x_i - y_i)^2}$$

Where $d(x, y)$ is the distance between points $x$ and $y$, and $n$ is the number of dimensions.

### 2.5.3 Deep Learning

Deep learning offers a powerful set of tools for automatically generating embeddings from the graph representation of heap dumps. Leveraging neural networks, we can build custom models using PyTorch to perform binary classification tasks, such as predicting key nodes in a heap dump. In this section, we will explore various neural network architectures that are well-suited for this task.
Decision Trees use metrics like Gini impurity or entropy to make splits:

$$Gini(T) = 1 - \sum_{i=1}^{C} p_{i}^{2}$$

Where T is a node and $p_i$ is the proportion of class i instances among the training instances in node T.

**Random Forest** An ensemble technique that aggregates predictions from multiple decision trees. Known for its robustness and ability to handle large, high-dimensional data [0].

The final prediction is an average or majority vote from all trees:

$$\hat{y} = \frac{1}{n} \sum_{i=1}^{n} \hat{y}_{i}$$

Where $\hat{y}$ is the final prediction and $\hat{y}_i$ is the prediction from the $i^{th}$ tree.

**Support Vector Machines (SVM)** Effective for both classification and regression, SVMs find the hyperplane that best separates the data into classes. They excel in high-dimensional spaces [0].

The objective is to maximize the margin between classes:

$$\max_{w,b} \frac{2}{\|w\|}$$

Where $w$ is the weight vector and $b$ is the bias term.

**k-Nearest Neighbors (k-NN)** An instance-based algorithm that classifies a new point based on the majority class among its 'k' nearest neighbors [0].

The distance between points is often calculated using Euclidean distance:

$$d(x, y) = \sqrt{\sum_{i=1}^{n} (x_i - y_i)^2}$$

Where $d(x, y)$ is the distance between points $x$ and $y$, and $n$ is the number of dimensions.

### 2.5.3 Deep Learning

Deep learning offers a powerful set of tools for automatically generating embeddings from the graph representation of heap dumps. Leveraging neural networks, we can build custom models using PyTorch to perform binary classification tasks, such as predicting key nodes in a heap dump. In this section, we will explore various neural network architectures that are well-suited for this task.
Neural Networks serve as the backbone of deep learning models [0]. They consist of inter-
connected nodes or "neurons" organized into layers. Deep learning extends this architecture by
employing multiple hidden layers, enabling the model to learn complex representations from data.
This is particularly useful when dealing with graph-based heap dump representations, where the
relationships between nodes can be intricate [0].

Choosing Deep Learning models is dependent on the task. As such, we need to present the
different types of neural networks and their advantages and disadvantages. Below are some
common neural network architectures:

2.5.3.1 Recurrent Neural Networks (RNN)

Recurrent Neural Networks (RNN) are particularly effective for sequence-based data. In the context of heap dumps, if the memory addresses or keys exhibit some form of sequential pattern, RNNs can be employed to capture these temporal dependencies for binary classification [0, p. 10.2].

• Advantages:

- Good at capturing short-term dependencies in sequence data.

- Relatively simpler architecture.

• Disadvantages:

- Struggles with long-term dependencies due to the vanishing gradient problem.

- May require more data for effective training.

2.5.3.2 Long Short-Term Memory (LSTM)

LSTMs are an extension of RNNs designed to capture long-term dependencies, making them suitable for more complex sequences [0].

• Advantages:

- Effective in capturing long-term dependencies.

- Less susceptible to the vanishing gradient problem.

• Disadvantages:

- More complex and computationally intensive than RNNs.

- May require fine-tuning of hyperparameters.

2.5.3.3 Gated Recurrent Units (GRU)

Gated Recurrent Units (GRU) offer a compromise between the simplicity of RNNs and the power of LSTMs. They are effective in capturing both short-term and long-term dependencies but with a less complex architecture [0].
Neural Networks serve as the backbone of deep learning models [0]. They consist of inter-connected nodes or "neurons" organized into layers. Deep learning extends this architecture by employing multiple hidden layers, enabling the model to learn complex representations from data. This is particularly useful when dealing with graph-based heap dump representations, where the relationships between nodes can be intricate [0].

Choosing Deep Learning models is dependent on the task. As such, we need to present the different types of neural networks and their advantages and disadvantages. Below are some common neural network architectures:

### 2.5.3.1 Recurrent Neural Networks (RNN)

Recurrent Neural Networks (RNN) are particularly effective for sequence-based data. In the context of heap dumps, if the memory addresses or keys exhibit some form of sequential pattern, RNNs can be employed to capture these temporal dependencies for binary classification [0, p. 10.2].

* **Advantages:**

- Good at capturing short-term dependencies in sequence data.

- Relatively simpler architecture.

* **Disadvantages:**

- Struggles with long-term dependencies due to the vanishing gradient problem.

- May require more data for effective training.

### 2.5.3.2 Long Short-Term Memory (LSTM)

LSTMs are an extension of RNNs designed to capture long-term dependencies, making them suitable for more complex sequences [0].

* **Advantages:**

- Effective in capturing long-term dependencies.

- Less susceptible to the vanishing gradient problem.

* **Disadvantages:**

- More complex and computationally intensive than RNNs.

- May require fine-tuning of hyperparameters.

### 2.5.3.3 Gated Recurrent Units (GRU)

Gated Recurrent Units (GRU) offer a compromise between the simplicity of RNNs and the power of LSTMs. They are effective in capturing both short-term and long-term dependencies but with a less complex architecture [0].
* **Advantages:**

- Simpler architecture compared to LSTM.

- Efficient in capturing long-term dependencies.

* **Disadvantages:**

- May not perform as well as LSTMs for very complex sequences.

- Still more computationally intensive than basic RNNs.

### 2.5.3.4 Convolutional Neural Networks (CNN)

Though traditionally used in image processing, CNNs can also be adapted for sequence data like heap dumps. They are excellent at identifying spatial hierarchies or patterns in the data [0] [0].

* **Advantages:**

- Highly effective in identifying local patterns.

- Less prone to overfitting due to pooling layers.

* **Disadvantages:**

- May not capture global dependencies as effectively as RNNs or LSTMs.

- Requires a fixed-size input.

### 2.5.3.5 Graph Convolutional Networks (GCN)

Graph Convolutional Networks (GCNs) are a specialized form of neural networks designed to work directly with graphs [0]. They are particularly useful for our task as they can automatically generate embeddings from the graph representation of heap dumps. These embeddings can then be used for binary classification to predict key nodes.

* **Advantages:**

- Capable of capturing both local and global graph structures.

- No need for manual feature extraction from graphs.

* **Disadvantages:**

- May require fine-tuning and a well-defined graph structure.

- Computationally intensive for large graphs.

Several Python libraries can be used to implement GCNs for our specific task. Some notable ones are PyTorch Geometric, Spektral, and DGL (Deep Graph Library). These libraries offer pre-built GCN layers and various utilities to facilitate the embedding and binary classification of heap dump graphs.
* **Advantages:**

- Simpler architecture compared to LSTM.

- Efficient in capturing long-term dependencies.

* **Disadvantages:**

- May not perform as well as LSTMs for very complex sequences.

- Still more computationally intensive than basic RNNs.

### 2.5.3.4 Convolutional Neural Networks (CNN)

Though traditionally used in image processing, CNNs can also be adapted for sequence data like heap dumps. They are excellent at identifying spatial hierarchies or patterns in the data [0] [0].

* **Advantages:**

- Highly effective in identifying local patterns.

- Less prone to overfitting due to pooling layers.

* **Disadvantages:**

- May not capture global dependencies as effectively as RNNs or LSTMs.

- Requires a fixed-size input.

### 2.5.3.5 Graph Convolutional Networks (GCN)

Graph Convolutional Networks (GCNs) are a specialized form of neural networks designed to work directly with graphs [0]. They are particularly useful for our task as they can automatically generate embeddings from the graph representation of heap dumps. These embeddings can then be used for binary classification to predict key nodes.

* **Advantages:**

- Capable of capturing both local and global graph structures.

- No need for manual feature extraction from graphs.

* **Disadvantages:**

- May require fine-tuning and a well-defined graph structure.

- Computationally intensive for large graphs.

Several Python libraries can be used to implement GCNs for our specific task. Some notable ones are PyTorch Geometric, Spektral, and DGL (Deep Graph Library). These libraries offer pre-built GCN layers and various utilities to facilitate the embedding and binary classification of heap dump graphs.
### 2.5.4 Graph Neural Networks

A Graph Neural Network (GNN) constructs a neural network that mirrors the structure of the underlying data graph. In this architecture, nodes are linked according to their relationships in the data graph. The model is trained in a supervised fashion to map input features of nodes to their corresponding output features [0]. These output features can either be manually annotated or sourced from a knowledge graph.

Unlike traditional knowledge graph embeddings, GNNs offer the advantage of end-to-end supervised learning tailored for specific tasks.

With a dataset of labeled examples, GNNs can classify individual nodes or even entire graphs. The challenge lies both in how to convert a given graph to a format that can be fed into a neural network (see 2.4.2.2) and how to design a neural network that can effectively learn from the graph data. Note that the distinction between the two is not always clear since two problems are often tackled together. As such, the present classification is not exhaustive and arbitrary, even though it is based on the literature and meta-analysis of the field, like „Knowledge Graphs (Extended)” [0] and „A comprehensive survey on graph neural networks” [0].

GNNs have been employed in various applications, ranging from traffic prediction, recommender systems, and software verification [0]. Remarkably, GNNs can also serve as substitutes for conventional graph algorithms. For instance, they have been used to identify central nodes in knowledge graphs through supervised learning [0]. The following sections delve into two specific types of GNNs: Recursive GNNs and Convolutional GNNs.

#### 2.5.4.1 Recursive Graph Neural Networks (RecGNNs)

Recursive Graph Neural Networks (RecGNNs) serve as the foundational approach to graph neural networks [0]. The model operates by passing messages between neighboring nodes to recursively compute results. The framework learns the functions that generate the expected output based on a training set of labeled nodes. Scarselli et al. [0] proposed a seminal GNN model that uses feature vectors for nodes and edges, along with state vectors for nodes. Two parametric functions, the transition function and the output function, are used to update the state vectors and compute the final output for nodes, respectively. These functions are applied recursively until a fixpoint is reached. The model is highly flexible and can be adapted in various ways, such as defining neighboring nodes differently or using distinct parameters for each node [0].

**Learning Process in GNNs** The learning process in GNNs can be divided into three steps: input computation, node state update, and output computation. These steps are repeated until a fixpoint is reached, and the final output is computed for each node. Essentially, this involves finding the optimal parameters $\boldsymbol{w}$ such as for $\varphi_w$ to best approximate the data in the learning dataset $\mathcal{L}$.
### 2.5.4 Graph Neural Networks

A Graph Neural Network (GNN) constructs a neural network that mirrors the structure of the underlying data graph. In this architecture, nodes are linked according to their relationships in the data graph. The model is trained in a supervised fashion to map input features of nodes to their corresponding output features [0]. These output features can either be manually annotated or sourced from a knowledge graph.

Unlike traditional knowledge graph embeddings, GNNs offer the advantage of end-to-end supervised learning tailored for specific tasks.

With a dataset of labeled examples, GNNs can classify individual nodes or even entire graphs. The challenge lies both in how to convert a given graph to a format that can be fed into a neural network (see 2.4.2.2) and how to design a neural network that can effectively learn from the graph data. Note that the distinction between the two is not always clear since two problems are often tackled together. As such, the present classification is not exhaustive and arbitrary, even though it is based on the literature and meta-analysis of the field, like „Knowledge Graphs (Extended)” [0] and „A comprehensive survey on graph neural networks” [0].

GNNs have been employed in various applications, ranging from traffic prediction, recommender systems, and software verification [0]. Remarkably, GNNs can also serve as substitutes for conventional graph algorithms. For instance, they have been used to identify central nodes in knowledge graphs through supervised learning [0]. The following sections delve into two specific types of GNNs: Recursive GNNs and Convolutional GNNs.

#### 2.5.4.1 Recursive Graph Neural Networks (RecGNNs)

Recursive Graph Neural Networks (RecGNNs) serve as the foundational approach to graph neural networks [0]. The model operates by passing messages between neighboring nodes to recursively compute results. The framework learns the functions that generate the expected output based on a training set of labeled nodes. Scarselli et al. [0] proposed a seminal GNN model that uses feature vectors for nodes and edges, along with state vectors for nodes. Two parametric functions, the transition function and the output function, are used to update the state vectors and compute the final output for nodes, respectively. These functions are applied recursively until a fixpoint is reached. The model is highly flexible and can be adapted in various ways, such as defining neighboring nodes differently or using distinct parameters for each node [0].

**Learning Process in GNNs** The learning process in GNNs can be divided into three steps: input computation, node state update, and output computation. These steps are repeated until a fixpoint is reached, and the final output is computed for each node. Essentially, this involves finding the optimal parameters $\boldsymbol{w}$ such as for $\varphi_w$ to best approximate the data in the learning dataset $\mathcal{L}$.
The learning task can be formulated as the minimization of a quadratic cost function $e_w$ through iterative gradient descent [0]:

$$e_w = \sum_{i=1}^{p} \sum_{j=1}^{q_i} (t_{i,j} - \varphi_w(G_i, n_{i,j}))^2$$

Where:

* $\mathcal{G}$: The set of graphs.

* $\mathcal{N}$: The subset of nodes.

* $\mathcal{D} = \mathcal{G} \times \mathcal{N}$: The set of pairs of a graph and nodes.

* $G_i = (N_i, E_i) \in \mathcal{G}$: The graph.

* $N_i$: The set of nodes in graph $G_i$.

* $E_i$: The set of edges in graph $G_i$.

* $n_{i,j} \in N_i$: The $j^{th}$ node of the graph $G_i$.

* $q_i \le |N_i|$; The number of supervised nodes in the graph $G_i$.

* $p \le |\mathcal{G}|$: The number of graphs in the learning set.

* $\mathcal{L} = \{(G_i, n_{i,j}, t_{i,j})\}$: The learning set.

* $t_{i,j} \in \mathbb{R}^m$: The target output for node $n_{i,j}$.

* $m$: The number of outputs.

* $\mathbb{R}^m$: The $m$-dimensional Euclidean space.

* $\varphi_w : \mathcal{D} \to \mathbb{R}^m$: The function that maps the input to the output.

* $e_w$: Error function.

For graph-focused tasks, a special node is used for the target ($t$), whereas for node-focused tasks, supervision can be performed on every node. More information about the learning process can be found in [0].

### 2.5.4.2 Convolutional Graph Neural Networks (ConvGNNs)

As introduced before, Graph Convolutional Networks extend the concept of convolution from images to graphs. «The core idea in the image setting is to apply small kernels (aka filters) over localized regions of an image using a convolution operator to extract features from that local region.» [0]. They are designed to work with non-Euclidean data and are particularly useful for semi-supervised learning tasks on graphs. GCNs aim to learn a function that maps nodes to a low-dimensional space while considering their local neighborhood and features.
The learning task can be formulated as the minimization of a quadratic cost function $e_w$ through iterative gradient descent [0]:

$$e_w = \sum_{i=1}^{p} \sum_{j=1}^{q_i} (t_{i,j} - \varphi_w(G_i, n_{i,j}))^2$$

Where:

* $\mathcal{G}$: The set of graphs.

* $\mathcal{N}$: The subset of nodes.

* $\mathcal{D} = \mathcal{G} \times \mathcal{N}$: The set of pairs of a graph and nodes.

* $G_i = (N_i, E_i) \in \mathcal{G}$: The graph.

* $N_i$: The set of nodes in graph $G_i$.

* $E_i$: The set of edges in graph $G_i$.

* $n_{i,j} \in N_i$: The $j^{th}$ node of the graph $G_i$.

* $q_i \le |N_i|$; The number of supervised nodes in the graph $G_i$.

* $p \le |\mathcal{G}|$: The number of graphs in the learning set.

* $\mathcal{L} = \{(G_i, n_{i,j}, t_{i,j})\}$: The learning set.

* $t_{i,j} \in \mathbb{R}^m$: The target output for node $n_{i,j}$.

* $m$: The number of outputs.

* $\mathbb{R}^m$: The $m$-dimensional Euclidean space.

* $\varphi_w: \mathcal{D} \to \mathbb{R}^m$: The function that maps the input to the output.

* $e_w$: Error function.

For graph-focused tasks, a special node is used for the target ($t$), whereas for node-focused tasks, supervision can be performed on every node. More information about the learning process can be found in [0].

### 2.5.4.2 Convolutional Graph Neural Networks (ConvGNNs)

As introduced before, Graph Convolutional Networks extend the concept of convolution from images to graphs. «The core idea in the image setting is to apply small kernels (aka filters) over localized regions of an image using a convolution operator to extract features from that local region.» [0]. They are designed to work with non-Euclidean data and are particularly useful for semi-supervised learning tasks on graphs. GCNs aim to learn a function that maps nodes to a low-dimensional space while considering their local neighborhood and features.
**Convolution filters** A Convolutional Neural Network (CNN) is a type of neural network that uses convolutional filters to extract features from images. These filters are applied to local regions of the image to capture spatial patterns [0]. The same concept can be extended to graphs, where the convolution filters are applied to local regions of the graph to capture structural patterns.

The convolution operation on an image is historically defined as follows [0] [0]:

$$y_{i,j} = \sum_{k=-m}^{m} \sum_{l=-n}^{n} x_{i+k,j+l} \times w_{kl}$$

Where:

* $y_{i,j}$: The output value at the coordinate $(i, j)$ of the convolution output.

* $x_{i,j}$: The input value at the coordinate $(i, j)$ of the input image.

* $w_{kl}$: The weight value (coefficient) of the kernel at the coordinate $(k, l)$.

* $m$: The kernel width.

* $n$: The kernel height.

Similar to this, ConvGNNs implement the transition function using convolutions. One of the challenges in ConvGNNs is defining regions of a graph, as nodes in a graph may have varying numbers of neighbors. Solutions to this problem involve using spectral or spatial representations of graphs [0] [0]. An alternative approach employs attention mechanisms to learn the most important features [0]. Unlike RecGNNs, ConvGNNs apply a fixed number of convolutional layers and can use different kernels/weights at each distinct step.

Here are some common ConvGNN architectures. I recommend reading „Beyond low-pass filtering: Graph convolutional networks with automatic filtering“ [0] for a more in-depth discussion of these models:

* **Vanilla GCN**: The basic GCN model consists of an input layer, one or more hidden layers, and an output layer. Each layer is associated with a graph convolution operation that updates the node features based on their neighbors [0].

* **GraphSAGE (Graph Sample and Aggregation)**: This model generalizes the GCN framework by allowing various aggregation functions like mean, LSTM, and pooling to combine information from a node's neighbors [0].

* **ChebNet**: ChebNet uses Chebyshev polynomials to generalize the convolution operation in the spectral domain. This allows the model to capture a broader range of graph structures [0].

* **GAT (Graph Attention Networks)**: GAT introduces attention mechanisms into GCNs, enabling the model to weigh neighbors differently when aggregating information [0].

* **MoNet**: This model employs a mixture model to generalize the convolution operation, making it capable of handling graphs with diverse structures [0].
**Convolution filters** A Convolutional Neural Network (CNN) is a type of neural network that uses convolutional filters to extract features from images. These filters are applied to local regions of the image to capture spatial patterns [0]. The same concept can be extended to graphs, where the convolution filters are applied to local regions of the graph to capture structural patterns.

The convolution operation on an image is historically defined as follows [0] [0]:

$$y_{i,j} = \sum_{k=-m}^{m} \sum_{l=-n}^{n} x_{i+k,j+l} \times w_{kl}$$

Where:

* $y_{i,j}$: The output value at the coordinate $(i, j)$ of the convolution output.

* $x_{i,j}$: The input value at the coordinate $(i, j)$ of the input image.

* $w_{kl}$: The weight value (coefficient) of the kernel at the coordinate $(k, l)$.

* $m$: The kernel width.

* $n$: The kernel height.

Similar to this, ConvGNNs implement the transition function using convolutions. One of the challenges in ConvGNNs is defining regions of a graph, as nodes in a graph may have varying numbers of neighbors. Solutions to this problem involve using spectral or spatial representations of graphs [0] [0]. An alternative approach employs attention mechanisms to learn the most important features [0]. Unlike RecGNNs, ConvGNNs apply a fixed number of convolutional layers and can use different kernels/weights at each distinct step.

Here are some common ConvGNN architectures. I recommend reading „Beyond low-pass filtering: Graph convolutional networks with automatic filtering” [0] for a more in-depth discussion of these models:

* **Vanilla GCN**: The basic GCN model consists of an input layer, one or more hidden layers, and an output layer. Each layer is associated with a graph convolution operation that updates the node features based on their neighbors [0].

* **GraphSAGE (Graph Sample and Aggregation)**: This model generalizes the GCN framework by allowing various aggregation functions like mean, LSTM, and pooling to combine information from a node's neighbors [0].

* **ChebNet**: ChebNet uses Chebyshev polynomials to generalize the convolution operation in the spectral domain. This allows the model to capture a broader range of graph structures [0].

* **GAT (Graph Attention Networks)**: GAT introduces attention mechanisms into GCNs, enabling the model to weigh neighbors differently when aggregating information [0].

* **MoNet**: This model employs a mixture model to generalize the convolution operation, making it capable of handling graphs with diverse structures [0].
* **Graph Isomorphism Network (GIN):** GIN is designed to capture the isomorphism between different graphs, making it powerful for tasks like graph classification [0].

* Research on the topic is still ongoing, and a lot of new architectures are being proposed: Cluster-GCN, TAGCN, AutoGCN, and many more [0]. It's worth noting that many of these models are not mutually exclusive and can be combined to create more powerful models.

The background chapter has introduced a lot of concepts and techniques that are relevant to our work. We have discussed the importance of data preprocessing and feature engineering, explored various machine learning algorithms, and looked at some common neural network architectures. Although not exhaustive, this overview should provide a solid foundation for the methods, design and implementation that will be discussed in the next chapters.
* **Graph Isomorphism Network (GIN):** GIN is designed to capture the isomorphism between different graphs, making it powerful for tasks like graph classification [0].

* Research on the topic is still ongoing, and a lot of new architectures are being proposed: Cluster-GCN, TAGCN, AutoGCN, and many more [0]. It's worth noting that many of these models are not mutually exclusive and can be combined to create more powerful models.

The background chapter has introduced a lot of concepts and techniques that are relevant to our work. We have discussed the importance of data preprocessing and feature engineering, explored various machine learning algorithms, and looked at some common neural network architectures. Although not exhaustive, this overview should provide a solid foundation for the methods, design and implementation that will be discussed in the next chapters.
# 3 Methods

In the preceding chapters, all the necessary background knowledge to understand the methods have been introduced. In this chapter, we will present an overview of the challenges, the methods, and the tools we have developed for this thesis. We will first describe the dataset we have used. Then, we will describe the programs developed for this thesis. Finally, we will describe how we have packaged and deployed our programs with Nix.

## 3.1 Hardware and software architecture

Throughout this thesis, we have used a variety of hardware and software architectures.

### 3.1.1 Hardware development and testing environment

In this section, as a reference for the reader, we will describe shortly the hardware development environment. All environments are running some Linux x86_64 distribution.

At the start of the project, around the end of 2022, the project started on an old laptop HP EliteBook Folio 1040 G2, running Ubuntu 22.04 LTS (Jammy Jellyfish) with the following specifications:

* **CPU:** 5th Generation Intel Core i7-5600U 2.6 GHz (max turbo frequency 3.2-GHz), 4 MB L3 Cache, 15W

* **GPU:** Intel HD Graphics 5500

* **RAM:** 8GB DDR3L SDRAM (1600 MHz, 1.3v)

This device was used for the first experiments, and for the development of the first programs. However, it was not powerful enough to run the experiments on the whole dataset, and especially working on ML part. As such, we have moved to a more powerful machine, a TUXEDO InfinityBook Pro 16 - Gen7 with the following specifications:

* **CPU:** 12th Gen Intel i7-12700H (20) @ 4.600GHz

* **GPU:** NVIDIA Geforce RTX 3070 Ti Laptop GPU

* **RAM:** 64GB DDR5 4800MHz Samsung

For the Operating System, we have switched from Fedora 37 to NixOS 23 (Tapir). This change was motivated by the fact that NixOS is a Linux distribution that uses a purely functional package management system [0]. This means that the operating system is built by the Nix package manager, using a declarative configuration language. It allows to have a reproducible development environment, and to easily switch between different development environments. This has proved to be very useful in many areas like work environment isolation, on work collaboration with Clément Lahoche, and for software deployment to the server.
# 3 Methods

In the preceding chapters, all the necessary background knowledge to understand the methods have been introduced. In this chapter, we will present an overview of the challenges, the methods, and the tools we have developed for this thesis. We will first describe the dataset we have used. Then, we will describe the programs developed for this thesis. Finally, we will describe how we have packaged and deployed our programs with Nix.

## 3.1 Hardware and software architecture

Throughout this thesis, we have used a variety of hardware and software architectures.

### 3.1.1 Hardware development and testing environment

In this section, as a reference for the reader, we will describe shortly the hardware development environment. All environments are running some Linux x86_64 distribution.

At the start of the project, around the end of 2022, the project started on an old laptop HP EliteBook Folio 1040 G2, running Ubuntu 22.04 LTS (Jammy Jellyfish) with the following specifications:

* **CPU:** 5th Generation Intel Core i7-5600U 2.6 GHz (max turbo frequency 3.2-GHz), 4 MB L3 Cache, 15W

* **GPU:** Intel HD Graphics 5500

* **RAM:** 8GB DDR3L SDRAM (1600 MHz, 1.3v)

This device was used for the first experiments, and for the development of the first programs. However, it was not powerful enough to run the experiments on the whole dataset, and especially working on ML part. As such, we have moved to a more powerful machine, a TUXEDO InfinityBook Pro 16 - Gen7 with the following specifications:

* **CPU:** 12th Gen Intel i7-12700H (20) @ 4.600GHz

* **GPU:** NVIDIA Geforce RTX 3070 Ti Laptop GPU

* **RAM:** 64GB DDR5 4800MHz Samsung

For the Operating System, we have switched from Fedora 37 to NixOS 23 (Tapir). This change was motivated by the fact that NixOS is a Linux distribution that uses a purely functional package management system [0]. This means that the operating system is built by the Nix package manager, using a declarative configuration language. It allows to have a reproducible development environment, and to easily switch between different development environments. This has proved to be very useful in many areas like work environment isolation, on work collaboration with Clément Lahoche, and for software deployment to the server.
Unfortunately, the *TUXEDO InfinityBook Pro 16 - Gen7* laptop was not powerful enough to run the experiments on the whole dataset. Running the python script would have taken more than a week for some simple ML experiments to run on the whole dataset. Small bash and python scripts have been run on this laptop, as well as tests of the different developed programs, but all the main experiments have been run on the server.

In that context, we were provided 2 development servers towards the end of the thesis, around August 2023. The hardware server is a AS-4124GS-TNR with the following specifications:

* CPU: 2x AMD EPYC 7662 (256) @ 2.000GHz

* GPU: NVIDIA Geforce RTX 3090 Ti

* RAM: 512GB DDR4 3200MHz

On this server, we have been given access to two docker instances running Ubuntu 20.04.6 LTS. The first instance is called **Deathstar** and the second one is called **Drogon**. For this Masterarbeit, I have mostly relied on Drogon for the final experiments, although Deathstar has been used for some preliminary experiments.

This server has been provided by the Department of Computer Science of Universität Passau, and especially the Chair of Data Science of Prof. Dr. Michael Granitzer. We would like to thank them for their support.

### 3.1.2 Software, languages and tools

In Computer Sciences, it doesn't take long to realize that testing hypotheses, diving deeper in problems and finding solutions to them is a very iterative process that requires a lot of experimentation. As such, the development of scripts and programs has been a substantial part of this thesis, from the very beginning to the very end. In this process, we have used a variety of tools and programming languages, such as Rust, Python, Bash, or Nix just to name the programming language used.

In this section, as a reference for the reader, we will describe the software architectures, languages and tools that have been used throughout this thesis.

Throughout the project, we have come to use a range of programming languages. Initial tests have been done using shell and bash command and simple scripts. However, as the project grew, we quickly moved to more powerful programming languages.

Python version 3.11 has been the main language for high level data science and ML development. This new version of python features many improvements over the previous version, and especially in terms of performance. Better error messages, exception groups, improved support for f-strings, support for TOML configuration files, variadic generics, improved support for asyncio, and new modules for working with cryptography and machine learning are just some new features of this new version of python. While relatively new, this is why we have decided to use this version of python for the development of the ML part of the project.

Although Python is a popular and powerful language, it is not the most efficient language. As such, we have used Rust for some parts of the project, especially when no high level library is needed and when performances are critical to be able to parse efficiently the dataset. Rust is
Unfortunately, the *TUXEDO InfinityBook Pro 16 - Gen7* laptop was not powerful enough to run the experiments on the whole dataset. Running the python script would have taken more than a week for some simple ML experiments to run on the whole dataset. Small bash and python scripts have been run on this laptop, as well as tests of the different developed programs, but all the main experiments have been run on the server.

In that context, we were provided 2 development servers towards the end of the thesis, around August 2023. The hardware server is a AS-4124GS-TNR with the following specifications:

* CPU: 2x AMD EPYC 7662 (256) @ 2.000GHz

* GPU: NVIDIA Geforce RTX 3090 Ti

* RAM: 512GB DDR4 3200MHz

On this server, we have been given access to two docker instances running Ubuntu 20.04.6 LTS. The first instance is called **Deathstar** and the second one is called **Drogon**. For this Masterarbeit, I have mostly relied on Drogon for the final experiments, although Deathstar has been used for some preliminary experiments.

This server has been provided by the Department of Computer Science of Universität Passau, and especially the Chair of Data Science of Prof. Dr. Michael Granitzer. We would like to thank them for their support.

### 3.1.2 Software, languages and tools

In Computer Sciences, it doesn't take long to realize that testing hypotheses, diving deeper in problems and finding solutions to them is a very iterative process that requires a lot of experimentation. As such, the development of scripts and programs has been a substantial part of this thesis, from the very beginning to the very end. In this process, we have used a variety of tools and programming languages, such as Rust, Python, Bash, or Nix just to name the programming language used.

In this section, as a reference for the reader, we will describe the software architectures, languages and tools that have been used throughout this thesis.

Throughout the project, we have come to use a range of programming languages. Initial tests have been done using shell and bash command and simple scripts. However, as the project grew, we quickly moved to more powerful programming languages.

Python version 3.11 has been the main language for high level data science and ML development. This new version of python features many improvements over the previous version, and especially in terms of performance. Better error messages, exception groups, improved support for f-strings, support for TOML configuration files, variadic generics, improved support for asyncio, and new modules for working with cryptography and machine learning are just some new features of this new version of python. While relatively new, this is why we have decided to use this version of python for the development of the ML part of the project.

Although Python is a popular and powerful language, it is not the most efficient language. As such, we have used Rust for some parts of the project, especially when no high level library is needed and when performances are critical to be able to parse efficiently the dataset. Rust is
a systems programming language that runs blazingly fast, prevents segfaults, and guarantees thread safety. It is a very powerful language, and is especially useful for low-level programming. We have used it for the development of the algorithms that are used to extract the data from the dataset.

### 3.1.2.1 Packaging and deployment

We made an extensive use of git repositories for version control, with GitHub as a main platform for hosting the repositories. An ever-growing number of script and programs have been developed for this thesis. As such, we have needed a way to easily deploy those programs on different machines.

Rust comes with a handful of tools for managing packages and dependencies. Cargo is Rust's build system and package manager. Cargo downloads your Rust project's dependencies, compiles your project, makes executables, and runs the tests. It is a powerful tool that allows to easily manage Rust projects. However, it is not the best tool for deploying programs on different machines.

On Python's side of things, things are a bit more complicated. For a long time, we have relied on virtual environments using the conda package manager. However, it is heavy to use, and it doesn't allow to easily export an environment from one Linux distribution to the other.

An example is the library pygraphviz. This library relies on third parties system libraries, that have different names depending on the Linux distribution:

* Ubuntu: sudo apt-get install graphviz graphviz-dev is needed before a correct install of the Python pygraphviz library.

* Fedora: sudo dnf install graphviz graphviz-devel is needed before installing pygraphviz

Although it can be seen as a minor issue, this is just one example among dozens of libraries. This is a real problem with conda. This is why we have decided to use Nix for managing python packages and dependencies. Nix is a purely functional package manager [0]. It allows to easily manage packages and dependencies, and to easily deploy programs on different machines as it guarantees reproducible builds. It is also very useful for development, as it allows to easily create isolated environments for development. This is why we have used Nix for managing the python packages and dependencies. Gradually, Nix has become a superset of other package managers like pip, conda, or cargo.

Any Nix project comes with either a shell.nix or a more modern flake.nix. Those files are used to describe the project, and to list all necessary dependencies. Since we are developing on NixOS, the integration of Nix with the operating system is very good, and can be easily setup.

Nix is however really straightforward to install on any other distribution through the use of a single script available online. It can be installed in as little as one command.
a systems programming language that runs blazingly fast, prevents segfaults, and guarantees thread safety. It is a very powerful language, and is especially useful for low-level programming. We have used it for the development of the algorithms that are used to extract the data from the dataset.

### 3.1.2.1 Packaging and deployment

We made an extensive use of git repositories for version control, with GitHub as a main platform for hosting the repositories. An ever-growing number of script and programs have been developed for this thesis. As such, we have needed a way to easily deploy those programs on different machines.

Rust comes with a handful of tools for managing packages and dependencies. Cargo is Rust's build system and package manager. Cargo downloads your Rust project's dependencies, compiles your project, makes executables, and runs the tests. It is a powerful tool that allows to easily manage Rust projects. However, it is not the best tool for deploying programs on different machines.

On Python's side of things, things are a bit more complicated. For a long time, we have relied on virtual environments using the conda package manager. However, it is heavy to use, and it doesn't allow to easily export an environment from one Linux distribution to the other.

An example is the library pygraphviz. This library relies on third parties system libraries, that have different names depending on the Linux distribution:

* Ubuntu: sudo apt-get install graphviz graphviz-dev is needed before a correct install of the Python pygraphviz library.

* Fedora: sudo dnf install graphviz graphviz-devel is needed before installing pygraphviz

Although it can be seen as a minor issue, this is just one example among dozens of libraries. This is a real problem with conda. This is why we have decided to use Nix for managing python packages and dependencies. Nix is a purely functional package manager [0]. It allows to easily manage packages and dependencies, and to easily deploy programs on different machines as it guarantees reproducible builds. It is also very useful for development, as it allows to easily create isolated environments for development. This is why we have used Nix for managing the python packages and dependencies. Gradually, Nix has become a superset of other package managers like pip, conda, or cargo.

Any Nix project comes with either a shell.nix or a more modern flake.nix. Those files are used to describe the project, and to list all necessary dependencies. Since we are developing on NixOS, the integration of Nix with the operating system is very good, and can be easily setup.

Nix is however really straightforward to install on any other distribution through the use of a single script available online. It can be installed in as little as one command.
Here is an example of content of a RAW memory dump file, displayed using `vim` and `xxd` commands:

<figure><img src="image_3.png" /><figcaption>Listing 3.1: 16 bytes per line visualization of a Hex Dump from `Training/basic/V_7_8_-P1/16/5070-1643978841-heapraw`</figcaption></figure>

The original file contains the raw byte content of the heap dump of a specific version of OpenSSH. It is a binary file, which means that it is not human-readable. However, it can be converted to a human-readable format using the `xxd` command. The first column to the left represents the offset in hexadecimal. The last column represents the actual content of the bytes, in ASCII format. The columns in between represent the content of the bytes in hexadecimal format.

Since hexadecimal is a base-16 number system, each byte is represented by two hexadecimal digits. The ASCII representation of the bytes is displayed on the right, and is only used for reference, as it is not always possible to convert the bytes to ASCII. For instance, the bytes at offset `0x10` are not printable characters, and thus cannot be converted to ASCII. Each line represents 16 bytes, and the offset is incremented by 16 for each line.

For the purpose of this thesis, it will be more interesting to visualize the content of the heap dump as 8 bytes lines. This can be achieved by using the `xxd` command with the `-c` option, as shown in the following example:

The same example as before, a memory dump file, displayed using `vim` and `xxd -c 8` commands:

<figure><img src="image_4.png" /><figcaption>Listing 3.2: 8 bytes per line visualization of a Hex Dump from `Training/basic/V_7_8_P1/16/5070-1643978841-heapraw`</figcaption></figure>

This example shows the exact content of the preceding one.

To this RAW file is associated a JSON file, which contains its annotations.
Here is an example of content of a RAW memory dump file, displayed using `vim` and `xxd` commands:

<figure><img src="image_3.png" /><figcaption>Listing 3.1: 16 bytes per line visualization of a Hex Dump from `Training/basic/V_7_8_-P1/16/5070-1643978841-heapraw`</figcaption></figure>

The original file contains the raw byte content of the heap dump of a specific version of OpenSSH. It is a binary file, which means that it is not human-readable. However, it can be converted to a human-readable format using the `xxd` command. The first column to the left represents the offset in hexadecimal. The last column represents the actual content of the bytes, in ASCII format. The columns in between represent the content of the bytes in hexadecimal format.

Since hexadecimal is a base-16 number system, each byte is represented by two hexadecimal digits. The ASCII representation of the bytes is displayed on the right, and is only used for reference, as it is not always possible to convert the bytes to ASCII. For instance, the bytes at offset `0x10` are not printable characters, and thus cannot be converted to ASCII. Each line represents 16 bytes, and the offset is incremented by 16 for each line.

For the purpose of this thesis, it will be more interesting to visualize the content of the heap dump as 8 bytes lines. This can be achieved by using the `xxd` command with the `-c` option, as shown in the following example:

The same example as before, a memory dump file, displayed using `vim` and `xxd -c 8` commands:

<figure><img src="image_4.png" /><figcaption>Listing 3.2: 8 bytes per line visualization of a Hex Dump from `Training/basic/V_7_8_P1/16/5070-1643978841-heapraw`</figcaption></figure>

This example shows the exact content of the preceding one.

To this RAW file is associated a JSON file, which contains its annotations.
Here is an example of content of a JSON annotation file that comes with the previous RAW file:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

```json
{
  "SSH_PID": "5070",
  "SSH STRUCT_ADDR": "56343a1a4800",
  "session_state_OFFSET": "0",
  "SESSION_STATE_ADDR": "56343a1a8d30",
  "newkeys_OFFSET": "344",
  "NEWKEYS_1_ADDR": "56343a1aaa40",
  "NEWKEYS_2_ADDR": "56343a1aab40",
  "enc_KEY_OFFSET": "0",
  "mac_KEY_OFFSET": "48",
  "name_ENCRYPTION_KEY_OFFSET": "0",
  "ENCRYPTION_KEY_1_NAME_ADDR": "56343a1a9db0",
  "ENCRYPTION_KEY_1_NAME": "aes128-gcm@openssh.com",
  "ENCRYPTION_KEY_2_NAME_ADDR": "56343a1a3fb0",
  "ENCRYPTION_KEY_2_NAME": "aes128-gcm@openssh.com",
  "key_ENCRYPTION_KEY_OFFSET": "32",
  "key_len_ENCRYPTION_KEY_OFFSET": "20",
  "iv_ENCRYPTION_KEY_OFFSET": "40",
  "iv_len_ENCRYPTION_KEY_OFFSET": "24",
  "KEY_A_ADDR": "56343a1a3170",
  "KEY_A_LENGTH": "12",
  "KEY_A_REAL_LENGTH": "12",
  "KEY_A": "feb5fd4ef0759b034d69b858",
  "KEY_B_ADDR": "56343a1a33e0",
  "KEY_B_LENGTH": "12",
  "KEY_B_REAL_LENGTH": "12",
  "KEY_B": "f50b988297fa19709445c4ee",
  "KEY_C_ADDR": "56343a1a1b0",
  "KEY_C_LENGTH": "16",
  "KEY_C_REAL_LENGTH": "16",
  "KEY_C": "f5b53280e944db0fe196668d877cd4c0",
  "KEY_D_ADDR": "56343a1a4010",
  "KEY_D_LENGTH": "16",
  "KEY_D_REAL_LENGTH": "16",
  "KEY_D": "ac4f18a963d9e72c857497b7dc9d088d",
  "KEY_E_ADDR": "56343a1a7d90",
  "KEY_E_LENGTH": "0",
  "KEY_E_REAL_LENGTH": "0",
  "KEY_E": "",
  "KEY_F_ADDR": "56343a1a2f60",
  "KEY_F_LENGTH": "0",
  "KEY_F_REAL_LENGTH": "0",
  "KEY_F": "",
  "HEAP_START": "56343a198000"
}
```

<caption>Listing 3.3: Complete JSON example, from Training/basic/V_7_8_P1/16/5070-1643978841.json</caption>

Those annotation files contain the meta-information about the heap dump, such as the encryption method, virtual memory address of the key, and the key's value in hexadecimal representation. Those annotations are invaluable for the development of machine learning models used for key prediction.

The dataset is not just limited to SSH key extraction; it also serves as a resource for identifying essential data structures that hold sensitive information. This makes it a versatile tool for various research applications.
Here is an example of content of a JSON annotation file that comes with the previous RAW file:

<figure><img src="image_5.png" /><figcaption>Listing 3.3: Complete JSON example, from Training/basic/V_7_8_P1/16/5070-1643978841.json</figcaption></figure>

Those annotation files contain the meta-information about the heap dump, such as the encryption method, virtual memory address of the key, and the key's value in hexadecimal representation. Those annotations are invaluable for the development of machine learning models used for key prediction.

The dataset is not just limited to SSH key extraction; it also serves as a resource for identifying essential data structures that hold sensitive information. This makes it a versatile tool for various research applications.
### 3.2.1 Assumptions

Before we dive in, let's make some assumptions about the dataset. We will use these assumptions to guide our exploration of the heap dump file.

* **Heap dump file size:** We will assume that the heap dump file size is a multiple of 8 bytes. This is because the heap dump file is a memory dump, and memory is allocated in chunks that are multiples of 8 bytes. This means that we can expect the heap dump file to be composed of a sequence of 8 bytes blocks. If this assumption is not met, we will assume that padding the last block with 0s will not change the results of our exploration.

* **Chunk chaining:** We will assume that all the heap dump files have been generated using the same malloc implementation from GlibC. It means that we can expect to find the same patterns in all the heap dump files. Especially, we expect all the heap dump files to start by a first allocated in-use chunk. We can then follow the malloc header chaining to explore the heap dump file allocated memory chunks [0].

* **Dataset key annotation format:** We will assume that the JSON annotation files have been generated using the same program. This means that we can expect the same format for all the JSON annotation files. This is important, as we will use the JSON annotation files to get the key addresses for annotating memory graphs used for the embedding step. If the format is not the same, we will assume that the JSON annotation file is corrupted, and we will skip it.

The **chunk chaining assumption** is absolutely crucial for the exploration of the heap dump file. It allows us to follow the malloc header chaining to explore the heap dump file allocated memory chunks. This assumption is supported by the code where we can find a comment stating that: «since chunks are adjacent to each other in memory, if you know the address of the first chunk (lowest address) in a heap, you can iterate through all the chunks in the heap by using the size information, but only by increasing address, although it may be difficult to detect when you've hit the last chunk in the heap» [0].

In the scripts and programs that have been developed for the following thesis, we have implemented a number of checks and tests to ensure that these assumptions are met. If not, the programs will raise an error, log the problem and generally skip the data. This behavior is implemented to ensure that the programs are robust to unexpected data, and to ensure that the results are reliable. These assumptions and related problems will be discussed and measured at several locations in the following sections.

### 3.2.2 Dataset production system information

Neither the paper „SmartKex: Machine Learning Assisted SSH Keys Extraction From The Heap Dump“ nor the dataset itself provide information about the hardware and software used for its generation. This is important since we will be exploring allocated raw bytes which depend on the system and C library used. We obtained some information about the dataset generation by contacting the authors of the paper.

As specified in a mail from Reiser, Hans, the dataset was generated on a system with the following command output:
### 3.2.1 Assumptions

Before we dive in, let's make some assumptions about the dataset. We will use these assumptions to guide our exploration of the heap dump file.

* **Heap dump file size:** We will assume that the heap dump file size is a multiple of 8 bytes. This is because the heap dump file is a memory dump, and memory is allocated in chunks that are multiples of 8 bytes. This means that we can expect the heap dump file to be composed of a sequence of 8 bytes blocks. If this assumption is not met, we will assume that padding the last block with 0s will not change the results of our exploration.

* **Chunk chaining:** We will assume that all the heap dump files have been generated using the same malloc implementation from GlibC. It means that we can expect to find the same patterns in all the heap dump files. Especially, we expect all the heap dump files to start by a first allocated in-use chunk. We can then follow the malloc header chaining to explore the heap dump file allocated memory chunks [0].

* **Dataset key annotation format:** We will assume that the JSON annotation files have been generated using the same program. This means that we can expect the same format for all the JSON annotation files. This is important, as we will use the JSON annotation files to get the key addresses for annotating memory graphs used for the embedding step. If the format is not the same, we will assume that the JSON annotation file is corrupted, and we will skip it.

The **chunk chaining assumption** is absolutely crucial for the exploration of the heap dump file. It allows us to follow the malloc header chaining to explore the heap dump file allocated memory chunks. This assumption is supported by the code where we can find a comment stating that: «since chunks are adjacent to each other in memory, if you know the address of the first chunk (lowest address) in a heap, you can iterate through all the chunks in the heap by using the size information, but only by increasing address, although it may be difficult to detect when you've hit the last chunk in the heap» [0].

In the scripts and programs that have been developed for the following thesis, we have implemented a number of checks and tests to ensure that these assumptions are met. If not, the programs will raise an error, log the problem and generally skip the data. This behavior is implemented to ensure that the programs are robust to unexpected data, and to ensure that the results are reliable. These assumptions and related problems will be discussed and measured at several locations in the following sections.

### 3.2.2 Dataset production system information

Neither the paper „SmartKex: Machine Learning Assisted SSH Keys Extraction From The Heap Dump“ nor the dataset itself provide information about the hardware and software used for its generation. This is important since we will be exploring allocated raw bytes which depend on the system and C library used. We obtained some information about the dataset generation by contacting the authors of the paper.

As specified in a mail from Reiser, Hans, the dataset was generated on a system with the following command output:
1

root@debian10:~# ldd --version

2

ldd (Debian GLIBC 2.28-10) 2.28

3

Copyright (C) 2018 Free Software Foundation, Inc.

4

This is free software; see the source for copying conditions. There is NO

5

warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

6

Written by Roland McGrath and Ulrich Drepper.

<caption>Listing 3.4: Command and logs of the C-library version used for the dataset generation</caption>

1

root@debian10:~# lsb_release -a

2

No LSB modules are available.

3

Distributor ID: Debian

4

Description: Debian GNU/Linux 10 (buster)

5

Release: 10

6

Codename: buster

<caption>Listing 3.5: Command and logs of the Linux Standard Base Release used for the dataset generation</caption>

1

root@debian10:~# uname -a

2

Linux debian10 4.19.0-16-amd64 #1 SMP Debian 4.19.181-1 (2021-03-19) x86_64 GNU/Linux

<caption>Listing 3.6: Command and logs of the OS and kernel version used for the dataset generation</caption>

He also precise that the CPU used was an Intel Xeon CPU, either a E5-2609 or a E3-1230. From
those commands, we can deduce the following crucial system related information:

* **CPU architecture:** x86_64

* **OS version:** Debian GNU/Linux 10 (buster)

* **Kernel version:** 4.19.0-16-amd64

* **C library version:** Debian GLIBC 2.28-10

### 3.2.3 Conventions and vocabulary

It's important to define some conventions and vocabulary that will be used in the following sections,
since many concepts can be ambiguous depending on the context.

* **memory graph:** A memory graph is our particular case refers to a directed graph that represents the memory of a heap dump file. The memory graph is the main data structure used for the embedding step.

* **block:** In the following, we will refer to a block as a sequence of 8 bytes. This is because the heap dump file is a memory dump, and memory is allocated in chunks that are multiples of 8 bytes. This means that we can expect the heap dump file to be composed of a sequence of 8 bytes blocks.

* **chunk:** A chunk is a sequence of blocks bytes. This concepts directly comes from the malloc implementation. At its core, a chunk has a user data body composed of blocks and a malloc header block. A chunk can be in-use or free.
1

root@debian10:~# ldd --version

2

ldd (Debian GLIBC 2.28-10) 2.28

3

Copyright (C) 2018 Free Software Foundation, Inc.

4

This is free software; see the source for copying conditions. There is NO

5

warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

6

Written by Roland McGrath and Ulrich Drepper.

<caption>Listing 3.4: Command and logs of the C-library version used for the dataset generation</caption>

1

root@debian10:~# lsb_release -a

2

No LSB modules are available.

3

Distributor ID: Debian

4

Description: Debian GNU/Linux 10 (buster)

5

Release: 10

6

Codename: buster

<caption>Listing 3.5: Command and logs of the Linux Standard Base Release used for the dataset generation</caption>

1

root@debian10:~# uname -a

2

Linux debian10 4.19.0-16-amd64 #1 SMP Debian 4.19.181-1 (2021-03-19) x86_64

GNU/Linux

<caption>Listing 3.6: Command and logs of the OS and kernel version used for the dataset generation</caption>

He also precise that the CPU used was an Intel Xeon CPU, either a E5-2609 or a E3-1230. From
those commands, we can deduce the following crucial system related information:

* **CPU architecture:** x86_64

* **OS version:** Debian GNU/Linux 10 (buster)

* **Kernel version:** 4.19.0-16-amd64

* **C library version:** Debian GLIBC 2.28-10

### 3.2.3 Conventions and vocabulary

It's important to define some conventions and vocabulary that will be used in the following sections,
since many concepts can be ambiguous depending on the context.

* **memory graph:** A memory graph is our particular case refers to a directed graph that represents the memory of a heap dump file. The memory graph is the main data structure used for the embedding step.

* **block:** In the following, we will refer to a block as a sequence of 8 bytes. This is because the heap dump file is a memory dump, and memory is allocated in chunks that are multiples of 8 bytes. This means that we can expect the heap dump file to be composed of a sequence of 8 bytes blocks.

* **chunk:** A chunk is a sequence of blocks bytes. This concepts directly comes from the malloc implementation. At its core, a chunk has a user data body composed of blocks and a malloc header block. A chunk can be in-use or free.
### 3.2.4 Estimating the dataset balancing for key prediction

First, let's quickly estimate what the dataset is composed about. This will later be used to estimate the balancing of data for our key prediction goal. Some quick Linux commands can be used to get a general overview of the dataset.

A first command can quickly give us an idea of the number of files in the dataset:

```
find /path/to/dataset -type f | wc -l
```

<caption>Listing 3.7: Count all dataset files</caption>

```
du -sb /path/to/dataset
```

<caption>Listing 3.8: Get the total size of the dataset</caption>

The first command indicates that the dataset contains 208749 files, which represents, according to second one, a total of 18203592048 bytes, or around 18 Gigabytes.

We could just divide the number of files by the size of the dataset to get an average size of the files. However, this would not be accurate, as we are only interested in the size of the RAW files. Since JSON files are much smaller than RAW files, they would skew the average size of the files. Since we are only considering RAW files, we will use improved commands in order to determine the size of the RAW file only.

The following command can be used to get a better understanding of the dataset, concerning the number of RAW files and their size:

```
find /path/to/dataset -type f -name "*.RAW" | wc -l
```

<caption>Listing 3.9: Find the number of RAW files in the dataset</caption>

```
find /path/to/dataset -type f -name "*.raw" -exec du -b {} + \
| awk '{s+=$1} END {print s}'
```

<caption>Listing 3.10: Find the number of bytes of RAW files in the dataset</caption>

Where:

* `find phdtrack_data/ -type f -name "*.raw"` finds all the files in the dataset that have the extension `.raw`.

* `-exec du -b {} + | awk '{s+=$1} END {print s}'` executes the command `du -b` on each file found by the previous command, and sums the size of each file.

These commands indicate that the dataset contains 103595 RAW files, which represents a total of 18067001344 bytes, or around 18 Gigabytes. This shows that the vast majority of the data is contained in RAW files, with JSON files representing less than a percent of the dataset in terms of byte size. As such, the average size for every RAW file is around 170 Kilobytes.

Now, considering that a given heap dump file is expecting to have only 6 keys (see 2.1.1.2), with keys maximal possible size being of 64 bytes, we can estimate that we have at maximum 39780480
### 3.2.4 Estimating the dataset balancing for key prediction

First, let's quickly estimate what the dataset is composed about. This will later be used to estimate the balancing of data for our key prediction goal. Some quick Linux commands can be used to get a general overview of the dataset.

A first command can quickly give us an idea of the number of files in the dataset:

```
find /path/to/dataset -type f | wc -l
```

<caption>Listing 3.7: Count all dataset files</caption>

```
du -sb /path/to/dataset
```

<caption>Listing 3.8: Get the total size of the dataset</caption>

The first command indicates that the dataset contains 208749 files, which represents, according to second one, a total of 18203592048 bytes, or around 18 Gigabytes.

We could just divide the number of files by the size of the dataset to get an average size of the files. However, this would not be accurate, as we are only interested in the size of the RAW files. Since JSON files are much smaller than RAW files, they would skew the average size of the files. Since we are only considering RAW files, we will use improved commands in order to determine the size of the RAW file only.

The following command can be used to get a better understanding of the dataset, concerning the number of RAW files and their size:

```
find /path/to/dataset -type f -name "*.RAW" | wc -l
```

<caption>Listing 3.9: Find the number of RAW files in the dataset</caption>

```
find /path/to/dataset -type f -name "*.raw" -exec du -b {} + \
| awk '{s+=$1} END {print s}'
```

<caption>Listing 3.10: Find the number of bytes of RAW files in the dataset</caption>

Where:

* `find phdtrack_data/ -type f -name "*.raw"` finds all the files in the dataset that have the extension `.raw`.

* `-exec du -b {} + | awk '{s+=$1} END {print s}'` executes the command `du -b` on each file found by the previous command, and sums the size of each file.

These commands indicate that the dataset contains 103595 RAW files, which represents a total of 18067001344 bytes, or around 18 Gigabytes. This shows that the vast majority of the data is contained in RAW files, with JSON files representing less than a percent of the dataset in terms of byte size. As such, the average size for every RAW file is around 170 Kilobytes.

Now, considering that a given heap dump file is expecting to have only 6 keys (see 2.1.1.2), with keys maximal possible size being of 64 bytes, we can estimate that we have at maximum 39780480
or around 40 Megabytes of positively labeled samples. This, considering the total useful size of around 18 Gigabytes, means that our dataset is very imbalanced, with an expected upper-bounded ratio of 0.0022% of positively labeled samples or around 2 : 1000.

Considering that, a frontal ML binary classification approach will not work. This is why the present report will discuss feature engineering and graph-based memory representation. The idea is to embed more information to our keys so as to be able to fight effectively the imbalanceness of the raw data.

3.2.5 Dataset validation

The dataset is merely a collection of heap dump RAW files for different use cases and versions
of OpenSSH. Each heap dump file goes along a JSON annotation file that has been generated by
the creators of the dataset to provide additional information about the heap dump, and especially
encryption keys.

However, it is worth noting that the dataset is not perfect. The use of the dataset for machine
learning has revealed some issues. For instance, some JSON annotation files are not valid JSON
files, and cannot be loaded as such. Some JSON annotation files are also not complete, with some
crucial information missing. This is a problem, as we will use the JSON annotation files to get the
key addresses for annotating memory graphs used for the embedding step. If the format is not the
same, we will assume that the JSON annotation file is corrupted, and we will skip it.

This is probably due to the fact that the annotations were generated automatically. For instance,
in *Training/basic/V_7_8_P1/16*, literally the first file of the dataset contains an incomplete annota-
tion file, as some keys are missing. This is a limitation of the dataset that should be kept in mind
when using it for research purposes.

Here is an example of content of a JSON annotation file with missing keys, and with missing
annotations (like address or length) for the keys that are present:

<figure><img src="image_5.png" /><figcaption>Listing 3.11: Missing keys in JSON annotation file *Training/basic/V_6_0_P1/16/24375-1644243522.json*</figcaption></figure>

3.2.5.1 Automatic annotation validation

So as to determine really how much of the dataset can be used really for machine learned, we
have developed a script that checks the validity of those annotations. This script called check_-
annotations.py, is used to verify the quality, completeness, consistency and coherence of the
annotations.

Files are regrouped under the following categories:
or around 40 Megabytes of positively labeled samples. This, considering the total useful size of around 18 Gigabytes, means that our dataset is very imbalanced, with an expected upper-bounded ratio of 0.0022% of positively labeled samples or around 2 : 1000.

Considering that, a frontal ML binary classification approach will not work. This is why the present report will discuss feature engineering and graph-based memory representation. The idea is to embed more information to our keys so as to be able to fight effectively the imbalanceness of the raw data.

3.2.5 Dataset validation

The dataset is merely a collection of heap dump RAW files for different use cases and versions
of OpenSSH. Each heap dump file goes along a JSON annotation file that has been generated by
the creators of the dataset to provide additional information about the heap dump, and especially
encryption keys.

However, it is worth noting that the dataset is not perfect. The use of the dataset for machine
learning has revealed some issues. For instance, some JSON annotation files are not valid JSON
files, and cannot be loaded as such. Some JSON annotation files are also not complete, with some
crucial information missing. This is a problem, as we will use the JSON annotation files to get the
key addresses for annotating memory graphs used for the embedding step. If the format is not the
same, we will assume that the JSON annotation file is corrupted, and we will skip it.

This is probably due to the fact that the annotations were generated automatically. For instance,
in *Training/basic/V_7_8_P1/16*, literally the first file of the dataset contains an incomplete annota-
tion file, as some keys are missing. This is a limitation of the dataset that should be kept in mind
when using it for research purposes.

Here is an example of content of a JSON annotation file with missing keys, and with missing
annotations (like address or length) for the keys that are present:

<figure><img src="image_6.png" /><figcaption>Listing 3.11: Missing keys in JSON annotation file *Training/basic/V_6_0_P1/16/24375-1644243522.json*</figcaption></figure>

3.2.5.1 Automatic annotation validation

So as to determine really how much of the dataset can be used really for machine learned, we
have developed a script that checks the validity of those annotations. This script called check_-
annotations.py, is used to verify the quality, completeness, consistency and coherence of the
annotations.

Files are regrouped under the following categories:
* **Correct and Complete Files:** Files that have no missing keys, and that have all the keys with correct values.

* **Broken Files:** Files that are not valid JSON files, and cannot be loaded as such.

* **Incorrect Files:** Files that have contradictory information in their annotation file.

* **Missing key Files:** Files that have missing keys in their annotation file. A typical example is a JSON file with `"KEY_E": ""`. This means that the key E is missing, and that the key E address is not present in the annotation file, which is a problem for the machine learning since it means that we cannot label correctly the key E.

* **Incomplete key Files:** Files that have incomplete keys in their annotation file. A typical example is a JSON file with `"KEY_E": "689e549a80ce4be95d8b742e36a229bf"`. This means that the key E is present, but that the key E address is not present in the annotation file, which is a problem for the machine learning since it means that we cannot label correctly the key E.

The script is used to validate each JSON file using the following process:

<caption>**Algorithm 1** Json Annotation Validation</caption>

1: **Procedure** ValidateJson(json_data)
2:     **Initialize** errors = Dictionary{}
3:     ▷ Serve as collection for counted errors
4:     **Initialize** mandatory_json_keys = ['HEAP_START', 'SSH STRUCT ADDR', 'SESSION - STATE_ADDR']
5:     **Initialize** key_names = {}
6:     **for** mandatory_json_key in mandatory_json_keys **do** ▷ Check if some expected json keys are missing
7:         **if** mandatory_json_key not in json_data or not correct hex address then
8:             errors[mandatory_json_key] = False
9:             **else**
10:             errors[mandatory_json_key] = True
11:         **end if**
12:     **end for**
13:     **for** json_key in json_data.keys() **do** ▷ Get all the keys names, like A, B, C, D, E, F
14:         **if** json_key LIKE "KEY_" then
15:             key_name = GetLetterOfSSHKeyFromJSONKeyName(json_key)
16:             key_names.add(key_name)
17:         **end if**
18:     **end for**
19:     **for** key_letter in key_names **do**
20:         base_key = "KEY_" + key_letter
21:         **PerformSSHKeyAnnotationValidationAndCompleteness**(base_key, json_data) that counts incorrect_keys, missing_keys, incomplete_keys
22:     **end for**
23:     Store counters in errors
24:     **return** errors
25: **end Procedure**

The counting error algorithm done on each SSH key annotation by is described in the following:
* **Correct and Complete Files:** Files that have no missing keys, and that have all the keys with correct values.

* **Broken Files:** Files that are not valid JSON files, and cannot be loaded as such.

* **Incorrect Files:** Files that have contradictory information in their annotation file.

* **Missing key Files:** Files that have missing keys in their annotation file. A typical example is a JSON file with `"KEY_E": ""`. This means that the key E is missing, and that the key E address is not present in the annotation file, which is a problem for the machine learning since it means that we cannot label correctly the key E.

* **Incomplete key Files:** Files that have incomplete keys in their annotation file. A typical example is a JSON file with `"KEY_E": "689e549a80ce4be95d8b742e36a229bf"`. This means that the key E is present, but that the key E address is not present in the annotation file, which is a problem for the machine learning since it means that we cannot label correctly the key E.

The script is used to validate each JSON file using the following process:

**Algorithm 1** `Json Annotation Validation`

1: **Procedure** `ValidateJson(json_data)`
2:     **Initialize** `errors = Dictionary{}` ▷ Serve as collection for counted errors
3:     **Initialize** `mandatory_json_keys = ['HEAP_START', 'SSH STRUCT ADDR', 'SESSION - STATE_ADDR']`
4:     **Initialize** `key_names = {}`
5:     **Initialize** `incorrect_keys, missing_keys, incomplete_keys = 0`
6:     **for** `mandatory_json_key` **in** `mandatory_json_keys` **do** ▷ Check if some expected json keys are missing
7:         **if** `mandatory_json_key` **not in** `json_data` **or not** correct hex address **then**
8:             `errors[mandatory_json_key]` = False
9:             **else**
10:             `errors[mandatory_json_key]` = True
11:         **end if**
12:     **end for**
13:     **for** `json_key` **in** `json_data.keys()` **do** ▷ Get all the keys names, like A, B, C, D, E, F
14:         **if** `json_key` ** startwith**("KEY") **then**
15:             `key_name` = GetLetterOfSSHKeyFromJSONKeyName(json_key)
16:             `key_names`.add(`key_name`)
17:         **end if**
18:     **end for**
19:     **for** `key_letter` **in** `key_names` **do**
20:         `base_key` = "KEY" + `key_letter`
21:     **PerformSSHKeyAnnotationValidationAndCompleteness**(`base_key`, `json_data`) that counts incorrect_keys, missing_keys, incomplete_keys
22:     **end for**
23: Store counters in errors
24:     **return** errors
25: **end Procedure**

The counting error algorithm done on each SSH key annotation by is described in the following:
**Algorithm 2** SSH Key Annotation Validation

1: **Procedure** PerformSSHKeyAnnotationValidationAndCompleteness(base_key, json_data)
2:     **Initialize** incorrect_keys, missing_keys, incomplete_keys = 0
3:     **if** length(json_data(base_key)) == 0 **then**
4:         missing_keys += 1
5:     **else**
6:         is_key_len present = exists(json_data(base_key_LENGTH))
7:         is_key_addr present = exists(json_data(base_key_ADDR))
8:         is_key_real_len present = exists(json_data(base_key_REAL_LENGTH))
9:         **if** not is_key_len present or not is_key_addr present or not is_key_real_len present **then**
10:             incomplete_keys += 1
11:         **else**
12:             **if** not is_hex_address_correct(json_data(base_key_ADDR)) **then**
13:                 incorrect_keys += 1
14:             **else**
15:                 **if** json_data(base_key_LENGTH) is not a number or is negative **then**
16:                     incorrect_keys += 1
17:                 **else**
18:                     **else**
19:                         Validate key value length based on annotation length
20:                         **if** json_data(base_key_LENGTH) == 0 **then**
21:                             missing_keys += 1
22:                         **else**
23:                             **if** length(json_data(base_key)) != json_data(base_key_LENGTH) * 2 **then**
24:                                 incorrect_keys += 1
25:                             **else**
26:                                 **end if**
27:                                 **end if**
28:                                 **return** incorrect_keys, missing_keys, incomplete_keys
29: **end Procedure**

Note that I have simplified this algorithm. The is_hex_address correct function requires other manipulations to be called, since it checks that the given value is in the range of the heap dump addresses. To do so, it requires handling potentially missing HEAP_START annotation, hexadecimal conversion with correct endianness, and other manipulations like determining the size of the heap dump. The full code is available in the check_annotations.py file.

The script runs in a few seconds on all the 103595 JSON annotation files, and gives the following results:

* **Number of Correct and Complete Files:** 26196 files

* **Number of Broken Files:** 6 files are broken. A direct look at those files shows that they are empty files.

* **Number of Incorrect Files:** 0 files

* **Number of Missing key Files:** 58643 files have missing keys.

* **Number of Incomplete key Files:** 18750 files have incomplete keys.

We can also directly look at the keys in general:
**Algorithm 2** SSH Key Annotation Validation

1: **Procedure** PerformSSHKeyAnnotationValidationAndCompleteness(base_key, json_data)
2:     **Initialize** incorrect_keys, missing_keys, incomplete_keys = 0
3:     **if** length(json_data[base_key]) == 0 **then**
4:         missing_keys += 1
5:     **else**
6:         is_key_len present = exists(json_data[base_key_LENGTH])
7:         is_key_addr present = exists(json_data[base_key_ADDR])
8:         is_key_real_len present = exists(json_data[base_key_REAL_LENGTH])
9:         **if** not is_key_len present or not is_key_addr present or not is_key_real_len present **then**
10:             incomplete_keys += 1
11:         **else**
12:             **if** not is_hex_address_correct(json_data[base_key_ADDR]) **then**
13:                 incorrect_keys += 1
14:             **else**
15:                 **if** json_data[base_key_LENGTH] is not a number or is negative **then**
16:                     incorrect_keys += 1
17:                 **else**
18:                     **else**
19:                         Validate key value length based on annotation length
20:                         **if** json_data[base_key_LENGTH] == 0 **then**
21:                             missing_keys += 1
22:                         **else**
23:                             **if** length(json_data[base_key]) != json_data[base_key_LENGTH] * 2 **then**
24:                                 incorrect_keys += 1
25:                             **else**
26:                                 **end if**
27:                                 **end if**
28:                                 **return** incorrect_keys, missing_keys, incomplete_keys
29: **end Procedure**

Note that I have simplified this algorithm. The is_hex_address correct function requires other manipulations to be called, since it checks that the given value is in the range of the heap dump addresses. To do so, it requires handling potentially missing HEAP_START annotation, hexadecimal conversion with correct endianness, and other manipulations like determining the size of the heap dump. The full code is available in the check_annotations.py file.

The script runs in a few seconds on all the 103595 JSON annotation files, and give the following results:

* **Number of Correct and Complete Files:** 26196 files

* **Number of Broken Files:** 6 files are broken. A direct look at those files shows that they are empty files.

* **Number of Incorrect Files:** 0 files

* **Number of Missing key Files:** 58643 files have missing keys.

* **Number of Incomplete key Files:** 18750 files have incomplete keys.

We can also directly look at the keys in general:
* Number of SSH keys: 546534 keys

* Number of missing (empty) SSH keys: 157244 keys

* Number of incompletely annotated SSH keys: 37500 keys

* Number of incorrectly annotated SSH keys: 0 keys

### 3.2.6 Dataset cleaning

We need to ensure that the subset of the original dataset that will be used for machine learning is correct and consistent. This means that we need to remove the broken files, and the files that have missing or incomplete keys.

In the new cleaned subset of the dataset, we kept only the files identified as correct and complete. This way, we are left with 26196 RAW files.

From this, we need to remove the raw files that do not respect the **Chunk chaining assumption**
3.2.1. This cleaning process involves the chunk chaining algorithm that will be introduced later.
During this process, out of the 26196 RAW files, 5 of them have been detected to have 0 sized
chunks. Those files have been removed from the cleaned dataset. This leaves us with 26191 RAW
files.

1
2
3
4

```
$ find ~/code/phdtrack/phdtrack_data_clean/ -type f -name "*-heap/raw" | wc -l
26191
$ find ~/code/phdtrack/phdtrack_data_clean/ -type f -name "*.json" | wc -l
26191
```

Listing 3.12: Command and logs of counting the number of RAW files in the cleaned dataset.

In total, this means that only 25.3% of the RAW files with their JSON files are actually usable (correct, complete, with valid chunk chaining), and can be used for machine learning. This is because we don't have access to the packets that have been used to generate the dataset, and thus we cannot regenerate the annotations. Since the machine learning relies entirely on those annotations, we cannot afford to use partially annotated files.

This is a limitation of the dataset that should be kept in mind when using it for research purposes, and especially for supervised machine learning.

### 3.2.7 Exploring patterns in RAW heap dump files

Before diving into programming, we need to gain a better understanding of how to retrieve useful information from heap dump raw file. For that matter, we will continue to experiment with simple commands in RAW heap dump files. Note that in the following, number bases are indicated, since endianness and conversions can get confusing.

Let's start by looking back at the RAW file we already presented in 3.2.

#### 3.2.7.1 Detecting potential pointers

The paper „SmartKex: Machine Learning Assisted SSH Keys Extraction From The Heap Dump“ indicates that the keys are 8-bytes aligned. In fact, this is the case for the whole heap dump file.
* Number of SSH keys: 546534 keys

* Number of missing (empty) SSH keys: 157244 keys

* Number of incompletely annotated SSH keys: 37500 keys

* Number of incorrectly annotated SSH keys: 0 keys

### 3.2.6 Dataset cleaning

We need to ensure that the subset of the original dataset that will be used for machine learning is correct and consistent. This means that we need to remove the broken files, and the files that have missing or incomplete keys.

In the new cleaned subset of the dataset, we kept only the files identified as correct and complete. This way, we are left with 26196 RAW files.

From this, we need to remove the raw files that do not respect the **Chunk chaining assumption**
3.2.1. This cleaning process involves the chunk chaining algorithm that will be introduced later.
During this process, out of the 26196 RAW files, 5 of them have been detected to have 0 sized
chunks. Those files have been removed from the cleaned dataset. This leaves us with 26191 RAW
files.

1
2
3
4

```
$ find ~/code/phdtrack/phdtrack_data_clean/ -type f -name "*-heap/raw" | wc -l
26191
$ find ~/code/phdtrack/phdtrack_data_clean/ -type f -name "*.json" | wc -l
26191
```

Listing 3.12: Command and logs of counting the number of RAW files in the cleaned dataset.

In total, this means that only 25.3% of the RAW files with their JSON files are actually usable (correct, complete, with valid chunk chaining), and can be used for machine learning. This is because we don't have access to the packets that have been used to generate the dataset, and thus we cannot regenerate the annotations. Since the machine learning relies entirely on those annotations, we cannot afford to use partially annotated files.

This is a limitation of the dataset that should be kept in mind when using it for research purposes, and especially for supervised machine learning.

### 3.2.7 Exploring patterns in RAW heap dump files

Before diving into programming, we need to gain a better understanding of how to retrieve useful information from heap dump raw file. For that matter, we will continue to experiment with simple commands in RAW heap dump files. Note that in the following, number bases are indicated, since endianness and conversions can get confusing.

Let's start by looking back at the RAW file we already presented in 3.2.

#### 3.2.7.1 Detecting potential pointers

The paper „SmartKex: Machine Learning Assisted SSH Keys Extraction From The Heap Dump“ indicates that the keys are 8-bytes aligned. In fact, this is the case for the whole heap dump file.
This is why we have chosen to split the study of heap dump files in chunks or blocks of 8 bytes.
The term *block* in code is always referring to this, unless specified otherwise. The precision is
important, since these blocks should not be confused with *memory blocks* like the ones that are
allocated by the `malloc()` function in C.

Let's re-open the heap dump file in vim, and let's use the following vim commands to explore
the example heap dump file:

* `:%xd -c 8 5070-1643978841-heap/raw!`: This vim command converts the opened file to a hex dump. The `-c 8` option indicates that we want to display 8 bytes per line.

* `:set hlsearch`: This vim command highlights the search results.

* `:%s/\s\+//g`: This vim command removes all the whitespaces in the file.

* `:%s/\v([0-9a-f]{8}:/\1\` This vim command adds a whitespace after each 8 byte addresses.

* `:%s/\v([0-9a-f]{8}: )([0-9a-f]{16})/\1\` This vim command adds a whitespace after each heap dump byte line.

To find potential pointers, we can use the following command in vim:

1

:/[0-9a-f]\{12}0\{4}

<caption>Listing 3.13: Vim command to find potential pointers</caption>

This is a search that looks for 12 hexadecimal digits followed by 4 zeros. This is because, the maximum possible addresses in the heap dump file have a size of around 12 hexadecimal digits, and because pointer addresses are in little-endian format, meaning that the last 4 bytes of the address are also the Most Significant Bytes (MSB) of the address.

The result is illustrated below 3.2.7.1:
This is why we have chosen to split the study of heap dump files in chunks or blocks of 8 bytes.
The term *block* in code is always referring to this, unless specified otherwise. The precision is
important, since these blocks should not be confused with *memory blocks* like the ones that are
allocated by the `malloc()` function in C.

Let's re-open the heap dump file in vim, and let's use the following vim commands to explore
the example heap dump file:

* `:%xd -c 8 5070-1643978841-heap/raw!`: This vim command converts the opened file to a hex dump. The `-c 8` option indicates that we want to display 8 bytes per line.

* `:set hlsearch`: This vim command highlights the search results.

* `:%s/\s\+//g`: This vim command removes all the whitespaces in the file.

* `:%s/\v([0-9a-f]{8}:/\1\` This vim command adds a whitespace after each 8 byte addresses.

* `:%s/\v([0-9a-f]{8}: ([0-9a-f]{16}))/\1\` This vim command adds a whitespace after each heap dump byte line.

To find potential pointers, we can use the following command in vim:

1

:/[0-9a-f]\{12}0\{4}

<caption>Listing 3.13: Vim command to find potential pointers</caption>

This is a search that looks for 12 hexadecimal digits followed by 4 zeros. This is because, the maximum possible addresses in the heap dump file have a size of around 12 hexadecimal digits, and because pointer addresses are in little-endian format, meaning that the last 4 bytes of the address are also the Most Significant Bytes (MSB) of the address.

The result is illustrated below 3.2.7.1:
<figure><img src="image_6.png" /><figcaption>Figure 3.2: Binary RAW heap dump file loaded using vim and xxd, from `/Training/Training/scp/V_-7_8_P1/16/1010-1644391327-heapraw`, with highlight on rows with 12 hexadecimal digits followed by 4 zeros.</figcaption></figure>

We have information about the starting address of the heap using `"HEAP_START": "56343a198000"`. Considering that the example heap dump file contains 135169 bytes, this means that for this given heap dump file, the pointer addresses range from value `9478231303782410` and `9478231317299310`. Note that the little-endian hexadecimal representation of the heap end address is `0x01901b3a3456` which is 12 character long, or 6 bytes long.

Note that conversions here can get confusing, since potential pointer strings extracted from the heap dump file are given in little-endian hexadecimal format, but the heap start address from the JSON annotation file is given in big-endian hexadecimal format.
<figure><img src="image_7.png" /><figcaption>Figure 3.2: Binary RAW heap dump file loaded using vim and xxd, from `/Training/Training/scp/V_7_8_P1/16/1010-1644391327-heapraw`, with highlight on rows with 12 hexadecimal digits followed by 4 zeros.</figcaption></figure>

We have information about the starting address of the heap using `"HEAP_START": "56343a198000"`. Considering that the example heap dump file contains 135169 bytes, this means that for this given heap dump file, the pointer addresses range from value `9478231303782410` and `9478231317299310`. Note that the little-endian hexadecimal representation of the heap end address is `0x01901b3a3456` which is 12 character long, or 6 bytes long.

Note that conversions here can get confusing, since potential pointer strings extracted from the heap dump file are given in little-endian hexadecimal format, but the heap start address from the JSON annotation file is given in big-endian hexadecimal format.
That way, we can refine the detection of potential pointers by only considering the bytes that are in the range of the heap. Potential pointers are highlighted with "<<" in the following hex dump:

```python
# conversion from hex to decimal
def hex_str_to_int(hex_str: str) -> int:
    """
    Convert a normal (big-endian) hex string to an int.
    WARNING: HEAP_START in JSON is big-endian.
    """
    bytes_from_str = bytes.fromhex(hex_str)
    return int.from_bytes(
        bytes_from_str, byteorder='big', signed=False
    )

def pointer_str_to_int(hex_str: str) -> int:
    """
    Convert a pointer hex string to an int.
    WARNING: Pointer hex strings are little-endian.
    """
    bytes_from_str = bytes.fromhex(hex_str)
    return int.from_bytes(
        bytes_from_str, byteorder='little', signed=False
    )
```

<caption>Listing 3.14: Conversions function from hex strings to decimal *int* values.</caption>

Using the functions above, we can check which potential pointers are indeed within the heap dump range.

That way, we can refine the detection of potential pointers. In the following, pointers are highlighted with `<<<` in the following hex dump:

```
00000000: 00000000000000000000000000000000
00000008: 51020000000000000000000000000000
00000010: 06070707070707030300000000000000
00000018: 02000006040102060000000000000000
00000020: 02000001010001070000000000000000
00000028: 06040100000000203000000000000000
00000030: 01030101000000000000000000000000
00000038: 00000000000000000000000000000000
00000040: 00010000000000000000000000000000
00000048: 00000100000000000000000000000000
00000050: 80221a3a345600000000000000000000
00000058: 007f1a3a345600000000000000000000
00000060: f0401a3a345600000000000000000000
00000068: 90321a3a345600000000000000000000
00000070: 608b1a3a345600000000000000000000
00000078: 90471a3a345600000000000000000000
```

<caption>Listing 3.15: 8 bytes per line visualization of a Hex Dump from Training/basic/V_7_8_-P1/16/5070-1643978841-heapraw</caption>
That way, we can refine the detection of potential pointers by only considering the bytes that are in the range of the heap. Potential pointers are highlighted with "<<" in the following hex dump:

```python
# conversion from hex to decimal
def hex_str_to_int(hex_str: str) -> int:
    """
    Convert a normal (big-endian) hex string to an int.
    WARNING: HEAP_START in JSON is big-endian.
    """
    bytes_from_str = bytes.fromhex(hex_str)
    return int.from_bytes(
        bytes_from_str, byteorder='big', signed=False
    )

def pointer_str_to_int(hex_str: str) -> int:
    """
    Convert a pointer hex string to an int.
    WARNING: Pointer hex strings are little-endian.
    """
    bytes_from_str = bytes.fromhex(hex_str)
    return int.from_bytes(
        bytes_from_str, byteorder='little', signed=False
    )
```

<caption>Listing 3.14: Conversions function from hex strings to decimal *int* values.</caption>

Using the functions above, we can check which potential pointers are indeed within the heap dump range.

That way, we can refine the detection of potential pointers. In the following, pointers are highlighted with `<<<` in the following hex dump:

```
00000000: 0000000000000000  .......
00000008: 5102000000000000 Q......
00000010: 0607070707070303 .......
00000018: 0200000604010206 .......
00000020: 0200000101000107 .......
00000028: 0604010000000203 .......
00000030: 0103010100000000 .......
00000038: 0000000000000002 .......
00000040: 0001000000000000 .......
00000048: 0000010000000001 .......
00000050: 80221a3a34560000 .".:4V.. <<<
00000058: 007f1a3a34560000 ...:4V..
00000060: f0401a3a34560000 .@.:4V.. <<<
00000068: 90321a3a34560000 .2.:4V.. <<<
00000070: 608b1a3a34560000 ‘..:4V.. <<<
00000078: 90471a3a34560000 .G.:4V.. <<<
```

<caption>Listing 3.15: 8 bytes per line visualization of a Hex Dump from Training/basic/V_7_8_-P1/16/5070-1643978841-heapraw</caption>
One last check we can do, is verify if the potential pointers are 8-bytes aligned. This can be
done by checking if the last 3 bits of the potential address are 0, or using a modulo 8 operation.
A simple python function can be used to check that:

```python
def is_pointer Aligned(pointer: int) -> bool:
    """
    Check if a pointer is 8-bytes aligned.
    """
    return pointer % 8 == 0
```

<caption>Listing 3.16: Python function to check if a potential pointer is 8-bytes aligned</caption>

Using this function on the potential pointers we have found so far, we can see that all of them
are indeed 8-bytes aligned. This is a good sign for pointer detection, as we now have a range of
tests that can be used to detect potential pointers from other potentially random values.

Here is the pseudocode for the pointer detection algorithm. This algorithm is presented for a
full heap dump file:

**Algorithm 3 Pointer Detection Algorithm**
1: **Procedure** PointerDetection(heapDumpFile, HEAP_START)
2:     heapStart ← hex_str_to_int(HEAP_START)
3:     heapEnd ← heapStart + FileSize{heapDumpFile)}
4:     position ← 0
5:     potentialPointers ← []
6:     **while** position < FileSize{|heapDumpFile|} **do**
7:         block ← Read8Bytes{|heapDumpFile, position})
8:         **if** block ≠ 0 **then**
9:             pointer ← pointer_str_to_int(block)
10:         **if** heapStart ≤ pointer ≤ heapEnd **then**
11:             **if** is_pointer Aligned{pointer} **then**
12:                 Append{pointer, potentialPointers})
13:             **end if**
14:         **end if**
15:     **end if**
16:     position ← position + 8
17:     **end while**
18:     **return** potentialPointers
19: **end Procedure**

This pseudocode outlines the steps for detecting potential pointers in the heap dump file. It starts by reading the heap dump file 8 bytes at a time. For each 8-byte block, it checks if the block is non-zero and within the heap range. If so, it checks if the potential pointer is 8-bytes aligned using the `is_pointer Aligned` function we described before. If all conditions are met, the potential pointer is added to the list of potential pointers. The algorithm returns this list at the end.

### 3.2.7.2 Detecting potential keys

Encryption key prediction is the main focus of the present thesis. As such, we will now focus on
how to detect potential keys in heap dump files. The paper „SmartKex: Machine Learning Assisted
SSH Keys Extraction From The Heap Dump“ introduces 2 algorithms for key detection. The first
one is a brute force approach that consists in trying all the possible keys in the heap dump file.
One last check we can do, is verify if the potential pointers are 8-bytes aligned. This can be
done by checking if the last 3 bits of the potential address are 0, or using a modulo 8 operation.
A simple python function can be used to check that:

<figure><img src="image_8.png" /><figcaption>Listing 3.16: Python function to check if a potential pointer is 8-bytes aligned</figcaption></figure>

Using this function on the potential pointers we have found so far, we can see that all of them
are indeed 8-bytes aligned. This is a good sign for pointer detection, as we now have a range of
tests that can be used to detect potential pointers from other potentially random values.

Here is the pseudocode for the pointer detection algorithm. This algorithm is presented for a
full heap dump file:

**Algorithm 3 Pointer Detection Algorithm**

1: **Procedure** PointerDetection(heapDumpFile, HEAP_START)
2:     heapStart ← hex_str_to_int(HEAP_START)
3:     heapEnd ← heapStart + FileSizeABLATION
4:     position ← 0
5:     potentialPointers ← []
6:     **while** position < FileSize(heapDumpFile) **do**
7:         block ← Read8BytesABLA
8:         **if** block ≠ 0 **then**
9:             pointer ← pointer_str_to_int(block)
10:         **if** heapStart ≤ pointer ≤ heapEnd **then**
11:             **if** is_pointer Aligned(pointer) **then**
12:                 Append(pointer, potentialPointers)
13:             **end if**
14:         **end if**
15:     **end if**
16:     position ← position + 8
17:     **end while**
18:     **return** potentialPointers
19: **end Procedure**

This pseudocode outlines the steps for detecting potential pointers in the heap dump file. It
starts by reading the heap dump file 8 bytes at a time. For each 8-byte block, it checks if the
block is non-zero and within the heap range. If so, it checks if the potential pointer is 8-bytes
aligned using the `is_pointer Aligned` function we described before. If all conditions are met,
the potential pointer is added to the list of potential pointers. The algorithm returns this list at the
end.

### 3.2.7.2 Detecting potential keys

Encryption key prediction is the main focus of the present thesis. As such, we will now focus on
how to detect potential keys in heap dump files. The paper „SmartKex: Machine Learning Assisted
SSH Keys Extraction From The Heap Dump“ introduces 2 algorithms for key detection. The first
one is a brute force approach that consists in trying all the possible keys in the heap dump file.
The second one is a more sophisticated approach that uses a set of rules to detect potential keys.

The first brute-force algorithm is given by:

**Algorithm 4** SSH keys brute-force algorithm from „SmartKex: Machine Learning Assisted SSH Keys Extraction From The Heap Dump“ [0]

1: **Procedure** FindIVAndKey(netPacket, heapDump)
2:     ivLen ← 16
3:     keyLen ← 24
4:     i ← sizeof(cleanHeapDump)
5:     r ← 0
6:     **while** r < i **do**
7:         pIV ← heapDump[r : r + ivLen]
8:         x ← 0
9:         **while** x < i **do**
10:         pKey ← heapDump[x : x + keyLen]
11:        f ← decrypt(netPacket, pIV, pKey)
12:        **if** f is TRUE **then**
13:            **return** pIV, pKey
14:        **end if**
15:        x ← x + 8
16:    ▶ The IV is 8-bytes aligned
17:    **end while**
18:    **end while**
19: **end Procedure**

▶ Based on the encryption method
▶ Based on the encryption method

This algorithm 3.2.7.2 outlines the brute-force approach for finding the Initialization Vector (IV) and the key. Initially, the lengths ivLen and keyLen are set based on the encryption method used for the heap. The algorithm then takes the first ivLen bytes from the heap dump to serve as the potential IV (pIV). Subsequently, keyLen bytes are extracted from the heap dump, starting from the first byte, to act as the potential key (pKey). The algorithm iterates through this potential key until it reaches the end of the heap dump. If decryption of the network packet is unsuccessful, the process is repeated by reading the next potential IV and the subsequent potential key [0].

This algorithm is fairly straightforward, and can be implemented in a few lines of code. However, it is also very inefficient, as it tries all the possible keys in the heap dump file. It also needs some encrypted network packets to be able to test the keys, which are not included in the dataset. As such, we will not implement this algorithm.

This is why the authors of the paper have also developed a more sophisticated algorithm that uses a set of rules to detect potential keys.

No pseudocode is given for the second algorithm, but the paper „SmartKex: Machine Learning Assisted SSH Keys Extraction From The Heap Dump“ gives a description of the algorithm. It relies on the high-entropy assumption of encryption keys. The algorithm is inspired by image processing techniques, and can be described as follows:

This Preprocessing Algorithm serves as a crucial step in adapting the heap data for machine learning models. The algorithm begins by reshaping the raw heap data into an $N \times 8$ matrix $X$, since keys are 8-bytes aligned [0]. Here, $N \times 8$ is the size of the original heap data in bytes. It then calculates the discrete differences of the bytes in both vertical and horizontal directions, storing the results in matrix $Y$. The algorithm employs a logical AND operation on these differences to
The second one is a more sophisticated approach that uses a set of rules to detect potential keys.

The first brute-force algorithm is given by:

**Algorithm 4** SSH keys brute-force algorithm from „SmartKex: Machine Learning Assisted SSH Keys Extraction From The Heap Dump“ [0]

1: **Procedure** FindIVAndKey(netPacket, heapDump)
2:     ivLen ← 16
3:     keyLen ← 24
4:     i ← sizeof(cleanHeapDump)
5:     r ← 0
6:     **while** r < i **do**
7:         pIV ← heapDump[r : r + ivLen]
8:         x ← 0
9:         **while** x < i **do**
10:         pKey ← heapDump[x : x + keyLen]
11:        f ← decrypt(netPacket, pIV, pKey)
12:        **if** f is TRUE **then**
13:            **return** pIV, pKey
14:        **end if**
15:        x ← x + 8
16:        ▶ The IV is 8-bytes aligned
17:        **end while**
18:        **end while**
19:    **end Procedure**

    ▶ Based on the encryption method
    ▶ Based on the encryption method

    ▶ The IV is 8-bytes aligned
    ▶ The key is 8-bytes aligned

This algorithm 3.2.7.2 outlines the brute-force approach for finding the Initialization Vector (IV) and the key. Initially, the lengths ivLen and keyLen are set based on the encryption method used for the heap. The algorithm then takes the first ivLen bytes from the heap dump to serve as the potential IV (pIV). Subsequently, keyLen bytes are extracted from the heap dump, starting from the first byte, to act as the potential key (pKey). The algorithm iterates through this potential key until it reaches the end of the heap dump. If decryption of the network packet is unsuccessful, the process is repeated by reading the next potential IV and the subsequent potential key [0].

This algorithm is fairly straightforward, and can be implemented in a few lines of code. However, it is also very inefficient, as it tries all the possible keys in the heap dump file. It also needs some encrypted network packets to be able to test the keys, which are not included in the dataset. As such, we will not implement this algorithm.

This is why the authors of the paper have also developed a more sophisticated algorithm that uses a set of rules to detect potential keys.

No pseudocode is given for the second algorithm, but the paper „SmartKex: Machine Learning Assisted SSH Keys Extraction From The Heap Dump“ gives a description of the algorithm. It relies on the high-entropy assumption of encryption keys. The algorithm is inspired by image processing techniques, and can be described as follows:

This Preprocessing Algorithm serves as a crucial step in adapting the heap data for machine learning models. The algorithm begins by reshaping the raw heap data into an $N \times 8$ matrix $X$, since keys are 8-bytes aligned [0]. Here, $N \times 8$ is the size of the original heap data in bytes. It then calculates the discrete differences of the bytes in both vertical and horizontal directions, storing the results in matrix $Y$. The algorithm employs a logical AND operation on these differences to
<caption>**Algorithm 5** Image-processing inspired Preprocessing Algorithm, as described in „SmartKex: Machine Learning Assisted SSH Keys Extraction From The Heap Dump“ [0]</caption>

1: **Procedure** PreprocessingABL heapData)
2:     **Reshape** heapData into N × 8 matrix X
3:     **for** i = 0 to N − 1 **do**
4:         **for** j = 0 to 7 **do**
5:             Y[i][j] = |X[i][j] − X[i][j + 1]| & |X[i][j] − X[i + 1][j]|
6:             Z[i] = count(Y[i][k] == 0) ≥ 4
7:             **if** i < N − 1 **then**
8:                 R[i] = Z[i] & Z[i + 1]
9:             **end if**
10:         **end for**
11:     **end for**
12:     **Extract** 128-byte slices from R for training
13: **end Procedure**

identify high-entropy regions, which are likely candidates for encryption keys. Each 8-byte row in Y is examined for randomness, and if at least half of its bytes differ from adjacent bytes, it is marked as a potential part of an encryption key. The algorithm then filters out isolated rows that are unlikely to be part of an encryption key, resulting in an array R. Finally, 128-byte slices are extracted from R for training the machine learning model. This preprocessing step not only adapts the data for machine learning but also narrows down the search space for potential encryption keys, thereby enhancing the efficiency of the subsequent steps.

However, this algorithm is not as efficient as it could be. It relies on using a kind of sliding
window, which is not easily parallelizable. Also, the entropy-inspired computation is not as
straightforward as it could be. That's why we propose a new algorithm that is more efficient and
more easily parallelizable.

In order to perform some ML techniques, and because the keys we are looking for can have a
range of possible lengths (16, 24, 32, or 64 bytes), we shift the focus from detecting the full key,
to just be able to predict the address of the key. That way, we can deal with keys of different sizes,
and we can also use the same algorithm to detect the IV. This is why we will focus on detecting
potential keys addresses, and not the full keys.

We thus introduce a new algorithm for narrowing the search space for potential keys. This
algorithm is inspired by the paper „SmartKex: Machine Learning Assisted SSH Keys Extraction
From The Heap Dump“, but is more efficient and more easily parallelizable, as it focuses on
producing pairs of blocks of 8 bytes with high entropy. It uses directly the Shannon entropy
formula, with each entropy computation being independent of the others.

<caption>**Algorithm 6** Entropy Based Detection of Potential Key blocks</caption>

1: **Procedure** EntropyDetectionABL heapData)
2:     **Pad** heapData with 0s to be 8-bytes aligned
3:     **Reshape** heapData into N × 8 matrix X
4:     **for** i = 0 to N − 1, **do**
5:         entropy[i] = ShannonEntropy(X[i]) ▷ Independents, compute in parallel.
6:     **end for**
7:     **Add** entropy 2 by 2 pairs into entropy pairs ▷ Keep block indexes in resulting tuples.
8:     **Sort** entropy pairs by entropy as sorted pairs
9:     **return** SortedPairs(sorted pairs)
10: **end Procedure**
<caption>**Algorithm 5** Image-processing inspired Preprocessing Algorithm, as described in „SmartKex: Machine Learning Assisted SSH Keys Extraction From The Heap Dump“ [0]</caption>

1: **Procedure** PreprocessingABL heapData)
2:     **Reshape** heapData into N × 8 matrix X
3:     **for** i = 0 to N − 1 **do**
4:         **for** j = 0 to 7 **do**
5:             Y[i][j] = |X[i][j] − X[i][j + 1]| & |X[i][j] − X[i + 1][j]|
6:             Z[i] = count(Y[i][k] == 0) ≥ 4
7:             **if** i < N − 1 **then**
8:                 R[i] = Z[i] & Z[i + 1]
9:             **end if**
10:         **end for**
11:     **end for**
12:     **Extract** 128-byte slices from R for training
13: **end Procedure**

identify high-entropy regions, which are likely candidates for encryption keys. Each 8-byte row in Y is examined for randomness, and if at least half of its bytes differ from adjacent bytes, it is marked as a potential part of an encryption key. The algorithm then filters out isolated rows that are unlikely to be part of an encryption key, resulting in an array R. Finally, 128-byte slices are extracted from R for training the machine learning model. This preprocessing step not only adapts the data for machine learning but also narrows down the search space for potential encryption keys, thereby enhancing the efficiency of the subsequent steps.

However, this algorithm is not as efficient as it could be. It relies on using a kind of sliding
window, which is not easily parallelizable. Also, the entropy-inspired computation is not as
straightforward as it could be. That's why we propose a new algorithm that is more efficient and
more easily parallelizable.

In order to perform some ML techniques, and because the keys we are looking for can have a
range of possible lengths (16, 24, 32, or 64 bytes), we shift the focus from detecting the full key,
to just be able to predict the address of the key. That way, we can deal with keys of different sizes,
and we can also use the same algorithm to detect the IV. This is why we will focus on detecting
potential keys addresses, and not the full keys.

We thus introduce a new algorithm for narrowing the search space for potential keys. This
algorithm is inspired by the paper „SmartKex: Machine Learning Assisted SSH Keys Extraction
From The Heap Dump“, but is more efficient and more easily parallelizable, as it focuses on
producing pairs of blocks of 8 bytes with high entropy. It uses directly the Shannon entropy
formula, with each entropy computation being independent of the others.

<caption>**Algorithm 6** Entropy Based Detection of Potential Key blocks</caption>

1: **Procedure** EntropyDetectionABL heapData)
2:     **Pad** heapData with 0s to be 8-bytes aligned
3:     **Reshape** heapData into N × 8 matrix X
4:     **for** i = 0 to N − 1, **do**
5:         entropy[i] = ShannonEntropy(X[i]) ▷ Independents, compute in parallel.
6:     **end for**
7:     **Add** entropy 2 by 2 pairs into entropy pairs ▷ Keep block indexes in resulting tuples.
8:     **Sort** entropy pairs by entropy as sorted pairs
9:     **return** SortedPairs(sorted pairs)
10: **end Procedure**
The *Entropy Based Detection of Potential Key blocks* algorithm takes a raw heap dump, represented by the variable `heapData`, as input. The data is first padded with zeros to align it to 8-byte blocks and then reshaped into an $N \times 8$ matrix $X$. The Shannon entropy is computed for each 8-byte block in parallel, resulting in an array entropy. Subsequently, the entropy values of adjacent blocks are summed to form pairs, which are stored in `entropy.pairs` along with their block indexes. These pairs are then sorted by their entropy sums to produce `sorted.pairs`. The idea of using pairs of blocks instead of a single block or more than two blocks is related to the minimum key size, which is 16 bytes. This means that we need at least 2 blocks to be able to detect a potential key. The algorithm returns sorted pairs, so that we can easily extract the ones with the highest entropy sums. Given the index of a block, its actual memory address can be recomputed using the `HEAP_START` address available in annotations.

Using this algorithm, let's continue to explore our example heap dump file from 3.2. We will use the following python function to compute the Shannon entropy of a given block of 8 bytes:

```python
def get_entropy(data: bytes):
    """
    Computes the entropy of a byte array, using Shannon's formula.
    """
    if len(data) == 0:
        return 0.0

    # Count the occurrences of each byte value
    _ , counts = np.unique(data, return_counts=True)

    # Calculate the probabilities
    prob = counts / len(data)

    # Calculate the entropy using Shannon's formula
    entropy = -np.sum(prob * np.log2(prob))

    return entropy
```

<caption>Listing 3.17: Python function to compute the Shannon entropy of a given block of 8 bytes</caption>

This function used NumPy array function for efficient computation. We can now use this function to compute the entropy of each block of 8 bytes in the heap dump file. We can then sort the pair of blocks by their entropy, and keep the ones with the highest entropy.

When applied to the file `Training/basic/V_7_8_P1/16/5070-1643978841-heap/raw`, the algorithm produced 16896 entropy pairs, with 631 pairs having the maximum entropy sum. Another test using the index to address conversion and the JSON annotation file also indicate that all the 6 key addresses are within the 631 pairs with the highest entropy sum.

This allows to reduce significantly the search space for potential keys, to already less that 4% of the original heap dump file, which is significantly better than the 30% reduction obtained by the preprocessing algorithm described in the paper *SmartKex* [0], but less that the 2% reduction obtained by the ML-based processing algorithm described in the paper [0]. However, the same paper indicated that it was tested only for Key A and Key C, whereas this algorithm is tested for all the keys. Keep in mind that this is just an example for a single random file in the dataset, as a way to introduce the subject. In-depth experiments will be done in the dedicated chapter on Machine Learning.

Indeed, it is important to mention that we can rely on the JSON annotation files for providing
The *Entropy Based Detection of Potential Key blocks* algorithm takes a raw heap dump, represented by the variable `heapData`, as input. The data is first padded with zeros to align it to 8-byte blocks and then reshaped into an $N \times 8$ matrix $X$. The Shannon entropy is computed for each 8-byte block in parallel, resulting in an array entropy. Subsequently, the entropy values of adjacent blocks are summed to form pairs, which are stored in `entropy.pairs` along with their block indexes. These pairs are then sorted by their entropy sums to produce `sorted.pairs`. The idea of using pairs of blocks instead of a single block or more than two blocks is related to the minimum key size, which is 16 bytes. This means that we need at least 2 blocks to be able to detect a potential key. The algorithm returns sorted pairs, so that we can easily extract the ones with the highest entropy sums. Given the index of a block, its actual memory address can be recomputed using the `HEAP_START` address available in annotations.

Using this algorithm, let's continue to explore our example heap dump file from 3.2. We will use the following python function to compute the Shannon entropy of a given block of 8 bytes:

```python
def get_entropy(data: bytes):
    """
    Computes the entropy of a byte array, using Shannon's formula.
    """
    if len(data) == 0:
        return 0.0

    # Count the occurrences of each byte value
    _ , counts = np.unique(data, return_counts=True)

    # Calculate the probabilities
    prob = counts / len(data)

    # Calculate the entropy using Shannon's formula
    entropy = -np.sum(prob * np.log2(prob))

    return entropy
```

<caption>Listing 3.17: Python function to compute the Shannon entropy of a given block of 8 bytes</caption>

This function used NumPy array function for efficient computation. We can now use this function to compute the entropy of each block of 8 bytes in the heap dump file. We can then sort the pair of blocks by their entropy, and keep the ones with the highest entropy.

When applied to the file `Training/basic/V_7_8_P1/16/5070-1643978841-heap/raw`, the algorithm produced 16896 entropy pairs, with 631 pairs having the maximum entropy sum. Another test using the index to address conversion and the JSON annotation file also indicate that all the 6 key addresses are within the 631 pairs with the highest entropy sum.

This allows to reduce significantly the search space for potential keys, to already less that 4% of the original heap dump file, which is significantly better than the 30% reduction obtained by the preprocessing algorithm described in the paper *SmartKex* [0], but less that the 2% reduction obtained by the ML-based processing algorithm described in the paper [0]. However, the same paper indicated that it was tested only for Key A and Key C, whereas this algorithm is tested for all the keys. Keep in mind that this is just an example for a single random file in the dataset, as a way to introduce the subject. In-depth experiments will be done in the dedicated chapter on Machine Learning.

Indeed, it is important to mention that we can rely on the JSON annotation files for providing
labelling for key address prediction. Using this, we do not need to decrypt the network packets to be able to train our ML models. This is a huge advantage, and is also required since we don't have the encrypted network packets in the dataset. Since we don't have those, and since the keys are already given, that is why we will focus on key address prediction, and not on key prediction.

### 3.2.8 Data structure exploration

Since the dataset contain whole heap dump file, we can also try to detect allocated chunks in those heap dumps. This can be done by looking for patterns in the heap dump file, in a similar fashion as we have done for potential pointers. However, for data structure, we can rely on our knowledge of the C library used to know exactly what to look for.

Since OpenSSH is written in C, we can expect to find some C memory chunks in the heap dump files. C uses the `malloc` function to allocate memory. This function is used to allocate memory for a given data structure. It takes as input the size of the data structure to allocate, and returns a pointer to the allocated memory. We know that the dataset has been produced using `GLIBC 2.28 3.2.2`. Looking directly at the code for `malloc` in `GLIBC 2.28`, we can read in the comments that «Minimum overhead per allocated chunk: 4 or 8 bytes. Each malloc chunk has a hidden word of overhead holding size and status information» [0]. This is what we refer to as the *malloc header*. This means that we can expect to find some 8-bytes aligned blocks in the heap dump file, that are not pointers, but that are the result of a `malloc` call. Detecting and using those *malloc headers* is how we will try to detect memory chunks in heap dump files.

In Linux on a x86_64 architecture, the `malloc` function typically uses a block (chunk) header to store metadata about each allocated block. This header is placed immediately before the block of memory returned to the user. The exact layout can vary depending on the implementation of the C library (e.g., glibc, musl), but generally, it contains the following:

* **Size of the Block**: The size of the allocated block, usually in bytes. This size often includes the size of the header itself and may be aligned to a multiple of 8 or 16 bytes.

* **Flags**: Various flags that indicate the status of the block, such as whether it is free or allocated, or whether the previous block is free or allocated. These flags are often stored in the least significant bits of the size field, taking advantage of the fact that the size is usually aligned, leaving the least significant bits zeroed.

#### 3.2.8.1 How `malloc` handles Heap Allocation

The `malloc` function in `GLIBC 2.28` uses a boundary tag method to manage chunks of memory. Each chunk contains metadata that helps in the allocation and deallocation of memory [0] [0]. Below are the key components of a chunk:

A chunk is a contiguous section of memory, in our case composed of several blocks of 8 bytes, that is handled by `malloc`. It contains the following components [0] [0]:

1. **Size of Previous Chunk**: This field exists only if the previous chunk is unallocated and its P (PREV_INUSE) bit is clear. It helps in finding the front of the previous chunk.

2. **Size of Chunk**: This field contains the size of the chunk in bytes along with three flags: A (NON_main_arena), M (IS_Mmapped), and P (PREV_INUSE). These flags are in the last 3
labelling for key address prediction. Using this, we do not need to decrypt the network packets to be able to train our ML models. This is a huge advantage, and is also required since we don't have the encrypted network packets in the dataset. Since we don't have those, and since the keys are already given, that is why we will focus on key address prediction, and not on key prediction.

### 3.2.8 Data structure exploration

Since the dataset contain whole heap dump file, we can also try to detect allocated chunks in those heap dumps. This can be done by looking for patterns in the heap dump file, in a similar fashion as we have done for potential pointers. However, for data structure, we can rely on our knowledge of the C library used to know exactly what to look for.

Since OpenSSH is written in C, we can expect to find some C memory chunks in the heap dump files. C uses the `malloc` function to allocate memory. This function is used to allocate memory for a given data structure. It takes as input the size of the data structure to allocate, and returns a pointer to the allocated memory. We know that the dataset has been produced using `GLIBC 2.28 3.2.2`. Looking directly at the code for `malloc` in `GLIBC 2.28`, we can read in the comments that «Minimum overhead per allocated chunk: 4 or 8 bytes. Each malloc chunk has a hidden word of overhead holding size and status information» [0]. This is what we refer to as the *malloc header*. This means that we can expect to find some 8-bytes aligned blocks in the heap dump file, that are not pointers, but that are the result of a `malloc` call. Detecting and using those *malloc headers* is how we will try to detect memory chunks in heap dump files.

In Linux on a x86_64 architecture, the `malloc` function typically uses a block (chunk) header to store metadata about each allocated block. This header is placed immediately before the block of memory returned to the user. The exact layout can vary depending on the implementation of the C library (e.g., glibc, musl), but generally, it contains the following:

* **Size of the Block**: The size of the allocated block, usually in bytes. This size often includes the size of the header itself and may be aligned to a multiple of 8 or 16 bytes.

* **Flags**: Various flags that indicate the status of the block, such as whether it is free or allocated, or whether the previous block is free or allocated. These flags are often stored in the least significant bits of the size field, taking advantage of the fact that the size is usually aligned, leaving the least significant bits zeroed.

#### 3.2.8.1 How `malloc` handles Heap Allocation

The `malloc` function in `GLIBC 2.28` uses a boundary tag method to manage chunks of memory. Each chunk contains metadata that helps in the allocation and deallocation of memory [0] [0]. Below are the key components of a chunk:

A chunk is a contiguous section of memory, in our case composed of several blocks of 8 bytes, that is handled by `malloc`. It contains the following components [0] [0]:

1. **Size of Previous Chunk**: This field exists only if the previous chunk is unallocated and its P (PREV_INUSE) bit is clear. It helps in finding the front of the previous chunk.

2. **Size of Chunk**: This field contains the size of the chunk in bytes along with three flags: A (NON_main_arena), M (IS_Mmapped), and P (PREV_INUSE). These flags are in the last 3
LSBs of the size field. This precise block is considered in the following report as the *malloc header* block. Note that the size of the chunk include the size of the *malloc header*, chunk user data and * footer* blocks.

3. **User Data**: This is the actual memory space that is returned to the user.

4. ** Footer**: This is the same as the size of the chunk but is used for application data. Depending on how the chunk is represented, this is exactly the same as the **Size of Chunk** field. This is a more intuitive representation and is the one chosen in the schematic representation below.

5. **Flags**:

* A (`NON_main_arena`): Indicates if the chunk is in the main arena or a thread-specific arena.

* M (`IS_MMAPPED`): Indicates if the chunk is allocated via mmap.

* P (`PREV_INUSE`): Indicates if the previous chunk is in use. If false, it means the previous chunk is free.

The chunk allocation process involves the following concepts:

1. **Initialization**: The very first chunk allocated always has the P bit set to prevent access to non-existent memory.

2. **Free Chunks**: Free chunks are stored in circular doubly-linked lists. They contain forward and backward pointers to the next and previous chunks in the list.

3. **Mmapped Chunks**: These chunks have the M bit set in their size fields and are allocated one-by-one.

4. **Fastbins**: These are treated as allocated chunks and are consolidated only in bulk. These bins are used to speed up the allocation process.

5. **Top Chunk**: This is a special chunk that always exists. If it becomes less than `MINSIZE` bytes long, it is replenished.

As explained directly in the code comments, an allocated chunk of 8 byte blocks can be described by the diagram below [0]. Note that this representation is personal to better suit the needs of our forensic analysis. The slight difference resides in the fact that the * footer* with the size of the considered chunk is represented as being part of the next chunk and not the current chunk. The * footer* of the previous chunk is actually the `mchunkptr` address. As stated in the GlicC wiki: «within the malloc library, a "chunk pointer" or `mchunkptr` does not point to the beginning of the chunk, but to the last word in the previous chunk - i.e. the first field in `mchunkptr` is not valid unless you know the previous chunk is free» [0]. Due to consideration of free/allocated chunks, it's actually easier to just consider the * footer* as being part of the next chunk, and not the current chunk. This is why the diagram below is slightly different from the one in the GLIBC wiki. This is just a difference in schematic representation, and does not change the actual data structure.
LSBs of the size field. This precise block is considered in the following report as the *malloc header* block. Note that the size of the chunk include the size of the *malloc header*, chunk user data and * footer* blocks.

3. **User Data**: This is the actual memory space that is returned to the user.

4. ** Footer**: This is the same as the size of the chunk but is used for application data. Depending on how the chunk is represented, this is exactly the same as the **Size of Chunk** field. This is a more intuitive representation and is the one chosen in the schematic representation below.

5. **Flags**:

* A (`NON_main_arena`): Indicates if the chunk is in the main arena or a thread-specific arena.

* M (`IS_MMAPPED`): Indicates if the chunk is allocated via mmap.

* P (`PREV_INUSE`): Indicates if the previous chunk is in use. If false, it means the previous chunk is free.

The chunk allocation process involves the following concepts:

1. **Initialization**: The very first chunk allocated always has the P bit set to prevent access to non-existent memory.

2. **Free Chunks**: Free chunks are stored in circular doubly-linked lists. They contain forward and backward pointers to the next and previous chunks in the list.

3. **Mmapped Chunks**: These chunks have the M bit set in their size fields and are allocated one-by-one.

4. **Fastbins**: These are treated as allocated chunks and are consolidated only in bulk. These bins are used to speed up the allocation process.

5. **Top Chunk**: This is a special chunk that always exists. If it becomes less than `MINSIZE` bytes long, it is replenished.

As explained directly in the code comments, an allocated chunk of 8 byte blocks can be described by the diagram below [0]. Note that this representation is personal to better suit the needs of our forensic analysis. The slight difference resides in the fact that the * footer* with the size of the considered chunk is represented as being part of the next chunk and not the current chunk. The * footer* of the previous chunk is actually the *mchunkptr* address. As stated in the GlicC wiki: «within the malloc library, a "chunk pointer" or *mchunkptr* does not point to the beginning of the chunk, but to the last word in the previous chunk - i.e. the first field in *mchunkptr* is not valid unless you know the previous chunk is free» [0]. Due to consideration of free/allocated chunks, it's actually easier to just consider the * footer* as being part of the next chunk, and not the current chunk. This is why the diagram below is slightly different from the one in the GLIBC wiki. This is just a difference in schematic representation, and does not change the actual data structure.
<figure><img src="image_7.png" /><figcaption>Figure 3.3: Diagram of an allocated chunk in GLIBC 2.28 [0].</figcaption></figure>

The `malloc` function in `GLIBC 2.28` uses a boundary tag method to manage chunks of memory. Each chunk contains metadata that helps in the allocation and deallocation of memory [0] [0]. The library stores available free chunks in circular doubly-linked lists called «bins». This allows to quickly find a free chunk of memory of a given size. The problem is that we don't have access to those bins in the heap dump file. So to detect if a given chunk is in-use or free, we can rely on several methods. The first one is to look at the P bit of the `malloc` header. If it is set to 1, it means that the chunk is in use. If it is set to 0, it means that the chunk is free.

I also remarked that sometimes, the given heap dump file is cropped, and the last block is only composed of zeros and not complete. This is for instance the case with the last chunk of `Training/basic/V_7_1_P1/24/17016-1643962152-heap/raw`.

1

WARN: Chunk [94022266975200] Chunk(block_index=10876, size=48176, flags=[A=False, M=False, P=True]) is out of bounds. Last block index: 16895 Iteration index: 16896

2

WARN: Chunk [94022266975200] Chunk(block_index=10876, size=48176, flags=[A=False, M=False, P=True]) is out of bounds. Last block index: 16895 Iteration index: 16897

3

Chunk(block_index=10876, size=48176) is only composed of zeros.

Listing 3.18: Logs from chunk exploration script, related to the last chunk of the file `Training/basic/V_7_1_P1/24/17016-1643962152-heap/raw`.

A free chunk contains the pointers of the next and previous free chunks in the heap, for its given bin. A representation of a free chunk, based directly on the code documentation [0], is given below:
<figure><img src="image_9.png" /><figcaption>Figure 3.3: Diagram of an allocated chunk in GLIBC 2.28 [0].</figcaption></figure>

The malloc function in GLIBC 2.28 uses a boundary tag method to manage chunks of memory. Each chunk contains metadata that helps in the allocation and deallocation of memory [0] [0]. The library stores available free chunks in circular doubly-linked lists called «bins». This allows to quickly find a free chunk of memory of a given size. The problem is that we don't have access to those bins in the heap dump file. So to detect if a given chunk is in-use or free, we can rely on several methods. The first one is to look at the P bit of the malloc header. If it is set to 1, it means that the chunk is in use. If it is set to 0, it means that the chunk is free.

I also remarked that sometimes, the given heap dump file is cropped, and the last block is
only composed of zeros and not complete. This is for instance the case with the last chunk of
*Training/basic/V_7_1_P1/24/17016-1643962152-heap/raw*.

1

WARN: Chunk [94022266975200] Chunk(block_index=10876, size=48176, flags=[A=False, M=False, P=True]) is out of bounds. Last block index: 16895 Iteration index: 16896

2

WARN: Chunk [94022266975200] Chunk(block_index=10876, size=48176, flags=[A=False, M=False, P=True]) is out of bounds. Last block index: 16895 Iteration index: 16897

3

Chunk(block_index=10876, size=48176) is only composed of zeros.

Listing 3.18: Logs from chunk exploration script, related to the last chunk of the file *Training/basic/V_7_1_P1/24/17016-1643962152-heap/raw*.

A free chunk contains the pointers of the next and previous free chunks in the heap, for its
given bin. A representation of a free chunk, based directly on the code documentation [0], is given
below:
<figure><img src="image_8.png" /><figcaption>Figure 3.4: Diagram of a free chunk in GLIBC 2.28 [0].</figcaption></figure>

### 3.2.8.2 Chunk chaining

The chunk chaining algorithm relies on the **chunk chaining assumption** 3.2.1. This assumption states that the allocator allocates chunks after chunks, and that the chunks are contiguous in memory. This means that we can expect to find the malloc header of the next chunk at the address `current_malloc_header_chunk_address + current_chunk_size + 8`, where 8 is the size of the malloc header block, or `current_chunk_user_data_address + current_chunk_size`. It is the case for both free and allocated chunks. This is why we can use this assumption to detect chunks in the heap dump file.

This necessitates to understand malloc header blocks, and how they are represented in the heap dump file. In the specific case of GLIBC 2.28, the malloc header is defined as follows:

1

#define SIZE_BITS (PREV_INUSE | IS_MMAPPED | NON_main_arena)

<caption>Listing 3.19: Malloc header definition in GLIBC 2.28</caption>

Since the malloc header respects the endianness of the system, we can expect to find the malloc header in little-endian format in the heap dump file. Using `vim` on `Training/basic/V_7_8_P1/16/5070-1643978841-heapraw`, we can use the following command to find some potential malloc headers:

1

:/[0-9a-f]\{4}0\{12}

<caption>Listing 3.20: Vim command to find potential malloc headers</caption>
<figure><img src="image_10.png" /><figcaption>Figure 3.4: Diagram of a free chunk in GLIBC 2.28 [0].</figcaption></figure>

### 3.2.8.2 Chunk chaining

The chunk chaining algorithm relies on the **chunk chaining assumption** 3.2.1. This assumption states that the allocator allocates chunks after chunks, and that the chunks are contiguous in memory. This means that we can expect to find the malloc header of the next chunk at the address `current_malloc_header_chunk_address + current_chunk_size + 8`, where 8 is the size of the malloc header block, or `current_chunk_user_data_address + current_chunk_size`. It is the case for both free and allocated chunks. This is why we can use this assumption to detect chunks in the heap dump file.

This necessitates to understand malloc header blocks, and how they are represented in the heap dump file. In the specific case of GLIBC 2.28, the malloc header is defined as follows:

1. `#define SIZE_BITS (PREV_INUSE | IS_MMAPPED | NON_main_arena)`

<caption>Listing 3.19: Malloc header definition in GLIBC 2.28</caption>

Since the malloc header respects the endianness of the system, we can expect to find the malloc header in little-endian format in the heap dump file. Using `vim` on `Training/basic/V_7_8_P1/16/5070-1643978841-heapraw`, we can use the following command to find some potential malloc headers:

1. `:/[0-9a-f]\{4}0\{12}`

<caption>Listing 3.20: Vim command to find potential malloc headers</caption>
This gives something like the following:

<figure><img src="image_9.png" /><figcaption>Figure 3.5: Attempt at malloc header detection in `Training/basic/V_7_8_P1/16/5070-1643978841-heap/raw`, at heap start.</figcaption></figure>

Indeed, after a first zero block of 8 bytes (potential previous chunk footer), we expect a first data structure to be allocated at the start of the heap. Here this data structure is of size 5102000000000000$_{16LE}$ (little-endian hex format) or $593_{10}$ bytes. The fact that it is an odd number is due to the LSB being set to 1, to indicate that the preceding chunk is allocated (P flag). This means that the real size of the structure is actually $593_{10} - 1_{10} = 592_{10}$. This value is 8-byte aligned.

Since we know that the allocator allocates chunks after chunks, we can expect the next chunk to be allocated at the address $5102000000000000_{16LE} + 592_{10} + 8_{10} = 5882193a34560000_{16LE} =$. Note that we need to add 8 to the size to account for the malloc header block.

In vim, since the address start at 0, we have to look at $592_{10} + 8_{10} = 258_{16}$. Let's have a look there:

<figure><img src="image_10.png" /><figcaption>Figure 3.6: Attempt at malloc header detection in `Training/basic/V_7_8_P1/16/5070-1643978841-heap/raw`, at index $592_{10} = 258_{16}$.</figcaption></figure>

There, we can see a zero block, followed by what we can expect to be another malloc header at address $258_{16}$. By doing the same process, we can thus propose an algorithm to detect the malloc headers, and thus the structures in the heap dump file.

First, here is a simple algorithm to extract all the necessary information from a malloc header block:
This gives something like the following:

<figure><img src="image_11.png" /><figcaption>Figure 3.5: Attempt at malloc header detection in `Training/basic/V_7_8_P1/16/5070-1643978841-heap/raw`, at heap start.</figcaption></figure>

Indeed, after a first zero block of 8 bytes (potential previous chunk footer), we expect a first data structure to be allocated at the start of the heap. Here this data structure is of size 5102000000000000$_{16LE}$ (little-endian hex format) or $593_{10}$ bytes. The fact that it is an odd number is due to the LSB being set to 1, to indicate that the preceding chunk is allocated (P flag). This means that the real size of the structure is actually $593_{10} - 1_{10} = 592_{10}$. This value is 8-byte aligned.

Since we know that the allocator allocates chunks after chunks, we can expect the next chunk to be allocated at the address $5102000000000000_{16LE} + 592_{10} + 8_{10} = 5882193a34560000_{16LE} =$. Note that we need to add 8 to the size to account for the malloc header block.

In vim, since the address start at 0, we have to look at $592_{10} + 8_{10} = 258_{16}$. Let's have a look there:

<figure><img src="image_12.png" /><figcaption>Figure 3.6: Attempt at malloc header detection in `Training/basic/V_7_8_P1/16/5070-1643978841-heap/raw`, at index $592_{10} = 258_{16}$.</figcaption></figure>

There, we can see a zero block, followed by what we can expect to be another malloc header at address $258_{16}$. By doing the same process, we can thus propose an algorithm to detect the malloc headers, and thus the structures in the heap dump file.

First, here is a simple algorithm to extract all the necessary information from a malloc header block: