Information Technology | IT security » Dr. Leitold Ferenc - A számítógépes vírusok matematikai modellje

Segédlet a Vírusvédelem c. tantárgyhoz Számítógépes vírusok A vírusok matematikai modellje Készítette: Dr. Leitold Ferenc Tartalomjegyzék Tartalomjegyzék . 2 1. A számítógépes vírusok 3 1.1 A vírusok fajtái 3 1.11 Boot vírusok 3 1.12 File indításakor aktivizálódó vírusok 4 1.2 A vírusok fejlôdése 7 1.21 Elsô generációs vírusok 7 1.22 Második generációs vírusok 7 1.23 Harmadik generációs vírusok 8 1.3 Védekezés a vírusok ellen 8 2. Az automataelmélet alapjai 10 2.1 Algoritmusok bonyolultsága 10 2.2 Közvetlen elérésű gépek 11 2.3 Közvetlen elérésű tárolt programú gépek 14 2.4 A Turing-gép 16 2.5 Egyszerű eldönthetetlen feladatok 21 3. A számítógépes vírusok matematikai modellje 24 3.1 Háttértárral kiegészített KETPG 24 3.2 Operációs rendszerek 30 3.3 Vírusok a HRKETPG-n 33 3.31 A vírusok lehetséges terjedési módjai 33 3.32 Polimorf vírusok 35 3.4 A vírus-felismerési probléma 35 3.41

Az általános vírus-felismerési probléma 36 3.42 Vírus-felismerési módszerek 36 2 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." Intelligens, mert létrehozásához mély számítástechnikai ismeret szükséges. Erkö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ôfitogtatás. A számítógépes vírus valójában egy olyan program (vagy programré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ítson, 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épessége két fô módon biztosítható az IBM PC-k DOS operációs rendszerén. 1.11 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, 3 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 elindí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 feladatá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 rendszerek viszont az elmentett eredeti szektortól függetlenül képesek tevékenykedni Ezt természetesen az elmentett szektor helye határozza meg. 1.12 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égrehajtó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üljö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 eredeti program elsô utasítására adja a vezérlést. 4 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 eredeti 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 lefutá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 futtatá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étrehozhat egy nagyobb prioritású programfile-t (COM vagy EXE), amely csak a vírusprogramot tartalmazza. Így, ha a felhasználó az eredeti programot ú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írusnak ezután már csak arról kell gondoskodnia, hogy az alacsonyabb prioritású eredeti programot futtassa. Egy program indításakor a felhasználó megadja, hogy milyen programot 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 nevét. Az operációs rendszer a file könyvtárbejegyzésébôl kiolvassa, hogy fizikailag 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: 5 • 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íthatja a file könyvtárbejegyzését (nevét, vagy az elsô cluster mutatóját), illetve 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 fileokba, 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 formája a futtatható file-okban nehezen azonosítható, hiszen a víruskód elhelyezkedé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 programként, és egyszer adatként A fordítás és szerkesztés hatására csak a programré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 mindké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ôfordulhat továbbá az is, hogy a vírus nem igényli a két fordító teljes kompatibilitá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. 6 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 elbujtatni 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 besorolni 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ükrözi. 1.21 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ôfordulhat, 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 felfedezése körülményesebb. 1.22 Második generációs vírusok A következô generációba tartozó vírusokat két fô osztályba sorolhatjuk be. Egyik osztályukra az jellemzô, hogy a lappangási idejük alatt nehezen 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 osztá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 jelenlétét. Ennek érdekében például a file végéhez fűzôdô vírusok eseté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. 7 • 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 titkosí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árolják el, hanem egy az egyben felülírják a megfertôzendô programterületet. Ebbe a kategóriába tartoznak a legrövidebb vírusok, hiszen nekik nem kell az eredeti állapotot szimulálniuk. 1.23 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írusok 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 prioritá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 dolgoznak, í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életesen 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 amelyek a billentyűzetet átdefiniálhatják, így egy egyszerű TYPE

