Security and robustness enhanced route structures for mobile agents, ACMKluwer

Mobile Networks and Applications 8, 413–423, 2003 ? 2003 Kluwer Academic Publishers. Manufactured in The Netherlands.

Security and Robustness Enhanced Route Structures for Mobile Agents
Department of Computer Science, National University of Singapore, 3 Science Drive 2, Singapore 117543

Abstract. In this paper, we present a parallel dispatch model with secure route structures for protecting the dispatch route information of mobile agents. This model facilitates ef?cient dispatching of agents in a hierarchical manner, and ensures route security by exposing minimal route information to hosts. It also provides the capability for detecting attacks. Based on the secure dispatch model, two extensions are further presented. The ?rst integrates parallel dispatch with small-scale serial migration to keep the number of mobile agents manageable while preserving similar dispatch performance. The second is a route robustness enhanced mechanism with substitute routes that allows temporarily unreachable hosts to be bypassed. We evaluated the various models both analytically and empirically, and report our ?ndings here. Keywords: mobile agent, secure route, robust route, dispatch model, binary dispatch

1. Introduction In recent years, there have been increasing interests in deploying mobile agents carrying both code and data for distributed processing in an environment such as the Internet. For example, in electronic commerce (EC), a pool of mobile agents can be dispatched from a host to related e-shops to gather “fresh” information, such as price, stock status, warranty and delivery services, for the products speci?ed by a customer [3,11]. Clearly, an ef?cient strategy is to dispatch a large number of agents to work in parallel [8,9,12]. This will also provide customers with the possibility to ?nd the “best” e-shop for his/her purchases. However, for mobile agent technologies to be accepted, performance and security issues on their use have to be addressed. First, deploying a large number of agents may cause signi?cant overhead when dispatching them. Novel methods for dispatching agents are desirable. Second, when a mobile agent arrives at a host for execution, the code and data will be exposed to the host and the resources at the host may also be exposed to the mobile agent. Thus, security mechanisms should be set up to protect mobile agents from malicious hosts as well as to protect hosts from malicious agents. Some works have been done to restrict an agent’s access to the resources of a remote host [5,13]. Protecting the agent is also a dif?cult task. In particular, in an EC environment, since e-shops are competitive, it is important to protect the routes of a mobile agent if it should visit a list of hosts (e-shops) or if it should dispatch mobile agents to other hosts to accomplish the task. If a malicious host knows the route information, it may tamper with it so that its competitors that may offer better prices or services will not be visited. Several secure route structures are presented in [7,18] for protecting a serially migrating agent. But a serial migrating agent can only satisfy small-scale applications. This calls for novel methods to be designed.

In this paper, we present a secure dispatch route structure for a binary dispatch model that can hierarchically and ef?ciently dispatch mobile agents in parallel. The model ensures that minimal route information is revealed to a host that dispatches mobile agents. We further propose two extensions. First, we extend the model to facilitate both parallel dispatch and small-scale serial migration to reduce the number of dispatched mobile agents. In this model, a mobile agent can visit several e-shops within the Intranet of a marketplace. Second, we extend the model with encrypted substitute routes to facilitate robustness to allow temporarily unreachable routes to be bypassed to substitute hosts. We report results on both analytical and empirical evaluations of the various models. In this paper, we employ well-known public-key encryption algorithm, signature generating algorithm and X.509 authentication framework [2,17]. In the following, we assume that there exists a secure environment including the generation, certi?cation and distribution of public keys and each host can know the authentic public keys of other hosts. The rest of this paper is organized as follows. Section 2 presents the secure route structure for binary dispatch model. In sections 3 and 4, we present the two extensions to the model, respectively. The complexities of dispatch and route generation of all parallel models are analyzed in section 5 and the results of experimental study are illustrated in section 6. In sections 5 and 6, our parallel models are also compared with 2 existing serial models. Finally, in section 7, we conclude our work.

2. A basic binary dispatch model with secure route structure In this paper, we assume an infrastructure where a set of marketplaces is connected to the Internet. Within each marketplace, there exist multiple e-shops. Requests by users go



through the master customer-agent A0 running at the server (say H0 ) of Mobile Agent Service Provider (MASP). At H0 , a customer agent can be created as a request from an end-user. We call an agent a Worker Agent (WA) if its sole responsibility is to perform simple tasks assigned to it, e.g., accessing local data on a host. If an agent also dispatches other agents besides performing the task of local data accessing, it is called a Primary Worker Agent (PWA). At the stage of price gathering, since a large number of e-shops may sell the same kind of products, ef?cient dispatch model is needed. Due to limited space, we focus on dispatch issues in this paper. An in-depth discussion on the infrastructure can be found in [14]. 2.1. A binary dispatch model Here, we brie?y introduce the binary dispatch model, which is a typical parallel dispatch model where each parent agent can dispatch two child agents resulting in a binary tree structure. As discussed in [15], the model can be easily generalized to dispatch m (m 2) agents in parallel. As shown in ?gure 1, master agent A0 has to dispatch 16 agents to 16 hosts (e.g., agent Ai to host Hi ). Now, 16 mobile agents can be divided into 2 groups led by two PWAs, say A1 and A9 . When agents A1 and A9 are dispatched to H1 and H9 , respectively, each of them has 8 members including itself. For A1 at layer L1 , it will dispatch its right child agent A5 and distribute 4 members to it. After that A1 will transfer to layer L2 , which is called a virtual dispatch costing no time. Now A1 has 4 members only. Following the same process, A1 dispatches A3 and A2 successively. During all these processes, A1 always resides at H1 without any migration. At the same time when A1 dispatches A5 , A0 dispatches A9 to H9 to activate all agents in another branch in parallel. At last, after all dispatch tasks have been completed, A1 becomes a WA and starts its local data-accessing task at H1 . The whole dispatch process can be illustrated by a dispatch tree, as shown in ?gure 1. As expected, the dispatch complexity is O(log2 n) for dispatching n mobile agents. 2.2. A secure route structure To ensure route security, we applied cryptographic technique to the basic binary dispatch model. For protecting the routes,

