Title: Protect the agents

Abstract

We propose a mechanism for constructing a market economy using mobile agents on the Internet.

keywords: agents, contracts, digital signatures, message digest

Motivation: A New Economic Frontier

The Internet has expanded to connect people all over the globe, and many merchants can now even sell their products and services to consumers via the Internet. For example, it is now possible to order a shirt or other items from the Dilbert Store, by just checking off on a form which items you wish to purchase, and entering a credit card number into a form. The company then sends you the purchased items.

The ability to purchase things over the Internet is not much different from purchasing via mail order or over the phone. Although the Internet does typically increase the speed at which you can make such transactions, and the amount of information you can obtain while investigating a purchase, the essential qualitative difference in the process is that you can now automate it with software agents. (An agent is one who acts on behalf of, and presumably with authority of, another.)

Mobile agents, programs that act to represent a user, allow one to extend their purchasing power. For example, it is possible to write an agent that could find and purchase the least expensive ticket to Washington DC given a user-supplied list of airlines. The user could further specify constraints to the solution, e.g., window seat leaving after 10:00 am.

One obstacle to mobile agents is the problem of ensuring that the agent will behave. Running arbitrary programs received from the Internet on one's own machine clearly demands some mechanism to prevent the agent from abusing machine resources. Techniques to address this issue of possible mobile agent misbehavior include:

  1. Using restricted languages to limit agent behavior (e.g., bpf, modula3, Java), one can confine the range of possible behavior to that which can be expressed in the given language.
  2. Use operating system constructs (e.g., VM, file permissions). IBM's VM operating system protected the system from the running program by presenting the executing program with a `virtual machine'. Rather than handing over control of the system to a program, the operating system would trap all actions and emulate them. Any program that misbehaved would only hurt its self. Similarly, restricting file permissions can prevent user programs from modifying system files inappropriately.
  3. Use sandboxing, or code analysis tools, to modify agents so they can not do damaging things.
However, these techniques will not protect a mobile agent from the servers on which they run. Indeed, a server could actually exploit these tools to deceive a mobile agent. In addition, there is nothing to prevent a host from modifying a mobile agent's code or its data. A pure software approach is not sufficient for an agent to detect whether it has been tampered with.

Possible solution

One possible solution to this problem is for the agent to establish a contract with the server before it moves to a site. The contract would provide the user (of the mobile agent) with a set of assurances, and specify actions to take when the user detects violations of an assurance (i.e., the contract).

We first define what we mean by contract: the collection of things upon which both parties agree. Similar to non-networked contract negotiations, a contract requires a description of the task, and iteration on the specifics until involved parties reach mutual agreement on what constitutes successful completion. A complete contract should protect both parties, and should include a way to handle situations beyond either parties control (e.g., loss of connectivity).

Contract Generation

A protocol could support the generation of a contract, where each party would append their modifications to the current contract draft, digitally sign it, and send it to the other party. The protocol could ensure that each round is recorded, thus enabling either party to perform consistency checks. Thus both parties would have assurance that no agreed upon section was modified later in the cycle. Figure 1 illustrates a possible contract-building iteration process. Each box in the figure represents a digitally signed object.


Fig 1. Building a contract: the process of two-party, coupled iteration

Similar to traditional non-Internetted contracts, if either party is not in compliance with the contract, they can take it up with a higher authority (e.g., bank, government, company).

Computation-based contracts

An example of a relatively simple contract is a CPU contract, which requires minimal information or semantic attention from the server. The agent itself is responsible for all changes to the data, and the server is merely supplying compute cycles. It is thus easy to determine compliance with the contract. If there is a dispute, both parties can run the agent again. During longer runs, the buyer might request checkpoints of the run, which the server could pass through a message digest routine to, e.g., prevent the buyer from receiving results without paying for the complete run. Passing the check point through a message digest routine also has the advantage of having a significantly smaller size compared to the original check point.

Fig 2. Check points

For example, a small company may have a compute-intensive project, e.g., extended rendering and movie animation, for which it needs more computational resources than it has in house. A computations contract would allow the company to out-source the task with an institution that sells CPU cycles. (The CPU-cycle-supplier would either have to have the rendering software to create accurate images, or be able to arrange with the customer to get it. The software licensing issue is beyond the scope of this draft.) The client could request that the server send periodic check points thus allowing the client to terminate the computation upon detection of a problem.

Brokers

One advantage of an electronic contract is that an appropriate task description could allow one to subdivide the contract and create subcontracts whose work could be distributed across multiple resources. For example, in the movie animation project, each individual image is complete by itself, and the client's agent might easily break the job up into several pieces and distribute it among different servers. In fact, some tasks descriptions might be such that the server itself could assume responsibility for task breaking the tasks into subtasks and distributing the computation to other servers.

Fig 3. Brokers

A new role/industry could emerge, that of a broker, or clearinghouse to aggregate, e.g., computational, resources together and sells the merged resource. Brokers might be servers that purchase CPU cycles from individual or companies willing to run jobs on their idle machines. In this scenario the users and providers of the cycles do not have to know about each other, reducing the number of servers an agent has to know. An additional feature is that since the broker would be buying cycles from many different sources, it could even replicate the sub-jobs on multiple machines to gain assurance that the computation is correct.

So using our movie animation project, only one agent would be sent to the broker. The broker would proceed to partition the contract into smaller subcontracts and send them to other servers. After all the subcontracts where completed the broker would merge the results and sent it to the client.

Information-based contracts

The notion of a broker, as an intermediary between the users and the resources we want to use, spawns several promising possibilities, of which CPU cycles are perhaps the most mundane. The vast quantity of data on the Internet continues to grow at a much faster speed than any human, or reasonable set of humans, can keep up with. Even the most popular, sophisticated search engines are now proving difficult to use since a keyword-based single pass filter results in still too much information for one to wade through within a useful time frame. Data mining poses similar problems. Taking advantage of third party agencies that either have filtered or will filter through a certain class of data for a fee, precisely the role of e.g., real estate agents, will add tremendous value to the Internet as a resources, and give the human users more time to do things other than deal with it.

Conclusion

Electronic contracts will be a central part of any form of automated commerce on the Internet. Without effective agents and brokers to flexibly execute transaction details, Internet commerce will be limited to merely awkward transplants of traditional non-networked mechanisms.

Bibliography

1. The Role of Brokers in Electronic Commerce, Paul Resnick. http://ccs.mit.edu/paulproj.html
2. The Berkeley Now Project http://now.cs.berkeley.edu/
3. Bruce Schneier, "Applied Cryptography: Protocols, Algorithms, and Source Code in C"
okumoto@cs.ucsd.edu