KR102689032B1 - Cyber attack route recommendation method of electronic apparatus - Google Patents

Abstract

Create a topology from the start node to the destination node based on the accessibility to the destination node, operational elements, and vulnerabilities of individual nodes, calculate the node weights of nodes included in the topology, and create an attack graph based on the topology and desired effects. Provides an electronic device and method of operating the same that generate, calculate the edge weight of the edge included in the attack graph, and check at least one shortest path from the start node to the destination node based on the node weight and the edge weight. .

Description

Cyber attack route recommendation method for electronic devices {CYBER ATTACK ROUTE RECOMMENDATION METHOD OF ELECTRONIC APPARATUS}

This disclosure relates to a method for recommending a cyber attack route for an electronic device.

Recently, in cyber attack defense, the attack graph method has been applied as a method of analyzing defense priority, defense probability, and probability of being attacked. The attack graph is used as a method to prepare appropriate defense measures by analyzing data from assets and devices based on attack scenarios.

The present invention automatically generates an optimal attack graph based on the enemy's network information, vulnerability information, and environmental information in order to recommend and determine the optimal offensive response plan and weapon in a cyber environment, thereby creating effective attack methods, routes, weapons, etc. This is a method and device for recommending. The technology of the present invention can clearly analyze the optimal attack path by using a method that can calculate the connection weight between nodes based on preconditions between vulnerabilities between nodes. The weight of the confidentiality, integrity, and availability values changes depending on the desired effect. To reflect this, the edge score value can be calculated including the weight according to the attack type and vulnerability prerequisites, creating a more optimized attack path to achieve the attack purpose. You can explore and establish attack plans.

The technical problem to be achieved by the present invention is not limited to the problems described above, and other technical problems can be inferred from the following examples.

According to one embodiment, a method for recommending a cyber attack path for an electronic device includes: generating a topology from a starting node to the destination node based on accessibility to the destination node, operational elements, and vulnerabilities of individual nodes; calculating node weights of nodes included in the topology; generating an attack graph based on the topology and desired effects, and calculating edge weights of edges included in the attack graph; and confirming at least one shortest path from the start node to the destination node based on the node weight and the edge weight.

According to one embodiment, an electronic device for cyber attack route recommendation, which generates a topology from a starting node to a destination node based on accessibility to the destination node, operational elements, and vulnerabilities, and nodes of nodes included in the topology. Calculate weights, create an attack graph based on the topology and desired effects, calculate edge weights of edges included in the attack graph, and based on the node weight and the edge weight, from the start node to the destination node. It may include a processor that checks at least one shortest path.

According to one embodiment, the computer-readable recording medium may include a non-transitory recording medium on which a program for executing the above-described operation method on a computer is recorded.

Details of other embodiments are included in the detailed description and drawings.

According to the present invention, it is possible to effectively analyze enemy information and automatically find an optimized attack path, so that intelligent and automated offensive response measures and weapons can be recommended and decision makers can be supported in their decisions.

In addition, according to the present invention, an optimal attack graph can be efficiently generated depending on accessibility and weapon possession, and an efficient offensive strategy can be determined.

In addition, according to the present invention, it is designed to calculate the values of nodes or edges of the attack graph based on the commander's desired effect, thereby generating an attack graph that is most suitable for the desired effect, so that effective offensive measures can be established.

The effect of the invention is not limited to the effects mentioned above, and other effects not mentioned can be clearly understood by those skilled in the art from the claims.

1 shows an electronic device according to the present disclosure.
Figure 2 shows a conceptual diagram of a method according to the present disclosure.
Figure 3 shows an example of an automatic attack graph generation unit according to the present disclosure.
Figure 4 shows one embodiment of a method according to the present disclosure.
Figure 5 shows one embodiment of a network topology according to the present disclosure.
Figure 6 shows an example of an attack graph according to the present disclosure.
7 shows an example of an attack graph according to the present disclosure.

The embodiments described in this disclosure are illustrative rather than limiting, and those skilled in the art may design many alternative embodiments without departing from the scope of the disclosure as defined by the appended claims. there is. The terms used in the embodiments are general terms that are currently widely used as much as possible while considering the functions in the present disclosure, but this may vary depending on the intention or precedent of a person working in the art, the emergence of new technology, etc. In addition, in certain cases, there are terms arbitrarily selected by the applicant, and in this case, the meaning will be described in detail in the relevant description. Therefore, the terms used in this disclosure should be defined based on the meaning of the term and the overall content of this disclosure, rather than simply the name of the term.