we should expose addresses to a host only when necessary. For example, if an agent is at host A, and it has to dispatch an agent to host B, then the address of B must (obviously) be exposed to the host A; however, no other addresses should be exposed. For the binary dispatch model, it is more complicated than the traditional serial migration model since a PWA has different dispatch tasks at different layers. Only the operations for a WA are simple. For the binary dispatch model, a basic de?nition of route structure, is as follows. Route structure (I). (1) For a PWA at current host CH,
r(CH) = PCH isPWA, ip(RH), rL (CH), rR (CH), SH0 H isPWA, ip(PH), ip(CH), ip(RH), rL (CH), rR (CH), t


(2) For a WA at current host CH,
r(CH) = PCH isWA, ip(H0 ), SH0 H isWA, ip(PH), ip(CH), ip(H0 ), t


where: ? r(CH) denotes the route at the current host CH, where the agent should reside; ? isPWA or isWA is the token showing the current state of the agent; ? ip(Hi ) denotes the IP address of host Hi ; ? RH denotes the right child host of current host; ? PH denotes the parent host of current host; ? rL (CH) and rR (CH) denote the encrypted route for the left and right children, respectively; ? PCH [M] denotes the message M is encrypted by the public key PCH of current host CH; ? H(isPWA, ip(PH), ip(CH), ip(RH), rL(CH), rR (CH), t) is the digest with ?x-length (e.g., 128 bytes by MD5) returned by a hash function H (e.g., MD5); ? SH0 (D) denotes the signature signed on digest D by host H0 using its secret key SH0 ; ? and t is the timestamp at which the route is generated at host H0 . t is unique for all routes within a dispatch tree. In route structure (I), ip(PH) and ip(CH) only appear in the signature for veri?cation. Starting the binary dispatch process with secure routes, the agent A0 dispatches two PWAs to different hosts, each being encapsulated with an encrypted route for future dispatch task. When an agent has successfully arrived at the current host CH, the carried route r(CH) can be decrypted with the secret key of CH so that the agent can know:

Figure 1. Dispatch tree with 16 mobile agents.

(1) it is a PWA or a WA. It is used to determine the next task of the agent;



(2) the signature signed at host H0 : SH0 (H(isPWA, ip(PH), ip(CH), ip(RH), rL (CH), rR (CH), t)) for a PWA, or SH0 (H(isWA, ip(PH), ip(CH), ip(H0), t)) for a WA. If it is a PWA, it will also know: (1) the address ip(RH) of the right child host RH; (2) the encrypted route rR (CH) for the right child agent, which can only be decrypted by the right child host; (3) the encrypted route rL (CH) for the left dispatch (virtual dispatch). If it is a WA, it will know the address of H0 , ip(H0 ), the home host where A0 is residing. With this address, the WA can send its result to A0 . Clearly, in this model, at any layer, only the address of the right child agent is exposed to the current host so that the right dispatch can be completed. For a PWA, if it has m = 2k members, only k addresses of its members are exposed to the current host. The algorithm for dispatching agents is described as follows. Algorithm 1. Binary dispatch with secure routes. Step 1. When an agent A is successfully dispatched to a host CH, the host will use the secret key SCH , to decrypt the carried route r(CH), obtaining the route r as
r = SCH r(CH) .

