We have designed and implemented ARMor, a system that uses software fault isolation (SFI) to sandbox application code running on small embedded processors. Sandboxing can be used to protect components such as the RTOS and critical control loops from other, less-trusted components. ARMor guarantees memory safety and control flow integrity; it works by rewriting a binary to put a check in front of every potentially dangerous operation. We formally and automatically verify that an ARMored application respects the SFI safety properties using the HOL theorem prover. Thus, ARMor provides strong isolation guarantees and has an exceptionally small trusted computing base?there is no trusted compiler, binary rewriter, verifier, or operating system.