As used herein, the singular expressions singular and plural include both the singular and the plural, unless the context clearly states otherwise.

Throughout the specification, when a part is said to “include” certain elements or certain steps, this does not necessarily mean that any part must include all of the elements or steps, unless specifically stated to the contrary, and is not included in the claims. Additionally, it does not exclude the inclusion of components or steps other than those listed throughout the specification, but only means that they may be further included.

Additionally, terms containing ordinal numbers, such as first, second, etc., used in this specification may be used to describe various components, but the components should not be limited by terms containing the ordinal numbers. The above terms are used in context only to distinguish one element from another element in one part of the specification. For example, without departing from the scope of the present invention, a first element may be referred to as a second element in other parts of the specification, and conversely, the second element may also be referred to as a first element in other parts of the specification. It can be.

In this specification, terms such as “mechanism,” “element,” “means,” and “configuration” may be used broadly and are not limited to mechanical and physical configurations. The term may include the meaning of a series of software routines in connection with a processor, etc.

In this specification (particularly in the claims), the use of the term “above” and similar referential terms may refer to both the singular and the plural. In addition, when a range is described, it includes individual values within the range (unless there is a statement to the contrary), which is the same as describing each individual value constituting the range in the detailed description. Lastly, unless the order of the steps constituting the method is clearly stated or stated to the contrary, the steps may be rearranged and performed in an appropriate order, and are not necessarily limited to the order of description of the steps. The use of any examples or illustrative terms (e.g., etc.) is merely for illustrating the technical idea in detail, and the scope is not limited by the examples or illustrative terms unless limited by the claims. A person skilled in the art can add various modifications, combinations, and changes to the embodiments disclosed in this specification according to design conditions and factors to construct new embodiments that fall within the scope of the patent claims or their equivalents.

In the present disclosure, “topology” may mean “network topology” and may refer to the physical connection of elements (links, nodes, etc.) of a computer network, or the connection method.

In the present disclosure, “desired effect” may mean a negative effect that a user of the method according to the present disclosure wishes to generate in an adversary, a target node, or a target network. For example, the desired effect could be "Degrade", "Denial", "Destroy", "Deceive", "Disrupt", or "Manipulate". It can be included.

Hereinafter, embodiments of the present disclosure will be described with reference to the drawings.

1 illustrates an example, simplified block diagram of an electronic device 100 that may be used to practice at least one embodiment of the present disclosure. In various embodiments, electronic device 100 may be used to implement any system or method described in this disclosure. For example, electronic device 100 may include any data server, web server, portable computing device, personal computer, tablet computer, workstation, mobile phone, smart phone, or any other device described below. It can be configured to be used as an electronic device.

Electronic device 100 may include memory 120 and one or more processors 110 having one or more cache memories and a memory controller that may be configured to communicate with memory 120 . Additionally, the electronic device 100 may be connected to the electronic device 100 through one or more ports (e.g., Universal Serial Bus (USB), headphone jack, Lightning connector, Thunderbolt connector, etc.). May include devices. A device that can be connected to electronic device 100 can include a plurality of ports configured to receive fiber optic connectors. The configuration of electronic device 100 shown is intended as a specific example only for the purpose of illustrating preferred embodiments of the device. In the illustrated electronic device 100, only components related to the present embodiments are shown. Accordingly, it is obvious to those skilled in the art that the electronic device 100 may further include other general-purpose components in addition to the components shown.

Processor 110 may be used to cause electronic device 100 to provide the steps or functions of any embodiment described in this disclosure. For example, the processor 110 generally controls the electronic device 100 by executing programs stored in the memory 120 within the electronic device 100. The processor 110 may be implemented as a central processing unit (CPU), graphics processing unit (GPU), or application processor (AP) provided in the electronic device 100, but is not limited thereto.

The memory 120 is hardware that stores various data processed within the electronic device 100. The memory 120 can store data processed through the processor 110 and data to be processed in the electronic device 100. there is. In addition, the memory 120 stores basic programming and data structures that can provide the functions of at least one embodiment of the present disclosure, as well as applications (programs, code modules) that can provide the functions of the embodiments of the present disclosure. , commands), drivers, etc. can be saved. The memory 120 includes random access memory (RAM) such as dynamic random access memory (DRAM), static random access memory (SRAM), read-only memory (ROM), electrically erasable programmable read-only memory (EEPROM), CD- It may include ROM, Blu-ray or other optical disk storage, a hard disk drive (HDD), a solid state drive (SSD), or flash memory.

