Forensic Artifacts' Analysis using Graph Theory

Abstract

The number of cyber-attacks is constantly growing, and their sophistication is increasing due to new techniques and strategies of attackers. Organisations must continuously improve their methods of detecting and responding to these attacks to protect their networks and information systems. The time between the occurrence of a security incident and its identification takes an average of 100 - 200 days, with organisations having a response time of between 50 - 70 days. Our work aims to reduce this time so that organisations can respond to security incidents more quickly. In this work, we use graph theory for forensic analysis in the Windows operating system. The main objective of the work is to identify digital evidence and the relationships between them. For this purpose, we work with datasets from various Capture the Flag (CTF) competitions. We describe the processing stages of the digital evidence and their transformation into graphs and then identify anomalies and cycles in the graphs in order to provide readers with a deeper insight.

Keywords

• eol>graph theory
• graph algorithms
• forensic analysis
• artifact
• cybersecurity

1. Introduction

that article, we focus on how graph theory applied to individual forensic artefacts available in the Windows In the digital world, data and network security is a key operating system and the NTFS file system can help us. concern for organisations of all sizes and industries. With Graph analysis allows us to identify the relationships the rise of cyber-attacks and their ever-changing nature, between diferent digital evidence and their attributes, organisations must constantly adapt to protect their as- thereby better understanding the nature of the attack. sets and ensure the security of their information. Cyber To achieve this objective, we specify the following attackers are constantly moving forward and developing partial research objectives: new ways to penetrate systems and gain unauthorised access to sensitive data. As these attacks become more so- • What attributes of forensic artefacts are best phisticated, the challenge for organisations is to identify suited for graph representation? attacks as quickly as possible and respond appropriately • How can specific properties of graphs help idenand ideally. tify key forensic artefacts and relationships in

One of the main issues in the response to security at- digital forensics? tacks is the time between the occurrence of a security incident, its identification, and the subsequent response. This paper is divided into six sections. Section 2 disThis time can be non-trivial, often measured in hundreds cusses papers relevant to this research. Section 3 specifies of days, giving attackers ample time to cause damage the methods employed in this paper, including the colwithout being detected. In addition, even after a secu- lection and processing of the digital evidence. Section 4 rity incident is identified, an organisation needs time to outlines the graph theory applied to digital evidence and resolve it and restore normal operations. graph generation options. Section 5 discusses the lessons

Our research focuses on the security incident response learned from applied graph properties to digital evidence. process, including digital forensics. The main aim is to Section 6 provides a summary, including our suggestions reduce the time interval required to resolve a security for future research. incident and provide organisations with a way to respond more quickly and efectively to security incidents. In

2. Related works

ITAT 2024 Information Technologies – Applications and Theory 2024, We often think of data analysis and machine learning September 20–24, 2024, Drienica, Slovakia as elements of artificial intelligence. It may be about * Corresponding author. analysing data diferently. We must also visualise the † These authors contributed equally. data, preprocess it, get basic statistics, etc. It is in the vi$ [e-mail] (S. P. Krišáková); sualisation that graphs can help us. Several works have [e-mail] (P. Sokol); [e-mail] ready been done in forensic artefact analysis using graphs. (R. 0K0r0i0v-o0š0-0B2e-l1lu9š6)7-8802 (P. Sokol) Many of these have focused on network communication, © 2024 Copyright for this paper by its authors. Use permitted under Creative Commons License which is diferent from the form of data we use in this CPWrEooUrckReshdoinpgs IhStpN:/c1e6u1r3-w-0s.o7r3g ACttEribUutRion W4.0oInrtekrnsahtioonpal (PCCroBYce4.0e).dings (CEUR-WS.org) work. Nevertheless, we can take inspiration from them as they ofer insight into the representation of forensic Due to the proliferation of smart devices, detecting artefacts using graphs and their connections. We have and mitigating faults in computer networks is crucial. selected a few of these papers to get a basic overview of Anomalies, whether from security breaches, component the current state of the art in the given field. failures, or environmental factors, must be promptly addressed. Recent studies on anomaly detection in com2.1. Security Data Analysis puter networks categorize solutions and highlight trends and shortcomings, especially regarding malware in smartCybercrime risks have escalated with the digitization of phone networks. data (books, videos, images, medical and genetic infor- Paper [ 8 ] introduces a graph-based approach to netmation) via laptops, tablets, smartphones, and wearables. work forensics, using a graph model of digital evidence Digital forensics recovers lost or deleted files but requires for evidence presentation and automated reasoning. The more eficient investigation resources. Current processes proposed hierarchical reasoning framework infers netrely heavily on human input, slowing responses to rapid work entity states and identifies critical entities. An incybercrimes. Machine learning can automate digital in- teractive hypothesis testing framework aids in detecting vestigations, aiding digital investigators [ 1 ]. attack activities. Experimental results show the proto

