cited []

Masterarbeit

Predicting SSH keys in Open SSH Memory dumps

A report by

Rascoussier, Florian Guillaume Pierre
Matrikelnummer (Passau): 112485
Matrikelnummer (INSA): 4018543
ORCID: 0009-0005-3253-9814

Erstprüfer
Prof. Dr. Harald Kosch
Zweitprüfer
Prof. Dr. Michael Granitzer
Betreuer
Christofer Fellicious
Prof. Dr. Pierre-Edouard Portier
Prof. Dr. Elöd Egyed-Zsigmond

August 28, 2024

### Abstract

As the digital landscape evolves, cybersecurity has become an indispensable
focus of IT systems. Its ever-escalating challenges have amplified the
importance of digital forensics, particularly in the analysis of heap dumps
from main memory. In this context, the Secure Shell protocol (SSH) designed
for encrypted communications, serves as both a safeguard and a potential veil
for malicious activities. This research project focuses on predicting SSH keys
in OpenSSH memory dumps, aiming to enhance protective measures against illicit
access and enable the development of advanced security frameworks or tools
like honeypots.

This Masterarbeit is situated within the broader SmartVMI project, a
collaborative research initiative with the objective to advance artificial
intelligence-based mechanisms for attack detection and digital forensics.
Specifically, this work seeks to build upon existing research on key
prediction in OpenSSH heap dumps. Utilizing machine learning and deep learning
models, the study aims to refine feature for embedding techniques and explore
innovative methods for effective key detection. The objective is to accurately
predict the presence and location of SSH keys within memory dumps. This work
builds upon, and aims to enhance, the foundations laid by SSHkex [1] and
SmartKex [10], enriching both the methodology and the results of the original
research while exploring the untapped potential of newly proposed approaches.

The current thesis dives into memory graph modelization from raw binary heap
dump files. Each memory graph can support a range of embeddings than can be
used directly for model training, through the use of classic ML models and
graph neural network. The report encapsulates the progress of a year-long
Master’s thesis research project executed between October 2022 and October
2023. Conducted within the framework of the PhDTrack program between the
University of Passau and INSA Lyon, the research has been supervised by Prof.
Dr. Michael Granitzer and Christofer Fellicious from the University of Passau,
as well as Prof. Dr. Pierre-Edouard Portier from INSA Lyon. It offers an in-
depth discussion on the current state-of-the-art in key prediction for OpenSSH
memory dumps, research questions, experimental setups, programs development,
results as well as discussing potential future directions.

### Acknowledgements

First acknowledgement goes to Christofer Fellicious, my supervisor at the
University of Passau, for his guidance, support and feedback during the
Masterarbeit.

I want to express my sincere gratitude to my colleague and friend, Clément
Lahoche, whose human and technical skills have been a great source of
inspiration and motivation throughout this project; especially considering
that we have been working on closely related subjects. It has been a great
pleasure to share our ideas and insights, and to collaborate on the
development of several programs necessary for the experimentation.

Another acknowledgements go to my esteemed supervisors Prof. Dr. Granitzer and
Prof. Dr. Portier for their support and feedback during the Masterarbeit.

I would also like to express my sincere gratitude to all the persons that have
helped me, even punctually, during the Masterarbeit with their valuable help,
insights, discussions and contributions as well as all the persons involved in
the PhDTrack program that made this Masterarbeit possible, including but not
limited to:

  * •

Lionel Brunie, Director of CS Department at INSA Lyon, that makes this
PhDTrack program possible from the French side.

  * •

Harald Kosch, Head of the Chair of Distributed Information Systems at the
University of Passau, that makes this PhDTrack program possible from the
German side.

  * •

Natalia Lucari, PhDTrack coordinator at INSA Lyon, for her support and help
during the PhDTrack program.

  * •

Ophelie Coueffe, PhDTrack coordinator at the University of Passau, for her
patience, support and invaluable help during the PhDTrack program.

  * •

Elöd Egyed-Zsigmond, PhDTrack coordinator at INSA Lyon, for the subject
selection, administrative support and final proofreading.

  * •

All the other PhDTrack students for the great atmosphere, mutual help and the
interesting discussions during almost two years.

I cannot forget to mention my many friends from Lyon to Passau and beyond, for
their encouragements during this Masterarbeit.

Finally, my last acknowledgements go to my family whose support has been
precious throughout the two years of the PhDTrack program.

###### Contents

  1. 1 Introduction
    1. 1.1 Research Questions
    2. 1.2 Commitment to Open Science and Reproducibility
      1. 1.2.1 GitHub Repositories
      2. 1.2.2 Datasets
    3. 1.3 Structure of the Thesis
  2. 2 Background
    1. 2.1 SSH and OpenSSH Implementation
      1. 2.1.1 Basics of the Secure Shell Protocol (SSH)
        1. 2.1.1.1 SSH design and origin
        2. 2.1.1.2 SSH keys
        3. 2.1.1.3 SSH key encryption
      2. 2.1.2 OpenSSH Implementation
        1. 2.1.2.1 OpenSSH components
        2. 2.1.2.2 OpenSSH hashing
      3. 2.1.3 The state of SSH security
        1. 2.1.3.1 SSH security issues
        2. 2.1.3.2 SSH vulnerabilities
        3. 2.1.3.3 SSH and cyber-attacks
      4. 2.1.4 The Imperative of SSH Honeypots in Cybersecurity Monitoring
      5. 2.1.5 Research context and motivation for this Masterarbeit
    2. 2.2 Previous Work on OpenSSH key extraction
      1. 2.2.1 SSHKex
      2. 2.2.2 SmartKex
        1. 2.2.2.1 Baseline brute-force method
        2. 2.2.2.2 SmartKex machine-learning method
      3. 2.2.3 Objectives of the present work
    3. 2.3 Graph-based memory modelization
      1. 2.3.1 Defining memory concepts and modelization
        1. 2.3.1.1 Endianness
        2. 2.3.1.2 The role of entropy in forensic analysis
      2. 2.3.2 Graphs and Knowledge Graphs
        1. 2.3.2.1 Defining Graph Theory concepts
        2. 2.3.2.2 Graphs types
        3. 2.3.2.3 Graph vs Knowledge Graph
        4. 2.3.2.4 Ontologies
        5. 2.3.2.5 Inductive Reasoning and Learning
    4. 2.4 Data preprocessing for Machine Learning
      1. 2.4.1 Feature engineering
        1. 2.4.1.1 Types of Features
        2. 2.4.1.2 The Curse of Dimensionality
        3. 2.4.1.3 Feature Engineering techniques
        4. 2.4.1.4 Evaluating Features with Correlation Tests
      2. 2.4.2 Embeddings
        1. 2.4.2.1 Embedding Creation vs Feature Engineering
        2. 2.4.2.2 Embeddings for graphs
        3. 2.4.2.3 Word Embeddings
      3. 2.4.3 Other preprocessing techniques for Machine Learning
        1. 2.4.3.1 Data Cleaning
        2. 2.4.3.2 Dataset splitting and sampling
        3. 2.4.3.3 Dealing with Imbalanced Datasets
    5. 2.5 Machine Learning and Deep Learning
      1. 2.5.1 Machine Learning
        1. 2.5.1.1 What is Machine Learning
        2. 2.5.1.2 Model Evaluation
      2. 2.5.2 Machine Learning Models for Binary Classification
      3. 2.5.3 Deep Learning
        1. 2.5.3.1 Recurrent Neural Networks (RNN)
        2. 2.5.3.2 Long Short-Term Memory (LSTM)
        3. 2.5.3.3 Gated Recurrent Units (GRU)
        4. 2.5.3.4 Convolutional Neural Networks (CNN)
        5. 2.5.3.5 Graph Convolutional Networks (GCN)
      4. 2.5.4 Graph Neural Networks
        1. 2.5.4.1 Recursive Graph Neural Networks (RecGNNs)
        2. 2.5.4.2 Convolutional Graph Neural Networks (ConvGNNs)
  3. 3 Methods
    1. 3.1 Hardware and software architecture
      1. 3.1.1 Hardware development and testing environment
      2. 3.1.2 Software, languages and tools
        1. 3.1.2.1 Packaging and deployment
    2. 3.2 OpenSSH memory dumps dataset
      1. 3.2.1 Assumptions
      2. 3.2.2 Dataset production system information
      3. 3.2.3 Conventions and vocabulary
      4. 3.2.4 Estimating the dataset balancing for key prediction
      5. 3.2.5 Dataset validation
        1. 3.2.5.1 Automatic annotation validation
      6. 3.2.6 Dataset cleaning
      7. 3.2.7 Exploring patterns in RAW heap dump files
        1. 3.2.7.1 Detecting potential pointers
        2. 3.2.7.2 Detecting potential keys
      8. 3.2.8 Data structure exploration
        1. 3.2.8.1 How malloc handles Heap Allocation
        2. 3.2.8.2 Chunk chaining
        3. 3.2.8.3 Chunk chaining example
        4. 3.2.8.4 Distinguishing between free and allocated chunks
        5. 3.2.8.5 Chunk footer
      9. 3.2.9 Discussing chunk parsing for problem scale reduction
        1. 3.2.9.1 From a block-based to a chunk-based approach
        2. 3.2.9.2 Using chunk footer for filtering is not possible
        3. 3.2.9.3 Chunk filtering
    3. 3.3 Graph-based memory dumps embedding
      1. 3.3.1 Initial work from Python to Rust
      2. 3.3.2 Memory Graph Representation
    4. 3.4 From heap dump to memory graph embeddings
      1. 3.4.1 Initialization and data checking
        1. 3.4.1.1 Graph Construction steps
        2. 3.4.1.2 Graph Annotation
        3. 3.4.1.3 Custom Graph-Based Embeddings
        4. 3.4.1.4 Exporting the Graph
    5. 3.5 A wide range of features and embeddings
      1. 3.5.1 Embeddings based on custom features
        1. 3.5.1.1 Remark on the collaborative work
        2. 3.5.1.2 Semantic graph embedding
        3. 3.5.1.3 Semantic features from essential chunks attributes
        4. 3.5.1.4 Statistical Embedding
        5. 3.5.1.5 Start-bytes Embedding
      2. 3.5.2 Embedding transformations depending on the model
        1. 3.5.2.1 Node filtering to feature
      3. 3.5.3 Graph-agnostic Embeddings
        1. 3.5.3.1 RandomWalk
        2. 3.5.3.2 Node2Vec
    6. 3.6 Machine Learning Binary Classification
      1. 3.6.1 Classic Models of Machine Learning
        1. 3.6.1.1 Random Forest
        2. 3.6.1.2 Logistic Regression
        3. 3.6.1.3 SGD Classifier
      2. 3.6.2 Graph Convolutional Networks (GCN)
        1. 3.6.2.1 Very Simple GCN
        2. 3.6.2.2 Simple GCN Models
        3. 3.6.2.3 First GCN Model
      3. 3.6.3 The Impact of Complexity
      4. 3.6.4 Understanding Dropout in GCNs
        1. 3.6.4.1 Effect on Binary Classification
        2. 3.6.4.2 Batch Normalization
      5. 3.6.5 More Complex GCN Models
        1. 3.6.5.1 GCN with Dropout and Batch Normalization
        2. 3.6.5.2 Advanced GCN
  4. 4 Results
    1. 4.1 Developed programs
      1. 4.1.1 Mem2Graph
      2. 4.1.2 Machine Learning Pipelines Runner
      3. 4.1.3 Other programs
    2. 4.2 Experimental Setup
      1. 4.2.1 Generation of the memgraph datasets
      2. 4.2.2 Sanity checking and preloading the generated memgraph datasets
      3. 4.2.3 Launching the experiments
      4. 4.2.4 Dealing with hyperparameter tuning
        1. 4.2.4.1 Limited number of input graphs due to compute time and memory usage
        2. 4.2.4.2 Parallel launch of experiments for hyperparameters tuning
        3. 4.2.4.3 Description of the results.csv File
    3. 4.3 Obtained Results
      1. 4.3.1 Feature Engineering results
      2. 4.3.2 Classic Model results
      3. 4.3.3 Deep Learning GCN Model results
    4. 4.4 Compared Performances of models and embeddings
  5. 5 Discussion
    1. 5.1 Discussion of the results
      1. 5.1.1 Objectives of the experiments
      2. 5.1.2 Discussing features and embeddings
      3. 5.1.3 Classic ML models performances
        1. 5.1.3.1 Logistic Regression
        2. 5.1.3.2 Random Forest
        3. 5.1.3.3 SGD Classifier
        4. 5.1.3.4 Comparison
      4. 5.1.4 GCN models performances
        1. 5.1.4.1 Very Simple GCN
        2. 5.1.4.2 Simple GCN
        3. 5.1.4.3 First GCN
        4. 5.1.4.4 GCN with Dropout
        5. 5.1.4.5 Advanced GCN
        6. 5.1.4.6 Layer Complexity
      5. 5.1.5 Comparing the embeddings impact on the models
      6. 5.1.6 Comparing GCN and classical ML models
        1. 5.1.6.1 Overall Performance
        2. 5.1.6.2 Precision
        3. 5.1.6.3 Recall
        4. 5.1.6.4 Class Separation (AUC)
        5. 5.1.6.5 Considerations for Small Datasets
        6. 5.1.6.6 Summary
    2. 5.2 Limitations of the Experiments
      1. 5.2.1 Limited number of input graphs
      2. 5.2.2 Duration of the experiments
  6. 6 Conclusion
    1. 6.1 Summary of Results
      1. 6.1.1 Dataset Exploration
      2. 6.1.2 Memory Graph Generation
      3. 6.1.3 Feature Engineering and Embeddings
      4. 6.1.4 Conclusion on Model Performances
    2. 6.2 Outlook on Future Work
  7. .3 Code and files
  8. .4 Memory Graphs
  9. .5 Latest ML Experiment results