The method and each step according to the present disclosure can be performed by the electronic device 100 or the processor 110, but for simplicity of explanation, the following assumes that the processor 110 is the one performing the method and each step according to the present disclosure. This explains.

Figure 2 shows a conceptual diagram of a method according to the present disclosure. In one embodiment, processor 110 generates a topology from the starting node to the destination node based on the accessibility to the destination node, operational factors, and vulnerabilities of individual nodes, calculates node weights for nodes included in the topology, and , generate an attack graph based on topology and desired effects, calculate edge weights of edges included in the attack graph, and determine at least one shortest path from the start node to the destination node based on the node weight and edge weight. You can.

The information collection unit 220 shown in Figure 2, the automatic attack graph generation unit 230, the attack graph analysis unit 250, the offensive strategy recommendation unit 251, the weapon recommendation unit 252, and the attack route recommendation unit 253. may be included in the electronic device 100 or the processor 110.

The topology or reachable path-based topology 210 may include one or more paths that can be accessed or reached from a starting node to a destination node. A specific embodiment of the topology or accessible path-based topology 210 will be described later with reference to FIG. 5 .

In one embodiment, the information collection unit 220 may collect information such as operational elements, weapon information, and input information.

division utilization data Input information Information identification_ID INFO_ID Requested effect information REQ_EFFECT_INFO Weapon Information WEAPON_INFO Operation element information COMBAT_INFO User input information USER_INPUT Prerequisites between vulnerabilities CVE_PRECONDITION Collected information Collection information identification_ID COLLECT_ID Network information NETWORK_INFO Network access location information NETWORK_ACCESS_TYPE CVSS_SCOREInformation CVSS_SCORE Vulnerability information CVSS_INFO Asset information ASSET_INFO Accessibility Information REACHABILITY_INFO Attack type information CVE_ATTACK_TYPE

Table 1 shows information that the information collection unit 220 can collect. The information collection unit 220 may receive input information from a user or another electronic device. Information identification_ID may include the identifier of the input information. The desired effect information may include information about the desired effect. Weapon information may include weapons that a user or an ally can use to attack an enemy or enemy network. Operational element information may include resources such as weapons, attack teams, support weapons, and support teams that friendly forces can utilize to attack enemy forces or enemy networks. User input information may include additional information that the user can input. Preconditions between vulnerabilities may include preconditions between network vulnerabilities. For example, in order to attack using vulnerability A, you may need to attack using vulnerability B first. In this case, vulnerability B may be a prerequisite for vulnerability A.

The information collection unit 220 may collect information from other devices, networks, or databases in addition to input information. Collection information identification_ID may refer to the identifier of the collected information. Network information may include information about enemy networks. Network access location information may include nodes that can access the enemy network or one or more nodes included in the enemy network and their connection relationships. CVSS_SCORE information may include scores for one or more vulnerabilities defined by the Common Vulnerability Scoring System (CVSS). Vulnerability information may include information about vulnerabilities about an enemy, a target node, or one or more nodes included in the path from the start node to the target node. Asset information may include information about nodes included in the enemy network. Accessibility information may include information or a connection relationship regarding whether one or more nodes included in the enemy network can be accessed from another node. Attack type information may include information about attack types for vulnerabilities.

The automatic attack graph generation unit 230 may generate an attack graph or an optimal attack graph model 240 based on the information collected by the accessible path-based topology 210 and the information collection unit 220. The attack graph or optimal attack graph model 240 may include one or more paths from a start node to a destination node and transit nodes included in each path. Individual nodes included in the attack graph or optimal attack graph model 240 may be assigned a node weight or node rank (nodeRank). Edge weights may be assigned to individual edges included in the attack graph or optimal attack graph model 240. In particular, edge weights may be assigned based on desired effects. Methods for assigning node weights or edge weights will be described in detail later.

The attack graph analysis unit 250 may check at least one shortest path in the attack graph or the optimal attack graph model 240. The attack graph analysis unit 250 may include an offensive strategy recommendation unit 251, a weapon recommendation unit 252, and an attack route recommendation unit 253. The attack path recommendation unit 253 can recommend the optimal or shortest path to reach the destination node from the start node. The offensive countermeasure recommendation unit 251 and the weapon recommendation unit 252 can recommend operational elements and weapons necessary to execute an attack according to the attack route recommendation unit 253.

Figure 3 shows the elements necessary for the automatic attack graph generation unit 350 according to the present disclosure to generate an attack graph. The automatic attack graph generation unit 350 may be included in the electronic device 100 or the processor 110. The automatic attack graph generation unit 350 may generate an attack graph based on the desired effect 310, weapon information 320, collected information 330, and accessible network topology information 340. That is, the processor 110 can calculate the node weight of the node included in the topology, generate an attack graph based on the topology and the desired effect, and calculate the edge weight of the edge included in the attack graph.