parancs kiadása után egy billentyűlenyomásra elindulhat egy, akár vírusos program is. Ez a módszer csak az ANSISYS 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 alkalmazott rendszerekben a futtatható kód 8 é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étben, 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 megakadá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 betartott óvatossági rendszabályokkal is jelentôsen lehet csökkenteni. A rendszerbe kerülô idegen lemezeket alaposan meg kell vizsgálni, forgalmukat nem árt korlátozni. Szoftvertelepítésnél különösen oda kell figyelni a vírusos fertôzés lehetôségeire. Az esetleges fertôzés hatásainak csökkentése érdekében célszerű legalább az újonnan keletkezô adatokat rendszeresen menteni. Rendszeres mentéseknél bármiféle rendszerhiba, vírusfertôzés sem okozhat majd katasztrofális károkat, míg rendszeres mentés nélkül a keletkezô károk nagyon nagyok is lehetnek. 9 2. Az automataelmélet alapjai A következô szakaszokban számítóeszközök néhány alapvetô modelljét tárgyaljuk ( [3], [4], [5] ), a

legfontosabbak közülük: a közvetlen elérésű gép, a közvetlen 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. Leggyakrabban 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 feldolgoznunk. 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átrixszorzási probléma mérete lehet pl az összeszorzandó mátrixok dimenzió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árbonyolultság és az aszimptotikus tárbonyolultság hasonló módon definiá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 bonyolultságot vesszük az összes adott méretű bemenetre, a várható bonyolultsághoz 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álasztanunk, amely pontosan tükrözi a valódi számítógép aktuális számolási idejét. 10 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 nincsenek 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 beolvasásra 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égrehajtá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 r0, r1, . , ri, sorozatából áll, melyek egy tetszôleges nagyságú egész számot tartalmazhatnak. Az r0 rekeszt 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 feltevé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. 11 Művelet Cím Jelentés LOAD operandus Az operandus akkumulátorba. STORE operandus Az akkumulátor másolása az operandus által meghatározott helyre. ADD operandus Az operandus által meghatározott érték hozzáadása az akkumulátorhoz. SUB operandus Az operandus akkumulátorból. MULT operandus Az akkumulátor szorzása az operandus által meghatározott értékkel. DIV operandus Az akkumulátor osztása az operandus által meghatározott értékkel. READ operandus Olvasás a bemeneti szalagról az operandus által meghatározott helyre. WRITE operandus Az operandus által meghatározott érték írása a kimeneti szalagra. JUMP címke Az utasításszámláló módosítása a címke által meghatározott helyre. JGTZ

címke Az utasításszámláló módosítása a címke által meghatározott helyre, ha az akkumulátor pozitív. JZERO címke Az utasításszámláló módosítása a címke által meghatározott helyre, ha az akkumulátor zérus. HALT - által által meghatározott meghatározott érték érték töltése kivonása az az Leállítja a gép működését Az a utasításhalmaz elvileg bôvíthetô bármely más, a számítógépekné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 pedig 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 osztania, 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. 12 Általában egy KEG program egy leképezést definiál a bemenô szalagokról a kimenô szalagokra. Mivel a program esetleg nem minden bemenô szalaggal áll meg, a leképezés nem feltétlenül teljes (bizonyos bemenetekre definiálatlan maradhat). Ezt a leképezést értelmezhetjük függvé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 x1, x2, , xn 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(x1, x2, , xn) = 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álisan 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áncok egy halmazát pedig nyelvnek nevezzük. Az ábécé jeleit megfeleltethetjü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 = a1a2.an0

láncot 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 elfogadott 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 program akkor és csak akkor fogad el egy nyelvet, ha az rekurzívan felsorolható. 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 maximuma 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ű bemenetekre 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 mennyi 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 szerint minden KEG utasítás egységnyi idôt és minden rekesz egységnyi tárhelyet 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 13 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íthatja önmagát. A KETPG utasításainak halmaza azonos a KEG utasításainak halmazával, csak az indirekt címzés nem megengedett, hiszen nincs rá szüksé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. Minden 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 pozití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 megfelelô KEG utasítások hatásával. A KETPG programok bonyolultságát a KEG programokéhoz hasonló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-kimenet leképezést az egyik modell T(n) idô alatt hajt végre, akkor alkalmas c konstanssal ezt a másik modell c⋅T(n) idô alatt végzi el, akár uniform, akár logaritmikus költséggel számolunk. Hasonlóan a két modellben használt tár is csak egy konstans szorzó erejéig különbözik e kétfajta költségkritérium esetén. 14 A következô két tétel ezt a kapcsolatot mondja ki formálisan. Bizonyí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