where SH0 (H(isWA, ip(PH), ip(CH), ip(H0), t)) is the signature from H0 , which is included in the decrypted route of the agent. Here it is used to show the identi?cation of the agent. SCH (H(ip(PH), ip(CH), ResultCH, tResult )) is the signature generated by current host CH. ResultCH is the result obtained at CH. PH is the parent host of CH and tResult is the time when getting the result (tResult > t). 2.3. Resolving security threats We shall examine several security issues that will be encountered when dispatching mobile agents and show how our model resolves them. 2.3.1. Preventing a PWA from dispatching a child agent When an agent is dispatching a child agent, a malicious host may peek into the code and modify it to stop the dispatch process in certain layer after the route is decrypted. In the worst case, assuming host H1 is the malicious one, taking the case shown in ?gure 1 as an example, if A5 is not dispatched, those agents in the group including A5 –A8 will not be activated. However this attack can be detected in our model because in such a case agent A0 cannot receive any messages from each agent of A5 , A6 , A7 or A8 . If this happens, since the four agents belong to the same group led by agent A5 , A0 will suspect ?rst that A5 may have not been dispatched. A0 will ask hosts H1 and H5 to show whether the prede?ned dispatch has been performed. Apparently, if the dispatch has been carried out, H1 will receive the con?rmation message with the signature SH5 (H(EntityA5, ip(H5 ), tr )) from H5 . H1 cannot forge this signature without H5 ’s secret key. So, no matter what H1 claims, the attack can be detected. Even H1 and H5 make a collusion attack, the attack can be detected since A0 cannot receive any message from A6 , A7 and A8 and no con?rmation information for dispatch can be produced by H5 . If H6 , H7 and H8 are also accomplices, the attack may be successful but no honest host is affected. 2.3.2. Dispatch skip attack There is yet another case that can be handled in this model. Let us consider a partial dispatch route: PWA Ai at host Hi dispatches Aj to Hj and Aj dispatches Ak to Hk . In our model, the encrypted route encapsulated to a PWA includes the encrypted route for its right child agent, which can only be decrypted at the child host in the dispatch route. This means when a PWA is dispatching an agent, normally it does not know what the child agent is, a PWA or a WA, and how many members it has. So the case that Ai directly dispatches Ak is not likely to take place without the involvement of Aj . This explains why the encrypted route uses the nested structure. In the worst case, even if Hi can successfully predict that Hk is its descendant in the dispatch route and makes Ai dispatch a forged agent to Hk , the attack will not be successful either since forging the signature is impossible. The skip attack can be successful only when Hi , Hj and Hk are accomplices. But no honest is affected.

Step 2. If A is a WA, go to step 6; otherwise, A is a PWA, it will dispatch another agent to the host at ip(RH), encapsulating the right dispatch route rR (CH) to it. Step 3. If the dispatch is successful, host RH will send back a message including its signature to CH:
msg = SRH H EntityRS , ip(RH), tr ,


where EntityRS is the full entity of the received agent including its code, state and data; tr is the timestamp when receiving the agent successfully; H is the hash function. Once getting such a message, host CH will keep SRH (H(EntityRS, ip(RH), tr )) in its database as a successful dispatch record. Step 4. Now A should try to complete its left dispatch after decrypting the left dispatch route. Let r = SCH [rL (CH)]. Step 5. If A is still a PWA, go to step 2; otherwise go to step 6. Step 6. A is a WA and starts its task for local data accessing. Step 7 . When the data access task is completed, A will be disposed after successfully sending a message to agent A0 ,
msg = PH0 ip(PH), ip(CH), ResultCH, SH0 isWA, ip(PH), ip(CH), ip(H0), t , SCH H ip(PH), ip(CH), ResultCH, tResult





2.3.3. Dispatching an agent to a wrong host Since the hosts (e-shops) may be competitors, a malicious host may tamper with the addresses so that agents are routed to other hosts instead of the predetermined hosts. The tampering can be done just after the encrypted route is decrypted. However, when an agent is dispatched to a wrong host, its encrypted route will not be correctly decrypted there. Without the correct route, the veri?cation process cannot be undertaken. Even if the destination host can get the correctly decrypted route, the veri?cation will show that is a wrong destination since the address of the destination host is included in the signature in the route generated by H0 that cannot be tampered with. Thus, in both situations, the attack can be detected by the destination host and the agent will be returned to the sender. Meanwhile, this error will be recorded by the destination host for future investigation. 2.3.4. Sending the result of a WA to A0 directly or not In our model, when a WA has ful?lled its data access task, it will send a message to A0 directly by encrypting the result, the signature by current host as well as the signature by the H0 originally included in the agent’s route. The structure is shown as message (2) in section 2.2. The whole message is encrypted with the public key of H0 . We choose this strategy in this model with regard to both security and performance issues. An alternative is that a PWA should be responsible for dispatching agents and collecting data from them. But this solution increases the workload of a PWA and the possibility of attacks in the result-returning path. In comparison, in our model, since a WA only visits one host, the host would not delete the result or prevent its offer from being returned once the agent has been successfully dispatched there. In case the attack occurs, based on the detection of successful dispatch, the problem should be with the host where the agent has arrived. In terms of performance, since each WA has different starting time and ending time for the data-accessing task and the size of each offer will be small, the returned results will not lead to a bottleneck at A0 . 2.3.5. Replay attack In a malicious host, the replay attack may occur. Consider the following scenario, that a malicious Hi who has a PWA residing at it and it dispatched agent Aj to host Hj . After the normal process has been completed, Hi may replay the dispatch with a forged agent. However, when an agent is dispatched from Hi to Hj as a replay attack, the timestamp included in the signature from H0 cannot be tampered with. By verifying the signature, Hj can easily detect the replay attack and Hi will face the risk to be reported. Similarly, another type of replay attack is for a host, where a WA had earlier resided, to repeatedly counterfeit the WA and send messages to the agent A0 . But it can be easily detected by A0 by checking the signatures included in messages. 2.3.6. Collusion attack If in a normal sequence, host Ha should dispatch an agent to Hb . Assuming Ha and Hc are in a collusion tie, the agent is

