In dit hoofdstuk worden enkele toepassingen van self modifying code behandeld. De meeste toepassingen van self modifying code zijn nog niet wijd verbreid, maar er zijn toch enkele die je tegen kan komen.

Toepassingen van self modifying code zijn vaak te vinden op de iets 'primitievere' systemen. In bijvoorbeeld veel unix-systemen is self modifying code niet te gebruiken door beveiligingen van het besturingssysteem.

Het leeg maken van caches en andere hardware-afhankelijke zaken die komen kijken bij het gebruik van self modifying code worden buiten beschouwing gelaten, tenzij dat expliciet vermeld is.

Behandeld worden enkele technieken die virussen gebruiken om detectie te voorkomen, mogelijkheden van runtime compilers, aan de hand van een voorbeeld worden mogelijkheden van self modifying code en runtime compilers gedemonstreerd, een self modifying code variant van het mutual exclusion probleem wordt gegeven, er worden beschermingen tegen ongewenst copiëren behandeld en er wordt naar een debugger-trap gekeken. Ook wordt een klein deel van het spel Corewars toegelicht, waarin self modifying code erg veel gebruikt wordt.

Een virus is een klein programma dat in staat is zichzelf te vermenigvuldigen. Omdat het doel van een virus vaak destructief is, is er een groot scala aan programma's ontwikkeld met als doel het verwijderen en voorkomen van virus besmettingen. Veel van deze programma's werken door stukken geheugen te vergelijken met bekende patronen van 'virus-code'. Virussen bevatten voor dat virus specifieke code, de 'signature', wat als basis kan dienen voor de herkenning van dat virus.

Als reactie op deze programma's zijn de virussen 'slimmer' geworden om ontdekking te voorkomen. één van de methodes die de makers van virussen gebruiken is encryptie en decryptie tijdens runtime (met behulp van self modifying code). Hierbij wordt het grootste deel van het virus gecodeerd opgeslagen. Een klein deel wordt niet gecodeerd opgeslagen. Dit deel bevat de code om de rest van het virus te decoderen.

De werking zal nu behandeld worden aan de hand van een stukje voorbeeld-code. In figuur 3.1.1 is een deel van de source code van het Leprosy-B virus weergegeven. Het is omgeschreven en vereenvoudigd om het wat leesbaarder te maken.

Het virus begint met de uitvoering van procedure 'run'. Als eerste wordt de rest van het virus gedecodeerd door 'call encrypt_decprypt' aan te roepen. Deze procedure vraagt elke byte van het gecodeerde virus op en vervangt deze door een gedecodeerde versie. Hierna wordt het gedecodeerde virus uitgevoerd, waarna, door nogmaals een aanroep naar 'call encrypt_decrypt', het virus weer gecodeerd wordt.

var encrypt_val=123

proc run                 ; hier begint het programma
   call encode_decode    ; decodeer
virus_code:
   data ...              ; de gecodeerde instructies
   ...
   call encode_decode    ; her-codeer
   return

proc encode_decode
   move virus_code,r1    ; het code-adres
   move virus_len,r3     ; de code-lengte
   do {
      move (r1),r2       ; pak een byte.
      xor encrypt_val,r2 ; decodeer het
      move r2,(r1)       ; schrijf het terug
      increment r1
      decrement r3
   } while r3>0
   return

Door deze methode toe te passen bevinden de gedecodeerde instructies zich alleen tijdens het uitvoeren van deze instructies in het geheugen. Dit verkort de tijd, waarin het virus gedetecteerd kan worden en als er geen context-switches zouden zijn, zou detectie door middel van code-herkenning door een extern programma moeilijker worden.

In het hierboven genoemde voorbeeld wordt gebruik gemaakt van de 'xor' opdracht om te coderen. Het is ook mogelijk om een iets ingewikkeldere coderingsmethode, of zelfs compressie te gebruiken. Er bestaan ook virussen die 'muteren' op het moment dat ze een nieuw bestand infecteren. Deze virussen gebruiken verschillende coderingen door elkaar.

Er zijn ook 'gewone' programma's die decompressie tijdens runtime gebruiken om diskruimte te besparen. De executable die zich op het achtergrondgeheugen bevindt, wordt kleiner, terwijl er een iets langere executietijd (opstarttijd) betaald moet worden.