###### List of Figures

  1. 2.1 Graphical representation of an rdf:Bag container.
  2. 3.1 Illustration of the Dataset Directory Structure
  3. 3.2 Binary RAW heap dump file loaded using vim and xxd, from /Training/Training/scp/V_7_8_P1/16/1010-1644391327-heap.raw, with highlight on rows with 12 hexadecimal digits followed by 4 zeros.
  4. 3.3 Diagram of an allocated chunk in GLIBC 2.28 [6].
  5. 3.4 Diagram of a free chunk in GLIBC 2.28 [6].
  6. 3.5 Attempt at malloc header detection in Training/basic/V_7_8_P1/16/5070-1643978841-heap.raw, at heap start.
  7. 3.6 Attempt at malloc header detection in Training/basic/V_7_8_P1/16/5070-1643978841-heap.raw, at index $592_{10}=250_{16}$.
  8. 3.7 Heap dump showing a mix of free and in-use chunks. Note: each chunk immediately after a free chunk has a P flag set to 0. Each rectangle represents a chunk.
  9. 3.8 Visualization of the entropy distribution for all chunks of the phdtrack_data_clean/ RAW heap dump dataset.
  10. 3.9 Visualization of a truncated memory graph generated from Training/basic/V_7_1_P1/24/17016-1643962152-heap.raw. The addresses are not displayed for improved readability. Version with addresses here 3.
  11. 3.10 Visualization of the chunk memory graph, with only Chunk Header Nodes representing chunks, generated from Training/scp/V_7_8_P1/16/ 585-1644391327-heap.raw.
  12. 4.1 Illustration of the Data Directory Structure
  13. 4.2 Feature correlation matrices on the different Mem2Graph-generated datasets. Used algorithm: Kendall.
  14. 4.3 Feature correlation matrices on the different Mem2Graph-generated datasets. Used algorithm: Pearson.
  15. 4.4 Feature correlation matrices on the different Mem2Graph-generated datasets. Used algorithm: Spearman.
  16. 4.5 Visualization of the result metrics use to compare model performance on memory graphs, for different embeddings and hyperparameters.
  17. 4.6 Visualization of the result metrics use to compare model performance per memory graph node embedding strategies.
  18. 1 Visualization of the full memory graph generated from Training/scp/V_7_8_P1/16/302-1644391327-heap.raw.
  19. 2 Visualization of the full memory graph generated from Training/basic/V_7_1_P1/24/17016-1643962152-heap.raw.
  20. 3 Visualization of a truncated memory graph generated from Training/basic/V_7_1_P1/24/17016-1643962152-heap.raw. Here with real addresses.
  21. 4 Visualization of a chunk memory graph generated from Validation/Validation/basic/V_7_8_P1/24/8708-1643979488-heap.raw.
  22. 5 Visualization of a chunk memory graph generated from Training/Training/basic/V_6_8_P1/24/28621-1643890740-heap.raw.

###### List of Tables

  1. 4.1 Code Statistics for Masterarbeit
  2. 4.2 Best instances of model: logistic-regression.
  3. 4.3 Best instances of model: random-forest.
  4. 4.4 Best instances of model: sgd-classifier.
  5. 4.5 Best instances of model: very-simple-gcn.
  6. 4.6 Best instances of model: simple-gcn.
  7. 4.7 Best instances of model: first-gcn.
  8. 4.8 Best instances of model: gcn-with-dropout.
  9. 4.9 Best instances of model: advanced-gcn.
  10. 4.10 Results for the model very-simple-gcn
  11. 5.1 Duration times for duration of embedding generation in ML/DL/FE pipeline (in seconds).
  12. 5.2 Duration times for duration of training and testing in ML/DL/FE pipeline (in seconds).
  13. 1 Best instance for each model, with respect to accuracy.
  14. 2 Best instance for each model, with respect to precision.
  15. 3 Best instance for each model, with respect to recall.
  16. 4 Best instance for each model, with respect to f1 score.
  17. 5 Best model instance for each metric.

###### Listings

  1. 1 16 bytes per line visualization of a Hex Dump from Training/basic/V_7_8_P1/16/5070-1643978841-heap.raw
  2. 2 8 bytes per line visualization of a Hex Dump from Training/basic/V_7_8_P1/16/5070-1643978841-heap.raw
  3. 3 Complete JSON example, from Training/basic/V_7_8_P1/16/5070-1643978841.json
  4. 4 Command and logs of the C-library version used for the dataset generation
  5. 5 Command and logs of the Linux Standard Base Release used for the dataset generation
  6. 6 Command and logs of the OS and kernel version used for the dataset generation
  7. 7 Count all dataset files
  8. 8 Get the total size of the dataset
  9. 9 Find the number of RAW files in the dataset
  10. 10 Find the number of bytes of RAW files in the dataset
  11. 11 Missing keys in JSON annotation file Training/basic/V_6_0_P1/16/24375-1644243522.json
  12. 12 Command and logs of counting the number of RAW files in the cleaned dataset.
  13. 13 Vim command to find potential pointers
  14. 14 Conversions function from hex strings to decimal $int$ values.
  15. 15 8 bytes per line visualization of a Hex Dump from Training/basic/V_7_8_P1/16/5070-1643978841-heap.raw
  16. 16 Python function to check if a potential pointer is 8-bytes aligned
  17. 17 Python function to compute the Shannon entropy of a given block of 8 bytes
  18. 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.
  19. 19 Malloc header definition in GLIBC 2.28
  20. 20 Vim command to find potential malloc headers
  21. 21 Testing chunk parsing on Training/basic/V_7_1_P1/24/17016-1643962152-heap.raw. Partial log output.
  22. 22 Printing some free and in-use chunks from Training/basic/V_7_1_P1/24/17016-1643962152-heap.raw.
  23. 23 Printing cleaned dataset chunk parsing global statistics.
  24. 24 Command used to generate the memory graph visualization of Training/basic/V_7_1_P1/24/17016-1643962152-heap.raw
  25. 25 A comment field example for a node with embedding. Output is cropped.
  26. 26 A memgraph comment field example containing JSON serialized object with embedding type and feature names. Output is cropped.
  27. 27 Command used to count the number of lines of code in the phdtrack directory, containing the reposiroties of the present thesis.
  28. 28 Sample of final logs of the Mem2Graph program, after generating 6 memgraph datasets from the cleaned heap dump dataset.
  29. 29 Result logs of the memory_graph_gcn/src/sanity_check_gv_files.py program.
  30. 30 Command used to launch final experiments, on Drogon server.
  31. 31 JSON hyperparameters used during experiments
  32. 32 JSON hyperparameters used during experiments
  33. 33 The DOT file of uncompressed block memgraph, here Training/basic/V_7_1_P1/24/17016-1643962152-heap.raw, with real addresses. Output is cropped.
  34. 34 Command used to generate the memory graph visualization of Training/basic/V_7_1_P1/24/17016-1643962152-heap.raw here using real addresses.