The edge weight (edge_score) of each edge included in the attack graph can be calculated using the following equation.

In the above equation, AL refers to the Access Location indicator and AT refers to the Attack Type indicator. CIA stands for CIA (Confidentiality, Integrity and Availability) indicator. CCI stands for vulnerability correlation index (CVE Correlation Index). CVE stands for Common Vulnerabilities and Exposure. w1 to w4 mean weights for each indicator, and each weight can be set in advance by the user as needed.

In one embodiment, the processor 110 may check the edge weight based on the Common Vulnerability Scoring System (CVSS) attack vector of each end node of the edge. Specifically, the processor 110 may calculate an access location indicator (AL) based on the Common Vulnerability Scoring System (CVSS) attack vector of each end node of the edge.

The approach location indicator can be calculated using the following equation.

In the above equation, Node _i ALweight and Node _j ALweight mean the access position weight of node i and the access position weight of node j, respectively. The access location weight can be defined according to the method by which each node can be accessed. The access location weight can be defined using the following Table 2 based on the attack vector weight of CVSS.

type CVSS version 1.0 2.0 3.0++ Network 1.0 1.0 0.85 Adjacent Network - 0.646 0.62 Local 0.7 0.395 0.55 Physical - - 0.20

Table 2 shows the attack vector weights defined in CVSS, depending on the CVSS version. Assuming that CVSS 3.0 or higher is used, for example, if node i is accessible through an external network, Node _i ALweight may be 0.85. For another example, if node i is accessible only from a nearby external network, Node _i ALweight may be 0.62. For another example, if node i is accessible only from the local network or internal network, the Node _i ALweight may be 0.55. For another example, if node i is only accessible by physical means, Node _i ALweight may be 0.20.

Therefore, for example, if node i is accessible only from the adjacent network and node j is accessible only from the local network, the access location weight in this case can be 0.62 * 0.55 = 0.341.

In one embodiment, the processor 110 may check the edge weight based on the probability of occurrence of at least one attack type regarding both end nodes of the edge. Specifically, the processor 110 may calculate an attack type indicator (AT) based on the probability of occurrence of at least one attack type with respect to both end nodes of the edge.

The attack type may be a classification of vulnerabilities to cyber assets according to the attack method. Attack types can be classified into the following types, but other classification methods may be used as needed. For example, attack types include Denial of Service (DoS), Code Execution, Overflow, Memory Corruption, Cross Site Scripting (XSS), Directory Traversal, and HTTP. This may include HTTP response Splitting, Bypass Something, Gain Privileges, Cross Site Request Forgery (CSRF), File Inclusion, etc.

The attack type indicator can be calculated using the following equation:

In the above equation, numberofattack _i means the number of attacks on vulnerabilities corresponding to attack type i, means the total number of attacks. The number of attacks that occurred for vulnerabilities by attack type can be collected using publicly available data as shown in Table 3 below.

DoS Code Execution Overflow Memory Corruption 1836 3843 1680 484 CSS Directory Traversal Http response splitting Bypass Something 2703 503 5 874 Gain Privileges CSRF File Inclusion 260 504 46

For example, the attack type indicator for the DoS attack type may be 0.1287, which is divided by 1,836, the number of occurrences of the DoS attack type, by 14,318, the total number of attacks shown in the table above.

In one embodiment, the processor 110 may check the edge weight based on whether the vulnerability of the first node among the nodes at both ends of the edge is a prerequisite for the vulnerability of the second node among the nodes at both ends of the edge. Specifically, the processor 110 may check the vulnerability correlation index (CCI) based on whether the vulnerability of the first node among the nodes at both ends of the edge is a prerequisite for the vulnerability of the second node among the nodes at both ends of the edge.

The vulnerability correlation indicator can be confirmed using the following equation.

In the above equation, c _i,j = c(v _i ,v _j ), and v _i and v _j mean the vulnerabilities of node i and node j, respectively. c(v _i ,v _j ) can be set in advance depending on whether node i's vulnerability v _i is a prerequisite for node j's vulnerability v _j . For example, c(v _i ,v _j ) can be set according to the following table.

c(v _i ,v _j ) v _j go v _i prerequisites v _j go v _i Not a prerequisite for v _i go v _j prerequisites 5 3 v _i go v _j Not a prerequisite for 3 One

