Method of program obfuscation and processing device for executing obfuscated programs

Abstract

A program is obfuscated by reordering its instructions. Original instruction addresses are mapped to target addresses. A cache efficient obfuscated program is realized by restricting target addresses of a sequence of instructions to a limited set of the disjoint ranges (-) of target addresses, which are at lease half filled with instructions. Mapped address steps () are provided between the target addresses to which successive ones of the original instruction addresses are mapped. The address steps () include first address steps within at least a first one of the mutually disjoint ranges (-). Between said first address steps, second address steps within at least a second one of the mutually disjoint ranges (-). Thus, a deviation from successive addresses for logically successive instructions is realized. In an embodiment the mapping of original instruction addresses to target addresses may be visualized by means of a path () along points in an n-dimensional array, where n is greater than one. Successive original instruction addresses are mapped to successive locations in the path, and locations along respective rows of the array are mapped to respective ones of the mutually disjoint ranges (-). Because an n-dimensional path is used a form of locality is preserved that provides for cache efficiency, whereas the multi-dimensional nature of the path makes it possible to combine this locality with pseudo-random steps.