In plaats van het dynamisch veranderen van instructies kunnen natuurlijk ook tijdens runtime blokken met instructies gemaakt worden, dit wordt 'Runtime Code Generation' (RTCG) genoemd. Met deze techniek is het mogelijk om runtime compilers te maken.

Runtime compilers compileren tijdens runtime delen van het uit te voeren programma. Tijdens runtime is meer informatie beschikbaar over parameters, wat specifiekere optimalisaties toelaat. Deze methode biedt natuurlijk alleen een goed resultaat (wat tijd betreft) als de uit te voeren code relatief lang of vaak geëxecuteerd moet worden.

In figuur 3.2.1 is een idee gegeven hoe een runtime compiler voor een bepaalde functie zou kunnen werken.

proc my_proc               ; de aangeroepen procedure
   move my_proc_source,r0  ; de ongecompileerde instructies
   move allocated_mem,r1   ; geheugen waar de gecompileerde 
                           ; instructies komen te staan
   call dynamic_compiler   ; compileer
   call r1                 ; voor de instructies uit
   return

my_proc_source:
   text 'move a,b'         ; ongecompileerde instructies
   ...                     ; (tekst of halffabrikaat)
   ...

Er wordt een stuk geheugen gereserveerd, de ongecompileerde instructies in de vorm van tekst of een of ander halffabrikaat worden aan de compiler gevoerd, waarna de vers gecompileerde instructies uitgevoerd worden.

Als bijvoorbeeld interactief functies geformuleerd kunnen worden, die over een grote dataset geëvalueerd moeten worden, kan een statische compiler een tussenvorm van de ingevoerde functie genereren en deze interpreteren voor elk van de gegeven invoerwaarden, terwijl de dynamische compiler één keer de functie compileert en daarna per invoerwaarde alleen de gecompileerde functie hoeft uit te voeren.

Ook is het mogelijk om in runtime compilers machineafhankelijke optimalisaties (binnen een familie van processoren) toe te passen. Denk hierbij aan optimalisaties in de volgorde van instructies in een pipeline of mogelijkheden van co-processoren.

Het gebruik van runtime compilers heeft als nadeel dat tijdens runtime tijd besteed moet worden aan de interpretatie van het algoritme. Dit moet dan wel opmeten tegen de tijd die bespaard wordt met de optimalisatie.

Bitblt is een bit transformatie algoritme, dat veelvuldig gebruikt wordt binnen grafische systemen. Het doel van bitblt is om een rechthoek met bits samen te voegen met een doel rechthoek. Bij deze samenvoeging wordt gebruik gemaakt van een logische operator zoals AND, OR, XOR of NOT.

In deze paragraaf zal kort gekeken worden naar enkele implementaties van bitblt. De 'gewone' statische variant, de self modifying code variant en de variant met runtime compiler met optimizer.

Omdat bij het samenvoegen van de twee rechthoeken allerlei verschillende omstandigheden kunnen ontstaan is bitblt een zeer algemeen algoritme. Niet alleen kunnen de rechthoeken van grootte verschillen, ze kunnen ook geheel of gedeeltelijk overlappen. Het samenvoegen kan ook met een grote verscheidenheid aan operatoren gebeuren. Door deze algemeenheid is het een moeilijk algoritme om efficiënt te implementeren.

In figuur 3.3.1 is een vereenvoudigde versie gegeven van het binnenste gedeelte van het algoritme. De vereenvoudigingen liggen onder andere in het feit dat rechthoeken met overlappen en verschillende grootte niet ondersteund worden.

Het algoritme bestaat uit 2 for-lussen. De eerste wordt voor elke horizontale lijn binnen de bron rechthoek een keer uitgevoerd. De tweede leest de bron rechthoek een woord per keer en voegt dit woord samen met een woord uit de doel rechthoek. Omdat de rechthoeken kunnen beginnen bij willekeurige bit grenzen moet binnen deze loop de beide machine woorden op elkaar afgestemd worden.

