**Algorithm 7** Malloc Header Parsing Algorithm

1: **Procedure** MallocHeaderParsing(*block*)
   **Require:** *block* is a block of 8 bytes
   **Ensure:** MallocHeader object
   **Ensure:** *Flags* object
2:     **Note:** In this algorithm, & represents bitwise AND, and ~ represents bitwise negation.
3:     *size_and_flags* ← ConvertBytesToInteger(*block*, 'little-endian')
4:     *size* ← *size_and_flags* & (~0x07) ▷ Clear the last 3 bits to get the size
5:     *Flags.a* ← bool(*size_and_flags* & 0x04)
6:     *Flags.m* ← bool(*size_and_flags* & 0x02)
7:     *Flags.p* ← bool(*size_and_flags* & 0x01)
8:     **return** MallocHeader{*size*, *Flags*}
9: **end Procedure**

We can also isolate the size parsing algorithm into a handy function:

**Algorithm 8** Malloc Header block to size conversion Algorithm

1: **Procedure** ConvertToSize(*block*)
   **Require:** *block* is a block of 8 bytes
2:     **Note:** In this algorithm, & represents bitwise AND, and ~ represents bitwise negation.
3:     *size_and_flags* ← ConvertBytesToInteger(*block*, 'little-endian')
4:     *size* ← *size_and_flags* & (~0x07) ▷ Clear the last 3 bits to get the size
5:     **return** *size*
6: **end Procedure**

Based on those algorithms, and in a similar fashion as what we have done manually by exploring
the heap dump file with vim, we can propose the following algorithm to detect the malloc headers
in a heap dump file:

**Algorithm 9** Malloc Header Chaining Algorithm

1: **Procedure** MallocHeaderDetection(*heapDumpFile*)
2:     **Note:** ConvertToSize is equivalent to MallocHeaderParsing(*block*).size ▷ See 3.2.8.2
3:     **Initialize** malloc_header_list to empty list
4:     *position* ← 0
5:     **while** *position* < FileSize(*heapDumpFile*) **do**
6:         *block* ← Read8Bytes(*heapDumpFile*, *position*)
7:         **if** *block* ≠ 0 **then**
8:             *size* ← ConvertToSize(*block*) ▷ Be careful with flags
9:             **Assert** *size!* = 0
10:         **Assert** *size* mod 8 = 0 ▷ Check if the size is 8-bytes aligned
11:     *position* ← *position* + *size*
12:     **else**
13:         *position* ← *position* + 8
14:     **end if**
15:     **end while**
16:     **return** malloc_header_list
17: **end Procedure**

The idea behind the malloc header detection algorithm is simple. We start at the beginning of
**Algorithm 7** Malloc Header Parsing Algorithm

1: **Procedure** MallocHeaderParsing(*block*)
   **Require:** *block* is a block of 8 bytes
   **Ensure:** MallocHeader object
   **Ensure:** *Flags* object
2:     **Note:** In this algorithm, & represents bitwise AND, and ~ represents bitwise negation.
3:     *size_and_flags* ← ConvertBytesToInteger(*block*, 'little-endian')
4:     *size* ← *size_and_flags* & (~0x07) ▷ Clear the last 3 bits to get the size
5:     *Flags.a* ← bool(*size_and_flags* & 0x04)
6:     *Flags.m* ← bool(*size_and_flags* & 0x02)
7:     *Flags.p* ← bool(*size_and_flags* & 0x01)
8:     **return** MallocHeader{*size*, *Flags*}
9: **end Procedure**

We can also isolate the size parsing algorithm into a handy function:

**Algorithm 8** Malloc Header block to size conversion Algorithm

1: **Procedure** ConvertToSize(*block*)
   **Require:** *block* is a block of 8 bytes
2:     **Note:** In this algorithm, & represents bitwise AND, and ~ represents bitwise negation.
3:     *size_and_flags* ← ConvertBytesToInteger(*block*, 'little-endian')
4:     *size* ← *size_and_flags* & (~0x07) ▷ Clear the last 3 bits to get the size
5:     **return** *size*
6: **end Procedure**

Based on those algorithms, and in a similar fashion as what we have done manually by exploring
the heap dump file with vim, we can propose the following algorithm to detect the malloc headers
in a heap dump file:

**Algorithm 9** Malloc Header Chaining Algorithm

1: **Procedure** MallocHeaderDetection(*heapDumpFile*)
2:     **Note:** ConvertToSize is equivalent to MallocHeaderParsing(*block*).size ▷ See 3.2.8.2
3:     **Initialize** malloc_header_list to empty list
4:     *position* ← 0
5:     **while** *position* < FileSize(*heapDumpFile*) **do**
6:         *block* ← Read8Bytes(*heapDumpFile*, *position*)
7:         **if** *block* ≠ 0 **then**
8:             *size* ← ConvertToSize(*block*) ▷ Be careful with flags
9:             **Assert** *size!* = 0
10:         **Assert** *size* mod 8 = 0 ▷ Check if the size is 8-bytes aligned
11:     *position* ← *position* + *size*
12:     **else**
13:         *position* ← *position* + 8
14:     **end if**
15: **end while**
16: **return** malloc_header_list
17: **end Procedure**

The idea behind the malloc header detection algorithm is simple. We start at the beginning of
the heap dump file, and we look for the first non-zero block. Then we assume that the next block is a malloc header. We convert it to a size, and then leap over the user data and the footer up to the next chunk malloc header block index. The process is repeated until reaching the end of the heap dump file.

Note that in case of a problem, like when the size obtained from malloc header parsing is equal to 0, this means that the heap dump chaining is broken. This has been handled in the dataset cleaning section 3.2.6.

### 3.2.8.3 Chunk chaining example

The program `chunk_algorithms.py` has been developed specifically to test the chunk parsing and refine the associated algorithms.

We can test our chunk parsing algorithm on a test file in the cleaned dataset.

```bash
$ python src/data_structure_detection.py --input /home/onyr/code/phdtrack/phdtrack_data_clean/Training/Training/basic/V_7_1_P1/24/17016-1643962152-heapraw --debug Datetime: 2023_09_27_17_08_23_157209 Chunk [1]: Chunk(block_index=2, size=592, flags=[A=False, M=False, P=True]) Chunk [2]: Chunk(block_index=76, size=32, flags=[A=False, M=False, P=True]) Chunk [3]: Chunk(block_index=80, size=32, flags=[A=False, M=False, P=True]) Chunk [4]: Chunk(block_index=84, size=32, flags=[A=False, M=False, P=True]) Chunk [5]: Chunk(block_index=88, size=32, flags=[A=False, M=False, P=True]) Chunk [6]: Chunk(block_index=92, size=192, flags=[A=False, M=False, P=True]) Chunk [7]: Chunk(block_index=116, size=32, flags=[A=False, M=False, P=True]) Chunk [8]: Chunk(block_index=120, size=32, flags=[A=False, M=False, P=True]) Chunk [...] : ... Chunk [911]: Chunk(block_index=10194, size=128, flags=[A=False, M=False, P=True]) Chunk [912]: Chunk(block_index=10210, size=256, flags=[A=False, M=False, P=True]) Chunk [913]: Chunk(block_index=10242, size=160, flags=[A=False, M=False, P=True]) Chunk [914]: Chunk(block_index=10262, size=512, flags=[A=False, M=False, P=True]) Chunk [915]: Chunk(block_index=10326, size=1296, flags=[A=False, M=False, P=True]) Chunk [916]: Chunk(block_index=10488, size=1552, flags=[A=False, M=False, P=True]) Chunk [917]: Chunk(block_index=10682, size=1552, flags=[A=False, M=False, P=True]) Chunk [918]: Chunk(block_index=10876, size=48176, flags=[A=False, M=False, P=True]) -> Statistics: Total number of files: 1 Total number of chunks: 918 Total number of blocks: 16896 Total number of chunks with P=1: 903 Total number of chunks with M=1: 0 Total number of chunks with A=1: 0 Total number of chunks only composed of zeros: 1
```

<caption>Listing 3.21: Testing chunk parsing on `Training/basic/V_7_1_P1/24/17016-1643962152-heapraw`. Partial log output.</caption>

Looking at the first allocated chunks, we recognize what we had seen manually with `vim` for the file `Training/basic/V_7_8_P1/16/5070-1643978841-heapraw`. The first chunk is of size 592, and the next one is of size 32. This is exactly what we had seen manually. It is a good sign that our algorithm is working as expected. We can also see that the last chunk is of size 48176, which is significantly bigger than the other chunks. This chunk is only composed of zeros, and is truncated, meaning that its size if bigger than the actual size of the heap dump file.
the heap dump file, and we look for the first non-zero block. Then we assume that the next block is a malloc header. We convert it to a size, and then leap over the user data and the footer up to the next chunk malloc header block index. The process is repeated until reaching the end of the heap dump file.

Note that in case of a problem, like when the size obtained from malloc header parsing is equal to 0, this means that the heap dump chaining is broken. This has been handled in the dataset cleaning section 3.2.6.

### 3.2.8.3 Chunk chaining example

The program `chunk_algorithms.py` has been developed specifically to test the chunk parsing and refine the associated algorithms.

We can test our chunk parsing algorithm on a test file in the cleaned dataset.

```bash
$ python src/data_structure_detection.py --input /home/onyr/code/phdtrack/phdtrack_data_clean/Training/Training/basic/V_7_1_P1/24/17016-1643962152-heapraw --debug Datetime: 2023_09_27_17_08_23_157209 Chunk [1]: Chunk(block_index=2, size=592, flags=[A=False, M=False, P=True]) Chunk [2]: Chunk(block_index=76, size=32, flags=[A=False, M=False, P=True]) Chunk [3]: Chunk(block_index=80, size=32, flags=[A=False, M=False, P=True]) Chunk [4]: Chunk(block_index=84, size=32, flags=[A=False, M=False, P=True]) Chunk [5]: Chunk(block_index=88, size=32, flags=[A=False, M=False, P=True]) Chunk [6]: Chunk(block_index=92, size=192, flags=[A=False, M=False, P=True]) Chunk [7]: Chunk(block_index=116, size=32, flags=[A=False, M=False, P=True]) Chunk [8]: Chunk(block_index=120, size=32, flags=[A=False, M=False, P=True]) Chunk [...]... Chunk [911]: Chunk(block_index=10194, size=128, flags=[A=False, M=False, P=True]) Chunk [912]: Chunk(block_index=10210, size=256, flags=[A=False, M=False, P=True]) Chunk [913]: Chunk(block_index=10242, size=160, flags=[A=False, M=False, P=True]) Chunk [914]: Chunk(block_index=10262, size=512, flags=[A=False, M=False, P=True]) Chunk [915]: Chunk(block_index=10326, size=1296, flags=[A=False, M=False, P=True]) Chunk [916]: Chunk(block_index=10488, size=1552, flags=[A=False, M=False, P=True]) Chunk [917]: Chunk(block_index=10682, size=1552, flags=[A=False, M=False, P=True]) Chunk [918]: Chunk(block_index=10876, size=48176, flags=[A=False, M=False, P=True]) -> Statistics: Total number of files: 1 Total number of chunks: 918 Total number of blocks: 16896 Total number of chunks with P=1: 903 Total number of chunks with M=1: 0 Total number of chunks with A=1: 0 Total number of chunks only composed of zeros: 1
```

<caption>Listing 3.21: Testing chunk parsing on `Training/basic/V_7_1_P1/24/17016-1643962152-heapraw`. Partial log output.</caption>

Looking at the first allocated chunks, we recognize what we had seen manually with `vim` for the file `Training/basic/V_7_8_P1/16/5070-1643978841-heapraw`. The first chunk is of size 592, and the next one is of size 32. This is exactly what we had seen manually. It is a good sign that our algorithm is working as expected. We can also see that the last chunk is of size 48176, which is significantly bigger than the other chunks. This chunk is only composed of zeros, and is truncated, meaning that its size if bigger than the actual size of the heap dump file.
### 3.2.8.4 Distinguishing between free and allocated chunks

The malloc header chaining algorithm allows to detect memory chunks in the heap dump file. However, it does not allow to distinguish between free and allocated chunks. This is a problem, since we want to be able to distinguish between free and allocated chunks, to be able to detect potential data structures and filter out useless blocks.

Considering the structural differences between a free and in-use block, it's possible to try distinguishing free blocks by their *forward* and *backward* pointers. The issue is that the head dump raw file are not provided with any *bins* information. As such, distinguishing between two normal pointers and the ones expected inside a free block is a non-trivial task. Hence, the tests performed on this idea are inconclusive. A more straightforward technique is to rely on the P malloc header flags.

<figure><img src="image_11.png" /><figcaption>Figure 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.</figcaption></figure>

For a given chunk, the follow-up chunk in ascending address number, contains such a flag in its header block. If the flag value is 0, then the current chunk is free. If the flag value is 1, then the current chunk is in use by the program. This is the technique that has been used in the final
### 3.2.8.4 Distinguishing between free and allocated chunks

The malloc header chaining algorithm allows to detect memory chunks in the heap dump file. However, it does not allow to distinguish between free and allocated chunks. This is a problem, since we want to be able to distinguish between free and allocated chunks, to be able to detect potential data structures and filter out useless blocks.

Considering the structural differences between a free and in-use block, it's possible to try distinguishing free blocks by their *forward* and *backward* pointers. The issue is that the head dump raw file are not provided with any *bins* information. As such, distinguishing between two normal pointers and the ones expected inside a free block is a non-trivial task. Hence, the tests performed on this idea are inconclusive. A more straightforward technique is to rely on the P malloc header flags.

<figure><img src="image_13.png" /><figcaption>Figure 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.</figcaption></figure>

For a given chunk, the follow-up chunk in ascending address number, contains such a flag in its header block. If the flag value is 0, then the current chunk is free. If the flag value is 1, then the current chunk is in use by the program. This is the technique that has been used in the final
implementation of the chunk chaining algorithm.

**Algorithm 10 Chunk Parsing Algorithm**

1: **Procedure** ChunkParsing(*heapDumpFile*, *HEAP_START*)
2:     **Note:** ConvertToSize is equivalent to MallocHeaderParsing(*block*).size
3:     **Note:** Get8BytesBlocks returns a list of 8 bytes blocks from the heap dump file.
4:     **Ensure:** MallocHeader object
5:     **Ensure:** Flags object
6:     **Ensure:** Chunk object
7:     **Ensure:** HEAP_START provided from annotation file is a correct address.
4:     **Note:** In this algorithm, & represents bitwise AND, and ~ represents bitwise negation.
5:     **Initialize** chunk_list to empty list
6:     blocks ← Get8BytesBlocks(*heapDumpFile*)
7:     **Initialize** index ← 0
8:     **while** index < lenght(*blocks*) **do**
9:         block ← blocks[index]
10:        **Initialize** Chunk to empty object
11:        **if** block ≠ 0 **then**
12:            Chunk header : {size, Flags} ← MallocHeaderParsing(*block*) ▷ See 3.2.8.2
13:            **Assert** Chunk header.size ≥ 2 ▷ Must contains at least header and footer
14:            **Assert** Chunk header.size mod 8 = 0 ▷ Check if the size is 8-bytes aligned
15:            Chunk block index ← index ▷ Index of the first block of the chunk after header
16:            Chunk address ← HEAP_START + (index * 8) ▷ Address of block index
17:            footer index ← index + Chunk header.size - 1 ▷ Index of the footer block
18:            **if** footer index < lenght(*blocks*) **then**
19:                footer ← blocks[ footer index ]
20:                **if** ConvertToSize( footer ) = Chunk footer.size **then**
21:                    Chunk correct footer ← True
22:                **else**
23:                    Chunk correct footer ← False
24:                **end if**
25:                **else**
26:                    Chunk correct footer ← False
27:                **end if**
28:            next_chunk_header_index ← index + Chunk header.size ▷ Index of the next chunk
29:        header block
29:        **if** next_chunk_header_index < lenght(*blocks*) **then**
30:            next_chunk_header ← blocks[ next_chunk_header_index ]
31:            Chunk.is_in_use ← MallocHeaderParsing( next_chunk_header ).flags.p
32:            **else**
33:                Chunk is in use ← False ▷ See²
34:            **end if**
35:            index ← index + Chunk header.size ▷ Leap over chunk.
36:        **else**
37:            index ← index + 8 ▷ Leap over zero block.
38:        **end if**
39:    **end while**
40:    **return** malloc header_list
41: **end Procedure**

Note that this algorithm is based on the malloc header chaining algorithm 3.2.8.2. The main
implementation of the chunk chaining algorithm.

**Algorithm 10 Chunk Parsing Algorithm**

1: **Procedure** ChunkParsingABL heapDumpFile, HEAP_START
2: **Note:** ConvertToSize is equivalent to MallocHeaderParsing abl block).size
3: **Note:** Get8BytesBlocks returns a list of 8 bytes blocks from the heap dump file.
**Ensure:** MallocHeader object
**Ensure:** Flags object
**Ensure:** Chunk object
**Ensure:** HEAP_START provided from annotation file is a correct address.
4: **Note:** In this algorithm, & represents bitwise AND, and ~ represents bitwise negation.
5: **Initialize** chunk_list to empty list
6: blocks ← Get8BytesBlocksABL heapDumpFile
7: **Initialize** index ← 0
8: **while** index < lenght abl blocks) **do**
9:     block ← blocks[index]
10:    **Initialize** Chunk to empty object
11:    **if** block ≠ 0 **then**
12:        Chunk header : { size, Flags } ← MallocHeaderParsing abl block) ▷ See 3.2.8.2
13:        **Assert** Chunk header size ≥ 2 ▷ Must contains at least header and footer
14:        **Assert** Chunk header size mod 8 = 0 ▷ Check if the size is 8-bytes aligned
15:        Chunk block index ← index ▷ Index of the first block of the chunk after header
16:        Chunk address ← HEAP_START + (index * 8) ▷ Address of block index
17:        footer index ← index + Chunk header size - 1 ▷ Index of the footer block
18:        **if** footer index < lenght abl blocks) **then**
19:            footer ← blocks[ footer index ]
20:            **if** ConvertToSize abl footer) = Chunk footer size **then**
21:                Chunk correct footer ← True
22:            **else**
23:                Chunk correct footer ← False
24:            **end if**
25:        **else**
26:            Chunk correct footer ← False
27:        **end if**
28:        next_chunk_header index ← index + Chunk header size ▷ Index of the next chunk
header block
29:        **if** next_chunk_header index < lenght abl blocks) **then**
30:            next_chunk_header ← blocks(next_chunk_header index]
31:            Chunk is in use ← MallocHeaderParsing abl next_chunk_header).flags.p
32:        **else**
33:            Chunk is in use ← False ▷ See²
34:        **end if**
35:        index ← index + Chunk header size ▷ Leap over chunk.
36:        **else**
37:            index ← index + 8 ▷ Leap over zero block.
38:        **end if**
39:    **end while**
40:    return malloc header list
41: **end Procedure**

Note that this algorithm is based on the malloc header chaining algorithm 3.2.8.2. The main
difference is that we now have access to the malloc header flags from the following chunk, and
that we can thus distinguish between free and allocated chunks. The algorithm also includes the
 footer parsing technique discussed briefly in the following section.

3.2.8.5 Chunk footer

The documentation of the malloc function of GLIBC states that the footer of a chunk is the same
as the size of the chunk considered. In the current report, we represent the footer as being part of
the chunk itself.

Below are two chunks content of similar size:

```
Printing Chunk [addr:0x80a2d1438355] [status:in-use] [ footer:incorrect] Chunk(block_index
=80, size=32, flags=[A=False, M=False, P=True])
Block [79]: b'!\x00\x00\x00\x00\x00\x00\x00' 33 -malloc-header-
Block [80]: b'\xa0\xa2\xd1C\x83U\x00\x00' 94022266888864
Block [81]: b'\xc0\xa2\xd1C\x83U\x00\x00' 94022266888896
Block [82]: b'\x00\x00\x00\x00\x00\x00\x00\x00' 0 - footer-

Printing Chunk [addr:0xa09fd2438355] [status:free] [ footer:correct] Chunk(block_index
=8180, size=32, flags=[A=False, M=False, P=True])
Block [8179]: b'!\x00\x00\x00\x00\x00\x00\x00' 33 -malloc-header-
Block [8180]: b'\xb0\\xe1\xeES\x7f\x00\x00' 139998466784432
Block [8181]: b'\xb0\\xe1\xeES\x7f\x00\x00' 139998466784432
Block [8182]: b'\x00\x00\x00\x00\x00\x00\x00\x00' 32 - footer-
```

Listing 3.22: Printing some free and in-use chunks from *Training/basic/V_7_1_P1/24/17016-1643962152-heapraw*.

Here, the status of the chunk has been detected using the P flag technique. At first sight,
those two blocks seems similar. The first 2 blocks in the user data space of the chunks both
seems to contain what looks like pointers. As one can see, the first chunk in this example, with a
block_index=80 has clearly a malloc header and footer as expected. Note that here, the value 33
represents the size of the block (32 bytes which correspond to 4 blocks) with the LSB being set to
1 meaning the preceding chunk is in use. However, the in-use block footer doesn't correspond to
the value we expect. This difference of behavior is observed throughout the cleaned dataset.

