Network Meta-Reasoning for Information Assurance in Mobile Agent Systems

1 Introduction

This paper develops a practical means of measuring informa­ tion assurance for mobile agent systems operating on wire­ less, ad hoc networks based on meta-reasoning [Dix eta!., 2000; Xuan et a!. , 2001] to improve the security of com­ munication. Figure 1 shows an agent system and its two distinct layers of communication: host-to-host and agent-to­ agent. Given the plethora of new techniques for identifYing network intruders, we study the compromised host problem: determining the appropriate response to an identified intruder. In the context of a mobile, multi-agent system operating on an ad hoc network [Forman & Zah01jan, 1994], it is not merely a simple matter of removing the compromised hosts and its agents. While keeping the compromised host can result in information disclosure, removal of the host can degrade or even sever the network. We develop a state description for an agent system and introduce a measure of information assur­ ance for the system in terms of the integrity of the messages delivered to the agents in a given network state. Agents have three responses to a compromised host: ignore the compro­ mised host; reroute around the compromised host using net­ work route redundancies; or remove the compromised host, by having the agents instruct their hosts to eliminate it from the network. These responses are shown in Figure 2.

2 Technical Formulation

A state description for a mobile agent network is defined in terms of sets of hosts (H) and agents (A). Given Hand A, we can define:

• Agent topology, TA, is a graph of the connections be­ tween agents in the agent layer: TA = (A, LA) where LA <;;; A X A.
• Host topology, TH, is a graph of the direct connections between hosts in the network layer: TH = (H, LH) where LH <;;; H x H.
• Host routing, R, is a set of sequences of hosts which describes the network routes used between hosts in the network layer: R = { Ri,j : hi, h1 E H} where ~. j is the current physical network route from host hi to host h1. If no route exists from hi to h1, then Ri ,j = 0.
• Agent location, TJ, is a function mapping an agent to the host on which it is physically located in a given state:

in routing. If a route changes, the time taken to transmit a message over that route may also change. A change in mes­ sage delivery time can negatively impact a decision proce­ dure. Moreover, a compromised host contains agents that may violate their expected behavior in a decision procedure. Both factors must be considered when evaluating a state N . We define two values that can be used to evaluate N with respect to each factor:

1. A message integrity rating, which relates successful messages received to failed messages.
2. A time rating, which is an estimate of optimality for the current network routes.

Measuring Message Assurance. If each agent is in com­ munication with all of the other agents, n; = (!AI - l77- 1 (h;)J)I77- 1 (h;)l is the total number of messages that the agents on host h; expect to receive from agents on other hosts per unit of time given stateN. Based on the current routes R, one can calculate the number of successful messages received on host h;, succ(h;). The message integrity rating for host h; . d SUCC(h ·) N . h IS compute as: m; = n; ' . ote, as m; mcreases, t e integrity of messages sent to host hi also increases. When all messages sent to hi are successful, m; = 1.0. When all messages sent to h; fail, m; = 0.0. The mean message in­ tegrity rating over the entire mobile agent network in state N L IHI . - . ffi i

Measuring Network Routing Efficiency. The trade off is between message integrity and the timeliness of message de­ livery. Network routing algorithms find sets of routes that minimize some value for all routes in a network. In general, routing algorithms use a weight function on each route and find the shortest, single source, paths to all vertices in TH. In this context, the function p represents the network rout­ ing algorithm which returns a set of shortest path routes for the set of hosts, given their current physical network topol­ ogy: R = p(H,LH,w), where w is the edge weight func­ tion. There are several schemes that can be used to weight routes in wireless, ad hoc networks [Royer & Toh, 1999], all of which can be approximated or bounded using a w that re­ turns a value proportional to the time required to transmit a message through the network. The units of time returned by w are used for relative comparison of network routes, which we normalize w to simplify computations: w: R--+ [1, I HI], where w(R;,j) = IHI signifies that the route from host h; to hj is non-existent and weight of the longest possible route is I HI- 1. Now we can define a time rating, t;, for the network h . L~:;,iz!i w(Rj ,i ) routes used by ost hi as. t; = IHI(IHI-I) Note, as t; increases, the routing efficiency to host h; decreases. When the routing efficiency is minimized (i.e., no connections ex­ ist) for a host h;, t; = 1.0. As the routing efficiency increases (i.e., shorter routes are used) for host h;, t; approaches 0.0. Hence, the mean time rating for the entire mobile agent netL IHI