dispatched to Hc . In this way Ha and Hc make an attempt to skip the visit to Hb who is their competitor and send their own offers instead. However Hc can hardly forge the signature by Hb that should be included in the message returned to A0 . In such a case, the counterfeited message can be detected when it is returned and this will cause the investigation against Hc and Ha . Since Hb will report that no such agent has ever been dispatched to it and Ha cannot show the correct dispatch record which should include the signature by Hb , the attack can be identi?ed. The attack can be successful only when Ha , Hb and Hc make a collusion attack sending a result from Hb encapsulating the price from Hc . However, in a healthy competitive environment, the probability is fairly low. Even if it can take place, the buying agents will visit Hb not Hc . If Hb cannot offer the product with the provided price, it will result in a commercial cheating, which is the same as a merchant’s giving abnormally low price and causing the abortion of the purchase. This will cause the deduction of the merchant’s credit standing and little agents will be dispatched later to such merchants.

3. Serial migration extension for parallel dispatch (PD-SM) In binary dispatch model, n WAs should be dispatched to visit n e-shops. This may overload the network traf?c. Since several e-shops to be visited may locate in the same intranet of a marketplace, if the number of these e-shops is very limited (e.g., 3 or 4), one agent can be dispatched to the marketplace to visit several e-shops one-by-one. If many e-shops within a marketplace should be visited, a few agents can be dispatched in parallel and each agent serially visits a set of e-shops. The number of e-shops to be visited by one agent can be determined by a threshold. This will help to reduce the inter-marketplace network load caused by a fully parallel dispatch and will not signi?cantly affect the whole ef?ciency. Figure 2 illustrates an example with 8 WAs visiting 16 hosts. Suppose the threshold for serial migration is 3, the secure route structure is described as follows.

Figure 2. Dispatch tree with 8 WAs for PD-SM+ 2.



Secure route structure (II). (1) For a PWA at CH,
r(CH) = PCH isPWA, ip(RH), rL (CH), rR (CH), SH0 H isPWA, ip(PH), ip(CH), ip(RH), rL (CH), rR (CH), t


(2) For a WA, assuming the threshold is 3 and the e-shop servers are H1 , H2 and H3 in sequence,
r(CH) = PCH isWA, ip(H1 ), MIG, SH0 H isWA, ip(CH),ip(H1 ), MIG, t , PH1 isWA, ip(H2 ), MIG, SH0 H isWA, ip(H1 ), ip(H2 ), MIG, t , PH2 isWA, ip(H3 ), MIG, SH0 H isWA, ip(H2 ), ip(H3 ), MIG, t , PH3 isWA, EoR, ip(H0 ), SH0 H isWA, ip(H3 ), ip(H0 ), EoR, t


In route structure (II), the route for a PWA is the same as route structure (I). For a WA, the route is a bit complicated, where MIG is the token meaning that the WA should migrate to the next host after completing the task at the current host and EoR is the token showing the end of the route. When a PWA has completed all its dispatch tasks, it will become a WA and migrate within a marketplace following the prede?ned sequence as H1 , H2 and H3 . When having obtained the information from H3 , a WA will send the whole results back to agent A0 at H0 . The message is as follows:
msg = PH0 Result(H3 ), ER(H2 ), SIGH0 (H3 ), SH3 H Result(H3 ), ER(H2 ), SIGH0 (H3 ), t3

, (3)

where ? ER(Hi ) is the encrypted result obtained at Hi ; ? SIGH0 (Hi ) denotes the signature generated by H0 , which is included in the route decrypted by Hi . Here it shows the identi?cation of the agent; ? ER(H2 ) = PH0 [Result(H2), ER(H1 ), SIGH0 (H2 ), SH2 (H(Result(H2 ), ER(H1 ), SIGH0 (H2 ), t2 ))]; ? and ER(H1 ) = PH0 [Result(H1), SIGH0 (H1 ), t3 , SH1 (H(Result(H1 ), SIGH0 (H1 ), t1 ))]. In message (3), the results are encrypted by the public key of H0 in a nested structure. This helps to prevent deletion attack. The signature of current agent is included in the message preventing forged results. And the signature generated by current host shows all are from the correct host. Figure 2 illustrates an example for PD-SM model with the threshold of 2, which is termed as PD-SM+ 2. 4. Robustness enhanced extension So far we have presented a security enhanced dispatch model for mobile agents and an extension combining parallel dis-

patch and serial migration. However, in terms of secure dispatch model, each PWA only knows the right child host RH where its right child agent is to be dispatched at a certain layer. As such, should the right host be unreachable, the right dispatch branch cannot be deployed and all the members grouped in this agent will thereby not be activated. A straightforward solution is for a PWA to have an alternative route for dispatching its right child agent so that if the prede?ned right child agent cannot be successfully dispatched due to some reasons from the destination host, the PWA can have another route for the right dispatch. In [7] Li proposed a robust model for serial migrating agents and the route robustness is enhanced by equally dividing a route, say {ip(H1), ip(H2 ), . . . , ip(Hn )}, into two parts, say {ip(H1 ), . . . , ip(Hi )} and {ip(Hi+1), . . . , ip(Hn )}. They are distributed to two agents A1 and A2 , respectively. A1 and A2 are in partner relationship. Each agent residing at any host en route knows the addresses of the next destination and an alternative host. But the latter is encrypted by the public key of its partner agent. In case the migration cannot be performed, the encrypted address will be sent to the partner agent for decrypting. With its assistance, the agent can continue its migration. The problem with the model is that since both A1 and A2 are dynamically migrating, when one needs the other’s assistance, locating each other will be costly for both time and system resources. Meanwhile, the model is serial so it is not ef?cient. Additionally, using the secret key of a dynamically migrating agent is not secure. But the idea of using the mutual assistance of two agents to enhance the robustness is good and can be easily used in our model, where the two ?rst PWAs (e.g., A1 and A9 in ?gure 1) in the left and right branches can do it better. Since they do not need to migrate, sending messages to them is fairly simple and fast. Encrypting and decrypting a route using the keys of the host where the ?rst PWA resides is more secure. If we were to provide one substitute route, the route structure in equation (1) can be extended as follows. Route structure (III). (1) For a PWA at current host CH,
r(CH) = PCH isPWA, ip(RH), rL (CH), rR (CH), rR (CH), SH0 H isPWA, ip(PH), ip(CH), ip(RH), rL (CH), rR (CH), rR (CH), t


