Segédlet a Vírusvédelem c. tantárgyhoz

Számítógépes vírusok

A vírusok matematikai modellje

1. A számítógépes vírusok

"A számítógépes vírus intelligencia, erkölcs és értelem nélkül." Intel­ligens, mert létrehozásához mély számítástechnikai ismeret szükséges. Er­kölcstelen, mert alattomosan kihasználja a számítógépek sebezhetôségét. Értelmetlen, mert egy vírus terjedése, pusztítása mindössze öncélú erôfi­togtatás.

A számítógépes vírus valójában egy olyan program (vagy program­részlet), amely képes arra, hogy reprodukálja önmagát vagyis önmagát másolva szaporodjon. Nem minden számítógépes vírus okoz károkat, né­melyikük csak észrevétlenül terjed.

Minden számítógépes rendszerben, bármely operációs rendszer alatt, ahol lehetôség van arra, hogy egy program egy másik programot módosít­son, azaz lehetôség van az adatok és a futtatható kód konvertációjára, létrehozható vírus. A világon talán a legjobban elterjedt DOS operációs rendszer pedig messzemenôleg alkalmas vírusok létrehozására és azok terjedésére. Jelen fejezetben a DOS operációs rendszer alatti vírusokat osztályozzuk, csoportosítjuk [7], [8], [9], [10], [11].

1.1. A vírusok fajtái

Egyetlen olyan feltétel van, amely minden vírus esetében fenn kell, hogy álljon: valamilyen úton-módon el kell indulnia a vírusprogramnak. Ellenkezô esetben ugyanis nem lenne működôképes. A vírusok futóképes­sége két fô módon biztosítható az IBM PC-k DOS operációs rendszerén.

1.1.1. Boot vírusok

Ez a vírusfajta a bootolási folyamatban aktivizálódik, megfertôzve a boot-lemez partíciós tábláját (ha van) vagy a boot szektorát. Elôfordulhat továbbá az is, hogy a vírus a bootolás során beolvasásra kerülô rejtett file-ok betöltésekor aktivizálódik. A boot vírusok tehát módosíthatják:

a merevlemez partíciós táblájának programját,

a boot szektort,

valamelyik rejtett file-t,

valamelyik rejtett file könyvtárbejegyzését,

a DOS FAT-bejegyzéseit.

A boot vírusok létéért valójában nem is a DOS, hanem a BIOS (Basic Input Output System) a felelôs, ugyanis ez a gépekbe beégetett - a kezdeti memória és gép ellenôrzését, valamint a lemezegységek és a fôbb ki-, és bemeneti egységek kezelését végzô - rendszer futtatja ôket. Ezek a vírusok azt használják ki, hogy a BIOS induláskor betölti és el­indítja az operációs rendszert. A hívatlan betolakodó elhiteti a BIOS-sal, hogy ô az operációs rendszer, majd miután a BIOS-tól megkapta a vezérlést gyakorlatilag azt csinál amit akar. Lefutása után általában a vírus betölti az eredeti operációs rendszert, így leplezi jelenlétét. Az eredeti operációs rendszer betöltését a vírus két módon teheti meg:

A felülírt szektorba kerülô víruskód elvégzi az eredeti szektor fel­adatát.

Az eredeti szektort a vírus elmenti, majd aktivizálódása után ezt a szektort tölti be és futtatja. Ebben az esetben az operációs rendszer meggátolhatja a vírus terjedését, hiszen elképzelhetô, hogy egyes operációs rendszerekben az elmentett eredeti szektor megbénítja az operációs rendszer elindulását vagy működését. Más operációs rend­szerek viszont az elmentett eredeti szektortól függetlenül képesek tevékenykedni. Ezt természetesen az elmentett szektor helye hatá­rozza meg.

1.1.2. File indításakor aktivizálódó vírusok

A vírus valamilyen végrehajtható program futtatásakor aktivizálódik. Ekkor a vírus módosíthatja:

magát az eredeti programot,

a program könyvtárbejegyzését,

a DOS FAT-bejegyzéseit.

Ezeket a vírusokat file-vírusoknak is szokás nevezni. Jellemzôjük, hogy a futtatható programokhoz kapcsolódnak oly módon, hogy az eredeti file futtatásakor a program helyett a vírusprogram indul el. Elindulása után általában a vírus gondoskodik róla, hogy a hordozó program is vég­rehajtódjon, így a fertôzésbôl általában semmi sem vehetô észre. Léteznek azonban olyan romboló vírusok is, melyek a fertôzéssel egyidejűleg a hordozó programot tönkreteszik. Ekkor az eredeti program végrehajtá­sára már nincs lehetôség.

A DOS operációs rendszer alatt a .COM file-ok fertôzése lehetséges oly módon, hogy a vírus az eredeti program után másolja magát, majd az eredeti program elsô néhány byte-ját módosítja úgy, hogy a vírusra kerül­jön a vezérlés. A vírus a lefutása során gondoskodik róla, hogy visszaírja az elsô néhány byte-ot, majd a lefutása végén az elsô utasításra adja a vezérlést.

A .COM file-ok fertôzésének egy másik lehetséges módja, hogy a vírus az eredeti program elé kerül. Ezzel már biztosította, hogy a fertôzött program futtatásakor rá adódjon a vezérlés. A vírus lefutása során már csak arról kell gondoskodnia, hogy a memóriában az eredeti program és a vírusprogram helyet cseréljen, a lefutás után pedig az ere­deti program elsô utasítására adja a vezérlést.

A két alapeset átmenete is elôfordulhat. Ekkor a vírus az eredeti program közepébe kerül. Ekkor a vírusnak módosítania kell az eredeti program elsô néhány byte-ját. Ezzel biztosítja, hogy a program futtatása esetén a vezérlés elôször a vírusprogramra kerüljön. Természetesen az eredeti program vírus utáni részét a vírusnak az eredeti helyére kell má­solnia, mielôtt az eredeti programot futtatná.

Az .EXE file-ok esetén a vírus a fertôzendô program bármely ré­szére kerülhet (természetesen beszúrással). Azonban, ha a vírus nem a file végére kerül, a vírusnak módosítania kell az .EXE file header-ében lévô relokációs bejegyzéseket, a relokációról pedig lefutása során gondoskodnia kell. Amennyiben viszont a vírus a file végére kerül, úgy betöltéskor a DOS helyesen végzi el az eredeti program relokálását. A fertôzés során a vírusnak az .EXE header-t kell módosítania úgy, hogy végrehajtáskor elô­ször a vírusra adódjon a vezérlés, amely lefutása után indítja az eredeti programot.

Elôfordulhat az az eset is, hogy a vírus megváltoztatja a fertôzendô program típusát. A .COM file-ból .EXE-t készíthet, a 64 Kbyte-nál kisebb .EXE-kbôl pedig .COM file-t. Amennyiben EXE-bôl készít COM-ot, úgy a vírusnak az e 848b12i redeti program relokációját is el kell végezni.

Sokkal egyszerűbb a DOS alatt a .BAT file-ok fertôzése. A vírus ugyanis a szöveges batch file elejére szúrhat be sorokat, melyeknek a le­futása után automatikusan az eredeti sorokra kerül a vezérlés.

A vírusfertôzés az eredeti program módosulása nélkül is létrejöhet. Egyes operációs rendszerek, mint például a DOS ugyanis az azonos nevű, de különbözô típusú és kiterjesztésű (COM, EXE, BAT) programok fut­tatását prioritási sorrendben végzi. A legnagyobb prioritással a COM, a legkisebbel a BAT bír. Így, egy vírus a fertôzendô program mellett létre­hozhat egy nagyobb prioritású programfile-t (COM vagy EXE), amely csak a vírusprogramot tartalmazza. Így, ha a felhasználó az eredeti prog­ramot úgy szeretné futtatni, hogy az indításnál nem adja meg a futtatandó program kiterjesztését, akkor a DOS azonnal a vírust indítja el. A vírus­nak ezután már csak arról kell gondoskodnia, hogy az alacsonyabb priori­tású eredeti programot futtassa.

Egy program indításakor a felhasználó megadja, hogy milyen prog­ramot szeretne elindítani. Ekkor az operációs rendszer az aktuális, illetve néhány elôre definiált alkönyvtárban megkeresi az futtatandó program ne­vét. Az operációs rendszer a file könyvtárbejegyzésébôl kiolvassa, hogy fi­zikailag hol található a file elsô blokkja a háttértáron. További táblá­zat(ok) írja(k) le, hogy a következô blokkok hol találhatók. Egy vírus az operációs rendszerek file-strúktúrájába többféleképpen avatkozhat be:

Módosíthatja a fertôzendô file könyvtárbejegyzését úgy, hogy az operációs rendszer ne az eredeti file-tartalmat töltse be, hanem a víruskódot.

Természetesen módosíthatja a blokkok sorrendjét leíró táblázatot is.

A DOS operációs rendszerben a háttértár cluster-ekre van osztva. A file-okhoz tartozó könyvtárbejegyzések tartalmazzák a file-ok elsô cluster-ének helyét a háttértáron. A file következô cluster-ének helyét a FAT (File Allocation Table) tartalmazza. Így a DOS esetén a vírus módosít­hatja a file könyvtárbejegyzését (nevét, vagy az elsô cluster mutatóját), il­letve a FAT bejegyzéseket.

A vírusfertôzések egy eddig még (szerencsére) nem elterjedt módja, hogy a vírus az eddigiektôl eltérôen nem közvetlenül a végrehajtható programokba épül be, hanem olyan file-okba, amelyekbôl végrehajtható programok készíthetôk (compiling, linking). A módszer a vírustól jóval bonyolultabb terjedési eljárást követel meg, hiszen ismernie kell a fertô­zendô file felépítését, szintaktikáját. Ezen fertôzés végsô megjelenési for­mája a futtatható file-okban nehezen azonosítható, hiszen a víruskód elhe­lyezkedése függ a fordító (compiler) és a szerkesztô (linker) opcióitól, valamint az egész (eredeti) program felépítésétôl. Az opcióktól függôen a víruskód is más és más lehet. Felmerül a kérdés, hogy hogyan valósítható meg, hogy egy futó vírusprogram a saját forráskódját állítsa elô. Erre nincs is szükség, ugyanis feltehetjük, hogy a fertôzéskor a forráskódú ví­rusprogram két példányban kerül a fertôzendô file-ba. Egyszer program­ként, és egyszer adatként. A fordítás és szerkesztés hatására csak a prog­ramrészbôl képzôdik kód, az adatterület változatlan marad. A fertôzéskor tehát az adatterületen rendelkezésre áll a teljes forráskódú vírusprogram, amit persze két példányban kell a fertôzendô forrás file-ba másolni.

Amennyiben két fordító kompatibilis, úgy egy vírus fertôzheti mind­két fordítóhoz tartozó forrásfile-okat, legyenek azok különbözô operációs rendszerek alatt, vagy különbözô géptípusokon implementálva. Elôfordul­hat továbbá az is, hogy a vírus nem igényli a két fordító teljes kompati­bilitását, csak ennek néhány részét. Például egy tetszôleges operációs rendszer alatti C fordítótól egy vírus a következôket várhatja el:

A program végrehajtása a main() függvénnyel történik.

A forrásfile-ok a .C kiterjesztésű file-ok.

Egy file megnyitására, lezárására, olvasásra, írásra az fopen(), fclose(), fread(), fwrite() parancsok szolgálnak.

Ezek általában mind szabványos követelmények, amelyekkel minden C fordító rendelkezik.

1.2. A vírusok fejlôdése

