{"id":3086,"date":"2022-04-12T15:27:00","date_gmt":"2022-04-12T21:27:00","guid":{"rendered":"https:\/\/wpsites.ucalgary.ca\/isec-601-f21\/?p=3086"},"modified":"2022-04-12T15:27:04","modified_gmt":"2022-04-12T21:27:04","slug":"graph-theory-in-computational-security","status":"publish","type":"post","link":"https:\/\/wpsites.ucalgary.ca\/isec-601-f21\/2022\/04\/12\/graph-theory-in-computational-security\/","title":{"rendered":"Graph Theory in Computational Security"},"content":{"rendered":"\n

The study of graphs consisting of nodes connected by edges representing some pairwise relation are of interest to security experts who wish to model complex computer or server networks. My paper describes several applications of graph theoretic results in cybersecurity, one of which is introduced here. <\/p>\n\n\n\n

The healthcare industry is a frequent target of cyberattacks due to overworked hospital staff, a problem only exacerbated as a result of Covid 19. Confidential patient data can be sold or ransomed for a lot of money, and hospitals often rely on outdated technology to keep information secure. The concept of a dominating set may be utilized when a lack of sufficient resources makes it impossible to guard every component of a system.<\/p>\n\n\n\n

We might model defenders as mobile guards defending a network, where a guard on vertex v can protect against an attack on any server adjacent to v by an edge. This set of vertices is known as the neighborhood of v, denoted N(v). If every vertex is protected in such a way by at least one guard, the network is said to be dominated<\/em>. The problem of determining the size of a minimum dominating set is an exact solution for efficiently defending networks against worm propagation.[1]<\/sup> <\/p>\n\n\n\n

Consider the small grid below. Guards located at vertices u, w, and y would dominate the graph, but so would two guards located at x and w. Since no vertex is adjacent to all other vertices, a dominating set of size 1 cannot exist, and hence the minimum domination number of the graph is 2.<\/p>\n\n\n\n

\"\"
Figure 1: A 2×3 grid.<\/figcaption><\/figure><\/div>\n\n\n\n

A dominating set S is secure<\/em> if exchanging a vertex outside of the dominating set for its neighbour in S results in a new dominating set. In our application, the network remains dominated even after a mobile guard were to move from his node to a neighboring node. In figure 1, the set {u, w, y} satisfies the secure dominating set condition but {x, w} does not: if vertex z were to be attacked, the guard on w would have to move, leaving v uncovered. <\/p>\n\n\n\n

\"\"
Figure 2: The Bloom Graph B3,6<\/sub>.[1]<\/sup><\/figcaption><\/figure><\/div>\n\n\n\n

Although determining the minimum size of a dominating or secure dominating set is NP-complete, exact constructions can be found in linear time for certain families of graphs. One such family is bloom graphs (above), whose symmetry and structure makes them appealing for large-scale parallel computer networks. It was shown in [1] that if Bm,n<\/sub> is a bloom graph with m ‘layers’ of n ‘petals’ each, the smallest possible secure dominating set has size n(ceiling(m\/2)).<\/p>\n\n\n\n

With a secure dominating set in place, safeguarding the nodes of the network and monitoring for any potential deficiencies becomes a significantly easier task.  <\/p>\n\n\n\n

References:<\/p>\n\n\n\n