The DOI matches its Crossref record; 16 of the 16 references it cites were found in a registry or an index.
Two formal analyses of attack graphs
Abstract
An attack graph is a succinct representation of all paths through a system that end in a state where an intruder has successfully achieved his goal. Today Red Teams determine the vulnerability of networked systems by drawing gigantic attack graphs by hand. Constructing attack graphs by hand is tedious, error-prone, and impractical for large systems. By viewing an attack as a violation of a safety property, we can use off-the-shelf model checking technology to produce attack graphs automatically: a successful path from the intruder's viewpoint is a counterexample produced by the model checker In this paper we present an algorithm for generating attack graphs using model checking as a subroutine. Security analysts use attack graphs for detection, defense and forensics. In this paper we present a minimization analysis technique that allows analysts to decide which minimal set of security measures would guarantee the safety of the system. We provide a formal characterization of this problem: we prove that it is polynomially equivalent to the minimum hitting set problem and we present a greedy algorithm with provable bounds. We also present a reliability analysis technique that allows analysts to perform a simple cost-benefit trade-off depending on the likelihoods of attacks. By interpreting attack graphs as Markov Decision Processes we can use the value iteration algorithm to compute the probabilities of intruder success for each attack the graph.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Rayward-Smith, V. J. (1991) · Journal of the Operational Research Society · doi:10.1057/jors.1991.155 · Cited by 16,821
Graph-Based Algorithms for Boolean Function Manipulation
Bryant (1986) · IEEE Transactions on Computers · doi:10.1109/tc.1986.1676819 · Cited by 8,891
Markov decision processes: Discrete stochastic dynamic programming
Hazeghi, K., & Puterman, M. L. (1995) · Journal of the American Statistical Association · doi:10.2307/2291177 · Cited by 8,037
Clarke, E. M., & Schlingloff, B. (1999) · Cited by 4,226
Probability: Theory and Examples.
Prewitt, K., & Durrett, R. (1992) · Journal of the American Statistical Association · doi:10.2307/2290301 · Cited by 3,085
Markov Decision Processes: Discrete Stochastic Dynamic Programming
Baxter, L. A. (1995) · Technometrics · doi:10.1080/00401706.1995.10484354 · Cited by 2,415
Constrained Markov Decision Processes: Stochastic Modeling
Altman, E. (2021) · Routledge eBooks · doi:10.1201/9781315140223 · Cited by 1,693
Automated generation and analysis of attack graphs
Sheyner, O., Haines, J., Jha, S., Lippmann, R., & Wing, J. M. (2005) · Proceedings 2002 IEEE Symposium on Security and Privacy · doi:10.1109/secpri.2002.1004377 · Cited by 1,293
Self-citationProbability: Theory and Examples.
Durrett, R. (1993) · Biometrics · doi:10.2307/2532227 · Cited by 857
A graph-based system for network-vulnerability analysis
Phillips, C., & Swiler, L. P. (1998) · Proceedings of the 1998 workshop on New security paradigms · doi:10.1145/310889.310919 · Cited by 828
NUSMV: a new symbolic model checker
Cimatti, A., Clarke, E. M., Giunchiglia, F., et al. (2000) · International Journal on Software Tools for Technology Transfer · doi:10.1007/s100090050046 · Cited by 726
Probabilistic Alert Correlation
Valdes, A., & Skinner, K. (2001) · Lecture Notes in Computer Science · doi:10.1007/3-540-45474-8_4 · Cited by 632
Using model checking to analyze network vulnerabilities
Ritchey, R. W., & Ammann, P. (2002) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/secpri.2000.848453 · Cited by 444
Experimenting with quantitative evaluation tools for monitoring operational security
Ortalo, R., Deswarte, Y., & Kaaniche, M. (1999) · IEEE Transactions on Software Engineering · doi:10.1109/32.815323 · Cited by 404
Computer-attack graph generation tool
Swiler, L. P., Phillips, C., Ellis, D., & Chakerian, S. (2002) · Proceedings DARPA Information Survivability Conference and Exposition II. DISCEX'01 · doi:10.1109/discex.2001.932182 · Cited by 324
Structure preserving reductions among convex optimization problems
Ausiello, G., D'Atri, A., & Protasi, M. (1980) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(80)90046-x · Cited by 264
Cited by
Scalable, graph-based network vulnerability analysis
Ammann, P., Wijesekera, D., & Kaushik, S. (2002) · Proceedings of the 9th ACM conference on Computer and communications security · doi:10.1145/586110.586140 · Cited by 697
Alshamrani, A., Myneni, S., Chowdhary, A., & Huang, D. (2019) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2019.2891891 · Cited by 656
Dynamic Security Risk Management Using Bayesian Attack Graphs
Poolsappasit, N., Dewri, R., & Ray, I. (2012) · IEEE Transactions on Dependable and Secure Computing · doi:10.1109/tdsc.2011.34 · Cited by 617
Constructing attack scenarios through correlation of intrusion alerts
Ning, P., Cui, Y., & Reeves, D. S. (2002) · Proceedings of the 9th ACM conference on Computer and communications security · doi:10.1145/586110.586144 · Cited by 495
A Survey on Systems Security Metrics
Pendleton, M., Garcia-Lebron, R., Cho, J.-H., & Xu, S. (2017) · ACM Computing Surveys · doi:10.1145/3005714 · Cited by 283
Metadata
- Authors
- Jha, S., Sheyner, O., & Wing, J.
- Venue
- Proceedings 15th IEEE Computer Security Foundations Workshop. CSFW-15
- Publisher
- IEEE Comput. Soc
- Published
- 2003-06-25
- Pages
- 49-63
- OpenAlex
- W2157554212
- Cited by
- 494
- References
- 16
- FWCI
- 17.77
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.