Graphs are excellent tools for modeling that are used to model various relations between different physical situations. Various problems can be represented using graphs. Graph theory is a branch of discrete mathematics that deals with the study of graphs to analyze the pair-wise relationship between objects (Singh, 2014). Graph theory is a significant component in diverse applications in computer science and computing including networking and security. The significant growth in the world mobile communication networks calls for improved solutions to the current existing challenges. Some of these challenges include lower bandwidth in mobile phones and the continuous change in their respective network topologies. These problems demand solutions such as the creation of network algorithms with high-speed execution and reduced communication traffic. The challenges mentioned above can be solved by applying graph theory in algorithms that need low communication rounds (Singh, 2014). Graph labeling is one of the crucial areas in graph theory. Graph labeling is used in various fields including radar, astronomy, coding theory, circuit design, communication network addressing, and database management amongst others. This paper gives an overview of different applications of graph theory in network security using its various components and how the theory has advanced the knowledge in network and security.
Detecting the vulnerability of a system to attack
Controlling information flow protects data security by keeping a check on how data is transmitted from objects to users of various security classifications (Wing, 2008). These classifications are expressed using labeling in relation to the data or its applications. This can be done by use of language based mechanism to ensure secure manipulation of data using dynamic security graph labels. The mechanism is formalized in a primary language by the lambda calculus that is typed with dependent security typologies, first class label values as well as run time label tests.
Delegate your assignment to our experts and they will do the rest.
For instance, a file that needs permissions before access, its information cannot be revealed until is opened by keying in the security code.
Attack graphs are used in the security community to determine the degree of vulnerability of a system to attack. Attack graphs comprise of paths which clearly show how an intruder can compromise or pose a danger to the security of a system (Wing, 2008). These graphs are hand drawn. Some of the examples of these manual attack graphs include wall-to-wall, floor to ceiling attack graph. The graph has boxes, and each box represents a single intruder attempt or action. A path from one of the far left box to one of the far right boxes represents various actions associated with a scenario of attack. At the end of such a scenario, it reveals that an intruder has broken into the system security in some way.
Since attack graphs are drawn manually, they are prone to errors including they might be incomplete hence missing other attacks, they may have redundant sub graphs or paths, and irrelevant transitions, nodes or paths. The relationship between attack graphs and scenario graphs is simplified. For a specified security property, a scenario graph is constructed for the system model to be secured such as preventing an intruder from accessing a particular host (Wing, 2008).Therefore, since each scenario graph represents specific property, many scenario graphs are generated to represent the attack graph that the security team may construct manually.
The primary reason for using scenario graphs adjacently with attack graphs is to improve the process by which attack graphs are produced. By use of scenario graphs, the technique goes beyond what human beings can do manually. The algorithms used in scenario graphs produce graphs that are exhaustive, sound and succinct making the resulting attack graphs not prone to the errors that humans make by hand drawing (Wing, 2008).
Attack graphs serve various functions in network security including defense, intrusion detection and forensic analysis (Wing, 2008). System administrators utilize attack graphs first in information collection: these graphs can reveal the attacks the system is vulnerable to as well as the various ways an intruder can attack the system from an original configuration (Wing, 2008). Secondly, administrators use attack graphs in decision making: these graphs can be used to determine the actions that can be put in place to prevent the intruder from attacking the system and the measures to deploy to constrain the intruder from achieving his goal.
Since the process of producing attack graphs can be automated, system administrators are given options on what is likely to happen if various changes are made to the system. Some of the changes include the addition of an intrusion system, change of firewall rules, removing a host from the system or installing a software patch (Wing, 2008). To overcome the above challenges, two analyses can be performed on the attack graphs: critical action set minimization and single action removal. The first one identifies various actions that need to be removed to prevent the intruder from attacking the system. The second one lets administrators learn the effect of removing one action from the intruder’s reach.
Graph theory in different types of communication networks
Graph theoretical ideas are of great importance in the representation of communication networks. Communication network/system is a group of links, terminals, and nodes which join to enhance efficient communication between terminal users (Sravanthi & Sudhakar, 2014). Different addresses are assigned to distinct terminals to ensure messages are passed to the right recipients. A communication network comprises three components including processors, terminals, and transmission channels. The primary aim of a communication network is to convey data packets between telephones, computers, processors or any other device. A packet is a fixed quantity of data for instance 4096 bytes or 256 bytes (Deswal & Singhrova, 2012).
Communication networks can be denoted using graphs which also help in comparison by switch count, switch size, and congestion. In general, vertices in a graph indicate terminals, edges, and processors correspond to channels of transmission such as fibers, wires amongst others through which information flows (Deswal & Singhrova, 2012).
Network representations are global in nature, in that for system administrators to retrieve crucial information, they must have access to data structure globally representing the entire system. Massive graphs are global ranging from communication and social networks to the World Wide Web (Deswal & Singhrova, 2012). The geometric representation of graphs imposed on these information sets plays a significant role in the visualization and comprehension of the data.
In sensor networks, graph labeling enhances faster communication with the aid of radiolabeling. In this case, each vertex stands for a transmitter and any pair of vertices linked through an edge represents neighboring transmitters. The kind of graph labeling used in Radiolabeling can be defined as G= (V (G), E (G)) represent a connected graph while the (u, v) correspond to the distance between vertices in G.
Automatic allocation of channels is possible in wireless networks because to get an efficient mechanism; safe transmissions are necessary in areas including Wi-Fi, cellular telephony, security systems amongst others (Deswal & Singhrova, 2012). If there are multiple candidate vertexes, then a deterministic section function is used in place of the final selection in vertex selection.
The above protocol operation is performed by recognizing the neighbors by listening to the messages generated from the access points. In social networks, graph labeling is most efficient and provides efficient communication. Effective communication is achieved by use of key graphs and certificates (Deswal & Singhrova, 2012). A significant contribution to the analysis of social network is associated with sociograms. A sociogram is a graphical representation of a system or network. People correspond to dots which are called vertices while their relationships are represented by lines linking the dots, which are referred to as edges.
Conclusively, in networking, we apply graph theory by representing communication networks using a binary tree. In a binary tree, squares correspond to source and destination of the data packets, while the circles denote switches. The role of the switch is to receive direct packets on arriving edges and transmit the departing along the existing edges. Since the path between two vertices in a binary tree is unique, the natural route to channel a data packet from the entering terminal to output terminal is along the equivalent directed path. In the field of security, we apply graph theory by use of attack graphs automatically to help identify the kind of attacks networks might be vulnerable to as well as to come up with security measures that will assist in ensuring no intruder can attack the systems in any particular manner.
REFERENCES
Deswal, S., & Singhrova, A. (2012, October). Application of Graph Theory in Communication Networks. International Journal of Application of Innovation in Engineering & Management, 1(2), 66-70.
Singh, R. P. (2014). Application of Graph Theory in Computer Science and Engineering. International Journal of Computer Applications, 104(1).
Sravanthi, K., & Sudhakar, N. (2014). Applications of Graph Labeling in Major areas of Computer Science. IJRCCT, 3(8), 819-823.
Wing, J. M. (2008). Scenario graphs applied to network security. Information Assurance: Survivability and Security in Networked Systems, 247-277. (Wing, 2008)
