The Internet routing layer is at times too slow at recovering from faults and makes a sub-optimal use of redundancy available at the IP layer. Overlay networks can overcome these deficiencies to provide communication infrastructures with greater availability and flexibility. The majority of current experiences, however, are able to tolerate only simple (crash) failures of the underlying network. In this paper we present LITON, an overlay network architecture that aims at providing highly available communication in spite of faults and intrusions in the network. We also present a graph-theoretic model that allows the degree of fault and intrusion tolerance of a given overlay to be determined, as well as simulation results that validate this model and demonstrate that LITON accomplishes its goal even in worst-case scenarios.