Searching for a black hole in arbitrary networks: optimal mobile agent protocols

ABSTRACT

Protecting agents from host attacks is a pressing security concern in networked environments supporting mobile agents. In this paper, we consider a black hole: a highly harmful host that disposes of visiting agents upon their arrival, leaving no observable trace of such a destruction. The task to identify the location of the harmful host is clearly dangerous for the searching agents. We study under what conditions and at what cost a team of autonomous asynchronous mobile agents can successfully accomplish this task; we are concerned with solutions that are generic (i.e., topology-independent). We study the size of the optimal solution (i.e., the minimum number of agents needed to locate the black hole), and the cost of the minimal solution (i.e., the number of moves performed by the agents executing a size-optimal solution protocol). We establish tight bounds on size and cost depending on the a priori knowledge the agents have about the network, and on the consistency of the local labellings. In particular, we prove that: with topological ignorance Δ + 1 agents are needed and suffice, and the cost is Θ(n²), where Δ is the maximal degree of a node and n is the number of the nodes in the network; with topological ignorance but in presence of sense of direction only two agents suffice and the cost is Θ(n²); and with complete topological knowledge only two agents suffice and the cost is Θ(n log n). All the upper-bound proofs are constructive.

REFERENCES

• 1: David M. Chess, Security Issues in Mobile Code Systems, Mobile Agents and Security, p.1-14, January 1998
• 2: Stefan Dobrev , Paola Flocchini , Giuseppe Prencipe , Nicola Santoro, Mobile Search for a Black Hole in an Anonymous Ring, Proceedings of the 15th International Conference on Distributed Computing, p.166-179, October 03-05, 2001
• 3: P. Flocchini, B. Mans, and N. Santoro. Sense of direction: definition, properties and classes. Networks, 32(3):165-180, 1998.
• 4: Paola Flocchini , Bernard Mans , Nicola Santoro, Sense of direction in distributed computing, Theoretical Computer Science, v.291 n.1, p.29-53, 4 January 2003 [doi>10.1016/S0304-3975(01)00395-4]
• 5: M. Greenberg, J. Byington, and D. G. Harper. Mobile agents and security. IEEE Commun. Mag., 36(7):76-85, 1998.
• 6: Fritz Hohl, Time Limited Blackbox Security: Protecting Mobile Agents From Malicious Hosts, Mobile Agents and Security, p.92-113, January 1998
• 7: Fritz Hohl, A Framework to Protect Mobile Agents by Using Reference States, Proceedings of the The 20th International Conference on Distributed Computing Systems ( ICDCS 2000), p.410, April 10-13, 2000
• 8: Nicholas R. Jennings, On agent-based software engineering, Artificial Intelligence, v.117 n.2, p.277-296, March 2000 [doi>10.1016/S0004-3702(99)00107-1]
• 9: S. Ng and K. Cheung. Protecting mobile agents against malicious hosts by intention spreading. In Proc. 1999 Int. Conf. on Parallel and Distributed Processing Techniques and Applications (PDPTA '99), pages 725-729, 1999.
• 10: R. Oppliger. Security issues related to mobile code and agent-based systems. Computer Communications, 22(12):1165 - 1170, 1999.
• 11: Tomas Sander , Christian F. Tschudin, Protecting Mobile Agents Against Malicious Hosts, Mobile Agents and Security, p.44-60, January 1998
• 12: Kristian Schelderup , Jon Ølnes, Mobile Agent Security - Issues and Directions, Proceedings of the 6th International Conference on Intelligence and Services in Networks: Paving the Way for an Open Service Market, p.155-167, April 27-29, 1999
• 13: J. Vitek and G. Castagna. Mobile computations and hostile hosts. In D. Tsichritzis, editor, Mobile Objects, pages 241-261. University of Geneva, 1999.

INDEX TERMS

Keywords:
black holes, distributed computing, mobile agents