3.2.9 Discussing chunk parsing for problem scale reduction

Now that we have presented all the necessary knowledge and algorithms used to be able to parse
the RAW heap dump files, we can discuss the results of those algorithms and their uses and
limitations. Many tests have been needed in order to develop the final algorithms. This testing
process has also unveiled some interesting properties of the dataset that will be used as basis for
the semantic embedding of the memory graph representation and subsequent machine learning
steps.

The program `chunk_algorithms.py` has been developed specifically to test the chunk parsing and refine the associated algorithms on the cleaned dataset. Below are presented the global statistics produced by the final version of the program:

```
Input is directory: /home/onyr/code/phdtrack/phdtrack_data_clean/
Found 26191 files in /home/onyr/code/phdtrack/phdtrack_data_clean/.
Processing files: 100%|blacksquare \blacksquare \blacksquare \blacksquare \blacksquare | 26191/26191 [12:11<00:00, 35.81it/s, file=7091-1650972335]
```
difference is that we now have access to the malloc header flags from the following chunk, and
that we can thus distinguish between free and allocated chunks. The algorithm also includes the
 footer parsing technique discussed briefly in the following section.

3.2.8.5 Chunk footer

The documentation of the malloc function of GLIBC states that the footer of a chunk is the same
as the size of the chunk considered. In the current report, we represent the footer as being part of
the chunk itself.

Below are two chunks content of similar size:

```
Printing Chunk [addr:0x80a2d1438355] [status:in-use] [ footer:incorrect] Chunk(block_index
=80, size=32, flags=[A=False, M=False, P=True])
Block [79]: b'!\x00\x00\x00\x00\x00\x00\x00' 33 -malloc-header-
Block [80]: b'\xa0\xa2\xd1C\x83U\x00\x00' 94022266888864
Block [81]: b'\xc0\xa2\xd1C\x83U\x00\x00' 94022266888896
Block [82]: b'\x00\x00\x00\x00\x00\x00\x00\x00' 0 - footer-

Printing Chunk [addr:0xa09fd2438355] [status:free] [ footer:correct] Chunk(block_index
=8180, size=32, flags=[A=False, M=False, P=True])
Block [8179]: b'!\x00\x00\x00\x00\x00\x00\x00' 33 -malloc-header-
Block [8180]: b'\xb0\\xe1\xeES\x7f\x00\x00' 139998466784432
Block [8181]: b'\xb0\\xe1\xeES\x7f\x00\x00' 139998466784432
Block [8182]: b'\x00\x00\x00\x00\x00\x00\x00\x00' 32 - footer-
```

Listing 3.22: Printing some free and in-use chunks from Training/basic/V_7_1_P1/24/17016-1643962152-heapraw.

Here, the status of the chunk has been detected using the P flag technique. At first sight,
those two blocks seems similar. The first 2 blocks in the user data space of the chunks both
seems to contain what looks like pointers. As one can see, the first chunk in this example, with a
block_index=80 has clearly a malloc header and footer as expected. Note that here, the value 33
represents the size of the block (32 bytes which correspond to 4 blocks) with the LSB being set to
1 meaning the preceding chunk is in use. However, the in-use block footer doesn't correspond to
the value we expect. This difference of behavior is observed throughout the cleaned dataset.

3.2.9 Discussing chunk parsing for problem scale reduction

Now that we have presented all the necessary knowledge and algorithms used to be able to parse
the RAW heap dump files, we can discuss the results of those algorithms and their uses and
limitations. Many tests have been needed in order to develop the final algorithms. This testing
process has also unveiled some interesting properties of the dataset that will be used as basis for
the semantic embedding of the memory graph representation and subsequent machine learning
steps.

The program chunk_algorithms.py has been developed specifically to test the chunk parsing
and refine the associated algorithms on the cleaned dataset. Below are presented the global
statistics produced by the final version of the program:

```
Input is directory: /home/onyr/code/phdtrack/phdtrack_data_clean/
Found 26191 files in /home/onyr/code/phdtrack/phdtrack_data_clean/.
Processing files: 100%|blacksquare \blacksquare \blacksquare \blacksquare \blacksquare | 26191/26191 [12:11<00:00, 35.81it/s, file=7091-1650972335]
```
-------> Statistics:
Total number of parsed files: 26191
Total number of skipped files: 0
Total number of chunks: 37682063
Total number of blocks: 674232832
Total number of chunks with P=1: 37346373
Total number of chunks with M=1: 0
Total number of chunks with A=1: 0
Total number of free chunks: 354410
Total number of chunks only composed of zeros: 18720
Total number of blocks in free chunks: 183331224
Total number of chunks with correct footer value: 1009522
Total number of chunks both free and with correct footer value: 335690
Total number of chunks free and annotated: 0
Total number of potential footers with annotations (should be 0): 0
Total number of annotated chunks: 209528
Total number of chunks in use, with correct footer, and annotated: 7668
Total number of chunks in use, with correct footer, and key annotated: 7668
Percentage of free chunks: 0.9405270619074121%
Percentage of blocks in free chunks: 27.19108523033183%
Percentage of free chunks with correct footer value: 94.71798199825061%
Percentage of in-use chunks with correct footer value: 1.8051818044922352%
Average number of annotated chunks per file: 8.0
Average number of chunks in use with correct footer and annotated per file:
0.2927723263716544
Set of sizes of key chunks: {32, 48, 64}
Sizes of key chunks with their number of occurrences:
Size: 32 Number of occurrences: 34366
Size: 48 Number of occurrences: 109346
Size: 64 Number of occurrences: 13434
Number of sizes: 157146
Number of unique sizes: {32, 48, 64}

<caption>Listing 3.23: Printing cleaned dataset chunk parsing global statistics.</caption>

The cleaned dataset contains 26191 RAW files and their corresponding annotation files. The program has been able to parse all those files, and has been able to detect 37682063 chunks, which represents 674232832 blocks. This is a huge number of blocks. The goal being to be able to predict which of those blocks are first key blocks, we need to be able to filter out the useless blocks as much as possible to both optimize computations and scale down the problem.

Using the P flag technique, we can see that 37346373 chunks are in use, and 354410 chunks are free. Although the proportion of free chunks is only 0.94%, there are 27.19% of the blocks that are in free chunks. More importantly, we can see that no free chunk is annotated. This means we can filter out all free chunks and their blocks. This allows a huge reduction of the scale of the problem.

The average number of annotated chunks per file being a perfect value of 8, this means that all the parsed files indeed contains the 6 key annotations with the additional SSH STRUCT and SSH_KEY annotations. The dataset is very imbalanced since we have only 6 keys times the number of RAW files as positive labels and the rest as negative, thus the need for advanced reduction techniques.
-------> Statistics:
Total number of parsed files: 26191
Total number of skipped files: 0
Total number of chunks: 37682063
Total number of blocks: 674232832
Total number of chunks with P=1: 37346373
Total number of chunks with M=1: 0
Total number of chunks with A=1: 0
Total number of free chunks: 354410
Total number of chunks only composed of zeros: 18720
Total number of blocks in free chunks: 183331224
Total number of chunks with correct footer value: 1009522
Total number of chunks both free and with correct footer value: 335690
Total number of chunks free and annotated: 0
Total number of potential footers with annotations (should be 0): 0
Total number of annotated chunks: 209528
Total number of chunks in use, with correct footer, and annotated: 7668
Total number of chunks in use, with correct footer, and key annotated: 7668
Percentage of free chunks: 0.9405270619074121%
Percentage of blocks in free chunks: 27.19108523033183%
Percentage of free chunks with correct footer value: 94.71798199825061%
Percentage of in-use chunks with correct footer value: 1.8051818044922352%
Average number of annotated chunks per file: 8.0
Average number of chunks in use with correct footer and annotated per file:
0.2927723263716544
Set of sizes of key chunks: {32, 48, 64}
Sizes of key chunks with their number of occurrences:
Size: 32 Number of occurrences: 34366
Size: 48 Number of occurrences: 109346
Size: 64 Number of occurrences: 13434
Number of sizes: 157146
Number of unique sizes: {32, 48, 64}

<caption>Listing 3.23: Printing cleaned dataset chunk parsing global statistics.</caption>

The cleaned dataset contains 26191 RAW files and their corresponding annotation files. The program has been able to parse all those files, and has been able to detect 37682063 chunks, which represents 674232832 blocks. This is a huge number of blocks. The goal being to be able to predict which of those blocks are first key blocks, we need to be able to filter out the useless blocks as much as possible to both optimize computations and scale down the problem.

Using the P flag technique, we can see that 37346373 chunks are in use, and 354410 chunks are free. Although the proportion of free chunks is only 0.94%, there are 27.19% of the blocks that are in free chunks. More importantly, we can see that no free chunk is annotated. This means we can filter out all free chunks and their blocks. This allows a huge reduction of the scale of the problem.

The average number of annotated chunks per file being a perfect value of 8, this means that all the parsed files indeed contains the 6 key annotations with the additional SSH STRUCT and SSH_KEY annotations. The dataset is very imbalanced since we have only 6 keys times the number of RAW files as positive labels and the rest as negative, thus the need for advanced reduction techniques.
### 3.2.9.1 From a block-based to a chunk-based approach

The exact code to annotate the chunks can be as simple as the following:

**Algorithm 11 Annotate Chunk Algorithm**
1: **Procedure** AnnotateChunk(chunk, keys_addresses, ssh_struct_addr, session_state_addr)
   Ensure: chunk object
   Ensure: keys_addresses list of integers
   Ensure: ssh_struct_addr integer
   Ensure: session_state_addr integer
2:     **Note:** Annotations should be done after free chunk detection.
3:     **Procedure** AssertChunkUsedThenAnnotate(chunk, annotation)
4:         **Assert** chunk.is_in_use
5:         chunk.annotations.append lí annotation)
6:     **end Procedure**
7:     **if** chunk.address ∈ keys_addresses **then**
8:         AssertChunkUsedThenAnnotate(chunk, ChunkAnnotation.ChunkContainsKey)
9:         **else if** chunk.address = ssh_struct_addr **then**
10:         AssertChunkUsedThenAnnotate(chunk, ChunkAnnotation.ChunkContainsSSHStruct)
11:         **else if** chunk.address = session_state_addr **then**
12:         AssertChunkUsedThenAnnotate(chunk, ChunkAnnotation.ChunkContainsSessionState)
13:     **end if**
14: **end Procedure**

This algorithm in itself and the results observed is an important discovery. The annotations are actually always given for the `chunk.address` which corresponds to the address of the first block after the `malloc` header block. This means that the annotations are actually given for the beginning of the user data space of a chunk. This is crucial discovery, since it means that we can filter out the `malloc` header and footer blocks, and only keep the first block of the user data space of the chunks we want to embed. There are 674232832 - 183331224 = 490901608 blocks in use. But there is only 37346373 chunks in use. This means that we can reduce the number of blocks to embed from 490901608 to 37346373 which is an additional reduction applied after the previous filtering that reduces the scale of the problem by a factor of 13.

### 3.2.9.2 Using chunk footer for filtering is not possible

Now let's look at the footer parsing. We can see in the logs that 94.72% of free chunks are said to have a correct footer value. But this value is misleading. Since the last chunk of a heap dump is often cropped, it means it has no footer. But we consider those special last chunks as free chunks. In fact, in the 354410 free chunks, we have 18720 or around 5.28% of them that are those special last cropped chunks only composed of zeros. With this perspective, we understand that 100% of the free chunks should be considered with correct footer value. In contrast, only 1.81% of in-use chunks have a correct footer value. It's tempting to think that maybe, those few chunks could maybe be actually empty too and removed. But this is not the case since a few chunks are actually both in-use, with a key annotation and a correct footer value. This means that we need to keep those chunks.
### 3.2.9.1 From a block-based to a chunk-based approach

The exact code to annotate the chunks can be as simple as the following:

**Algorithm 11 Annotate Chunk Algorithm**
1: **Procedure** AnnotateChunk(chunk, keys_addresses, ssh_struct_addr, session_state_addr)
   Ensure: chunk object
   Ensure: keys_addresses list of integers
   Ensure: ssh_struct_addr integer
   Ensure: session_state_addr integer
2:     **Note:** Annotations should be done after free chunk detection.
3:     **Procedure** AssertChunkUsedThenAnnotate(chunk, annotation)
4:         **Assert** chunk.is_in_use
5:         chunk.annotations.append lí annotation)
6:     **end Procedure**
7:     **if** chunk.address ∈ keys_addresses **then**
8:         AssertChunkUsedThenAnnotate(chunk, ChunkAnnotation.ChunkContainsKey)
9:         **else if** chunk.address = ssh_struct_addr **then**
10:         AssertChunkUsedThenAnnotate(chunk, ChunkAnnotation.ChunkContainsSSHStruct)
11:         **else if** chunk.address = session_state_addr **then**
12:         AssertChunkUsedThenAnnotate(chunk, ChunkAnnotation.ChunkContainsSessionState)
13:     **end if**
14: **end Procedure**

This algorithm in itself and the results observed is an important discovery. The annotations are actually always given for the `chunk.address` which corresponds to the address of the first block after the `malloc` header block. This means that the annotations are actually given for the beginning of the user data space of a chunk. This is crucial discovery, since it means that we can filter out the `malloc` header and footer blocks, and only keep the first block of the user data space of the chunks we want to embed. There are 674232832 - 183331224 = 490901608 blocks in use. But there is only 37346373 chunks in use. This means that we can reduce the number of blocks to embed from 490901608 to 37346373 which is an additional reduction applied after the previous filtering that reduces the scale of the problem by a factor of 13.

### 3.2.9.2 Using chunk footer for filtering is not possible

Now let's look at the footer parsing. We can see in the logs that 94.72% of free chunks are said to have a correct footer value. But this value is misleading. Since the last chunk of a heap dump is often cropped, it means it has no footer. But we consider those special last chunks as free chunks. In fact, in the 354410 free chunks, we have 18720 or around 5.28% of them that are those special last cropped chunks only composed of zeros. With this perspective, we understand that 100% of the free chunks should be considered with correct footer value. In contrast, only 1.81% of in-use chunks have a correct footer value. It's tempting to think that maybe, those few chunks could maybe be actually empty too and removed. But this is not the case since a few chunks are actually both in-use, with a key annotation and a correct footer value. This means that we need to keep those chunks.
### 3.2.9.3 Chunk filtering

Based on the previous observations, we can propose different ways of filtering some chunks out. The objective is to reduce the number of chunks before any further processing to reduce the imbalanceness.

Since we have seen that free chunks are never annotated, we can filter them out. This filtering technique allows to reduce the number of chunks from 37682063 to 37346373, which is a small reduction of 0.89%. It is not a huge reduction of chunks, but is a much more significant reduction of the number of blocks since 27.2% of the blocks are in free chunks.

We can also filter the chunks whose size is not 32, 48 or 64 bytes. This is based on the observation that the key chunks are of those sizes. Such a filtering technique allows to reduce the number of chunks significantly, since there is a cumulated $109346 + 34366 + 13434 = 157146$ chunks of those size, which represents, compare to the original number of chunks, a diminution of 99.6%. It is indeed a huge reduction of the scale of the problem.

A last approach to chunk filtering for key prediction consists in measuring the entropy of the first bytes of a chunk. Since we have previously discovered that keys are always located at the beginning of a chunk, and since the keys are composed of random bytes, we can expect the entropy of the first bytes of a chunk to be high.

The following graph illustrates this phenomenon:

<figure><img src="image_12.png" /><figcaption>Figure 3.8: Visualization of the entropy distribution for all chunks of the phdtrack\_data\_clean/RAW heap dump dataset.</figcaption></figure>

Using a script to perform some counting, we realize that the number of chunks whose entropy
### 3.2.9.3 Chunk filtering

Based on the previous observations, we can propose different ways of filtering some chunks out. The objective is to reduce the number of chunks before any further processing to reduce the imbalanceness.

Since we have seen that free chunks are never annotated, we can filter them out. This filtering technique allows to reduce the number of chunks from 37682063 to 37346373, which is a small reduction of 0.89%. It is not a huge reduction of chunks, but is a much more significant reduction of the number of blocks since 27.2% of the blocks are in free chunks.

We can also filter the chunks whose size is not 32, 48 or 64 bytes. This is based on the observation that the key chunks are of those sizes. Such a filtering technique allows to reduce the number of chunks significantly, since there is a cumulated $109346 + 34366 + 13434 = 157146$ chunks of those size, which represents, compare to the original number of chunks, a diminution of 99.6%. It is indeed a huge reduction of the scale of the problem.

A last approach to chunk filtering for key prediction consists in measuring the entropy of the first bytes of a chunk. Since we have previously discovered that keys are always located at the beginning of a chunk, and since the keys are composed of random bytes, we can expect the entropy of the first bytes of a chunk to be high.

The following graph illustrates this phenomenon:

<figure><img src="image_14.png" /><figcaption>Figure 3.8: Visualization of the entropy distribution for all chunks of the phdtrack\_data\_clean/RAW heap dump dataset.</figcaption></figure>

Using a script to perform some counting, we realize that the number of chunks whose entropy
is less than the minimum entropy of the chunks that contains a key (is key chunk) is 19690826, which represents 52.3% of the total number of chunks. It's not entirely clear why the key chunk entropy values seem spread across 2 strips of values, but is probably an effect of the different distributions of chunks across the input dataset, depending on the version, use can and number of chunks in the considered input files.

After all those extensive analysis and tests, we have gained invaluable knowledge about how we can reduce the scale of the problem and parse the files. Now, we need a way to create meaningful embeddings for the blocks we want to perform machine learning on. This is the goal of the next section.

## 3.3 Graph-based memory dumps embedding

Now that we have a decent understanding of the dataset as well as the low level memory dump format, we can start to think about how to convert the memory dumps into graphs. As a recall, we want to be able to convert a memory dump into a graph representation that can be used for machine learning, since we want to be able to create a memory modelization as a basis for efficient embedding and feature engineering later. This is inherently due to the imbalanceness of the dataset, as we want to add more information to each memory block that just its raw bytes. The goal is to have a graph representation of the memory dump that can be used for efficient machine learning.

### 3.3.1 Initial work from Python to Rust

Initially, we have been working and manipulating the code provided by SmartKex<fnref n="3" /> for key detection. Our first explorations of the dataset quickly gave birth to some Jupyter Notebooks, which were used to explore the dataset and to understand the code, like `search_in_heap_mem.ipynb`. Rapidly, we decided to rebuild a complete Python 3.11 version of the code. This was done for several reasons:

* The provided code had no type hinting, which makes it hard to read and understand.

* We wanted to explore the dataset and learn by doing.

* The original code was not designed to be used as a library, but rather as a standalone script.

* The original code was just a few hundred lines of code and was not designed to be easily extensible, nor to be able to handle a large number of memory dumps.

* We wanted to modernize code by using the latest stable version of Python.

We decided to build a memory graph representation at that moment because we wanted to be able to add more information to the memory blocks than just their raw bytes. This new program was called `ssh_key_discover`, and relied on a number of Python libraries to work, like `graphviz`. This was a all-in-one library, composed of 2 sections, `mem_graph` and `ml_discovery`. The first one was devoted to build memory graphs, while the second one was dedicated to the data science and machine learning part.

<footnote n="3">³SmartKex GitHub repository: https://github.com/smartvmi/Smart-and-Naive-SSH-Key-Extraction</footnote>
is less than the minimum entropy of the chunks that contains a key (is key chunk) is 19690826, which represents 52.3% of the total number of chunks. It's not entirely clear why the key chunk entropy values seem spread across 2 strips of values, but is probably an effect of the different distributions of chunks across the input dataset, depending on the version, use can and number of chunks in the considered input files.

After all those extensive analysis and tests, we have gained invaluable knowledge about how we can reduce the scale of the problem and parse the files. Now, we need a way to create meaningful embeddings for the blocks we want to perform machine learning on. This is the goal of the next section.

## 3.3 Graph-based memory dumps embedding

Now that we have a decent understanding of the dataset as well as the low level memory dump format, we can start to think about how to convert the memory dumps into graphs. As a recall, we want to be able to convert a memory dump into a graph representation that can be used for machine learning, since we want to be able to create a memory modelization as a basis for efficient embedding and feature engineering later. This is inherently due to the imbalanceness of the dataset, as we want to add more information to each memory block that just its raw bytes. The goal is to have a graph representation of the memory dump that can be used for efficient machine learning.

### 3.3.1 Initial work from Python to Rust

Initially, we have been working and manipulating the code provided by SmartKex<fnref n="3" /> for key detection. Our first explorations of the dataset quickly gave birth to some Jupyter Notebooks, which were used to explore the dataset and to understand the code, like `search_in_heap_mem.ipynb`. Rapidly, we decided to rebuild a complete Python 3.11 version of the code. This was done for several reasons:

* The provided code had no type hinting, which makes it hard to read and understand.

* We wanted to explore the dataset and learn by doing.

* The original code was not designed to be used as a library, but rather as a standalone script.

* The original code was just a few hundred lines of code and was not designed to be easily extensible, nor to be able to handle a large number of memory dumps.

* We wanted to modernize code by using the latest stable version of Python.

