Motivations
Many of the network diagrams I see online or in CSCD27 all look very similar, essentially a graph with computers as its nodes and connections as its edges. This led to me searching for applications of graph theory in network security and I found many using graph algorithms that we learned in this and other courses. In this post, I’ll explore two of them.
Guarding a network
Consider the problem of securing a network using guards (like a firewall to control and secure information exchange). That is, each flow of information between devices in a network needs to be secured by a guard on a device. Solutions to the problem can be simulated using graphs with devices as nodes and the flow of information as edges. Specific graph algorithms can be used to check if a set of nodes (guards to place on devices) is a vertex cover, covering all edges (flow of information). Moreover, minimum vertex cover algorithms (or approximations) can be used to calculate the (approximately) minimum number of guards needed to secure a network.
Identifying alerts
Another example of graph theory in security is with security related alerts. These alerts are usually triggered by some application because of some kind of defined suspicious activity. Alerts are crucial to monitoring security, however alerts can get redundant in large networks with many alerts of the same issue being triggered from different services. Such a problem can be solved with graphs by having alerts as nodes and the correlation between alerts as edges. Correlation can be determined by many factors such as the type of alert, time and the alerting application. Clustering algorithms can then be used to find clusters of nodes. The resulting clusters of alerts are usually related and all from the same or similar attack, helping programmers group and identify the source.
Conclusion
Both these applications of graph theory uses concepts we learned in our courses with vertex cover from CSCC63 and clustering from this course. In conclusion, graph theory is an important field of study with many interconnecting relationships between other computer science related fields.
Sources
Angel, D. (2022, June 21). Protection of medical information systems against cyber attacks: A graph theoretical approach. National Library of Medicine. Retrieved October 6, 2022, from https://www.ncbi.nlm.nih.gov/pmc/articles/PMC9209834/
Maida, L. (2022, May 27). Graph algorithms for cybersecurity: A picture is worth 1,000 rows – NEO4J. neo4j. Retrieved October 6, 2022, from https://neo4j.com/blog/graph-algorithms-cybersecurity-picture-worth-1000-rows/