Self-modifying code

History

The IBM SSEC, demonstrated in January 1948, had the ability to modify its instructions or otherwise treat them exactly like data. However, the capability was rarely used in practice. In the early days of computers, self-modifying code was often used to reduce use of limited memory, or improve performance, or both. It was also sometimes used to implement subroutine calls and returns when the instruction set only provided simple branching or skipping instructions to vary the control flow. This use is still relevant in certain ultra-RISC architectures, at least theoretically; see for example one-instruction set computer. Donald Knuth's MIX architecture also used self-modifying code to implement subroutine calls.

Usage

Self-modifying code can be used for various purposes:

• Semi-automatic optimizing of a state-dependent loop.
• Dynamic in-place code optimization for speed depending on load environment.
• Run-time code generation, or specialization of an algorithm in runtime or loadtime (which is popular, for example, in the domain of real-time graphics) such as a general sort utility – preparing code to perform the key comparison described in a specific invocation.
• Altering of inlined state of an object, or simulating the high-level construction of closures.
• Patching of subroutine (pointer) address calling, usually as performed at load/initialization time of dynamic libraries, or else on each invocation, patching the subroutine's internal references to its parameters so as to use their actual addresses (i.e. indirect self-modification).
• Evolutionary computing systems such as neuroevolution, genetic programming and other evolutionary algorithms.
• Hiding of code to prevent reverse engineering (by use of a disassembler or debugger) or to evade detection by virus/spyware scanning software and the like.
• Filling all memory (in some architectures) with a rolling pattern of repeating opcodes, to erase all programs and data, or to burn-in hardware or perform RAM tests.
• Compressing code to be decompressed and executed at runtime, e.g., when memory or disk space is limited.
• Some very limited instruction sets leave no option but to use self-modifying code to perform certain functions. For example, a one-instruction set computer (OISC) machine that uses only the subtract-and-branch-if-negative "instruction" cannot do an indirect copy (something like the equivalent of *a = **b in the C language) without using self-modifying code.
• Booting. Early microcomputers often used self-modifying code in their bootloaders. Since the bootloader was keyed in via the front panel at every power-on, it did not matter if the bootloader modified itself. However, even today many bootstrap loaders are self-relocating, and a few are even self-modifying.
• Altering instructions for fault-tolerance.

Optimizing a state-dependent loop

Pseudocode example:

repeat <i id="mwAWk">N</i> times { if STATE is 1 increase A by one else decrease A by one do something with A }

Self-modifying code, in this case, would simply be a matter of rewriting the loop like this:

repeat <i id="mwAWw">N</i> times { <i id="mwAW0">increase</i> A by one do something with A when STATE has to switch { replace the opcode "increase" above with the opcode to decrease, or vice versa } }

Note that two-state replacement of the opcode can be easily written as "xor var at address with the value opcodeOf(Inc) xor opcodeOf(dec)".

Choosing this solution must depend on the value of N and the frequency of state changing.

Specialization

Suppose a set of statistics such as average, extrema, location of extrema, standard deviation, etc. are to be calculated for some large data set. In a general situation, there may be an option of associating weights with the data, so each x_i is associated with a w_i, and rather than test for the presence of weights at every index value, there could be two versions of the calculation, one for use with weights and one not, with one test at the start. Now consider a further option, that each value may have associated with it a Boolean to signify whether that value is to be skipped or not. This could be handled by producing four batches of code, one for each permutation and code bloat results. Alternatively, the weight and the skip arrays could be merged into a temporary array (with zero weights for values to be skipped), at the cost of processing and still there is bloat. However, with code modification, to the template for calculating the statistics could be added as appropriate the code for skipping unwanted values, and for applying weights. There would be no repeated testing of the options and the data array would be accessed once, as also would the weight and skip arrays, if involved.

Use as camouflage

Self-modifying code is more complex to analyze than standard code and can therefore be used as a protection against reverse engineering and software cracking. Self-modifying code was used to hide copy-protection instructions in 1980s disk-based programs for systems such as IBM PC compatibles and Apple II. For example, on an IBM PC, the floppy disk drive access instruction int 0x13 would not appear in the executable program's image but would be written into the executable's memory image after the program started executing.

Self-modifying code is also sometimes used by programs that do not want to reveal their presence, such as computer viruses and some shellcodes. Viruses and shellcodes that use self-modifying code mostly do this in combination with polymorphic code. Modifying a piece of running code is also used in certain attacks, such as buffer overflows.

Self-referential machine-learning systems

Traditional machine-learning systems have a fixed, pre-programmed learning algorithm to adjust their parameters. However, since the 1980s Jürgen Schmidhuber has published several self-modifying systems with the ability to change their own learning algorithm. They avoid the danger of catastrophic self-rewrites by making sure that self-modifications will survive only if they are useful according to a user-given fitness, error or reward function.