Az elsô vírus, mint ötlet megjelenése óta a vírusprogramozók egyre újabb és újabb módszereket találták ki arra, hogy hogyan lehet a DOS-t és a folyamatosan fejlôdô vírusvédelemeket kicselezni, minél jobban elbuj­tatni a vírusprogramot. A hagyományos vírusok ellen ugyanis már olyan vírusvédelemi szoftvereket fejlesztettek ki, melyeknél ezek a vírusok még lappangási idejükben lebuktak, nem tudták alkotójuk szándékát megvalósí­tani. Ezért a vírusok szerzôi újabb és újabb vírusterjedési, vírusálcázási technikákat dolgoztak ki. Ezt a fejlôdést (jelenleg) három szakaszra - úgynevezett generációkra - oszthatjuk. A vírusok generációkba osztása teljesen önkényes, az egyes szakaszok sem idôben sem felépítésben nem különülnek el élesen egymástól. A vírusokat sem lehet egyértelműen be­sorolni egy-egy generációba. A felvázolt generációkba sorolás csupán a leglényegesebb vírusterjedési és álcázási elveket és azok fejlôdését tük­rözi.

1.2.1. Elsô generációs vírusok

Az elsô generációs vírusok tulajdonképpen nem tartalmaznak különö­sebb álcázási technikákat, egyszerűen csak fertôznek. Általában az eredeti hordozó programot sem teszik tönkre, az visszaállítható marad. Elôfordul­hat, hogy a vírus rezidensen a memóriába kerül, de az is, hogy a szaporodását a memóriában maradás nélkül biztosítja. Az elôbbi esetben a vírus lényegesen gyorsabban képes terjedni, de könnyebben felfedezhetô. Ezzel szemben az utóbbi esetben a vírus ugyan lassabban terjed, de a fel­fedezése körülményesebb.

1.2.2. Második generációs vírusok

A következô generációba tartozó vírusokat két fô osztályba sorolhat­juk be. Egyik osztályukra az jellemzô, hogy a lappangási idejük alatt ne­hezen felfedezhetôek, mivel ezen vírusok már lopakodó (stealth), illetve polimorf jellegűek. A második generációs vírusok harmadik lényeges osz­tálya a felülíró (overwrite), gyorsan pusztító vírusok. Ezek már a hordozó programot is tönkreteszik, így jelenlétük azonnal felfedezhetô, de ekkor már többnyire a vírus az állományok nagy részét megfertôzte, azaz tönkre is tette.

Lopakodó vírusok: Jellemzôjük, hogy megpróbálnak úgy terjedni, hogy a felhasználó csak nagyon nehezen vehesse észre a vírus jelen­létét. Ennek érdekében például a file végéhez fűzôdô vírusok ese­tén, ha azok már bekerültek a memóriába akkor a file-ok eredeti hosszát mutatják, néha még a file eredeti tartalmát is szimulálják. A lopakodó boot-vírusok pedig az eredeti boot-szektort mutatják meg, elfedve vele jelenlétüket.

Polimorf vírusok: Ezek a vírusok nem úgy próbálnak elbújni, hogy szimulálják a gép fertôzésmentes állapotát, hanem önmagukat titko­sítják, változtatják megnehezítve ezzel felismerésüket.

Felülíró, gyorsan pusztító vírusok: A felülíró vírusok általában azzal okoznak adatveszteséget, hogy a fertôzés elôtti állapotot nem tárol­ják el, hanem egy az egyben felülírják a megfertôzendô programte­rületet. Ebbe a kategóriába tartoznak a legrövidebb vírusok, hiszen nekik nem kell az eredeti állapotot szimulálniuk.

1.2.3. Harmadik generációs vírusok

A vírusok legújabb generációja azt használja ki, hogy a DOS-nak a fentebb említett módokon túl még elég sok kiskapuja van a vírusok szá­mára. Így egy-egy új vírus úgy tud a legkönnyebben megélni, ha olyan módszerrel szaporodik, amit az eddigi vírusvédelmek nem ismernek.

CEB vírusok: A harmadik generációs vírusokra legszemléletesebb példa a CEB (companion) vírusok megjelenése volt. A CEB víru­sok működése azon az elven alapszik, hogy a DOS a futtatható állományokat prioritási sorrendben kezeli. Amennyiben a felhasználó egy program indításánál a kiterjesztést nem adja meg, úgy a DOS a prioritási sorrendben az elsô létezô programot indítja. Ez a priori­tási sorrend a kiterjesztések alapján: .COM, .EXE, .BAT. Így egy CEB vírusnak semmi mást nem kell tennie, mint keresni egy .EXE vagy .BAT kiterjesztésű file-t és ugyanolyan néven, de .COM (vagy .EXE) kiterjesztéssel lemásolnia magát. Ha ezek után az újonnan létrehozott .COM állományt Hidden (rejtett) jelzôvel látja el, akkor az a DIR parancsra nem jelenik meg, vagyis a vírus láthatatlan ! Mivel a vírus terjedése egy egyszerű COPY parancsnak fogható fel, nem keltette fel a vírusvédelmek gyanúját sem.

Device vírusok: A device vírusok talán a legújabb vírusok. A device driver-ek működésébe avatkoznak be, a DOS legalsó szintjén dol­goznak, így a vírusvédelmek többsége alá kerülnek. Mivel az operációs rendszer magjába ágyazzák be magukat szinte tökélete­sen tudnak lopakodni.

ANSI bombák: Ezek a vírusok azt használják ki, hogy a DOS által a képernyôre kiírt szöveg tartalmazhat olyan vezérlô kódokat ame­lyek a billentyűzetet átdefiniálhatják, így egy egyszerű TYPE pa­rancs kiadása után egy billentyűlenyomásra elindulhat egy, akár ví­rusos program is. Ez a módszer csak az ANSI.SYS használatánál lehetséges.

1.3. Védekezés a vírusok ellen

A vírusok elleni védekezési módszereket a vírus létezésének feltétele felôl közelíthetjük meg. Tökéletes megoldás csak úgy születhet, ha az al­kalmazott rendszerekben a futtatható kód és az adatok között semmiféle transzformációt sem engedünk meg. Ez sajnos egy teljesen új operációs rendszert, új rendszerszemléletet kíván meg. A Neumann-elvvel ellentét­ben, a futtatható számítógépes kódot és az adatokat teljesen elkülönítve kellene tárolni. Ez az út a közeljövôben - a jelenlegi operációs rendszerek nagy számú elterjedtsége miatt - még nem lesz járható. A másik lehetô­ség, hogy a DOS-t megtartva az adatok és a futtatható kódok közötti transzformációt megakadályozzuk vagy legalábbis felügyeljük. Sajnálatos módon a DOS felépítése miatt ezt a transzformációt tökéletesen megaka­dályozni lehetetlen.

Ha általánosságban egy vírus fertôzését megakadályozni nem lehet, akkor legalább azt biztosítani kell, hogy az esetleges fertôzés minél elôbb felismerhetô és eltávolítható legyen. Ehhez a rendszer veszélyeztetett terü­leteirôl mintát kell venni, s azt rendszeresen ellenôrizni kell. Fertôzés észlelése esetén a behatolót vírusirtó program segítségével el lehet távolí­tani. A víruskeresô és eltávolító programok általában a legegyszerűbb módszert használják: a vírusokból vett rövid minták, vagy más néven szekvenciák keresését végzik. A szekvenciakeresési módszer azonban nem használható a polimorf vírusok, illetve a vírusok átiratai esetén [13]. Ebben az esetben a szekvenciakeresési módszer mellett statisztikai, illetve heurisztikus algoritmusok használhatók [14], [15], [16].

Léteznek azonban olyan destruktív jellegű vírusok is, amiknek fertôzése után az adathordozókat már nem lehet az eredeti állapotukba visszaállí­tani. Így ez a vírusirtásos módszer nem nyújthat teljes biztonságot.

A vírusfertôzés esélyeit a szoftveres vírusvédelmen túl állandóan be­tartott óvatossági rendszabályokkal is jelentôsen lehet csökkenteni. A rendszerbe kerülô idegen lemezeket alaposan meg kell vizsgálni, for­galmukat nem árt korlátozni. Szoftvertelepítésnél különösen oda kell fi­gyelni a vírusos fertôzés lehetôségeire.

Az esetleges fertôzés hatásainak csökkentése érdekében célszerű leg­alább az újonnan keletkezô adatokat rendszeresen menteni. Rendszeres mentéseknél bármiféle rendszerhiba, vírusfertôzés sem okozhat majd ka­tasztrofális károkat, míg rendszeres mentés nélkül a keletkezô károk na­gyon nagyok is lehetnek.

2. Az automataelmélet alapjai

A következô szakaszokban számítóeszközök néhány alapvetô modell­jét tárgyaljuk ( [3], [4], [5] ), a legfontosabbak közülük: a közvetlen elérésű gép, a köz­vetlen elérésű tárolt programú gép és a Turing-gép. A három gép számí­tási képessége ekvivalens, de sebességük eltérô. Ezt követôen példaként néhány olyan probléma kerül bemutatásra, melyek a bemutatott számítóeszközökkel nem megoldhatók [6].

2.1. Algoritmusok bonyolultsága

Az algoritmusokat többféle szempont alapján értékelhetjük. Leggyak­rabban az érdekel bennünket, milyen ütemben nô a szükséges idô vagy a tárolási hely, ha a problémának egyre nagyobb példányát kell feldolgoz­nunk. A problémához egy egész számot szeretnénk rendelni, mely a probléma méretét jellemzi, és amely a bemenô adatok mennyiségét méri. Egy mát­rixszorzási probléma mérete lehet pl. az összeszorzandó mátrixok dimen­ziói közül a legnagyobb. Egy gráfprobléma mérete pedig lehet az élszám. Ha a szükséges idôt a probléma méretének függvényében fejezzük ki, az így kapott függvényt nevezzük az algoritmus idôbonyolultságának. A bonyolultságnak a méret növekedése melletti aszimptotikus viselkedését pedig az algoritmus aszimptotikus idôbonyolultságának nevezzük. A tárbonyo­lultság és az aszimptotikus tárbonyolultság hasonló módon de­finiálható.

Egy algoritmus bonyolultságára jellemzô két fontos mérôszám tehát a bemenet méretének függvé­nyében megadott idô- és tárbonyolultság. Adott méret mellett tekinthetjük az összes lehetséges adott méretű bemenetekre adódó maximális bonyolultságot, így a legrosszabb eset bonyolultságához jutunk. Ha viszont az átlagos bonyolult­ságot vesszük az összes adott mé­retű bemenetre, a várható bonyolultság­hoz jutunk.

Az algoritmusok bonyolultságának tárgyalásához, meg kell adnunk az algoritmusok végrehajtására alkalmas számítóeszköz-modellt. Sajnos nincs olyan számítási modell, amely minden probléma esetén megfelelne. Az egyik legnagyobb nehézséget a számítógép szavainak a mérete okozza. Ha például feltesszük, hogy a számítógép szavai bármilyen nagy egész szá­mok lehetnek, az egész probléma kódolható lenne egy egész számra, vagyis egyetlen szóba. Ha viszont azt tételezzük fel, hogy a számítógép szava vé­ges, már tetszôlegesen nagy egészek egyszerű tárolása is nehézsé­get, okoz. Így tehát minden egyes problémához egy alkalmas modellt kell választa­nunk, amely pontosan tükrözi a valódi számítógép aktuális számolási ide­jét.

2.2. Közvetlen elérésű gépek

A közvetlen elérésű gép (KEG) hasonlatos egy olyan egyakkumulá­toros számítógépmodellhez, amelyben önmagukat módosító utasítások nin­csenek megengedve.

A KEG, mint az az 2.1. ábrán is látható, a következôkbôl áll: egy csak olvasásra használható bemenô szalag, egy csak kiírásra használható kimenô szalag, a program és a tár (memória).

2.1. ábra: A KEG felépítése

A bemenô szalag rekeszek sorozata, minden négyzetben egy (esetleg negatív) egész szám áll. Amennyiben egy jel a bemenô szalagról beolva­sás­ra kerül, az olvasófej eggyel jobbra lép. A kimenô szalagra csak írni lehet, kezdetben ez üres rekeszekbôl áll. Kiírási utasítás végrehaj­tásakor az éppen az írófej alatt álló rekeszbe a gép egy egész számot nyomtat, majd az írófejet eggyel jobbra mozgatja. A kimenô jel kiírás után már nem módosítható. A tár a rekeszeknek egy r , r , ... , r_i, ... sorozatából áll, melyek egy tetszôleges nagyságú egész számot tartalmazhatnak. Az r re­keszt akkumulátornak nevezzük. A használható rekeszek számára nincs felsô korlát. Ez az általánosítás akkor jogos, ha

