A processor that protects an execution pipeline includes a residue-based error detection infrastructure including a first logic for computing a first residue of a result of an executed instruction instance, and a second logic for computing a second residue of the result. The second logic applies arithmetic operations of the executed instruction instance to residues of operands of the instruction instance. The execution pipeline includes registers and one or more arithmetic execution units. A method of protecting an execution pipeline includes performing one or more operations of an instruction instance on residues of operands of the instruction instance, computing a first residue of a result of the operations on the operand residues, computing a second residue from a result of executing the instruction instance, and checking the first residue against the second residue to determine whether errors were introduced while the instruction instance was resident in the execution pipeline.