We decided to build a memory graph representation at that moment because we wanted to be able to add more information to the memory blocks than just their raw bytes. This new program was called `ssh_key_discover`, and relied on a number of Python libraries to work, like `graphviz`. This was a all-in-one library, composed of 2 sections, `mem_graph` and `ml_discovery`. The first one was devoted to build memory graphs, while the second one was dedicated to the data science and machine learning part.

<footnote n="3">³SmartKex GitHub repository: https://github.com/smartvmi/Smart-and-Naive-SSH-Key-Extraction</footnote>
This initial program was already capable of handling several data processing pipelines, including machine learning pipelines with models like Random Forest, a grid search for hyperparameter optimization, a cross validation pipeline, several balancing strategies and of course, a memory graph representation with a semantic embedding. As an early development version, this program was not optimized for performance, and just loading a given heap dump file and its annotation, then building the memory graph representation could take from 30 seconds to a minute (on the TUXEDO machine), depending on the size of the heap dump file. As the original dataset comprises more than 10⁶ files, a rapid estimation of the time needed just for the semantic embedding of the memory graph representation was above a month. In this regard, this initial program was just used on a bunch of files as a way to develop the semantic embedding model, parsing algorithms and start working on feature engineering and machine learning. But it could not be used to produce final results on the whole dataset due to the performance issues described above.

Such an optimization issue was clearly not acceptable, and we decided to rewrite the graph part in Rust. This is a compiled language that leverages zero-cost abstractions, and thus, is several order of magnitude faster than Python. It was also a good opportunity to learn Rust, which is a language that is gaining more and more popularity, especially in the security community. This new program was called mem2graph. Switching from Rust to Python and doing a proper use of multithreading allowed us to reduce the time needed to build the memory graph representation from 30 seconds to less than 1 second. In our case, and comparing using only the TUXEDO laptop, this represents an estimated minimum of a 130x speedup. But this is even much better on the server, where the multithreading can really be leverage. This was a significant improvement which allowed us to build the memory graph representation for the whole original dataset in just a few hours.

### 3.3.2 Memory Graph Representation

Now, let's describe the memory graph representation. The goal is to be able to represent a memory dump as a graph. This modelization makes sense since the heap dump can be considered as having memory chunks as nodes, being connected by pointers acting as arrows. This is a very natural way to represent a memory dump. However, in our cases, and since the goal is to make predictions on raw bytes, we will not use the chunks as nodes, but rather the memory blocks directly. This is because we want to be able to make predictions on raw blocks of bytes, and not on chunks.

Our memory graph representation is composed of a directed graph, where each node is a memory block of bytes, and each edge is either indicative of a pointer link or a chunk membership relationship. This second representation is directly inspired by collection representation in Knowledge Graph ontologies. In the case of RDF, this could be equivalent to a **rdf:Bag**, which is an unordered container [0] (see 2.3.2.4). The graph is directed because the pointers are directed. We will also consider the relationship of belonging to a chunk as oriented from the data structure header block to the data structure member blocks.

Our memory graph representation is inherently a property graph. Each node and edge can have properties. The properties of an edge are the type of the edge, which can be either a pointer or a structure membership relationship.

* dts: Data Structure Membership Relationship

* ptr: Pointer Relationship (direction is from the source to the target)
This initial program was already capable of handling several data processing pipelines, including machine learning pipelines with models like Random Forest, a grid search for hyperparameter optimization, a cross validation pipeline, several balancing strategies and of course, a memory graph representation with a semantic embedding. As an early development version, this program was not optimized for performance, and just loading a given heap dump file and its annotation, then building the memory graph representation could take from 30 seconds to a minute (on the TUXEDO machine), depending on the size of the heap dump file. As the original dataset comprises more than 10⁶ files, a rapid estimation of the time needed just for the semantic embedding of the memory graph representation was above a month. In this regard, this initial program was just used on a bunch of files as a way to develop the semantic embedding model, parsing algorithms and start working on feature engineering and machine learning. But it could not be used to produce final results on the whole dataset due to the performance issues described above.

Such an optimization issue was clearly not acceptable, and we decided to rewrite the graph part in Rust. This is a compiled language that leverages zero-cost abstractions, and thus, is several order of magnitude faster than Python. It was also a good opportunity to learn Rust, which is a language that is gaining more and more popularity, especially in the security community. This new program was called mem2graph. Switching from Rust to Python and doing a proper use of multithreading allowed us to reduce the time needed to build the memory graph representation from 30 seconds to less than 1 second. In our case, and comparing using only the TUXEDO laptop, this represents an estimated minimum of a 130x speedup. But this is even much better on the server, where the multithreading can really be leverage. This was a significant improvement which allowed us to build the memory graph representation for the whole original dataset in just a few hours.

### 3.3.2 Memory Graph Representation

Now, let's describe the memory graph representation. The goal is to be able to represent a memory dump as a graph. This modelization makes sense since the heap dump can be considered as having memory chunks as nodes, being connected by pointers acting as arrows. This is a very natural way to represent a memory dump. However, in our cases, and since the goal is to make predictions on raw bytes, we will not use the chunks as nodes, but rather the memory blocks directly. This is because we want to be able to make predictions on raw blocks of bytes, and not on chunks.

Our memory graph representation is composed of a directed graph, where each node is a memory block of bytes, and each edge is either indicative of a pointer link or a chunk membership relationship. This second representation is directly inspired by collection representation in Knowledge Graph ontologies. In the case of RDF, this could be equivalent to a **rdf:Bag**, which is an unordered container [0] (see 2.3.2.4). The graph is directed because the pointers are directed. We will also consider the relationship of belonging to a chunk as oriented from the data structure header block to the data structure member blocks.

Our memory graph representation is inherently a property graph. Each node and edge can have properties. The properties of an edge are the type of the edge, which can be either a pointer or a structure membership relationship.

* **dts**: Data Structure Membership Relationship

* **ptr**: Pointer Relationship (direction is from the source to the target)
In our case, the properties of a node are at minimum the address and the byte block. The graph
is also heterogeneous since our nodes can have different types corresponding to their inferred
characteristics.

* PN: Pointer Node. This is a node whose bytes have been identified as a pointer.

* CHN: Chunk Header Node. This is a node whose bytes have been identified as a memory (malloc) chunk header. In the graph, this node is the root node of a memory structure managed by the C library responsible for memory management and allocation.

* KN: Key Node. This is a node whose bytes have been identified as a key. This identification relies both on the annotations and some verification checks.

* VN: Value Node. These are all blocks that have not been identified. It is the default node type.

These nodes and edges form the base of the memory graph representation. Below is a simplified (truncated) example of a memory graph representation. The full example is available in .2. For clarity, the addresses are not displayed in this simplified version. Another version of this graph with real addresses is available in .2.

<figure><img src="image_13.png" /><figcaption>Figure 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 .2.</figcaption></figure>

The given graph represents a memory layout with various types of nodes, each serving a specific purpose. The graph contains CHN nodes, which act as the root nodes for allocated structures and are colored in cyan. These DTN nodes are connected to KN nodes, which are identified as keys and are colored in green. The PN nodes, colored in orange, are pointers and can be connected to value nodes or key nodes. Finally, the graph includes VN nodes, which are the default node types and are colored in gray. These nodes have not been identified as any specific type and may contain arbitrary values.

The idea behind this representation will be to try to make predictions on the KN nodes, which are the nodes that have been identified as keys. Using the graph, we can build an embedding of
In our case, the properties of a node are at minimum the address and the byte block. The graph
is also heterogeneous since our nodes can have different types corresponding to their inferred
characteristics.

* PN: Pointer Node. This is a node whose bytes have been identified as a pointer.

* CHN: Chunk Header Node. This is a node whose bytes have been identified as a memory (malloc) chunk header. In the graph, this node is the root node of a memory structure managed by the C library responsible for memory management and allocation.

* KN: Key Node. This is a node whose bytes have been identified as a key. This identification relies both on the annotations and some verification checks.

* VN: Value Node. These are all blocks that have not been identified. It is the default node type.

These nodes and edges form the base of the memory graph representation. Below is a simplified (truncated) example of a memory graph representation. The full example is available in .2. For clarity, the addresses are not displayed in this simplified version. Another version of this graph with real addresses is available in .2.

<figure><img src="image_15.png" /><figcaption>Figure 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 .2.</figcaption></figure>

The given graph represents a memory layout with various types of nodes, each serving a specific purpose. The graph contains CHN nodes, which act as the root nodes for allocated structures and are colored in cyan. These DTN nodes are connected to KN nodes, which are identified as keys and are colored in green. The PN nodes, colored in orange, are pointers and can be connected to value nodes or key nodes. Finally, the graph includes VN nodes, which are the default node types and are colored in gray. These nodes have not been identified as any specific type and may contain arbitrary values.

The idea behind this representation will be to try to make predictions on the KN nodes, which are the nodes that have been identified as keys. Using the graph, we can build an embedding of
the nodes and as such, add more information to a given byte block than just its raw bytes. This is the basis of the semantic embedding, which will be discussed later.

This example is based on the heap dump file *Training/basic/V_7_1_P1/24/17016-1643962152-heap/raw* and has been generated using *mem2graph*, and the **sfdp** layout algorithm from *graphviz* using the following command:

```
sfdp -Gsize=30! -G overlap=voronoi -Tpng 17016-1643962152_truncated_no_addresses@gv > 17016-1643962152_truncated_no_addresses.png
```

Listing 3.24: Command used to generate the memory graph visualization of *Training/basic/V_7_1_P1/24/17016-1643962152-heap/raw*

## 3.4 From heap dump to memory graph embeddings

Now that the basis of the memory graph representation has been described, let's dive in the different phases involved in transforming a raw heap dump file into a memory graph file with some custom embeddings that can later be loaded and used by some data analysis and ML programs.

### 3.4.1 Initialization and data checking

The graph construction process begins with the initialization phase. In this phase, the first step is graph initialization, which involves loading a given heap dump file and its associated annotation file. Once the files are loaded, several checks are performed on the annotation file to ensure its validity. These checks include verifying that all annotations are present and formatted correctly, as well as ensuring that the annotation file is neither empty nor contains errors.

#### 3.4.1.1 Graph Construction steps

The second major step in the process is graph building. This involves constructing the graph from heap dump byte blocks. The first part of this step is the data structure detection, where blocks are parsed from start to finish. The parsing process leaps over blocks by using chunk sizes that are stored in chained chunk headers. Each chunk is then verified for its size, alignment, and the presence of a potential footer. Following this, the pointer detection step is carried out. In this phase, potential pointers are identified using the previously introduced pointer detection algorithm and are added to the graph.

An optional step that can be performed is the chunk pointer reduction. This step removes any blocks that are not Chunk Header Nodes, effectively transforming the graph from a block-based graph to a chunk-based graph. While this step is not mandatory, it can be useful for reducing the scale of the problem. This approach will be extensively used in the machine learning section, as it has been shown that the key block prediction problem is equivalent to a key chunk prediction problem.

#### 3.4.1.2 Graph Annotation

The third major step in the process is graph annotation. In this phase, Value Nodes in the graph are replaced by Key Nodes, utilizing the annotations provided in the JSON annotation file. Additional
the nodes and as such, add more information to a given byte block than just its raw bytes. This is the basis of the semantic embedding, which will be discussed later.

This example is based on the heap dump file *Training/basic/V_7_1_P1/24/17016-1643962152-heap/raw* and has been generated using *mem2graph*, and the **sfdp** layout algorithm from *graphviz* using the following command:

1

```
sfdp -Gsize=30! -Goverlap=voronoi -Tpng 17016-1643962152_truncated_no_addresses@gv > 17016-1643962152_truncated_no_addresses.png
```

Listing 3.24: Command used to generate the memory graph visualization of *Training/basic/V_7_1_P1/24/17016-1643962152-heap/raw*

## 3.4 From heap dump to memory graph embeddings

Now that the basis of the memory graph representation has been described, let's dive in the different phases involved in transforming a raw heap dump file into a memory graph file with some custom embeddings that can later be loaded and used by some data analysis and ML programs.

### 3.4.1 Initialization and data checking

The graph construction process begins with the initialization phase. In this phase, the first step is graph initialization, which involves loading a given heap dump file and its associated annotation file. Once the files are loaded, several checks are performed on the annotation file to ensure its validity. These checks include verifying that all annotations are present and formatted correctly, as well as ensuring that the annotation file is neither empty nor contains errors.

#### 3.4.1.1 Graph Construction steps

The second major step in the process is graph building. This involves constructing the graph from heap dump byte blocks. The first part of this step is the data structure detection, where blocks are parsed from start to finish. The parsing process leaps over blocks by using chunk sizes that are stored in chained chunk headers. Each chunk is then verified for its size, alignment, and the presence of a potential footer. Following this, the pointer detection step is carried out. In this phase, potential pointers are identified using the previously introduced pointer detection algorithm and are added to the graph.

An optional step that can be performed is the chunk pointer reduction. This step removes any blocks that are not Chunk Header Nodes, effectively transforming the graph from a block-based graph to a chunk-based graph. While this step is not mandatory, it can be useful for reducing the scale of the problem. This approach will be extensively used in the machine learning section, as it has been shown that the key block prediction problem is equivalent to a key chunk prediction problem.

#### 3.4.1.2 Graph Annotation

The third major step in the process is graph annotation. In this phase, Value Nodes in the graph are replaced by Key Nodes, utilizing the annotations provided in the JSON annotation file. Additional
annotations, such as SSH STRUCT, can also be added at this stage. Following the completion of
the annotation step, it becomes possible to export the graph for various purposes. The graph can
be exported to file formats like .dot or .gv, which are suitable for visualization or other analytical
tasks.

At this step, the graph is looking similar to the example shown before 3.3.2. Using the pointer
reduction to a chunk-only memory graph, we can obtain something like the following:

<figure><img src="image_14.png" /><figcaption>Figure 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-heapraw.</figcaption></figure>

Note how we can identify some data structures formed by pointer-connected chunks. This is a very interesting property of the memory graph representation, since it allows identifying data structures and their members based only on the shape of connections. This is a very important property that will be used later for feature engineering and embeddings.

3.4.1.3 Custom Graph-Based Embeddings

The fourth step in the workflow involves generating embeddings from the graph. Multiple types of
embeddings can be generated, each serving a unique purpose and offering different insights into
the graph structure. One such embedding is the semantic embedding. This is a general approach
that enriches each node with information related to its graph structure vicinity. It captures the
essence of the node's position and relationships within the graph, making it useful for various
machine learning and analytics tasks.

In addition to semantic embeddings, other types of embeddings can also be generated. For
annotations, such as SSH STRUCT, can also be added at this stage. Following the completion of
the annotation step, it becomes possible to export the graph for various purposes. The graph can
be exported to file formats like .dot or .gv, which are suitable for visualization or other analytical
tasks.

At this step, the graph is looking similar to the example shown before 3.3.2. Using the pointer
reduction to a chunk-only memory graph, we can obtain something like the following:

<figure><img src="image_16.png" /><figcaption>Figure 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-heapraw.</figcaption></figure>

Note how we can identify some data structures formed by pointer-connected chunks. This is a very interesting property of the memory graph representation, since it allows identifying data structures and their members based only on the shape of connections. This is a very important property that will be used later for feature engineering and embeddings.

3.4.1.3 Custom Graph-Based Embeddings

The fourth step in the workflow involves generating embeddings from the graph. Multiple types of
embeddings can be generated, each serving a unique purpose and offering different insights into
the graph structure. One such embedding is the semantic embedding. This is a general approach
that enriches each node with information related to its graph structure vicinity. It captures the
essence of the node's position and relationships within the graph, making it useful for various
machine learning and analytics tasks.

In addition to semantic embeddings, other types of embeddings can also be generated. For
instance, statistical embeddings focus on capturing the statistical properties of the graph. Another interesting type of embedding is the random walk embedding and related version called Node2Vec. This method leverages the random walk algorithm to generate embeddings, capturing the local and global structure of the graph by simulating random paths through it.

Each of these embeddings offers a unique lens through which to analyze and interpret the graph, and the choice of embedding can be tailored to the specific requirements of the task at hand. It's also possible to add additional features like entropy of the chunk start bytes and filtering information.

### 3.4.1.4 Exporting the Graph

The fifth step in the process involves exporting the graph. The graph is exported to a .gv DOT file format. Custom embeddings are integrated into the graph by utilizing the comment fields in a slightly modified stringified JSON format. This approach allows for easy reading of the embeddings associated with each node while maintaining the DOT file as a valid format that can be used with tools and libraries supporting the DOT graph formal.

The DOT (Directed Orthogonal Text) format is a plain text graph description language that is widely used for representing structured information. An example of a memory graph in DOT format without embeddings is provided for reference. In this example, nodes and edges are represented along with their attributes such as color, shape, and labels.

When embeddings are added to the graph, additional comment fields are included in the DOT file nodes. These comment fields contain a JSON string that holds the embedding information for each node. Moreover, the graph starts with a pseudo JSON comment field that contains a serialized JSON object specifying the embedding type and feature names.

Here is an example of a comment field in a node:

```
comment="[0,94918015119368,1,108,108,108,108,108,108,108,1,67,82,139,175,204,...
0,0,2.355388542207534]"
```

Listing 3.25: A comment field example for a node with embedding. Output is cropped.

Below is an example of a memory graph comment field containing a JSON serialized object with embedding type and feature names.

```
comment="{ 'embedding-type': 'chunk-semantic-embedding', 'embedding-fields': ['block_position_in_chunk', 'chn_addr', 'chns_ancestor_1',...,'chns_children_8', 'chunk_byte_size','chunk_number_in_heap','chunk_ptrs','chunk_vns','ptrs_ancestor_1','ptrs_ancestor_2',...,'ptrs_children_8','entropy'] }"
```

Listing 3.26: A memgraph comment field example containing JSON serialized object with embedding type and feature names. Output is cropped.

The inclusion of these comment fields serves multiple purposes. First, it allows for the storage of embeddings along with additional information, making the graph more informative. Second, this format can be easily integrated into Python machine learning pipelines, facilitating the use of the graph in various machine learning tasks. Lastly, the DOT format serves as a standard format for graph representation, making it a versatile choice for both visualization and computational tasks.
instance, statistical embeddings focus on capturing the statistical properties of the graph. Another interesting type of embedding is the random walk embedding and related version called Node2Vec. This method leverages the random walk algorithm to generate embeddings, capturing the local and global structure of the graph by simulating random paths through it.

Each of these embeddings offers a unique lens through which to analyze and interpret the graph, and the choice of embedding can be tailored to the specific requirements of the task at hand. It's also possible to add additional features like entropy of the chunk start bytes and filtering information.

### 3.4.1.4 Exporting the Graph

The fifth step in the process involves exporting the graph. The graph is exported to a .gv DOT file format. Custom embeddings are integrated into the graph by utilizing the comment fields in a slightly modified stringified JSON format. This approach allows for easy reading of the embeddings associated with each node while maintaining the DOT file as a valid format that can be used with tools and libraries supporting the DOT graph formal.

The DOT (Directed Orthogonal Text) format is a plain text graph description language that is widely used for representing structured information. An example of a memory graph in DOT format without embeddings is provided for reference. In this example, nodes and edges are represented along with their attributes such as color, shape, and labels.

When embeddings are added to the graph, additional comment fields are included in the DOT file nodes. These comment fields contain a JSON string that holds the embedding information for each node. Moreover, the graph starts with a pseudo JSON comment field that contains a serialized JSON object specifying the embedding type and feature names.

Here is an example of a comment field in a node:

```json
comment="[0,94918015119368,1,108,108,108,108,108,108,108,1,67,82,139,175,204,...
0,0,2.355388542207534]"
```

Listing 3.25: A comment field example for a node with embedding. Output is cropped.

Below is an example of a memory graph comment field containing a JSON serialized object with embedding type and feature names.

```json
comment="{ 'embedding-type': 'chunk-semantic-embedding', 'embedding-fields': ['
    block_position_in_chunk', 'chn_addr', 'chns_ancestor_1',... 'chns_children_8',
    chunk_byte_size', 'chunk_number_in_heap', 'chunk_ptrs', 'chunk_vns', 'ptrs_ancestor_1
    ','ptrs_ancestor_2',...,'ptrs_children_8','entropy'] }"
```

Listing 3.26: A memgraph comment field example containing JSON serialized object with embedding type and feature names. Output is cropped.

The inclusion of these comment fields serves multiple purposes. First, it allows for the storage of embeddings along with additional information, making the graph more informative. Second, this format can be easily integrated into Python machine learning pipelines, facilitating the use of the graph in various machine learning tasks. Lastly, the DOT format serves as a standard format for graph representation, making it a versatile choice for both visualization and computational tasks.
## 3.5 A wide range of features and embeddings

In the following, we will explore the features and embeddings developed and used in this thesis. We will start by the features and embeddings based on the memory graph characteristics, then we will explore the graph-agnostic embeddings, and finally, we will discuss the machine learning models used for the binary classification task.

### 3.5.1 Embeddings based on custom features

While doing the construction of the graph, we can add some custom features to the nodes. Those features have been developed to embed the unique characteristics of each node of the graph, depending on its type, parent chunk characteristics as well as its vicinity in the memory graph. Those features have been regrouped in several custom embeddings that will be discussed in the following.