proc bitblt
   ...
   ...                          ; bepaal bitverschuiving,
   ...                          ; operatie e.d.
   ...
   move src.top,r1;
   while r1<src.onder do {      ; doe lijnen
      ...
      move #0,r4
      move src.links,r0
      while r0<src.rechts do {  ; doe pixels
         ...
         move src,r5            ; nieuwe woord
         shiftleft ls,r4,r6     ; schuif deel naar links
         shiftright ls,r5,r7    ; schuif deel naar rechts
         or r7,r6               ; voeg samen
         move dst,r7            ; haal doelwoord op
         ...
         case op of {           ; kies bewerking
            AND: and r6,r7
            OR:  or r6,r7
            XOR: xor r6,r7
            NOT: not r7
            ...
         } esac
         move r7,dst            ; bewaar doelwoord
         ...
         move r5,r4             ; bewaar oude woord
         increment r0
      } od
      ...
      increment r1
   } od
   ...

Als dit probleem met self modifying code aangepakt wordt, kan bijvoorbeeld het case statement in de lus, vlak voor de lus vervangen worden door één operatie. Als een runtime compiler gebruikt wordt, zouden meer optimalisaties meegenomen kunnen worden. Deze zou ook bijvoorbeeld de shiftoperaties kunnen optimaliseren. Dit alles is natuurlijk ook mogelijk met 'gewone' self modifying code.

Een plaats waar self modifying code gebruikt kan worden om een probleem echt sneller op te lossen is het concurrencyprobleem van mutual exclusion. Een bepaald deel code wordt gelockt door een enkel proces. Zolang een proces bezig is met de executie van een bepaald blok code, kunnen andere processen dit niet doen. Na afloop van executie geeft het proces de code weer vrij voor het volgende proces.

proc locked_proc
x: move 'goto x', x            ; zet semafoor
   ...                         ; voer gelockte
   ...                         ; instructies uit
   move 'move \'goto x\',x',x  ; zet instructie terug
   return

In figuur 3.4.1 is een oplossing gegeven van het beschreven probleem met gebruikmaking van self modifying code. De oplossing berust op de ondeelbaarheid van instructies. De eerste instructie veranderd zijn eigen instructie in een sprong naar zichzelf, wat er voor zorgt dat wanneer andere processen dezelfde code proberen te executeren, deze in een schijnbaar oneindigende lus komen te zitten. Op de puntjes bevinden zich de gelockte instructies. Het proces geeft de code weer vrij door de oorspronkelijke instructie weer terug te schrijven.

Deze oplossing is veel korter, sneller en eenvoudiger dan de statische code variant die vaak gebruikt wordt. De in figuur 3.4.1 beschreven oplossing gebruikt wel processortijd voor wachtende processen. De volgende variant verbetert daar nog wat op.

proc locked_proc
x: move 'call sleep',x             ; anderen slapen
y: move 'goto x',y                 ; anderen wachten
   ...                             ; gelockte
   ...                             ; instrcuties
   move 'move \'goto x\',y',y      ; zet terug
   move 'move \'call sleep\',x',x  ; zet terug
   call wakeup                     ; maak wakker
   return

In plaats van in een lus te komen komt het volgende proces in een slaaptoestand. Mocht het proces uit de slaaptoestand ontwaken voordat het tijd is komt deze alsnog in een lus. Ook zou op deze manier het tweede proces in een wachtrij kunnen komen te staan. Na afloop worden de instructies hersteld en een signaal gestuurd naar het slapende proces.

Door de enorme toename van het illegaal copiëren van programmatuur zijn er methodes ontwikkeld om dit illegaal gebruiken van programmatuur tegen te gaan. Veel programma's maken gebruik van het zogenaamde registratie key systeem.

Hierbij wordt bij het software pakket een code (ook wel key genoemd) geleverd die tijdens het installeren ingetypt moet worden. Bij goed gebruik behoort de key gescheiden van het installatie medium opgeborgen te worden. We gaan er hier van uit dat dit ook zo gebeurd.

Wat overblijft is een programma dat niet (legaal) geïnstalleerd kan worden omdat de code ontbreekt. Om nu toch een werkende key te krijgen moet gekeken worden naar het algoritme die de key verifieert om te kijken of het een geldige key is.

Dit bevindt zich in het te beschermen programma. Door nu een debugger of disassembler te gebruiken, is het bron programma tot op de machine code te onderzoeken. Als het verificatie algoritme gevonden is, is het enige wat nog gedaan moet worden, het vinden van een key die door de verificatie komt.

Als nu gebruik gemaakt wordt van self modifying code dan kunnen we het key verificatie deel van het programma erg ingewikkeld maken of zelfs gecodeerd binnen het bron programma opslaan, zodat het moeilijker wordt om toch een key te genereren. Self modifying code is namelijk moeilijker te lezen, debuggen of disassembleren dan statische code. Dit kan potentiële hackers afschrikken.