a probléma olyan kis méretű, hogy elfér egy számítógép központi tárában, és

a számítás során használt egészek olyan kicsik, hogy elférnek egy gépi szóban.

A KEG programját a tár nem tárolja. Ebbôl persze adódik a felte­vés, hogy a program nem más, mint egy (esetleg címkézett) utasításokból álló sorozat. Mindegyik utasítás két részbôl áll: műveleti kódból és címbôl. A programban használható utasításokat a következô táblázat tartalmazza.

Az a utasításhalmaz elvileg bôvíthetô bármely más, a számítógépek­nél valóságosan elôforduló utasítással (pl. logikai utasításokkal), anélkül, hogy ezzel a problémák nagyságrendjén változtatnánk.

Az operandusok az alábbiak lehetnek:

i magát az i egészet jelöli;

[i] nemnegatív i egész esetén az i rekesz tartalmát jelöli;

[[i]] indirekt címzést jelez, vagyis az operandus a j rekesz tartalma, ahol j az i rekeszben talált egész szám, j < 0 esetén a gép leáll.

A gép indulásakor valamennyi memóriarekesz értéke zérus. Az utasí­tásszámláló a program elsô utasítására van beállítva, a kimenô szalag pe­dig végig üres. A program k-adik utasításának végrehajtása után az utasí­tásszámláló automatikusan a k+1-edik (tehát a következô) utasításra áll, kivéve, ha a k-adik utasítás JUMP, HALT, JGTZ vagy JZERO.

A KEG akkor áll le, ha HALT utasításhoz ér, 0-val kellene oszta­nia, vagy negatív című memóriarekesszel kellene műveletet végeznie vagy nem definiált utasításhoz ér. Nem definiált utasítás például a STORE i, vagy a READ i utasítások.

Általában egy KEG program egy leképezést definiál a bemenô szala­gokról a kimenô szalagokra. Mivel a program esetleg nem minden be­menô szalaggal áll meg, a leképezés nem feltétlenül teljes (bizonyos be­menetekre definiálatlan maradhat). Ezt a leképezést értelmezhetjük függ­vényként és nyelvként is.

Tegyük fel, hogy egy P program mindig n darab egész számot olvas be a bemenô szalagról és legfeljebb egy számot ír ki a kimenô szalagra. Tegyük fel, hogy ha x , x , ..., x_n a bemenô szalag elsô n rekeszében álló egész szám akkor a P program a kimenô szalag elsô négyzetébe y-t ír, majd megáll. Ilyenkor azt mondjuk, hogy a P program az f(x , x , ..., x_n) = y függvényt számítja ki. Megmutatható, hogy a KEG, bármely más értelmes számítógépmodellhez hasonlóan éppen a parciálisan rekurzív függvényeket tudja kiszámítani. Vagyis bármely, adott f parciáli­san rekurzív függvényhez megadható egy KEG program, amely f-et szá­mítja ki, és bármely adott KEG programhoz definiálható egy vele egyen­értékű parciálisan rekurzív függvény.

A másik értelmezési lehetôség szerint a KEG program egy nyelvet fogad el. Jelek egy véges halmazát ábécének, valamely ábécével írt lán­cok egy halmazát pedig nyelvnek nevezzük. Az ábécé jeleit megfeleltethet­jük az 1, 2, ..., k egész számoknak valamely k-ra. A KEG a következôképpen fogad el egy nyelvet: Elhelyezzük az s = a a ...a_n0 lán­cot a bemenô szalagon. Akkor mondjuk, hogy a P KEG program elfogad egy s láncot, ha P az egész s-et, valamint a 0 végjelet elolvassa, a kimenô szalagra egy 1-est ír, majd megáll. A P által elfogadott nyelv az elfoga­dott láncok halmaza. A P által elfogadott nyelvhez nem tartozó láncoknál P nyomtathat 1-tôl különbözô jelet a kiíró szalagra mielôtt megállna, de az is elképzelhetô, hogy sose áll le. Megmutatható, hogy egy KEG prog­ram akkor és csak akkor fogad el egy nyelvet, ha az rekurzívan felsorol­ható. Egy minden bemenetre leálló KEG akkor és csak akkor fogad el egy nyelvet, ha az rekurzív nyelv.

A KEG programok esetén a legrosszabb eset idôbonyolultsága  egy f(n) függvény, amely minden lehetséges n méretű bemenet melletti maxi­muma a végrehajtott utasításokhoz szükséges idôk összegének. A várható idôbonyolultság ugyanezeknek az összegeknek az összes n méretű bemene­tekre számított átlaga. A tárra is definiálhatjuk ezeket a fogalmakat, nem a végrehajtott utasításokhoz szükséges idôk maximumát, illetve átlagát, hanem a hivatkozott rekeszek által elfoglalt tárhelyek maximumát, illetve átlagát tekintjük.

Az idô- és tárbonyolultság pontos meghatározásához tudnunk kell, mennyi idô szükséges az egyes KEG utasítások végrehajtásához, és men­nyi tárhelyet foglalnak el az egyes rekeszek. KEG programok esetében kétfajta költségkritérium számolható. Az uniform költségkritérium sze­rint minden KEG utasítás egységnyi idôt és minden rekesz egységnyi tár­helyet igényel. A logaritmikus költségkritérium esetén azt is figyelembe vesszük, hogy a valódi tár szómérete korlátozott.

Természetesen egy programnak más és más idôbonyolultsága lehet attól függôen, hogy az uniform vagy a logaritmikus költséggel számolunk. Ha a problémában elôadódó összes számról feltehetô, hogy elfér egy gépi szóban, akkor az uniform költségfüggvény megfelelô. Ellenkezô esetben ha reális bonyolultság-vizsgálatot akarunk folytatni, a logaritmikus költség pontosabb.

2.3. Közvetlen elérésű tárolt programú gépek

Mivel a KEG programot nem tárolja a KEG tára, a program nem tudja önmagát módosítani. Most egy másik számítógépmodellt adunk meg, a közvetlen elérésű tárolt programú gépet (KETPG), amely mindenben hasonló a KEG-hez, kivéve, hogy a program a tárban van, s így módosít­hatja önmagát.

A KETPG utasításainak halmaza azonos a KEG utasításainak hal­mazával, csak az indirekt címzés nem megengedett, hiszen nincs rá szük­ség, mivel a KETPG szimulálni tudja azzal, hogy a program végrehajtása során módosítja saját utasításait.

A KETPG szerkezete megegyezik a KEG szerkezetével, csak annyit teszünk fel, hogy a KETPG programja a tár rekeszeiben helyezkedik el. Minden egyes KETPG utasítás két egymás utáni tárrekeszt foglal el. Az elsô rekesz a műveleti kódot, a második rekesz a címet tartalmazza. Min­den egyes utasításhoz tehát egy műveleti kódot rendelünk, melyek egész számok.

A KETPG indulásakor az utasításszámláló valamely meghatározott rekeszre van beállítva. A memóriában a gép indulásakor helyezzük el a programot. Ahhoz azonban ragaszkodunk, hogy véges sok rekesz kivételé­vel minden rekeszben, valamint az akkumulátorban is nulla van. Minden egyes utasítás végrehajtása után az utasításszámláló kettôvel megnövekszik, kivéve a következô utasításoknál: JUMP, JGTZ (ha az akkumulátor pozi­tív) és JZERO (ha az akkumulátorban nulla van), ezekben az esetekben az utasításszámláló i-re változik. Az egyes utasítások hatása azonos a meg­felelô KEG utasítások hatásával.

A KETPG programok bonyolultságát a KEG programokéhoz hason­lóan definiálhatjuk. Használhatjuk mind az uniform költségkritériumot, mind a logaritmikus költségkritériumot. Utóbbi esetben azonban nemcsak az operandus kiértékelését kell felszámolnunk, hanem magának az utasítás elérésének is van költsége. Az elérési költség az utasításszámláló tartalmá­nak, valamint magának az utasításnak az elolvasási költségét jelenti.

Felvetôdik a kérdés, hogy mi a különbség egy KEG program és egy megfelelô KETPG program bonyolultsága között. Ha egy bemenet-kime­net leképezést az egyik modell T(n) idô alatt hajt végre, akkor alkalmas c konstanssal ezt a másik modell cT(n) idô alatt végzi el, akár uniform, akár logaritmikus költséggel számolunk. Hasonlóan a két modellben hasz­nált tár is csak egy konstans szorzó erejéig különbözik e kétfajta költség­kritérium esetén.

A következô két tétel ezt a kapcsolatot mondja ki formálisan. Bizo­nyításuk úgy történik, hogy olyan algoritmusokat adunk meg, amelyek segítségével egy KETPG szimulálni képes egy KEG programot és viszont.

2.1. tétel: Tegyük fel, hogy az utasítások költségei uniformak vagy lo­garitmikusak. Ekkor minden T(n) idôbonyolultságú KEG programhoz van olyan k konstans és van olyan ekvivalens KETPG program, amelynek idôbonyolultsága kT(n).

Bizonyítás: Megmutatjuk, hogyan szimulálható egy P KEG program egy KETPG programmal. A KETPG 1-es rekeszét használjuk a KEG akkumulátor tartalmának idôleges tárolására. P-bôl kiindulva konstruálunk egy P, KETPG programot, ezt a KETPG következô r-1 rekeszében he­lyezzük el. Az r szám a P programtól függ. A KEG i rekeszének tartal­mát i  1 esetén a KETPG r+1 rekesze fogja tárolni. Így a KETPG program minden hivatkozása a KEG program megfelelô hivatkozásánál r-rel lesz nagyobb.

Ha P valamely KEG utasítása nem tartalmaz indirekt címzést, akkor közvetlenül lekódoljuk az azonos KETPG utasításba (a tárhivatkozást megfelelôen megnövelve). Ha viszont tartalmaz indirekt címzést akkor 6 KETPG utasításból álló sorozatot feleltetünk meg neki, ez az utasítássoro­zat az indirekt címzést utasításmódosítás segítségével szimulálja.

Megállapítható, hogy minden egyes KEG utasításhoz legfeljebb 6 KETPG utasítás szükséges, így az uniform költségkritériummal számolva a KETPG program idôbonyolultsága legfeljebb 6T(n). Ez attól függetlenül fennáll, hogyan határoztuk meg a bemenet méretét.

Logaritmikus költséggel számolva ismét megállapítjuk, hogy P mind­egyik utasítását egy KETPG utasítássorozattal szimulálhatjuk, aminek 1 vagy 6 tagja van. Megmutatható, hogy létezik olyan konstans, hogy a szi­muláló utasítások költsége a szimulált utasítás költsége és a konstans szor­zata alatt van.

2.2. tétel: Tegyük fel, hogy az utasítások költségei uniformak vagy lo­garitmikusak. Ekkor minden T(n) idôbonyolultságú KETPG programhoz van olyan k konstans és van olyan ekvivalens KEG program, amelynek idôbonyolultsága legfeljebb kT(n).

Bizonyítás: A KETPG szimulálására olyan KEG programot fogunk elôállítani, amely a KEG tárában tárolt KETPG utasításokat indirekt cím­zés segítségével dekódolja és szimulálja. A KEG bizonyos rekeszeit spe­ciális célokra tartjuk fenn:

az 1-es rekeszt indirekt címzésre,

a 2-es rekeszt a KETPG utasításszámálójaként,

a 3-as rekeszt a KETPG akkumulátorának tárolására fogjuk hasz­nálni.

A KETPG i-edik rekeszét i  1 esetén a KEG i+3-adik rekeszében tároljuk.

