Efficient Update on Exploitation Graphs for Vulnerability Analysis

A graph-based attack modeling technique is a formal approach for representing attack scenarios. One approach in this area is referred to as an exploitation graph (e-graph). This paper extends previous work on the e-graph approach by adding a function to efficiently insert new exploitations into the generated e-graph. The proposed algorithm has a time complexity that is much less than the original graph-generation algorithm. A case study is presented to support this claim. In addition to the update on the vulnerability information, the proposed technique can also be adapted to reflect updates on other security-related knowledge. This process will greatly assist the attack simulation process and can be used to perform various vulnerability studies.