Patent ID: 7971252

Claim:
A method to generate an attack graph, comprising: using a computer processor for: selecting a first state node as a starting point of a cyber attack, the first state node corresponding to access to a first host in a network; coupling the first state node to a first prerequisite node having a first precondition satisfied by the first state node by generating a first directed edge from the first state node to the prerequisite node; coupling the first prerequisite node to a first vulnerability instance node having a second precondition satisfied by the first prerequisite node by generating a second directed edge from the first prerequisite node to the first vulnerability instance node, each vulnerability instance node on the attack graph having a single directed edge from the vulnerability instance node to exactly one state node, each vulnerability instance node indicating a presence of a vulnerability on a port, each prerequisite node representing a prerequisite required to access at least one port associated with a vulnerability instance node; coupling the first vulnerability instance node to a second state node having a third precondition satisfied by the first vulnerability instance node by generating a third directed edge from the first vulnerability instance node to the second state node; determining if a potential node, having a fourth precondition satisfied by a current node on the attack graph, provides a fifth precondition equivalent to one of preconditions provided by a group of preexisting nodes, the group of preexisting nodes comprising the first state node, the first vulnerability instance node, the first prerequisite node and the second state node; if the fifth precondition is equivalent to one of the preconditions provided by the group of preexisting nodes, coupling the current node to a preexisting node providing the precondition equivalent to the fifth precondition by generating a fourth directed edge from the current node to the preexisting node; and if the fifth precondition is not equivalent to one of the preconditions provided by the group of preexisting nodes: generating the potential node as a new node on the attack graph; and coupling the new node to the current node by generating a fifth directed edge from the current node to the new node.