Threat modeling for information technology infrastructure can be done using shortest path algorithms in stochastic graphs. By modeling the infrastructure as a graph, potential vulnerabilities may be presented by computing what paths an attacker might take. This thesis project presents and compares two memory efficient algorithms that can be used to solve this problem approximately, the online k-means and sampled k-shortest path algorithm. By computing paths for several different graph types, the two algorithms were compared against a naive algorithm. The online k-means algorithm uses approximately 77 times less memory, executes in the same amount of time, and produces similar path lengths. In our experiments, the sampled k-shortest path algorithm uses approximately 154 times less memory, execution time is seen to be lowered by a factor of 5 to 20 depending on the graph type, but path distances computed are longer.
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:liu-178160 |
| Date | January 2021 |
| Creators | Wrede, Simon |
| Publisher | Linköpings universitet, Programvara och system |
| Source Sets | DiVA Archive at Upsalla University |
| Language | English |
| Detected Language | English |
| Type | Student thesis, info:eu-repo/semantics/bachelorThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.1663 seconds