where rR (CH) = PAPWA [ip(SH), r(SH), SH0(H(ip(SH), r(SH), t))] is the substitute route for the right branch of host CH, SH is the substitute host. (2) For a WA at CH,
r(CH) = PCH isWA, ip(PH), ip(H0 ), SH0 isWA, ip(PH), ip(CH), ip(H0 ), t . rR (CH) is encrypted by the public key of the ?rst PWA in another branch of the whole dispatch tree, which here is termed as Assistant PWA (APWA). For example, in ?gure 1, A1 is the ?rst PWA in left branch so it is the APWA for the right



Figure 3. Decrypting a substitute route.

branch following A9 . A9 is the APWA for the left branch following A1 . Now suppose A1 is the ?rst PWA in the left dispatch subtree. Am is the right one. If current host CH is the descendant of A1 , then rR (CH) is encrypted by the public key of Am , say PAm . Otherwise, if CH is in the right dispatch sub-tree from the root node, rR (CH) is encrypted by PA1 . If the dispatch failure occurs ACH is dispatching its right child agent ARH to right host RH, and ACH is in the left subtree, ACH should report it to Am attaching the substitute route rR (CH) (see ?gure 3):
msg = PHm ip(CH), ip(RH), rR(CH), SCH H ip(CH), ip(RH), rR (CH), t1



Figure 4. Examples of substitute routes.

where t1 is the time when message (1) is generated. There are two reasons for ACH to send a request to Am . One is that host RH has a temporary failure when ACH is trying to dispatch an agent there. Another reason is that host CH is malicious and attempts to know more addresses by sending a cheating request. However, the failure report will be con?rmed by Am before it responds to any decrypted routes. And the request is saved by Am for future investigation. In this way by route structure (III), a PWA will have a substitute route for the dispatch of its right child agent. Once the original dispatch is not successful, with the assistance of its APWA, it can have another destination to perform the right dispatch. When Am gets such a message, it will: Step 1. Detect whether RH is unreachable. If it is true, then go to step 2, otherwise go to step 3. Step 2. Am will decrypt rR (CH),
r = SHm rR (CH)

Step 3. If RH is in the correct state, Am will tell ACH about it and record the request in a database. Stop. In message (5), the second signature is generated by Hm and t2 is the corresponding timestamp; SH is the substitute host. What we should address is that the substitute host is originally included in the members for the right dispatch branch. Taking the dispatch tree in ?gure 4 as an example, if the dispatch failure occurs when A1 at host H1 is dispatching A17 to H17 , A1 can get a substitute route with the assistance PWA A33 at H33 . To generate the substitute route, choosing H18 to be the substitute host is better. By exchanging the positions of H17 and H18 as shown in ?gure 4(b), though H18 becomes the root of the branch with H17 to H32 , most sub-branches under H18 is kept unchanged. This is very important and can reduce the complexity to generate a new substitute route. Following the same idea, the second and the third substitute routes can be generated as shown in ?gures 4(c) and 4(d). If H18 is not reachable, H20 can be the second substitute. If H20 is not reachable either, H22 can be the new root for this branch and the positions of H20 and H22 are exchanged (see ?gure 4(d)). An originally unreachable host should be put to be a leaf node so that the failure of the second dispatch attempt can be made without increasing more load of the APWA for route decryption. For a detail discussion on generalizing the robust route structure for k substitute routes and k + 1 dispatch branches, see [16].

