This paper proposes a robust antitamper protection scheme to protect any critical regions of a program from being modified, using possibly a large number of lightweight protection units, called protectors, installed among the program code. A protector would cause an incorrect execution if the code protected by it has been tempered. The protectors are organized in the form of a protection tree. The root node is a critical region, and other nodes are protectors. The protection scheme also supports non-deterministic execution of functions. Modifying any critical region in the protected program has been shown to require an exponential time. Experiment results show that the proposed scheme would not increase noticeably the program execution time. © 2011 IEEE.