Design and implementation of instruction indirection for embedded software obfuscation

• Tamper-aware use of the Instruction Register File (IRF) is presented.
• Two heuristic algorithms are presented to find sub-optimal IRF assignments against tampering.
• For a small IRF, our precision-oriented algorithm obtained the optimal assignments in most cases.
• Our time-oriented algorithm completed the calculation in 16 milliseconds for a 1024-entry IRF.
• The additional logic amount for a large IRF is comparable to similar techniques.

Instruction Register File (IRF) was originally proposed to reduce the power consumption of a microprocessor by providing the indirect access to frequently executed instructions. The IRF is also an attractive and cost-effective unit to protect embedded software from analysis, plagiarism, and falsification. For this purpose, the correspondences between IRF entries and their original instructions must be concealed. This means the instructions in the IRF should be carefully selected both to have more instructions be executed through the IRF and to flatten the distribution of the indices of the IRF.This paper presents two heuristic algorithms, precision-oriented and time-oriented, to find sub-optimal assignments to the IRF. According to the evaluation results, the precision-oriented algorithm obtained the same as or very close to the optimal assignment of an IRF with 48 or less entries. The time-oriented algorithm found a sub-optimal assignment of a 1024-entry IRF in 16 ms, whose precision was 0.5% inferior to the precision-oriented solution at a maximum. The hardware cost of a 1024-entry IRF on an FPGA was modest: two 18 kib block RAM elements and 0.8% increase of the logic elements.