Constantini, Gasperis, and Olivieri explored artificial type’s efectiveness in extracting attack scenarios with intelligence and computational logic, particularly answer minimal expert knowledge. set programming, to automate evidence analysis in dig- As Internet trafic grows, so do cyber crimes, necesital forensics. They demonstrated how complex inves- sitating advanced network forensics. One method comtigations could be optimized and automated to assist bines network vulnerability and graph network evidence in generating hypotheses for court cases using graph to reconstruct attack scenarios and identify multi-stage theory-based algorithms [ 2 ]. attacks, confirmed by experimental results [ 9 ].

Ch. Easttom highlighted the use of graph theory in Spectral graph theory helps understand network malcriminal investigations, describing how mathematical ware propagation, essential as device connectivity inmodelling helps understand relationships among sus- creases. Using various Laplacian matrices to track netpects, victims, and systems [ 3 ]. Palmer, Campbell, and work pattern changes, one study [ 10 ] ofers insights into Gelfand further discussed graph theory’s role in forensic malware spread, aiding in faster infection detection. analysis, noting the visualization benefits for investigators and its potential to support the investigation process [ 4 ]. 3. Methodology

A study on distributed graph analysis of large-scale email datasets showcased improved eficiency and accu- In this chapter, we have covered how to acquire, preproracy in digital evidence analysis using centrality algo- cess, and explain data so that we can combine it into rithms [ 5 ]. Binwal, Devi, and Singh developed algorithms graphs, filter it, and analyse it later. We have also defor fingerprint graph representation and isomorphism scribed the creation of the super timeline and the subsetesting, applicable to broader forensic analysis despite quent transformation of the other two datasets. difering input data [ 6 ].

Additionally, attack graphs, used to identify potential 3.1. Data acquisition and description attack paths and vulnerabilities, are proposed for practical forensic analysis, including antiforensic scenarios.

These graphs help understand complex attack paths and missing evidence, demonstrated through a database attack case study [ 7 ].

Our contribution is to integrate these methods to enhance digital forensics. We focus on automating digital evidence analysis with graph theory to elucidate relationships among digital evidence and entities.

We selected seven fictitious cases from CTF competitions

focused on forensics, incident response, and threat detection, and we used disk images from these cases.

The first example is the case of the stolen Szechuan sauce from the DFIR Madness portal called Case001 The case of the Stolen Szechuan sauce [ 11 ], where in this case the main goal was to find out how CITADEL’s recipe got on the dark web. The company requested forensic analysis, identification of unwanted applications installed on the system, and detection of the location and time of installation. The case also ofers information as to whether any content was changed, modified, deleted, or data was leaked. We worked with artefacts from the company’s DC domain control server (hereafter called the ”DC server”) and from the Desktop - therefore we count this case as two datasets.

2.2. Forensic Analysis in Network

Communication Using Graph Theory

While our primary focus is on NTFS file system data from Windows, we also review digital forensics in network communication, linking file system data with network communication data.

