  Man-At-The-End (MATE) attackers are almighty adversaries against whom there
exists no silver-bullet countermeasure. To raise the bar, a wide range of
protection measures were proposed in the literature each of which adds
resilience against certain attacks on certain digital assets of a program.
Intuitively, composing a set of protections (rather than applying just one of
them) can mitigate a wider range of attacks and hence offer a higher level of
security. Despite the potential benefits, very limited research has been done
on the composition of protections. Naive compositions could lead to conflicts
which, in turn, limit the application of protections, raise false alarms, and
worse yet, yield corrupted binaries. More importantly, inadequate compositions
of such protections are not tailored for the program at hand and thus the
offered security and performance are sub-optimal. In this paper, we first lay
out a set of generic constraints for a conflict-free composition of
protections. Then, we develop a composition framework based on a defense graph
in which nodes and edges capture protections, their relations, and constraints.
The conflicts problem together with optimization requirements are then
translated into a set of integer constraints. We then use Integer Linear
Programming (ILP) to handle conflicts while optimizing for a higher security
and lower overhead. To measure the overhead, we use a set of real-world
programs (MiBench dataset and open source games). Our evaluation results
indicate that our composition framework reduces the overhead by $\approx$ 39%
while maximizing the coverage. Moreover, our approach yields a 5-fold decrease
in overhead compared to state-of-the-art heuristics.