For example, if node i's vulnerability v _i is a prerequisite for node j's vulnerability v _j , but node j's vulnerability v _j is not a prerequisite for node i's vulnerability v _i , c(v _i ,v _j ) = It can be 3.

Whether node i's vulnerability v _i is a prerequisite for node j's vulnerability v _j can be analyzed in advance, and when determining whether it is a prerequisite, the vulnerability number, type, service, connection method, pre-authorization, post-authorization, or possibility of CVSS are considered. data can be taken into account.

In one embodiment, processor 110 determines the desired effect based on the Confidentiality Impact, Integrity Impact, and Availability Impact of at least one vulnerability corresponding to at least one attack type. You can check the edge weight. Specifically, the processor 110 provides CIA indicators based on the Confidentiality Impact, Integrity Impact, and Availability Impact of at least one vulnerability corresponding to at least one attack type with respect to the desired effect. (CIA) can be checked.

The CIA indicator can be checked using the following equation.

In the above equation, CVSS _{confidentiality} , CVSS _integrity , and CVSS _availability mean Confidentiality Impact, Integrity Impact, and Availability Impact defined in CVSS, respectively. Additionally, RE _{confidentiality} , RE _integrity , and RE _availability mean weights for confidentiality, integrity, and availability impacts.

Confidentiality, integrity, and availability impacts can be set according to the following table for each version of CVSS, depending on the magnitude of each impact.

type CVSS version 1.0 2.0 3.0++ High 1.0 0.66 0.56 Low 0.7 0.275 0.22 None 0.0 0.0 0.0

For example, when using CVSS 3.0 or higher, if the confidentiality impact of a particular vulnerability is high, the CVSS _{confidentiality} of that vulnerability may be 0.56.

In one embodiment, processor 110 may determine edge weights based on the average of the confidentiality impact, the average of the integrity impact, and the average of the availability impact of at least one vulnerability corresponding to each of the at least one attack type with respect to the desired effect. there is. Specifically, the processor 110 determines the confidentiality, integrity, and availability impacts based on the average of the confidentiality impact, the average of the integrity impact, and the average of the availability impact of at least one vulnerability corresponding to each of at least one attack type with respect to the desired effect. The weights for RE _{confidentiality} , RE _integrity , and RE _availability can be calculated.

The weight for confidentiality impact (RE _{confidentiality} ) can be calculated using the equation below.

In the above equation, ACI(AT _i ) means the average of the confidentiality impact (Average of CI) of vulnerabilities corresponding to the ith attack type among n attack types associated with a specific desired effect. The attack type may be one of the attack types shown in Table 3. For example, if the attack types related to Destroy among the desired effects are two types, DoS (Denial of Service) and Code Execution, n is 2.

The average confidentiality impact of vulnerabilities corresponding to a specific attack type can be calculated using the following equation:

In the above equation, CVE(CI) _k means the Confidentiality Impact (CI) of the kth vulnerability (CVE) among m vulnerabilities corresponding to a specific attack type.

The weight for integrity impact (RE _integrity ) can be calculated using the equation below.

In the above equation, AII(AT _i ) means the average of the integrity impact (Average of II) of vulnerabilities corresponding to the ith attack type among n attack types associated with a specific desired effect. The attack type may be one of the attack types shown in Table 3.

The average integrity impact of vulnerabilities corresponding to a specific attack type can be calculated using the following equation:

In the above equation, CVE(II) _k means the integrity impact (II) of the kth vulnerability (CVE) among m vulnerabilities corresponding to a specific attack type.

The weight for availability impact (RE _availability ) can be calculated using the equation below.

In the above equation, ACI(AT _i ) means the average of the availability impact of vulnerabilities corresponding to the ith attack type among n attack types associated with a specific desired effect (Average of AI). The attack type may be one of the attack types shown in Table 3.

The average availability impact of vulnerabilities corresponding to a specific attack type can be calculated using the following equation:

In the above equation, CVE(AI) _k means the availability impact of the kth vulnerability (CVE) among m vulnerabilities corresponding to a specific attack type.

In one embodiment, the processor 110 may calculate node weights based on CVSS scores regarding vulnerabilities and operational elements of nodes included in the topology. Specifically, the node weight (nodeRank) included in the attack graph can be calculated using the following equation.

In the above equation, VulScore may be the score of the vulnerability of the node. For example, VulScore could be the BaseVector score of CVSS. Additionally, OperationScore may be a score for an operational element. OperationScore can be predefined considering attack weapons, attack team, support weapons, support team, etc. v and o may mean a weight for each score and may be predefined. v and o may be values between 0 and 1.