#### 3.5.1.1 Remark on the collaborative work

This section focuses on the embeddings developed during a Masterarbeit project around OpenSSH heap dump analysis. Clément Lahoche and the author of the present report have done a collaborative effort on the matter. Since Clément has focused on the embeddings, the following section will not discuss in too many details the embeddings that are already described and analyzed in details by Clément's work. The reader is invited to read his Masterarbeit report [0] for more information. This section includes some elements that are clearly identified as coming from Clément's work.

As a notable difference, the Node2Vec embedding, which is a graph-agnostic embedding, will also be discussed in the following, which is not the case in Clément's thesis. This is because the present report focuses on the machine learning part, and especially on graph representation learning.

#### 3.5.1.2 Semantic graph embedding

The focus of this stage is on semantic embedding, a technique that transforms the graph into a low-dimensional vector space. Each vector encapsulates the local neighborhood of a graph chunk, enabling the application of advanced machine learning methods. The embedding process is intricate, considering both direct and indirect connections to and from each chunk. It starts by counting the number of pointers and chunks directly linked to a specific chunk, and then extends this by recursively exploring deeper layers of connections. A parallel reverse analysis is also conducted to capture child nodes. The outcome is a compact vector that richly represents the chunk's contextual relationships within the graph.

The following algorithm describes the process of generating the semantic embedding for a given chunk:
## 3.5 A wide range of features and embeddings

In the following, we will explore the features and embeddings developed and used in this thesis. We will start by the features and embeddings based on the memory graph characteristics, then we will explore the graph-agnostic embeddings, and finally, we will discuss the machine learning models used for the binary classification task.

### 3.5.1 Embeddings based on custom features

While doing the construction of the graph, we can add some custom features to the nodes. Those features have been developed to embed the unique characteristics of each node of the graph, depending on its type, parent chunk characteristics as well as its vicinity in the memory graph. Those features have been regrouped in several custom embeddings that will be discussed in the following.

#### 3.5.1.1 Remark on the collaborative work

This section focuses on the embeddings developed during a Masterarbeit project around OpenSSH heap dump analysis. Clément Lahoche and the author of the present report have done a collaborative effort on the matter. Since Clément has focused on the embeddings, the following section will not discuss in too many details the embeddings that are already described and analyzed in details by Clément's work. The reader is invited to read his Masterarbeit report [0] for more information. This section includes some elements that are clearly identified as coming from Clément's work.

As a notable difference, the Node2Vec embedding, which is a graph-agnostic embedding, will also be discussed in the following, which is not the case in Clément's thesis. This is because the present report focuses on the machine learning part, and especially on graph representation learning.

#### 3.5.1.2 Semantic graph embedding

The focus of this stage is on semantic embedding, a technique that transforms the graph into a low-dimensional vector space. Each vector encapsulates the local neighborhood of a graph chunk, enabling the application of advanced machine learning methods. The embedding process is intricate, considering both direct and indirect connections to and from each chunk. It starts by counting the number of pointers and chunks directly linked to a specific chunk, and then extends this by recursively exploring deeper layers of connections. A parallel reverse analysis is also conducted to capture child nodes. The outcome is a compact vector that richly represents the chunk's contextual relationships within the graph.

The following algorithm describes the process of generating the semantic embedding for a given chunk:
**Algorithm 12** Generate Ancestor/Children Embedding.

**function** GenerateNeighborsCHN(chunk_node, dir)
    ancestor_nodes ← an empty set
    children ← graph_neighbors_directed(chunk_node, OUT)
    ▷ Get members of the chunk
    **for** child **in** children **do**
        ancestor_nodes.insert(child)
    **end for**
    result ← an empty list
    current_nodes ← an empty set
    **for** _ **in** 0 **to** DEPTH **do**
        current_nodes ← ancestor_nodes
        ancestor_nodes ← an empty set
        nb_chn ← 0
        nb_ptr ← 0
        **for** current_node **in** current_nodes **do**
            **if** node is ChunkHeaderNode **then**
                nb_chn ← nb_dtn + 1
            **else if** node is PointerNode **then**
                nb_ptr ← nb_ptr + 1
            **end if**
            ▷ Get neighbors of the current node
            **for** neighbor **in** graph_neighbors_directed(current_node, dir) **do**
                ancestor_nodes.insert(neighbor)
            ▷ Add neighbors to the next ancestor nodes
        **end for**
        **end for**
        result.append nb_chn
        result.append nb_ptr
    ▷ Add number of data structures
    ▷ Add number of pointers
    **end for**
    **return** result
**end function**

Note that this algorithm is taken from Lahoche, from his Masterarbeit report [0]. It has been
developed and implemented as a collaborative effort on this project.

The embedding algorithm is applied to each chunk in the graph, exploring up to a predefined
depth, generally 8, which is a hyperparameter of this embedding. This results in a 32-unit
embedding, broken down into 8 units each for ancestor pointers, ancestor chunks, child pointers,
and child chunks. Basic chunk attributes like block position, byte size, and number of pointers
and value nodes are also included, bringing the total embedding size to 37 units. Despite its
comprehensiveness, the embedding has limitations, such as the potential for noise from value
nodes and the complexity of capturing intricate relationships.

A way that have been used extensively, to both reduce the number of nodes and to improve
the quality of the embeddings, is to reduce the graph to a chunk-only graph. This is done by
removing all the nodes that are not chunk header nodes. It is a very interesting approach, since it
allows to reduce the scale of the problem by a factor of 10, and also allows focusing on the data
structures, which are the most interesting nodes to embed. This approach will be used in the
machine learning section, since we have shifted the focus from block to chunk prediction.
**Algorithm 12** Generate Ancestor/Children Embedding.

**function** GenerateNeighborsCHN(chunk_node, dir)
    ancestor_nodes ← an empty set
    children ← graph_neighbors_directed(chunk_node, OUT)
    ▷ Get members of the chunk
    **for** child **in** children **do**
        ancestor_nodes.insert(child)
    **end for**
    result ← an empty list
    current_nodes ← an empty set
    **for** _ **in** 0 **to** DEPTH **do**
        current_nodes ← ancestor_nodes
        ancestor_nodes ← an empty set
        nb_chn ← 0
        nb_ptr ← 0
        **for** current_node **in** current_nodes **do**
            **if** node is ChunkHeaderNode **then**
                nb_chn ← nb_dtn + 1
            **else if** node is PointerNode **then**
                nb_ptr ← nb_ptr + 1
            **end if**
            ▷ Get neighbors of the current node
            **for** neighbor **in** graph_neighbors_directed(current_node, dir) **do**
                ancestor_nodes.insert(neighbor)
            ▷ Add neighbors to the next ancestor nodes
            **end for**
            **end for**
            result.append nb_chn
            result.append nb_ptr
        ▷ Add number of data structures
        ▷ Add number of pointers
    **end for**
    **return** result
**end function**

Note that this algorithm is taken from Lahoche, from his Masterarbeit report [0]. It has been
developed and implemented as a collaborative effort on this project.

The embedding algorithm is applied to each chunk in the graph, exploring up to a predefined
depth, generally 8, which is a hyperparameter of this embedding. This results in a 32-unit
embedding, broken down into 8 units each for ancestor pointers, ancestor chunks, child pointers,
and child chunks. Basic chunk attributes like block position, byte size, and number of pointers
and value nodes are also included, bringing the total embedding size to 37 units. Despite its
comprehensiveness, the embedding has limitations, such as the potential for noise from value
nodes and the complexity of capturing intricate relationships.

A way that have been used extensively, to both reduce the number of nodes and to improve
the quality of the embeddings, is to reduce the graph to a chunk-only graph. This is done by
removing all the nodes that are not chunk header nodes. It is a very interesting approach, since it
allows to reduce the scale of the problem by a factor of 10, and also allows focusing on the data
structures, which are the most interesting nodes to embed. This approach will be used in the
machine learning section, since we have shifted the focus from block to chunk prediction.
### 3.5.1.3 Semantic features from essential chunks attributes

Every chunk in the heap dump comes with fundamental attributes that provide insights on its structure and content. These attributes are not limited to the primary chunk nodes but are also inherited by value and pointer nodes, which are subcomponents of a chunk. The key attributes include the block's position within the chunk, the chunk's byte size, the total number of pointers and value nodes in the chunk, and the chunk's index in the heap. These details collectively offer a thorough understanding of each chunk's makeup and its relative position in the heap.

### 3.5.1.4 Statistical Embedding

Statistical embeddings serve as a powerful tool for reducing high-dimensional data while preserving essential patterns and probabilistic relationships. One key technique employed is the use of n-gram values, specifically focusing on bit combinations to manage dimensionality. This approach aligns with the primary goal of identifying SSH keys, which inherently display a wide range of frequencies. Various n-gram sizes are utilized, including 1-gram, 2-gram, 3-gram, up to 8-gram, with the latter contributing significantly to capturing broader contextual patterns.

In addition to n-grams, other statistical metrics like mean, standard deviation, MAD, skewness, kurtosis, and Shannon entropy are incorporated. These metrics offer a multi-faceted view of the data, aiding in the identification of SSH keys. However, chunks with a standard deviation of zero are excluded from the analysis, as they are unlikely to contribute to the identification of random patterns like SSH keys. These skipped values are replaced with NaN values in embedding comment of nodes, that needs to be handled by the machine learning pipeline. It has been chosen to replace those values with zeros.

Finally, the statistical embedding vector for each chunk is constructed by combining n-gram values and these additional statistical metrics. The vector also includes basic chunk information, resulting in a comprehensive vector that encapsulates the chunk's characteristics.

### 3.5.1.5 Start-bytes Embedding

In addition to the aforementioned embeddings, a simpler approach was implemented to serve as a baseline for comparison. This method focuses solely on the initial bytes of each chunk for vectorization. The sample vector is initialized with basic chunk information and then populated with the first bytes of the chunk, up to a predefined limit. If the chunk has fewer starting bytes than the predefined limit, zeros are added to fill the remaining positions. This straightforward approach provides a straightforward embedding, suitable for comparative evaluations with more intricate embeddings.

## 3.5.2 Embedding transformations depending on the model

When it comes to feeding embeddings into machine learning models, the shape and size of the embeddings need to be tailored to fit the model's requirements. For classic machine learning algorithms like Random Forest, the requirement is that the embedding matrices must be of a fixed, predefined size. This presents a unique challenge when working with graph embeddings, as graphs usually have a variable number of nodes. To address this, padding is added to the embedding matrices to ensure they all match the size of the largest graph. In contrast, Graph
### 3.5.1.3 Semantic features from essential chunks attributes

Every chunk in the heap dump comes with fundamental attributes that provide insights on its structure and content. These attributes are not limited to the primary chunk nodes but are also inherited by value and pointer nodes, which are subcomponents of a chunk. The key attributes include the block's position within the chunk, the chunk's byte size, the total number of pointers and value nodes in the chunk, and the chunk's index in the heap. These details collectively offer a thorough understanding of each chunk's makeup and its relative position in the heap.

### 3.5.1.4 Statistical Embedding

Statistical embeddings serve as a powerful tool for reducing high-dimensional data while preserving essential patterns and probabilistic relationships. One key technique employed is the use of n-gram values, specifically focusing on bit combinations to manage dimensionality. This approach aligns with the primary goal of identifying SSH keys, which inherently display a wide range of frequencies. Various n-gram sizes are utilized, including 1-gram, 2-gram, 3-gram, up to 8-gram, with the latter contributing significantly to capturing broader contextual patterns.

In addition to n-grams, other statistical metrics like mean, standard deviation, MAD, skewness, kurtosis, and Shannon entropy are incorporated. These metrics offer a multi-faceted view of the data, aiding in the identification of SSH keys. However, chunks with a standard deviation of zero are excluded from the analysis, as they are unlikely to contribute to the identification of random patterns like SSH keys. These skipped values are replaced with NaN values in embedding comment of nodes, that needs to be handled by the machine learning pipeline. It has been chosen to replace those values with zeros.

Finally, the statistical embedding vector for each chunk is constructed by combining n-gram values and these additional statistical metrics. The vector also includes basic chunk information, resulting in a comprehensive vector that encapsulates the chunk's characteristics.

### 3.5.1.5 Start-bytes Embedding

In addition to the aforementioned embeddings, a simpler approach was implemented to serve as a baseline for comparison. This method focuses solely on the initial bytes of each chunk for vectorization. The sample vector is initialized with basic chunk information and then populated with the first bytes of the chunk, up to a predefined limit. If the chunk has fewer starting bytes than the predefined limit, zeros are added to fill the remaining positions. This straightforward approach provides a straightforward embedding, suitable for comparative evaluations with more intricate embeddings.

## 3.5.2 Embedding transformations depending on the model

When it comes to feeding embeddings into machine learning models, the shape and size of the embeddings need to be tailored to fit the model's requirements. For classic machine learning algorithms like Random Forest, the requirement is that the embedding matrices must be of a fixed, predefined size. This presents a unique challenge when working with graph embeddings, as graphs usually have a variable number of nodes. To address this, padding is added to the embedding matrices to ensure they all match the size of the largest graph. In contrast, Graph
Convolutional Networks (GCN) offer more flexibility in this aspect. GCNs are capable of handling variable-size embedding matrices as long as the number of features is fixed. This eliminates the need for padding the matrices, which is advantageous as it simplifies the preprocessing steps.

### 3.5.2.1 Node filtering to feature

On the topic of node filtering in the context of chunk memory graphs, it's important to note that active rebalancing isn't performed, despite the number of positive nodes (key chunks) being substantially lower than the number of negative nodes (non-key chunks). The rationale behind this choice is to enable models to learn from complete graphs. This is particularly relevant for Graph Convolutional Networks, which are capable of handling graphs of variable sizes. The goal is for the models to be able to identify key chunks even in completely unlabeled memory graphs. The ability of GCNs to process variable-size graphs makes them especially suitable for this kind of task, as it allows the model to learn from the full structure of the graph without the need for compromising the integrity of the data through techniques like rebalancing.

### 3.5.3 Graph-agnostic Embeddings

Unlike our previous embeddings, which were developed manually to suit the intricacies of chunk graphs, there are also pre-existing, generalized graph embeddings. These graph-agnostic embeddings offer the benefit of being applicable to a wide range of graphs without requiring specific customization based on the characteristics of the underlying data.

#### 3.5.3.1 RandomWalk

The RandomWalk algorithm offers a straightforward approach to graph embedding. It simulates random walks starting from each node in the graph and uses these walks to create vector representations of the nodes. One of the advantages of RandomWalk is its simplicity, both in terms of implementation and interpretation. The algorithm excels at capturing local structures within the graph, making it particularly effective for tasks such as community detection and link prediction. However, its focus on local characteristics means that it might not capture global properties of the graph as effectively.

#### 3.5.3.2 Node2Vec

Node2Vec extends the capabilities of the RandomWalk algorithm by introducing additional parameters that allow for a more nuanced exploration of the graph. This makes Node2Vec more versatile than RandomWalk, enabling it to capture both local and global graph structures. Because of its flexibility, Node2Vec is well-suited for a range of applications including the specific task of providing an embedding for the node of memory graphs. While its versatility is a strong point, it comes at the cost of increased computational complexity due to the introduction of several hyperparameters.

**Hyperparameters:**

* **p**: The return parameter, which controls the likelihood of the walk returning to the node it just left.
Convolutional Networks (GCN) offer more flexibility in this aspect. GCNs are capable of handling variable-size embedding matrices as long as the number of features is fixed. This eliminates the need for padding the matrices, which is advantageous as it simplifies the preprocessing steps.

### 3.5.2.1 Node filtering to feature

On the topic of node filtering in the context of chunk memory graphs, it's important to note that active rebalancing isn't performed, despite the number of positive nodes (key chunks) being substantially lower than the number of negative nodes (non-key chunks). The rationale behind this choice is to enable models to learn from complete graphs. This is particularly relevant for Graph Convolutional Networks, which are capable of handling graphs of variable sizes. The goal is for the models to be able to identify key chunks even in completely unlabeled memory graphs. The ability of GCNs to process variable-size graphs makes them especially suitable for this kind of task, as it allows the model to learn from the full structure of the graph without the need for compromising the integrity of the data through techniques like rebalancing.

### 3.5.3 Graph-agnostic Embeddings

Unlike our previous embeddings, which were developed manually to suit the intricacies of chunk graphs, there are also pre-existing, generalized graph embeddings. These graph-agnostic embeddings offer the benefit of being applicable to a wide range of graphs without requiring specific customization based on the characteristics of the underlying data.

#### 3.5.3.1 RandomWalk

The RandomWalk algorithm offers a straightforward approach to graph embedding. It simulates random walks starting from each node in the graph and uses these walks to create vector representations of the nodes. One of the advantages of RandomWalk is its simplicity, both in terms of implementation and interpretation. The algorithm excels at capturing local structures within the graph, making it particularly effective for tasks such as community detection and link prediction. However, its focus on local characteristics means that it might not capture global properties of the graph as effectively.

#### 3.5.3.2 Node2Vec

Node2Vec extends the capabilities of the RandomWalk algorithm by introducing additional parameters that allow for a more nuanced exploration of the graph. This makes Node2Vec more versatile than RandomWalk, enabling it to capture both local and global graph structures. Because of its flexibility, Node2Vec is well-suited for a range of applications including the specific task of providing an embedding for the node of memory graphs. While its versatility is a strong point, it comes at the cost of increased computational complexity due to the introduction of several hyperparameters.

**Hyperparameters:**

* **p**: The return parameter, which controls the likelihood of the walk returning to the node it just left.
* **q**: The in-out parameter, which differentiates between inward and outward nodes in the walk.

* **Length of Walk**: Determines the length of each random walk.

* **Number of Walks**: Specifies the number of walks to initiate from each node.

Note that the two last hyperparameters have a huge impact on the performance of the algorithm. These hyperparameters play a crucial role in shaping the behavior of the Node2Vec algorithm. Specifically, the return and in-out parameters help guide the random walks in a way that allows the algorithm to capture different types of structural information from the graph. The length and number of walks, meanwhile, impact the granularity and quality of the embeddings generated.

## 3.6 Machine Learning Binary Classification

Binary classification is a type of machine learning task where the model is trained to differentiate between two classes. In the context of key chunk prediction, binary classification serves to identify whether a given chunk is a "key chunk" or not. Successfully predicting key chunks is crucial as it leads to a 100% successful key retrieval rate. This is because, in our case, all keys are situated at the beginning of a chunk, and no chunk contains more than one key. Various machine learning models, ranging from classic approaches to more modern methods like Graph Convolutional Networks (GCNs), have been employed for this task.

### 3.6.1 Classic Models of Machine Learning

For baseline comparisons, we have experimented with classic machine learning models including Random Forest, Logistic Regression, and the SGD Classifier. These models serve as a well-studied and understood starting point for our classification problem, providing a frame of reference against which more complex models can be compared.

#### 3.6.1.1 Random Forest

Random Forest is an ensemble learning method that operates by constructing multiple decision trees during training and outputs the class that is the mode of the classes of the individual trees for classification tasks. It is highly flexible and can handle a wide range of data types, making it a strong candidate for various use cases, including key chunk prediction.

**Strong and Weak Points:**

* **Strong**: The model is robust to overfitting and can handle high dimensional data well.

* **Weak**: Random Forest models can be computationally expensive and may require a long training time, especially for larger datasets.

As often with models, Random Forest has a bunch of hyperparameters:

**Hyperparameters:**
* **q**: The in-out parameter, which differentiates between inward and outward nodes in the walk.

* **Length of Walk**: Determines the length of each random walk.

* **Number of Walks**: Specifies the number of walks to initiate from each node.

Note that the two last hyperparameters have a huge impact on the performance of the algorithm. These hyperparameters play a crucial role in shaping the behavior of the Node2Vec algorithm. Specifically, the return and in-out parameters help guide the random walks in a way that allows the algorithm to capture different types of structural information from the graph. The length and number of walks, meanwhile, impact the granularity and quality of the embeddings generated.

## 3.6 Machine Learning Binary Classification

Binary classification is a type of machine learning task where the model is trained to differentiate between two classes. In the context of key chunk prediction, binary classification serves to identify whether a given chunk is a "key chunk" or not. Successfully predicting key chunks is crucial as it leads to a 100% successful key retrieval rate. This is because, in our case, all keys are situated at the beginning of a chunk, and no chunk contains more than one key. Various machine learning models, ranging from classic approaches to more modern methods like Graph Convolutional Networks (GCNs), have been employed for this task.

### 3.6.1 Classic Models of Machine Learning

For baseline comparisons, we have experimented with classic machine learning models including Random Forest, Logistic Regression, and the SGD Classifier. These models serve as a well-studied and understood starting point for our classification problem, providing a frame of reference against which more complex models can be compared.

#### 3.6.1.1 Random Forest

Random Forest is an ensemble learning method that operates by constructing multiple decision trees during training and outputs the class that is the mode of the classes of the individual trees for classification tasks. It is highly flexible and can handle a wide range of data types, making it a strong candidate for various use cases, including key chunk prediction.

**Strong and Weak Points:**

* **Strong**: The model is robust to overfitting and can handle high dimensional data well.