## 1 Introduction

The digital age has brought with it an unprecedented increase in the volume
and complexity of data that is being generated, stored, and processed. This
data is often sensitive in nature, and its security is of paramount
importance, making cybersecurity a critical focus area. This evolving
landscape is fraught with challenges that continue to amplify the importance
of digital forensics in IT systems. One area that stands out for its
widespread use and importance is the Secure Shell protocol (SSH) and its most
popular implementation, OpenSSH. SSH is a cryptographic network protocol
widely used for secure remote access to systems. It is also used for secure
file transfer, and as a secure tunnel for other applications. SSH is a key
component of IT systems whose encryption capabilities are critical to the
security of IT systems. However, it also presents a unique set of challenges,
most notably the concealment of malicious activities.

A common case is when an unauthorized actor gains access to SSH keys so as to
get access to a system. This can happen through a malicious human actor, but
more commonly through automated processes such as malwares and botnets. This
situation presents a formidable and growing threat to cybersecurity, affecting
a broad range of stakeholders from governments and financial institutions to
individual users. In just 2019, the number of Command and Control (C&C)
servers for botnets increased by 71.5%, leading to an estimated $19 billion in
advertising theft [76]. Many malwares and botnets have in common that they
have used as attack vector the Secure Shell (SSH) remote access service [76].

At the heart of the issue lies the fact that SSH veils its communications
through encryption, making it difficult to detect malicious activities. To be
able to detect those potential malicious actors, it is possible to replace SSH
by a honeypot that enables to monitor pseudo-SSH activities. There is a range
of readily available honeypots, such as Kippo or Cowrie, which are designed to
emulate a vulnerable SSH system and attract attackers [85]. The problem lies
that those honeypots are not able to mimic perfectly a real system, which
makes them easy to detect by experienced attackers. As stated by [86]: The
ability to collect meaningful malware from attackers depends on how the
attackers receive the honeypot. Most attackers fingerprint targets before they
launch their attack, so it would be very beneficial for security researchers
to understand how to hide honeypots from fingerprinting and trick the
attackers into depositing malware. […] What is certain is that if a cautious
attacker believes they are in a honeypot, they will leave without depositing
malware onto the system, which reduces the effectiveness of the honeypot [86].

There are other approaches that allow to decrypt SSH connections without
relying on a honeypot, like the man-in-the-middle or binary manipulation with
their own set of challenges [1]. Instead of relying on softwares that mimics
or modify a real system, it is possible to use a real unmodified system
directly. The idea is to be able to decrypt SSH connection channels, which is
possible if the SSH keys are known. Since SSH encryption keys are typically
stored in the main memory of a system, it is possible for the administrators
to extract them through the exploitation of memory dumps of a targeted system.
In this context, the ability to detect SSH keys in memory dumps, and
specifically OpenSSH keys, is critical to the development of effective SSH
honeypot-like systems. The research introduced by the SmartVMI project with
SSHKex, SmartKex, the present thesis and the future related work could be used
to develop such a new type of system-monitoring tools. This new kind of tools
would be very difficult to detect by attackers, increasing their
effectiveness, and wouldn’t require the alteration of the system. The present
report is focused on the SSH key detection in memory dumps, which is a key
component allowing to decode SSH communications such that it becomes possible
to intercept malicious communications and to detect malicious activities.

###  1.1 Research Questions

At the very beginning of this thesis, first questions were:

  * •

What is the state of the art in the field of security key detection in heap
dump memory?

  * •

What are the challenges of security key detection in heap dump memory?

  * •

How can the existing methods for detecting SSH keys in OpenSSH heap dumps be
improved?

The SmartVMI project has already made significant progress in the detection of
SSH keys in OpenSSH heap dumps. An open dataset of memory dumps has been
created, and a simple yet effective method for detecting SSH keys has been
developed. The dataset has been used to train and test simple machine learning
algorithms, and the results have been promising. The research has been
published in the form of two papers, SSHkex [1] and SmartKex [10], which is
the basis of this thesis.

However, there is still room for improvement, particularly in the area of
machine learning algorithms. This thesis seeks to build upon the existing
research by refining feature extraction techniques and exploring innovative
methods for effective key detection prediction. The objective is to accurately
predict the presence and location of SSH keys within memory dumps. Rooted in
this context, this Masterarbeit aims to address several key research
questions:

  * •

Memory graph: How can we develop a memory graph representation to improve the
prediction of SSH keys in memory dumps?

  * •

Memory graph embedding: How can we develop a memory graph embedding
representation to improve the prediction of SSH keys in memory dumps?

  * •

Feature importance: What features are most indicative of SSH keys in memory
dumps?

  * •

Feature extraction: How can these features be extracted from memory dumps and
used to train machine learning algorithms?

  * •

ML for key prediction: How can machine learning algorithms be optimized for
the prediction of SSH keys in memory dumps?

  * •

Graph Convolutional Networks for key prediction: How can GCN be used to
improve the prediction of SSH keys in memory dumps, and how does it compare to
traditional machine learning algorithms?

By tackling these research questions, this thesis seeks not only to advance
the academic understanding of SSH key prediction and digital forensics but
also to provide practical insights that could lead to the development of more
secure and effective systems.

###  1.2 Commitment to Open Science and Reproducibility

In alignment with the principles of Open Science, this thesis aims to be not
just a scholarly report but also a comprehensive guide for anyone who wishes
to understand, replicate, or extend the work presented. Open Science is a
movement that advocates for the transparent and accessible sharing of
scientific research, data, and dissemination processes [46]. It is built on
six fundamental principles [45]:

  1. 1.

Open Methodology: Detailed methodologies are provided to ensure that the
experiments can be replicated.

  2. 2.

Open Source: All code used in this research is available for scrutiny and
reuse. As such, all code including the LaTeX code for the present report
111The present report repository can be found here:
https://github.com/0nyr/masterarbeit_report is properly documented and can be
accessed on GitHub.

  3. 3.

Open Data: Raw data and the data processing techniques are made publicly
available.

  4. 4.

Open Access: The research is published in a manner that is free for all to
read and download.

  5. 5.

Open Peer Review: The peer review process is transparent. In the case of this
Masterarbeit, the research is reviewed by the supervisors of the project.

  6. 6.

Open Educational Resources: Any educational content produced is shared openly.

To ensure the highest level of reproducibility and accessibility, this thesis
includes what might seem like exhaustive details, such as hardware or software
specifications, precise shell commands and some code implementations used
during the research. These are included to provide a complete picture and to
minimize the friction for those who wish to replicate the experiments,
whatever their level of expertise may be. By adhering to the principles of
Open Science, this thesis aims to contribute to a more transparent,
collaborative, and efficient scientific community.

####  1.2.1 GitHub Repositories

In the context of the present Masterarbeit, a number of GitHub repositories
have been created to facilitate the sharing of code and data. These
repositories are listed below:

  * •

masterarbeit_report_onyr: Repository containing the LaTeX code for the report
as well as several scripts related to dataset exploration:
https://github.com/passau-masterarbeit-2023/masterarbeit_report_onyr

  * •

mem2graph: Memory graph creation utility built in Rust, featuring different
graph creation and embedding strategies. Collaboration with Clément Lahoche:
https://github.com/passau-masterarbeit-2023/mem2graph

  * •

research-base: Custom Python framework for developing programs that include
all the basics of a research project, such as logging, environment and
argument loading, result keeping, and more. Collaboration with Clément
Lahoche: https://github.com/0nyr/research-base

  * •

data_processing: Python program for data processing and machine learning for
SSH key prediction. This repository contains tests on machine learning model
training and evaluation for classical .csv based embedding files from
mem2graph: https://github.com/passau-masterarbeit-2023/data_processing

  * •

phdtrack_project_3: Legacy repository containing the first version of the
memory graph creation utility and the first version of the dataset creation
script. Collaboration with Clément Lahoche.
https://github.com/0nyr/phdtrack_project_3

  * •

memory_graph_gcn: Main Python program and scripts around GCN for SSH key
prediction. This program leverages the modified DOT file with embedding
generated by mem2graph: mem2graph: https://github.com/passau-
masterarbeit-2023/memory_graph_gcn

  * •

phdtrack_server_scripts: Scripts for the servers used for computing
experiments. This repository contains the scripts used to install the
necessary tooling and run the experiments on the different servers we used.
Collaboration with Clément Lahoche: https://github.com/passau-
masterarbeit-2023/phdtrack_server_scripts

####  1.2.2 Datasets

All datasets used in this research are publicly available and can be accessed
on the Zenodo. The datasets are organized in the following manner:

  * •

Original Heap Dumps Dataset: This is the raw dataset used for the research and
produced by the SmartKex team [1]. It contains the original heap dumps in the
form of -heap.raw files with .json annotation files. The dataset is available
here: https://zenodo.org/records/6537904.

  * •

Cleaned Heap Dumps Dataset: This dataset contains heap dumps with annotation
files but has been parsed as described in section 3.2. The dataset is
available here: https://doi.org/10.5281/zenodo.10514199.