• MACB : timestamps (Modification, Access,

Changed, Birth) • Source : source name abbreviation (e.g. REG registry records) • Sourcetype : description of the source • Type : timestamp type (e.g. last entry) • User : the user name (if any) that is associated with the event • Host : host name (if any) that is associated with the event • Short : contains a short description field in which the text is stored • Desc : an array that contains most of the parsed information • Version : version number of the timestamp • Filename : the name of the file that is associated with the event • Inode : inode number of the file being analysed • Notes : a place to store additional information • Format : the input module that was used to parse • Extra : field with parsed information that is linked and stored here

The other three cases Magnet CTF 2019 [12], Magnet

CTF 2020 [ 13 ] and Magnet CTF 2022 [ 14 ] were from the CTF (Capture the Flag) Magnet Forensics competition. It was not a classical forensic analysis, but rather answering questions like ”when did we get the disk image” or ”when was the software installed”.

The last two cases, NIST Data Leakage Case [ 15 ] and NIST Hacking Case [ 16 ], are used to learn about diferent forms of data leakage and to improve techniques for investigating them. We focused on investigating a data leak case where the key is to uncover evidence of illegal activities and obtain any information generated by the suspect.

3.2. Data preprocessing

For data preprocessing, we followed the same steps in

all seven cases, specifically specifying the preprocessing process for only one case. We worked with the data according to the procedure described in the paper [ 17 ].

We created the timeline using the Log2timeline [ 18 ] tool and its plugins. We modified the resulting timeline with the psort.py tool and the Python language with the pandas library. Our dataset contained records from 11 diferent data sources, with FILE, EVT, and REG records In addition to the basic seven datasets, we created 6 being the most prominently represented, accounting for additional CSV files containing records from FILE and 87% of all records. We divided the extracted attributes 7 CSV files containing records from EVT. The datasets into seven categories. from FILE have 44 attributes, and EVT have 40 attributes.

We narrowed the dataset to the time of the security These files were created by extracting data from the origincident and manually identified relevant digital inal supertimeline. For example, if there was a MACB evidence, including the inode files: 84630, 84880, 84987, column in the original dataset, four new columns were 86966, 86967, 86968, 86970, 86971, 86975, 87059, 87060, created in the new (EVT or FILE) dataset, and the original 87064, 87111, 87112, 87137, and files with the names: one was deleted. The new columns are ’M’, ’A’, ’C’, ’B’. If ’coreupdater. exe’, ’FILESH 1’, ’Secret’, ’BETH_S 1.TXT’, there was a ’.ACB’ record in the original data, we wrote ’Beth-_Secret.lnk’, ’SECRET 1.TXT’, ’SECRET_beth.lnk’, 1 in the relevant ’A’, ’C’, ’B’ columns and 0 in the ’M’ ’Szechuan’, ’SZECHU1.TXT’, ’Secret.lnk’, ’NoJerry. column. In this way, we partially created binary data or lnk’, ’No-Jerry.txt’, ’f01b4d95cf55d32a.automatic- columns. Not all attributes could be converted this way, Destinationsms’, ’SECRET_beth.txt’, ’Beth_Secret.txt’, so columns like ’date’ or ’time’ were left unchanged. The ’Secret.zip’, ’coreupdater.exe.2424 urv. partial’. exact procedure for creating datasets is explained in [ 19 ].

Next, we analysed the inodes and filenames, excluding For later analysis and graphing needs, we had to cresome inodes and filenames. Finally, we used aggregation ate additional columns in the FILE datasets - MACB, file, functions and created attribute combinations to analyse dir, and NTFS, which were created by concatenating the data. some of the columns. MACB - we merged the ’broken’

We only manually identified inodes and file names in columns ’M’, ’A’, ’C’, ’B’ into one again. In the case of the the stolen Szechuan sauce recipe; the identified inodes ifle column, these were ’file_executable’, ’file_graphic’, and file names still need to be identified for the other ’file_documents’, ’file_ps’ and ’file_other’. For dir datasets. ’dir_appdata’, ’dir_win’, ’dir_user’ and ’dir_other’. NTFS

