Would they wear those treads that go on the bottom of your shoes? Effectiveness varies but I've seen some nice ones at REI.

You want the ones with actual "teeth", not the ones that use coiled wire.

Edit: Apparently this has already been suggested.