[ Pobierz całość w formacie PDF ]
AClassificationofVirusesthroughRecursion
Theorems
GuillaumeBonfante,MatthieuKaczmarekandJean-YvesMarion
Guillaume.Bonfante@loria.fr,Matthieu.Kaczmarek@loria.frand
Jean-Yves.Marion@loria.fr
Nancy-Universit´e-Loria-INPL-EcoleNationaleSup´erieuredesMinesdeNancy
B.P.239,54506Vandœuvre-l`es-NancyC´edex,France
Abstract.Westudycomputervirologyfromanabstractpointofview.
Virusesandwormsareself-replicatingprograms,whoseconstructionsare
essentiallybasedonKleene’ssecondrecursiontheorem.Weshowthat
wecanclassifyvirusesassolutionsoffixedpointequationswhichare
obtainedfromdierentversionsofKleene’ssecondrecursiontheorem.
Thisleadustoconsiderfourclassesofviruseswhichvariouspolymor-
phicfeatures.Weproposetousevirusdistributioninordertodealwith
mutations.
Topicscovered.Computabilitytheoreticaspectsofprograms,com-
putervirology.
Keywords.Computerviruses,polymorphism,propagation,recursion
theorem,iterationtheorem.
1TheoreticalComputerVirology
Animportantinformationsecuritybreachiscomputervirusinfections.Follow-
ingFiliol’sbook[9],wedothinkthattheoreticalstudiesshouldhelptodesign
newdefensesagainstcomputerviruses.Theobjectiveofthispaperistopursue
atheoreticalstudyofcomputervirusesinitiatedin[4].Sincevirusesareessen-
tiallyself-replicatingprograms,weseethatvirusprogrammingmethodsarean
attempttoanswertovonNeumann’squestion[22].
Cananautomatonbeconstructed,i.e.,assembledandbuiltfromappro-
priately“rawmaterial”,byanotherautomaton?[...]Cantheconstruc-
tionofautomatabyautomataprogressfromsimplertypestoincreasingly
complicatedtypes?
Abstractcomputervirologywasinitiatedinthe80’sbytheseminalworksof
CohenandAdleman[7].Thelattercoinedthetermvirus.Cohendefinedviruses
withrespecttoTuringMachines[8].Later[1],Adlemantookamoreabstract
pointofviewinordertohaveadefinitionindependentfromanyparticular
computationalmodel.Then,onlyafewtheoreticalstudiesfollowedthoseseminal
works.ChessandWhiterefinedthemutationmodelofCohenin[6].Zuoand
ZhouformalizedpolymorphismfromAdleman’swork[23]andtheyanalyzedthe
timecomplexityofviruses[24].
Recently,wetried[3,4]toformalizeinsidecomputabilitythenotionofviruses.
Thisformalizationcapturespreviousdefinitionsthatwehavementionedabove.
Wealsocharacterizedtwokindsofviruses,blueprintandsmithviruses,andwe
provedconstructivelytheirexistence.Thisworkproposestogofurther,introduc-
inganotionofdistributiontotakeintoaccountpolymorphismormetamorphism.
Wedefinefourkindsofviruses:
1.Ablueprintvirusisavirus,whichreproducesbyjustduplicatingitscode.
2.Anevolvingblueprintvirusisavirus,whichcanmutatewhenitduplicatesby
modifyingitscode.Evolvingblueprintvirusesaregeneratedbyadisbution
engine.
3.Asmithvirusisablueprintviruswhichcanuseitspropagationfunction
directlytoreproduce.
4.Lastly,wepresentSmithdistribution.AvirusgeneratingbyaSmithdistri-
butioncanmutateitscodelikeevolvingblueprintviruses,butalsomutate
itspropagationfunction.
Weshowthateachcategoryiscloselylinkedtoacorrespondingformofthe
recursiontheorem,givenarationaltaxonomyofviruses.Sorecursiontheorems
playakeyroleinconstructionsofviruses,whichisworthtomention.Indeed,
anddespitetheworks[11,12],recursiontheoremsareusedessentiallytoprove
“negative”resultssuchastheconstructionsofundecidableorinseparablesets,
see[19]forageneralreference,orsuchasBlum’sspeed-uptheorem[2].
Lastly,weswitchtoasimpleprogramminglanguagenamed
WHILE
+
toillus-
tratethefactthatourconstructionslivesintheprogrammingworld.Actually,
wefollowtheideasoftheexperimentationoftheiterationtheoremandofthere-
cursiontheorem,whicharedevelopedin[11,12]byJonesetal.andveryrecently
byMossin[16].
2AVirusDefinition
2.1The
WHILE
+
language
ThedomainofcomputationDisthesetofbinarytreesgeneratedfromanatom
nil
andapairingmechanismh,i.Thesyntaxof
WHILE
+
isgivenbythefollowing
grammarfromasetofvariablesV:
Expressions:E!V|
cons
(E
1
,E
2
)|
hd
(E)|
tl
(E)|
exec
n
(E
0
,E
1
,...,E
n
)|
spec
n
(E
0
,E
1
...,E
n
)withn1
Commands:C!V:=E|C
1
;C
2
|
while
(E){C}|
if
(E){C
1
}
else
{C
2
}
A
WHILE
+
programpisdefinedasfollowsp(V
1
,...,V
n
){C;
return
E;}.Apro-
grampcomputesafunction
J
p
K
fromD
n
toD.
Wesupposethatwearegivenaconcretesyntaxof
WHILE
+
,thatisanencod-
ingofprogramsbybinarytreesofD.Fromnowon,whenthecontextisclear,
wedonotmakeanydistinctionbetweenaprogramanditsconcretesyntax.And
wemakenodistinctionbetweenprogramsanddata.
Forconvenience,wehaveabuilt-inself-interpreter
exec
n
of
WHILE
+
programs
whichsatisfies:
Jexec
n
K
(p,x
1
,...x
n
)=
J
p
K
(x
1
,...x
n
)
Intheaboveequation,thenotationpmeanstheconcretesyntaxoftheprogram
p.
Wealsouseabuilt-inspecializer
spec
n
whichsatisfies:
JJspec
m
K
(p,x
1
,...x
m
)
K
(x
m+1
,...,x
n
)=
J
p
K
(x
1
,...x
n
)
Wemayomitthesubscpriptnwhichindicatesthenumberofargumentsofan
interpreteroraspecializer.
TheuseofaninterpreterandofaspecializerisjustifiedbyJoneswhoshowed
in[13]thatprogramswiththeseconstructionscanbesimulateduptoalinear
constanttimebyprogramswithoutthem.
Iffandgdesignatethesamefunction,wewritefg.Afunctionfis
semi-computableifthereisaprogrampsuchthat
J
p
K
f,moreover,iffis
total,wesaythatfiscomputable.
2.2AComputerVirusrepresentation
Weproposethefollowingscenarioinordertorepresentviruses.Whenaprogram
pisexecutedwithinanenvironmentx,theevaluationof
J
p
K
(x),ifithalts,isa
newenvironment.Thisprocessmaybethenrepeatedbyreplacingxbythenew
computedenvironment.Theentryxisthoughtofasafinitesequencehx
1
,...,x
n
i
whichrepresentsfilesandaccessibleparameters.
Typically,aprogramcopywhichduplicatesafilesatisfies
J
copy
K
(p,x)=
hp,p,xi.Theoriginalenvironmentishp,xi.Aftertheevaluationofcopy,we
havetheenvironmenthp,p,xiinwhichpiscopied.
Nextconsideranexampleofparasiticvirus.Parasiticvirusesinsertthem-
selvesintoexistingfiles.Whenaninfectedhostisexecuted,firstthevirusin-
fectsanewhost,thenitgivesthecontrolbacktotheoriginalhost.Formore
detailswerefertotheviruswritingmanualofLudwig[15].Aparasisticvirus
isaprogramvwhichworksonanenvironmenthp,q,xi.Theinfectedform
ofpisB(v,p)whereBisapropagationfunctionwhichspecifieshowavirus
contaminatesafile.Here,thepropagationfunctionBcanbeforexamplea
programcodeconcatenationfunction.So,wehaveafirst“generic”equation:
J
v
K
(p,hq,xi)=
J
B(v,p)
K
(hq,xi).Followingthedescriptionofaparasiticvirus,
vcomputestheinfectedformB(v,q)andthenexecutesp.Thismeansthatthe
followingequationalsoholds:
J
v
K
(q,x)=
J
p
K
(B(v,q),x).Aparasisticvirusis
definedbythetwoaboveequations.
Moregenerally,theconstructionofvirusesliesintheresolutionoffixedpoint
equationssuchastheonesaboveinwhichvandBareunknowns.Theexistence
ofsolutionsofsuchsystemsisprovidedbyKleene’srecursiontheorem.From
thisobservationandfollowing[4],weproposethefollowingvirusrepresentation:
Definition1(ComputerVirus).LetBbeacomputablefunction.Avirus
w.r.tBisaprogramvsuchthat8p,x:
J
v
K
(p,x)=
J
B(v,p)
K
(x).Then,Bis
namedapropagationfunctionforthevirusv.
ThisdefinitionincludestheonesofAdlemanandCohen,andithandles
morepropagationandduplicationfeaturesthantheothermodels[4].However,
itisworthtonoticethattheexistenceofavirusvw.r.tagivenpropagation
functionBisconstructive.Thisisakeydierencesinceitallowstobuildviruses
byapplyingfixedpointconstructionsgivenbyproofsofrecursiontheorems.
Amotivationbehindthechoiceof
WHILE
+
programminglanguageisthefact
thatthereisnoself-referentialoperator,like$0inbash,whichreturnsacopy
oftheprogramconcretesyntax.Indeed,wepresentbelowvirusconstruction
withoutthisfeature.Thisshowsthatevenifthereisnoself-referentialoperator,
therearestillviruses.Now,virusesshouldbemoreecientifsuchoperatorsare
present.Ofcourse,aseminalpaperonthissubjectis[21].
3BlueprintDuplication
3.1Blueprintdistributionengine
From[4],ablueprintvirusforafunctiongisaprogramvwhichcomputesg
usingitsowncodevanditsenvironmentp,x.Thefunctiongcanbeseenas
thevirusspecificationfunction.Ablueprintvirusforafunctiongisaprogram
vwhichsatisfies
(
visavirusw.r.tsomepropagationfunction
8p,x:
J
v
K
(p,x)=g(v,p,x)
(1)
Notethatablueprintvirusdoesnotuseanycodeofitspropagationfunction,
unlikesmithvirusesthatweshallseeshortly.Thesolutionsofthissystemare
providedbyKleene’srecursiontheorem.
Theorem2(Kleene’sRecursionTheorem[14]).Letfbeasemi-computable
function.Thereisaprogramesuchthat
J
e
K
(x)=f(e,x).
Definition3(Distributionengine).Adistributionengineisaprogramd
v
suchthatforeveryvirusspecificationprogramg,
J
d
v
K
(g)isavirusw.r.tafixed
andgivenapropagationfunctionB.
Theorem4.Thereisadistributionengined
v
suchthatforanyprogramg,
J
d
v
K
(g)isablueprintvirusfor
J
g
K
.
Proof.WeuseaconstructionfortherecursiontheoremduetoSmullyan[20].
Itprovidesafixpointwhichcanbedirectlyusedasadistributionengine.We
defined
v
thankstotheconcretesyntaxofdgasfollows:
dg(z,u,y,x){
r:=
exec
(z,
spec
(u,z,u),y,x);
return
r;
d
v
(g){
r:=
spec
(dg,g,dg);
return
r;
}
}
Weobservethat
JJ
d
v
K
(g)
K
(p,x)=
J
g
K
(
J
d
v
K
(g),p,x).Moreover,
J
d
v
K
(g)isclearly
avirusw.r.ttothepropagationfunction
JspecK
. ut
Weconsideratypicalexampleofblueprintduplicationwhichlookslikethe
reallifevirus
ILoveYou
.Thisprogramarrivesasane-mailattachment.Opening
theattachmenttriggerstheattack.Theinfectionfirstscansthememoryfor
passwordsandsendsthembacktotheattacker,thenthevirusself-duplicates
sendingitselfateveryaddressofthelocaladdressbook.
Torepresentthisscenarioweneedtodealwithmailingprocesses.Amail
m=h@,yiisanassociationofanaddress@anddatay.Then,weconsiderthat
theenvironmentcontainsamailboxmb=hm
1
,...,m
n
iwhichisasequenceof
mails.Tosendamailm,weaddittothemailbox,thatismb:=
cons
(m,mb).
Wesupposethatanexternalprocessdealswithmailing.
Inthefollowing,xdenotesthelocalfilestructure,and@bk=h@
1
,...,@
n
i
denotesthelocaladdressbook,asequenceofaddresses.Wefinallyintroducea
WHILE
+
programfindwhichsearchesitsinputforpasswordsandwhichreturns
themasitsevaluation.Thevirusbehaviorforthescenarioof
ILoveYou
isgiven
bythefollowingprogram.
g(v,mb,h@bk,xi){
pass:=
exec
(find,x);
mb:=
cons
(
cons
(‘‘badguy@dom.com’’,pass),mb);
y:=@bk;
while
(y){
mb:=
cons
(
cons
(
hd
(y),v),mb);
y:=
tl
(y);
}
return
mb;
}
Fromthevirusspecificationprogramg,wegeneratetheblueprintvirus
J
d
v
K
(g).
3.2Distributionsofevolvingblueprintviruses
Anevolvingblueprintvirusisavirus,whichcanmutatebutthepropagation
functionremainsthesame.Here,wedescribeadistributionengineforwhichthe
specificationofaviruscanusethecodeofitsowndistributionengine.Thus,
wecangenerateevolvedcopiesofavirus.Formally,givenavirusspecification
functiong,adistributionofevolvingblueprintvirusesisaprogramd
v
satisfying:
(
d
v
isadistributionengine
8i,p,x:
JJ
d
v
K
(i)
K
(p,x)=g(d
v
,i,p,x)
(2)
Theexistenceofblueprintdistributionscorrespondstoastrongerformofthe
recursiontheorem,whichwasfirstprovedbyCase[5].
[ Pobierz całość w formacie PDF ]