Mecanismo pa a e i a a aques po
con abulaci´on basados en code passing
Ma c Jaimez
Uni e si a Poli ecnica de Ca alunya. C/ Jo di Gi ona 1 i 3. Campus No d UPC.
Abs ac . Los agen es m´o iles son en idades so wa e o madas po
c´odigo, da os, i ine a io y es ado, que pueden mig a de hos en hos
au ´onomamen e ejecu ando su c´odigo. A pesa de sus en ajas, los as-
pec os de segu idad es ingen eno memen e el uso de c´odigo m´o il. La
p o ecci´on del agen e an e a aques de hos s maliciosos, es el p oblema
de segu idad m´as di ´ıcil de esol e en los sis emas de agen es m´o iles.
En pa icula , los a aques po con abulaci´on han sido poco es udiados
en la li e a u a. Es e pape p esen a un mecanismo de p o ecci´on an e
a aques po con abulaci´on basados en code passing. Nues a p opues a
es un Mul i-Code Agen que con iene di e en es a ian es del c´odigo pa a
cada hos . Una T us ed Thi d Pa y es la esponsable de p opo ciona
la in o maci´on pa a ex ae cada a ian e, y de oma e e encias em-
po ales que se usa ´an pa a e i ica la cohe encia empo al.
Keywo ds: Mobile agen secu i y, malicious hos s, collusion a ack,
code passing
1 In oducci´on
Los agen es m´o iles son en idades so wa e que mue en c´odigo y da os a hos s
emo os. Los agen es m´o iles pueden mig a de hos en hos ealizando acciones
de o ma au ´onoma o en nomb e de un usua io. El uso de agen es m´o iles pe mi e
aho a ancho banda, y pe mi e una ejecuci´on au ´onoma y o -line. Los agen es
m´o iles son especialmen e ´u iles pa a lle a a cabo a eas au om´a icamen e, en
casi odos los se icios elec ´onicos como el come cio elec ´onico y la adminis-
aci´on de edes. A pesa de sus en ajas, el uso masi o de los agen es m´o iles
se e es ingido po p oblemas de segu idad [12, 22]. Den o de es e escena io,
se conside an dos en idades p incipales a la ho a de es udia los p oblemas de
segu idad: el agen e m´o il, y el hos que lo ejecu a. ´
Es os son los p incipales
a aques: (1) el agen e a aca al hos : la p o ecci´on del hos se consigue usando
´ecnicas de sand-boxing y un ap opiado con ol de acceso [9]; (2) a aque a las
comunicaciones: la p o ecci´on del agen e mien as es ´a mig ando de hos en hos
se puede asegu a median e el uso de los p o ocolos c ip og ´a icos conocidos [15];
y (3) el hos a aca al agen e: no exis e po el momen o ninguna soluci´on pub-
licada que p o eja comple amen e a los agen es an e es os a aques. Es e ´ul imo
a aque es conocido como el p oblema de los hos s maliciosos.
Es e pape in oduce un nue o mecanismo de de ensa an e a aques po con-
abulaci´on basados en code passing. En es e ipo de a aque, un hos en ´ıa el
c´odigo del agen e a o o hos que no es el siguien e des ina a io de la u a, y
de es a o ma es e hos puede analiza el c´odigo del agen e an es que llegue a
a ´es de la u a legal. Los a aques po con abulaci´on son di ´ıciles de p e eni o
de ec a , y es po es a az´on que la mayo ´ıa de p opues as no los esis en. Solo
algunas p opues as in en an limi a es os a aques usando ´ecnicas de p o ecci´on
del i ine a io [6, 3, 19]. El uso de nues o mecanismo implica la ejecuci´on de un
agen e dis in o en cada hos . Pa a hace lo, gene amos dis in as a ian es del
c´odigo del agen e, y las unimos pa a cons ui un Mul i-Code Agen (MCA), que
se ´a la en idad inal que se en ia ´a a los hos s. Cuando un hos s eciba el MCA,
necesi a a cie a in o maci´on (ex ac ing ins uc ions) pa a pode ex ae la a i-
an e del agen e que le co esponda, es as ex ac ing ins uc ionsse ´an solici adas
a una T us ed Thi d Pa y (TTP). ´
Es as pe iciones, se ´an usadas ambi´en po la
TTP pa a oma e e encias empo ales que se i ´an pa a con ola los iempos
de ejecuci´on de los hos s, pe mi iendo de ec a compo amien os maliciosos. El
MCA se cons uye de o ma que se pueda e i a que dos o m´as hos s con abulen
pa a analiza sus a ian es y localiza ulne abilidades en el c´odigo.
2 Hos s Maliciosos
Los a aques ealizados po un hos malicioso que es ´a ejecu ando un agen e
m´o il son, con di e encia, el p oblema de segu idad m´as di ´ıcil de esol e en
un sis ema de agen es m´o iles [8, 13]. Aunque es posible p o ege la mig aci´on
del agen e m´o il de escuchas o manipulaciones, median e el uso de la i ma
digi al o ´ecnicas c ip og ´a icas (communica ions secu i y), es di ´ıcil de ec a o
p e eni a aques ealizados po hos s maliciosos du an e la ejecuci´on del agen e
(po ejemplo p opo ciona in eg idad y p i acidad). Los hos s maliciosos pueden
in en a saca p o echo del agen e, si leen o modi ican el c´odigo, los da os, el
lujo de ejecuci´on, las comunicaciones o incluso los esul ados. El agen e, po
supues o, no puede anspo a una cla e de desci ado ya que el hos pod ´ıa
lee la [5]. Asimismo, si dos o m´as hos s maliciosos colabo an pa a ealiza un
a aque, la a ea de p o ege el agen e se o na a´un m´as di ´ıcil.
En es e pape asumimos que los hos s no son en idades de con ianza (pueden
in en a a aca un agen e cuando lo es ´en ejecu ando). Las p opues as publicadas
que in en an consegui in eg idad de ejecuci´on y p i acidad, se pueden di idi
en dos ca ego ´ıas p incipales: p opues as de de ecci´on de a aques y p opues as
de p e enci´on de a aques. Po un lado, las p opues as de p e enci´on de a aques
in en a e i a a aques de ea esd opping o manipulaci´on, an es de que ocu an.
Po o o lado, el obje i o de las p opues as de de ecci´on de a aques consis e en
p e eni los a aques disuadiendo a los hos s maliciosos.
Ob iamen e, p e eni es mejo que cu a , po lo que las p opues as de p e-
enci´on son m´as e icien es en ´e minos de segu idad. Sin emba go, seg´un nues a
opini´on las ´ecnicas de p e enci´on de a aques son di ´ıciles de implemen a , o sus
cos es compu acionales las hacen di ´ıciles de usa en escena ios eales. De echo,
no exis e ninguna p opues a de p e enci´on de a aques que p opo cione una e-
sis encia sa is ac o ia. Po o a pa e, las ´ecnicas de de ecci´on de a aques suelen
se m´as ´aciles de implemen a , y po ello las conside amos m´as p ome edo as.
No obs an e, las ´ecnicas de de ecci´on de a aques son e ec i as solo en aquellos
escena ios en los que exis a la posibilidad de penaliza a los hos s maliciosos, y
en los que las penalizaciones sean mayo es que los bene icios ob enidos po el
a acan e.
2.1 P opues as de p e encion de a aques
Aqu´ı esumimos las p incipales p opues as que in en an e i a a aques de ea es-
d opping y manipulaciones, p opo cionando p i acidad e in eg idad en la eje-
cuci´on.
En [23], O dille p opone ejecu a los agen es solo en maquinas de con ianza,
es o es, m´aquinas de las cuales no se espe a ning´un ipo de ac i idad an´omala
o maliciosa. Sin emba go, es a p opues a no es ´u il en una ed abie a como
In e ne po que exis en pocos hos s de con ianza. Se puede pensa , de o ma
m´as gene al, en un cie o con ol social y es ablece unos a emos de epu aci´on
de las pla a o mas que ejecu an los agen es. A pa i de es as elaciones de
con ianza en e en idades es posible in e i o as elaciones que pueden se usadas
pa a de e mina el g ado de con ianza de un hos [14, 20]. Desa o unadamen e,
es as p opues as no desc iben los mecanismos de segu idad a u iliza una ez
que se ha de e minado el ni el de con ianza. Algunos au o es p oponen el uso
de un subsis ema ce ado donde se ejecu an de o ma segu a los agen es y al
cual no iene acceso ni el p opio due˜no de la pla a o ma [31, 30, 17]. El p incipal
incon enien e de es a p opues a, es que obliga ´ıa a cada hos con capacidad pa a
ejecu a agen es a adqui i un equipo ha dwa e. Adem´as, es dudosa la con ianza
que se puede deposi a en el ha dwa e de un de e minado suminis ado .
En [26], Ro h p esen a la idea de la p o ecci´on mu ua. En un en o no abie o
como In e ne , se puede asumi que las elaciones de con ianza es ´an limi adas,
y po an o la con abulaci´on en e hos s es poco p obable. Po es a az´on, el
agen e m´o il se en ´ıa jun o con o os agen es coope a i os a a ´es de i ine a -
ios disjun os. El almacenamien o de da os con idenciales y la oma de decisiones
del agen e m´o il se ealizan en esos agen es coope a i os, y po an o los a aques
po ea esd opping o manipulaciones no se pueden ealiza di ec amen e sob e el
agen e m´o il, sino que deben se e ec uados sob e los agen es coope a i os. Po
desg acia, el sis ema debe ga an iza que las comunicaciones en e los agen es co-
ope a i os sean posibles du an e oda la ansacci´on. Adicionalmen e, ienen que
habe mecanismos pa a ecupe a los esul ados en caso que un agen e se pie da.
Todo y con es o, la posibilidad de con abulaci´on no desapa ece po comple o.
En [21], se de ine la en op´ıa de agen es m´o iles como medida m´e ica pa a
calcula las in enciones del agen e. La idea de es a p opues a es hace que las
in enciones del agen e sean desconocidas pa a el hos , po que un hos malicioso
que no sea capaz de in e p e a las in enciones del agen e m´o il, no se ´a capaz
de lee o modi ica el agen e pa a saca bene icio. Es o se puede hace medi-
an e (1) in en ion sp eading, disminuyendola en op´ıa haciendo que el agen e
ejecu e a eas que el usua io no ha pedido; o median e (2) in en ion sh inking,
aumen ando la en op´ıa median e la dis ibuci´on de las in enciones del usua io
en a ios agen es coope a i os. En el p ime caso, nada e i a que los hos s ma-
liciosos ob engan bene icios de odas las a eas. En el segundo caso, enemos los
mismos p oblemas que en la p opues a p e ia de p o ecci´on mu ua [26].
La Gene aci´on de Cla es Dependien es del En o no p esen ada en [25] hace
que el c´odigo del agen e sea imposible de desci a has a que se den las condi-
ciones p opicias, as´ı el an´alisis p e io po pa e del hos se e i a po comple o.
No obs an e, el p incipal p oblema de es a p opues a es que el agen e es ul-
ne able una ez ha sido desci ado, y po an o, la p i acidad y la in eg idad de
ejecuci´on no se pueden asegu a . Adem´as, la p opues a obliga a man ene una
con inua moni o izaci´on del en o no.
Una Blackbox es un en o no so wa e que solo pe mi e la lec u a de las en-
adas y las salidas, y los da os in e nos no pueden se le´ıdos ni modi icados.
Desa o unadamen e, no hay ning´un algo i mo conocido con es as p opiedades.
La Blackbox limi ada en iempo [10] iene es e ni el de segu idad pe o solo du-
an e un pe iodo de iempo limi ado. T anscu ido es e iempo, ni la p i acidad
ni la in eg idad de la ejecuci´on se pueden ga an iza . El mecanismo de Hohl se
basa en un algo i mo de mess-up que o usca el c´odigo y los da os pa a hace los
di ´ıciles de en ende , y po ende de modi ica . La p incipal di icul ad en es e caso
es como es ima el iempo du an e el cual la ejecuci´on es segu a. Po o olado,
ampoco exis en mecanismos pa a e alua la bondad de un algo i mo de mess-
up. Adicionalmen e, un hos malicioso con su icien e iempo y ecu sos pod ´ıa
analiza el agen e o uscado pa a saca in o maci´on, o manipula el agen e pa a
ob ene una ejecuci´on a o able.
El uso de p og amas ci ados [27] se p opone como la ´unica mane a de p opo -
ciona p i acidad y in eg idad de ejecuci´on al c´odigo m´o il. Los hos s ejecu an
el c´odigo ci ado di ec amen e. La unci´on pa a desci a , es u ilizada pa a ecu-
pe a los esul ados cuando el agen e llega al hos o igen. En [4], la p opues a
se mejo a de o ma que los agen es pueden a a esa m´ul iples hos s. En [1], el
esquema p opues o pe mi e a los agen es oma decisiones mien as iajan, g a-
cias al uso de una TTP. La di icul ad con la que se encuen an es as p opues as,
es encon a unciones que pueden se ejecu adas de o ma ci ada.
2.2 P opues as de De ecci´on de A aques
Aqu´ı esumimos las p incipales p opues as publicadas que in en an de ec a ma-
nipulaciones pa a p opo ciona in eg idad de ejecuci´on.
En [18], se in oduce la idea de eplicaci´on y o o. En cada e apa, los hos s
ejecu an el agen e en pa alelo y en ´ıan a ias ´eplicas del agen e a un conjun o
independien e de hos s en la siguien e e apa. En algunas de las e apas, los hos s
compa an los esul ados de los agen es y escogen los esul ados co ec os po
mayo ´ıa. Es a p opues a no solo p opo ciona un mecanismo de ole ancia a allos,
sino que de ec a aquellos hos s que han ealizado un a aque de manipulaci´on. Se
asume que los esul ados de odas las ´eplicas deben se los mismos si odos los
hos s han ac uado hones amen e, po an o odos los hos s en una misma e apa
ienen que ene los mismos ecu sos y da os. Desa o unadamen e, es o no es
cohe en e con la p opiedad de independencia de los hos , po ejemplo los hos s
pueden ene dis in os in e eses pa a a aca al agen e.
En [29, 28], Vigna in oduce la idea de las azas c ip og ´a icas, que son logs
de las ope aciones ealizadas po el agen e du an e su ejecuci´on. Con dichas
azas, se puede ol e a ejecu a el agen e pa a e i ica su ejecuci´on en el
hos . Si el hos o igen sospecha que un hos ha modi icado el agen e y quie e
e i ica lo, pide las azas y uel e a ejecu a el agen e. Si la nue a ejecuci´on
no coincide con las azas, el hos nos es a in en ando enga˜na . En luga de
las azas, el hos en ´ıa un hash de es as pa a e i a a aques de epudio. La
p opues a no solo de ec a manipulaciones, sino que ambi´en p opo ciona una
p ueba del compo amien o malicioso del hos . Sin emba go, es a p opues a iene
dos incon enien es: (1) la e i icaci´on solo se lle a a cabo en caso de sospecha,
pe o no se explica como se de ec a a un hos sospechoso; (2) du an e un pe iodo
inde e minado, cada hos iene que ese a su icien e capacidad pa a almacena
las azas ya que el hos o igen se las puede pedi . [7], aun as´ı, conside amos que
el uso de azas sigue siendo muy cos oso pa a odas las en idades in oluc adas.
En la p opues a de los Es ados de Re e encia1[11], la co ec a ejecuci´on en
un hos se e i ica en el siguien e hos . Es a p opues a se basa en las azas
c ip og ´a icas de Vigna, pe o iene el p oblema de en ia los da os de en ada
del agen e (que pueden se con idenciales) al siguien e hos pa a e i ica la eje-
cuci´on. Algunas p opues as pos e io es es ´an basados ambi´en en las azas de
Vigna [32, 16], pe o ninguna de ellas soluciona el p oblema de de ec a manipu-
laciones de o ma sa is ac o ia.
En [2] se usa un agen e clon pa a ealiza una ejecuci´on de e e encia del
agen e. Si un hos ha al e ado el c´odigo del agen e o la ejecuci´on, podemos
compa a la con la ob enida po el clon de e e encia. Con es a p opues a pode-
mos de ec a los a aques p ´ac icamen e en el momen o de lle a se a cabo. Sin
emba go, las con inuas e i icaciones de la ejecuci´on implican una cons an e co-
municaci´on en e agen es. Adem´as, la ejecuci´on de dos agen es (uno ejecu ado
po el hos , y el o o en una TTP) conlle a un gas o mayo de ancho de banda y
ecu sos compu acionales. En [24], dis in os agen es (agen es m´o iles y agen es
seden a ios) coope an, el agen e m´o il es ejecu ado po los hos s y los agen es
seden a ios son ejecu ados en pla a o mas de con ianza que gene an ejecuciones
de e e encia.
3 Mul i-Code Agen
En es e pape p esen amos un nue o mecanismo que pe mi e esis i a aques po
con abulaci´on basados en Code Passing. Tal y como hemos mencionado p e ia-
men e, los a aques po con abulaci´on en sis emas de agen es m´o iles apenas han
sido es udiados. En un a aque basado en Code Passing, un hos en ´ıa el c´odigo
del agen e a o o hos que no es el siguien e des ina a io en la u a del agen e,
1Los es ados de e e encia son aquellos que han sido p oducidos en hos s de e e encia
(de con ianza)
sino que es cualquie o o den o del i ine a io; g acias a es o, es e hos puede
dispone del c´odigo del agen e mucho an es de ecibi lo a a ´es de la u a legal,
y po an o puede ap o echa ese iempo pa a analiza lo en busca de posibles
ulne abilidades.
O igin H os H os 1 H os 3H os 2 H os 4
A gen A gen A gen A gen
Collusion ou e
Collusion ela ion
O igin H os H os 1 H os 3
H os 2 H os 4
M u l i-C o de
A gen
Collusion ou e
Collusion ela ion
TTP
(a)
(b)
M u l i-C o de
A gen
M u l i-C o de
A gen
M u l i-C o de
A gen
M u l i-C o de A g en
Fig. 1. El p oblema del Code Passing
En la Figu a 1.a se mues a un a aque po con abulaci´on basado en Code
Passing: el hos o igen en ´ıa el agen e m´o il al Hos -1, que ejecu a el agen e
de o ma no mal y lo en ´ıa al p ´oximo hos (Hos -2) a a ´es del i ine a io
ma cado. Al mismo iempo, el Hos -1 en ´ıa el c´odigo del agen e a o o hos
den o del i ine a io, llam´emosle Hos -4, quien dispond ´a de m´as iempo pa a
analiza el c´odigo del agen e en busca de posibles ulne abilidades.
Pa a e i a lo, gene a emos di e en es a ian es del c´odigo del agen e o ig-
inal, las uni emos de o ma adecuada, y cons ui emos un Mul i-Code Agen
(MCA), que se ´a la en idad inal que se en ia ´a a odos los hos s. Cuando un
hos s eciba el MCA, necesi a a cie a in o maci´on (ex ac ing ins uc ions) pa a
pode ex ae la a ian e del agen e que le co esponda, es as ex ac ing ins uc-
ions se ´an solici adas a una T us ed Thi d Pa y (TTP). A su ez, la TTP
se enca ga ´a de ob ene e e encias empo ales pa a con ola los iempos de
ejecuci´on de los hos . Finalmen e, cuando el hos inalice la ejecuci´on de su a i-
an e, en ia ´a el MCA al siguien e hos y el p oceso empeza ´a de nue o. El MCA
se dise˜na po an o con el obje i o de e i a que dos o mas hos s con abulen
y puedan analiza el c´odigo de sus a ian es pa a halla ulne abilidades. Las
e e encias empo ales se usan pa a limi a el iempo de ejecuci´on en cada hos ,
con lo que se pueden de ec a compo amien os maliciosos.
En la Figu a 1.b se mues a la idea p incipal de es e mecanismo. El hos
o igen en ´ıa el MCA al p ime hos del i ine a io, Hos -1. El Hos -1 solici a las
ex ac ing ins uc ions a la TTP pa a pode ex ae su co espondien e a ian e,
y a su ez la TTP usa es a solici ud pa a oma una e e encia empo al de con-
ianza. Seguidamen e, el Hos -1 ejecu a su a ian e y en ´ıa el MCA al siguien e
hos en el i ine a io, Hos -2. El Hos -1 sigue eniendo la posibilidad de en ia
el MCA (o incluso su p opia a ian e) a o o hos di ec amen e, po ejemplo
al Hos -4, a a ´es de la u a de con abulaci´on. Sin emba go, es e ´ul imo no
pod ´a ex ae su a ian e sin dispone de las ex ac ing ins uc ions pe inen es.
Adem´as, como la TTP con ola los iempos de ejecuci´on, el Hos -4 no pod ´a
solici a las ex ac ing ins uc ions has a que el Hos -3 le en ´ıe el MCA.
3.1 E apa de Codi icaci´on
La e apa de codi icaci´on empieza con la modi icaci´on del c´odigo del agen e o ig-
inal pa a ob ene las di e en es a ian es ( e Figu a 2.a). Tal como se mues a,
el agen e o iginal iene una secci´on de C´odigo, que con iene odo el By ecode
del agen e, y una secci´on de Resul ados que hace e e encia a la es uc u a de
da os d´onde se gua dan los esul ados de la ejecuci´on. En es e ejemplo en pa -
icula hay es a ian es del agen e o iginal, ya que el agen e se a a ejecu a
en es hos s dis in os. Es as es nue as a ian es del agen e deben cumpli dos
unciones b´asicas: p opo ciona By ecodes dis in os, y p opo ciona una es uc-
u a de da os dis in a pa a los esul ados de ejecuci´on de cada uno de los hos .
Despu´es de ob ene odas las a ian es, el codi icado oma el By ecode de cada
una de ellas y cons uye el MCA. Es e p oceso se di ide en es ases: la ase de
Me ging, la ase de Meshing up, y la ase de Comp essing. En la ase de Me ging
( e Figu a 2.b) se oma el By ecode de odas y cada una de las a ian es las
a ian e y se pone odo jun o en un ´unico a chi o. En la ase de Meshing up
( e Figu a 2.c) se mezclan las ins ucciones By ecode de los dis in as a ian es.
Finalmen e, en la ase de Comp essing ( e Figu a2.d) se elimina edundancia
de c´odigo. Al inal de la ase de codi icaci´on, enemos un MCA que iene una
secci´on de C´odigo (que con iene el By ecode de odas las a ian es) y una secci´on
de Resul ados d´onde se almacenan los esul ados espec´ı icos de cada hos .
C eaci´on de los nue os agen es El Mul i-Code Agen con iene el c´odigo
de odas las a ian es del agen e o iginal, y es as deben cumpli dos unciones
b´asicas: p opo ciona dis in os By ecodes (que emos que cada hos ejecu e un
agen e dis in o), y p opo ciona dis in as es uc u as de da os pa a los esul ados
de ejecuci´on (que emos e i ica que cada hos ha ejecu ado el agen e co ec o).
El p oceso de c eaci´on de las a ian es del agen e o iginal se di ide en dos pasos:
Paso1. Modi icaci´on del c´odigo pa a ob ene di e en es es uc u as de da os En
es e paso, modi icamos el c´odigo del agen e o iginal pa a que cada una de las
O ig in al A gen
V a ia n 1
V a ia n 2
V a ia n 3
R esu l s
C od e
M e ging M ixin g C om p essin g
R esu l s 1
R esu l s 2
R esu l s 3
C od e 1
C od e 3
C od e 2
R esu l s 1
R esu l s 2
R esu l s 3
R esu l s 1
R esu l s 2
R esu l s 3
R esu l s 1
R esu l s 2
R esu l s 3
(a)
(b) (c)
(d)
M u l i-C o de A gen
Fig. 2. E apa de codi icacion
a ian es gene e una secci´on de Resul ados dis in a. Cada una de es as secciones
de Resul ados con end ´a una Iden i y Ma k, que se i ´a pa a comp oba que
cada hos ha ejecu ado su co espondien e a ian e. La o ma en que cada hos
dispond ´a oda es a in o maci´on (los p opios alo es, su o den y sus elaciones) en
la secci´on de Resul ados de ini ´a como implemen a su Iden i y Ma k. La secci´on
de Resul ados, inalmen e se adjun a ´a al MCA pa a se en iado al siguien e
hos .
Paso2. Modi icaci´on del c´odigo pa a ob ene a iabilidad en el By ecode El obje-
i o de es e paso es ob ene un conjun o de nue as a ian es, dis in as y di ´ıciles
de analiza , que ealicen las mismas a eas que el agen e o iginal pe o usando un
c´odigo dis in o. Sin emba go, ecomendamos que es as nue as a ian es engan
una es uc u a simila (mismas clases, m´e odos, nomb es, a iables, e c) y solo
se modi ique el c´odigo de los m´e odos pa a in oduci di e encias en e a ian es.
Si espe amos es a es icci´on, se emos capaces de educi signi ica i amen e la
longi ud del MCA, la longi ud de las ex ac ing ins uc ions, y la complejidad
de las ex ac ing ins uc ions. Es impo an e ecalca que cuando decimos que
odas las a ian es deben ene una es uc u a simila , es o no signi ica que se
deba man ene la es uc u a del agen e o iginal.
Pa a ilus a la impo ancia de man ene la es uc u a b´asica de las clase en
odas las a ian es, mos a emos un ejemplo con un agen e o iginal y dos a i-
an es. La Figu a 3.a mues a el c´odigo del agen e o iginal, que es a compues o
po una ´unica clase llamada O iginalAgen Code. Es a clase con iene un ´unico
m´e odo llamado me hod1(), que ealiza un simple c´alculo a i m´e ico a= 10+20,
y de uel e el esul ado. Como se puede e , pa a c ea las nue as a ian es man-
enemos la misma es uc u a del agen e o iginal (una clase y un m´e odo) pe o
a˜nadimos dos nue as a iables, byc. Es as dos nue as a iables nos pe mi i ´an
ealiza las mismas ope aciones que ealizaba el agen e o iginal, pe o de mane a
dis in a. La Figu a 3.b mues a el c´odigo de la p ime a a ian e, y la Figu a
3.c mues a el c´odigo de la segunda a ian e. La ´unica di e encia en e ambas
a ian es es el o den en que se usan las a iables.
public class O ig ina lA ge n C o de {
in m e hod 1(){
in a = 10 + 20;
e u n a ;
}
}
public class O ig ina lA ge n C o de A {
in m e hod 1( ) {
in a;
in b;
in c;
a = 10 ;
b = 10 + a;
c = a + b;
e u n c;
}
}
public class O ig ina lA ge n C o de B {
in m e hod 1( ) {
in a;
in b;
in c;
c = 10;
a = c + 10;
b = a + c;
e u n b ;
}
}
(a)
(b ) (c)
Fig. 3. C´odigo o iginal y c´odigo de las nue as a ian es
Si analizamos el c´odigo del ejemplo, ambas a ian es ienen una longi ud de
3328 bi s, pe o an solo 144 bi s de los 3328 son dis in os pa a cada a ian e. Es o
signi ica que solo un 3,42% del By ecode di ie e de una a ian e a o a, y es debido
al hecho que hemos usado la misma es uc u a pa a las dos a ian es. Si hubie an
m´as de dos hos s en el i ine a io, necesi a ´ıamos mas a ian es del agen e o iginal,
y po an o debe ´ıamos implemen a la misma ope aci´on a i m´e ica de mane a
dis in a pa a cada nue a a ian e. Pa a hace lo, simplemen e debe ´ıamos inclui
nue as a iables y cambia el o den en que las usamos.
Cons uyendo una Iden i y Ma k La Iden i y Ma k es un ec o que con-
iene n alo es. Es os alo es pueden se esul ados de ejecuci´on Ri, o pueden
se alo es in e medios Vj. Un ejemplo sencillo de una posible implemen aci´on
de una Iden i y Ma k con n= 5 se mues a en la Figu a 4. El Hos ejecu a el
c´odigo de su a ian e y ob iene dos alo es que se co esponden a los esul ados
de ejecuci´on (R1yR2), y es alo es in e medios (V1,V2,V3). Con odos es os
alo es, el agen e cons uye una es uc u a de da os que implemen a su Iden i y
Ma k, y inalmen e la en ´ıa jun o al MCA.
La o aleza de la Iden i y Ma k se basa en dos ca ac e ´ıs icas p incipales:
1. El o den de los alo es: la Iden i y Ma k es un ec o o denado de n al-
o es, po an o, exis en n!Iden i y Ma ks dis in as que se pueden ob ene
simplemen e o denando los alo es de mane a dis in a. De es a mane a, la
p obabilidad de gene a la Iden i y Ma k de una cie a a ian e es de 1
n!. En
–Paso 5: el Hos -1 ex ae el c´odigo de su a ian e, la ejecu a, y adjun a los
esul ados de la ejecuci´on D1al MCA an es de en ia lo al siguien e hos
(Hos -2).
–Paso 6 y 7: el es o de hos s del i ine a io ealizan el mismo p oceso que el
Hos -1.
–Paso 8: cuando el ´ul imo hos ha ecibido sus ex ac ing ins uc ions, la TTP
en ´ıa odas las e e encias empo ales ecogidas (T1, ..., TN) al hos o igen .
–Paso 9: el ´ul imo hos en ´ıa el MCA con odos los esul ados de ejecuci´on
(D1, ... ,DN) al hos o igen.
5
T us S e e
H os o igin H os 1 H os 2
I1I2
1
M ul i-C od ed A gen
2
Ins uc ionReques
Ins uc ionResponse
3
4
D1M ul i-C oded A gen
IReq
IResp
6
7
T1T2
8
D1M ul i-C oded A gen D 2
9
Fig. 9. Dis ibucion del Mul i-Code Agen
3.3 E apa de e i icaci´on de las e e encias empo ales
La TTP ha es ado omando e e encias empo ales cada ez que ha ecibido una
pe ici´on de ex ac ing Ins uc ions (IReq) ´alida. G acias a es o, a a se posible
(a pos e io i) calcula el pe iodo de iempo en el que cada hos ha dispues o
de su a ian e. La Figu a 10 nos mues a un diag ama empo al en el que se
puede ap ecia que la TTP oma la e e encia empo al jus o en el momen o
en que en ´ıa el Ins uc ion Response message (IResp) al hos . Es as e e encias
empo ales se u ilizan en el hos o igen pa a e i ica la cohe encia de iempos
de ejecuci´on en los hos s. El hos o igen calcula 4Ti=Ti+1 −Ti, que incluye el
iempo de ex acci´on del agen e, el iempo de ejecuci´on de agen e, el iempo de
ansmisi´on del MCA al siguien e hos , el e a do de p opagaci´on, y el in e alo
de iempo desde que el hos siguien e ecibe el MCA has a que es e ecibe el
IResp. Con oda es a in o maci´on, el hos o igen es capaz de es ima el iempo
de ejecuci´on de cada agen e.
H os 1
TTP
H os 2
IR eq
IR es
Ex ac Execu ion D1M C A
D1M CA IR eq
IR es
T1T2
∆T1=T2-T1
T im es am p T im es am p
Ex ac
Ti
Fig. 10. Times amps s o ing
Dependiendo de las ca ac e ´ıs icas compu acionales de los hos s, y de los
ecu sos necesa ios pa a ejecu a los agen es, el hos o igen es ima un iempo
m´aximo de ejecuci´on pe mi ido (4TMax). En el caso que alg´un 4Tisea mayo
que es e alo , el hos se ´a e ique ado como sospechoso de ealiza ac i idades
maliciosas. La Figu a 11 nos mues a dos lineas empo ales, una en la que el Hos -
2 ac ´ua hones amen e, y o a en la que ac ´ua maliciosamen e. Si el Hos -2 ac ´ua
hones amen e, no ebasa ´a el m´aximo iempo de ejecuci´on, y po an o, el hos
o igen de ec a ´a que 4THones Hos <4TMax. Po o o lado, si el Hos -2 in en a
analiza el c´odigo del agen e en busca de ulne abilidades, ebasa ´a el iempo
m´aximo de ejecuci´on, y el hos o igen de ec a ´a que 4TMaliciousHos >4TMax.
En es e caso el Hos -2 se ´a sospechoso de ac ua maliciosamen e.
3.4 Fase de e i icaci´on de la cohe encia de los da os
Como hemos mencionado con an e io idad, cada agen e iene una Iden i y Ma k
p opia, que se codi ica en los esul ados de ejecuci´on. Analizando es as Iden i y
Ma ks, se emos capaces de e i ica que a ian e ha sido ejecu ada po cada hos .
Conc e amen e, al inal del p oceso de dis ibuci´on, el hos o igen ecibe el MCA
con los esul ados de ejecuci´on, y una po una a ex ayendo odas las Iden i y
Ma ks. Si al ex ae una Iden i y Ma k, comp o amos que se co esponde con
la que espe amos ob ene , en onces enemos un esul ado posi i o y asumimos
TTP
H os 2 (H on es )
IR eq
IR es
Ex ac Execu ion DiM C A IR eq i+1 IR es TTP
TiTi+ 1
H os 2 (M a licio us)
Ex ac IReq i+1 IR es TTP
??????????????????? Execu ion
IR eq
∆TM a x
DjM CA
∆TM a l ic io u s H o s
∆TH o n e s H o s
Fig. 11. Ejecuci´on hones a s ejecuci´on maliciosa
que es e hos en pa icula ha ejecu ado su a ian e asignada. En caso con a io,
asumimos que el hos ha ejecu ado cualquie o a a ian e o ha ejecu ado una
e si´on al e ada de la suya p opia, y po lo an o lo e ique amos como sospecho.
3.5 Ejemplo de a aque po con abulaci´on basado en code passing
Tal y como hemos con ado, en un a aque basado en Code Passing, un hos en ´ıa
el c´odigo del agen e a o o hos que no es el siguien e des ina a io en la u a
del agen e, sino que es cualquie o o den o del i ine a io; g acias a es o, es e
hos puede dispone del c´odigo del agen e mucho an es de ecibi lo a a ´es de la
u a legal, y po an o puede ap o echa ese iempo pa a analiza lo en busca de
posibles ulne abilidades. Pos e io men e, cuando el segundo hos in oluc ado
en el a aque eciba el agen e a a ´es de la u a legal, in en a ´a ob ene una
ejecuci´on a o able. Pa a in en a e i a es e ipo de a aques, usa emos nues o
Mul i-Code Agen .
Supongamos que el i ine a io de nues o MCA es a compues o po ein e
hos s, y que dos de es os hos s ienen in enci´on de ealiza un a aque basado en
Code Passing. En es e caso, el hos o igen cons ui ´a un MCA compues o po
ien e a ian es del agen e o ginal (una po cada hos del i ine a io). La Figu a
12 nos mues a una isi´on gene al del conjun o de acciones lle adas a cabo po
los hos s maliciosos en su in en o de ealiza un a aque po Code Passing. El
Hos -1, ecibe el MCA del hos o igen y pide las ex ac ing ins uc ions a la TTP.
La TTP au en ica al Hos -1, e i ica que puede en ia las ex ac ing ins uc ions
en ese momen o, y inalmen e las en ´ıa. Una ez que el Hos -1 ha ecibido las
ex ac ing Ins uc ions, en ´ıa oda la in o maci´on necesa ia al Hos -13 (el MCA,
las ex ac ing ins uc ions de la a ian e 1, o cualquie in o maci´on que puede
se u ilizada pa a a aca el agen e. Despu´es de es o, el Hos -1 con inua con la
ejecuci´on no mal de su a ian e, ob iene los esul ados de ejecuci´on y en ´ıa el
MCA al siguien e hos (Hos -2), quien ex ae y ejecu a la a ian e B. De es a
o ma, el MCA i ´a siguiendo su u a no mal segun lo dispues o en el i ine a io
ma cado po el hos o ´ıgen, has a llega de nue o al Hos -13 pa a ejecu a la a i-
an e M. Mien as que se p oduce es a mig aci´on ( ease Figu e 12.a), el Hos -13
ap o echa es e iempo pa a analiza la in o maci´on p i ilegiada ecibida a a ´es
de la u a de con abulaci´on (see Figu e 12.b). Con es a in o maci´on p i ilegiada
(el MCA, las ex ac ing ins uc ions del Hos -1, la a ian e A) el Hos -13 puede
in en a en ende como unciona la a ian e M pa a al e a la an es de ejecu a la,
o puede in en a usa la a ian e A.
H os 1
H os 2
H os 3
H os 12
O igin H os
M C A
H os 13
M C A + IR e sp
TTP
IR e q
IR e sp M C A
M C A
· E x a c in g V a ia n M
Tim eline
T1
T2
T3
T12
T13 H os 13
M C A
· A na lyze V a ian A .
· E xecu e V a ia n A .
· R esu l s o V a ia n A :
A1A2A3A4A5
· M odi ying V a ian A o ob ain a
a ou able execu ion.
· F a ou ab le R esu l s :
A*1A*2A*3A*4A*5
TTP
IR e q
IR e sp
· E x a c V a ia n A .
· Ex ac V a ian M .
· E xecu e V a ia n M .
· R esu l s o V a ia n M :
M1M2M3M4M5
· U se in o m a ion o m V a ia n A an alisys
o m odi y V a ian M execu ion .
· A a ch a ou ab le R e sul s om V a ian
A execu ion.
H os 14
M C A
T14
a
H os 13
b1
b
b2
b3
b4
b5
Fig. 12. A collusion a ack based on code passing
El p ime a aque que puede lanza el Hos -13, consis e en in en a a e igua
que ins ucciones del c´odigo del MCA pe enecen ´unica y exclusi amen e a la
a ian e M ( ease la Figu a 12.b1). Es e a aque es imposible que de esul ado sin
ha e ob enido las co espondien es ex ac ing Ins uc ions p e ia pe ici´on a la
TTP. El Hos -13 no dispone de su icien e in o maci´on como pa a de e mina que
ins ucciones pe enecen ´unicamen e a su a ian e, que ins ucciones pe enecen
a o as a ian es, y que ins ucciones pe enecen a odas o a a ias a ian es.
El segundo a aque que puede lle a a cabo el Hos -13 consis e en analiza la
a ian e A pa a in e i cuales son las in enciones del agen e, y in en a en ende
como se cons uye la Iden i y Ma k. Con es o, in en a ´ıa gene a un es uc u a
de da os ´alida a pa i de la in o maci´on ob enida de la ejecuci´on de la a i-
an e A. Como el Hos -1 le ha acili ado las ex ac ing Ins uc ions, el Hos -13
puede ex ae la a ian e A, ejecu a la, y ob ene el ec o con los esul ados
de ejecuci´on [A1A2A3A4A5] de o ma ´apida y sencilla, pe o no ob end ´a la in-
o maci´on deseada pues o que es e ec o en pa icula no se co eponde con
la iden i y ma k del Hos -13 (ya que los alo es dependen de la a ian e que
se ha ejecu ado). Aun as´ı, el Hos -13 puede in en a analiza es os esul ados
de ejecuci´on pa a en ende como se cons uye la Iden i y Ma k ( ease Figu a
12.b2). Sin emba go, el an´alisis de una e si´on pa icula de una Iden i y Ma k
no le pe mi i ´a desen a˜na la es uc u a de la Iden i y Ma k. Tan solo le pe mi-
i an ob ene los alo es que compenen es a Iden i y Ma k, pe o sin sabe a que
hace e e encia cada uno de ellos ni a que secuencia de o denaci´on es ´an suje os.
Es deci , algunos de es os alo es se co esponden con esul ados de ejecuci´on
p opiamen e dichos (Ri), y el es o se co esponden con alo es in e medios (Vi),
pe o de echo el Hos -13 no sabe que alo es se co esponden a uno a o a o o
g upo ni en que o den. al y como se mues a en la Figu a 13.a, el Hos -13 no
puede ex apola la elaci´on en e los Hos 13 Aiy los Vio los Ri. Po ´ul imo,
el Hos -13 puede in en a analiza el c´odigo de la a ian e A, y modi ica lo pa a
ob ene una ejecuci´on a o able. G acias a es a ejecuci´on deshones a, se gene an
unos esul ados de ejecuci´on al e ados [A∗
1A∗
2A∗
3A∗
4A∗
5] ( ease la Figu a 12.b3)
que pueden se compa ados pos e io men e con los esul ados ob enidos hon-
es amen e usando la a ian e M. Pa a ello, cuando el Hos -13 ecibe el MCA
desde el Hos -12 (a a ´es de la u a legal), es e inalmen e puede pedi las ex-
ac ing Ins uc ions a la TTP y ex ae la a ian e M. Aho a, el Hos -13 iene
un iempo limi ado pa a pa a ejecu a la a ian e M, y po lo an o no puede
in e i demasiado iempo en en ealiza un an´alisis p o undo del c´odigo. Es po
es o, que la ´unica cosa que puede hace es ejecu a la a ian e M hones amen e,
ob ene [M1M2M3M4M5], y usa la in o maci´on ex a´ıda p e iamen e pa a
modi ica es os alo es con enien emen e y ob ene una Iden i y Ma k ´alida
(Figu a 12.b4). Es o se ´ıa posible en el supues o que an o la a ian e A como
la a ian e B, cons uye an los alo es de la Iden i y Ma k de la misma o ma y
siguiendo el mismo o den, pe o cada agen e calcula es os alo es de o ma dis-
in a y en un o den dis in o. como consecuencia, el Hos -13 no puede de e mina
la es uc u a de su Iden i y Ma k en base a [A∗
1A∗
2A∗
3A∗
4A∗
5]y[M1M2M3M4M5]
( ease la Figu a 13.b)
Execu ing and deep
an alizy ing V a ian A
A1A2A3A4A5
A*1A*2A*3A*4A*5
M1M2M3M4M5
V1R1V2R2V3V1R1
V2R2V3
?????
N o e nou gh in o m a ion o
un de s and he Iden i y M a k
S uc u e
U sing esu l s o ex ecu ion
A1A2A3A4A5
V1R1V2R2V3
?????
N o enough in o m a ion o unde s an d he Id en i y M a k,
an d no en ough im e o ob ain a a ou able execu ion o
V a ian M
U sing esul s o V a ian A and V a ian M execu ion
Execu ing a m odi ied e sion
o V a ian A
O b en ion o a u o a ble R esu l s
Execu ing and quick
an alizy ing V a ian M
? ? ? ? ?
?
?
Fi s a em p Second a em p
a
b
Fig. 13. Unde s anding he Iden i y Ma k
4 P opues as de o uscaci´on de c´odigo
Exis en a ias ´ecnicas de o uscaci´on de c´odigo que podemos aplica a un agen e
pa a do a lo de mayo obus ez an e un a aque. La o uscaci´on de c´odigo ans-
o ma un p og ama en o o sem´an icamen e equi alen e, pe o que esul a m´as
di icil de en ende median e ingenie ´ıa in e sa. El p oblema que nos encon amos
con las ´ecnicas habi uales de o uscaci´on, es que no las podemos aplica di ec-
amen e sob e el c´odigo del MCA po que es ´a compues o po a ios c´odigos.
Adem´as ampoco las podemos aplica sob e cada a ian e, po que en onces e-
sul a ´ıa muy complicado cons ui el MCA. Po es o debemos aplica un ipo
de o uscaciones espec´ı icas que no a ec en al uncionamien o y a la codi icaci´on
del MCA. En es a Mas e Thesis, se p oponen es posibles o uscaciones que
do a an al MCA de mayo obus ez an e a aques. En p ime luga e emos una
o uscaci´on basada en inse a Dummy Ins uc ions, que no s´on m´as que ins uc-
ciones basu a que no se an a ejecu a pe o que se inse an en zonas de c´odigo
d´onde end ´ıa sen ido usa las. En segundo luga p opond emos una o uscaci´on
consis en e en deso dena los conjun os de ins ucciones den o de cada secci´on
de c´odigo en elazado. Y inalmen e, p opond emos una o uscaci´on muy su il
consis en e en hace que las implemen aciones del c´odigo de los m´e odos pa a
a ian es dis in as, no di ie an en su o alidad. Con es o consegui emos que au-
men e el c´odigo compa ido po las a ian es y po an o pod emos aumen a el
ac o de comp esi´on en la ase de Comp essing.
4.1 Inse ci´on de Dummy Ins uc ions
Es a ´ecnica de o uscaci´on de c´odigo iene una pa icula idad especial, en luga
de o usca el c´odigo uen e, la o uscaci´on se ealiza di ec amen e sob e el c´odigo
compilado (en es e caso el Ja a By ecode). Aunque la M´aquina Vi ual de Ja a
e i ica el c´odigo an es de ejecu a lo, noso os no enemos que p eocupa nos po
es o ya que cuando se ex aigan los agen es se elimina an es as ins ucciones ba-
su a. Las Dummy Ins uc ions son po lo an o, ins ucciones By ecode ´alidas
que se a˜naden di ec amen e al By ecode del MCA con el ´unico obje i o de di i-
cul a la comp ensi´on del c´odigo. Re omando el ejemplo del MCA o mado po
dos agen es, amos a analiza la in o maci´on que pod ´ıa ex ae un a acan e si
no se ealiza alg´un ipo de o uscaci´on. La Figu a 14.a nos mues a la secci´on de
c´odigo en elazado del MCA inal. Es a secci´on de c´odigo en elazado con iene las
implemen aciones del me hod1() ( ease la Figu a 3) an o de la a ian e A como
de la a ian e B. Las celdas esal adas en neg o se co esponden con las ins uc-
ciones espec´ı icas de la a ian e A, las celdas esal adas en g is se co esponden
con las ins ucciones espec´ı icas de la a ian e B, y las celdas blancas con ienen
ins ucciones compa idas po ambas a ian es. La ins ucci´on en la posici´on 0
(bipush10) ca ga el alo en e o 10 en la pila de ope andos, y las ins ucciones en
la posici´on 2 y 3 almacenan es e alo en la a iable local 1 y 3 espec i amen e.
Has a aqu´ı, el c´odigo se de las dos a ian es se puede dis ingui con acilidad ya
que ambas es an ca gando el mismo alo (10) en dis in as a iables. Has a la
posici´on 10 (iadd), un a acan e con conocimien os de Ja a By ecode pod ´ıa sep-
a a las ins ucciones de cada a ian e, si nos ijamos, el agen e A ha gua dado
el alo en la a iable local cuyo ´ındice es 1 (is o e−1), mien as que el agen e
B ha gua dado ese mismo alo en la a iable local cuyo ´ındice es 3 (is o e−3).
Pos e io men e el agen e A usa la ins ucci´on iload−1 (almacena en la pila el
alo con enido en la a iable local 1), y el agen e B usa la ins ucci´on iload−3.
Es deci , cada agen e almacena ´a y ex ae ´a alo es de la misma a iable local.
Pa a e i a que el a acan e puede llega a deduci es a in o maci´on, podemos
en p ime luga inclui una Dummy Ins cuc ion que ca gue un alo a bi a io
en la pila de ope andos, po ejemplo bipush 20 ( ease la Figu a 14.b). Al pone
es a ins ucci´on inmedia amen e despu´es del bipush10, el a acan e no sab `a a
que alo hace e e enecia la ins ucci´on is o e−1 y la ins ucci´on is o e−2. Si
ealizamos a ias inse ciones de es e ipo a lo la go del c´odigo, el a acan e nece-
si a ´a in e i mucho iempo pa a ob ene las m´ul iples posibles combinaciones
´alidas, y de odos modos no sab ´ıa dis ingui cual es la buena. O a soluci´on
a es e p oblema, consis e en a˜nadi almacenamien os y ex acciones de las a i-
ables locales ( ease Figu a 14.c). Si po ejemplo a˜nadimos un is o e−2 en la
posici´on 3, y un iload−2 en la poici´on 8, el a acan e nos sabe cual de es as
ins ucciones es a usando cada agen e. Adem´as si aplicamos inse ciones de in-
s ucciones bipushby e conjun amen e con inse ciones de ins uccionec is o e−i
yiload−i, podemos consegui o uscaciones m´as elabo adas que ha ´an que un
a acan e no pueda ni an siquie a en ende acciones peque˜nas del c´odigo.
Debemos ene en cuen a que el c´odigo mos ado en el ejemplo ( ease Figu a
14) co esponde a una implemen aci´on muy sencilla. P obablemen e, si usa amos
una agen e eal, el c´odigo de po s´ı ya se ´ıa conside ablemen e m´as complejo.
Sin emba go, y eniendo en cuen a que nos podemos encon a cualquie ipo
de agen e, hemos op ado po conside a que el c´odigo esul an e es sencillo de
en ende pa pone nos en el peo de los casos. La en aja de es as o uscaciones
al ni el del By ecode, es que podemos o usca cualquie ipo de c´odigo de o ma
muy local. El incon enien e p incipal de es a ´ecnica, es que esul a muy edioso
ene que i inse ando ins ucciones una po una sob e odo cuando se a ´e de
c´odigos de longi ud conside able. Po odo es o, ecomendamos usa es a ´ecnica
solo pa a co egi peque˜nas secciones de c´odigo que pueden se en endidas con
cie a acilidad. Pa a do a a odo el conjun o de c´odigo en elazado de mayo
opacidad, ecomendamos usa la ´ecnica desc i a en 4.4.
0 bipu sh 10
2is o e_1
3is o e_3
4bip ush 10
6ilo ad_3
7ilo ad_1
8bip ush 10
10
11
12
13
14
15
16
17
18
19
20
iadd
is o e_2
is o e_1
ilo ad_1
ilo ad_2
ilo ad_3
iadd
is o e_3
is o e_2
ilo ad_3
ilo ad_2
21 i e u n
(a)
0 bipu sh 10
2 bipu sh 20
4is o e_1
5is o e_3
0 bipu sh 10
2is o e_1
3is o e_2
4is o e_3
5bip ush 10
7ilo ad_3
8ilo ad_2
9ilo ad_1
10 bip ush 10
12 iad d
(b) (c)
6bip ush 10
8ilo ad_3
9ilo ad_1
10 bip ush 10
12 iad d
Fig. 14. O uscaci´on po inse ci´on de Dummy Ins uc ions
4.2 Al e aci´on del o den de las ins ucciones
En la ase de Mixing, ealizamos un en elazado con las ins ucciones espec´ı icas
de cada a ian e, y de es a o ma se gene an conjun os de ins ucciones que
pe enecen a dis in as implemen aciones, pe o que a su ez hacen e e encia al
mismo segmen o de c´odigo en cada una de a ian es. Den o de es os conjun os,
las ins ucciones pe enecien es a cada a ian e se pueden o dena de o ma
dis in a pa a cada segmen o. G acias a es a cons an e al e aci´on del o den de
las ins ucciones, si se consigue desci a el o den de un conjun o de ins ucciones,
el es o no se e comp ome ido. La Figu a 15.a nos mues a a ios segmen os
de c´odigo en elazado d´onde no se ha al e ado el o den de apa ici´on de las
a ian es. La Figu a 15.b mues a a ios segmen os de c´odigo en elazado d´onde
se ha al e ado el o den de apa ici´on de las ins ucciones.
2 0 2
2 0 3
2 0 4
2 0 5
2 0 6
V a ia n 1
V a ia n 2
V a ia n 3
V a ia n 4
V a ia n 5
(a)
2 0 7
2 0 8
2 0 9
2 1 0
2 1 1
V a ia n 1
V a ia n 2
V a ia n 3
V a ia n 4
V a ia n 5
2 1 2
2 1 3
2 1 4
2 1 5
2 1 6
V a ia n 1
V a ia n 2
V a ia n 3
V a ia n 4
V a ia n 5
2 1 7
2 1 8
2 1 9
2 2 0
2 2 1
V a ia n 1
V a ia n 2
V a ia n 3
V a ia n 4
V a ia n 5
2 0 2
2 0 3
2 0 4
2 0 5
2 0 6
V a ia n 1
V a ia n 2
V a ia n 3
V a ia n 4
V a ia n 5
2 0 7
2 0 8
2 0 9
2 1 0
2 1 1 V a ia n 1
V a ia n 2
V a ia n 3
V a ia n 4
V a ia n 5
2 1 2
2 1 3
2 1 4
2 1 5
2 1 6
V a ia n 1
V a ia n 2
V a ia n 3
V a ia n 4
V a ia n 5
2 1 7
2 1 8
2 1 9
2 2 0
2 2 1
V a ia n 1
V a ia n 2
V a ia n 3
V a ia n 4
V a ia n 5
(b)
Fig. 15. O uscaci´on po al e aci´on del o den de las ins ucciones
4.3 Compa ici´on de a iables en e a ian es
Nues a p opues a se basa en gene a m´ul iples a iables, y usa las de modo dis-
in o en cada una de las a ian es. De es e modo, las ins ucciones By ecode que
incluyen ´ındices de a iables locales en cada segmen o de c´odigo en elazado, son
dis in as pa a cada a ian e. No obs an e, no es necesa io que las a iables us-
adas po cada a ian e en cada momen o sean o almen e dis in as. Al con a io
de lo que puede pa ece l´ogico, si las a ian es compa en cie as a iables, con-
seguimos que el By ecode esul an e no sea o almen e disjun o y po lo an o es
m´as di ´ıcil pa a un a acan e dis ingui las ins ucciones co epondien es a cada
a ian e.
4.4 P eca ga de a iables
Re omando el p oblema plan eado en 4.1, emos que puede ocu i que el c´odigo
sea ´acil de en ende ( ease la Figu a 14.a). Es o es debido a que en el c´odigo
uen e del agen e, las a iables se usan inmedia amen e despu´es de habe alma-
cenado un alo en ellas. Po lo an o, en el By ecode se pueden dis ingui las
ins ucciones de cada a ian e simplemen e iden i icando que a iable hacen e -
e encia. E iden emen e, es a dis inci´on no se puede ealiza a ni el global, pe o
si que pe mi e dis ingui peque˜nos conjun os de ins ucciones pe enecien es a
dis in as a ian es. Pa a consegui elimina del odo es a posibilidad, amos
a soluciona el p oblema de a´ız haciendo una p eca ga de las a iables en el
c´odigo uen e. Reco demos que nues o esquema de gene aci´on de las a ian es
se basa en la adici´on de m´ul iples a iables al c´odigo o iginal. Es as a iables
se ´an usadas en o den dis in o po cada agen e, de o ma que el c´odigo esul-
an e ambi´en se ´a dis in o. Sabiendo es o, asigna emos p ime o alo es a a ias
a iables y luego ha emos las ope aciones que las in oluc en. El esul ado se ´a
que end emos una amalgama de ins ucciones is o e−iconsecu i as, que en
algunos casos ha an e e enacia al mismo ´ındice, pe o que pe enece ´an a a i-
an es dis in as. Seguidamen e end emos ins ucciones de odo ipo jun o con
las co espondien es iload−i. Con es a ag upaci´on de ins ucciones el a acan e
se ´a incapaza de aza el as o de una a ian e iden i icando los ´ındices de
los is o e−iy los iload−i, y adem´as pod emos comp imi aquellas ins ucciones
que hagan e e encia al mismo ´ındice. Es a ´ecnica es a indicada pa a o usca
agen es cuyo c´odigo sea ex emadamen e sencillo, de longi ud conside able. Su
incon enien e, es que dependiendo de como es e p og amado el c´odigo uen e,
puede aumen a de o ma conside able el ama˜no del MCA. Sin emba go, com-
binando es a ´ecnica con la p esen ada en 4.3 podemos gene a muchas ins uc-
ciones compa idas po a ios agen es, d´ando luga a ins ucciones epe idas
que pueden se comp imidas en un ´unica ins ucci´on. La en aja de usa es as
´ecnicas combinadas, es que las ex ac ing ins uc ions es an dise˜nadas de al
modo que p ´ac icamen e no aumen a ni su longi ud ni su complejidad.
5 Conclusiones
Es e pape in oduce un nue o mecanismo pa a e i a a aques po con abulaci´on
basados en Code Passing. El mecanismo se basa en cons ui un Mul i-Code
Agen que con iene di e en es a ian es del c´odigo de un agen e o iginal. Cada
a ian e se ejecu a en un hos dis in o, y g acias a es o, cualquie in o maci´on
compa ida po los hos s (en una con abulaci´on) no si e pa a ob ene ninguna
en aja. La in oducci´on de una T us ed Thi d Pa y, que se enca ga de dis-
ibui las ex ac ing Ins uc ions y oma e e encias empo ales, nos pe mi e
de ec a y e i a a aques po Code Passing. Aunque el Mul i-Code Agen con-
iene di e en es a ian es del c´odigo de un mismo agen e, la longi ud de es e
es p ´ac icamen e igual a la de un ´unico agen e. Po an o, e i amos malgas a
ancho de banda, que es un incon enien e ´ıpico de las p opues as basadas en el
uso de a ios agen es. Con la inclusi´on de una Iden i y Ma k en los esul ados