Assurance for Whole Mobile Agent Network. A linear combination of message integrity rating and time rating de­ fines a utility function assessing a mobile agent network in stateN in terms of both assurance and routing efficiency:

a is a coefficient between 0 and 1 that determines the balance between assurance and network performance. If a = 1.0, only message integrity is considered; if a = 0.0, only time efficiency is considered. Note that V : N --+ [0.0, 1.0], where V(N) = 1.0 is the best possible result.

2.2 Operators on an Agent System Network

Using Equation 1, agents can decide how to operate on their network. Naturally, the ignore operator does nothing. The reroute operator generates a new set of network routes, us­ ing only safe routes wherever possible. If R' is the set of safest possible routes, the resulting mobile agent network N' = (TA ,TH,R 1 , 1J) is generated using the reroute oper­ ator on N (Figure 2(b)). Given the routing algorithm p and route weight function w, the following algorithm can be used to compute N':

The remove operator results in the complete removal of the compromised host from participation in the agent sys­ tem's underlying network. The new mobile agent network, N" = (T~, T~, R", 77), is the result of applying the removal operator on N and is generated by the following algorithm:

In order to select the operator resulting in the highest val­ ued agent system, consider the values V(N), V(N'), and V(N"). The highest of these values represents the best ac­ tion for the agent system.

3 Application: A Compromised Auction

The disclosure of bids to a compromised host can affect the intended, timely, outcome of an auction. A Vickrey auction is a sealed bid auction where the second highest bid is paid by the highest bidder [Vickrey, 1961]. All bidders maximize their payoff if they employ a truthful bidding strategy. Agents often use Vickrey auctions to acquire resources. Each agent submits its bid to an auctioneer host h1 (the sink)-but unless the physical host of a bidding agent is directly connected to h 1, the message containing the bid must pass through other hosts in the agent system. All agents operating under normal conditions have neither the intent nor the capability of reading bids that are routed through their physical hosts.

First, a compromised host, he can read all bids that are sent directly to or routed by means of he and potentially cor­ rupt the auction. In this case, instead of maximizing absolute payoff, the bidding agents on he maximize their payoff rel­ ative to other bidding agents. In this type of "antisocial bid­ ding" [Brandt & Weiss, 2001], assuming there are n bidding agents in the agent system, he most successful if it knows all bids b1 , b2, ... , bn placed by all of the other bidding agents. The worst case is when all physical hosts use routes that con­ tain he. In general this is not the case. Hence, if there are n' hosts that use routes containing he, the probability that the highest (or any) bid is disclosed to he is equal ton' jn.

Secondly, time is an issue: auctioneers are not willing to wait indefinitely for all bidders to respond. In any given de­ cision problem there is some threshold, T, such that, if a bid­ der is more than T hops from the auctioneer, its bid will not reach the auctioneer in time. Let Ui be the set of all hosts that communicate with host hi via a route longer than T hops: ui = {hj : hj E H (\ IRj,il > T} ui may contain hosts that use a route containing the compromised host. To adjust for this overlap, compute the set ci of hosts affected by the Table 1: The terms and result of V(N) using a = 0.5, the probability of compromised messages q;, and the probability of unreceived messages ~ for the result of each operator.

compromised host, but not by the required message delivery time: ci = {hj: hj E H (\he E Rj,i (\ IRj,i l::; T}

The disclosure of bids to a compromised host during this decision procedure is illustrated in Figure 3. Assume for tim­ ing that T = 3. In this example, the probability IC1I/n is representative of the effect of compromised messages, and the probability IU11/n is representative of the effect of time. As either probability increases, the value of the underlying mobile agent system should decrease.

Table 1 demonstrates how V(N) can be used to minimize the effect of a compromised host in a Vickrey auction. As the probability of compromised messages increases, the message integrity rating decreases. As the probability of unreceived messages increases, the time rating also increases. The oper­ ator yielding the highest value in this example is reroute.

4 Conclusions

This paper developed a utility-based model for agents to bal­ ance information assurance and network routing efficiency. We have discovered that there exists a natural tradeoff be­ tween information assurance and network routing efficiency for ad hoc mobile agent networks. Further, by empowering agents to decide for themselves how they communicate at the network level, one can increase the overall level of message integrity in an agent system. Our approach involves a novel exploitation of properties of ad hoc networks, enabling mo­ bile agents to automatically adapt to changes that affect the security of their communication and migration. The capabil­ ity to dynamically reason about the state of their network will provides new possibilities for secure computing.