Figure 4 shows one embodiment of a method according to the present disclosure. As long as the order of each step is not clearly logically contradictory, the steps shown in Figure 4 may be reversed. In one embodiment, the processor 110 may select a start node S and a destination node G according to step S410. The processor 110 may analyze accessibility from the start node S to the destination node G according to step S411. From the start node S to the destination node G may be directly accessible, or may be accessible through one or more transit nodes.

Processor 110 may load operational elements and vulnerabilities according to step S412. For example, operational elements and vulnerabilities can be loaded from a separate database or obtained from user input.

The processor 110 may generate an accessibility-based topology in step S413. An example of an accessibility-based topology is shown in Figure 5.

The processor 110 may calculate the node weight (nodeRank) of all nodes in the topology according to step S414. To calculate the node weight, Equation 12 can be used.

The processor 110 may receive a desired effect input from the user in step S415. Thereafter, the processor 110 may calculate edge weights (edge scores) for edges between all nodes included in the topology based on the desired effect received in step S416.

The processor 110 may generate an attack graph based on topology, node weights, and edge weights in step S417. Examples of attack graphs are shown in Figures 6 and 7.

The processor 110 may execute a task of generating an optimal or shortest path in the attack graph according to step S418. Specifically, the processor 110 may generate k optimal path attack graphs based on the k-shortest algorithm.

First, the processor 110 may initialize a loop in step S419. AGn represents the sequence number of the optimal path. The processor 110 may initialize AGn to 1. k represents the total number of optimal paths. k can be set by the user. The processor 110 can generate n optimal path attack graphs by initializing k=n.

The processor 110 may search the AGnth optimal path attack graph in step S420. At this time, known shortest path search algorithms such as the Djakstra algorithm or the Customizable Contraction Hierarchies (CCH) algorithm may be used as the optimal or shortest path search algorithm. Thereafter, the processor 110 may generate the optimal path AGn in step S421.

The processor 110 may increase the value of AGn by 1 in step S422 and check whether AGn exceeds k in step S423. If AGn does not exceed k, the processor 110 may return to step S420 and repeat steps S420 to S423. If AGn exceeds k, k optimal or shortest path attack graphs have been created, so the processor 110 can end the loop and derive the optimal path attack graph set in step S424. Finally, the processor 110 may sort the optimal or shortest path attack graph in order of shortest distance or rank according to step S425. That is, the processor 110 can confirm the shortest path with a preset rank using the Dijkstra algorithm or the CCH algorithm.

At this time, the shortest path or optimal path may mean a path with the smallest or largest value calculated based on the node weight and edge weight. For example, the shortest path or optimal path may mean the path in which the sum, product, or weighted sum of node weights and edge weights is the smallest or the largest.

Specifically, steps S419 to S423 may be executed according to the algorithm shown in the following table.

function GenerateAG_KShortestPath(Graph, source, sink, K):
// Determine the shortest path from the start node to the destination node
A[0] = CCH or Dijkstra(Graph, source, sink);
// initialize a set to store the potential k shortest path
B = [];
for k from 1 to K:
// branch nodes are set from the first node to the node adjacent to the last node of the previous k-shortest path
for i from 0 to size(A[k-1]) - 2:
// The branch node is obtained from the k-1th path, which is the previous k-shortest path.
spurNode = A[k-1].node(i);
// Sequence from start node to branch node of previous k-shortest path
rootPath = A[k-1].nodes(0, i);
for each path p in A:
if rootPath == p.nodes(0, i):
// Remove edges that are part of previous shortest paths that share the same root path
remove p.edge(i,i + 1) from Graph;
for each node rootPathNode in rootPath except spurNode:
remove rootPathNode from Graph;
// Check the branch path from the branch node to the destination node
spurPath = CCH or Dijkstra(Graph, spurNode, sink);
// The full path is created by concatenating the root path and branch path.
totalPath = rootPath + spurPath;
// Store potential k-shortest paths in heap
if (totalPath not in B):
B.append(totalPath);
// Restore removed edges and nodes.
restore edges to graph;
restore nodes in rootPath to Graph;
if B is empty:
// Action when no branch path remains
break;
// Sort potential k-shortest paths according to their weights
B.sort();
// The path with the lowest weight becomes the k-shortest path
A[k] = B[0];
// Pop the first path from the heap
B.pop();
return A;

FIG. 5 illustrates an embodiment of an accessibility-based topology or network topology 500 according to the present disclosure. Processor 110 may generate the topology shown in FIG. 5.

