Complexity Problems in the Analysis of Information Systems Security - Computer Network Security - page 54

6 Network Vulnerability
Global analysis of network vulnerabilities is often done in terms of attack graphs.
These graphs represent local, atomic vulnerabilities, maybe some probabilities,
and paths representing access to these vulnerabilities. The construction of such
graphs for real life networks must be automated, and the problem of ecient
methods immediately arises; the current knowledge seems to be insucient to
formulate reasonable complexity problems nowadays; the ontology is under de-
velopment (e. g. see [14]). On the other hand, if a graph for vulnerability analysis
is constructed, its processing brings us to problems that seem to be related in
spirit to traditional problems (e. g. see [24]). However, the big size of graphs
imposes more tough questions of the complexity, for example, whether this or
that question about the risk of attack on a particular node can be answered
without analysis of the whole graph.
7 Conclusion
One can see that we are arriving at a level of knowledge about the security
when complexity analysis becomes feasible and useful. Cryptography, practice
and theory, teaches us that reasoning about security must be well founded [15].
Complexity may give some insights. However, specific features of the security are
not yet describe in the complexity theory, in particular, what reductions preserve
this or that security property? However, this and other theoretical questions are
under study.
References
1. Amadio, R. and Charatonik, W.: On name generation and set-based analysis in the
Dolev-Yao model. In Proc. of the 13th International Conference on Concurrency
Theory (CONCUR'02), Lect. Notes in Comput. Sci., , Springer-Verlag (2002) 499-
514
2. Bellare, M., Desai, A., Pointcheval, D., and Rogaway, P.: Relations among notions
of security for public-key encryption schemes. Lecture Notes in Computer Science ,
1462 (1998) 26-45
3. Bellare, M.: Practice-oriented provable security. Lecture Notes in Computer Sci-
ence , 1561 (1999) 1-15
4. Bosworth, S. and Kabay, M.E. editors: Computer Security Handbook . John Wiley,
4th edition edition (2002)
5. Bauer, L., Ligatti, J., and Walker, D.: More enforceable security policies. In Il-
iano Cervesato, editor, Foundations of Computer Security , volume 02-12 of DIKU
technical reports , (July 25-26 2002) 95-104
6. Beauquier, D. and Slissenko, A.: A first order logic for specification of timed algo-
rithms: Basic properties and a decidable class. Annals of Pure and Applied Logic ,
113(1-3) (2002) 13-52