= ip(SH), r(SH), SH0 H (ip(SH), r(SH), t and send r to ACH through a message
msg = PCH ip(SH), r(SH), SH0 H ip(SH), r(SH), t , SHm H ip(SH), r(SH), SH0 H ip(SH), r(SH), t , t2






5. Complexity analysis In this section we present some analytical results of our models and compare them with two existing secure models, Westhoff’s model [18] and Li’s model [7]. Due to space constraint, we shall not present the proofs of the various results. We refer the readers to [16]. Westhoff’s model [18] adopted a fully serial migration providing secure route structure without any robustness mechanism. Suppose the visited hosts are H1 , H2 , . . . , Hn , the route is:
r(Hi ) = PHi ip(Hi+1 ), r(Hi+1 ), SH0 H ip(Hi ), ip(Hi+1 ),

before serial migration (m · 2H = n), t is the time for dispatching a PWA or a WA including the time for decryption, then the total dispatch and migration time with n WAs is T = (H + 1 + m) t. With regard to the complexity for generating routes, the two serial models and the secure binary dispatch model have different performances. Based on the nested secure structure, which helps to prevent route tampering or deleting attacks and detects them as early as possible, assuming that the time to encrypt a route of arbitrary-length is a constant, we have the following results on the complexity for generating routes. Theorem 4. Assuming that the time to encrypt a route is a constant, the time complexity for generating routes of Westhoff’s model is O(n). Theorem 5. In the secure binary dispatch model, the complexity for generating routes without substitute route is O(n). Table 1 summarizes and compares the features of the various models without any substitute route. Theorem 6. Assuming that the time to encrypt a route is a constant, the time complexity for generating a route with 1 substitute route in Li’s model is O(n). However, if a failed host is used for a second attempt in Li’s model, the complexity for generating routes will become extremely bad since the sequence of hosts in a substitute route has been changed and the route should be generated and encrypted again. Theorem 7. The time complexity for generating routes with 1 substitute routes of Li’s model making the 2nd attempt to the failed hosts is O(2n ). Theorem 8. In the secure binary dispatch model, the complexity for generating routes with 1 substitute route is O(n log2 n). Table 2 summarizes and compares the features of the various models with substitute routes.
Table 1 Comparison of models without substitute routes. Models Features Nested secure route Westhoff’s model Binary dispatch with secure routes PD-SM Yes Yes Yes Dispatch/ Migration complexity O(n) O(log2 n) O(log2 n + m) Route generating complexity O(n) O(n) O(n)


r(Hi+1 ), t


i < n),

r(Hn ) = PHn EoR, SH0 H ip(Hn?1 ), ip(Hn ), t


where SH0 is the secret key of home host H0 and EoR is the token meaning the end of the route. Obviously the migration complexity is O(n) if there are n hosts to be visited. Li’s model [7] mentioned in section 4 ensures both security and robustness. In Li’s model, as the addresses of n hosts are distributed to two agents, say {ip(H1 ), . . . , ip(Hm )} and {ip(Hm+1 ), . . . , ip(Hn )}, the nested route structure is: (ii)
r(Hi ) = PHi ip(Hi+1 ), r(Hi+1 ), r(Hi ) , SH0 H ip(Hi+1 ), r(Hi+1 ), r(Hi ) , t

where r(Hi ) = PAA [ip(Hi+2), r(Hi+2 ), r(Hi+2 ) , SH0 (ip(Hi+1 ), r(Hi+2 ), r(Hi+2 ) , t)] is the substitute route where Hi+2 is the new destination if Hi+1 is not reachable. PAA is the public key of the assistant agent. The whole migration time can be theoretically half of the ?rst model. However the time complexity is O(n). Theorem 1. Disregarding the time spent on local data access, the time complexity of migration of Westhoff’s model and Li’s model for visiting n hosts is O(n). In comparison, in our model the ef?ciency is greatly improved while the security and robustness are ensured in our model. With the binary dispatch model the dispatch complexity is O(log2 n). Theorem 2. If n (n 2) WAs are dispatched by binary dispatch model, h = log2 n (h 1) is an integer and the height of the dispatch tree, t is the time for dispatching a PWA or a WA, then the total dispatch time for n WAs is T = (h + 1) t. Corollary 1. When all n WAs are dispatched by binary dispatch model, the dispatch time is T = (log2 n + 1) t and the time complexity is O(log2 n). Theorem 3. If n (n 4) e-shops should be visited by PDSM model, m is the threshold for serial migration (n m), H (H 1) is an integer and the height of the dispatch tree



Table 2 Comparison of models with substitute routes. Models Nested secure route Robust route Dispatch/ Migration complexity Features Route Generating complexity with 1 substitute route O(n) or O(2n ) O(n log2 n) N/A

Route generating complexity with 3 substitute routes O(n) or O(4n ) N/A O(n log2 n)

Try failed hosts latter

Li’s model [7] Binary dispatch with 1 substitute route Binary dispatch with 4 branches and 3 substitute routes

Yes Yes Yes

Yes Yes Yes

O(n) O(log2 n) O(log2 n)

No Yes Yes

“N/A” means the model does not match corresponding feature. “No” means the model does not have corresponding feature.

6. Experiments In section 5, for simplicity, the analysis is based on the assumption that the encryption time of a message of any length is a constant. To further study the performance of the different models, we conducted some experiments on a cluster of PCs. These PCs are connected to a LAN with 10 Mbytes/s network cards PCs running Window NT, JDK, IBM Aglets 1.0.3 [1,6]. For route generations, the experiment is based on a PC of Pentium III 700 MHz CPU and 128 Mbytes RAM and the number of addresses is set up to 1024. For serial migration and binary dispatch models, the experiments are put on a cluster of PCs. Each PC has a Pentium 200 MMX CPU and 64 Mbytes RAM. The number of e-shops is set up to 64. All programs run on the top of the Tahiti servers from the ASDK [1,6] and JDK from Sun Microsystems [4]. Note that all encrypted routes adopt nested structure so that the performance variations will be totally from the differences in the route structures. To encrypt a route, we use the RSA algorithm [10] and the length of each key is 1024 bits. Before generating a signature, hash function MD5 [17] is used to generate a hash value with ?xed-length of 128 bytes. For the third experiment, the dispatched mobile agent has no task of local data-access. And since all PCs have the same con?guration, the performance differences are totally from the difference of serial migration and parallel dispatch. All results are illustrated in ?gures 5–10. Each result is the average of four independent executions. 6.1. Experiment 1: comparison of route generation of models without substitute routes In this experiment, we ?rst compare the route generation time of Westhoff’s model and our secure binary dispatch model. All results are shown in ?gure 5. When the number of addresses is fewer than 128, the 2 models deliver similar performances. When the number becomes 256 or more, the binary dispatch model begins to outperform the serial model. Theoretically, when there are n addresses, the binary dispatch model should do the encryption for 2n ? 2 times. For the serial model, it is n times only. The time complexity of