Each of the seven datasets is a super timeline con- - ’file_stat’, ’NTFS_file_stat’, ’file_entry_shell_item’ and taining 17 attributes, and the following rows are records ’NTFS_USN_change’. (events). There are 17 attributes and their description The analysis of the selection of the attributes menby [ 19 ]: tioned above, as well as the analysis of various combinations of attributes for anomaly detection, is presented in the paper [ 17 ]. • Date : the date when the event occurred • Time : time the event occurred • Timezone : time zone

4. Graph Theory

4.1. Background

A Graph = (, ) is a pair of a finite set of vertices = {0, 1, . . . , − 1} and edges = {{, }|0 ≤ , , < , ̸= }. A directed graph has oriented edges(directed arcs), i.e. the order of vertices is important (, ). (Edge-)Weighted graph assigns the weight to each edge, so the edges are in the form (, , ).

A bipartite graph is a special type of graph where a set of vertices can be divided into two disjoint sets (partitions), where each edge has exactly one vertex from every partition.

There are several definitions and parameters: path (sequence of incident vertices and edges, starting and ending vertex (leaf), all vertices are mutually diferent), excentricity, etc.

The degree of the vertex in a graph , denoted by deg() or (), is the number of edges incident to in . The maximum degree of a graph , denoted by ∆( ), is the maximum value among the degrees of all vertices of the graph . By analogy, we also denote the minimum degree of a graph .

Walk in the graph denotes the alternating sequence of incident vertices and edges (starting and ending with vertex). A sequence with mutually diferent edges is called a trail. A walk where all vertices difer is called a path. In other words, a path in a graph is a sequence of vertices for which there indeed exists an edge in the graph between every two following vertices. No two vertices (and hence no edges) are repeated. A trail in which all vertices except the first and last are distinct is called a cycle.

A graph is connected if every pair of vertices in the graph is connected. It means that there is a path between every pair of vertices. A component of a graph is a connected subgraph that is not part of any larger connected subgraph.

An edge of a graph is called a bridge if the number of components increases when it is removed. A vertex of a graph is called a cut vertex/articulation point if the number of components of the graph increases when it is removed.

Eccentricity the () of a point is the distance of the point from the farthest point in the graph. The radius of the graph () is the minimum eccentricity of a point in the graph , and () is the maximum The center of () is the set of all central vertices in the graph . The eccentric vertex of a vertex is the vertex that is the furthest from it. A vertex v is called peripheral if () = (). Periphery () of a graph is the set of all peripheral vertices in the graph .

4.2. Graph Generation from Forensic

Artifacts

Typical graph generation in the security area is creating

just nodes of one type and connecting them depending on communication [ 22 ] in graph or finding an attack vector in a directed graph [ 23 ]. Standard computer networkbased cybersecurity applications cover trafic, security policies and vulnerabilities/threats [ 24 ].

For the artefacts, one can create nodes from any attribute (column) or any combination of attributes. Moreover, we found the most interesting results for bipartite graphs, e.g., using two node types. Depending on the dataset, we focused on diferent pairs of node types.

4.3. Graph from supertimeline

For the super timeline, we have chosen attributes such as user, source, MACB, sourcetype and inode and always two of them as vertex types for the generated bipartite graph. We can consider other attributes that will be represented by vertices in the graph, e.g. host, type, filename. Some of these attributes are categorical so that we can think of them in this sense. The edge represents the row’s existence in data containing these two vertices (artefact). An example of the NIST Data Leakage case is shown in Fig. 2.

4.4. Graph from EVT artifacts

In the EVT dataset, we created binary combinations of three attributes: event_id, user_sid, and execution_process because we could not tell any vital information about the relationships between the attributes by selecting other attributes. We could also consider attributes like inode, computer_name, and source_name, since we assume they are finite in number and not binary values, but that probably wouldn’t add any value for us. An example of a generated graph from the EVT dataset is shown in Fig. 1.

4.5. Graph from FILE artefacts

In a similar way to the super timeline, we also created

graphs in the FILE dataset, but with diferent attributes, such as MACB, dir, file, and NTFS, the creation of which we explained in Chapter 3.2. In the datasets file, it was challenging to think of other attributes that would be suitable for graphing because they were in binary form. This is why we merged some attributes, but it was impossible for all of them. We would still include the inode attribute in the graph creation process, but it had many unique values. Examples of these graphs are in Fig. 4 and Fig. 5.

