Software obfuscation is one of the most promising approaches to
protect intellectual property rights and secret information of
software in untrusted environments. Unfortunately previous
software obfuscation techniques have common drawbacks such that
they only address tamper resistance against static analysis
or they do not have any theoretical basis, so that it is not
clear how effective they are.

Therefore we propose software obfuscation techniques which have
tamper resistance against dynamic analysis and have some theoretical
basis for the difficulty of conducting analysis on the obfuscated
programs.

Our proposed techniques make execution paths of an
obfuscated program variable each time it is executed,
which significantly obstructs its dynamic analysis.
Furthermore we give a theoretical basis on the difficulty
in conducting analysis of the program.