* **Weak**: Random Forest models can be computationally expensive and may require a long training time, especially for larger datasets.

As often with models, Random Forest has a bunch of hyperparameters:

**Hyperparameters:**
* **n_estimators**: Number of trees in the forest.

* **max_features**: The number of features to consider when looking for the best split.

* **max_depth**: The maximum depth of the tree.

* **min Samples Split**: The minimum number of samples required to split an internal node.

* **min Samples Leaf**: The minimum number of samples required to be at a leaf node.

We have used the implementation of Random Forest available in the Scikit-learn library [0].

### 3.6.1.2 Logistic Regression

Logistic Regression is a statistical model commonly used for binary classification tasks. It models the log-odds of the probability of the event occurring as a linear combination of the predictor variables. The model is particularly effective when the probability of the outcome (dependent variable) can be expressed as a logistic function of the predictor (independent variable).

**Strong and Weak Points:** Logistic Regression is straightforward to implement and understand, making it a good starting point for many classification problems. However, its simplicity is both a strength and a weakness; it might not perform well when the relationship between the variables is not log-linear or when the dataset has high dimensionality.

**Hyperparameters:**

* **C**: Inverse of regularization strength; smaller values specify stronger regularization.

* **solver**: Algorithm to use for optimization, such as 'liblinear' or ' saga'.

* **max_iter**: Maximum number of iterations for the solver to converge.

We have relied on the Logistic Regression implementation available in the Scikit-learn library for our experiments[0], using the default hyperparameters.

### 3.6.1.3 SGD Classifier

The Stochastic Gradient Descent (SGD) Classifier is a linear classifier optimized by stochastic gradient descent. It is especially useful for large-scale and sparse machine learning problems. The SGD Classifier can approximate other types of linear classifiers like Logistic Regression and Support Vector Machines.

**Strong and Weak Points:** SGD Classifier is computationally efficient, making it well-suited for large datasets. However, it requires careful tuning of its hyperparameters and might be sensitive to feature scaling.

**Hyperparameters:**

* **alpha**: Regularization term that discourages large coefficients to prevent overfitting.

* **loss**: Specifies the loss function to be used, such as 'hinge' for SVM or 'log' for logistic regression.
* **n_estimators**: Number of trees in the forest.

* **max_features**: The number of features to consider when looking for the best split.

* **max_depth**: The maximum depth of the tree.

* **min Samples Split**: The minimum number of samples required to split an internal node.

* **min samples leaf**: The minimum number of samples required to be at a leaf node.

We have used the implementation of Random Forest available in the Scikit-learn library [0].

### 3.6.1.2 Logistic Regression

Logistic Regression is a statistical model commonly used for binary classification tasks. It models the log-odds of the probability of the event occurring as a linear combination of the predictor variables. The model is particularly effective when the probability of the outcome (dependent variable) can be expressed as a logistic function of the predictor (independent variable).

**Strong and Weak Points:** Logistic Regression is straightforward to implement and understand, making it a good starting point for many classification problems. However, its simplicity is both a strength and a weakness; it might not perform well when the relationship between the variables is not log-linear or when the dataset has high dimensionality.

**Hyperparameters:**

* **C**: Inverse of regularization strength; smaller values specify stronger regularization.

* **solver**: Algorithm to use for optimization, such as 'liblinear' or ' saga'.

* **max_iter**: Maximum number of iterations for the solver to converge.

We have relied on the Logistic Regression implementation available in the Scikit-learn library for our experiments[0], using the default hyperparameters.

### 3.6.1.3 SGD Classifier

The Stochastic Gradient Descent (SGD) Classifier is a linear classifier optimized by stochastic gradient descent. It is especially useful for large-scale and sparse machine learning problems. The SGD Classifier can approximate other types of linear classifiers like Logistic Regression and Support Vector Machines.

**Strong and Weak Points:** SGD Classifier is computationally efficient, making it well-suited for large datasets. However, it requires careful tuning of its hyperparameters and might be sensitive to feature scaling.

**Hyperparameters:**

* **alpha**: Regularization term that discourages large coefficients to prevent overfitting.

* **loss**: Specifies the loss function to be used, such as 'hinge' for SVM or 'log' for logistic regression.
* **max_iter**: Maximum number of passes over the training data.

* **learning_rate**: The learning rate schedule, could be 'constant', 'optimal', 'invscaling', or 'adaptive'.

For the SGD Classifier as well, we used the Scikit-learn implementation [0].

### 3.6.2 Graph Convolutional Networks (GCN)

As GCNs have already been introduced in the background section, this part will primarily focus on our specific implementation and the variants of GCN models employed for the task of key chunk prediction.

GCNs are a specialized form of neural networks designed to operate directly on graphs. One of their main characteristics is their ability to capture the graph's structural information. They accomplish this by using edge connectivity information, either from an adjacency matrix or an edge list, as part of their input. This makes them particularly effective for tasks involving irregular data structures like the memory graphs discussed previously.

We used the PyTorch Geometric library for the development of our GCN models. This library offers a robust set of tools and abstractions, making it easier to construct custom graph-based neural networks [0].

GCNs excel at capturing the topological features of graphs, making them a strong candidate for our task of key chunk prediction. However, they can be computationally intensive, especially for large graphs, and also require careful tuning of hyperparameters for optimal performance.

#### 3.6.2.1 Very Simple GCN

The Very Simple GCN model is a minimalist approach, capturing the essential features of a Graph Convolutional Network. This model consists of just one graph convolution layer followed by a single fully connected layer. The convolution layer takes the input features and transforms them into a 16-dimensional space.

After the graph convolution operation, a ReLU (Rectified Linear Unit) activation function is applied to the output. ReLU is defined as $f(x) = max(0, x)$, replacing all negative values in the tensor with zeros. In the context of GCNs, ReLU is commonly used to introduce non-linearity into the model. It enables the network to learn from the error and make adjustments, making it more capable of handling complex, non-linear relationships in the graph data.

Finally, the output from the ReLU activation is passed through a fully connected layer to produce the final output for classification. Due to its simplicity, this model is computationally efficient but may not capture complex graph structures effectively.

#### 3.6.2.2 Simple GCN Models

The Simple GCN model, or LessSimplifiedGNN, is a step-up in complexity from the very simplified version. It incorporates two graph convolutional layers, doubling the depth of the network. The first convolution transforms the input features to a 12-dimensional space, and the second one
* **max_iter**: Maximum number of passes over the training data.

* **learning_rate**: The learning rate schedule, could be 'constant', 'optimal', 'invscaling', or 'adaptive'.

For the SGD Classifier as well, we used the Scikit-learn implementation [0].

## 3.6.2 Graph Convolutional Networks (GCN)

As GCNs have already been introduced in the background section, this part will primarily focus on our specific implementation and the variants of GCN models employed for the task of key chunk prediction.

GCNs are a specialized form of neural networks designed to operate directly on graphs. One of their main characteristics is their ability to capture the graph's structural information. They accomplish this by using edge connectivity information, either from an adjacency matrix or an edge list, as part of their input. This makes them particularly effective for tasks involving irregular data structures like the memory graphs discussed previously.

We used the PyTorch Geometric library for the development of our GCN models. This library offers a robust set of tools and abstractions, making it easier to construct custom graph-based neural networks [0].

GCNs excel at capturing the topological features of graphs, making them a strong candidate for our task of key chunk prediction. However, they can be computationally intensive, especially for large graphs, and also require careful tuning of hyperparameters for optimal performance.

### 3.6.2.1 Very Simple GCN

The Very Simple GCN model is a minimalist approach, capturing the essential features of a Graph Convolutional Network. This model consists of just one graph convolution layer followed by a single fully connected layer. The convolution layer takes the input features and transforms them into a 16-dimensional space.

After the graph convolution operation, a ReLU (Rectified Linear Unit) activation function is applied to the output. ReLU is defined as $f(x) = max(0, x)$, replacing all negative values in the tensor with zeros. In the context of GCNs, ReLU is commonly used to introduce non-linearity into the model. It enables the network to learn from the error and make adjustments, making it more capable of handling complex, non-linear relationships in the graph data.

Finally, the output from the ReLU activation is passed through a fully connected layer to produce the final output for classification. Due to its simplicity, this model is computationally efficient but may not capture complex graph structures effectively.

### 3.6.2.2 Simple GCN Models

The Simple GCN model, or LessSimplifiedGNN, is a step-up in complexity from the very simplified version. It incorporates two graph convolutional layers, doubling the depth of the network. The first convolution transforms the input features to a 12-dimensional space, and the second one
further transforms these 12-dimensional vectors into 24 dimensions. Two fully connected layers follow, ultimately producing the final output. This model is capable of capturing more complex features in the graph but is computationally more demanding than the simpler model.

### 3.6.2.3 First GCN Model

The First GCN model is the first version that was actually implemented and tested for the task. It's a more complex architecture optimized for higher performance. It consists of two graph convolution layers that transform the input features first into a 16-dimensional and then into a 32-dimensional space. Following these, the network contains three fully connected layers. These layers are intended to capture more intricate patterns in the data. Failed attempts to scale the model computation speed by delegating the fully connected layers to the GPU were made, but ultimately, the model was too memory intensive to be trained on the GPU. This model is designed for capturing more nuanced relationships in the graph but at the cost of higher computational requirements.

### 3.6.3 The Impact of Complexity

The complexity of a model is a double-edged sword when it comes to performance metrics like precision and recall. On one hand, more complex models with additional layers or more neurons can capture intricate patterns in the graph data, potentially improving precision by accurately identifying key chunks. On the other hand, the complexity often leads to overfitting, especially when the training dataset is small or lacks diversity. Overfitting can adversely affect recall, as the model might become too specialized in recognizing training graphs and fail to generalize well to unseen data.

In the case of Graph Convolutional Networks (GCNs), the non-linear transformations and multiple layers can allow the network to learn highly specialized features, which is excellent for achieving high precision. However, these can be detrimental to recall if the model becomes so tailored to the training data that it fails to identify key chunks in new, unseen graphs.

The impact of the model's complexity also varies with the number of input graphs. For datasets with few graphs, a simpler model is often more appropriate to prevent overfitting. In contrast, when numerous diverse graphs are available for training, a more complex model can be employed to capture the rich set of features inherent in the data, thereby potentially improving both precision and recall.

Therefore, the choice of model complexity should be carefully considered, weighing its impact on performance metrics and the size and diversity of the available training data. This is why more complex GCN models have also been implemented and tested.

### 3.6.4 Understanding Dropout in GCNs

Dropout is a regularization technique used in neural networks, including Graph Convolutional Networks (GCNs) and Convolutional Neural Networks (CNNs), to prevent overfitting. The dropout layer randomly sets a fraction of the input units to 0 during training, which helps to make the model more robust and improves generalization. In the ML pipelines developed in Python, a dropout rate of 0.5 is used, meaning approximately 50% of the neurons will be turned off during
further transforms these 12-dimensional vectors into 24 dimensions. Two fully connected layers follow, ultimately producing the final output. This model is capable of capturing more complex features in the graph but is computationally more demanding than the simpler model.

### 3.6.2.3 First GCN Model

The First GCN model is the first version that was actually implemented and tested for the task. It's a more complex architecture optimized for higher performance. It consists of two graph convolution layers that transform the input features first into a 16-dimensional and then into a 32-dimensional space. Following these, the network contains three fully connected layers. These layers are intended to capture more intricate patterns in the data. Failed attempts to scale the model computation speed by delegating the fully connected layers to the GPU were made, but ultimately, the model was too memory intensive to be trained on the GPU. This model is designed for capturing more nuanced relationships in the graph but at the cost of higher computational requirements.

### 3.6.3 The Impact of Complexity

The complexity of a model is a double-edged sword when it comes to performance metrics like precision and recall. On one hand, more complex models with additional layers or more neurons can capture intricate patterns in the graph data, potentially improving precision by accurately identifying key chunks. On the other hand, the complexity often leads to overfitting, especially when the training dataset is small or lacks diversity. Overfitting can adversely affect recall, as the model might become too specialized in recognizing training graphs and fail to generalize well to unseen data.

In the case of Graph Convolutional Networks (GCNs), the non-linear transformations and multiple layers can allow the network to learn highly specialized features, which is excellent for achieving high precision. However, these can be detrimental to recall if the model becomes so tailored to the training data that it fails to identify key chunks in new, unseen graphs.

The impact of the model's complexity also varies with the number of input graphs. For datasets with few graphs, a simpler model is often more appropriate to prevent overfitting. In contrast, when numerous diverse graphs are available for training, a more complex model can be employed to capture the rich set of features inherent in the data, thereby potentially improving both precision and recall.

Therefore, the choice of model complexity should be carefully considered, weighing its impact on performance metrics and the size and diversity of the available training data. This is why more complex GCN models have also been implemented and tested.

### 3.6.4 Understanding Dropout in GCNs

Dropout is a regularization technique used in neural networks, including Graph Convolutional Networks (GCNs) and Convolutional Neural Networks (CNNs), to prevent overfitting. The dropout layer randomly sets a fraction of the input units to 0 during training, which helps to make the model more robust and improves generalization. In the ML pipelines developed in Python, a dropout rate of 0.5 is used, meaning approximately 50% of the neurons will be turned off during
each forward pass. This section will discuss the effect of dropout on the model's performance and the intuition behind it.

### 3.6.4.1 Effect on Binary Classification

In a binary classification problem, dropout can have several effects:

* **Reduced Overfitting:** By randomly deactivating neurons, the model is less likely to rely on any single feature, making it generalize better to unseen data. This is expected to reduce overfitting and thus improve the model's performance, especially the recall of the positive class.

* **Increased Robustness:** Dropout can make the model more robust to noise in the training data.

* **Variable Performance:** While dropout can improve generalization, it may also lead to increased variance in the model's predictions, especially if the dropout rate is too high.

In the code of some GCN models implemented, dropout is applied after the activation functions of the GCN layers and the first fully connected layer:

$$ 
\begin{aligned}
x &= Figm(x) \\
x &= self.dropout(x)
\end{aligned}
 $$

This is a common practice as it allows the model to learn more robust features. However, the dropout rate and its placement in the architecture are yet other hyperparameters that may need to be tuned for optimal performance. Since we already have a large number of hyperparameters, we will not tune the dropout rate in this thesis.

### 3.6.4.2 Batch Normalization

The code also includes Batch Normalization layers, denoted by `self.bn1` and `self.bn2`. These layers normalize the features to have zero mean and unit variance, which can accelerate training and provide some regularization effect, complementing the dropout layers.

### 3.6.5 More Complex GCN Models

In an effort to enhance the performance of our initial GCN models, we explored more complex architectures. The motivation behind increasing the complexity was to evaluate whether additional layers or techniques could lead to improved performance metrics such as precision and recall. These advanced models have been tested against the simpler GCN models to determine their effectiveness.

#### 3.6.5.1 GCN with Dropout and Batch Normalization

Building upon the First GCN model, we incorporated dropout and batch normalization layers. Dropout is employed to mitigate the issue of overfitting, especially relevant for complex models
each forward pass. This section will discuss the effect of dropout on the model's performance and the intuition behind it.

### 3.6.4.1 Effect on Binary Classification

In a binary classification problem, dropout can have several effects:

* **Reduced Overfitting:** By randomly deactivating neurons, the model is less likely to rely on any single feature, making it generalize better to unseen data. This is expected to reduce overfitting and thus improve the model's performance, especially the recall of the positive class.

* **Increased Robustness:** Dropout can make the model more robust to noise in the training data.

* **Variable Performance:** While dropout can improve generalization, it may also lead to increased variance in the model's predictions, especially if the dropout rate is too high.

In the code of some GCN models implemented, dropout is applied after the activation functions of the GCN layers and the first fully connected layer:

$$x = Figm(x)$$

$$x = self.dropout(x)$$

This is a common practice as it allows the model to learn more robust features. However, the dropout rate and its placement in the architecture are yet other hyperparameters that may need to be tuned for optimal performance. Since we already have a large number of hyperparameters, we will not tune the dropout rate in this thesis.

### 3.6.4.2 Batch Normalization

The code also includes Batch Normalization layers, denoted by `self.bn1` and `self.bn2`. These layers normalize the features to have zero mean and unit variance, which can accelerate training and provide some regularization effect, complementing the dropout layers.

### 3.6.5 More Complex GCN Models

In an effort to enhance the performance of our initial GCN models, we explored more complex architectures. The motivation behind increasing the complexity was to evaluate whether additional layers or techniques could lead to improved performance metrics such as precision and recall. These advanced models have been tested against the simpler GCN models to determine their effectiveness.

#### 3.6.5.1 GCN with Dropout and Batch Normalization

Building upon the First GCN model, we incorporated dropout and batch normalization layers. Dropout is employed to mitigate the issue of overfitting, especially relevant for complex models
trained on limited data. With a dropout rate of 0.5 after each ReLU activation, we were able to
regulate the model's complexity during training.

Batch normalization, on the other hand, aims to accelerate training and stabilize the learn-
ing process. By normalizing the output features of each layer, batch normalization helps in
alleviating internal covariance shift, making the model training more resilient to the choice of
hyperparameters.

This version of the model aligns closely with the First GCN model, but the addition of dropout and batch normalization layers offer greater robustness, especially when training on imbalanced or smaller datasets.

3.6.5.2 Advanced GCN

The Advanced GCN model represents the most intricate architecture we have experimented with.
This model introduces several additional components compared to the simpler models.

The Advanced GCN consists of three Graph Convolution layers, followed by Batch Normalization layers. The initial Graph Convolution layer transforms the input features into a 32-dimensional space, which is then normalized using BatchNorm1d. The second and third Graph Convolution layers further increase the dimensions to 64 and 128, respectively, also followed by batch normalization steps. These layers aim to capture more complex features from the graph structure.

ReLU (Rectified Linear Unit) activation functions are applied after each batch normalization, introducing non-linearity to the model and helping to capture intricate relationships in the data. Additionally, dropout layers with a rate of 0.5 are placed after each ReLU activation to mitigate the risk of overfitting.

After the Graph Convolution layers, the architecture includes a series of fully connected layers that transform the 128-dimensional feature vector into a 256-dimensional space, which is further compressed into 128 and then 64 dimensions. Finally, the model outputs a vector of dimensions corresponding to the number of classes. Each of these fully connected layers is followed by ReLU activations, except for the final output layer.

- **Graph Conv Layers**: Three layers with dimensions 32, 64, and 128

- **Batch Normalization**: Applied after each Graph Conv layer

- **Fully Connected Layers**: Layers with dimensions 256, 128, and 64

- **Dropout**: Applied after each ReLU activation with a rate of 0.5

In summary, the model is engineered to capture more complex relationships in the data, at the cost of increased computational requirements and a higher risk of overfitting, especially when trained on small or less diverse datasets. The dropout and batch normalization layers are integrated to combat overfitting to some extent.

The current chapter has been an overview of the dataset, development environment, and tools used for this thesis. In the next chapter, we will dive deeper into developed programs, experimentations conducted and subsequent results.
trained on limited data. With a dropout rate of 0.5 after each ReLU activation, we were able to
regulate the model's complexity during training.

Batch normalization, on the other hand, aims to accelerate training and stabilize the learn-
ing process. By normalizing the output features of each layer, batch normalization helps in
alleviating internal covariance shift, making the model training more resilient to the choice of
hyperparameters.

This version of the model aligns closely with the First GCN model, but the addition of dropout and batch normalization layers offer greater robustness, especially when training on imbalanced or smaller datasets.

3.6.5.2 Advanced GCN

The Advanced GCN model represents the most intricate architecture we have experimented with.
This model introduces several additional components compared to the simpler models.

The Advanced GCN consists of three Graph Convolution layers, followed by Batch Normalization layers. The initial Graph Convolution layer transforms the input features into a 32-dimensional space, which is then normalized using BatchNorm1d. The second and third Graph Convolution layers further increase the dimensions to 64 and 128, respectively, also followed by batch normalization steps. These layers aim to capture more complex features from the graph structure.

ReLU (Rectified Linear Unit) activation functions are applied after each batch normalization, introducing non-linearity to the model and helping to capture intricate relationships in the data. Additionally, dropout layers with a rate of 0.5 are placed after each ReLU activation to mitigate the risk of overfitting.

After the Graph Convolution layers, the architecture includes a series of fully connected layers that transform the 128-dimensional feature vector into a 256-dimensional space, which is further compressed into 128 and then 64 dimensions. Finally, the model outputs a vector of dimensions corresponding to the number of classes. Each of these fully connected layers is followed by ReLU activations, except for the final output layer.

- **Graph Conv Layers**: Three layers with dimensions 32, 64, and 128

- **Batch Normalization**: Applied after each Graph Conv layer

- **Fully Connected Layers**: Layers with dimensions 256, 128, and 64

- **Dropout**: Applied after each ReLU activation with a rate of 0.5

In summary, the model is engineered to capture more complex relationships in the data, at
the cost of increased computational requirements and a higher risk of overfitting, especially
when trained on small or less diverse datasets. The dropout and batch normalization layers are
integrated to combat overfitting to some extent.

The current chapter has been an overview of the dataset, development environment, and tools used for this thesis. In the next chapter, we will dive deeper into developed programs, experimentations conducted and subsequent results.
# 4 Results