logaritmikusak Ekkor minden T(n) idôbonyolultságú KEG programhoz van olyan k konstans és van olyan ekvivalens KETPG program, amelynek idôbonyolultsága k⋅T(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ô r1 rekeszében helyezzük el Az r szám a P programtól függ A KEG i rekeszének tartalmá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ássorozat 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 mindegyik 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 szimuláló utasítások költsége a szimulált utasítás költsége és a konstans szorzata alatt van.  2.2 tétel: Tegyük fel, hogy az utasítások költségei uniformak vagy logaritmikusak Ekkor minden T(n) idôbonyolultságú KETPG programhoz van olyan k konstans és van olyan ekvivalens KEG program, amelynek idôbonyolultsága legfeljebb k⋅T(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ímzés segítségével dekódolja és szimulálja. A KEG bizonyos rekeszeit speciá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 haszná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 15 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 minden 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 22 tételekbôl következik, hogy a KEG és a KETPG modellek idôbonyolultság tekintetében konstans faktor erejéig ekvivalensek. Hasonlóan igaz ez, ha a tárbonyolultságot tekintjük. Így ugyanazon algoritmus 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 elnevezett automatát vagy gépet, mint olyan szerkezetet, mellyel matematikai problémák megoldhatók. Matematikailag a Turing-gépet egy olyan T = < Q,Σ,Γ,{l,r},δ,q0,F > hetes írja le, melyben • Q az állapotok véges halmaza, • Σ a bemeneti jelek halmaza, • Γ a szalag szimbólumainak a halmaza, • {l,r} az író/olvasófej mozgási lehetôségeinek megfelelô halmaz, • δ a mozgási szabályok halmaza, • q0 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 Σ halmaznak. A továbbiakban az üres szimbólumot jelölje # Az {l, r} halmaz a mozgás irányát adja meg. Elvben a szalag az automata működése során helyben is maradhat, de ez nem növeli az automata 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 × { Γ - # } × { l, r } Míg a mozgás meghatározásakor bármely

szimbólum, így a # is szerepelhet, 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 16 irányban potenciá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 elfogadó á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épvisel. 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 logaritmikusak Ekkor minden T(n)

idôbonyolultságú Turing-géphez van olyan ekvivalens KEG program, amelynek idôbonyolultsága legfeljebb T2(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 tartalmazzá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 helyzetét mutatja. A Turing-gép szalagok celláit a KEG indirekt címzés segítsé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 helyezé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öltségfüggvénnyel számolunk. A KEGen szükséges idô mindkét esetben felü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(T2(n)) is.  17 A fordított állítás csak akkor igaz, ha a KEG-en logaritmikus költséggel számolunk. Uniform költség esetén ugyanis egy n-lépéses KEG program bemenet nélkül is olyan magas n számokat tud elôállítani, mint például 22 amelyeknek puszta tárolásához és elolvasásához is legalább 2n 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. Logaritmikus 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 logaritmikus 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(T2(n)) egy alkalmas többszalagos 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 ( ij, cj ) számpárok sorozata fog állni Minden j-re cj az ij 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 mutatunk, amibôl látható, hogy hogyan szimulálható

egy tetszôleges KEG utasí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: 1. 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 találja meg, megáll Ekkor ugyanis a 20-as rekesz tartalma 0, így az indirekt címzés nem kivitelezhetô. 2. 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 harmadik szalagra. Ha nem találja meg, egy 0-t ír a harmadik szalagra. 18 3. 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 - tartalmához. A STORE 30 utasítás szimulálásakor a Turing-gép a

következôképpen működjék: 1. Megkeresi a 30-as KEG rekesz címét, vagyis a ##11110# sorozatot 2. 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 akkumulá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. 3. Ha a 30-as rekesz címe nem található az elsô szalagon, akkor elmegy 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 logaritmikus költségű KEG program a Turinggépen legfeljebb O(k2) 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 annak a költsége, hogy cj-t elhelyezzük az ij rekeszbe konstans szorzó erejéig megegyezik a ##ij#cj## 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ágrendű, 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(k2)  Ha egy KEG program utasításai

között a szorzás vagy osztás is szerepel, akkor a Turinggé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 logaritmikus költségének a négyzete. 2.5 tétel: A logaritmikus költséggel számolt KEG és KETPG, valamint a többszalagos Turing-gép polinomiálisan összehasonlítható modell. Bizonyítás: A tétel állítása az 2.1, az 22, az 23, valamint az 24 tételek következménye.  19 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 aktuális állapota és valamennyi szalagról leolvasott szimbólum együttesen hatá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üggetlenü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úlmenô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ávban található egy marker Az egyszalagos gép megkeresi valamennyi markert, 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 összegyűjtheti a következô lépés megtételéhez szükséges információt. Az állapotté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. Minden 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örnyezetfüggetlen nyelvet alkotnak. Így viszont a Turing-gépek száma megszámlálhatóan végtelen, és így beszélhetünk az elsô, a második, stb.

Turing-géprô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 hogyan reagálnak erre a bemenetre. Nyilván lesznek olyanok, amelyek elfogadjá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 L01 és L02 Az L01 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 L02 nyelvvel, amely a saját specifikációjukat visszautasító Turinggépek leírását tartalmazza ? Vajon erre

a nyelvre is szerkeszthetô Turing-gép ? Sajnos nem: 20 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 L02 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 ennek 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 L02 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 fogadott el, tehát mondata az L02 nyelvnek, és így el kellene fogadnia. Mindkét esetben ellentmondásra jutottunk, ezek szerint eredeti feltevésünk volt helytelen. Nincsen tehát az L02

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 megoldható. A lehetséges megoldások halmazába persze beleértjük azt az esetet 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 azonban sok olyan feladat vetôdött fel, amely késôbb eldönthetetlennek bizonyul. 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ásszunk 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! 21 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 kezelhetetlennek tűntek, és biztos volt benne, hogy többségükkel ebben az évszázadban 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ünket. Speciális diofantoszi egyenletekkel kétezer év óta foglalkoznak, példá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 feladatot 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 problé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(2πx) 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˛(2πx) = 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 egyenletnek van egész számokból álló megoldása Ezért, ha a valós gyök problémája eldönthetô 22 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ô algoritmus, 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. 23 3. A számítógépes vírusok matematikai modellje 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özvetlenü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 programú gépnek (HRKETPG) egy olyan G = < V,U,T,f,q,M > hatost nevezü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ölcsö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.) 24 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ó, illetve í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 halmaz minden elemének egy-egy T-beli tevékenységet feleltet meg. Az x∈U 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: Művelet Cím Jelentés LOAD operandus Az operandus akkumulátorba. által STORE operandus Az akkumulátor másolása az operandus által meghatározott helyre. ADD operandus Az operandus által meghatározott érték

hozzáadása az akkumulátorhoz. SUB operandus Az operandus akkumulátorból. MULT operandus Az akkumulátor szorzása az operandus által meghatározott értékkel. DIV operandus Az akkumulátor osztása az operandus által meghatározott értékkel. AND operandus Az akkumulátor bitenkénti ÉS művelete az operandus által meghatározott értékkel. által meghatározott meghatározott érték érték töltése kivonása az az 25 OR operandus Az akkumulátor bitenkénti VAGY művelete az operandus által meghatározott értékkel. XOR operandus Az akkumulátor bitenkénti KIZÁRÓ VAGY művelete az operandus által meghatározott értékkel. READ operandus Olvasás a bemeneti szalagról az operandus által meghatározott helyre. WRITE operandus Az operandus által meghatározott érték írása a kimeneti szalagra. JUMP címke Az utasításszámláló módosítása a címke által meghatározott helyre. JGTZ címke Az utasításszámláló

módosítása a címke által meghatározott helyre, ha az akkumulátor pozitív. JZERO címke Az utasításszámláló módosítása a címke által meghatározott helyre, ha az akkumulátor zérus. GET operandus Olvasás a háttértár szalagról az operandus által meghatározott helyre. PUT operandus Az operandus által meghatározott érték írása a kimeneti szalagra. SEEK operandus A háttértár szalag író/olvasó fejének a mozgatása az operandus által megjelölt helyre. Jelöljük c(i)-vel a memóriabeli i-edik rekesz tartalmát. Ekkor az operandusok az alábbiak lehetnek: Operandus i [i] [[i]] Jelentés i c(i) c(c(i)) 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 lehetsé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 programok 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 26 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 tartalmazza, minden kikapcsoláskor pedig törlôdik. A háttértár viszont a kikapcsolá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: Művelet SETDRIVE Cím Jelentés operandus Az aktuális háttértárszalag az operandusban meghatározott sorszámú háttértár szalag lesz. Az utasítás végrehajtását követôen minden háttértár szalagra vonatkozó 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átté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 ), 27 az i. rekesz ( 3 ≤ i ≤ N+2 ) tartalma legyen az i-3-adik hátté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 szalagot, ú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 LOAD ADD STORE LOAD • ; akkumulátor mentése ; operandus ; címmé alakítása és ; mentése ; 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 SEEK WRITE LOAD ADD STORE LOAD • [1] a 3 [2] [1] [1] [[2]] a [[2]] N [[2]] [1] ; akkumulátor mentése ; fej mozgatása ; operandus írása ; a fej helyzetének az olvasása ; módosítás ; visszatöltés ; 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áltoztatást a megfelelô rekeszben végzi el: STORE LOAD MULT ADD SUB STORE LOAD [1] a N [2] 3 [[2]] [1] ;

akkumulátor mentése ; operandus töltése ; az operandus konverziója ; az egyetlen szalagon lévô ; helyre ; visszatöltés ; 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 programnak megfelelôen. 28 A több háttértárral rendelkezô HRKETPG-t tehát úgy tudtuk szimulálni az egyszalagos HRKETPG-vel, hogy néhány utasítást utasítások sorozatával helyettesítettük. Utasításonként legfeljebb 7 utasításra van szükség. Így az 21 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ôbonyolultsága legfeljebb 7T(n), ami természetesen a bemenettôl függetlenül teljesül. Logaritmikus költségkritériumot tekintve bonyolultabb a helyzet. Ekkor 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, melynek a logaritmikus költsége hasonlóképpen függvénye az akkumulátor-tartalom 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észletek 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 tekinthetô.) Í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üggvé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árral 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 megegyezik, 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 viszont (2.5 tétel), ezért a HRKETPG is szimulálható Turing-géppel és viszont. A költségkritériumok az 25