As one can see, and considering the collaborative work effort that has been,
it has been decided to regroup all repositories related to the OpenSSH heap
dump exploration in a single GitHub organization, passau-masterarbeit-2023
https://github.com/passau-masterarbeit-2023.

###  1.3 Structure of the Thesis

The present thesis is organized in a manner that ensures a coherent and
logical flow of information, following the standard structure of a
Masterarbeit report. The structure is designed to gradually guide the reader
from understanding the context and background of the research to the
intricacies of the methods employed, and finally to the interpretation of the
results. Below is a breakdown of each section:

  * •

Background Section: This section serves as an introduction to the research
context and establishes the foundation for the thesis. It outlines the
previous work and state of the art, providing the reader with an understanding
of existing knowledge and identifying gaps that this research aims to address.
Key concepts, terminologies, and theories relevant to the study are
introduced, setting the stage for the subsequent sections.

  * •

Methods Section: This section meticulously describes the methods and
approaches employed during the research. From the creation of the dataset to
the selection and implementation of machine learning algorithms, this section
ensures that the research process is transparent and reproducible.

  * •

Results Section: The results’ section presents the data obtained from the
experiments conducted, outlining both the layout of programs used and the raw
results. It provides a factual account of the findings without delving into
interpretation or discussion.

  * •

Discussion Section: This section offers an analysis and interpretation of the
results obtained. It explores the implications of the findings, discusses the
limitations of the study, and contextualizes the results within the broader
research landscape.

  * •

Conclusion: The concluding section succinctly recall the salient points of the
thesis. It underscores the contributions made to the field and suggests
avenues for future research, providing a fitting closure to the report.

In structuring the thesis in this manner, the intention is to provide the
reader with a comprehensive yet accessible insight into the research
undertaken all along this year-long project.

## 2 Background

This section is dedicated to the background information needed to understand
the work developed in the thesis. It provides the necessary context for the
research, including the problem being solved, why it’s important, and the
related state-of-the-art and background information. It also includes
fundamental concepts and theories, terminology definitions, and a high-level
overview of the problem domain. Likewise, it serves as a primer to the rest of
the report, providing the necessary context for the research and is intended
for readers who may not be experts in the specific area of the research but
have some knowledge of the broader field.

###  2.1 SSH and OpenSSH Implementation

####  2.1.1 Basics of the Secure Shell Protocol (SSH)

The Secure Shell Protocol, commonly known as SSH, is designed to facilitate
secure remote login and other secure network services over insecure networks.
SSH has been designed since its inception with security in mind, as a
successor of the Telnet protocol, which is not secure, and other unsecured
remote shell protocols such as rlogin, rsh and rexec [1].

#####  2.1.1.1 SSH design and origin

As stated by the authors of the [77], The founder of SSH, Tatu Ylönen,
designed the first version of the SSH protocol after a password-sniffing
attack at his university network. Tatu released his implementation as freeware
in July 1995, and the tool quickly gained in popularity. Towards the end of
1995, the SSH user base had grown to 20,000 users in fifty countries. By 2000,
there were an estimated 2,000,000 users of the protocol. Today, more than 95%
of the servers used to power the Internet have SSH installed in them. The SSH
protocol is truly one of the cornerstones of a safe Internet. [77].

SSH is defined in [68] [68]. It is divided into three major components:

  * •

Transport Layer Protocol: This provides server authentication,
confidentiality, and integrity. It can also optionally provide compression.
Typically, the transport layer runs over a TCP/IP connection but can also be
used on top of any other reliable data stream.

  * •

User Authentication Protocol: Running over the transport layer, this protocol
authenticates the client-side user to the server. Multiple methods of
authentication such as password and public key are supported.

  * •

Connection Protocol: This multiplexes the encrypted tunnel established by the
preceding layers into several logical channels. Channels can be used for
various purposes, such as setting up secure interactive shell sessions or
tunneling arbitrary TCP/IP ports.

The client sends a service request once a secure transport layer connection
has been established. A second service request is sent after user
authentication is complete. This allows new protocols to be defined and
coexist with the protocols listed above [68].

#####  2.1.1.2 SSH keys

For the purposes of this Masterarbeit, a comprehensive understanding of SSH’s
key exchange and encryption mechanism is important. As outlined in SSHKex [1],
the SSH protocol utilizes a key exchange procedure that culminates in a
derived master key $K$ and a hash value $h$. These components are pivotal for
encrypting client-server communications and identifying sessions.

During the key exchange process, Diffie-Hellman is employed to negotiate an
ephemeral shared key between the client and the server [68] [67]. The Diffie-
Hellman key exchange is a method of securely exchanging cryptographic keys
over a public channel. Proposed by Whitfield Diffie and Martin Hellman in
1976, this protocol is one of the first practical implementations of public
key exchange. The fundamental principle behind Diffie-Hellman is the
difficulty of solving discrete logarithm problems [38]. This ephemeral key is
then signed by the server using either RSA, DSA, or another suitable signature
algorithm (see 2.1.2.2). The signed key confirms to the client that the
negotiated key is indeed from the intended server and not an imposter or a
middleman, thereby preventing man-in-the-middle (MITM) attacks.

In addition, the host key of the server is used to sign the Diffie-Hellman
parameters. This key is not to be confused with the client key listed in the
server’s authorized_keys file, which is used later for client authentication.

The key exchange process results in multiple session keys computed for various
purposes:

  * •

Initialization Vectors: Key A and Key B are designated for initialization
vectors from the client to the server and vice versa.

  * •

Encryption Keys: Key C and Key D act as encryption keys for client-to-server
and server-to-client communications, respectively.

  * •

Integrity Keys: Key E and Key F are utilized to preserve the integrity of data
transmitted between the client and server.

This approach provides forward secrecy: if the private key is stolen, it does
not compromise the encryption of old sessions. This is because the Diffie-
Hellman parameters are ephemeral and discarded once they are no longer needed.
Therefore, the only long-lasting keypair is used for authentication purposes.

#####  2.1.1.3 SSH key encryption

These keys are computed using hash functions that take the master key K and a
hash value H, a unique letter (A, B, C, D, E, or F), and the session ID as
inputs. This is summarized in [70]: The equations used for deriving the above
vectors and keys are taken from RFC 4253 [69]. In the following, the $||$
symbol stands for concatenation, K is encoded as mpint, $K$ is already a
number (hash), $"A"$ as byte and $session_{i}d$ as raw data. Any letter, such
as the $"A"$ (in quotation marks) means the single character A, or ASCII 65.

  * •

Initial IV client to server: $HASH(K||H||"A"||session_{i}d)$.

  * •

Initial IV server to client: $HASH(K||H||"B"||session_{i}d)$.

  * •

Encryption key client to server: $HASH(K||H||"C"||session_{i}d)$.

  * •

Encryption key server to client: $HASH(K||H||"D"||session_{i}d)$.

  * •

Integrity key client to server: $HASH(K||H||"E"||session_{i}d)$.

  * •

Integrity key server to client: $HASH(K||H||"F"||session_{i}d)$.

[70]. Details about the hash function are given in the next section.

The most interesting keys are the encryption keys, as they are used to encrypt
the communication between the client and the server. The other keys are used
for integrity checks and initialization vectors. Decrypting encrypted SSH
communication necessitates either to retrieve these session keys and variables
so as to recompute the keys, or to retrieve those keys directly, which is the
focus of this Masterarbeit.

####  2.1.2 OpenSSH Implementation

OpenSSH (OpenBSD Secure Shell) is an open-source implementation written in C
of the SSH protocol suite, and it is the most widely used SSH implementation
[70]. It is the default SSH implementation on most Linux distributions, and it
is also available for Windows. OpenSSH is used for a wide range of purposes,
including remote command-line login and remote command execution. It is also
used for port forwarding, tunneling, and transferring files via SCP and SFTP
either manually or via automated processes, such as backup systems,
configuration management tools, and automated software deployment tools.

#####  2.1.2.1 OpenSSH components

OpenSSH is composed of several tools and daemons, including client and server
components [74]:

  * •

ssh: The basic client program that allows to log into and execute commands on
a remote machine.

  * •

sftp: An interactive file transfer program that uses SSH to secure the
connection.

  * •

sshd: This is the SSH daemon that runs on the server. This is used for
connecting to a remote machine when using the SSH client from another system.

  * •

ssh-agent: The program that holds private keys in memory, so one doesn’t have
to enter one’s passphrase every time.

  * •

ssh-add: A program for adding RSA or DSA identities to the authentication
agent.

  * •

ssh-keygen: A utility for creating and managing SSH keys.

  * •

ssh-keyscan: A utility for gathering public SSH host keys from a number of
hosts.

  * •

ssh-keychk: A utility for checking the validity of SSH keys.

  * •

Several other tools to support the SSH protocol and the OpenSSH
implementation.

#####  2.1.2.2 OpenSSH hashing

OpenSSH employs a variety of hash functions and algorithms to secure data,
most commonly using SHA1. However, SHA1 is increasingly seen as weak due to
its vulnerability to collision attacks [70]. In light of this, the
contemporary standard leans towards SHA512. The hash functions are used
alongside cipher algorithms like Advance Encryption Standard (AES) Cipher
Block Chaining (CBC), AES Counter (AES-CTR), and ChaCha20 [10]. The Message
Authentication Code (MAC) typically uses either MD5 or SHA1 hash algorithms in
combination with a secret key. Since cybersecurity and cryptography are
constantly evolving, so do SSH and OpenSSH. Depending on the version [70], the
available hash options include:

  * •

ssh-dss: (disabled at run-time since OpenSSH 7.0 released in 2015) SSH-1
version using Digital Signature Algorithm (DSA) from the Digital Signature
Standard (DSS). Originally popular but phased out due to vulnerabilities to
collision attacks for DSA Key in a 1024-bit modulus. As stated by [11]: These
attacks are still computationally very difficult to perform, but it is
desirable that any key exchange using SHA-1 be phased out as soon as possible
[11] [18].

  * •