5. Lessons learned from graph properties

From the generated graphs, we have focused on some graph-based metrics [22] and found some anomalies. In the current research, we have used only unweighted graphs.

5.1. Eccentricity

2022. Fig. 3 shows the graph from the Magnet CTF 2022 case. The lowest eccentricities in this graph were in the vertices ’WinEVTX’ (source type attribute) and ’Patrick’ (user attribute). We observed the same behaviour in the other Magnet CTF cases - that is, the graph centre was always identified as the ’WinEVTX’ vertex and one of the users.

5.2. Degree of vertices

In particular, we can exploit eccentricity in graphs in

the super timeline dataset created from user and source We exploited the degree of vertex in the datasets created or user and source type attributes. For example, in the from the supertimeline from the FILE source. We creNIST Data Leakage Case in Fig. 2, we created a graph ated three types of graphs - MACB and file, MACB and from the user and source attributes and then found the dir, MACB and NTFS. Fig. 4 shows an example of such eccentricity of all vertices. The vertices belonging to a graph. The most interesting graphs arose when the the user attribute had the lowest eccentricity of 3: ’-’, MACB and NTFS timestamps were combined, as shown ’informant’, ’admin11’ and ’temporary’, and the vertices in Fig. 4. At first glance, it might seem that we should belonging to the source attribute had ’REG’ and ’EVT’. focus on the NTFS_UNS_change attribute because it is These vertices can also be called the centre of the graph. associated with timestamp C (Change), but neither the

We also created graphs from the user and source type ifle_stat and NTFS_file_stat vertices are, despite having attributes and searched for the graph centre. We can illus- the highest degree of vertex - 14. The most significant trate this with all three Magnet CTF cases 2019, 2020 and vertex in this graph is file_entry_shell_item with a vertex degree of 6 because if we look further at the records containing this NTFS attribute value, we find "only" 19 unique inode values in 163 records, and just 9 of these inodes were identified as relevant to the case.

5.3. Cycles in graphs

After creating the graph from The Stolen Szechuan Sauce

- FILE dataset in Fig. 5, it was not visible what specifically to focus on, so we had to apply the properties of the graph. We looked for the base cycles in the graph. We found 43 of these, and seven cycles contained inodes that were manually identified as relevant to the case by the analysis. In the same way, we analysed the graph created from the MACB and lfiename attributes, where we also found file names in the base cycles marked as relevant to the case by manual analysis. In this analysis, however, we must consider that the attributes are not equivalent because the MACB timestamps or combinations will always be at most 16, and the inodes are a diferent number, often much higher.

6. Results and future works

This paper focuses on the automation of response to secu

rity incidents, including digital forensic analysis within the Windows operating system and NTFS file system. For this purpose, we used the graphs’ structure and properties to better understand the relationships between the analysed digital evidence. The paper demonstrated the possibilities of generating graphs, particularly from super timeline formats, event records, and the Master File Table. We showed that it is essential to carefully select the attributes of artefacts that can be used as vertices and to determine the corresponding edges of the graphs. At the same time, we identified several properties of graphs, whose analysis can help better understand the relationships and identify interesting or relevant digital evidence. In the future, we will enhance our models with weighted graphs.

Acknowledgment

This paper was supported by the Slovak Research and Development Agency under contract No. APVV-23-0137 and contract No. APVV-21-0336.

References

[1] Iqbal , Salman, S. A. Alharbi , Advancing automation in digital forensic investigations using machine learning forensics, Digital Forensic Science . IntechOpen ( 2019 ).

[2] S. Costantini , G. D. Gasperis , R. Olivieri , Digital forensics and investigations meet artificial intelligence , Annals of Mathematics and Artificial Intelligence ( 2019 ).

[3] C. Easttom , Utilizing graph theory to model forensic examination , International Journal of Innovative Research in Information Security (IJIRIS) 4 ( 2017 ).