The following section describes the experimental setup, the used and generated datasets as well as parameters to conclude with the experimental results achieved.

## 4.1 Developed programs

Many programs have been developed for the need of the present thesis. Early data exploration scripts have paved the way towards efficient highly parallel programs in both Rust and Python for data analysis, graph and embedding generation of ML and DL tested on different models and contexts. All the necessary concepts and methods have been introduced previously, so it is now time to present those main program in details.

### 4.1.1 Mem2Graph

The present report has already presented the *Mem2Graph* program throughout the heap dump memory parsing algorithm, graph construction and embeddings. This program has been developed in Rust and is an active collaboration between the author and Clément Lahoche, another PhDTrack student at Passau. The program is available on GitHub at https://github.com/passau-masterarbeit-2023/mem2graph.

The program is composed of several layers that build on top of each other. The first layer is dedicated into loading a RAW heap dump file with its annotation JSON file, performs some checks and prepare the data for further analysis. The next one performs the graph construction following the algorithms introduced in the Methods section. Another layer performs some annotations of the nodes. The final layer is more versatile and dependent on the input program parameters. For the need of this report, several pipelines of memgraph with and without embeddings have been added, namely *graph* and *graph-with-embedding-comments*. The first pipeline doesn't perform any embedding and export the memory graph to a text file following the DOT format [0]. The second pipeline performs the same operations, but also exports the memory graph with the embeddings as comments in the DOT file.

Since the prediction effort is focused on memory chunks, this embedding is generally called with the `-no-value-node` parameter, which transform the memory graph from a graph of blocks of 8 bytes, into a memory graph of memory chunks, connected by their pointers inside their respective user data space. Several chunk node embeddings have been implemented, and the user can choose which one to use. The chunk node embeddings are the following: *chunk-semantic-embedding*, *chunk-statistic-embedding*, and *chunk-start-bytes-embedding*.

### 4.1.2 Machine Learning Pipelines Runner

When working with machine learning, Python is a dominant language, benefiting from a rich ecosystem of libraries and frameworks.

The project leverages a wide range of Python libraries to build comprehensive machine learning pipelines:
# 4 Results

The following section describes the experimental setup, the used and generated datasets as well as parameters to conclude with the experimental results achieved.

## 4.1 Developed programs

Many programs have been developed for the need of the present thesis. Early data exploration scripts have paved the way towards efficient highly parallel programs in both Rust and Python for data analysis, graph and embedding generation of ML and DL tested on different models and contexts. All the necessary concepts and methods have been introduced previously, so it is now time to present those main program in details.

### 4.1.1 Mem2Graph

The present report has already presented the *Mem2Graph* program throughout the heap dump memory parsing algorithm, graph construction and embeddings. This program has been developed in Rust and is an active collaboration between the author and Clément Lahoche, another PhDTrack student at Passau. The program is available on GitHub at https://github.com/passau-masterarbeit-2023/mem2graph.

The program is composed of several layers that build on top of each other. The first layer is dedicated into loading a RAW heap dump file with its annotation JSON file, performs some checks and prepare the data for further analysis. The next one performs the graph construction following the algorithms introduced in the Methods section. Another layer performs some annotations of the nodes. The final layer is more versatile and dependent on the input program parameters. For the need of this report, several pipelines of memgraph with and without embeddings have been added, namely *graph* and *graph-with-embedding-comments*. The first pipeline doesn't perform any embedding and export the memory graph to a text file following the DOT format [0]. The second pipeline performs the same operations, but also exports the memory graph with the embeddings as comments in the DOT file.

Since the prediction effort is focused on memory chunks, this embedding is generally called with the `-no-value-node` parameter, which transform the memory graph from a graph of blocks of 8 bytes, into a memory graph of memory chunks, connected by their pointers inside their respective user data space. Several chunk node embeddings have been implemented, and the user can choose which one to use. The chunk node embeddings are the following: *chunk-semantic-embedding*, *chunk-statistic-embedding*, and *chunk-start-bytes-embedding*.

### 4.1.2 Machine Learning Pipelines Runner

When working with machine learning, Python is a dominant language, benefiting from a rich ecosystem of libraries and frameworks.

The project leverages a wide range of Python libraries to build comprehensive machine learning pipelines:
* NetworkX for graph-based data structures and algorithms.

* PyGraphviz for graph visualization.

* Torch for tensor computations and building neural networks.

* Scikit-learn for classical machine learning algorithms.

* Pandas for data manipulation and analysis.

* NumPy for numerical computations.

* Matplotlib for data visualization.

* Torch-Geometric for Geometric Deep Learning extensions for PyTorch.

The program encompasses a variety of machine learning models to compare how different models react to the embeddings and representations developed earlier. It includes classical machine learning models from the Scikit-learn library, such as Random Forest, Stochastic Gradient Descent (SGD), and Logistic Regression. These models serve a point of comparison since they don't rely on graph-based data structures and algorithms.

The program also includes Graph Convolutional Network (GCN) models built on top of PyTorch and Torch-Geometric. These models are more complex and powerful, leveraging the graph structure and embeddings to achieve better results. Those models specifically leverage graph-based embeddings and input data, generated using the Node2Vec algorithm to create dense and continuous node features that can be used for subsequent analysis or machine learning tasks.

**Main Pipelines:** The program is organized around three main pipelines:

1. **GCN Pipeline**: For Graph Convolutional Network models, built using libraries such as Torch and Torch-Geometric.

2. **Classical ML Pipeline**: Leveraging algorithms like Random Forest, SGD, and Logistic Regression from Scikit-learn.

3. **Feature Evaluation Pipeline**: Primarily aimed at evaluating the quality and importance of generated features or graph embeddings.

### 4.1.3 Other programs

A lot of other programs have been developed for the need of this thesis, but they are not as important as the ones presented above. Those scripts and short program have been developed for several purposes:

* **Data exploration**: Several scripts have been developed to explore the data, and to understand the structure of the heap dump files, the annotations, and the memory graphs.

* **Heap Dump parsing algorithm testers**: Several scripts have been developed to test the heap dump parsing algorithms, and to ensure that the algorithms are working as intended on all possible situations.
* NetworkX for graph-based data structures and algorithms.

* PyGraphviz for graph visualization.

* Torch for tensor computations and building neural networks.

* Scikit-learn for classical machine learning algorithms.

* Pandas for data manipulation and analysis.

* NumPy for numerical computations.

* Matplotlib for data visualization.

* Torch-Geometric for Geometric Deep Learning extensions for PyTorch.

The program encompasses a variety of machine learning models to compare how different models react to the embeddings and representations developed earlier. It includes classical machine learning models from the Scikit-learn library, such as Random Forest, Stochastic Gradient Descent (SGD), and Logistic Regression. These models serve a point of comparison since they don't rely on graph-based data structures and algorithms.

The program also includes Graph Convolutional Network (GCN) models built on top of PyTorch and Torch-Geometric. These models are more complex and powerful, leveraging the graph structure and embeddings to achieve better results. Those models specifically leverage graph-based embeddings and input data, generated using the Node2Vec algorithm to create dense and continuous node features that can be used for subsequent analysis or machine learning tasks.

**Main Pipelines:** The program is organized around three main pipelines:

1. **GCN Pipeline**: For Graph Convolutional Network models, built using libraries such as Torch and Torch-Geometric.

2. **Classical ML Pipeline**: Leveraging algorithms like Random Forest, SGD, and Logistic Regression from Scikit-learn.

3. **Feature Evaluation Pipeline**: Primarily aimed at evaluating the quality and importance of generated features or graph embeddings.

### 4.1.3 Other programs

A lot of other programs have been developed for the need of this thesis, but they are not as important as the ones presented above. Those scripts and short program have been developed for several purposes:

* **Data exploration**: Several scripts have been developed to explore the data, and to understand the structure of the heap dump files, the annotations, and the memory graphs.

* **Heap Dump parsing algorithm testers**: Several scripts have been developed to test the heap dump parsing algorithms, and to ensure that the algorithms are working as intended on all possible situations.
* **Graph and embedding generation testers:** Others have been developed to test the graph and embedding generation algorithms, and to ensure that the algorithms are working as intended on all possible situations.

* **Result visualization, analysis and latex generators:** Later in the report, the results will be presented and discussed. Several scripts have been developed to generate the latex tables and plots, and to analyze the results.

All those programs represent a consequent amount of work, and have been invaluable to the success of this thesis. Using CLOC (Count Lines of Code), a command-line utility that can count lines of code in various languages, the following statistics have been obtained:

1

cloc mem2graph research-base predicting_ssh_key_masterarbeit_report
phdtrack_serverScripts phdtrack_project_3 memory_graph_gcn
data_processing_masterarbeit --exclude-dir=.venv

Listing 4.1: Command used to count the number of lines of code in the *phdtrack* directory, containing the repositories of the present thesis.

The following table shows the number of lines of code for each programming language used in the present thesis:

<table><caption>Table 4.1: Code Statistics for Masterarbeit</caption><thead><tr><td>Language</td><td>Files</td><td>Blank Lines</td><td>Comments</td><td>Code Lines</td></tr></thead><tbody><tr><td>CSV</td><td>867</td><td>0</td><td>0</td><td>158305697</td></tr><tr><td>Text</td><td>25</td><td>272</td><td>0</td><td>50073</td></tr><tr><td>Python</td><td>132</td><td>2326</td><td>2682</td><td>8050</td></tr><tr><td>Rust</td><td>50</td><td>1343</td><td>1149</td><td>6823</td></tr><tr><td>TeX</td><td>28</td><td>963</td><td>141</td><td>6636</td></tr><tr><td>Markdown</td><td>33</td><td>1016</td><td>0</td><td>2375</td></tr><tr><td>JSON</td><td>1345</td><td>1</td><td>0</td><td>1677</td></tr><tr><td>Jupyter Notebook</td><td>2</td><td>0</td><td>1811</td><td>381</td></tr><tr><td>Nix</td><td>12</td><td>50</td><td>31</td><td>290</td></tr><tr><td>TOML</td><td>1</td><td>2</td><td>1</td><td>22</td></tr><tr><td>Bourne Shell</td><td>3</td><td>8</td><td>8</td><td>18</td></tr><tr><td>make</td><td>1</td><td>8</td><td>3</td><td>18</td></tr><tr><td>Dockerfile</td><td>1</td><td>1</td><td>0</td><td>2</td></tr></tbody></table>

In the context of this thesis, three programming languages stand out for their specialized roles: Python, Rust, and Nix. Python is predominantly used for the machine learning pipeline, offering ease of use and a rich ecosystem for data science tasks. Rust serves as the backbone for the Mem2Graph program, providing the efficiency required for graph construction and manipulation. Nix is employed for package management and building, ensuring reproducibility across different computing environments. These languages complement each other well, with Python offering high-level abstractions for machine learning, and Rust providing low-level control for performance-critical tasks. Additionally, CSV files are utilized to store model results. TeX is used for generating this report, highlighting the diverse yet complementary set of tools and languages employed in this research.
* **Graph and embedding generation testers:** Others have been developed to test the graph and embedding generation algorithms, and to ensure that the algorithms are working as intended on all possible situations.

* **Result visualization, analysis and latex generators:** Later in the report, the results will be presented and discussed. Several scripts have been developed to generate the latex tables and plots, and to analyze the results.

All those programs represent a consequent amount of work, and have been invaluable to the success of this thesis. Using CLOC (Count Lines of Code), a command-line utility that can count lines of code in various languages, the following statistics have been obtained:

1

cloc mem2graph research-base predicting_ssh_key_masterarbeit_report
phdtrack_serverScripts phdtrack_project_3 memory_graph_gcn
data_processing_masterarbeit --exclude-dir=.venv

Listing 4.1: Command used to count the number of lines of code in the phdtrack directory, containing the repositories of the present thesis.

The following table shows the number of lines of code for each programming language used in the present thesis:

<table><caption>Table 4.1: Code Statistics for Masterarbeit</caption><thead><tr><td>Language</td><td>Files</td><td>Blank Lines</td><td>Comments</td><td>Code Lines</td></tr></thead><tbody><tr><td>CSV</td><td>867</td><td>0</td><td>0</td><td>158305697</td></tr><tr><td>Text</td><td>25</td><td>272</td><td>0</td><td>50073</td></tr><tr><td>Python</td><td>132</td><td>2326</td><td>2682</td><td>8050</td></tr><tr><td>Rust</td><td>50</td><td>1343</td><td>1149</td><td>6823</td></tr><tr><td>TeX</td><td>28</td><td>963</td><td>141</td><td>6636</td></tr><tr><td>Markdown</td><td>33</td><td>1016</td><td>0</td><td>2375</td></tr><tr><td>JSON</td><td>1345</td><td>1</td><td>0</td><td>1677</td></tr><tr><td>Jupyter Notebook</td><td>2</td><td>0</td><td>1811</td><td>381</td></tr><tr><td>Nix</td><td>12</td><td>50</td><td>31</td><td>290</td></tr><tr><td>TOML</td><td>1</td><td>2</td><td>1</td><td>22</td></tr><tr><td>Bourne Shell</td><td>3</td><td>8</td><td>8</td><td>18</td></tr><tr><td>make</td><td>1</td><td>8</td><td>3</td><td>18</td></tr><tr><td>Dockerfile</td><td>1</td><td>1</td><td>0</td><td>2</td></tr></tbody></table>

In the context of this thesis, three programming languages stand out for their specialized roles: Python, Rust, and Nix. Python is predominantly used for the machine learning pipeline, offering ease of use and a rich ecosystem for data science tasks. Rust serves as the backbone for the Mem2Graph program, providing the efficiency required for graph construction and manipulation. Nix is employed for package management and building, ensuring reproducibility across different computing environments. These languages complement each other well, with Python offering high-level abstractions for machine learning, and Rust providing low-level control for performance-critical tasks. Additionally, CSV files are utilized to store model results. TeX is used for generating this report, highlighting the diverse yet complementary set of tools and languages employed in this research.
## 4.2 Experimental Setup

The experimental setup serves as the backbone of this research, providing a structured framework for conducting large-scale experiments on the server. This section delves into the intricacies of the setup, detailing the steps involved and the tools used. It also includes selected program output logs to offer a granular view of the program parameters, environment, and usage.

The elements discussed in this section are not merely illustrative; they offer invaluable insights into the challenges encountered during the experiments. These details are particularly crucial when discussing the large-scale experiments, as they provide a comprehensive understanding of the various facets involved.

The final experiments were conducted in a systematic manner, following these steps:

1. **Data Cleaning:** The original Zenodo dataset was cleaned to produce a RAW heap dump dataset, serving as the foundational data for the experiments.

2. **Graph and Embedding Generation:** The Mem2Graph Rust program was employed to generate graphs along with their embeddings. A Python launcher script facilitated the generation of multiple memgraph datasets, each with varying combinations of program parameters.

3. **Data Preloading and Validation:** A sanity check Python program was used for data preload- ing and validation, ensuring the integrity and consistency of the data before proceeding to the experimental phase.

4. **ML and DL GCN Pipelines:** The main Python program was responsible for the seamless launching of data science tasks, machine learning training, and model evaluation. It was designed to cover a predefined range of parameters and model hyperparameters.

5. **Result Collection and Evaluation:** The final step involved the collection, evaluation, and visualization of the results. Error handling mechanisms were in place to make necessary corrections and prepare for the next iteration of experiments. This step also facilitated the confrontation of hypotheses and research questions.

Initial small-scale tests were conducted on a laptop to validate the programs and their results. The final, large-scale experiments were carried out on the Drogon server, equipped with 80 threads and 256 GB of RAM. The computational resources provided by the University of Passau have been invaluable for conducting these experiments, sometimes running for several days straight.

### 4.2.1 Generation of the memgraph datasets

Using Mem2Graph powerful features, it is possible to generate several memgraph datasets with different parameters. The following command has been used to generate 6 memgraph datasets, each containing 26202 graphs, for a total of 157212 graphs. Those datasets account for different chunk node embeddings and a potential additional filtering feature. The command is run on the Drogon server, with 80 threads.

1

```
[2023-10-24T20:42:44 UTC][INFO mem_to_graph::exe_pipeLine::pipeline] OK [t: worker
-63] [N*202 / 26202 files] [fid: 8683-1650977906] (Nb samples: 0)
```
## 4.2 Experimental Setup

The experimental setup serves as the backbone of this research, providing a structured framework for conducting large-scale experiments on the server. This section delves into the intricacies of the setup, detailing the steps involved and the tools used. It also includes selected program output logs to offer a granular view of the program parameters, environment, and usage.

The elements discussed in this section are not merely illustrative; they offer invaluable insights into the challenges encountered during the experiments. These details are particularly crucial when discussing the large-scale experiments, as they provide a comprehensive understanding of the various facets involved.

The final experiments were conducted in a systematic manner, following these steps:

1. **Data Cleaning:** The original Zenodo dataset was cleaned to produce a RAW heap dump dataset, serving as the foundational data for the experiments.

2. **Graph and Embedding Generation:** The Mem2Graph Rust program was employed to generate graphs along with their embeddings. A Python launcher script facilitated the generation of multiple memgraph datasets, each with varying combinations of program parameters.

3. **Data Preloading and Validation:** A sanity check Python program was used for data preload- ing and validation, ensuring the integrity and consistency of the data before proceeding to the experimental phase.

4. **ML and DL GCN Pipelines:** The main Python program was responsible for the seamless launching of data science tasks, machine learning training, and model evaluation. It was designed to cover a predefined range of parameters and model hyperparameters.

5. **Result Collection and Evaluation:** The final step involved the collection, evaluation, and visualization of the results. Error handling mechanisms were in place to make necessary corrections and prepare for the next iteration of experiments. This step also facilitated the confrontation of hypotheses and research questions.

Initial small-scale tests were conducted on a laptop to validate the programs and their results. The final, large-scale experiments were carried out on the Drogon server, equipped with 80 threads and 256 GB of RAM. The computational resources provided by the University of Passau have been invaluable for conducting these experiments, sometimes running for several days straight.

### 4.2.1 Generation of the memgraph datasets

Using Mem2Graph powerful features, it is possible to generate several memgraph datasets with different parameters. The following command has been used to generate 6 memgraph datasets, each containing 26202 graphs, for a total of 157212 graphs. Those datasets account for different chunk node embeddings and a potential additional filtering feature. The command is run on the Drogon server, with 80 threads.

1

```
[2023-10-24T20:42:44 UTC][INFO mem_to_graph::exe_pipeLine::pipeline] OK [t: worker
-63] [N*202 / 26202 files] [fid: 8683-1650977906] (Nb samples: 0)
```
2

[2023-10-24T20:42:44 UTC] [INFO mem_to_graph::graph_data::heap_dump_data] FILE heap dump raw file path: "/root/phdtrack/phdtrack_data_clean/Performance Test/V_8_1_P1 /32/8794-1650977906-heapraw"

3

[2023-10-24T20:42:44 UTC] [INFO mem_to_graph::exe_pipeLine::pipeline] OK [t: worker -63] [N*203 / 26202 files] [fid: 8794-1650977906] (Nb samples: 0)

4

[2023-10-24T20:42:44 UTC] [INFO mem_to_graph::exe_pipeLine::pipeline] TIME [total pipeline time: 114.84s]

5

100% | ########################################### | 6/6 [1:07:15<00:00, 672.62s/it]

6

Finished! Total time: hours: 1, minutes: 7, seconds: 15 (Drogon Server)

Listing 4.2: Sample of final logs of the Mem2Graph program, after generating 6 memgraph datasets from the cleaned heap dump dataset.

It took a little more than an hour to generate 6 memgraph datasets, each containing 26202 graphs. The total number of graphs generated is 157212. The generated memgraph datasets are stored in the data/ directory, as follows:

<figure><img src="image_15.png" /><figcaption>Figure 4.1: Illustration of the Data Directory Structure</figcaption></figure>

As one can see, the dataset directory names are composed with the most important Mem2Graph program parameters, responsible for some feature and embedding generations. The -e flag, short for -entropy-filter is responsible for the filtering using the Shannon entropy, the -s for -chunk-byte-size-filter for chunk byte size filtering. The -c, -graph-comment-embedding-type controls the custom embedding being save alongside each node in the generated .GV memgraph files.

4.2.2 Sanity checking and preloading the generated memgraph datasets

Loading the graph from DOT files into NetworkX graph in Python is a resource intensive operation that consumes all the available computing power on all tested platforms (laptop, servers). It takes several dozens of seconds up to a minute to load a memory graph containing only around 1000 chunk nodes. It has been experimented that saving those loaded graphs using the *pickle* python library allows to perform checks while loading the graph, add more information about each graph. The subsequent retrieval of the graph is much faster, and allows to perform the sanity checks before any further processing. So to verify the memory graph dataset generation as
well as transforming DOT files into pre-saved NetworkX graph, a sanity checking script has been
developed.

Below is a sample of the logs generated by the sanity check script:

