Multi-step attacks have been widely adopted by attackers, resulting in privacy leakage. Although many cost-sensitive approaches have been proposed to respond to the multi-step attacks, most studies have lack global optimization and ignored the fact that attackers may take multiple paths to launch multi-step attacks, which may lead to an over-response or an under-response. To address this problem, we formulate a response to multi-path attacks as an optimization problem and prove it is NP-hard. To obtain a feasible solution to the problem, we first identify suspicious attack paths and evaluate several metrics (i.e., security benefit, deployment cost, and negative impact on the quality of services) of the countermeasures. Specifically, by considering the compositions and cover degrees of atomic attacks, we define Attacks Surface Coverage to accurately evaluate the security benefit of countermeasures. Then, we propose an improved greedy algorithm to select reasonable countermeasures. Experimental results demonstrate the effectiveness and feasibility of our approach.