العربية
中国
Français
Deutsch
Ελληνική
हिन्दी
Italiano
日本語
Português
Русский
EspañolSELF-MODIFYING CODE
In computer science, 'self-modifying code' is code that alters its own instructions, whether or not it is on purpose, while it is executing.
Self-modifying code is quite straightforward to write when using assembly language (taking into account the CPU cache). It is also supported by some high level language interpreters such as SNOBOL4, the Lisp programming language, or the ALTER verb in COBOL. It is more difficult to implement on compilers but compilers such as Clipper and Spitbol make a fair attempt at it, and COBOL almost encouraged it. Batch programming scripts often involve self-modifying code as well.
Self-modifying code can be used for various purposes:
#Optimization of a state dependent loop.
#Runtime code generation, or specialization of an algorithm in runtime or loadtime (which is popular, for example, in the domain of real-time graphics).
#Altering of inlined state of an object, or simulating the high-level construction of closures.
#Patching of subroutine address calling, as done usually at load time of dynamic libraries. Whether this is regarded as 'self-modifying code' or not is a case of terminology.
#Evolutionary computing systems such as genetic programming.
#Hiding of code to prevent reverse engineering, as through use of a disassembler or debugger.
#Hiding of code to evade detection by virus/spyware scanning software and the like.
#Filling 100% of memory (in some architectures) with a rolling pattern of repeating opcodes, to erase all programs and data, or to burn-in hardware.
#Compression of 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 achieve certain functionality. For example, a "One Instruction Set Computer" 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 programming language) without using self-modifying code.
#Altering instructions for fault-tolerance
The second and third types are probably the kinds mostly used also in high-level languages, such as LISP.
Pseudocode example:
repeat N 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 N times {
''increase'' A by one
do something with A
}
when STATE has to switch {
replace the opcode "increase" above with the opcode to decrease
}
Note that 2-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 will have to depend of course on the value of 'N' and the frequency of state changing.
Some claim that use of self-modifying code is not recommended when a viable alternative exists, because such code can be difficult to understand and maintain.
Others simply view self-modifying code as something one would be doing while editing code (in the above example, replacing a line, or keyword), only done in run-time.
Self-modifying code was used in the early days of computers in order to save memory space, which was limited. It was also used to implement subroutine calls and returns when the instruction set only provided simple branching or skipping instructions to vary the control flow. This application is still relevant in certain ultra-RISC architectures, at least theoretically; see for example One instruction set computer. Donald Knuth's original MIX architecture also used self-modifying code to implement subroutine calls.
It may be argued that the most advanced artificially intelligent systems of the future must inherently become self-modifying, as is the human brain. Future software is likely to understand its own workings well enough to be able to interact with users in order to provide almost unlimited customizability.
Already, critical systems which are too complex for people to fully manage in real time, such as the Internet and electrical distribution networks routinely rely upon self-modifying behaviors (though not necessarily self-modifying code) in order to function acceptably.
Self-modifying code was used to hide copy protection instructions in 1980s DOS based games. The floppy disk drive access instruction 'int 0x13' would not appear in the executable program's image but it 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. Polymorphic viruses are sometimes called primitive self-mutators. Modifying a piece of running code is also used in certain attacks, such as buffer overflows.
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 function or error function or reward function.
Because of the security implications of self-modifying code, some operating systems go to lengths to rule it out. (The concern is usually not that programs will intentionally modify themselves, but that they could be maliciously changed by an exploit).
An OS feature called W^X (for "write xor execute") 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. Some systems provide a back door 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.
Regardless, at a meta-level, programs can still modify their own behavior by changing data stored elsewhere (see Metaprogramming.)
Just in time compilers for Java, .NET, ActionScript 3.0 and other programming languages often compile short blocks of byte-code or p-code into machine code suitable for the host processor and then immediately execute them.
In some cases self-modifying code executes 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.
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.
This consideration is not unique to processors with code cache, since on any processor rewriting the code never comes for free.
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 have to handle self-modifying code correctly for backwards compatibility reasons but they are far from efficient at doing so.
NASM-syntax self-modifying x86-assembly algorithm that determines the size of the Prefetch Input Queue
code_starts_here:
xor cx, cx ; zero register cx
xor ax, ax ; zero register ax
around:
cmp ax, 1 ; check if ax has been altered
je found_size
mov [nop_field+cx], 0x90 ; 0x90 = opcode "nop" (No OPeration)
inc cx
jmp short flush_queue
flush_queue:
mov [nop_field+cx], 0x40 ; 0x40 = opcode "inc ax" (INCrease ax)
nop_field:
nop times 256
jmp around
found_size:
; register cx now contains the size of the PIQ
What this code essentially does is change the execution flow, and determine by brute force how large the PIQ is. "How far away do I have to change the code in front of me for it to affect me?" If it is too near (it is already in the PIQ) the update will not have any effect. If it is far enough, the change of the code will affect the program and the program has then found the size of the processor's PIQ. If this code is being executed in protected mode, the operating system must not make any context switch, or else this program may return the wrong value.
The Synthesis kernel written by Dr. Henry Massalin as his PhD. thesis is commonly viewed to be the "mother of all self-modifying code." Massalin's tiny Unix kernel 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 (like a JIT interpreter might) to apply a number of optimizations such as constant folding or common subexpression elimination.
The Synthesis kernel was extremely 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 extremely fast 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; drawing a parallel to the "heavy religious atmosphere" which the Italian Futurist movement rebelled against.
★ Reflection (computer science)
★ Self-replication
★ Quine (computing)
★ Using self modifying code under Linux
★ self modifying C code
★ "Synthesis: An Efficient Implementation of Fundamental Operating System Services" -Henry Massalin's PhD thesis on the Synthesis kernel
★ Futurist Programming
★ Certified Self-Modifying Code
★ Jürgen Schmidhuber's publications on self-modifying code for self-referential machine learning systems
Self-modifying code is quite straightforward to write when using assembly language (taking into account the CPU cache). It is also supported by some high level language interpreters such as SNOBOL4, the Lisp programming language, or the ALTER verb in COBOL. It is more difficult to implement on compilers but compilers such as Clipper and Spitbol make a fair attempt at it, and COBOL almost encouraged it. Batch programming scripts often involve self-modifying code as well.
Usage of self-modifying code
Self-modifying code can be used for various purposes:
#Optimization of a state dependent loop.
#Runtime code generation, or specialization of an algorithm in runtime or loadtime (which is popular, for example, in the domain of real-time graphics).
#Altering of inlined state of an object, or simulating the high-level construction of closures.
#Patching of subroutine address calling, as done usually at load time of dynamic libraries. Whether this is regarded as 'self-modifying code' or not is a case of terminology.
#Evolutionary computing systems such as genetic programming.
#Hiding of code to prevent reverse engineering, as through use of a disassembler or debugger.
#Hiding of code to evade detection by virus/spyware scanning software and the like.
#Filling 100% of memory (in some architectures) with a rolling pattern of repeating opcodes, to erase all programs and data, or to burn-in hardware.
#Compression of 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 achieve certain functionality. For example, a "One Instruction Set Computer" 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 programming language) without using self-modifying code.
#Altering instructions for fault-tolerance
The second and third types are probably the kinds mostly used also in high-level languages, such as LISP.
Self-modifying code used to optimize a state-dependent loop
Pseudocode example:
repeat N 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 N times {
''increase'' A by one
do something with A
}
when STATE has to switch {
replace the opcode "increase" above with the opcode to decrease
}
Note that 2-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 will have to depend of course on the value of 'N' and the frequency of state changing.
Attitudes towards self-modifying code
Some claim that use of self-modifying code is not recommended when a viable alternative exists, because such code can be difficult to understand and maintain.
Others simply view self-modifying code as something one would be doing while editing code (in the above example, replacing a line, or keyword), only done in run-time.
Self-modifying code was used in the early days of computers in order to save memory space, which was limited. It was also used to implement subroutine calls and returns when the instruction set only provided simple branching or skipping instructions to vary the control flow. This application is still relevant in certain ultra-RISC architectures, at least theoretically; see for example One instruction set computer. Donald Knuth's original MIX architecture also used self-modifying code to implement subroutine calls.
It may be argued that the most advanced artificially intelligent systems of the future must inherently become self-modifying, as is the human brain. Future software is likely to understand its own workings well enough to be able to interact with users in order to provide almost unlimited customizability.
Already, critical systems which are too complex for people to fully manage in real time, such as the Internet and electrical distribution networks routinely rely upon self-modifying behaviors (though not necessarily self-modifying code) in order to function acceptably.
Self-modifying code used as camouflage
Self-modifying code was used to hide copy protection instructions in 1980s DOS based games. The floppy disk drive access instruction 'int 0x13' would not appear in the executable program's image but it 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. Polymorphic viruses are sometimes called primitive self-mutators. Modifying a piece of running code is also used in certain attacks, such as buffer overflows.
Self-modifying code in 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 function or error function or reward function.
Operating systems and self-modifying code
Because of the security implications of self-modifying code, some operating systems go to lengths to rule it out. (The concern is usually not that programs will intentionally modify themselves, but that they could be maliciously changed by an exploit).
An OS feature called W^X (for "write xor execute") 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. Some systems provide a back door 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.
Regardless, at a meta-level, programs can still modify their own behavior by changing data stored elsewhere (see Metaprogramming.)
Just-in-time compilers
Just in time compilers for Java, .NET, ActionScript 3.0 and other programming languages often compile short blocks of byte-code or p-code into machine code suitable for the host processor and then immediately execute them.
Interaction of cache and self-modifying code
In some cases self-modifying code executes 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.
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.
This consideration is not unique to processors with code cache, since on any processor rewriting the code never comes for free.
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 have to handle self-modifying code correctly for backwards compatibility reasons but they are far from efficient at doing so.
Example
NASM-syntax self-modifying x86-assembly algorithm that determines the size of the Prefetch Input Queue
code_starts_here:
xor cx, cx ; zero register cx
xor ax, ax ; zero register ax
around:
cmp ax, 1 ; check if ax has been altered
je found_size
mov [nop_field+cx], 0x90 ; 0x90 = opcode "nop" (No OPeration)
inc cx
jmp short flush_queue
flush_queue:
mov [nop_field+cx], 0x40 ; 0x40 = opcode "inc ax" (INCrease ax)
nop_field:
nop times 256
jmp around
found_size:
; register cx now contains the size of the PIQ
What this code essentially does is change the execution flow, and determine by brute force how large the PIQ is. "How far away do I have to change the code in front of me for it to affect me?" If it is too near (it is already in the PIQ) the update will not have any effect. If it is far enough, the change of the code will affect the program and the program has then found the size of the processor's PIQ. If this code is being executed in protected mode, the operating system must not make any context switch, or else this program may return the wrong value.
Henry Massalin's Synthesis kernel
The Synthesis kernel written by Dr. Henry Massalin as his PhD. thesis is commonly viewed to be the "mother of all self-modifying code." Massalin's tiny Unix kernel 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 (like a JIT interpreter might) to apply a number of optimizations such as constant folding or common subexpression elimination.
The Synthesis kernel was extremely 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 extremely fast 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; drawing a parallel to the "heavy religious atmosphere" which the Italian Futurist movement rebelled against.
See also
★ Reflection (computer science)
★ Self-replication
★ Quine (computing)
External links
★ Using self modifying code under Linux
★ self modifying C code
★ "Synthesis: An Efficient Implementation of Fundamental Operating System Services" -Henry Massalin's PhD thesis on the Synthesis kernel
★ Futurist Programming
★ Certified Self-Modifying Code
★ Jürgen Schmidhuber's publications on self-modifying code for self-referential machine learning systems
This article provided by Wikipedia. To edit the contents of this article, click here for original source.
psst.. try this: add to faves