és a 32 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 29 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 definiá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 bemeneti 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 Turinggé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 alkalmasak 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 31 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 keretprogramra van szükség, amely a különálló programokat és adatállományokat kezelni, futtatni tudja. 3.2 Definíció: Operációs rendszernek nevezzük az olyan

programrendszert, 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átté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 rendszert 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

operá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. 30 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: 1. blokk rekeszeinek a száma 1. blokk 2. blokk rekeszeinek a száma 2. blokk . . . N. blokk rekeszeinek a száma N. blokk Minden egyes blokk felépítése az alábbi: Típuskód Következô

blokk helye Adatok A típuskód függvényében a blokk négyféle típusú adatot tartalmazhat: Típuskód Jelentés 0 A blokk egy file adatait tartalmazza. A következô blokk helye a további, a file-hoz tartozó adatok blokkjának címét tartalmazza. Ha ez az utolsó blokk, akkor az értéke -1 1 A blokk egy file könyvtárbejegyzését tartalmazza, mely file adatfile, nem futtatható. 2 A blokk egy file könyvtárbejegyzését tartalmazza, mely file futtatható, nem adatfile. 31 0x100 * A blokk a háttértár szalag utolsó (N-edik) blokkja. 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 rekeszei 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 megjelení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 felhasználó ezektôl eltérô parancsot ad, úgy az operációs rendszer megvizsgá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 találhatók. Természetesen ahhoz, hogy az operációs rendszertôl ismét visszakerüljön a felhasználói programra a vezérlés az operációs rendszer szolgáltatá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: f1st2: load store seek 0 [f1stv1] [f1stv1] Tegyük fel, hogy HRKETPG memóriája kezdetben egy olyan programot 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: f1st2: load store seek 1024 [f1stv1] [f1stv1] Természetesen a HRKETPG-re számtalan operációs rendszert készíthetü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. * A továbbiakban 0x elôtaggal jelöljük a hexadecimális számokat. 32 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 futtatá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 fertôzött program indításakor a vírus indul el, majd keres egy programállomá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állomá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 32 példában szerepelt operá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 rendszeré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átté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 rendszert, úgy továbbterjed a fertôzés. 3.31 A vírusok lehetséges terjedési módjai Mint azt a 3.3-as és a 34-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 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 a gép szolgáltatását, vagy valamely tulajdonságát, úgy gépfüggetlen terjedési módról beszélünk. 33 3.5 Definíció: Operációs rendszertôl függônek nevezzük egy vírus terjedési módját, ha a vírus ezen terjedési módja során felhasználja az operá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 rendszer 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 rendszertô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 csupán az adott gép funkcióira épít. Ez a vírus az adott gépen futó valamennyi 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 rendszer 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égrehajtható á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ôdnek. 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 kompatibilisek. 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égrehajtható á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 hordozó programba. 34 3.32 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 útonmó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 rendelkezik polimorf

