Since the 9/11 terrorist attacks, the effective and efficient protection of critical information infrastructures has become an even more important issue. To enhance network survivability, a network operator needs to invest a fixed amount of budget and distribute it properly. However, a potential attacker will always adjust his attack strategies to compromise a network at minimal cost, if he knows the resource allocation strategy of the network operator. In this paper, we first evaluate the survivability of a given network under two different metrics; that is, we assess the minimal attack cost incurred by an attacker. The two survivability metrics are assumed to be the connectivity of at least one given critical Origin- Destination pair (OD pair) and that of all given critical OD pairs. We then analyze the problem with two optimization-based models, in which the problem structure is, by nature, a mixed integer programming problem.