Figure 5. Route generation time for Westhoff’s model and binary dispatch model.

Figure 6. Comparison of route length of 2 models.

both is O(n). If the encryption time for a message is a constant, the route generation time of the binary dispatch model is obviously longer. Nevertheless, the encryption time varies with the length of the encrypted message. For the binary dispatch model, n times’ encryptions are spent on all leaf nodes in the dispatch tree where the length of each route is only about 200 bytes. Unfortunately, as shown in ?gure 6, for Westhoff’s model, each time after encryption, the route’s length is increased at least with a length of an IP address and a signature. So, the encryption time will gradually increase



Figure 7. Route generation time for 3 parallel dispatch models without substitute routes.

Figure 9. Comparison of the time for generating a route with 1 substitute route.

6.2. Experiment 2: comparison of route generation of models with one substitute route In this experiment, we compare the route generation time for models with one substitute route. For Li’s model, we implemented the case of skipping a failed host. The results shown in ?gure 9 illustrates that though the time complexities of the two models analyzed in section 5 are different (i.e., O(n) vs. O(n log2 n)), their performances are very close to each other when the number of addresses is not greater than 256. But when the there are 512 addresses, the binary dispatch model begins to outperform. When the address number is 1024, 2 routes are generated and each has 512 addresses. Herein the route generation time of Li’s model is too long. The reason is the same as we analyzed in experiment 1. 6.3. Experiment 3: comparison of serial migration models and binary dispatch models with the increase of the route length. When the number of addresses is large, the total encryption time will become very long. For example, when there are 512 addresses, the Westhoff’s model performs 512 encryptions. As we measure, it uses 284 seconds to complete the ?rst 256 encryptions and 2731 more seconds for the last 256 encryptions. The total time is 3015 seconds. For the binary dispatch model, it completes all encryptions in 101 seconds, and takes 37 seconds for 512 leaf nodes. But when generating the route with 1024 addresses, the program of the Westhoff’s model ran out of memory after the 771th address is added where the heap size is set up to 1200 Mbytes and it has reached the maximum. The results of PD-SM model are shown in ?gure 7. We observe that when the threshold is 2, PD-SM+ 2 delivers almost the same performance as the binary dispatch model. When the threshold is 4, the route generation time from PD-SM+ 4 is decreased. The reason can be found from ?gure 8, where we observe that the route of PD-SM+ model with threshold = 4 is shorter than other two cases. That explains why its route generation time is shorter. In this experiment, we tested up to 64 hosts to compare the migration/dispatch time of different models ignoring any robustness mechanisms. In the implementation, a mobile agent will not access any local data so that the measured time is spent for migration or dispatch only. The results are shown in ?gure 10 and table 3. When the number of visited hosts is 8, the performance differences are not signi?cant. With the increase of the number of hosts, the migration time of any serial migration model increases very fast. In comparison, the dispatch time for binary dispatch model or PD-SM model increases fairly slowly. The performances from PD-SM+ 2 and PD-SM+ 4 are fairly acceptable (see table 3). Moreover, the number of dispatched agents is different in the 3 parallel models. They are compared in table 4. Meanwhile, the migration time for Li’s model is always shorter than that of Westhoff’s model since in Li’s model, 2 mobile agents are dispatched and each only visits n/2 hosts. Nevertheless, its performance is not comparable to the parallel dispatch models. When having 64 hosts, the binary dispatch model can get 73.6% and 86% savings, respectively, in comparison to Li’s model and Westhoff’s model.

Figure 8. Comparison of route length of 3 models.



the power of 2, it will cause the changes of leaf nodes but the performance differences will be similar. For practical applications, mobile agents having tasks of the same type and having physically close destinations can be put in the same group encapsulated with pre-encrypted route structures. Acknowledgement This work is supported by the NSTB/MOE funded project on Strategic Program on Computer Security (R-252-000-015112/303).
Figure 10. Comparison of dispatch/migration time. Table 3 Dispatch/migration time in milliseconds for 5 models. Models 8 Westhoff’s model Li’s model Binary dispatch PD-SM+ 2 PD-SM+ 4 13279 9324 6467 6689 7313 Number of hosts 16 32 30323 14321 7254 7341 8124 48300 28321 9435 9897 10005