ssh-rsa: (disabled at run-time since OpenSSH 8.8 released in 2021) It refers
to the use of RSA (Rivest-Shamir-Adleman) encryption algorithm. In the context
of SSH-1, this version had to be replaced due to the related to key size issue
similar to DSS: RSA 1024-bit keys have approximately 80 bits of security
strength… which may not be sufficient for most users. [11] [23].

  * •

ecdsa-sha2-nistp256: (since OpenSSH 5.7 released in 2011) Uses the SHA-2
family for hashing and the NIST P-256 curve. It is considered secure and
efficient, with an Estimated Security Strength (ESS)of 128 bits [11] [15].

  * •

ecdsa-sha2-nistp384: (since OpenSSH 5.7) Utilizes the SHA-2 family and the
larger NIST P-384 curve for additional security at the cost of performance. It
has an ESS of 192 bits [11] [15].

  * •

ecdsa-sha2-nistp521: (since OpenSSH 5.7) Employs SHA-2 and the even larger
NIST P-521 curve for maximal security with an ESS of 256 bits [11]. It is less
commonly used due to performance considerations [15].

  * •

ssh-ed25519: (since OpenSSH 6.5 released in 2014) Known for high security and
performance efficiency; employs the Ed25519 elliptic curve with an ESS of 128
bits [11] which is similar to $ecdsa-sha2-nistp256$, and has been more
prevalent following the 2013 suspicions of NSA backdoors in NIST curves [14]
following the Snowden revelations [12] [13] [17].

  * •

rsa-sha2-256: (since OpenSSH 7.2 released in 2016) An upgrade from ssh-rsa,
using SHA-256 (with ESS of 128 bits) for hashing to improve security without
major performance hits [21].

  * •

rsa-sha2-512: (since OpenSSH 7.2) Similar to $rsa-sha2-256$ but employs
SHA-512 for even stronger security, albeit with some performance cost [21].

  * •

ecdsa-sk: (since OpenSSH 8.2 released in 2020) Security Key-enabled, uses NIST
curves and is geared towards modern hardware-based authentication [22].

  * •

ed25519-sk: (since OpenSSH 8.2) Similar to ssh-ed25519 but integrates
hardware-based Security Keys for an additional layer of security [22].

  * •

NTRU Prime-x25519: (since OpenSSH 9.0) A new, highly secure algorithm focused
on post-quantum cryptography, providing future-proof security [71] [66].

These hashes have fixed lengths such that key lengths range between 12 and 64
bytes [10]. Since high-quality random number generation is crucial to ensure
that those keys are secure and difficult to predict, it can thus be assumed
that those key have a high entropy [73]. This is a crucial assumption as it is
the basis for the use of both brute force and machine learning algorithms to
predict the presence and location of SSH keys in memory dumps.

The keys generated by these hash functions are pseudo-random numbers stored in
the system’s RAM. Following the Kerckhoffs’ principle: that a cryptosystem
should be secure, even if everything about the system, except the key, is
public knowledge, the code for the OpenSSH implementation is open-source and
available on GitHub [74]. This allows for the analysis of the code and the
identification of the memory structures where the keys are stored.

####  2.1.3 The state of SSH security

Since its origins, SSH has been developed with cybersecurity in mind, and is
generally considered a secure method for remote login and other secure network
services over an insecure network. However, as with any technology, it can be
exploited if not configured or managed correctly. The protocol is used by
system administrators to manage remote systems, and it is also used by
automated processes to transfer data and perform other tasks. This makes SSH a
valuable target for attackers. In fact, SSH has been a popular target for
cyber-attacks. Due to being so prevalent, it is often used by threat actors
either as a vector for initial access, as a means to move laterally across a
network or as a covered exit for exfiltration of sensitive data [84]. The
encrypted nature of its communications makes it an attractive option for
attackers, as it can be difficult to detect malicious activity.

#####  2.1.3.1 SSH security issues

Here are some cases where SSH can involve in cyber-attacks, although it’s
important to note that SSH itself is not inherently insecure:

  * •

SSH Brute-Force Attacks: One of the most common types of attacks involving SSH
is a brute-force attack, where an attacker tries to gain access by repeatedly
attempting to log in with different username-password combinations. These
attacks are not sophisticated but can be effective if strong authentication
measures are not in place. For instance, the botnet Chabulo was used to launch
a large-scale brute-force attack through compromised SSH servers and IoT
devices in 2018 [77].

  * •

SSH Key Theft: In some advanced attacks, threat actors have stolen SSH keys to
move laterally across a network after initial entry. This allows them to
authenticate as a legitimate user and can make detection much more
challenging. It can occur when users have their SSH password or unencrypted
keys stolen through a variety of methods (sniffed via a key-logging console
program, shoulder-surfed via bad security awareness, poor key management
practices, etc.). [78].

  * •

Man-in-the-Middle Attacks: Although SSH is designed to be secure, it can be
susceptible to man-in-the-middle attacks if proper verification of SSH keys is
not done during the initial connection setup [70].

  * •

Misconfiguration: As with any technology, misconfiguration can lead to
security issues. For example, leaving default passwords, using weak encryption
algorithms, or enabling root login can all make an SSH-enabled system
vulnerable [76].

#####  2.1.3.2 SSH vulnerabilities

In cybersecurity, it is generally considered that any system that is connected
to the Internet will be attacked at some point. Similarly, it is a common
saying that no system is 100% secure. This is true for SSH as well. Although
it is a secure protocol, it can be exploited if not configured or managed
correctly.

Some vulnerabilities have also been discovered in the protocol itself,
although these are rare.

  * •

SSH-1 Vulnerabilities: A series of vulnerabilities in the first implementation
of SSH were discovered from 1998 to 2001, with its subsequent fixes leading to
unauthorized content insertion and arbitrary code execution. SSH-1 had many
design flows and is now considered obsolete. [80], [79].

  * •

CBC Plaintext Recovery: A theoretical vulnerability discovered in 2008
affecting all versions of SSH, allowing the recovery of up to 32 bits of
plaintext from CBC-encrypted ciphertext [81].

  * •

Suspected Decryption by NSA: Leaked information in 2014 suggested that the NSA
might be able to decrypt some SSH traffic, although the protocol itself was
not confirmed to be compromised [82].

#####  2.1.3.3 SSH and cyber-attacks

SSH has been used in many high-profile cyber-attacks and malwares, including
the following:

  * •

Operation Windigo: This was a large-scale campaign that infected over 25,000
UNIX servers. SSH was one of the vectors used for maintaining control over
compromised servers. A report by ESET mentions that the OpenSSH backdoor
Linux/Ebury was first discovered in 2011 as a component of the aforementioned
operation. This operation has been ongoing since at least 2011 and has
affected high profile servers and companies, including cPanel - the company
behind the famous web hosting control panel - and Linux Foundation’s
kernel.org - the main repository of source code for the Linux kernel [83].

  * •

Linux/Hydra: Initially unleashed in 2008, this malware is a fast login cracker
that targets a range of popular protocols including SSH. Hence, SSH is one of
its primary vectors to gain initial access to Internet of Things (IoT)
devices. Once a device is infected by Linux/Hydra, it joins an IRC channel and
initiates a SYN Flood attack [85].

  * •

Psyb0t: Discovered in early 2009, Psyb0t is an IRC-controlled malware
specifically designed to target devices with MIPS architecture, such as
routers and modems. Notably, it was responsible for orchestrating a DDoS
attack against the DroneBL service, infecting up to 100,000 devices for this
purpose. The malware is equipped to conduct UDP and ICMP flood attacks and
employs a brute-force attack mechanism against Telnet and SSH ports.
Remarkably, it uses a pre-configured list of 6,000 usernames and 13,000
passwords to perform these attacks [85].

  * •

Chuck Noris: Similar to Psyb0t in its objectives and methods, Chuck Noris
targets routers and DSL modems, focusing on SoHo (small office/home office)
devices. However, unlike Psyb0t, which uses ICMP flood attacks, Chuck Noris
deploys ACK flood attacks. The malware carries out brute-force attacks on
Telnet and SSH open ports, drawing parallels to the tactics employed by Psyb0t
but with the specific variation in flooding techniques [85].

It’s worth noting that in many of these cases, SSH was not the initial attack
vector but was used at some stage in the attack lifecycle. Properly configured
and managed SSH is still considered a secure and robust protocol for remote
access and data transfer. In all those situations, a tool monitoring the SSH
traffic could have detected the malicious activities and prevented the attack.

####  2.1.4 The Imperative of SSH Honeypots in Cybersecurity Monitoring

SH (Secure Shell) has become an indispensable protocol for secure
communication but can also conceal malicious agents. This reality underscores
the urgency for robust monitoring mechanisms capable of identifying suspicious
activities in real-time. Among various countermeasures, SSH honeypots have
emerged as a particularly effective tool for monitoring and gathering
intelligence on potential threats.

An SSH honeypot is a decoy server or service that mimics legitimate SSH
services. The primary aim is to attract cybercriminals and study their
tactics, thereby offering an active form of surveillance and data collection.
Unlike traditional intrusion detection systems, honeypots do not merely
identify an attack; they engage the attacker in a controlled environment,
enabling detailed observation and logging of the intruder’s actions. This
allows for the collection of valuable information, such as the attacker’s IP
address, the tools used, and the techniques employed. This data can then be
used to enhance security measures and develop more robust countermeasures
[85].

SSH honeypots serve as an invaluable asset in the cybersecurity arsenal,
providing not just a reactive but a proactive measure against evolving cyber
threats. They can collect actionable intelligence on new hacking methods,
malware, and exploitation scripts. This information can be crucial for
proactively securing actual production environments. The data collected can
also be used to trace back to the origin of the attack, facilitating legal
pursuits against the perpetrators. By diverting attackers to decoy servers,
honeypots also protect real assets from being targeted, saving both
computational resources and administrative effort needed for post-incident
recovery.

Popular SSH honeypots include Kippo, Cowrie, and HoneySSH. Cowrie is a fork of
Kippo, with additional features such as logging of attacker’s keystrokes and
file transfer.

  * •

