  Network Address Translation (NAT) plays an essential role in shielding
devices inside an internal local area network from direct malicious accesses
from the public Internet. However, recent studies show the possibilities of
penetrating NAT boxes in some specific circumstances. The penetrated NAT box
can be exploited by attackers as a pivot to abuse the otherwise inaccessible
internal network resources, leading to serious security consequences. In this
paper, we aim to conduct an Internet-wide penetration testing on NAT boxes. The
main difference between our study and the previous ones is that ours is based
on the TCP/IP side channels. We explore the TCP/IP side channels in the
research literature, and find that the shared-IPID side channel is the most
suitable for NAT-penetration testing, as it satisfies the three requirements of
our study: generality, ethics, and robustness. Based on this side channel, we
develop an adaptive scanner that can accomplish the Internet-wide scanning in 5
days in a very non-aggressive manner. The evaluation shows that our scanner is
effective in both the controlled network and the real network. Our measurement
results reveal that more than 30,000 network middleboxes are potentially
vulnerable to NAT penetration. They are distributed across 154 countries and
4,146 different organizations, showing that NAT-penetration poses a serious
security threat.
