In defending against multi-step attacks, network hardening answers the following important question: Which vulnerabilities must be removed from a network in order to prevent attackers from compromising critical resources while minimizing the implied cost in terms of availability or administrative efforts. Existing approaches to network hardening derive a logic proposition to represent the negation of the attack goal in terms of initially satisfied security conditions. In the disjunctive normal form (DNF) of the logic proposition, each disjunction then provides a viable solution to network hardening. However, such solutions suffer from an exponential time complexity. In this thesis, we study heuristic methods for solving this important problem with reasonable complexity. We evaluate our proposed solutions through extensive experiments. The results show that our solution can achieve reasonably good network hardening results in significantly less time than the optimal solution would require. Also, for scenarios where additional cost constraints may render a perfectly secure network hardening solution impossible, we extend our heuristic methods to partial hardening solutions. Such solutions can provide best possible improvement in terms of security under given cost constraints.