Kippo: Kippo is a medium-interaction honeypot that logs the attacker’s shell
interaction. It specializes in capturing brute force and Telnet-based attacks
[85].

  * •

Cowrie: Serving as Kippo’s successor, Cowrie emulates various protocols
including SSH, SFTP, and SCP. It logs events in JSON format, making it
particularly useful for detecting brute force and Telnet-based attacks, as
well as spoofing attacks [85].

  * •

IoTPOT: This IoT-focused honeypot supports multiple CPU architectures and can
detect a variety of attacks including brute force, DoS, and sniffing attacks
on Telnet, SSH, and HTTP ports [85].

  * •

HoneySSH: HoneySSH is a low-interaction honeypot that emulates an SSH server
and logs the attacker’s IP address, username, and password [87].

  * •

Sarracenia (SSHKex): Introduced in 2018, Sarracenia is a high-interaction SSH
honeypot that has been enhanced by SSHKex. Instead of requiring the VM to be
paused for every incoming or outgoing packet, which degrades the server
performance [1], SSHKex allows for the extraction of derived SSH session keys.
This reduces the performance degradation significantly, as the VM is paused
less frequently [1] [16].

These honeypots are useful tools for gathering intelligence on potential
threats. However, they are not without their limitations.

####  2.1.5 Research context and motivation for this Masterarbeit

Security and malware detection are active areas of research, with SSH
honeypots being a particularly promising tool for gathering intelligence on
potential threats. However, they are not without their limitations. For
instance, they are not able to perfectly mimic a real system, such that
attackers might be able to detect them [86].

As explained in [86]: As attackers become more sophisticated with their
ransomware and malware campaigns, there is a significant need for security
researchers to assist the greater community by running vulnerable honeypot
machines to collect malicious software. [86] explain that the ability to
collect meaningful malware from attackers depends on how the attackers receive
the honeypot. Most attackers fingerprint targets before they launch their
attack, so it would be very beneficial for security researchers to understand
how to hide honeypots from fingerprinting and trick the attackers into
depositing malware. They conclude that What is certain is that if a cautious
attacker believes they are in a honeypot, they will leave without depositing
malware onto the system, which reduces the effectiveness of the honeypot for
security research. We can extrapolate this conclusion to SSH honeypots, which
are also vulnerable to fingerprinting and detection by attackers.

Hence, the need for more advanced SSH honeypots-inspired tools that can
leverage data forensic and machine learning techniques so as to be able to use
directly a real server as a honeypot, without the need to emulate a system.
The current master’s thesis is aligned with this ongoing research (see 2.2),
further enhancing the state of SSH honeypots. It aims to develop algorithms,
proof of concepts and tools that can extract SSH keys from memory dumps of a
real server, and use them to decrypt SSH traffic. This could lead to the
development of new tools for SSH monitoring, as discussed in the future work
section 6.2.

###  2.2 Previous Work on OpenSSH key extraction

Now that the necessary context has been established, this section will present
the related work in the field of machine learning for memory forensics in the
context of OpenSSH. It is divided into two parts. The first part will present
the related work in the field of memory forensics, and the second part will
present the related work in the field of machine learning for memory
forensics.

####  2.2.1 SSHKex

SSHKex is a research project that aims to address the challenges of analyzing
encrypted SSH traffic by leveraging Virtual Machine Introspection
(VMI)techniques. Developed by [1], the project focuses on extracting SSH keys
and decrypting SSH network traffic in a stealthy, non-intrusive manner while
maintaining evidence integrity [1]. This paper is itself a continuation of the
work presented in [16] [16], which introduced Sarracenia, a high-interaction
SSH honeypot. It is also related to a range of other research projects and
papers [1, section 5.6 and 6].

The SSHKex approach combines standard network traffic capturing methods with
dynamic SSH session key extraction. It assumes that the SSH implementation
running on the server is known, which is crucial for the key extraction
process. The project employs VMI tools like LibVMI and Volatility to gain a
complete and untainted view of all guest VM’s state information. This allows
to efficiently locate SSH session keys in the main memory of a Linux machine.

Here is a summary of the SSHKex methodology for key extraction:

  1. 1.

Data Structure Information: The method leverages detailed knowledge about the
data structures used to store the keys. Specific debugging symbols
corresponding to the SSH implementation version on the target system provide
essential offset values to facilitate the extraction of key material. The
structures of interest include struct ssh, struct session_state, struct
newkeys, and struct sshenc. These structures store a range of information such
as IP addresses, ports, session states, and encryption keys.

  2. 2.

Tracing OpenSSH Functions: Function tracing is employed to identify the
precise locations of data structures and to extract keys at the right time.
The focus is on two key functions: kex_derive_keys (which initiates key
generation) and do_authentication2 (which kicks off user authentication).

  3. 3.

Breakpoints Injection: Software breakpoints are intentionally placed in the
program execution to facilitate debugging. SSHKex utilizes Virtual Machine
Introspection (VMI) to inject these breakpoints at the initial points of the
two aforementioned key functions.

  4. 4.

Key Extraction: Upon calling the kex_derive_keys function, SSHKex initially
stores the address of the ssh struct. The actual keys are extracted from
memory when the do_authentication2 function is subsequently called, adhering
to the known structures.

  5. 5.

Key Indexing: OpenSSH stores client-to-server and server-to-client keys in
distinct indices of the newkeys structure. SSHKex extracts keys based on these
specific indices.

  6. 6.

Handling Multiple Connections: To manage multiple SSH connections, OpenSSH
spawns child processes. SSHKex extends its key extraction strategy to each
child process by identifying them through their unique process IDs.

One of the key strengths of SSHKex is its focus on stealthiness, preservation,
and evidence integrity. The approach aims to be as unobtrusive as possible,
avoiding any modifications to the system under investigation. This is
particularly important in forensic contexts, where the integrity of the
evidence is crucial [1].

####  2.2.2 SmartKex

SmartKex is a direct followup project that focuses on the extraction of SSH
keys from heap memory dumps. Its primary objective is to automate the process
of SSH key extraction from heap memory dumps. The project introduces a machine
learning-assisted methodology that significantly improves the efficiency and
accuracy of key extraction compared to traditional brute-force methods. This
method is also significantly more straightforward to implement compared to the
previous SSHKex approach, which requires detailed knowledge of the SSH
implementation and the ability to inject breakpoints into the program
execution.

SmartKex discusses two distinct methods for SSH key extraction:

  * •

Brute-Force Baseline Method: This is a traditional approach that scans through
the heap memory to identify potential keys based on known patterns.

  * •

Machine Learning-Assisted Method: This approach uses a Random Forest algorithm
trained on a highly imbalanced dataset using SMOTE balancing. The machine
learning model is designed to identify SSH keys with high precision and recall
rates, but is not exact as compared to the brute-force method since it is
based on a probabilistic model.

#####  2.2.2.1 Baseline brute-force method

Here is a summary of SmartKex’s brute-force method for SSH key extraction from
heap dumps [10]:

  1. 1.

Heap Dump Generation: Heap dump binary files of OpenSSH server process have
been generated (ASK HOW) and serves as the input for the key extraction
process. The exact process and architecture is not described in SmartKex
paper, but we suppose it was done on a linux-x86_64 architecture.

  2. 2.

Data Reduction: To minimize the heap size, the method removes memory pages
that are irrelevant (empty) based on Hamming distance.

  3. 3.

Brute-force key search: Starting from the first byte, a key length of 128
bytes is taken from the heap dump as the potential key. The algorithm iterates
over the entire heap, continuously updating the potential key until the heap’s
end is reached.

  4. 4.

Decryption Attempt: For every potential key, an attempt is made to decrypt
network packets. If decryption fails, the process is repeated with a new
potential key.

Although the brute-force approach is exact, it is computationally expensive.
It performs poorly especially when keys are located at the end of the heap
dump [10, section 6.2].

#####  2.2.2.2 SmartKex machine-learning method

The real innovation of SmartKex is its machine learning-assisted methodology
for SSH key extraction. At the cost fo exactness, this approach is
significantly faster than the brute-force method and has a high degree of
accuracy in identifying encryption keys. It also allows for the heap size to
be reduced to less than 2% of its original size, further optimizing the
extraction process.

Here is a summary of SmartKex’s machine learning-assisted method for SSH key
extraction from heap dumps [10]:

  1. 1.

Heap Dump inputs: Similarly to the brute-force method, heap dump binary files
of OpenSSH also serve as inputs for the key extraction process.

  2. 2.

Preprocessing: The raw heap dump is resized into an $N\times 8$ matrix. High
entropy parts of the heap dump, which are likely to be encryption keys, are
identified using the logical AND operation on the vertical and horizontal
differences of adjacent bytes. This creates an array that flags potential key
locations.

  3. 3.

Training: A Random Forest algorithm is trained on 128-byte slices of the
preprocessed heap. The dataset is imbalanced, with the slices that contain
keys being rare. A stacked classifier approach is used, comprising a high
precision classifier and a high recall classifier.

  4. 4.

Key Identification: The machine learning model is used to predict which
128-byte slices of the heap dump are likely to contain encryption keys. These
slices are then subjected to a brute-force method to actually extract the
keys.

SmartKex is significantly faster than the brute-force method alone and has a
high degree of accuracy in identifying encryption keys. It also allows for the
heap size to be reduced to less than 2% of its original size, further
optimizing the extraction process.

SmartKex has broad applications in the field of cybersecurity, particularly in
memory forensics. Its machine learning-assisted methodology can be adapted for
other types of sensitive data extraction, making it a versatile tool for
researchers and practitioners alike. The project is open-source, with the code
available on GitHub111https://github.com/smartvmi/Smart-and-Naive-SSH-Key-
Extraction.

####  2.2.3 Objectives of the present work

This Masterarbeit can be seen as a direct followup to the paper [10]. The
present work aims to improve the SmartKex methodology by exploring new machine
learning architectures and algorithms. The goal is to improve the accuracy of
the machine learning model and to reduce the computational complexity of the
overall process.

