The program is a sequence of instructions in a certain order, and the permutation and combinations of instructions constitute the ever-changing program semantics. Although reordering instructions usually changes the program semantics, it is possible to swap adjacent instruction sequences without changing the program semantics via analyzing the relative independence of adjacent instruction sequences. Instructions swapping increases the distance of instructions and change characteristics of the program, which raises the cost of reverse analysis to a certain extent. Sufficient conditions of instructions swapping are proven by the improvement of the formal definition of the program, upon which the randomize method of instructions reordering based on simulated annealing is proposed in the study. Furthermore, a prototype of IS-VMP (virtual machine protection system based on instructions reordering) is implemented. In addition, the experiments are carried out with a set of encryption algorithms. Experiment results show that instruction reordering is effective and applicable for anti-reversing.