All types of network systems are subject to computer attacks. The overall security of a network cannot be determined by simply considering the vulnerable points in the network; it is essential to realize how vulnerabilities can be combined in the same host or in a set of connected hosts to initiate an attack. Attack graph is a tool for modeling compositions of vulnerabilities and thus representing possible multi-stage multi-host attacks in networks. Attack graphs can be used for measuring network security; supporting security solutions by identifying vulnerabilities that should be removed such that no attack can be realized targeting given critical resources, and thus hardening the network. We consider a general model of attack graphs and a scheme of attack graph generating algorithm; and investigate graph-theoretical problems related to particular tasks of network hardening.