We consider the problem of optimal investment in cyber-security by an enterprise. Optimality is measured with respect to the overall (1) monetary cost of implementation, (2) negative side-effects of cyber-security controls (indirect costs), and (3) mitigation of the cyber-security risk. We consider “passive” and “reactive” threats, the former representing the case where attack attempts are independent of the defender’s plan, the latter, where attackers can adapt and react to an implemented cyber-security defense. Moreover, we model in three different ways the combined effect of multiple cyber-security controls, depending on their degree of complementarity and correlation. We also consider multi-stage attacks and the potential correlations in the success of different stages. First, we formalize the problem as a non-linear multi-objective integer programming. We then convert them into Mixed Integer Linear Programs (MILP) that very efficiently solve for the exact Pareto-optimal solutions even when the number of available controls is large. In our case study, we consider 27 of the most typical security controls, each with multiple intensity levels of implementation, and 37 common vulnerabilities facing a typical SME. We compare our findings against expert-recommended critical controls. We then investigate the effect of the security models on the resulting optimal plan and contrast the merits of different security metrics. In particular, we show the superior robustness of the security measures based on the “reactive” threat model, and the significance of the hitherto overlooked role of correlations.