SS-N-12 Sandbox is the NATO reporting name for the P-350 Bazalt (and its later modified version, the P-500 Bazalt), a large anti-ship cruise missile used by the Soviet Union and later by Russia. It was first deployed aboard Echo-II class guided missile submarines, replacing the older and more primitive SS-N-3 Shaddock. Around the same time it was used on the Kiev class hybrid cruiser/carrier as the primary ASuW weapon. Nowadays it is used only on the Slava class cruiser, and possibly in a land-launched coastal defense system.
The missile is approximately 12 meters long, with a wingspan of 2.6 meters, weighing five thousand kilograms including a 1000kg semi-armor-piercing conventional warhead or a 250kt nuclear physics package. It travels at Mach 2.5 (though it strikes its target at Mach 1.6 or so due to air resistance at low altitudes) and has a maxiumum range of 550km. For targeting it employs an inertial navigation system with midcourse updates, and an active radar seeker to locate its target in the final phase of flight.
The missile uses an unusual formation-flight pattern, shared with its successor the SS-N-19 Shipwreck - in a salvo of missiles, the first flies high, watching for targets with its radar, while the remaining missiles fly lower to evade counterdetection. Should the lead missile be destroyed, a random member of the formation will take up the position of the destroyed missile.
As the weapon's large size suggests, it was intended for attacking large warships, especially carriers and heavy amphibious ships (like the Wasp class). It is also believed to have a land-attack mode similar to Tomahawk.
A new revision of this missile exists, known as the P-1000 Vulkan. Its launchers are externally identical to those of Sandbox, and the missile itself looks very similar. As it no longer retains the Bazalt designation, it seems likely that it will receive a new NATO reporting name, though as yet this has not happened. The Vulkan is believed to be installed on the Slava class cruiser Varyag, but little other information is available regarding this weapon.
Sources: Google, hazegray.org, Jane's Fighting Ships