Het is ook mogelijk om de key te gebruiken om code te genereren. Zo is de key onderdeel van de verificatie. Dit is veelal niet eenvoudig te achterhalen.

De bovengenoemde methoden zijn niet fool-proof, net zo als alle andere beveiligingsmethoden werpen ze alleen een drempel op. Met genoeg tijd, kennis en geduld zijn ze te omzeilen.

Zoals eerder vermeld is het soms handig om code moeilijk leesbaar te maken. Dit lezen gebeurt vaak met een debugger of een disassembler. Het is mogelijk, om met behulp van self modifying code, te detecteren of een programma onder een debugger uitgevoerd wordt.

proc debugger_found
   move #1,R0
   move 'return',x
x: nop
   move #0,R0
   return

In figuur 3.6.1 is code gegeven dat werkt als een prefech mechanisme in gebruik is. Onder debuggers die de toestand van de cache of pipeline niet herstellen en die single-steppen door de gegeven code, wordt de return opdracht uitgevoerd, niet de nop instructie die in normale gevallen al in de cache of pipeline zit. Deze procedure levert dus de waarde 1 (in register R0) als een debugger actief is.

Inmiddels zijn er debuggers die de cache herstellen. Zodat de bovengenoemde methode in een aantal gevallen onbruikbaar is geworden. Er zijn cehter nog tal van andere soortgelijke mannieren om een debugger te detecteren.

Tot slot een iets minder serieuze toepassing. Corewars is een spel waarbij 2 of meer spelers ieder een programma schrijven, dat moet zien te overleven in het geheugen (core) van een virtuele computer. Deze computer, die MARS (Memory Array Redcode Simulator) heet, heeft een geheugen dat bestaat een uit continu array van woorden. Continu wil zeggen dat het geheugen een loop is, na het laatste geheugenwoord komt het eerste weer. Het geheugen is leeg met uitzondering van de deelnemende programma's. De programmeertaal waarin de programma's (warriors) geschreven worden is een simpele assembler achtige taal die Redcode heet. Redcode heeft slechts 17 instructies.

Het doel van het spel is om alle sub processen van de programma's van de tegenstanders te laten termineren. Een proces termineert als het een DAT instructie uitvoert. DAT instructies worden gebruikt om data op te slaan in het geheugen. Daarom is ook een van de gebruikte technieken binnen warriors het selectief "bomberderen" van de core met DAT instructies. In de hoop een instructie van de tegenstander te overschrijven, die na executeren van deze instructie termineert.

;redcode
;name Dwarf
;author A. K. Dewdney
;strategy Throw DAT bombs around memory,
;strategy hitting every 4th memory cell.
;strategy This program was presented in
;strategy the first Corewar article.
bomb  DAT   #0
dwarf ADD   #4,bomb
      MOV   bomb,@bomb
      JMP   dwarf
      END   dwarf

In figuur 3.7.1 is een eenvoudig voorbeeld van een warrior dat DAT instructies over het geheugen verspreidt. Omdat het effectieve programma maar 3 instructies (en drie geheugenwoorden) groot is, kan het elke vierde instructie wijzigen, zonder zichzelf te beschadigen. De techniek die hier gebruikt is, is niet self modifying code, maar eerder het wijzigen van andermans code.

Self modifying code is binnen Corewars heel normaal. Om een zo'n klein mogelijk doel te zijn voor de tegenstanders moeten de warriors klein zijn, dit is zoals we eerder zagen te doen met self modifying code. Er zijn warriors die alleen maar gebruik maken van self modifying code bijvoorbeeld de imp. Deze warrior bestaat alleen uit één 'MOV 0,1' instructie. Dit commando zet als volgende instructie de huidige instructie neer, waarna deze wordt uitgevoerd.

Andere warriors gebruiken self modifying code om zichzelf te repareren nadat ze "geraakt" zijn. Al met al is self modifying code binnen Corewars een must om een effectieve warrior te schrijven. Doordat de omgeving en de taal betrekkelijk eenvoudig te lezen en te gebruiken zijn is het gebruik van selfmodifying code eenvoudiger te begrijpen.

Uit de wedstrijden om de meest succesvolle warrior te maken komen erg leuke stukken code.