To do so, this work has significantly broadened the research area by exploring
entirely new ways to deal with the dataset by leveraging memory graph
representation, feature engineering, new machine learning and deep learning
model architectures, and new training strategies. A range of different tools
and script, with a focus on code quality and reproducibility with careful
packaging using Nix ensure that the present research can be easily extended
and reproduced by other researchers.

###  2.3 Graph-based memory modelization

In the following section, we present important concepts that will be used for
the memory modelization of the heap dump.

Because the dataset used is composed of RAW heap dump files from OpenSSH, it
is a critical aspect to understand how memory works at a low level point of
view. This section aims to provide an in-depth understanding of how memory is
managed in C, the language used in the OpenSSH implementation of SSH, for a
linux-x86_64 architecture. We will explore the fundamental concepts of memory
management, including the heap and the stack, memory allocation, and the role
of pointers. These concepts will serve later as the foundation for our graph-
based approach to memory modelization.

This section will also introduce many graph theory and Knowledge Graph
(KG)concepts. We will explore the fundamentals of graph theory, including the
definition of a graph, its components, and its properties. We will also
discuss the concept of a Knowledge Graph (KG), which is a type of graph that
stores information in the form of nodes and edges, and its applications in the
field of machine learning.

####  2.3.1 Defining memory concepts and modelization

Memory management in C is a complex task that requires a deep understanding of
the language’s features, the operating system’s capabilities and the compiler
used. In C, memory is primarily managed through two built-in functions: malloc
(memory allocation) and free (memory deallocation). These functions operate on
two primary types of memory: the heap and the stack.

  * •

Heap vs Stack: The heap is used for dynamic memory allocation, where variables
are allocated and freed at runtime. In contrast, the stack is used for static
memory allocation, where variables are allocated and deallocated
automatically. The stack is faster but has a limited size, while the heap is
more flexible but requires manual management to prevent memory leaks.

  * •

Heap Dump: A heap dump is a snapshot of the heap’s state at a given time. It
provides valuable information about the memory layout, active pointers, and
data stored in the heap. Analyzing heap dumps can help in debugging memory-
related issues and understanding the program’s behavior.

  * •

Memory Addresses: Each location in memory is identified by a unique memory
address. These addresses are usually represented in hexadecimal notation. Note
that the address $0x0$ is reserved for the NULL pointer, which is used to
indicate that a pointer does not point to any memory location.

  * •

Pointer: A pointer is a variable that stores the memory address of another
variable. It is used to indirectly access the value of the variable it points
to. Pointers are used extensively in C, particularly for dynamic memory
allocation.

  * •

Data Structure: A data structure is a collection of data values, the
relationships among them, and the functions or operations that can be applied
to the data. In the context of C programming, data structures are declared
using the keyword struct and are byte aligned. This means that the size of the
data structure is always a multiple of the size of the largest member of the
structure. Structures can be nested within each other, and pointers can be
used to indirectly access the members of a structure. Data structures are
often stored in the heap using malloc.

  * •

Malloc headers: When malloc is called, it allocates a block of memory in the
heap and returns a pointer to the first byte of the block. The heap manager
keeps track of these allocations through metadata, often stored in headers
preceding the allocated blocks. These headers contain information such as the
size of the allocated block and whether it is free or occupied. Note that the
pointer returned by malloc in C points to the first byte of the block of
memory that has been allocated for your use, not to the malloc header. The
malloc header, is managed internally by the memory allocator and is not
exposed to the programmer, but is visible in the heap dump.

#####  2.3.1.1 Endianness

Endianness refers to the byte order used to represent multibyte data types. In
a little-endian system, the least significant byte is stored first, while in a
big-endian system, the most significant byte is stored first. Knowing the
endianness of the system is crucial for interpreting the content of memory
[72].

For instance, the hexadecimal value 0x56343a198000 (taken from "HEAP_START" of
3) is represented as $550179058774$ ($\simeq 5.50e+11$) in decimal basis in a
little-endian system, while it is represented as $94782313037824$ ($\simeq
9.48e+13$) in a big-endian system.

###### Little-Endian Conversion

The conversion of a hexadecimal number in little-endian format to a decimal
number is given by the following formula:

$\text{Decimal}=\sum_{i=0}^{N-1}\left(\text{HexDigit}_{i}\times 16^{i}\right)$

###### Big-Endian conversion

And the conversion of a hexadecimal number in big-endian format to a decimal
number is given by following formula:

$\text{Decimal}=\sum_{i=0}^{N-1}\left(\text{HexDigit}_{N-1-i}\times
16^{i}\right)$

Here, $\text{HexDigit}_{i}$ is the value of the $i$-th digit in the little-
endian hexadecimal number, and $N$ is the number of digits in the hexadecimal
number. Note that $\text{HexDigit}_{i}$ should be converted to its decimal
equivalent (’A’ becomes 10, ’B’ becomes 11, etc.) before performing the
calculation.

These formulas will be used later to convert pointer addresses from
hexadecimal to decimal format in mem2graph.

#####  2.3.1.2 The role of entropy in forensic analysis

Entropy plays a pivotal role in forensic analysis, particularly in the context
of memory dumps analysis. It serves as a measure of uncertainty and
randomness, which can be crucial for tasks such as endianness detection and
identifying encrypted keys in memory.

As defined by Shannon in the realm of information theory, it is a measure of
the uncertainty or randomness associated with a set of possible outcomes [72]
[26]. In digital applications, when calculated using the logarithm to base 2,
entropy represents the amount of bits of information in a message.

###### Entropy Formula

The entropy $H$ of a message is calculated using the formula:

$H=-\sum_{i=1}^{n}p_{i}\log_{2}p_{i}$

Where $p_{1},p_{2},\ldots,p_{n}$ are the probabilities of the set of all
possible messages [72].

Endianness, as presented before, refers to the byte order used to represent
multibyte data types in computer memory [72]. It is necessary to know the
endianness of the heap dump to correctly interpret the content of memory, and
especially the addresses of potential pointers. In this context, entropy can
be used to infer the endianness of a system by analyzing the distribution of
byte values in a memory dump, as presented in [72] [72].

Entropy is also a key element for encryption key detection, since those should
be random byte sequences with high entropy [10]. By examining 8-byte aligned
data for high entropy, it is possible to detect potential keys in a heap dump.
Techniques such as the calculation of discrete differences and logical
operations can further refine this detection as described in [10] [10].

####  2.3.2 Graphs and Knowledge Graphs

In this project, we (i.e. Clément Lahoche and the author) have built a program
called mem2graph, a generic tool developed in Rust for efficiency. It is used
to convert a RAW memory dump into a graph representation. This graph is
technically a directed Edge-labeled heterogeneous property graph, whose
concepts are described later. As such, and while it is debatable whether or
not mem2graph can be seen as building Knowledge Graphs (KGs), it relies on
many concepts from the domain, necessitating a proper introduction.

#####  2.3.2.1 Defining Graph Theory concepts

Graph theory is a mathematical field concerned with the study of graphs. It
has applications in various fields, including computer science, social
sciences, or linguistics. Graphs are used to model pairwise relations between
objects, and the study of graphs involves analyzing the properties of these
relations. In a few words, a graph is just a collection of nodes and edges.

A graph can be formally defined as: a pair $G=(S,A)$ where:

  * •

$S$ is a finite set of vertices.

  * •

$A$ is a set of pairs of vertices $(s_{i},s_{j})\in S^{2}$.

Graphs can be either directed or undirected. In a directed graph, the pairs
$(s_{i},s_{j})$ are ordered, representing arcs from $s_{i}$ to $s_{j}$. In an
undirected graph, the pairs are unordered, representing edges between $s_{i}$
and $s_{j}$ [19]. Let’s introduce some vocabulary to describe graphs:

  * •

Node (or Vertex): A single entity in the graph, often represented as a circle.

  * •

Edge (or Arc): A connection between two nodes, often represented as a line or
arrow.

  * •

Degree: The number of edges connected to a node.

  * •

Path: A sequence of edges that connect two nodes.

  * •

Cycle: A path that starts and ends at the same node.

  * •

Order: The number of vertices in the graph.

  * •

Adjacency: Two nodes are adjacent if there is an edge between them.

  * •

Loop: An edge that connects a node to itself.

  * •

Weight: A value assigned to an edge.

  * •

Ancestors (parents) and Descendants (children): A node $s_{i}$ is an ancestor
of $s_{j}$ if there is a path from $s_{i}$ to $s_{j}$. A node $s_{j}$ is a
descendant of $s_{i}$ if there is a path from $s_{i}$ to $s_{j}$.

Various other terminologies and concepts exist in graph theory, but these are
the most important ones for our purposes. For a more in-depth understanding of
graph theory, the reader is encouraged to consult the work by [19] as a quick
introduction, [19] or a more in-depth one by [20] [20].

#####  2.3.2.2 Graphs types

Graphs offer a flexible way to conceptualize, represent, and integrate diverse
and incomplete data. Many graph models exist, each with its own advantages and
disadvantages, as well as graph properties 222Some parts of the following
section are directly from a prior work for Seminar 5369S: Knowledge Graphs,
written during summer 2023. As of the date of writting and to the best of my
knowledge, this work has not been published, and as such, cannot be properly
referenced. Those different types of graphs include:

  * •

Directed Edge-labelled Graphs (DEL): The classic graph, set of nodes and edges
that connect the nodes with in certain way. RDF is a popular DEL data model.

  * •

Heterogeneous Graphs: Each node and edge is assigned one type, allowing for
partitioning nodes according to their type, which is useful for machine
learning.

  * •

Property Graphs: Allows a set of property-value pairs and a label to be
associated with nodes and edges. This model is used in Neo4j and offers great
flexibility but is harder to handle and query.

  * •

Graph Dataset: A set of named graphs, with a default graph with no ID. Useful
when working with different sources.

  * •