[4] I. Palmer , R. Campbell , B. Gelfand , Exploring digital evidence with graph theory , in: ADFSL Conference on Digital Forensics, Security and Law , 2017 .

[5] S. Ozcan , M. Astekin , N. K. Shashidhar , B. Zhou , Centrality and scalability analysis on distributed graph of large-scale e-mail dataset for digital forensics , in: IEEE International Conference on Big Data (Big Data) , 2020 .

[6] J. Binwal , R. Devi , B. Singh , Mathematical modelling and simulation of fingerprint analysis using graph isomorphism, domination, and graph pebbling , Advances and Applications in Discrete Mathematics ( 2023 ).

[7] C. Liu , A. Singhal , D. Wijesekera , Using attack graphs in forensic examinations , in: Seventh International Conference on Availability, Reliability and Security , 2012 .

[8] W. Wang , T. E. Daniels , Building evidence graphs for network forensics analysis , in: 21st Annual Computer Security Applications Conference (ACSAC'05) , 2005 .

[9] J. He , C. Chang , P. He , M. S. Pathan , Network forensics method based on evidence graph and vulnerability reasoning , MDPI, future internet ( 2016 ).

[10] C. McGee , J. Guo , Z. Wang, The application of the graph laplacian in network forensics , in: IEEE 12th Annual Information Technology, Electronics and Mobile Communication Conference (IEMCON) , 2021 .

[11] Case 001 - the stolen szechuan sauce , 2024 . URL: https://dfirmadness.com/ the-stolen - szechuan-sauce/, online, [cit. 2024- 02 - 18].

[12] Magnet ctf 2019 windows desktop , 2019 . URL: https://digitalcorpora.s3.amazonaws.com/ corpora/scenarios/magnet/2019%20CTF% 20 - % 20Windows-Desktop.zip, online, [cit. 2024- 02 -18].

[13] Magnet ctf 2020 windows, 2020 . URL: https://digitalcorpora.s3.amazonaws.com/ corpora/scenarios/magnet/2020%20CTF% 20 - % 20Windows.zip, online, [cit. 2024- 02 -18].

[14] Magnet ctf 2022 windows, 2022 . URL: https://digitalcorpora.s3.amazonaws.com/ corpora/scenarios/magnet/2022%20CTF% 20 - % 20Windows.zip, online, [cit. 2024- 02 -18].

[15] Data leakage case , 2024 . URL: https: //cfreds-archive. nist.gov/data_leakage_case/ data-leakage-case.html, online , [cit. 2024- 02 -18].

[16] Hacking case , 2024 . URL: https://cfreds-archive.nist. gov/Hacking_Case.html, online, [cit. 2024- 02 -18].

[17] E. Marková , P. Sokol , K. Kováčová , Detection of relevant digital evidence in the forensic timelines , in: International Conference on Electronics, Computers and Artificial Intelligence (ECAI) , IEEE, 2022 , pp. 1 - 7 .

[18] Plaso , 2024 . URL: https://plaso.readthedocs.io/en/ latest, online, [cit. 2024- 04 -13].

[19] E. Marková , P. Sokol , S. P. Krišáková , K. Kováčová , Dataset of windows operating system forensics artefacts, Data in Brief ( 2024 ) 110693 .

[20] D. B. West , Introduction to graph theory, Prentice hall, 2001 .

[21] B. Brešar , F. Kardoš , J. Katrenič , G. Semanišin, Minimum -path vertex cover , DAM 159 ( 2011 ) 1189 - 1195 .

[22] G. Zonneveld , L. Principi , M. Baldi , Using graph theory for improving machine learning-based detection of cyber attacks , 2024 . URL: https://arxiv. org/pdf/2402.07878.

[23] T. Mézešová , P. Sokol , T. Bajtoš , Evaluation of attackers' skill levels in multi-stage attacks , Information 11 ( 2020 ) 537 .

[24] V. P. Janeja , Data Analytics for Cybersecurity, Chapter 9: Cybersecurity through Network and Graph Data , 2022 . URL: https://doi.org/10.1017/ 9781108231954.