A number of multi-hop wireless reprogramming systems have emerged for sensor network retasking but none of these systems support a cryptographically-strong, public-key-based system for program authentication or any form of recovery from authenticated, but Byzantine, programs. The traditional techniques for authenticating a program and recovering from Byzantine user programs, namely a digital signature of the program hash and hardware-based memory protection, respectively, are not suited to resource-contrained sensor nodes. We present techniques that are consistent with the limited resources of sensor networks, can be used to secure existing wireless reprogramming systems, and allow recovery from Byzantine programs. Our solution to the secure reprogramming problem is based on authenticated streams. A program image consists of several code and data segments that are mapped to a series of messages for transmission over the network. A hash of the first message in this series is digitally signed and the hash and signature are prepended to the series. The signed hash authenticates the first message, which in turn contains a hash of the second message. Similarly, the second message contains a hash of the third message, and so on, recursively binding each message to the one logically preceding it in the series through the hash chain. The solution to the recovery problem requires both on- and off-chip hardware support in the form of a write-protected boot block and a grenade timer. Recovery is enforced by periodically resetting the node which executes a trusted bootloader located in the boot block. We implemented the security and recovery primitives using TinyOS and demonstrated that the overhead incurred is small compared with the cost of network programming.