Open Source Software Vulnerability Propagation Analysis Algorithm based on Knowledge Graph

With the extensive reuse of open source components, the scope of vulnerability impact will have cascade expansion. At the level of vulnerability data analysis, aiming at the vulnerability propagation problem, this thesis proposes a hierarchical propagation path search algorithm based on open source software vulnerability knowledge graph, at the same time, proposes a heuristic search strategy in both component layer and class layer to reduce the search space complexity, which is optimized from exponential down to polynomial. Furthermore, we propose the optimal blocking concept to represent the cost of repairing the entire propagation path, in order to measure the severity of the project's vulnerability. As for the purpose of providing effective suggestions on vulnerability repairing, we model the optimal blocking calculation as the network flow minimal separate problem, then calculate the network maximal flux to obtain the key dependencies with risks. Finally, multiple case studies with various vulnerability dependent risks show that the proposed algorithm can find software vulnerabilities affecting specific projects effectively.