* Running program...
Passed program params:
param[0]: src/sanity_check_gv_files.py
param[1]: -k
Parsed program params:
keep_old_output: True
skip_dir_starting_with_number: None
dry_run: False
* Now, performing data loading and sanity checks...
* Looking for Mem2Graph dataset directories in /root/phdtrack/mem2graph/data...
* Skipping .gitignore...
* Found 6 Mem2Graph dataset directories.
[...]
Loading graphs: 100%|##########| 26201/26202 [3:22:17<00:00, 1.17it/s]
Loading graphs: 100%|##########| 26202/26202 [3:22:25<00:00, 3.19s/it]
Loading graphs: 100%|##########| 26202/26202 [3:22:25<00:00, 2.16it/s]
* Checking embedding length of graphs in /root/phdtrack/mem2graph/data/5_graph_with_embedding_comments_-v_-a_chunk-header-node_-c_chunk-start-bytes-embedding_-e_only-max-entropy_-s_activation...
-> [x] 26202 graphs in /root/phdtrack/mem2graph/data/5_graph_with_embeding_comments_-v_-a_chunk-header-node_-c_chunk-start-bytes-embedding_-e_only-max-entropy_-s_activation have been loaded and checked.
-> [_] 0 graphs in /root/phdtrack/mem2graph/data/5_graph_with_embeding_commments_-v_-a_chunk-header-node_-c_chunk-start-bytes-embedding_-e_only-max-entropy_-s_activation have been skipped (deleted).
[x] 157212 total graphs in the input mem2graph dataset dir paths have been loaded and checked.
[_] 0 total graphs in the input mem2graph dataset dir paths have been skipped (deleted).
<END> Program took: 42626.062309 total sec (11h 50m 26s)

<caption>Listing 4.3: Result logs of the memory_graph_gcn/src/sanity_check_gv_files.py program.</caption>

The sanity checking file can be considered very long to run, having taken almost 12 hours straight, but it is a necessary step to ensure the quality of the generated memgraph datasets. It is also a good way to check the validity of the generated embeddings, and to ensure that the graphs are re-exported as NetworkX graphs that can be loaded much faster than the original DOT files.

4.2.3 Launching the experiments

Two pass of experiments have been conducted, with the exact same parameters and input
memgraph dataset. Contrary to expectations, the experiments were much faster on the laptop
that on the Drogon server.

* Time take for the experiments on the laptop: 12h 31m 53s

* Time take for the experiments on the Drogon server: 29h 17m 57s

The experiments have been launched using the following command (here, on Drogon server):
well as transforming DOT files into pre-saved NetworkX graph, a sanity checking script has been
developed.

Below is a sample of the logs generated by the sanity check script:

* Running program...
Passed program params:
param[0]: src/sanity_check_gv_files.py
param[1]: -k
Parsed program params:
keep_old_output: True
skip_dir_starting_with_number: None
dry_run: False
* Now, performing data loading and sanity checks...
* Looking for Mem2Graph dataset directories in /root/phdtrack/mem2graph/data...
* Skipping .gitignore...
* Found 6 Mem2Graph dataset directories.
[...]
Loading graphs: 100%|##########| 26201/26202 [3:22:17<00:00, 1.17it/s]
Loading graphs: 100%|##########| 26202/26202 [3:22:25<00:00, 3.19s/it]
Loading graphs: 100%|##########| 26202/26202 [3:22:25<00:00, 2.16it/s]
* Checking embedding length of graphs in /root/phdtrack/mem2graph/data/5_graph_with_embedding_comments_-v_-a_chunk-header-node_-c_chunk-start-bytes-embedding_-e_only-max-entropy_-s_activation...
-> [x] 26202 graphs in /root/phdtrack/mem2graph/data/5_graph_with_embeding_commments_-v_-a_chunk-header-node_-c_chunk-start-bytes-embedding_-e_only-max-entropy_-s_activation have been loaded and checked.
-> [_] 0 graphs in /root/phdtrack/mem2graph/data/5_graph_with_embeding_commments_-v_-a_chunk-header-node_-c_chunk-start-bytes-embedding_-e_only-max-entropy_-s_activation have been skipped (deleted).
[x] 157212 total graphs in the input mem2graph dataset dir paths have been loaded and checked.
[_] 0 total graphs in the input mem2graph dataset dir paths have been skipped (deleted).
<END> Program took: 42626.062309 total sec (11h 50m 26s)

<caption>Listing 4.3: Result logs of the memory_graph_gcn/src/sanity_check_gv_files.py program.</caption>

The sanity checking file can be considered very long to run, having taken almost 12 hours straight, but it is a necessary step to ensure the quality of the generated memgraph datasets. It is also a good way to check the validity of the generated embeddings, and to ensure that the graphs are re-exported as NetworkX graphs that can be loaded much faster than the original DOT files.

4.2.3 Launching the experiments

Two pass of experiments have been conducted, with the exact same parameters and input
memgraph dataset. Contrary to expectations, the experiments were much faster on the laptop
that on the Drogon server.

* Time take for the experiments on the laptop: 12h 31m 53s

• Time take for the experiments on the Drogon server: 29h 17m 57s

The experiments have been launched using the following command (here, on Drogon server):
1

```
nohup python src/main_gcn.py -i /root/phdtrack/phdtrack\_data\_clean/ -p gcn-pipeline classic-ml-pipeline feature-evaluation-pipeline -b 6 -a -q -n 16 > output\_ml\_ 2>&1 &
```

<caption>Listing 4.4: Command used to launch final experiments, on Drogon server.</caption>

Using nohup and redirecting the output to a log file allows the experiments to run in the background and enables the retrieval of the output at a later time. The command specifies the input directory containing the annotated DOT (.gv) graph directory with the -i flag. All three pipelines are chosen: gcn-pipeline, classic-ml-pipeline, and feature-evaluation-pipeline, as indicated by the -p flag. The batch size for parallel processing is set to 6 using the -b flag, and the -a flag indicates the use of all available Mem2Graph datasets. The -q flag enables quiet mode for Node2Vec, and the -n flag specifies the use of 16 input graphs.

### 4.2.4 Dealing with hyperparameter tuning

In the quest to optimize the performance of both ML and DL models, hyperparameter tuning plays a crucial role. This section elaborates on the various strategies and tools employed for hyperparameter tuning in this research.

* **Precise Command Lines for Tuning:** The compute instances and experiment parameters can be finely tuned using precise command-line options. This flexibility allows for a more targeted approach to model optimization, enabling the user to specify various hyperparameters and settings right from the terminal.

* **Python Program for Experiment Launch:** A dedicated Python program has been developed to automate the launching of ML, GCN and FE pipelines. This program takes different hyperparameters as input and initiates the corresponding experiments, thereby streamlining the entire process.

* **Automatic Logging in CSV:** All the results from each experiment, along with the hyperparameters used, are automatically logged into a CSV file. This facilitates easy tracking and comparison of different model configurations and their corresponding performances.

* **Timestamps and Duration Steps:** Each experiment is meticulously logged with precise timestamps and duration steps. This includes the time taken for generating embeddings, as well as the time required for the training and testing phases. Such detailed logging aids in identifying bottlenecks and optimizing the pipeline further.

* **Extensive Experimentation:** Over the course of this research, thousands of experiments have been conducted. These experiments span a wide range of parameters, models, and embeddings, providing a comprehensive understanding of the model behaviors and their sensitivities to different hyperparameters.

* **Automated Result Analysis and Visualization:** To aid in the interpretation of the extensive experimental results, automated scripts have been developed for result analysis and visualization. These scripts generate various plots and metrics that provide insights into the performance and reliability of the different models and configurations.

Of all the parameters, the model types, their respective hyperparameters, the combinations of possible embeddings with their own parameters, and the number of input graphs are the
1

```
nohup python src/main_gcn.py -i /root/phdtrack/phdtrack\_data\_clean/ -p gcn-pipeline classic-ml-pipeline feature-evaluation-pipeline -b 6 -a -q -n 16 > output\_ml\_ 2>&1 &
```

Listing 4.4: Command used to launch final experiments, on Drogon server.

Using nohup and redirecting the output to a log file allows the experiments to run in the background and enables the retrieval of the output at a later time. The command specifies the input directory containing the annotated DOT (.gv) graph directory with the -i flag. All three pipelines are chosen: gcn-pipeline, classic-ml-pipeline, and feature-evaluation-pipeline, as indicated by the -p flag. The batch size for parallel processing is set to 6 using the -b flag, and the -a flag indicates the use of all available Mem2Graph datasets. The -q flag enables quiet mode for Node2Vec, and the -n flag specifies the use of 16 input graphs.

### 4.2.4 Dealing with hyperparameter tuning

In the quest to optimize the performance of both ML and DL models, hyperparameter tuning plays a crucial role. This section elaborates on the various strategies and tools employed for hyperparameter tuning in this research.

* **Precise Command Lines for Tuning:** The compute instances and experiment parameters can be finely tuned using precise command-line options. This flexibility allows for a more targeted approach to model optimization, enabling the user to specify various hyperparameters and settings right from the terminal.

* **Python Program for Experiment Launch:** A dedicated Python program has been developed to automate the launching of ML, GCN and FE pipelines. This program takes different hyperparameters as input and initiates the corresponding experiments, thereby streamlining the entire process.

* **Automatic Logging in CSV:** All the results from each experiment, along with the hyperparameters used, are automatically logged into a CSV file. This facilitates easy tracking and comparison of different model configurations and their corresponding performances.

* **Timestamps and Duration Steps:** Each experiment is meticulously logged with precise timestamps and duration steps. This includes the time taken for generating embeddings, as well as the time required for the training and testing phases. Such detailed logging aids in identifying bottlenecks and optimizing the pipeline further.

* **Extensive Experimentation:** Over the course of this research, thousands of experiments have been conducted. These experiments span a wide range of parameters, models, and embeddings, providing a comprehensive understanding of the model behaviors and their sensitivities to different hyperparameters.

* **Automated Result Analysis and Visualization:** To aid in the interpretation of the extensive experimental results, automated scripts have been developed for result analysis and visualization. These scripts generate various plots and metrics that provide insights into the performance and reliability of the different models and configurations.

Of all the parameters, the model types, their respective hyperparameters, the combinations of possible embeddings with their own parameters, and the number of input graphs are the
most important. All those parameters explains the large number of experiments that have been conducted, and the need for a precise and automated way to launch them.

#### 4.2.4.1 Limited number of input graphs due to compute time and memory usage

It also explains why the input number of memgraphs has been limited to 16, as it is already a very large number of experiments to run. Each file taking several dozens of seconds to be transformed into an embedding, this represents around 10 minutes just for the embedding generation phase, for each pipeline. With more than 600 pipelines to run, this already represents dozens of hours of compute time. Depending on the context and model, the training and evaluation phases are also time-consuming, and the more input graphs there are, the longer it takes to train and test the model.

The compute time is not the only issue with dealing with a large number of input graphs. The memory usage is also a problem, as the memory usage increases linearly with the number of input graphs. The parallel processing of only 6 pipelines having 16 memgraphs as inputs generally represents between 16 and 50 GB of RAM usage, depending on the model and the embedding used. Due to this, all tests consisting of trying to run this already limited number of input graphs on the GPU have failed, as the GPU memory is not sufficient to handle the memory usage of the program. The slowness of the CPU alongside memory bandwidth limitations are the main bottlenecks of the program, and the main reasons why the number of input graphs has been limited to 16.

#### 4.2.4.2 Parallel launch of experiments for hyperparameters tuning

To maximize efficiency and expedite the research process, a Python program was developed to launch multiple experiments in parallel. This approach allows for simultaneous testing of various input graphs, machine learning and deep learning models, embedding techniques, and hyperparameters. By leveraging parallel computing, the program significantly reduces the time required for extensive experimentation, thereby accelerating the overall research and development cycle.

Below are the hyperparameters used during the main experiments, as stored in the hyperparams.json file:

```json
{
    "node2vec dimensions_range": [128],
    "node2vecru walk_length_range": [16],
    "node2vecnum walks_range": [50],
    "node2vecpp range": [0.5, 1.0, 1.5],
    "node2veqq range": [0.5, 1.0, 1.5],
    "node2ve window_range": [10],
    "node2vebatch words_range": [8],
    "node2ve workers_range": [16],
    "randomforest trees_range": [100, 500, 1000],
    "gcn training_epochs_range": [20]
}
```

<caption>Listing 4.5: JSON hyperparameters used during experiments</caption>

Even though the above JSON file shows the hyperparameters selected for the large scale final experiments, pre-experiments have been previously conducted to find some usable values. Due to compute time limitations, the ranges of hyperparameters have been limited to a few values,
most important. All those parameters explains the large number of experiments that have been conducted, and the need for a precise and automated way to launch them.

#### 4.2.4.1 Limited number of input graphs due to compute time and memory usage

It also explains why the input number of memgraphs has been limited to 16, as it is already a very large number of experiments to run. Each file taking several dozens of seconds to be transformed into an embedding, this represents around 10 minutes just for the embedding generation phase, for each pipeline. With more than 600 pipelines to run, this already represents dozens of hours of compute time. Depending on the context and model, the training and evaluation phases are also time-consuming, and the more input graphs there are, the longer it takes to train and test the model.

The compute time is not the only issue with dealing with a large number of input graphs. The memory usage is also a problem, as the memory usage increases linearly with the number of input graphs. The parallel processing of only 6 pipelines having 16 memgraphs as inputs generally represents between 16 and 50 GB of RAM usage, depending on the model and the embedding used. Due to this, all tests consisting of trying to run this already limited number of input graphs on the GPU have failed, as the GPU memory is not sufficient to handle the memory usage of the program. The slowness of the CPU alongside memory bandwidth limitations are the main bottlenecks of the program, and the main reasons why the number of input graphs has been limited to 16.

#### 4.2.4.2 Parallel launch of experiments for hyperparameters tuning

To maximize efficiency and expedite the research process, a Python program was developed to launch multiple experiments in parallel. This approach allows for simultaneous testing of various input graphs, machine learning and deep learning models, embedding techniques, and hyperparameters. By leveraging parallel computing, the program significantly reduces the time required for extensive experimentation, thereby accelerating the overall research and development cycle.

Below are the hyperparameters used during the main experiments, as stored in the hyperparams.json file:

```json
{
    "node2vec dimensions_range": [128],
    "node2vec_walk_length_range": [16],
    "node2vec_num_walks_range": [50],
    "node2vec_p_range": [0.5, 1.0, 1.5],
    "node2vec_q_range": [0.5, 1.0, 1.5],
    "node2vec_windows_range": [10],
    "node2vec_batch_words_range": [8],
    "node2vec_workers_range": [16],
    "randomforestTrees_range": [100, 500, 1000],
    "gcn_training_epochs_range": [20]
}
```

<caption>Listing 4.5: JSON hyperparameters used during experiments</caption>

Even though the above JSON file shows the hyperparameters selected for the large scale final experiments, pre-experiments have been previously conducted to find some usable values. Due to compute time limitations, the ranges of hyperparameters have been limited to a few values,
and the number of input graphs has been limited to 16. The following JSON file shows the hyperparameters used during the pre-experiments:

```json
{
  "node2vec升高范围": [16, 32, 128],
  "node2vec walks范围": [16, 32],
  "node2vec num_walks_range": [50, 100],
  "node2vec_p_range": [0.5, 1.0, 1.5],
  "node2vec_q_range": [0.5, 1.0, 1.5],
  "node2vec 八川范围": [10, 20],
  "node2vec_batch_words_range": [4, 8, 16],
  "node2vec_workers_range": [16, 32],
  "randomforest Trees_range": [100, 500, 1000],
  "gcn _training_epochs_range": [5, 10, 20]
}
```

<caption>Listing 4.6: JSON hyperparameters used during experiments</caption>

Several observations were made during the early experiments concerning the impact of different hyperparameters on the model's performance, especially concerning the Node2Vec parameters.
The following observations were made:

*   **Walk Length and Number of Walks:** Increasing the number of walks and the walk length generally improved the model's performance. However, this came at the cost of significantly increased computational time. The benefits plateaued after reaching a certain threshold.

*   **Number of Dimensions:** A higher number of dimensions generally led to better results. Lower values were found to be detrimental to the model's performance, indicating the importance of this parameter.

*   **Impact of *p* and *q*:** The parameters *p* and *q* had an unpredictable impact on the model's performance. While some combinations seemed to yield better results, no clear pattern was observed, making these parameters challenging to optimize.

*   **Batch Word Range:** The range of batch words had a minimal impact on the model's performance. As a result, an intermediate value was selected for this parameter to balance computational efficiency and performance.

These observations provide valuable insights into the behavior of the models under different hyperparameter settings and serve as a guide for future experiments.

### 4.2.4.3 Description of the results.csv File

The \*results.csv files are used to store the results of machine learning and deep learning classifiers, including Graph Convolutional Networks (GCNs) and classical classifiers like Random Forest. The files are regular CSVs organized with the following headers:

*   **system:** The operating system on which the experiment was run. Here, Linux.

*   **node_name:** The name of the node in the cluster. Here, either *nixos* (local machine) or *rascoussie* (lab server).

*   **release, version:** OS release and version information.
and the number of input graphs has been limited to 16. The following JSON file shows the hyperparameters used during the pre-experiments:

```json
{
  "node2vecontinents range": [16, 32, 128],
  "node2vecwalk length range": [16, 32],
  "node2vecnum_walks range": [50, 100],
  "node2vecp range": [0.5, 1.0, 1.5],
  "node2vecq range": [0.5, 1.0, 1.5],
  "node2vecwindow range": [10, 20],
  "node2vecbatch words range": [4, 8, 16],
  "node2vecworkers range": [16, 32],
  "random forest trees range": [100, 500, 1000],
  "gcntrainingepochs range": [5, 10, 20]
}
```

<caption>Listing 4.6: JSON hyperparameters used during experiments</caption>

Several observations were made during the early experiments concerning the impact of different hyperparameters on the model's performance, especially concerning the Node2Vec parameters. The following observations were made:

*   **Walk Length and Number of Walks:** Increasing the number of walks and the walk length generally improved the model's performance. However, this came at the cost of significantly increased computational time. The benefits plateaued after reaching a certain threshold.

*   **Number of Dimensions:** A higher number of dimensions generally led to better results. Lower values were found to be detrimental to the model's performance, indicating the importance of this parameter.

*   **Impact of *p* and *q*:** The parameters *p* and *q* had an unpredictable impact on the model's performance. While some combinations seemed to yield better results, no clear pattern was observed, making these parameters challenging to optimize.

*   **Batch Word Range:** The range of batch words had a minimal impact on the model's performance. As a result, an intermediate value was selected for this parameter to balance computational efficiency and performance.

These observations provide valuable insights into the behavior of the models under different hyperparameter settings and serve as a guide for future experiments.

### 4.2.4.3 Description of the results.csv File

The \*results.csv files are used to store the results of machine learning and deep learning classifiers, including Graph Convolutional Networks (GCNs) and classical classifiers like Random Forest. The files are regular CSVs organized with the following headers:

*   **system:** The operating system on which the experiment was run. Here, Linux.

*   **node_name:** The name of the node in the cluster. Here, either *nixos* (local machine) or *rascoussie* (lab server).

*   **release, version:** OS release and version information.
* **machine, processor**: Hardware details.

* **physical Cores, total Cores**: Number of physical and total cores.

* **total_memory, available_memory**: Total and available memory in bytes.

* **start_time**: The start time of the experiment.

* **nb_input_graphs**: Number of input graphs.

* **duration_embedders**: Time taken for embedding.

* **subpipeline_name, index, pipeline_name**: Information about the pipeline model used, with values like `sgd-classifier` or `gcn-with-dropout`.

* **input_mem2graph_dataset_dir_path**: Path to the dataset directory.

* **nodeimo embedding**: Type of node embedding used. Several values are possible, like solo embeddings like `chunk-header-node` or `node2vec`, or combined embeddings like `node2vec-chunk-semantic-embedding`.

* **node2vec***: Parameters for the Node2Vec algorithm, like the number of walks, the walk length, the window size, the number of dimensions, the number of epochs, and the p and q parameters.

* **random_forest***: Parameters for the Random Forest algorithm, like the number of estimators (trees) or the number of parallel jobs.

* **imbalance_ratio**: Ratio of the classes in the dataset. For instance, a value of 496.33 means that the dataset contains 496.33 times more negative samples than positive samples. Since no filtering is applied, the ratio is always greater than 1, and generally very high.

* **precision_class**, **recall_class**, **f1_score_class**, **support_class***: Metrics for each class.

* **true_positives, true negatives, false positives, false negatives**: Confusion matrix elements.

* **AUC**: Area under the ROC curve.

* **duration_train_test**: Time taken for training and testing.

* **nb_node_features**: Number of node features. This value directly depends on the node embedding used, and the input memory graph dataset parameters used during generation.

* **first_gcn_training_epochs**: Number of epochs in GCN training phase.

Each row in the *results.csv* files represents a single experiment run with a specific configuration and its corresponding results. Keeping a precise track of the parameters used for each experiment is crucial for reproducibility and traceability. They also form the basis for the analysis and visualization of the results.
* **machine, processor**: Hardware details.

* **physical Cores, total Cores**: Number of physical and total cores.

* **total_memory, available_memory**: Total and available memory in bytes.

* **start_time**: The start time of the experiment.

* **nb input graphs**: Number of input graphs.