[1] http://www.trl.ibm.co.jp/aglets/ [2] CCITT, Recommendation X. 509-1989, The directory-authentication framework, Consultation Committee, International Telephone and Telegraph, International Telecommunication Union, Geneva (1989). [3] A. Corradi, R. Montanari and C. Stefanelli, Mobile agents in e-commerce applications, in: Proceedings of 19th IEEE International Conference on Distributed Computing Systems, Workshops on Electronic Commerce and Web-Based Applications, Austin, TX, USA, May 30–June 4 (1999) pp. 59–64. [4] http://java.sun.com/products/ [5] G. Karjoth, D.B. Lange and M. Oshima, A security model for aglets, IEEE Internet Computing (July/August 1997) 68–77. [6] D.B. Lange and M. Oshima, Programming and Deploying Java Mobile Agents with Aglets (Addison-Wesley, Reading, MA, 1998). [7] T. Li, C.K. Seng and K.Y. Lam, A secure route structure for information gathering, in: Proceedings of 2000 Paci?c Rim International Conference on AI (2000). [8] C. Panayionou, G. Samaras, E. Pitoura and P. Evripidou, Parallel computing using Java mobile agents, in: Proceedings of 25th EUROMICRO Conference, Milan, Italy, September 8–10, Vol. 2 (1999) pp. 430–437. [9] S. Papastavrou, G. Samaras and E. Pitoura, Mobile agents for World Wide Web distributed database access, IEEE Transactions on Knowledge and Data Engineering 12(5) (September/October 2000) 802–820. [10] R.L. Rivest, A. Shamir and L. Adleman, A method for obtaining digital signature and public key cryptosystems, Communications of the ACM 21(2) (1978) 120–126. [11] T.D. Rodrigo and A. Stanski, The evolving future of agent-based electronic commerce, in: Electronic Commerce: Opportunity and Challenges, eds. S.M. Rahman and M.S. Raisinghani (Idea Group, Hershey, PA, 2000) pp. 337–351. [12] L.M. Silva, V. Batista, P. Martins and G. Scares, Using mobile agents for parallel processing, in: Proceedings of International Symposium on Distributed Objects and Applications (DOA’99), Edinburgh, Scotland (September 1999) pp. 34–42. [13] V. Varadharajan, Security enhanced mobile agents, in: Proceedings of the 7th ACM Conference on Computer and Communications Security, Athens, Greece, November 1–4 (2000) pp. 200–209. [14] Y. Wang, K.L. Tan, J. Ren and X. Pang, An agent-mediated, secure and ef?cient Internet marketplace, in: Proceedings of the 4th International Conference on Electronic Commerce Research (ICECR-4), Dallas, TX, November 8–11 (2001) pp. 649–641. [15] Y. Wang, Dispatching multiple mobile agents in parallel for visiting e-shops, in: Proceedings of 3rd International Conference on Mobile Data Management (MDM2002), IEEE Computer Society Press, Singapore, January 8–11 (2002) pp. 61–68. [16] Y. Wang, K.L. Tan and X. Pang, Enabling the parallel dispatch of mobile agents with secure and robust routes, Unpublished manuscript available upon request from authors. [17] P. Wayner, Digital Copyright Protection (SP Professional, Boston, MA, 1997).

64 104190 52696 13158 13988 14565

Table 4 The number of dispatched mobile agents in 3 parallel models. Models 8 Binary dispatch PD-SM+ 2 PD-SM+ 4 8 4 2 16 16 8 4 Number of hosts 32 32 16 8 64 64 32 16 n n n/2 n/4

Of course, what should be pointed out is that the time for local tasks is not measured in this experiment. Otherwise, the response time for 2 serial models will become inferior. For the PD-SM model, if the threshold is small, the performance will not be worsened signi?cantly. 7. Conclusions In this paper we have proposed and discussed binary dispatch models of mobile agents with secure routes and robustness mechanisms. These models utilize the automation and autonomy of mobile agents and the corresponding code is simple. Besides the high ef?ciency from binary dispatch, the secure mechanism provides the capability to protect mobile agents from malicious hosts and vise versa. Meanwhile, the robustness mechanism enables the fault-tolerance without any loss on security. The experiments show that the binary dispatch models cannot only bene?t from route generation, but also can signi?cantly bene?t from the parallel dispatch and parallel execution of mobile agents. In this paper for simplicity we only present and discuss some typical cases of different models that the depth of each leave node is the same. When the number of WAs is not just



[18] D. Westhoff, M. Schneider, C. Unger and F. Kenderali, Methods for protecting a mobile agent’s route, in: Proceedings of the Second International Information Security Workshop (ISW’99), Lecture Notes in Computer Science, Vol. 1729 (Springer, Berlin, 1999) pp. 57–71.

University of Singapore. His research interests cover mobile agent, electronic commerce and computer security. E-mail: ywang@comp.nus.edu.sg

Yan Wang received his Bachelor Degree of engineering, Master Degree of engineering and Doctorate Degree of engineering on computer science and technology in 1988, 1991 and 1996, respectively, from Harbin Institute of Technology (HIT), China. He ever worked at the Department of Computer Science, City University of Hong Kong as a senior research assistant/associate in 1997 and 1999. He is currently a Research Fellow of the Department of Computer Science, School of Computing, National

Xiaolin Pang received her Bachelor Degree of engineering in computer science from Taiyuan University of Technology, China in 1997. She is now a Master student of the Department of Computer Science, School of Computing, National University of Singapore. E-mail: pangxiao@comp.nus.edu.sg