Common software-protection systems attempt to detect malicious observation and modification of protected applications. Upon tamper detection, anti-hacking code may produce a crash or gradual failure, rendering the application unusable or troublesome. Such a response is designed to complicate attacks, but has also caused problems for developers and end users, particularly when bugs or other problems invoke anti-tampering measures accidentally. To address these issues, an alternative approach is to detect and fix malicious changes. This paper presents a scheme to transform programs into tamper-tolerant versions that use self-correcting operation as a response against attacks. Combining techniques from the fields of fault tolerance and software security, the approach transforms programs via code individualization and redundancy. We also describe security enhancements through error correction, delayed responses and checkpointing. For security analysis, we adapt a graph-based model of attacks and defenses in the context of software tamper-resistance. This helps to estimate the difficulty of breaking our scheme in practical scenarios.