Hypergraphs: Hypergraphs generalize the concept of graphs by allowing edges,
known as hyperedges, to connect any number of nodes, rather than just pairs.
This means that a single hyperedge can link together two or more nodes,
forming a subset of the hypergraph’s node set. This feature makes hypergraphs
particularly useful for modeling relationships in complex systems where
connections are not merely binary. They are widely used in areas such as
database design, combinatorial optimization, and complex network analysis,
where multi-way relationships are prevalent.

A given graph can have a range of properties that give some insights into its
structure. Here are some important properties of graphs:

  * •

Connected Graph: A graph is connected if there is a path between every pair of
nodes.

  * •

Disconnected Graph: A graph is disconnected if there is at least one pair of
nodes that are not connected by a path.

  * •

Cyclic Graph: A graph is cyclic if it contains at least one cycle.

  * •

Acyclic Graph: A graph is acyclic if it does not contain any cycles.

  * •

Complete Graph: A graph is complete if there is an edge between every pair of
nodes.

#####  2.3.2.3 Graph vs Knowledge Graph

A Knowledge Graph (KG)is a specialized form of graph intended to accumulate
and convey real-world knowledge. As said before, we are not technically
building KGs, but we rely on many concepts from the domain. Research on KG has
further accelerated in recent years, and introduced significant improvement to
Graph Theory, especially in the practical applications of graph construction
and use for Machine Learning or Deep Learning [89]. They have a number of
benefits when compared with a relational model or NoSQL alternatives, such as
the ability for data to evolve in a more flexible manner, and the capacity to
organize data in a way that is not hierarchical. They can represent incomplete
information, and does not require a precise schema [89, p.2], which is
invaluable in the context of memory analysis, where the structure of the heap
is not known in advance.

While all KGs are graphs, not all graphs are KGs. However, the line between
the two is often blurry, and the distinction is not always clear. The term
"knowledge graph" first appeared in 1973, but really gained popularity through
a 2012 blog post about Google’s Knowledge Graph [95]. Several definition
attempts have been made, but none of them are universally accepted. Below are
listed some of the most common definitions of Knowledge Graphs:

  * •

A graph of data intended to accumulate and convey knowledge of the real world,
whose nodes represent entities of interest and whose edges represent
potentially different relations between these entities. [89]

  * •

A graph of data consisting of semantically described entities and relations of
different types that are integrated from different sources. Entities have a
unique identifier. KG entities and relations are semantically described using
an ontology or, more clearly, an ontological representation. [92]

In KGs, edges are often labeled and may represent complex relationships like
"is a subclass of" or "is married to", allowing for more expressive power. The
very nature of KG makes any definition attempt difficult. Indeed, KG is a
broad concept that can be applied to many domains, use cases and can have
diverse implementations. The definition of KGs is thus very context-dependent,
and it’s debatable where the line between a graph and a KG is drawn.

For the purpose of this thesis, we won’t focus on this distinction and just
consider that we deal with memory graphs, which are graphs that are not
necessarily KGs, but that can be used to represent complex relationships
between entities extracted from memory dumps and be leveraged using KG-related
techniques for advance tasks like feature engineering, automated embedding,
inductive reasoning and learning.

#####  2.3.2.4 Ontologies

An ontology is a formal representation of knowledge within a domain, providing
a structured framework for organizing and interpreting information. It
consists of a set of concepts, relationships, and rules that define how data
is interconnected and how it can be reasoned about. Ontologies are often used
to model a domain and support reasoning about entities and their relationships
[90].

Ontologies play a crucial role in the development and utility of knowledge
graphs. They provide a semantic layer to the knowledge graph, enabling
machines to understand the meaning and context of the data. The axioms and
rules in an ontology enable automated reasoning, allowing the knowledge graph
to infer new facts from existing data. Ontologies also help in maintaining the
quality and consistency of data by enforcing constraints and validation rules.
Finally, ontologies enable interoperability by providing a common vocabulary
for data exchange and integration. Different popular ontologies exists, such
as Web Ontology Language (OWL)or Resource Description Framework (RDF).

By incorporating ontologies, knowledge graphs become more than just a
collection of nodes and edges; they become a rich, interconnected web of
semantically meaningful information that can be easily queried, analyzed, and
extended. We will be referring to concepts that have been inspired by
ontologies in the next sections, like rdf:Bag.

The rdf:Bag container is a part of the Resource Description Framework (RDF)
used to represent collections where the order of elements is not significant.
Unlike other containers such as rdf:Seq and rdf:Alt, rdf:Bag permits duplicate
entries. It can be used to model unsorted collections of resources or
literals. An instance of rdf:Bag can be represented as a graph where each node
connected to the root node represents an item in the collection [9]. For
example, consider a root node named "DataStructure" with a property Address
specifying its malloc header address.

DataStructureAddress: malloc header addressItem 1Item 2Item 3 Figure 2.1:
Graphical representation of an rdf:Bag container.

This small example illustrates how we can represent a container, or a
relationship of belonging, using a graph. This is a concept that will be used
later in the memory modelization process.

#####  2.3.2.5 Inductive Reasoning and Learning

Inductive reasoning in Knowledge Graphs (KGs) involves techniques like
embedding and Graph Convolutional Networks (GCNs) to learn the potential
underlying structure of the graph. This is particularly useful for tasks like
link prediction, node classification, and clustering.

For the sake of clarity and grouping, we will present the concepts of graph
embedding and GCNs in the next sections, but it is important to note that they
are not mutually exclusive. In fact, GCNs can be used to generate embeddings,
and embeddings can be used as input for GCNs. As such, they are often used
together in the context of KGs, or in our case, memory graphs.

###  2.4 Data preprocessing for Machine Learning

Machine Learning (ML)is a subfield of Artificial Intelligence (AI)that focuses
on the development of algorithms that can learn from data and make
predictions. It is a powerful tool that has been used to solve a wide range of
problems, including image classification, speech recognition, and natural
language processing. Before we can apply machine learning algorithms to a
dataset, we must first prepare the data by performing various preprocessing
steps. In this section, we will discuss the most common data preprocessing
techniques, including data cleaning, feature engineering, and dataset
splitting, as well as the importance of feature selection and dimensionality
reduction. All those elements are crucial for the development of effective
machine learning models for key extraction.

####  2.4.1 Feature engineering

In the realm of machine learning and data science, features refer to
individual measurable attributes or characteristics of the phenomena under
study. Those features can be of different types, and can be used to predict
the value of a target variable.

#####  2.4.1.1 Types of Features

Features can be of different types, depending on the nature of the data. The
type of feature determines how it is processed and utilized by the model. The
most common types of features include:

  * •

Numerical Features: These are quantitative attributes representing
measurements like height, weight, or age.

  * •

Categorical Features: These are qualitative attributes representing discrete
classes or labels, such as gender (Male, Female) or educational level (High
School, Bachelor’s, Master’s).

  * •

Ordinal Features: Similar to categorical features but with an inherent order,
like ratings on a scale of 1 to 5.

  * •

Text Features: These contain textual data and often require special
preprocessing steps like tokenization and vectorization.

  * •

Temporal Features: These are time-based attributes, such as timestamps,
requiring special handling to capture time-dependent patterns.

  * •

Geospatial Features: These attributes represent geographical or spatial
coordinates.

Features are pivotal for the performance of machine learning models. The
quality and pertinence of features can significantly influence the model’s
capability to discern underlying patterns in the data. Inadequately chosen, or
irrelevant features can lead to a poorly performing model, while carefully
selected, relevant features can result in a robust and accurate model.

#####  2.4.1.2 The Curse of Dimensionality

The curse of dimensionality refers to a set of challenges that arise when
dealing with high-dimensional data. As the number of features, or dimensions,
in a dataset increases, the volume of the feature space grows exponentially.
This exponential growth leads to several issues:

  * •

Data Sparsity: In high-dimensional spaces, data points tend to be sparse,
making it difficult for algorithms to identify patterns. The sparsity also
means that the notion of "distance" becomes less meaningful, which is
problematic for algorithms that rely on distance metrics.

  * •

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 [25].

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 [24].

  * •

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 exits, 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 [24].

  * •

Feature Selection: Unlike feature extraction, feature selection aims to pick a
subset of the most important features from the original set, without changing
them [24]. 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 [25].

#####  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 [28]. 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 [27], 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 [65]. In recent years, they have also been applied to graphs to
learn node representations [89]. 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 [65]. 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 [89]. 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 [89] [89,
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 [89].

  * •

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 [89].

  * •

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 [89].

  * •

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 [89].

  * •

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 [89].

  * •

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 [89] [90].

  * •

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

###### 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 [34].

  * •

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 [90].

  * •

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 [35].

  * •

R-GCN: Relational Graph Convolutional Networks (R-GCNs) combine the strengths
of GCNs and traditional embedding methods to capture both topological and
semantic information [36]. A more recent study by [49] 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)
[49].

  * •

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

###### 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
[37].

  * •

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 [39].

  * •

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 [65].

  * •

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 [90].

  * •

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
[90].

###### 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 [89].

  * •

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 [90].

  * •

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 [40].

  * •

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 [50].

  * •

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 [56]
[58].

  * •

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 [41].

  * •

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 [90].

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

#####  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 [29].

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 [29]:

  * •

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 [64]. 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
[27].

####  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 [30].

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 [31].

Decision Trees use metrics like Gini impurity or entropy to make splits:

$\text{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 [32].

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 [63].

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 [60].

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 [62]. They
consist of interconnected 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 [90].

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 [62, 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 [61].

  * •

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 [59].

  * •

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 [62] [33].

  * •

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 [90]. 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 [90]. 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 [90] [90] and [52] [52].

GNN s have been employed in various applications, ranging from traffic
prediction, recommender systems, and software verification [52]. 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 [90]. 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 [90]. 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. [55] [55] 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 [55].

###### Learning Process in GNN s

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 $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 [55]:

$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}\leq|N_{i}|$: The number of supervised nodes in the graph $G_{i}$.

  * •

$p\leq|\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 [55].

#####  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. [90]. 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 [43]. 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 [48]
[57]:

$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