The processor 110 may confirm that node B 551, node C 552, and node D 553 are accessible 520 from the starting node A 510. At this time, the processor 110 checks vulnerabilities V _b (531), V c (532), and V _d (533) for each of the accessible node B (552), node _C (552), and node D (553). You can.

The processor 110 uses the information according to Table 1 to determine that it possesses weapons 540 against vulnerabilities V _b (531) and V _c (532) of node B (552) and node C (552), respectively. You can check it.

Next, the processor 110 can confirm that node E (591) and node F (592) are accessible (561, 562) from node B (551), node C (552), and node D (553). The processor 110 can check vulnerabilities V _e (571) and V _f (572) for node E (591) and node F (592), respectively.

The processor 110 can confirm that it possesses a weapon (580) against the vulnerability V _f (572) of the node F (592) using the information according to Table 1.

Figures 6 and 7 show one embodiment of attack graphs 600 and 700 according to the present disclosure. The processor 110 may generate the attack graph 600 shown in FIG. 6 based on the accessibility-based topology from the starting node S to the destination node G. A node weight (nodeRank) may be assigned to each node, and an edge weight (edge score) may be assigned to each edge. The node weights of all nodes included in the attack graph 600 can be calculated using Equation 12, and the edge weights of all edges included in the attack graph 600 can be calculated using Equation 1.

The processor 110 may identify one or more optimal or shortest paths from the start node S to the destination node G of the attack graph 600 using the method or algorithm shown in FIG. 4 or Table 6.

For example, the processor 110 may check the paths of the first shortest path [S, V1, G] and the second shortest path [S, B2, V6, G], as shown in Figure 7. As shown in Figure 7, an optimal or shortest path attack graph 700 can be created.

FIG. 8 shows a method of operating the electronic device 100 according to an embodiment. Since each step of the operation method of FIG. 8 can be performed by the electronic device 100 of FIG. 1, description of content that overlaps with FIG. 1 will be omitted.

In step S810, the electronic device 100 may generate a topology from the start node to the destination node based on accessibility to the destination node, operational factors, and vulnerabilities of individual nodes.

In step S820, the electronic device 100 may calculate the node weight of the node included in the topology.

The electronic device 100 may calculate the node weight based on the CVSS score regarding vulnerabilities of nodes included in the topology and the scores regarding operational elements.

In step S830, the electronic device 100 may generate an attack graph based on the topology and desired effects and calculate edge weights of edges included in the attack graph.

The electronic device 100 can check the edge weight based on the Common Vulnerability Scoring System (CVSS) attack vector of each end node of the edge.

The electronic device 100 may check the edge weight based on the probability of occurrence of at least one attack type regarding both end nodes of the edge.

The electronic device 100 may check the edge weight based on whether the vulnerability of the first node among the nodes at both ends of the edge is a prerequisite for the vulnerability of the second node among the nodes at both ends of the edge.

The electronic device 100 determines the edge weight based on the Confidentiality Impact, Integrity Impact, and Availability Impact of at least one vulnerability corresponding to at least one attack type with respect to the desired effect. You can.

The electronic device 100 may check the edge weight based on the average of the confidentiality impact, the average of the integrity impact, and the average of the availability impact of at least one vulnerability corresponding to each of at least one attack type with respect to the desired effect.

In step S840, the electronic device 100 may check at least one shortest path from the start node to the destination node based on the node weight and the edge weight.

The electronic device 100 may check the shortest path with a preset ranking using the Dijkstra algorithm or the Customizable Contraction Hierarchies (CCH) algorithm.

Embodiments according to the present disclosure described above may be implemented in the form of program instructions that can be executed through various computer components and recorded on a computer-readable recording medium or non-transitory recording medium. The computer-readable recording medium or non-transitory recording medium may include program instructions, data files, data structures, etc., singly or in combination. Program instructions recorded on the computer-readable recording medium or non-transitory recording medium may be specially designed and constructed for the present invention or may be known and usable by those skilled in the computer software field. Examples of computer-readable recording media or non-transitory recording media include magnetic media such as hard disks, floppy disks and magnetic tapes, optical recording media such as CD-ROMs and DVDs, and magneto-optical media such as floptical disks. Includes magneto-optical media and hardware devices specifically configured to store and perform program instructions, such as ROM, RAM, flash memory, etc. Examples of program instructions include not only machine language code such as that created by a compiler, but also high-level language code that can be executed by a computer using an interpreter or the like. The hardware device or electronic device may be configured to operate as one or more software modules to perform processing according to the present disclosure, and vice versa.