Operating systems

The Linux kernel notably makes wide use of self-modifying code; it does so to be able to distribute a single binary image for each major architecture (e.g. IA-32, x86-64, 32-bit ARM, ARM64...) while adapting the kernel code in memory during boot depending on the specific CPU model detected, e.g. to be able to take advantage of new CPU instructions or to work around hardware bugs. To a lesser extent, the DR-DOS kernel also optimizes speed-critical sections of itself at loadtime depending on the underlying processor generation.

Regardless, at a meta-level, programs can still modify their own behavior by changing data stored elsewhere (see metaprogramming) or via use of polymorphism.

Massalin's Synthesis kernel

The Synthesis kernel presented in Alexia Massalin's Ph.D. thesis is a tiny Unix kernel that takes a structured, or even object-oriented, approach to self-modifying code, where code is created for individual quajects, like filehandles. Generating code for specific tasks allows the Synthesis kernel to (as a JIT interpreter might) apply a number of optimizations such as constant folding or common subexpression elimination.

The Synthesis kernel was very fast, but was written entirely in assembly. The resulting lack of portability has prevented Massalin's optimization ideas from being adopted by any production kernel. However, the structure of the techniques suggests that they could be captured by a higher-level language, albeit one more complex than existing mid-level languages. Such a language and compiler could allow development of faster operating systems and applications.

Paul Haeberli and Bruce Karsh have objected to the "marginalization" of self-modifying code, and optimization in general, in favor of reduced development costs.

Interaction of cache and self-modifying code

On architectures without coupled data and instruction cache (for example, some SPARC, ARM, and MIPS cores) the cache synchronization must be explicitly performed by the modifying code (flush data cache and invalidate instruction cache for the modified memory area).

In some cases short sections of self-modifying code execute more slowly on modern processors. This is because a modern processor will usually try to keep blocks of code in its cache memory. Each time the program rewrites a part of itself, the rewritten part must be loaded into the cache again, which results in a slight delay, if the modified codelet shares the same cache line with the modifying code, as is the case when the modified memory address is located within a few bytes to the one of the modifying code.

The cache invalidation issue on modern processors usually means that self-modifying code would still be faster only when the modification will occur rarely, such as in the case of a state switching inside an inner loop.

Most modern processors load the machine code before they execute it, which means that if an instruction that is too near the instruction pointer is modified, the processor will not notice, but instead execute the code as it was before it was modified. See prefetch input queue (PIQ). PC processors must handle self-modifying code correctly for backwards compatibility reasons but they are far from efficient at doing so.

Security issues

Because of the security implications of self-modifying code, all of the major operating systems are careful to remove such vulnerabilities as they become known. The concern is typically not that programs will intentionally modify themselves, but that they could be maliciously changed by an exploit.

One mechanism for preventing malicious code modification is an operating system feature called W^X (for "write xor execute"). This mechanism prohibits a program from making any page of memory both writable and executable. Some systems prevent a writable page from ever being changed to be executable, even if write permission is removed. Other systems provide a "backdoor" of sorts, allowing multiple mappings of a page of memory to have different permissions. A relatively portable way to bypass W^X is to create a file with all permissions, then map the file into memory twice. On Linux, one may use an undocumented SysV shared-memory flag to get executable shared memory without needing to create a file.

Advantages

• Fast paths can be established for a program's execution, reducing some otherwise repetitive conditional branches.
• Self-modifying code can improve algorithmic efficiency.

Disadvantages

Self-modifying code is harder to read and maintain because the instructions in the source program listing are not necessarily the instructions that will be executed. Self-modification that consists of substitution of function pointers might not be as cryptic, if it is clear that the names of functions to be called are placeholders for functions to be identified later.

Self-modifying code can be rewritten as code that tests a flag and branches to alternative sequences based on the outcome of the test, but self-modifying code typically runs faster.

Self-modifying code conflicts with authentication of the code and may require exceptions to policies requiring that all code running on a system be signed.

Modified code must be stored separately from its original form, conflicting with memory management solutions that normally discard the code in RAM and reload it from the executable file as needed.

On modern processors with an instruction pipeline, code that modifies itself frequently may run more slowly, if it modifies instructions that the processor has already read from memory into the pipeline. On some such processors, the only way to ensure that the modified instructions are executed correctly is to flush the pipeline and reread many instructions.

Self-modifying code cannot be used at all in some environments, such as the following:

• Application software running under an operating system with strict W^X security cannot execute instructions in pages it is allowed to write to—only the operating system is allowed to both write instructions to memory and later execute those instructions.
• Many Harvard architecture microcontrollers cannot execute instructions in read-write memory, but only instructions in memory that it cannot write to, ROM or non-self-programmable flash memory.
• A multithreaded application may have several threads executing the same section of self-modifying code, possibly resulting in computation errors and application failures.