Targeted attacks against network infrastructure are notoriously difficult to
guard against. In the case of communication networks, such attacks can leave
users vulnerable to censorship and surveillance, even when cryptography is
used. Much of the existing work on network fault-tolerance focuses on random
faults and does not apply to adversarial faults (attacks). Centralized networks
have single points of failure by definition, leading to a growing popularity in
decentralized architectures and protocols for greater fault-tolerance. However,
centralized network structure can arise even when protocols are decentralized.
Despite their decentralized protocols, the Internet and World-Wide Web have
been shown both theoretically and historically to be highly susceptible to
attack, in part due to emergent structural centralization. When single points
of failure exist, they are potentially vulnerable to non-technological (i.e.,
coercive) attacks, suggesting the importance of a structural approach to
attack-tolerance. We show how the assumption of partial trust transitivity,
while more realistic than the assumption underlying webs of trust, can be used
to quantify the effective redundancy of a network as a function of trust
transitivity. We also prove that the effective redundancy of the wrap-around
butterfly topology increases exponentially with trust transitivity and describe
a novel concurrent multipath routing algorithm for constructing paths to
utilize that redundancy. When portions of network structure can be dictated our
results can be used to create scalable, attack-tolerant infrastructures. More
generally, our results provide a theoretical formalism for evaluating the
effects of network structure on adversarial fault-tolerance.
Edward L Platt
All Jonkman Microblog content and data are available under the Creative Commons Attribution 3.0 license.