* **duration embedding**: Time taken for embedding.

* **subpipeline_name, index, pipeline_name**: Information about the pipeline model used, with values like `sgd-classifier` or `gcn-with-dropout`.

* **input_mem2graph_dataset_dir_path**: Path to the dataset directory.

* **node embedding**: Type of node embedding used. Several values are possible, like solo embeddings like `chunk-header-node` or `node2vec`, or combined embeddings like `node2vec-chunk-semantic-embedding`.

* **node2vec***: Parameters for the Node2Vec algorithm, like the number of walks, the walk length, the window size, the number of dimensions, the number of epochs, and the p and q parameters.

* **random forest***: Parameters for the Random Forest algorithm, like the number of estimators (trees) or the number of parallel jobs.

* **imbalance ratio**: Ratio of the classes in the dataset. For instance, a value of 496.33 means that the dataset contains 496.33 times more negative samples than positive samples. Since no filtering is applied, the ratio is always greater than 1, and generally very high.

* **precision_class***, **recall_class***, **f1_score_class***, **support_class***: Metrics for each class.

* **true positives, true negatives, false positives, false negatives**: Confusion matrix elements.

* **AUC**: Area under the ROC curve.

* **duration train test**: Time taken for training and testing.

* **nb node features**: Number of node features. This value directly depends on the node embedding used, and the input memory graph dataset parameters used during generation.

* **first_gcntraining_epochs**: Number of epochs in GCN training phase.

Each row in the *results.csv* files represents a single experiment run with a specific configuration and its corresponding results. Keeping a precise track of the parameters used for each experiment is crucial for reproducibility and traceability. They also form the basis for the analysis and visualization of the results.
## 4.3 Obtained Results

This section presents a comprehensive overview of the results obtained with the final experimentation. The outcomes are detailed in multiple formats, including correlation matrices, performance metrics tables, and visualizations, to provide a precise understanding of the model performances. The aim is to elucidate the effectiveness of different features and embeddings in the context of our machine learning pipelines. In-depth discussions on these results will be reserved for the following "Discussions" part.

### 4.3.1 Feature Engineering results

This section delves into the results obtained from the feature engineering efforts carried out during the experiments. The results are presented in multiple correlation matrices.
## 4.3 Obtained Results

This section presents a comprehensive overview of the results obtained with the final experimentation. The outcomes are detailed in multiple formats, including correlation matrices, performance metrics tables, and visualizations, to provide a precise understanding of the model performances. The aim is to elucidate the effectiveness of different features and embeddings in the context of our machine learning pipelines. In-depth discussions on these results will be reserved for the following "Discussions" part.

### 4.3.1 Feature Engineering results

This section delves into the results obtained from the feature engineering efforts carried out during the experiments. The results are presented in multiple correlation matrices.
<figure><img src="image_16.png" /><figcaption>Figure 4.2: Feature correlation matrices on the different Mem2Graph-generated datasets. Used algorithm: Kendall.</figcaption></figure>
<figure><img src="image_17.png" /><figcaption>Figure 4.2: Feature correlation matrices on the different Mem2Graph-generated datasets. Used algorithm: Kendall.</figcaption></figure>
<figure><img src="image_17.png" /><figcaption>Figure 4.3: Feature correlation matrices on the different Mem2Graph-generated datasets. Used algorithm: Pearson.</figcaption></figure>
<figure><img src="image_18.png" /><figcaption>Figure 4.3: Feature correlation matrices on the different Mem2Graph-generated datasets. Used algorithm: Pearson.</figcaption></figure>
<figure><img src="image_18.png" /><figcaption>Figure 4.4: Feature correlation matrices on the different Mem2Graph-generated datasets. Used algorithm: Spearman.</figcaption></figure>

4.3.2 Classic Model results

Tables are provided to summarize the performance of different pipelines and models. These tables
include four classical machine learning metrics: precision, recall, F1 score, and the Area Under
the Curve (AUC). Each table offers a snapshot of how well each model performs on the key chunk
<figure><img src="image_19.png" /><figcaption>Figure 4.4: Feature correlation matrices on the different Mem2Graph-generated datasets. Used algorithm: Spearman.</figcaption></figure>

4.3.2 Classic Model results

Tables are provided to summarize the performance of different pipelines and models. These tables
include four classical machine learning metrics: precision, recall, F1 score, and the Area Under
the Curve (AUC). Each table offers a snapshot of how well each model performs on the key chunk
prediction task.

<table><caption>Table 4.2: Best instances of model: logistic-regression.</caption><thead><tr><th>Best at</th><th>Precision</th><th>Recall</th><th>F1 Score</th><th>AUC</th></tr></thead><tbody><tr><td>precision</td><td>1.0000</td><td>0.0417</td><td>0.0800</td><td>0.5208</td></tr><tr><td>recall</td><td>0.3333</td><td>0.5000</td><td>0.4000</td><td>0.7471</td></tr><tr><td>f1 score</td><td>0.3333</td><td>0.5000</td><td>0.4000</td><td>0.7471</td></tr><tr><td>AUC</td><td>0.2449</td><td>0.5000</td><td>0.3288</td><td>0.7486</td></tr></tbody></table>

<table><caption>Table 4.3: Best instances of model: random-forest.</caption><thead><tr><th>Best at</th><th>Precision</th><th>Recall</th><th>F1 Score</th><th>AUC</th></tr></thead><tbody><tr><td>precision</td><td>1.0000</td><td>0.0417</td><td>0.0800</td><td>0.5208</td></tr><tr><td>recall</td><td>1.0000</td><td>0.0833</td><td>0.1538</td><td>0.5417</td></tr><tr><td>f1 score</td><td>1.0000</td><td>0.0833</td><td>0.1538</td><td>0.5417</td></tr><tr><td>AUC</td><td>1.0000</td><td>0.0833</td><td>0.1538</td><td>0.5417</td></tr></tbody></table>

<table><caption>Table 4.4: Best instances of model: sgd-classifier.</caption><thead><tr><th>Best at</th><th>Precision</th><th>Recall</th><th>F1 Score</th><th>AUC</th></tr></thead><tbody><tr><td>precision</td><td>1.0000</td><td>0.0417</td><td>0.0800</td><td>0.5208</td></tr><tr><td>recall</td><td>0.4615</td><td>1.0000</td><td>0.6316</td><td>0.9962</td></tr><tr><td>f1 score</td><td>0.4615</td><td>1.0000</td><td>0.6316</td><td>0.9962</td></tr><tr><td>AUC</td><td>0.4615</td><td>1.0000</td><td>0.6316</td><td>0.9962</td></tr></tbody></table>

### 4.3.3 Deep Learning GCN Model results

Best models obtained after the hyperparameter search, on a range of embeddings and models, this time focusing on the GCN models.

<table><caption>Table 4.5: Best instances of model: very-simple-gcn.</caption><thead><tr><th>Best at</th><th>Precision</th><th>Recall</th><th>F1 Score</th><th>AUC</th></tr></thead><tbody><tr><td>precision</td><td>0.6000</td><td>0.5000</td><td>0.5455</td><td>0.7489</td></tr><tr><td>recall</td><td>0.2609</td><td>1.0000</td><td>0.4138</td><td>0.9907</td></tr><tr><td>f1 score</td><td>0.6000</td><td>0.5000</td><td>0.5455</td><td>0.7489</td></tr><tr><td>AUC</td><td>0.2609</td><td>1.0000</td><td>0.4138</td><td>0.9907</td></tr></tbody></table>

<table><caption>Table 4.6: Best instances of model: simple-gcn.</caption><thead><tr><th>Best at</th><th>Precision</th><th>Recall</th><th>F1 Score</th><th>AUC</th></tr></thead><tbody><tr><td>precision</td><td>0.5000</td><td>0.5000</td><td>0.5000</td><td>0.7484</td></tr><tr><td>recall</td><td>0.2308</td><td>1.0000</td><td>0.3750</td><td>0.9891</td></tr><tr><td>f1 score</td><td>0.5000</td><td>0.5000</td><td>0.5000</td><td>0.7484</td></tr><tr><td>AUC</td><td>0.2609</td><td>1.0000</td><td>0.4138</td><td>0.9907</td></tr></tbody></table>
prediction task.

<table><caption>Table 4.2: Best instances of model: logistic-regression.</caption><thead><tr><th>Best at</th><th>Precision</th><th>Recall</th><th>F1 Score</th><th>AUC</th></tr></thead><tbody><tr><td>precision</td><td>1.0000</td><td>0.0417</td><td>0.0800</td><td>0.5208</td></tr><tr><td>recall</td><td>0.3333</td><td>0.5000</td><td>0.4000</td><td>0.7471</td></tr><tr><td>f1 score</td><td>0.3333</td><td>0.5000</td><td>0.4000</td><td>0.7471</td></tr><tr><td>AUC</td><td>0.2449</td><td>0.5000</td><td>0.3288</td><td>0.7486</td></tr></tbody></table>

<table><caption>Table 4.3: Best instances of model: random-forest.</caption><thead><tr><th>Best at</th><th>Precision</th><th>Recall</th><th>F1 Score</th><th>AUC</th></tr></thead><tbody><tr><td>precision</td><td>1.0000</td><td>0.0417</td><td>0.0800</td><td>0.5208</td></tr><tr><td>recall</td><td>1.0000</td><td>0.0833</td><td>0.1538</td><td>0.5417</td></tr><tr><td>f1 score</td><td>1.0000</td><td>0.0833</td><td>0.1538</td><td>0.5417</td></tr><tr><td>AUC</td><td>1.0000</td><td>0.0833</td><td>0.1538</td><td>0.5417</td></tr></tbody></table>

<table><caption>Table 4.4: Best instances of model: sgd-classifier.</caption><thead><tr><th>Best at</th><th>Precision</th><th>Recall</th><th>F1 Score</th><th>AUC</th></tr></thead><tbody><tr><td>precision</td><td>1.0000</td><td>0.0417</td><td>0.0800</td><td>0.5208</td></tr><tr><td>recall</td><td>0.4615</td><td>1.0000</td><td>0.6316</td><td>0.9962</td></tr><tr><td>f1 score</td><td>0.4615</td><td>1.0000</td><td>0.6316</td><td>0.9962</td></tr><tr><td>AUC</td><td>0.4615</td><td>1.0000</td><td>0.6316</td><td>0.9962</td></tr></tbody></table>

### 4.3.3 Deep Learning GCN Model results

Best models obtained after the hyperparameter search, on a range of embeddings and models, this time focusing on the GCN models.

<table><caption>Table 4.5: Best instances of model: very-simple-gcn.</caption><thead><tr><th>Best at</th><th>Precision</th><th>Recall</th><th>F1 Score</th><th>AUC</th></tr></thead><tbody><tr><td>precision</td><td>0.6000</td><td>0.5000</td><td>0.5455</td><td>0.7489</td></tr><tr><td>recall</td><td>0.2609</td><td>1.0000</td><td>0.4138</td><td>0.9907</td></tr><tr><td>f1 score</td><td>0.6000</td><td>0.5000</td><td>0.5455</td><td>0.7489</td></tr><tr><td>AUC</td><td>0.2609</td><td>1.0000</td><td>0.4138</td><td>0.9907</td></tr></tbody></table>

<table><caption>Table 4.6: Best instances of model: simple-gcn.</caption><thead><tr><th>Best at</th><th>Precision</th><th>Recall</th><th>F1 Score</th><th>AUC</th></tr></thead><tbody><tr><td>precision</td><td>0.5000</td><td>0.5000</td><td>0.5000</td><td>0.7484</td></tr><tr><td>recall</td><td>0.2308</td><td>1.0000</td><td>0.3750</td><td>0.9891</td></tr><tr><td>f1 score</td><td>0.5000</td><td>0.5000</td><td>0.5000</td><td>0.7484</td></tr><tr><td>AUC</td><td>0.2609</td><td>1.0000</td><td>0.4138</td><td>0.9907</td></tr></tbody></table>
<table><caption>Table 4.7: Best instances of model: first-gcn.</caption><thead><tr><th>Best at</th><th>Precision</th><th>Recall</th><th>F1 Score</th><th>AUC</th></tr></thead><tbody><tr><td>precision</td><td>0.5000</td><td>0.5000</td><td>0.5000</td><td>0.7484</td></tr><tr><td>recall</td><td>0.2727</td><td>1.0000</td><td>0.4286</td><td>0.9913</td></tr><tr><td>f1 score</td><td>0.5000</td><td>0.5000</td><td>0.5000</td><td>0.7484</td></tr><tr><td>AUC</td><td>0.2727</td><td>1.0000</td><td>0.4286</td><td>0.9913</td></tr></tbody></table>

<table><caption>Table 4.8: Best instances of model: gcn-with-dropout.</caption><thead><tr><th>Best at</th><th>Precision</th><th>Recall</th><th>F1 Score</th><th>AUC</th></tr></thead><tbody><tr><td>precision</td><td>0.3500</td><td>0.2333</td><td>0.2800</td><td>0.6152</td></tr><tr><td>recall</td><td>0.0863</td><td>0.8000</td><td>0.1558</td><td>0.8810</td></tr><tr><td>f1 score</td><td>0.2110</td><td>0.7667</td><td>0.3309</td><td>0.8767</td></tr><tr><td>AUC</td><td>0.0863</td><td>0.8000</td><td>0.1558</td><td>0.8810</td></tr></tbody></table>

<table><caption>Table 4.9: Best instances of model: advanced-gcn.</caption><thead><tr><th>Best at</th><th>Precision</th><th>Recall</th><th>F1 Score</th><th>AUC</th></tr></thead><tbody><tr><td>precision</td><td>0.2097</td><td>0.4333</td><td>0.2826</td><td>0.7129</td></tr><tr><td>recall</td><td>0.0533</td><td>0.9000</td><td>0.1006</td><td>0.8943</td></tr><tr><td>f1 score</td><td>0.2097</td><td>0.4333</td><td>0.2826</td><td>0.7129</td></tr><tr><td>AUC</td><td>0.1552</td><td>0.9000</td><td>0.2647</td><td>0.9390</td></tr></tbody></table>

## 4.4 Compared Performances of models and embeddings

In our experiments, we limited the analysis to a maximum of 16 input graphs, which may appear to be a relatively low number. However, this limitation was necessary due to the extensive range of hyperparameters, embeddings, and models that we aimed to evaluate. Despite this constraint, we were able to run a total of 7976 machine learning pipelines, accumulating over 100 hours of compute time. This extensive computational effort underscores the complexity and depth of the feature engineering and model evaluation processes undertaken in this study. The following tables and visualizations provide a comprehensive overview of the results obtained from these experiments.

<table><caption>Table 4.10: Results for the model very-simple-gcn</caption><thead><tr><th>Model</th><th>Precision</th><th>Recall</th><th>F1 Score</th><th>AUC</th></tr></thead><tbody><tr><td>advanced-gcn</td><td>0.2097</td><td>0.9000</td><td>0.2826</td><td>0.9390</td></tr><tr><td>first-gcn</td><td>0.5000</td><td>1.0000</td><td>0.5000</td><td>0.9913</td></tr><tr><td>gcn-with-dropout</td><td>0.3500</td><td>0.8000</td><td>0.3309</td><td>0.8810</td></tr><tr><td>logistic-regression</td><td>1.0000</td><td>0.5000</td><td>0.4000</td><td>0.7486</td></tr><tr><td>random-forest</td><td>1.0000</td><td>0.0833</td><td>0.1538</td><td>0.5417</td></tr><tr><td>sgd-classifier</td><td>1.0000</td><td>1.0000</td><td>0.6316</td><td>0.9962</td></tr><tr><td>simple-gcn</td><td>0.5000</td><td>1.0000</td><td>0.5000</td><td>0.9907</td></tr><tr><td>very-simple-gcn</td><td>0.6000</td><td>1.0000</td><td>0.5455</td><td>0.9907</td></tr></tbody></table>

In addition to the tabular data, we also offer visualizations to facilitate a more intuitive comparison between models and embeddings. These graphical representations aim to make the complex
<table><caption>Table 4.7: Best instances of model: first-gcn.</caption><thead><tr><th>Best at</th><th>Precision</th><th>Recall</th><th>F1 Score</th><th>AUC</th></tr></thead><tbody><tr><td>precision</td><td>0.5000</td><td>0.5000</td><td>0.5000</td><td>0.7484</td></tr><tr><td>recall</td><td>0.2727</td><td>1.0000</td><td>0.4286</td><td>0.9913</td></tr><tr><td>f1 score</td><td>0.5000</td><td>0.5000</td><td>0.5000</td><td>0.7484</td></tr><tr><td>AUC</td><td>0.2727</td><td>1.0000</td><td>0.4286</td><td>0.9913</td></tr></tbody></table>

<table><caption>Table 4.8: Best instances of model: gcn-with-dropout.</caption><thead><tr><th>Best at</th><th>Precision</th><th>Recall</th><th>F1 Score</th><th>AUC</th></tr></thead><tbody><tr><td>precision</td><td>0.3500</td><td>0.2333</td><td>0.2800</td><td>0.6152</td></tr><tr><td>recall</td><td>0.0863</td><td>0.8000</td><td>0.1558</td><td>0.8810</td></tr><tr><td>f1 score</td><td>0.2110</td><td>0.7667</td><td>0.3309</td><td>0.8767</td></tr><tr><td>AUC</td><td>0.0863</td><td>0.8000</td><td>0.1558</td><td>0.8810</td></tr></tbody></table>

<table><caption>Table 4.9: Best instances of model: advanced-gcn.</caption><thead><tr><th>Best at</th><th>Precision</th><th>Recall</th><th>F1 Score</th><th>AUC</th></tr></thead><tbody><tr><td>precision</td><td>0.2097</td><td>0.4333</td><td>0.2826</td><td>0.7129</td></tr><tr><td>recall</td><td>0.0533</td><td>0.9000</td><td>0.1006</td><td>0.8943</td></tr><tr><td>f1 score</td><td>0.2097</td><td>0.4333</td><td>0.2826</td><td>0.7129</td></tr><tr><td>AUC</td><td>0.1552</td><td>0.9000</td><td>0.2647</td><td>0.9390</td></tr></tbody></table>

## 4.4 Compared Performances of models and embeddings

In our experiments, we limited the analysis to a maximum of 16 input graphs, which may appear to be a relatively low number. However, this limitation was necessary due to the extensive range of hyperparameters, embeddings, and models that we aimed to evaluate. Despite this constraint, we were able to run a total of 7976 machine learning pipelines, accumulating over 100 hours of compute time. This extensive computational effort underscores the complexity and depth of the feature engineering and model evaluation processes undertaken in this study. The following tables and visualizations provide a comprehensive overview of the results obtained from these experiments.

<table><caption>Table 4.10: Results for the model very-simple-gcn</caption><thead><tr><th>Model</th><th>Precision</th><th>Recall</th><th>F1 Score</th><th>AUC</th></tr></thead><tbody><tr><td>advanced-gcn</td><td>0.2097</td><td>0.9000</td><td>0.2826</td><td>0.9390</td></tr><tr><td>first-gcn</td><td>0.5000</td><td>1.0000</td><td>0.5000</td><td>0.9913</td></tr><tr><td>gcn-with-dropout</td><td>0.3500</td><td>0.8000</td><td>0.3309</td><td>0.8810</td></tr><tr><td>logistic-regression</td><td>1.0000</td><td>0.5000</td><td>0.4000</td><td>0.7486</td></tr><tr><td>random-forest</td><td>1.0000</td><td>0.0833</td><td>0.1538</td><td>0.5417</td></tr><tr><td>sgd-classifier</td><td>1.0000</td><td>1.0000</td><td>0.6316</td><td>0.9962</td></tr><tr><td>simple-gcn</td><td>0.5000</td><td>1.0000</td><td>0.5000</td><td>0.9907</td></tr><tr><td>very-simple-gcn</td><td>0.6000</td><td>1.0000</td><td>0.5455</td><td>0.9907</td></tr></tbody></table>

In addition to the tabular data, we also offer visualizations to facilitate a more intuitive comparison between models and embeddings. These graphical representations aim to make the complex
data more digestible and provide insights that may not be immediately obvious from the tables
alone.

<figure><img src="image_19.png" /><figcaption>Figure 4.5: Visualization of the result metrics use to compare model performance on memory graphs, for different embeddings and hyperparameters.</figcaption></figure>
data more digestible and provide insights that may not be immediately obvious from the tables
alone.

<figure><img src="image_20.png" /><figcaption>Figure 4.5: Visualization of the result metrics use to compare model performance on memory graphs, for different embeddings and hyperparameters.</figcaption></figure>
<figure><img src="image_20.png" /><figcaption>Figure 4.6: Visualization of the result metrics used to compare model performance per memory graph node embedding strategies.</figcaption></figure>

It's worth noting that while this section provides a detailed account of the results, an in-depth discussion about these findings, their implications, and potential future work will be covered in the following "Discussions" section.
<figure><img src="image_21.png" /><figcaption>Figure 4.6: Visualization of the result metrics used to compare model performance per memory graph node embedding strategies.</figcaption></figure>

It's worth noting that while this section provides a detailed account of the results, an in-depth discussion about these findings, their implications, and potential future work will be covered in the following "Discussions" section.