A VLAN Hopping Attack

In our recent Implement Layer 2 Technologies series, we examined Q-in-Q tunneling in great detail. In this discussion, I mentioned a big caution about the Service Provider cloud with 802.1Q trunks in use for switch to switch trunking. This caution involved the use of an untagged native VLAN.
You see, this configuration could lead to what is known as the VLAN hopping attack. Here is how it works:

1. A computer criminal at a customer site wants to send frames into a VLAN that they are not part of.
2. The evil-doer double tags the frame (Q-in-Q) with the outer frame matching the native VLAN in use at the provider edge switch.
3. The provider edge switch strips off the outer tag (because it matches the native VLAN), and send this frame across the trunk.
4. The next switch in the path examines the frame and reads the inner VLAN tag and forwards the frame accordingly. Yikes!

Notice the nature of this attack is unidirectional. The attacker can send traffic into the VLAN, but traffic will not return. Admittedly, this is still NOT something we want taking place!
What are solutions for the Service Provider?

1. Use ISL trunks in the cloud. Yuck.
2. Use a Native VLAN that is outside of the range permitted for the customer. Yuck.
3. Tag the native VLAN in the cloud. Awesome.