terjedési móddal. A polimorf vírusok egy lehetséges megvalósítási módja, hogy a vírusprogramot 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 generá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, utasítássorozattal is elvégezheti, • a visszatitkosító rutint véletlenszerűen töltelékutasításokkal láthatja el. több 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 felismeré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. 35 3.41 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 Turinggé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 bizonyítása szempontjából lényegtelen.) Egy Turing-gépbôl ily módon készíthetü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 33-as példában szereplô vírust módosítsuk úgy, hogy a vírus tartalmazza az emlí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 minden 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 programot, 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 minden 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 27 tétel értelmében nem lehetséges. 

A vírusok felismerése tehát a Church-tézist figyelembe véve nem algoritmizá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.42 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. 36 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ódsorozatot 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áltozó szekvenciát; • milyen

valószínűséggel kapunk vakriasztást, azaz találunk meg véletlenü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 szekvenciá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 valamely állományban: p ≈ L⋅ M ⋅ 1 nN . 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 −61 generált egységben: p ≈ 1, 19 ⋅ 10 . 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 rendelkeznek, í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 tartalmát összehasonlítja a szekvenciák elsô rekeszével. Ehhez L ⋅ M 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 L ⋅ log M * 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 * x jelenti az x-nél nem kisebb, legkisebb egész számot. 37 találtunk, meg kell vizsgálni a 2. rekeszek tartalmát A szükséges további vizsgálatok 1 , így ennyi újabb vizsgálatra van szükség. A k-adik n 1 vizsgálat egyezôsége esetén tehát újabb L ⋅ M ⋅ k vizsgálatra van szükség. Mindezek n számának várható értéke L ⋅ M ⋅ alapján a szükséges vizsgálatok számának várható értéke: 1 −1 N 1   1 1 s = L ⋅ M ⋅ 1 + + 2 + . + N −1 = L ⋅ M ⋅ n 1 n   n n −1 n A legrosszabb esetet vizsgálva, az összehasonlítások számára s = L ⋅ M ⋅ N

adódik. Mivel az algoritmus idôigénye becsülhetô az összehasonlí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álhatunk. 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 polimorf vírusok már meglévô statisztikájával. Amennyiben egyezôséget tapasztalunk, 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 hasonlítva itt nem a kódsorozat egy részletének a hasonlítása történik, hanem a kódsorozat valamely részletének műveleti kódjaiból készített statisztikát vizsgáljuk. Így egyrészt az utasítások felcserélése esetén is azonosíthatóak a vírusok, viszont a

szekvenciakereséshez mérhetô biztonságú keresés eléréséhez jóval több műveleti kódból képzett statisztikára van szüksé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. 38