A method and an apparatus for runtime compilation that generates non-deterministic and unpredictable code to protect against un-trusted code attacks are described. The runtime compilation may be based on heuristic rules without requiring deterministic behavior reduction operations for all the code generated. The heuristic rules may include estimations on, for example, runtime overhead or cost incurred for code protection, amount of code protection required and/or other applicable factors and their relationships.