Elôször elhelyezzük a véges hosszúságú KETPG programot a KEG tárában, a 4-es rekesztôl kezdve. A 2-es rekeszben - az utasításszámláló­ban - 4 áll, az 1-es és 3-as rekeszekben pedig 0. A KEG program egy szimuláló ciklus: elôször elolvassa a KETPG soron következô utasítását, dekódolja azt, majd elágaztatás következik a lehetséges utasítások egyiké­hez. Ezen 18 halmaz mindegyike egy-egy KETPG utasítástípus végrehajtá­sáról intézkedik. Érvénytelen műveleti kód esetén a KEG a KETPG-hez hasonlóan leáll.

Az 2.1. tételhez hasonlóan itt is véges számú lépésben sikerült min­den KETPG utasítást szimulálni a KEG-en, így az 2.1 tétel bizonyításával megegyezô módon igazolhatjuk a tétel állítását.

Az 2.1 és 2.2 tételekbôl következik, hogy a KEG és a KETPG mo­dellek idôbonyolultság tekintetében konstans faktor erejéig ekvivalensek. Hasonlóan igaz ez, ha a tárbonyolultságot tekintjük. Így ugyanazon algo­ritmus bonyolultsága a két modellen azonos nagyságrendű.

2.4. A Turing-gép

Turing 1936-ban alkotta meg azt matematikai objektumot, a róla el­nevezett automatát vagy gépet, mint olyan szerkezetet, mellyel matemati­kai problémák megoldhatók.

Matematikailag a Turing-gépet egy olyan T = < Q, ,q ,F > hetes írja le, melyben

Q az állapotok véges halmaza,

a bemeneti jelek halmaza,

a szalag szimbólumainak a halmaza,

az író/olvasófej mozgási lehetôségeinek megfelelô halmaz,

a mozgási szabályok halmaza,

q a kezdô állapot,

F az elfogadó állapotok halmaza.

A Turing-gép induláskor a szalagon a bemeneti jelsorozat található, amely természetesen a bemeneti jelek szimbólumaiból áll, így a bemeneti jelek halmaza a halmaznak részhalmaza: . A részhalmaz valódi részhalmaz, hiszen az üres szimbólum eleme a de nem eleme a hal­maznak. A továbbiakban az üres szimbólumot jelölje #.

Az halmaz a mozgás irányát adja meg. Elvben a szalag az au­tomata működése során helyben is maradhat, de ez nem növeli az auto­mata erejét.

A mozgási szabályok egy leképezést reprezentálnak. A mozgás csakis az automata állapottól és az olvasott szimbólumtól függ. A mozgás során megváltozik az automata állapota, az olvasott szimbólum felülíródik, végül az író-olvasófej vagy jobbra vagy balra elmozdul. A leképezés tehát a kö­vetkezôképpen szemléltethetô:

Q     Q

Míg a mozgás meghatározásakor bármely szimbólum, így a # is sze­repelhet, addig felülírásra ez a szimbólum nem használható. A leképezés nem zár ki olyan mozgási szabályokat, ahol az olvasott szimbólum a #. Ebbôl következik, hogy az író/olvasófej elkalandozhat a szalag bemeneti jelsorozattal nem érintett részére is. Mivel a szalag mindkét irányban po­tenciálisan végtelen hosszú, az író/olvasófej tetszôlegesen messze távozhat kiindulási helyzetétôl. Ugyanakkor mindig pontosan lehet tudni, melyek a szalag még érintetlen részei, ugyanis itt, és csakis itt hordoz a szalag # szimbólumot. Természetesen használhatunk felülírásra egy, a # szimbólum szemantikájával azonos szemantikájú szimbólumot. Ilyen értelemben mondhatjuk, hogy egy karaktert a # szimbólummal írtunk felül.

A Turing-gép egy jelsorozatot akkor fogad el, ha a jelsorozattal mint bemenettel elindítva létezik olyan mozgássorozata, hogy a Turing-gép elfo­gadó állapotban megáll. A Turing-gép akkor áll meg, ha egy olyan szitu­ációba kerül, amelyre nézve nincs mozgási szabály.

Mint minden automata a Turing-gép is egy számítási potenciált kép­visel. Felmerül a kérdés, hogy milyen mértékű a Turing-gép számítási ké­pessége. Erre vonatkozóan Church deklarált egy feltételezést, amely Church-tézis néven ismert.

A Church-tézis azt állítja, hogy minden probléma, melynek kiszámítá­sára eljárás szerkeszthetô, Turing-géppel megoldható. Ez nagyon súlyos kijelentés, hiszen ez annyit jelent, hogy a Turing-gép képviseli a matematikai értelemben vett megismerhetôség határát. Az ember tehát azokra, és csakis azokra a kérdésekre képes választ adni, amelyekre a Turing-gép  is képes.

Az alábbi tételek szerint a KEG-en, és így a KETPG-n végzett számítások polinomiálisan összehasonlíthatók a Turing-gépen végzett számí­tásokkal.

2.3. tétel: Tegyük fel, hogy az utasítások költségei uniformak vagy lo­garitmikusak. Ekkor minden T(n) idôbonyolultságú Turing-géphez van olyan ekvivalens KEG program, amelynek idôbonyolultsága legfeljebb T (n).

Bizonyítás: A k szalaggal rendelkezô Turing-gép úgy szimulálható egy KEG-gel, hogy a rekeszek a Turing-gép egyes szalagjainak a celláit tar­talmazzák, oly módon, hogy a j-edik szalag (a szalagokat 0-tól k-1-ig szá­moljuk) i-edik celláját a ki+j+c számú rekesz tárolja, ahol c egy konstans, ezzel a KEG-ben megfelelô nagyságú 'munkaterület' tartható fenn. Ide helyezzük el azt a k rekeszt is, ami a Turing-gép k darab fejének a hely­zetét mutatja. A Turing-gép szalagok celláit a KEG indirekt címzés segít­ségével olvassa el, ehhez a fejek helyzetét jelzô rekeszeket használja fel. Tegyük fel, hogy a Turing-gép idôbonyolultsága T(n)  n. Ekkor a KEG-nek a bemenet leolvasásához és az elsô szalagot ábrázoló rekeszekbe he­lyezéséhez, továbbá a Turing-gép szimulálásához összesen O(T(n)), illetve O(T(n)logT(n)) idôre van szüksége, ha uniform, illetve logaritmikus költ­ségfüggvénnyel számolunk. A KEG-en szükséges idô mindkét esetben fe­lülrôl becsülhetô, tehát a Turing-gépen szükséges idô egy polinomiális függvényével, hiszen ha egy függvény O(T(n)logT(n)), akkor biztosan O(T (n)) is.

A fordított állítás csak akkor igaz, ha a KEG-en logaritmikus költ­séggel számolunk. Uniform költség esetén ugyanis egy n-lépéses KEG program bemenet nélkül is olyan magas számokat tud elôállítani, mint például 2 ⁿ amelyeknek puszta tárolásához és elolvasásához is legalább 2ⁿ cella szükséges Turing-gépen. Uniform költség esetén tehát a KEG-ek és a Turing-gépek között semmifajta polinomiális kapcsolat nincsen. Loga­ritmikus költség esetén viszont fennáll a következô tétel:

2.4. tétel: Legyen L egy tetszôleges nyelv. Tegyük fel, hogy  logarit­mikus költséggel számolva valamely T(n) idôbonyolultságú KEG program elfogadja ezt a nyelvet. Ha ebben a KEG programban nincs szorzás és osztás, akkor L idôbonyolultsága legfeljebb 0(T (n)) egy alkalmas többsza­lagos Turing-gépen.

Bizonyítás: Ábrázoljuk a KEG összes nem 0 tartalmú rekeszét az 2.2. ábrán látható módon. A szalagon ( i_j, c_j ) számpárok sorozata fog állni. Minden j-re c_j az i_j sorszámú rekesz tartalma. Az ij, cj számok bináris alakban vannak felírva, a számok elejérôl a fölösleges 0-kat elhagyjuk. A párokat is és a párok tagjait is külön jelzôkkel választjuk el egymástól. A KEG akkumulátor tartalmát egy második szalag tárolja bináris alakban. Egy harmadik szalagot "munkaszalagnak" használunk, további két szalagot pedig a bemenetre és a kimenetre.

A KEG program egyes lépéseit a Turing-gép állapotainak egy-egy véges halmaza fogja képviselni. Nem vesszük sorra, hogyan lehet a Turing-géppel szimulálni az összes KEG utasítást, csupán két példát muta­tunk, amibôl látható, hogy hogyan szimulálható egy tetszôleges KEG uta­sítás. Két példánk az ADD [20] és a STORE 30 utasítás.

2.2. ábra: A KEG rekeszeinek az ábrázolása

Az ADD [20] utasítás szimulálásához úgy tervezzük meg a Turing-gépet, hogy az a következô lépéseket hajtsa végre:

Megkeresi az elsô szalagon a 20-as KEG rekesz címét, vagyis a ##10100# sorozatot. Ha megtalálja, akkor az utána álló számot, a 20-as rekesz tartalmát rámásolja a harmadik szalagra. Ha nem ta­lálja meg, megáll. Ekkor ugyanis a 20-as rekesz tartalma 0, így az indirekt címzés nem kivitelezhetô.

Megkeresi az elsô szalagon a harmadik szalagon tárolt számú KEG rekesz címét. Ha megtalálja, rámásolja a rekesz tartalmát a harma­dik szalagra. Ha nem találja meg, egy 0-t ír a harmadik szalagra.

Azt a számot, amit a második lépésben a harmadik szalagra írt hozzáadja az akkumulátornak - a második szalagon tárolt - tartal­mához.

A STORE 30 utasítás szimulálásakor a Turing-gép a következôkép­pen működjék:

Megkeresi a 30-as KEG rekesz címét, vagyis a ##11110# sorozatot.

Ha megtalálja, a harmadik szalagra átmásolja mindazt, ami a ##11110# sorozattól jobbra áll, kivéve a közvetlenül utána következô számot (a 30-as rekesz régi tartalmát). Ezután átmásolja az akku­mulátor - második szalagon található - tartalmát közvetlenül a ##11110# sorozat jobb oldalára, majd folytatólagosan visszamásolja a harmadik szalagról az elôbb átmásolt láncot.

Ha a 30-as rekesz címe nem található az elsô szalagon, akkor el­megy a balról elsô üres helyig, kinyomtatja az 11110# sorozatot, utána az akkumulátor tartalmát és végül két # jelet.

A fentiek alapján nyilvánvaló, hogy tervezhetô olyan Turing-gép, ami hűen szimulálja a KEG-et. Meg kell még mutatnunk, hogy egy k loga­ritmikus költségű KEG program a Turing-gépen legfeljebb O(k ) lépést igényel. Az elsô szalagon egy rekesz csak akkor szerepel, ha egy elôzô idôpontban jelenlegi értékét elhelyeztük ebbe a rekeszbe. Így viszont an­nak a költsége, hogy c_j-t elhelyezzük az i_j rekeszbe konstans szorzó ere­jéig megegyezik a ##i_j#c_j## reprezentáció hosszával. Ebbôl vonható le az a következtetés, hogy az elsô szalag nem üres része O(k) hosszúságú.