This embodiment can be represented by functional block configurations and various processing steps. These functional blocks may be implemented as various numbers of hardware, software, or combinations thereof that execute specific functions. For example, embodiments include integrated circuit configurations such as memory, processing, logic, look-up tables, etc. that can execute various functions under the control of one or more microprocessors or other control devices. can be hired. Similar to how the components can be implemented as software programming or software elements, the present embodiments include various algorithms implemented as combinations of data structures, processes, routines or other programming constructs, such as C, C++, Java ( It can be implemented in a programming or scripting language such as Java), assembler, etc. Functional aspects may be implemented as algorithms running on one or more processors. Additionally, this embodiment may employ conventional technologies for electronic environment setting, signal processing, data processing, or a combination thereof.

Claims (10)

In the method of recommending a cyber attack route for an electronic device,
generating a topology from a starting node to the destination node based on accessibility to the destination node, operational factors, and vulnerabilities of individual nodes;
calculating node weights of nodes included in the topology;
generating an attack graph based on the topology and desired effects, and calculating edge weights of edges included in the attack graph; and
Confirming at least one shortest path from the start node to the destination node based on the node weight and the edge weight,
The step of calculating the edge weight is,
An access location indicator based on the CVSS (Common Vulnerability Scoring System) attack vector of each end node of the edge, an attack type indicator based on the probability of occurrence of at least one attack type for both end nodes of the edge, A vulnerability correlation indicator based on whether the vulnerability of the first node among the nodes at both ends of the edge is a prerequisite for the vulnerability of the second node among the nodes at both ends of the edge, and at least one attack type corresponding to the desired effect Cyber, comprising the step of checking the edge weight based on the Confidentiality, Integrity and Availability (CIA) indicator based on the Confidentiality Impact, Integrity Impact and Availability Impact of one vulnerability How to recommend attack routes. delete delete delete delete According to paragraph 1,
The step of calculating the edge weight is,
Identifying the CIA indicator based on the average confidentiality impact, average integrity impact, and average availability impact of at least one vulnerability corresponding to each of the at least one attack type with respect to the desired effect,
How to recommend cyber attack routes. According to paragraph 1,
The step of calculating the node weight is,
Comprising the step of calculating the node weight based on the CVSS score regarding the vulnerability of the node included in the topology and the score regarding the operational element,
How to recommend cyber attack routes. According to paragraph 1,
The step of checking the at least one shortest path includes:
A method of recommending a cyber attack path, including the step of checking the shortest path of a preset rank using Dijkstra's algorithm or CCH (Customizable Contraction Hierarchies) algorithm. As an electronic device,
a memory in which at least one program is stored; and
By executing the at least one program,
Create a topology from the start node to the destination node based on the accessibility to the destination node, operational elements, and vulnerabilities of individual nodes,
Calculate the node weight of the node included in the topology,
Generating an attack graph based on the topology and desired effects, calculating edge weights of edges included in the attack graph,
A processor that determines at least one shortest path from a starting node to a destination node based on the node weight and the edge weight,
The processor,
An access location indicator based on the CVSS attack vector of each end node of the edge, an attack type indicator based on the probability of occurrence of at least one attack type regarding both end nodes of the edge, and a first node among both end nodes of the edge A vulnerability relevance indicator based on whether the vulnerability is a prerequisite for a vulnerability in a second node of the edge nodes, and confidentiality impact, integrity impact, and Checking the edge weights based on CIA metrics based on availability impacts,
Electronic devices. It is a non-transitory computer-readable recording medium that records a program for executing a cyber attack path recommendation method for electronic devices on a computer,
The cyber attack route recommendation method is,
generating a topology from the starting node to the destination node based on the accessibility to the destination node, operational factors, and vulnerabilities of individual nodes;
calculating node weights of nodes included in the topology;
generating an attack graph based on the topology and desired effects, and calculating edge weights of edges included in the attack graph; and
Confirming at least one shortest path from a starting node to a destination node based on the node weight and the edge weight,
The step of calculating the edge weight is,
An access location indicator based on the CVSS attack vector of each end node of the edge, an attack type indicator based on the probability of occurrence of at least one attack type regarding both end nodes of the edge, and a first node among both end nodes of the edge a vulnerability relevance indicator based on whether the vulnerability is a prerequisite for a vulnerability in a second node of the edge nodes, and confidentiality impact, integrity impact, and Verifying the edge weight based on a CIA metric based on availability impact,
Non-transitory recording medium.

Images