A STORE kivételével minden utasítás szimulálása olyan nagyság­rendű, mint amilyen hosszú az elsô szalag, azaz O(k), hiszen a domináns költséget a szalagon való keresés adja. Ugyanezért azonban a STORE költsége sem több, mint az elsô szalagon való keresés költsége, plusz a szalag átmásolásának a költsége, melyek mindegyike O(k). A szorzást és osztást kivéve tehát bármelyik KEG utasítás legfeljebb O(k) lépésben szimulálható a Turing-gépen. Mivel logaritmikus költség szerint számolunk, minden KEG utasítás legalább egy idôegységet igényel. A Turing-gép által igényelt összes idô tehát O(k

Ha egy KEG program utasításai között a szorzás vagy osztás is sze­repel, akkor a Turing-gépre olyan szubrutinokat írhatunk, amik ezeket az utasításokat összeadás és kivonás segítségével hajtják végre. Egy ilyen szubrutin logaritmikus költsége nem nagyobb, mint a szimulált utasítás lo­garitmikus költségének a négyzete.

2.5. tétel: A logaritmikus költséggel számolt KEG és KETPG, vala­mint a többszalagos Turing-gép polinomiálisan összehasonlítható modell.

Bizonyítás: A tétel állítása az 2.1., az 2.2., az 2.3., valamint az 2.4. tételek következménye.

Kíséreljük meg a Turing-gépnél nagyobb erejű automata szerkesztését úgy, hogy a gépet nem egy, hanem n szalaggal látjuk el. A szalagoknak egymástól független író/olvasófejük van. Az ilyen gép mozgását a gép ak­tuális állapota és valamennyi szalagról leolvasott szimbólum együttesen ha­tározza meg. A mozgás hatására a gép új állapotba megy át, valamennyi olvasott szimbólumot felülírja, végül mindegyik szalag egymástól függetle­nül vagy jobbra vagy balra lép.

2.6. tétel: Az n szalagos Turing-gép szimulálható az egyszalagos Turing-géppel.

Bizonyítás: Az új gép szalagját válasszuk olyan szélesre, hogy rajta mind az n szalagon tárolt információ egymás alatt elférjen. Ezen túlme­nôen sávonként legyen hely egy-egy markerjel számára is. A szimulált gép író/olvasófejeinek helyzetét a szalagon markerrel jelöljük. Így minden sáv­ban található egy marker. Az egyszalagos gép megkeresi valamennyi mar­kert, kiolvassa az ott található infomációt, és tárolja megfelelôen kibôví­tett, de véges sok információ tárolására alkalmas állapotában. Ha minden információ rendelkezésre áll, akkor kiderül, melyik mozgási szabályt kell szimulálni. Az író/olvasófej megint végiglátogatja az összes marker helyét, a szimulált szabálynak megfelelôen felülírja a szimbólumot, és a markert jobbra vagy balra csúsztatja. Ennek során rögtön ki is olvashatja az új szimbólumot is, így az új állapot beállításával egyidejűen célszerűen össze­gyűjtheti a következô lépés megtételéhez szükséges információt. Az álla­pottérben meglehetôsen sok információt kell ugyan memorizálni, de ezen információk tárolásához mindenképpen elegendô véges sok állapot. Min­den szalagról egy-egy szimbólumot memorizálunk, tudnunk kell, hogy ez a szimbólum a felülírandó, vagy a már kiolvasott szimbólum-e, és minden sávra külön meg kell adni, jobbra vagy balra történik-e az elcsúsztatás, végül tudnunk kell, melyik szalagon helyezkedik el a baloldali illetve a jobboldali szélsô marker.

A lehetséges Turing-gépek specifikációja, vagyis azon jelsorozatok összessége, amelyek egy gép specifikációjának tekinthetôk, egy környezet­független nyelvet alkotnak. Így viszont a Turing-gépek száma megszámlál­hatóan végtelen, és így beszélhetünk az elsô, a második, stb. Turing-gép­rôl. Megtehetjük azt is, hogy egy Turing-gépnek saját leírását adjuk be adatként. Vegyük sorra a Turing-gépeket, és bemenetként kapják meg saját specifikációjukat. Osztályozzuk a Turing-gépeket aszerint, hogy ho­gyan reagálnak erre a bemenetre. Nyilván lesznek olyanok, amelyek elfo­gadják, de olyanok is, amelyek visszautasítják a bemenetet.

Azok a leírások, amelyeket saját gépük elfogad, de azok is, amelyek visszautasításban részesülnek, egy-egy nyelvet alkotnak. Legyen a két nyelv neve L és L . Az L tehát azokat a Turing-gép specifikációkat tartalmazza, amely gépek elfogadják saját leírásukat. Vajon készíthetô-e olyan Turing-gép, amely ezt a nyelvet fogadja el? Erre a kérdésre a vá­lasz pozitív. Egyszerű eszközökkel készíthetünk olyan gépet, amely éppen ezt a nyelvet fogadja el. Mi a helyzet a másik, az L nyelvvel, amely a saját specifikációjukat visszautasító Turing-gépek leírását tartalmazza ? Vajon erre a nyelvre is szerkeszthetô Turing-gép ? Sajnos nem:

2.7. tétel: Nem készíthetô olyan Turing-gép, amely egy Turing-gép specifikációjáról és a bemeneti jelsorozatról eldönti, hogy a megadott Turing-gép az adott jelsorozatra valaha is megáll.

Bizonyítás: Tételezzük fel ugyanis az ellenkezôjét, vagyis azt, hogy lé­tezik egy, az L nyelvet elfogadó Turing-gép. Ez a gép ez esetben egyike a megszámlálható Turing-gépeknek, így ennek is van specifikációja, és en­nek a gépnek is odaadható saját leírása. Kérdés, hogyan reagál ez a gép a saját leírására? Ha elfogadja, az hiba, mert ekkor a leírás nem mondata az L nyelvnek, így a gép nem fogadhatná el. Viszont az is baj, ha nem fogadja el, ugyanis akkor ez egy olyan leírás, amit saját gépe nem foga­dott el, tehát mondata az L nyelvnek, és így el kellene fogadnia. Mind­két esetben ellentmondásra jutottunk, ezek szerint eredeti feltevésünk volt helytelen. Nincsen tehát az L nyelvet elfogadó Turing-gép. 

2.5. Egyszerű eldönthetetlen feladatok

Amióta az emberiség egzakt tudományokkal foglalkozik általánosan elfogadott volt, hogy minden szabatosan megfogalmazható probléma meg­oldható. A lehetséges megoldások halmazába persze beleértjük azt az ese­tet is, amikor bizonyíthatóan nincs megoldás.

Ha valamelyik kérdésre ez idô szerint nem ismerjük a választ, akkor a régi felfogás szerint ez annak tudható be, hogy nem rendelkezünk elég ismerettel. Valóban, sok korábban válasz nélkül maradt kérdésre adta meg a tudomány fejlôdése késôbb a feleletet.

Az algebrában, topológiában és fôleg a matematikai logikában azon­ban sok olyan feladat vetôdött fel, amely késôbb eldönthetetlennek bizo­nyul. A matematikai gépek és nyelvek elméletében már - kis túlzással - ahhoz kell ügyesség, hogy az eldönthetetlen feladatok tömegébôl kihalás­szunk egy eldönthetôt. De mint látni fogjuk a számelmélet és az analízis nevezetes feladatai között is vannak eldönthetetlenek. Ezek közül három problémát mutatunk be.

A dominók téglalap alakú kövek, amelyeknek két végén számok vannak. Lerakáskor az azonos számmal ellátott végeknek kell egymás mellé kerülniük. Egy fokkal nehezebb dominójátékhoz jutunk, ha a köveket négyzet alakúaknak tekintjük és a kônek mind a négy oldalára egy-egy számot írunk. A köveket úgy kell egymás mellé rakni, hogy a szomszédos oldalakon lévô számok azonosak legyenek. Az ilyen lerakást szabályosnak mondjuk. A kövek felsô, alsó, bal és jobb oldala rögzített, forgatni nem szabad ôket. Tegyük fel, hogy kaptunk egy K dominókészletet. A készletben véges sok, adott dominótípus van. Minden kapott típusból végtelen sok darab egyforma kô áll rendelkezésre. Kérdés, hogy le tudjuk-e fedni az egész síkot szabályosan, az adott K készletbôl. Létezik-e olyan algoritmus, amely bármely K készlet esetén eldönti, hogy megoldható-e a lerakási feladat? A válasz negatív: ez eldönthetetlen probléma!

A következô példa a híres matematikus, Hilbert tizedik problémája. Hilbert 1900-ban még azon a véleményen volt, hogy minden matematikai probléma megoldható, ha elég sokáig keresik a megoldást. Felállított 23 olyan problémát, melyek az akkori matematika eszközeivel kezelhetetlen­nek tűntek, és biztos volt benne, hogy többségükkel ebben az évszázad­ban még nem boldogul a tudomány. A problémák közül szám szerint a tizedik a következô volt:

Diofantoszi egyenletnek nevezzük a többváltozós, egész együtthatós algebrai egyenleteket, tehát pl. egy

3xł - x˛yz + 6z + 11 = 0

alakú egyenletet, ha csak az egész megoldások érdekelnek bennün­ket. Speciális diofantoszi egyenletekkel kétezer év óta foglalkoznak, pél­dául az

x˛ + y˛ = z˛

egyenlet megoldásai az ún. pitagoraszi számhármasok. Az

xł + ył = zł

egyenletnek viszont nincs 0-tól különbözô egész megoldása. A speciális egyletek minden esetben speciális megoldási módszereket kö­veteltek, amelyek más egyenleteknél csôdöt mondtak. Hilbert azt a felada­tot tűzte ki, hogy keressünk olyan általános módszert (algoritmust), amely minden egész együtthatós algebrai egyenlet esetén eldönti: van-e annak egész megoldása. Nem gondolt arra, hogy esetleg ilyen módszer nem lé­tezik.

A klasszikus analízis területén is találkozhatunk eldönthetetlen prob­lémával. Tekintsük azt a kérdést, hogy van-e egy egyenletnek valós gyöke. A vizsgált egyenletek F(x) = 0 alakúak, ahol F(x) a racionális számokból, az x változóból és a sin(2x) függvénybôl összeadás és szorzás segítségével felépített kifejezés. Például az

1+40x˛-sin˛(2x) = 0

egyenlet nem oldható meg, az

xł+sin[2(x˛+˝)] = 0

egyenlet pedig igen (x = 0 biztosan megoldás).

Matyijaszevics eredményébôl Richardson és Wang levezették, hogy nincs olyan algoritmus, mellyel bármely ilyen alakú egyenletrôl eldönthetô lenne, hogy megoldható-e. A levezetés úgy történik, hogy minden diofantoszi egyenletnek megfeleltetünk egy P(x) = 0 egyenletet. Ez utóbbi egyenletnek akkor és csak akkor lesz valós gyöke, ha diofantoszi egyen­letnek van egész számokból álló megoldása. Ezért, ha a valós gyök prob­lémája eldönthetô volna, akkor a diofantoszi egyenletek problémáját is el lehetne dönteni. Ez utóbbi pedig eldönthetetlen.

Az a tény, hogy valamely problémaosztályra nem készíthetô algorit­mus, annyit jelent, hogy erre a feladattípusra nem adható meg olyan módszer amely általános, vagyis minden ebbe a kategóriába esô feladatnál alkalmazható. Ez nem zárja ki, hogy egyes konkrét feladatokat valamilyen szellemes ötlet, vagy heurisztika igénybevételével ne lehetne megoldani.

3. A számítógépes vírusok matematikai mo­dellje

A számítógépes vírusok megismeréséhez, tulajdonságaik vizsgálatához olyan matematikai modellre van szükség, mely alkalmas arra, hogy rajta a vírusokat definiáljuk. Az 2. fejezetben tárgyalt automaták, gépek közvet­lenül nem alkalmasak a vírusok vizsgálatára, mivel ezen eszközök csupán egyetlen programot képesek tárolni és végrehajtani. Nincs lehetôség ezen gépek esetén a programok, programterületek közti kapcsolatra (az egyik program módosíthatja a másikat), így nem terjedhet vírus. Ahhoz, hogy a vírusok működését modellezhessük, egy olyan gépmodellre van szükség, amelyen definiálható az operációs rendszer, amely már nem csupán egy, hanem több program kezelésére is alkalmas. Ezután az ismert vagy feltételezett vírusok matematikai modellje megalkotható, és így megvizsgálható, hogy általában is felismerhetôk, vagy csak speciális esetekben.

3.1. Háttértárral kiegészített KETPG

Ahhoz, hogy a programok közti kapcsolatot megteremtsük szükség van egy olyan területre, szalagra, melyen a programok, programállomá­nyok tárolhatók. Ezt a szalagot - nevezzük háttértárnak - valamennyi futó program elérheti, olvashatja, illetve módosíthatja.

3.1. Definíció: Háttértárral rendelkezô, közvetlen elérésű, tárolt prog­ramú gépnek (HRKETPG) egy olyan G = < V,U,T,f,q,M > hatost neve­zünk, melyben

V a bemeneti jelek, a kimeneti jelek és a háttértár szalagon lévô jelek, valamint a memória rekeszeiben elhelyezhetô jelek közös  nem üres halmaza, a szalag abc.

U a műveleti kódok nem üres halmaza, U V ;

T a processzor által elvégezhetô tevékenységek nem üres halmaza;

f kölcsönösen egyértelmű függvény, melyre: f: U T;

q az utasítás számláló kezdeti értéke,

M a tárolóegység kezdeti tartalma.

Feltételezzük, hogy a V szalag abc és az egész számok között köl­csönösen egyértelmű leképezés létesíthetô. (Így a HRKETPG és a KEG bemenô és kimenô szalagja, valamint a memóriája kölcsönösen egymásnak megfeleltethetô szimbólumokat tartalmaz.)

3.1. ábra: A HRKETPG felépítése

A 3.1. ábrán látható, hogy a HRKETPG rendelkezik egy bemenô, egy kimenô és egy háttértár szalaggal melyek mindegyike végtelen hosszú­ságú. A bemenô szalag csak olvasásra, a kimenô szalag csak írásra, míg a háttértár szalag mindkét műveletre használható. A szalagok az olvasó, il­letve író fejeken keresztül érhetôk el. Ezen olvasó/író fejek egy szimbó­lum olvasásával, illetve írásával eggyel jobbra mozdulnak. A háttértár szalag esetén lehetôség van az olvasó/író fej közvetlen mozgatására is. A továbbiakban legyen a szalag abc az egész számok halmaza.

A gép tartalmaz továbbá egy ugyancsak végtelen nagyságú memóriát (tárat) is, mely a szalagoktól eltérôen közvetlenül címezhetô (olvasható, írható). A memória elsô rekesze kitüntetett tulajdonságú, ezt a KEG-hez hasonlóan akkumulátornak nevezzük.

A HRKETPG-ben a szalagok és a memória kezelését a processzor végzi. Tekintsük az  U V  véges halmazt. Az f függvény ezen U hal­maz minden elemének egy-egy T-beli tevékenységet feleltet meg. Az xU műveleti kódhoz tartozó f(x) tevékenységet utasításnak nevezzük. A HRKETPG-ben a processzor az utasításszámláló által meghatározott rekeszben lévô műveleti kódot (utasítást) hajtja végre, majd beállítja az utasításszámláló új értékét. A műveleti kódot a memória egyetlen rekesze tartalmazza. A memóriában ezt követi a műveleti kód paramétere. A HRKETPG utasításait tehát két rekesz tartalmazza: a műveleti kódot és a hozzá tartozó paramétert tartalmazó rekesz. A lehetséges utasítások az alábbiak:

Jelöljük c(i)-vel a memóriabeli i-edik rekesz tartalmát. Ekkor az operandusok az alábbiak lehetnek:

Mivel a tárolt programú modellben a program módosíthatja önmagát, így a [[i]] típusú operandusú utasítások helyettesíthetôk a többi utasítással, valamint néhány művelet is helyettesíthetô más műveletek sorozatával.

Természetesen nem mindegyik művelethez tartozik valamennyi lehet­séges operandus, hiszen például a READ műveletnek csak a [i], illetve [[i]] típusú operandusa lehet.

A HRKETP gép utasításkészletét, valamint az egyes utasításokhoz tartozó műveleti kódot az A. melléklet tartalmazza. A hexadecimális mű­veleti kódot úgy definiáltuk, hogy annak elsô számjegye a műveletre, a második számjegye pedig az operandus típusára legyen jellemzô. A prog­ramok leírására a HRKETPG makro nyelve használható, melynek a le­írása a B. mellékletben található. A további példákban is ezen makro nyelv szintaktikáját használjuk.

Abban az esetben, ha az utasításszámláló olyan rekesz(ek) tartalmát címzi meg, amelyben olyan  x V

található, amelyre x U  (tehát nem műveleti kód, nem tartozik hozzá utasítás), úgy a gép leáll.

A gép bekapcsolásakor az utasításszámláló a kezdeti q értéket veszi fel, a processzor elôször a q értékkel címzett utasítást hajtja végre. Azt, hogy a gép milyen programot, milyen algoritmust hajt végre a memóriá­ban lévô utasítások, tehát a memória kezdeti tartalma (M) határozza meg. A gép akkor áll le, ha kikapcsolják, vagy pedig ha olyan utasításhoz ér, amely nem műveleti kód, illetve, ha 0-val osztana. A KEG-tôl eltérôen tehát nincs olyan utasítás, amely leállítaná a gépet. (A 0-val való osztáson kívül természetesen lehetôség van olyan végtelen ciklus létrehozására, amelyik nem csinál semmit.)

A memória tartalma minden bekapcsoláskor a kezdeti M értéket tar­talmazza, minden kikapcsoláskor pedig törlôdik. A háttértár viszont a ki­kapcsoláskor is megtartja tartalmát. Elôfordulhat, hogy a háttértárat a gépbôl kivesszük és egy másik géphez illesztve használjuk. Ennek nyilván akkor van értelme, ha egy HRKETPG egyszerre több háttértárhoz is kapcsolódhat. A több háttértár szalaggal rendelkezô HRKETPG-t egy újabb utasítás bevezetésével definiálhatjuk: a processzor elvégezhet egy olyan utasítást, amely kijelöli az aktuális háttértár szalagot:

Az utasítás végrehajtását követôen minden háttértár szalagra vonat­kozó művelet az aktuális háttértár szalagon történik. Abban az esetben, ha olyan háttértár szalagra vonatkozó utasítást hajt végre a gép, melyet nem elôz meg SETDRIVE utasítás, úgy a gép leáll. Az ilyen, több hát­tértárral rendelkezô HRKETPG azonban szimulálható az egy háttértárral rendelkezô HRKETPG-vel:

3.1. Tétel: A több háttértárral rendelkezô HRKETP gép egyenértékű az egy háttértárral rendelkezô HRKETP géppel.

Bizonyítás: Elegendô bizonyítani, hogy a több háttértárral rendelkezô HRKETP gép szimulálható az egy háttértárral rendelkezôvel, hiszen a fordított eset triviális.

A szimuláló gép egyetlen szalagjára fésüljük rá az eredeti gép N szalagját az alábbi módon: Legyenek a szimulálandó gép szalagjai 0-tól N-1-ig számozva. Az i-edik szalag j-edik szimbóluma kerüljön az új gép Nj+i-edik pozíciójába. A szimuláló gép memóriájának a felépítését is mó­dosítsuk az alábbiak szerint:

a 0. rekesz tartalma az akkumulátor,

az 1. rekesz tartalmát további célokra fenntartjuk,

a 2. rekesz tartalma az aktuális háttértár szalag író/olvasófejének a helyét tartalmazó rekesz címe ( 3-tól N+2-ig ),

az i. rekesz ( 3  i  N+2 ) tartalma legyen az i-3-adik hát­tértár szalag író/olvasófejének a helyzete,

az i. rekesz ( N+2 < i ) tartalma legyen a szimulálandó gép i-(N+2)-adik rekeszének a tartalma.

A szimulálandó gép utasításait az alábbiak szerint kell módosítani:

Amennyiben a program módosítaná az aktuális háttértár sza­lagot, úgy az új szalag sorszáma az 1. rekeszbe kerül. Ekkor tehát a

SETDRIVE a

utasítás helyet az alábbi utasításokat kell elvégezni:

STORE [1] ; akkumulátor mentése

LOAD a ; operandus

ADD 3 ; címmé alakítása és

STORE [2] ; mentése

LOAD [1] ; akkumulátor visszaállítása

Abban az esetben, ha a program ír/olvas az aktuális háttértár szalagról, úgy elôször az egyetlen háttértár szalagot az aktuá­lis pozícióba mozgatja, majd elvégzi a megfelelô műveletet és módosítja az aktuális háttértár szalag fejének a helyzetét. A megfelelô utasítások írási művelet esetén ( PUT a ) :

STORE [1] ; akkumulátor mentése

SEEK [[2]] ; fej mozgatása

WRITE a ; operandus írása

LOAD [[2]] ; a fej helyzetének az olvasása

ADD N ; módosítás

STORE [[2]] ; visszatöltés

LOAD [1] ; akkumulátor visszaállítása

Ha a program módosítja a háttértár szalag író/olvasó fejének a helyzetét ( SEEK a ), úgy a szimuláló program a változta­tást a megfelelô rekeszben végzi el:

STORE [1] ; akkumulátor mentése

LOAD a ; operandus töltése

MULT N ; az operandus konverziója

ADD [2] ; az egyetlen szalagon lévô

SUB 3 ; helyre

STORE [[2]] ; visszatöltés

LOAD [1] ; akkumulátor visszaállítása

Az utasítások szimulációjánál ügyelni kell azonban arra is, hogy a memóriarekeszekre történô hivatkozásokat is át kell alakítani az új prog­ramnak megfelelôen.

A több háttértárral rendelkezô HRKETPG-t tehát úgy tudtuk szimu­lálni az egyszalagos HRKETPG-vel, hogy néhány utasítást utasítások soroza­tával helyettesítettük. Utasításonként legfeljebb 7 utasításra van szükség. Így az 2.1. tételhez hasonlóan uniform költségkritériummal számolva, ha a szimulált program idôbonyolultsága T(n), úgy a szimuláló program idôbo­nyolultsága legfeljebb 7T(n), ami természetesen a bemenettôl függetlenül teljesül.

Logaritmikus költségkritériumot tekintve bonyolultabb a helyzet. Ek­kor ugyanis a STORE [1] és LOAD [1] utasítások költsége az akkumulátor kezdeti tartalmának a függvénye. Nyilvánvaló azonban, hogy az akkumulátor tartalmát az eredeti programnak is elô kell állítani, mely­nek a logaritmikus költsége hasonlóképpen függvénye az akkumulátor-tarta­lom méretének. Ez azt jelenti, hogy a STORE [1] és a LOAD [1] utasí­tások legrosszabb esetben is csak konstansszorosára növelhetik az eredeti program logaritmikus költségét. A fenti utasításszimulációs programrészle­tek olyan utasításokat tartalmaznak még, amely az eredeti utasítás oparandusával, illetve annak konstansszorosával végeznek műveletet. (Feltételezzük, hogy a szimulálandó gép N szalagszáma konstansnak te­kinthetô.) Így az eredeti program T(n) logaritmikus költsége is csak cT(n)-re nôtt.

Így tehát a HRKETPG számítási képességét nem növelhetjük azáltal, hogy több háttértár szalagot használunk. Ezek után már nem meglepô, hogy a HRKETPG számítási képessége sem nagyobb a KETPG-nél:

3.2. Tétel: Bármely HRKETPG szimulálható KETPG-vel, a szimuláló program költségfüggvényei megegyeznek a szimulált program költségfügg­vényeinek konstansszorosával.

Bizonyítás: A 3.1. tétel bizonyításához hasonlóan fésüljük össze a memória és a háttértár tartalmát egy új memóriába. Ekkor egy háttértár­ral nem rendelkezô, azaz KETPG-t kaptunk. Az összefésülésnél annyi a különbség, hogy nincs szükség az aktuális háttértár sorszámát tartalmazó rekeszre; valamint, hogy csak egyetlen, az író/olvasó fej helyét tartalmazó rekeszre van szükség.

A 3.2. tétel következménye a következô tétel:

3.3. Tétel: A Turing-gép és a HRKETPG számítási képessége meg­egyezik, költségeik polinomiálisan összehasonlíthatók.

Bizonyítás: Mivel a HRKETPG szimulálható KETPG-vel (3.2. tétel) és viszont (triviális), a KETPG pedig szimulálható Turing-géppel és vi­szont (2.5. tétel), ezért a HRKETPG is szimulálható Turing-géppel és vi­szont. A költségkritériumok az 2.5. és a 3.2. tétel állításából adódnak.

A HRKETPG-ben a háttértár tekinthetô úgy, mint egy bemeneti és egy kimeneti szalag együttesen, ugyanis a gép indulásakor feltételezzük, hogy a háttértár már rendelkezik adatokkal és a gép leállásakor (kikapcsolásakor) is megmaradnak benne az adatok. A háttértárral nem rendelkezô gépekben (KETPG, Turing-gép) a háttértár szerepét úgy defi­niálhatjuk, hogy a bemeneti szalag tartalmazza a háttértár tartalmát. Ez például úgy tehetô meg, hogy a páros sorszámú szalagbeli rekeszek a be­meneti szalag rekeszeit, míg a páratlan sorszámúak a háttértár rekeszeit jelentik. A gép indulásakor a KETPG a memóriába, a Turing-gép pedig a munkaszalagra másolja a háttértár tartalmát (összefésülve azzal). A gép leállása elôtt a háttértár tartalmát a kimeneti szalagra fésüli. Ily módon a Turing-gépet is háttértárral rendelkezô gépnek tekinthetjük.

Az értekezéshez mellékelt floppy lemezen lévô programok alkalma­sak a HRKETPG szimulációjára IBM PC, illetve kompatibilis számítógé­pen. A programról részletesebb információkat a B. melléklet tartalmaz.

3.2. Operációs rendszerek

A HRKETPG 3.1. definíciójában szereplô < V,U,T,f,q,M > hatos V,U,T,f tagjait a 3.1. fejezetben definiáltuk. q és M megadásával a gép működését specifikáló programot adhatjuk meg. A gyakorlatban a számí­tógépek több programot, adatállományt tartalmaznak. A HRKETPG-t is több program végrehajtására szeretnénk felhasználni, így szükséges, hogy a q és M által specifikált program a háttértárról olvasson be és futtasson programkódot. A futtatandó programok sorrendjét azonban a felhasználó szeretné befolyásolni (a bemeneti szalagon keresztül), így egy olyan keret­programra van szükség, amely a különálló programokat és adatállományo­kat kezelni, futtatni tudja.

3.2. Definíció: Operációs rendszernek nevezzük az olyan programrend­szert, amely alkalmas arra, hogy különálló programokat, adatállományokat kezeljen.

Az operációs rendszert tartalmazhatja egyrészt a memória M kezdeti értéke, másrészt pedig elhelyezkedhet a háttértáron is. Ez utóbbi esetben a memória kezdeti M értéke egy olyan programot tartalmaz, amely a hát­tértárról betölti és futtatja az operációs rendszert. Ebben az esetben az operációs rendszert betöltô programot nem tekintjük az operációs rendszer részének.

Amennyiben a memória kezdeti M értéke tartalmazza az operációs rendszert, úgy a HRKETPG megadásával definiáltuk az operációs rend­szert is. Így ebben az esetben a HRKETP gépen csak a gép saját operá­ciós rendszere használható. (Természetesen készíthetô olyan program amely egy másik operációs rendszert szimulál.) Az ilyen típusú operációs rendszert gépspecifikus operációs rendszernek nevezzük.

Abban az esetben viszont, ha a háttértár szalagja tartalmazza az ope­rációs rendszert, úgy egy HRKETP géphez több operációs rendszert is megadhatunk. Ehhez csupán a háttértár szalagot kell cserélni. Így ezeket az operációs rendszereket gépfüggetlen operációs rendszernek nevezzük.

Az alábbiakban néhány példát mutatunk az operációs rendszerekre.

3.1. Példa: Elôször egy olyan operációs rendszert definiálunk, amelyet a memória kezdeti M értéke tartalmaz. Az operációs rendszer programja a C mellékletben, valamint a mellékelt floppy lemezen található. A floppy lemezen lévô program a B melléklet leírása alapján IBM PC, illetve kompatibilis számítógépen a mellékelt HRKETPG szimulációs programmal futtatható.

Az operációs rendszer a háttértár szalagon blokkokban programokat tárol az alábbi szervezésben:

Minden egyes blokk felépítése az alábbi:

A típuskód függvényében a blokk négyféle típusú adatot tartalmaz­hat:

Amennyiben a blokk valamely file könyvtárbejegyzése (1-es vagy 2-es típuskód), úgy az adatok mezô elsô rekesze a file hosszát, további reke­szei pedig a file nevét tartalmazzák, rekeszenként egy karakterrel, 0-val lezárva. A következô blokkra mutató mezô a file adatait tartalmazó (0-ás típuskódú) elsô blokk helyét adja meg.

Az operációs rendszer két parancsot ismer: a DIR parancs megjele­níti a háttértár szalagon lévô állományokat, míg a VER parancs kiírja az operációs rendszer nevét és verziószámát. Abban az esetben, ha a fel­használó ezektôl eltérô parancsot ad, úgy az operációs rendszer megvizs­gálja, hogy létezik-e a háttértár szalagon a megadott paranccsal megegyezô nevű futtatható file. Amennyiben létezik, akkor azt a 0x1000-es címtôl kezdôdôen betölti és futtatja. A futtatott program igénybe vehet néhány operációs rendszer szolgáltatást. Ezt úgy érheti el, hogy egy JUMP utasí­tással az operációs rendszer egy rutinjára ugrik. A használható operációs rendszerbeli eljárások hívási címei a memória elején lévô változókban ta­lálhatók. Természetesen ahhoz, hogy az operációs rendszertôl ismét vissza­kerüljön a felhasználói programra a vezérlés az operációs rendszer szolgál­tatásának a hívása elôtt a visszatérési értéket az erre a célra szolgáló memóriarekeszben el kell helyezni.

Ezen példa operációs rendszere tehát a memóriában található, így gépspecifikus operációs rendszer. Az operációs rendszert átalakíthatjuk oly módon, hogy gépfüggetlen operációs rendszert kapjunk:

3.2. Példa: Második példánk operációs rendszere tehát a háttértár szalagon helyezkedik el. Az operációs rendszer programjában csupán egyetlen módosítást kell tenni: az elsô file keresését végzô szolgáltatás (f1st) elôször a háttértár szalag elejére áll:

f1st: load 0

f1st2: store [f1stv1]

seek [f1stv1]

Tegyük fel, hogy HRKETPG memóriája kezdetben egy olyan prog­ramot tartalmaz amely a memória elejére betölti a háttértár szalag elsô 1024 rekeszét, és a 0x0c-edik rekeszben lévô címre adja a vezérlést. (Egy ilyen programlista található a D mellékletben.) Így a háttértár szalagon lévô file-okat tároló blokkok nem a 0-adik, hanem az 1024-edik rekesszen kezdôdnek. Ezért a fenti utasítások az alábbiak szerint módosulnak:

f1st: load 1024

f1st2: store [f1stv1]

seek [f1stv1]

Természetesen a HRKETPG-re számtalan operációs rendszert készít­hetünk. A továbbiakban azonban a 3.2-es példában említett operációs rendszert tekintjük, a további példák is erre vonatkoznak.

3.3. Vírusok a HRKETPG-n

A 3.2. pontban definiáltuk az operációs rendszer fogalmát, mely egy olyan programrendszer, amely programállományok kezelésére, azok futta­tására alkalmas. Így a vírusok definícióját a HRKETPG-n is megadhatjuk:

3.3. Definíció: Számítógépes vírusnak nevezzük az olyan, valamely programterülethez kapcsolódó programrészletet, amely alkalmas arra, hogy önmagát másolva más programterületekhez kapcsolódjon. Amennyiben egy programterülethez vírus kapcsolódik, úgy ezen programterület végrehajtá­sakor a vírusprogram végrehajtódik.

A számítógépes vírus kapcsolódhat a háttértár egy programállomá­nyához:

3.3. Példa: A víruspélda listája az E. mellékletben található. Egy fer­tôzött program indításakor a vírus indul el, majd keres egy programállo­mányt és a programállomány blokkjai elé egy új blokkot illeszt, mely csak a vírusprogramot tartalmazza. Ezt követôen újra betölti az eredeti fertô­zött program maradék részét és futtatja azt.

Nem szükséges azonban, hogy a vírus a háttértár egy programállo­mányához kapcsolódjon. A következô példa vírusa az operációs rendszer betöltôdésekor aktivizálódik.

3.4. Példa: Az F. mellékletben látható a 3.2. példában szerepelt ope­rációs rendszer módosított változata, mely egy vírust tartalmaz. A fertôzött operációs rendszer működése megegyezik a 3.2. példa operációs rendsze­rével. A különbség csupán annyi, hogy amennyiben valamely program az 'elsô könyvtárbejegyzés keresése' szolgáltatást hívja, akkor az operációs rendszer elôtt a vírusra kerül a vezérlés, amely elôször megvizsgálja, hogy fertôzött-e az operációs rendszer. Amennyiben még nem fertôzött, úgy a vírusprogramot az operációs rendszerbe másolja és módosítja, hogy az 'elsô könyvtárbejegyzés keresése' szolgáltatás hívásánál a vezérlés a vírusra kerüljön.

Nyilvánvaló, hogy ez a vírus csak akkor terjed, ha egy gép több hát­tértárszalaggal rendelkezik. Ekkor az összes használt háttértár szalagot megfertôzi. Ezt követôen, ha fertôzött szalagról töltjük az operációs rend­szert, úgy továbbterjed a fertôzés.

3.3.1. A vírusok lehetséges terjedési módjai

Mint azt a 3.3-as és a 3.4-es példában láttuk, egy vírus többféle programterülethez is kapcsolódhat. A különbözô programterületekhez való kapcsolódást terjedési módoknak nevezzük. Egy vírus rendelkezhet akár több különbözô típusú terjedési móddal is.

3.4. Definíció: Gépspecifikusnak nevezzük egy vírus terjedési módját, ha a vírus ezen terjedési módja során felhasználja a gép valamely tulaj­donságát, szolgáltatását. Abban az esetben, ha egy terjedési mód során a vírus nem használja fel a gép szolgáltatását, vagy valamely tulajdonságát, úgy gépfüggetlen terjedési módról beszélünk.

3.5. Definíció: Operációs rendszertôl függônek nevezzük egy vírus ter­jedési módját, ha a vírus ezen terjedési módja során felhasználja az ope­rációs rendszer valamely tulajdonságát, szolgáltatását. Abban az esetben, ha egy terjedési mód során a vírus nem használja fel az operációs rend­szer szolgáltatását, vagy valamely tulajdonságát, úgy operációs rendszertôl független terjedési módról beszélünk.

3.6. Definíció: Gépspecifikus vírusnak nevezzük a csak gépspecifikus terjedési móddal rendelkezô vírust, gépfüggetlen vírusnak pedig a csak gépfüggetlen terjedési móddal rendelkezô vírust.

Hasonlóan definiálhatjuk a vírusok operációs rendszertôl való függô­ségét:

3.7. Definíció: A csak operációs rendszertôl függô terjedési móddal rendelkezô vírus operációs rendszertôl függô vírus, míg a csak operációs rendszertôl független terjedési móddal rendelkezô vírus operációs rendszer­tôl független vírus.

A 3.4. példában szereplô vírus egy olyan vírus, amely a működése során nem veszi igénybe az operációs rendszer szolgáltatásait, hanem csu­pán az adott gép funkcióira épít. Ez a vírus az adott gépen futó vala­mennyi operációs rendszer alatt képes aktivizálódni, illetve terjedni, így ez a vírus egy operációs rendszertôl független, gépspecifikus vírus.

A 3.3. példa vírusa a terjedése során kihasználja az operációs rend­szer tulajdonságait, mivel egyrészt a háttértár szalagon lévô file-szerkezetet módosítja, másrészt pedig igénybe veszi az operációs rendszer szolgáltatá­sait is. A terjedés során a gép tulajdonságait is kihasználja, mivel csak végrehajtható állományokat fertôz, így a vírus csak a gép kódformátumá­ban lehet. Ez a vírus tehát gép- és operációs rendszertôl függô vírus.

Nyilvánvaló, hogy egy valóban gépfüggetlen vírus nem fertôzhet vég­rehajtható állományokat, mivel ezzel kihasználná a gép processzorának az utasításkészletét. Egy számítógépes rendszerben a végrehajtható állomá­nyok valamilyen magasabb szintű nyelven megírt forrásfile-okból képzôd­nek. Abban az esetben, ha egy vírus a terjedése során ezen forrásfile-okat módosítja, akkor a vírus független a víruskódot végrehajtó processzortól is. Természetesen a különbözô gépeken futó operációs rendszerek szolgáltatás elérési pontjainak is egyezniük kell. Ennek az azonossága is biztosított abban az esetben, ha a forrásfile-okat lefordító fordítók egymással kom­patibilisek.

3.8. Definíció:  Közvetlen terjedési módról beszélünk abban az esetben, ha a vírus a terjedési mód során végrehajtható állományhoz kapcsolódik, szemben a közvetett terjedési móddal, melynek során a vírus nem végre­hajtható állományhoz kapcsolódik.

A közvetett terjedési móddal rendelkezô vírusok esetén a fordítótól és a szerkesztôtôl függôen a vírusok megjelenési formája a végrehajtható állományokban más és más lehet. A vírus ilyenkor teljesen beépül a hor­dozó programba.

3.3.2. Polimorf vírusok

Az eddig tárgyalt számítógépes vírusok megjelenési formája minden egyes fertôzésnél megegyezik. Elképzelhetô azonban olyan vírus is, amely fertôzésenként valamilyen úton-módon megváltoztatja formáját:

3.9. Definíció: Polimorf terjedési módnak nevezzük egy vírus terjedési módját, ha létezik két olyan, a terjedési mód során fertôzött állomány, melyben a vírusprogram kódsorozata különbözô.

3.10. Definíció: Polimorf, vagy mutációra képes vírusnak nevezünk egy vírust, ha az rendel­kezik polimorf terjedési móddal.

A polimorf vírusok egy lehetséges megvalósítási módja, hogy a vírus­programot egy véletlen kulccsal lekódoljuk, majd az így titkosított vírust egy visszatitkosító résszel látjuk el.

A polimorf vírusok bonyolultabb változatai a visszatitkosító részt is változtatgatják. Ezt megtehetik egyrészt úgy, hogy néhány elôre elkészített visszatitkosító rutinból választanak véletlenszerűen. Másrészt elérhetô ez oly módon is, hogy a terjedési mód során a vírus véletlenszerűen gene­rálja a rutin utasításait. Ezt például az alábbi módszerekkel érheti el:

változtathatja a visszatitkosító rutin utasításainak a sorrendjét,

kihasználhatja, hogy a processzor egy műveletet több utasítással, több utasítássorozattal is elvégezheti,

a visszatitkosító rutint véletlenszerűen töltelékutasításokkal láthatja el.

3.4. A vírus-felismerési probléma

A számítógépes vírusok megjelenésével együtt felmerül a vírusok fel­ismerésének a problémája:

3.11. Definíció: Vírusfelismerési problémának nevezzük azt az algoritmuselméleti kérdést, mely szerint létezik-e olyan algoritmus, amely egy állományról eldönti, hogy tartalmaz-e terjedôképes vírust vagy sem.

Feltételezzük, hogy az állomány formátumáról minden információ rendelkezésre áll. Ez alatt azt értjük, hogy végrehajtható állomány esetén ismerjük a processzor utasításkészletét, az egyes utasítások működését; forrásfile-ok esetén pedig ismerjük a programnyelv szintaktikáját, a fordító működését.

3.4.1. Az általános vírus-felismerési probléma

A Church-tézist szem elôtt tartva, ha létezik olyan algoritmus, amely választ adna a vírus-felismerési problémára, úgy ezen algoritmus elvégzé­sére készíthetô Turing-gép. Sajnos ilyen Turing-gép még egyszerűsített esetben sem készíthetô:

3.4. Tétel: Nem készíthetô olyan Turing-gép, amely egy HRKETPG végrehajtható állományról eldönti, hogy tartalmaz-e vírust, vagy sem.

Bizonyítás: A 3.3. tétel értelmében minden Turing-géphez készíthetô egy, a Turing-gépet szimuláló KETPG, illetve HRKETPG. (Az, hogy a szimuláció hatására az eljárás költségfüggvénye hogyan módosul a tétel bi­zonyítása szempontjából lényegtelen.) Egy Turing-gépbôl ily módon készít­hetünk egy HRKETPG-beli P programot, amely a kimeneti szalagra egy 1-est ír, ha a szimulált Turing-gép elfogadó állapotban megállt. A 3.3-as példában szereplô vírust módosítsuk úgy, hogy a vírus tartalmazza az em­lített P programot oly módon, hogy elôször a P program hajtódjon végre egy B véletlenszerű, de rögzített bemenetre, majd ezt követôen fusson a vírus. Ez megtehetô oly módon, hogy P-hez hozzáfűzzük a vírust, P min­den 1-est kiíró utasítása után egy JUMP utasítást szúrunk be, mely a ví­rusprogram elsô utasítására ugrik. A vírusprogramot is módosítjuk oly módon, hogy fertôzéskor ne csupán a vírusprogramot, hanem a P prog­ramot, valamint a B rögzített bemenetet is másolja.

A fenti módszerrel minden Turing-géphez készíthetô egy HRKETPG-beli V program, mely akkor vírus, ha valóban terjedôképes. Nyilvánvaló, hogy a V program akkor lesz terjedôképes, ha a P program és így a Turing-gép is megáll a rögzített bemenet esetén.

Indirekt tegyük fel, hogy létezik egy olyan T Turing-gép, amely min­den HRKETPG-beli programot a bemenetrôl elolvasva 1-est ír ki, ha az tartalmaz vírust, 0-át, ha nem. Abban az esetben, ha a T Turing-gép a V programra, mint bemenetre 1-essel válaszol, akkor a P program, illetve a neki megfelelô Turing-gép a B bemenetre biztosan megáll, ha viszont 0-át válaszol, akkor biztosan nem áll meg. Így a T Turing-gép képes eldönteni, hogy egy tetszôleges Turing-gép egy tetszôleges bemenetre megáll-e, vagy sem. Ez viszont az 2.7. tétel értelmében nem lehetséges.

A vírusok felismerése tehát a Church-tézist figyelembe véve nem al­goritmizálható. Célszerű tehát a vírus-felismerési problémát úgy egyszerűsí­teni, hogy az algoritmizálható és így a gyakorlatban is használható legyen.

3.4.2. Vírus-felismerési módszerek

Az általános vírus-felismerési probléma egy lehetséges egyszerűsítése, ha csupán "néhány" ismert vírussal foglalkozunk. Ekkor a vírusfelismerés algoritmizálásához felhasználhatjuk az ismert vírusokat is.

Minden ismert vírusból vegyünk egy kódsorozatot, amely minden egyes fertôzéskor a fertôzött állományban elôfordul. Nevezzük ezt a kód­sorozatot szekvenciának. Az vírusfelismerô algoritmusnak már csak ezeket a szekvenciákat kell keresnie a programterületeken. Az ezen az elven működô algoritmussal kapcsolatban azonban további problémák merülnek fel:

polimorf vírusok esetén nem biztos, hogy lehet találni egy nem vál­tozó szekvenciát;

milyen valószínűséggel kapunk vakriasztást, azaz találunk meg vélet­lenül egy szekvenciát egy állományban;

milyen költségkritériumok mellett valósítható meg a szekvenciakeresô algoritmus.

Nyilvánvaló, hogy a polimorf vírusok felismerésére a módszer nem használható, ezen vírusokra más eljárást kell keresni.

A vakriasztás mértéke attól függ, hogy milyen hosszúak a szekven­ciák, és a programállományokban lévô rekeszek melyik értéket milyen valószínűséggel tartalmazzák. Abban az esetben, ha egy szekvencia hossza N, egy rekeszben n érték szerepelhet egyenlô valószínűséggel és összesen M darab szekvenciánk van és a vizsgált állományok összhossza L >> N, akkor annak a valószínűsége, hogy valamelyik szekvencia elôfordul vala­mely állományban:

.

Ez azt jelenti, hogy például 2000 darab 30 byte-os szekvencia esetén annak a valószínűsége, hogy valamelyik szekvencia elôfordul egy 100 Mbyte-os véletlenszerűen generált egységben: . Sajnos a vakriasztás teljes mértékben nem zárható ki, de a megfelelô hosszúságú szekvenciák véletlenszerű elôfordulásának csekély valószínűsége miatt a szekvenciakeresési módszert biztonságosnak nevezhetjük.

Vizsgáljuk meg, hogy milyen költségkritériummal valósítható meg a szekvenciakeresési algoritmus. Mivel a gyakorlatban használt számítógé­pek a HRKETPG-tôl eltérôen fix rekeszmérettel és memóriával rendel­keznek, így minden utasítás költsége egy konstans érték alatt marad. Ezért célszerű a költségkritérium megállapításánál uniform költséggel számolni. A szekvenciakeresési algoritmus minden vizsgálandó rekesz tar­talmát összehasonlítja a szekvenciák elsô rekeszével. Ehhez darab összehasonlításra van szükség abban az esetben, ha külön-külön végezzük a vizsgálatot. A szekvenciákat azonban az elsô rekeszük tartalma alapján sorba rendezhetjük. A vizsgálatot a sorban a középsô helyen állóval kezdjük, majd haladunk a megfelelô irányba. Ezt a módszert használva átlagosan csak darab összehasonlítást kell végezni, feltéve, ha a szekvenciák elsô rekeszeinek tartalmai különbözôk. Abban az esetben, ha a szekvenciák elsô rekeszeinek a vizsgálatával azonosságot találtunk, meg kell vizsgálni a 2. rekeszek tartalmát. A szükséges további vizsgálatok számának várható értéke , így ennyi újabb vizsgálatra van szük­ség. A k-adik vizsgálat egyezôsége esetén tehát újabb vizsgá­latra van szükség. Mindezek alapján a szükséges vizsgálatok számának várható értéke:

A legrosszabb esetet vizsgálva, az összehasonlítások számára adódik. Mivel az algoritmus idôigénye becsülhetô az összeha­sonlítások számá­val, így a szekvenciakeresô algoritmus polinomidôben megvalósítható.

A polimorf vírusok azonosítására egy szimulációs módszert használha­tunk. A módszer lényege, hogy processzor emulálása (szimulálása) alatt elkezdjük végrehajtani a vizsgált programállományt. A végrehajtott utasítá­sokról statisztikát készítünk, melyet folyamatosan hasonlítjuk az ismert po­limorf vírusok már meglévô statisztikájával. Amennyiben egyezôséget ta­pasztalunk, akkor vírust találtunk. A módszerrel így a visszatitkosítás után vizsgáljuk a gyanús program műveleti kódjait. A szekvenciakereséshez ha­sonlítva itt nem a kódsorozat egy részletének a hasonlítása történik, ha­nem a kódsorozat valamely részletének műveleti kódjaiból készített sta­tisztikát vizsgáljuk. Így egyrészt az utasítások felcserélése esetén is azono­síthatóak a vírusok, viszont a szekvenciakereséshez mérhetô biztonságú ke­resés eléréséhez jóval több műveleti kódból képzett statisztikára van szük­ség.

Az emulátor alapú keresési eljárás viszont nem valósítható meg polinomiális idôkeretek között, mivel létezhet olyan vírus, melynek a visszatitkosító rutinja egy véletlenszámtól függôen exponenciális idô alatt fut le.

Az ismeretlen vírusok keresésének egy lehetséges módszere a polimorf vírusok azonosításakor említett processzoremulátor alapú eljárás. Ekkor azonban nem statisztikát készítünk, hanem jellemzô vírustevékenységeket figyelünk. Ilyen jellemzô vírustevékenység például, ha egy program

módosít egy másik programállományt,

megpróbál más programállományt módosítani,

megpróbálja az operációs rendszert módosítani.