Siarhei Kuryla
email: s.kuryla@jacobs-university.de

Jürgen Schönwälder
email: j.schoenwaelder@jacobs-university.de

Evaluation of the Resource Requirements of SNMP Agents on Constrained Devices

Keywords: SNMP, 6LoWPAN, Contiki, Internet of Things

Constrained devices equipped with a microcontroller and a low-power low-bitrate wireless interface are becoming part of the Internet. We investigate whether the monitoring and configuration of such constrained devices can be performed by adapting the Simple Network Management Protocol (SNMP) to the capabilities of these devices. To this end, we have implemented an SNMP agent under the Contiki operating system. We provide an analysis of its resource requirements and its runtime behaviour on an 8-bit AVR Raven platform.

Introduction

The Simple Network Management Protocol (SNMP) [START_REF] Case | Introduction and Applicability Statements for Internet Standard Management Framework[END_REF] is widely deployed to monitor, control, and sometimes also configure network elements. Even though the SNMP technology is well documented and well understood, it remains unclear what the exact resource requirements are of running SNMP on constrained devices, such as an 8-bit microcontroller with 16 kB of RAM connected to the Internet via an IEEE 802.15.4 transceiver. The origins of SNMP date back to the late 1980s when computers had much less resources compared to what we are used to today. In fact, one of the stated goals was that "the impact of adding network management to managed nodes must be minimal, reflecting a lowest common denominator" [START_REF] Rose | The Simple Book -An Introduction to Management of TCP/IP based Internets[END_REF]. From this historic perspective, SNMP seems to be a reasonable fit for managing today's constrained devices. However, it must be noted that SNMP did evolve during the 1990s and in particular security mechanisms present in SNMP version 3 (SNMPv3) add significant complexity, increasing the code size and impacting runtime performance. Hence, we were approached with question such as the following:

-What are the resource requirements of a minimal SNMPv3 implementation running on constrained devices? -Which parts of an SNMP protocol engine are most expensive? -What is the cost of adding instrumentation (additional MIB objects)? -What is the runtime behaviour of SNMP over an IPv6 link using an IEEE 802.15.4 radio and the 6LoWPAN adaptation layer? The answers to these questions are crucial in order to understand whether it is feasible to run multiple protocols concurrently on constrained devices providing end-to-end interoperability with deployed systems or whether it is necessary to adopt architectures, where interoperability with deployed systems is achieved via gateways translating between standard Internet protocols and a single protocol (e.g., CoAP [START_REF] Shelby | Constrained Application Protocol (CoAP)[END_REF]) interfacing constrained devices.

The rest of the paper is structured as follows. We first discuss some architectural options for using SNMP in constrained networks in Section 2 before we review related work in Section 3. The design choices behind our SNMP implementation running on the Contiki [START_REF] Dunkels | Contiki -A Lightweight and Flexible Operating System for Tiny Networked Sensors[END_REF] operating system are summarized in Section 4. In Section 5, we describe our experimental setup in. We present an analysis of the memory requirements in Section 6, which is followed by a discussion of the observed latency in Section 7. We conclude the paper in Section 8.

Architectural Considerations

Low-Power Wireless Personal Area Networks (LoWPANs) typically consist of a (potentially large) number of constrained devices embedded into everyday objects. Unlike conventional networks, nodes in such networks should need minimal configuration, they should preferably work "out of the box", they should be easy to bootstrap, and they should be largely self-healing [START_REF] Kushalnagar | IPv6 over Low-Power Wireless Personal Area Networks (6LoWPANs): Overview, Assumptions, Problem Statement, and Goals[END_REF]. However, even the best automated mechanisms may fail and require explicit management once in a while. As such, a certain amount of explicit management can never be completely removed. Since the goal of IPv6 over LoWPANs (6LoWPAN) is to reuse existing protocols as much as possible, it makes sense to look at the question how SNMP can be used to manage 6LoWPAN networks consisting of constrained devices. Figure 1 outlines four architectural options for the common scenario where a network management system residing in the normal Internet manages constrained devices connected via a 6LoWPAN network.

Figure 1(a) assumes direct end-to-end SNMP communication. This option provides straight forward access to individual 6LoWPAN nodes. Reuse of existing deployed SNMP-based tools is easy and end-to-end security can be provided. The downsides of this option are related to message sizes and fragmentation issues, the requirement to embed a full SNMP engine into constrained devices, and the trap-directed polling nature of SNMP if energy consumption is a concern.

By utilizing an SNMP proxy (see Figure 1(b)), it is possible to optimize the transport of SNMP messages on the 6LoWPAN network, e.g., by using an alternate encoding or by using different security mechanisms. Since SNMP proxies are well defined in the SNMP specifications, management applications supporting SNMP proxies should need no modifications. Note that this approach still requires an SNMP agent on the constrained devices and that it does not overcome the trap-directed polling nature of SNMP.

Figure 1(c) outlines the usage of SNMP subagent technology where a single SNMP agent, typically running on an edge router, provides access to management information, utilizing a special purpose subagent protocol to interact with subagents residing on constrained devices. By tailoring the subagent protocol to the constraints of the link and the devices, it is possible to improve efficiency in the 6LoWPAN network and some amount of caching of data in the SNMP agent becomes feasible. However, this approach is not transparent to the management system since management applications need to address management information by using specific SNMP contexts. The fact that SNMP security ends at the SNMP agent residing at the edge router may be considered a feature or a problem, depending on the deployment scenario. The subagent option only has a clear advantage if the implementation costs of subagents is significantly lower than the costs for implementing an SNMP agent.

Finally, Figure 1(d) develops the subagent approach further by introducing a new protocol enabling data fusion in the 6LoWPAN network, e.g., in-network data aggregation. This approach requires not only new protocols, but also new management applications that are able to properly address management information and that understand the semantics of aggregated management data. On the other hand, communication in the 6LoWPAN network can be optimized and in particular tree-like routing structures can be exploited by aggregating data as it travels towards the edge router.

Related Work

During the past decade, a large number of papers discussing various performance aspects of SNMP have been published [START_REF] Andrey | Survey of SNMP Performance Analysis Studies[END_REF]. The majority of these papers assume high bandwidth network links and PC-like end devices. In this section, we focus solely on recent work dealing with 6LoWPAN networks and constrained devices.

In 2008, Hamid Mukhtar et al. [START_REF] Mukhtar | LNMP -Management architecture for IPv6 based low-power Wireless Personal Area Networks (6LoWPAN)[END_REF] proposed a LoWPAN Network Management Protocol (LNMP). Their approach aims at a reduction of communication cost in order to increase the network lifetime and to avoid congestion. In the proposed architecture, SNMP is supported on the native IPv6 network side only and a 6LoWPAN gateway acts as a subagent proxy, translating between the SNMP protocol and the protocol used on the 6LoWPAN network. Their work therefore follows the subagent model shown in Figure 1(c). Whenever an SNMP request arrives at the gateway, it is translated from SNMP to a simplified query format. The gateway sends a query (via UDP) that contains identifiers of the objects to be retrieved from the agent residing on the destination device. Similarly, when a reply from the device arrives at the gateway, it is translated back into the SNMP protocol format and an SNMP response packet is sent back to the SNMP engine that requested the object. The gateway is also responsible for responding to requests for objects whose values are constant for the whole network. The proposed LNMP protocol was implemented for the Atmel ATmega 128L microcontroller. Unfortunately, the query protocol between the gateway is not further detailed and no details are given concerning the code size or the memory requirements. Furthermore, the proposal appears to be incomplete since protocol security has not been considered nor has the addressing through SNMP contexts and the OID mapping been fully worked out.

Haksoo Choi et al. describe two modifications of SNMP in order to optimize SNMP for resource-constrained low-power and low data-rate wireless networks [START_REF] Choi | 6LoWPAN-SNMP: Simple Network Management Protocol for 6LoWPAN[END_REF]. The first change is the introduction of compressed SNMPv1 and SNMPv2c message headers and the usage of SNMP delta compression [START_REF] Schönwälder | SNMP Payload Compression[END_REF]. The second modification is the introduction of new protocol operations to push management information periodically from an SNMP agent towards an SNMP manager and the usage of UDP multicasts. In order to interface existing SNMP applications with their extended version of SNMP, they introduce an SNMP proxy that performs the necessary translations. From an architectural viewpoint, this work follows the proxy model shown in Figure 1(b). The work by Haksoo Choi et al. has two major limitations: (i) The work is limited to SNMPv1 and SNMPv2c and does not consider protocol security. In fact, the elimination of community strings on the 6LoWPAN network causes SNMP agents to respond to any request. (ii) The push mechanism only works for non-dynamic MIB objects since it relies on Getoperations. Periodic retrieval of data in dynamically changing tables is thus not optimized. Multicasting has the same limitations and becomes rather complex if protocol security mechanisms would be considered. The modified SNMP protocol was implemented using the TinyOS operating system [START_REF] Gay | The nesC Language: A Holistic Approach to Networked Embedded Systems[END_REF] on the Tmote Sky platform featuring the 16-bit TI MSP430 microcontroller with 10 kB of RAM and 48 kB of flash memory.

Implementation

Our Contiki SNMP implementation supports the SNMPv1 and SNMPv2 message processing models and the Get, GetNext and Set protocol operations. The USM security model has been implemented. It supports the HMAC-MD5-96 authentication and CFB128-AES-128 symmetric encryption protocols. The standard specifies that SNMP entities must accept messages up to at least 484 bytes in size, which is the maximum message size supported by our implementation.

One of the goals of our implementation is memory efficiency. However, whenever a choice had to be made between easily readable and maintainable source code and memory efficient but hard to understand programming constructs, we gave preference to the readable code. Due to the small amount of available RAM memory, necessary data structures were optimized and designed very carefully. Since the amount of ROM memory provided by the hardware platform is significantly larger than the amount of RAM, ROM memory has been preferred for storing read-only data. This not only enables a memory efficient representation of OID values, it also allows to refer to the OID of a varbind by pointing inside the received packet, thus reducing the need for runtime memory allocations.

MIB objects are internally represented by instances of the mib object t structure shown in Figure 3. The attrs member specifies the attributes of the object. The varbind member holds the OID of the object and its value. The get fnc ptr and set fnc ptr members are pointers to the user-defined getter and setter functions respectively. In case of enabled tabular objects, two additional bytes are required for the get next oid fnc ptr pointer for every managed object. Tabular objects are an optional feature and they can be disabled by changing the value of the ENABLE MIB TABLE macro definition.

The OID of a managed object is an array of bytes which does not change its value over time. By default, such arrays are handled as all other initialized variables: they occupy RAM and they occupy the same amount of flash ROM so they can be initialized to the actual value by startup code. This is a waste of RAM, which is the most critical resource of today's constrained devices. Of course, such data can be moved to flash ROM. However, to access the data stored in the flash ROM special functions have to be used, which results in additional complexity. The implementation allows to store OIDs either in RAM or flash ROM. This can be defined at compile time, by switching the value of the ENABLE PROGMEM macro definition between 0 and 1. Our SNMP implementation supports two ways to organize the storage of managed objects by using either an array or a linked list. In the first case, the number of objects has to be predefined at compile time by using the MIB SIZE macro definition, otherwise a linked list is used. In the latter case, every managed object requires two extra bytes for the next ptr member.

Several objects of the SNMPv2-MIB [START_REF] Presuhn | Version 2 of the Protocol Operations for the Simple Network Management Protocol (SNMP)[END_REF], IF-MIB [START_REF] Mccloghrie | The Interfaces Group MIB[END_REF] and ENTITY-SENSOR-MIB [START_REF] Bierman | Entity Sensor Management Information Base[END_REF] have been implemented. The SNMPv2-MIB defines managed objects describing the identity and the capabilities of an SNMP entity. The IF-MIB provides access to information related to network interfaces. It exposes counters of packets received on and transmitted out an interface. In order to obtain such statistical data, the Contiki radio driver has been instrumented. The managed objects of the ENTITY-SENSOR-MIB provide access to physical sensors. The readings of the temperature sensor can be obtained via the objects of this module.

Hardware Platform and Experimental Setup

The AVR Raven board includes two microcontrollers (MCUs), a radio transceiver chip and an LCD display. The ATmega1284PV MCU runs the communication while the LCD display is driven by the ATmega3290PV. The wireless communication is enabled by the AT86RF230 transceiver. Both the ATmega1284PV and the ATmega3290PV are modified Harvard architecture 8-bit RISC single chip MCUs. The ATmega1284PV runs at 20 MHz and has 16 kB of SRAM, 128 kB of flash program memory and 4 kB of EEPROM. It embeds two 16-bit timers, two 8-bit timers and one real time counter. The ATmega3290PV runs at 16 MHz and has 2 kB of SRAM, 32 kB of flash memory and 1 kB of EEPROM. The AT86RF230 is a 2.4 GHz radio transceiver targeted for IEEE 802.15.4 and 6LoWPAN applications. It supports automatic frame acknowledgement and retransmission, automatic CSMA-CA and data transfer speeds of up to 250 kbps.

The network setup used consists of a PC equipped with an 802.15.4 interface connected via the USB bus. The AVR RZUSBstick, a USB stick with a 2.4 GHz IEEE 802.15.4 transceiver, is used to provide the PC with an 802.15.4 interface. The software running on the MCU on the USB stick is doing the 6LoWPAN adaptation and hence no software changes are needed on the PC. The Contiki SNMP implementation has been tested for interoperability with the snmpget, snmpgetnext, snmpset and snmpwalk applications from the Net-SNMP1 suite. All measurements reported in this paper were made with Contiki 2.4 using the IPHC header compression mechanism.

Memory and Code Footprint

Due to the limited memory resources of constrained devices, the RAM and flash ROM used by the agent are important parameters that have to be evaluated. However, RAM usage is hard to measure because of the variable size of the stack and the heap used for dynamic memory allocation. In this section, we present memory usage estimations obtained by using three different approaches.

Flash ROM and Static Memory Usage

In the first step, the avr-size utility was employed to determine the flash ROM and static memory usage. We are interested in measuring the memory used only by the agent and not by the whole program that also includes the Contiki operating system. To achieve this, we first compile the source code of Contiki with the agent and measure the size of the output object file using the avr-size utility. Then, the same procedure is repeated for Contiki without the agent. The total memory used by the agent is obtained by a simple subtraction. The full implementation uses 31220 bytes of ROM, which is around 24% of the available ROM on the targeted platform, and 235 bytes of statically allocated RAM. In case SNMPv1 is only enabled, the agent uses 8860 bytes of ROM (about 7% of available ROM) and 43 bytes of statically allocated RAM. In a similar way, we measured the code and memory footprint of each module of the agent. Table 1 shows the detailed breakdown of the measurements.

As can be seen from the table, the cryptographic primitives occupy a significant amount of flash ROM. The AES and MD5 implementations constitute around 31% and 33% respectively of the agent code size. Almost half of the ROM occupied by the AES implementation is used to store constants. The MD5 implementation intensively uses macro definitions for transformations, which results in the large code size. Using functions instead of macros could reduce the code size, but would negatively impact the performance. It is worth to mention that the cryptographic primitives were ported from the OpenSSL library and that they are not optimized for the instruction set of the MCU.

The USM security model occupies almost half of the agent's statically allocated RAM. This RAM is mostly used to store localized keys and OIDs of the error indication counters.

Stack Usage

An experimental approach has been taken to estimate the stack size used by the agent while processing a request. Upon receipt of an incoming SNMP message, the memory region allocated to the program stack is filled with a specific bit pattern. When the processing has been finished, the stack is examined to see how much of it is overwritten. Table 2 presents the maximum stack size observed during experiments for different versions of SNMP and different selected security levels. Most of the stack is occupied by the response message buffer of 484 bytes. The SNMPv1 and SNMPv3 protocol versions with the noAuthNoPriv security level use approximately the same stack size, which constitutes around 4% of the available RAM. When authentication and privacy are enabled, the stack grows up to 1144 bytes, which is about 7% of RAM on the targeted platform.

Heap Usage

Memory for the data structures used to store the fields of an SNMP message (see Section 4) is allocated from the heap using the malloc() function. Table 3(a) provides a memory estimation for the message t structure.

Each variable binding is stored in a linked list using an instance of the varbind list item t structure. In addition to the memory calculation shown in Table 3(c), a variable binding uses 4 additional bytes for an instance of the ptr t structure, which points to the OID stored in the message buffer. The overall memory utilized to store an SNMPv1 message with N variable bindings is given by the formula 13 + N (9 + 4) = 13(N + 1). The SNMP message size is limited in the implementation to 484 bytes. Each variable binding encoded in the BER format requires at least 7 bytes, therefore, in the worst (albeit unrealistic) case an SNMPv1 message may carry 484/7 = 69 variable bindings, which would require 13(69 + 1) = 910 bytes of the heap to store such a message.

Managed Objects

As discussed in Section 4, each managed object is stored in memory as an instance of the mib object t structure. Table 3(b) presents a memory estimation for the members of this structure. A managed object uses additional 4 + L bytes for the OID, where L is the length in bytes of the OID encoded in the BER format. In case a managed object is of a string-based type, S extra bytes are required to store its value, where S is the length of the value. The total RAM usage for a managed object is given by the formula 16 + (4 + L) + S. Using flash ROM to store OIDs allows to save 4+L bytes of RAM for every managed object. In this case, the formula changes to 16 + S, which would require 1600 bytes of RAM for 100 managed objects of an integer-based type.

Response Latency

A simple udp-echo application has been developed for Contiki, which allows to obtain a round-trip time estimation for a UDP datagram of a certain size. provides some experimental results obtained using udp-echo. The results reveal that the transmission time of an 802.15.4 frame depends significantly on the amount of data being sent. For example, the difference between the round-trip time for datagrams with a payload of 1 byte and 90 bytes, both of which fit into one 802.15.4 frame, is around 8 ms. The delay is caused by the low speed of the radio transceiver. When sending a UDP packet with a 91 byte payload, 6LoWPAN fragmentation is used and, as expected, we observe an abrupt increase in the round-trip time compared to the 90 byte payload packet.

In order to estimate the SNMP request processing time taken by the agent, the request-response latency for individual messages was measured at the gateway by noting the delay between sending of the message and receiving of the response. In addition to the actual processing time, the measured delay also includes the time to transmit messages over the air between the gateway and the agent. If a message does not fit into a single 802.15.4 frame, the 6LoW-PAN fragmentation takes place, which causes additional overhead as explained above. The SNMP request processing time can be found as the difference between the the SNMP request-response latency and the round-trip time estimated with udp-echo for datagrams with the same payload length.

Table 5 and Figure 4(a) present latency measurements for SNMPv1 and SN-MPv3 with three different security levels. All measurements were obtained for requests with one variable binding referring to the same MIB object. The first observation is that the time spent in the SNMP request processing is small relative to that spent in data transfer for SNMPv1 and SNMPv3 in the noAuthNoPriv security level. The SNMP processing constitutes only around 6-7% of the total latency. As expected, the usage of the authentication protocol results in a significant increase of this metric. The results also reveal that encryption does not have that much impact on the processing time as the authentication does. It is important to mention that the measurements for SNMPv3 do not include the discovery procedure, which would result in an additional message exchange.

Figure 4(b) shows changes in the processing time by varying the number of variable bindings in a request. These measurements were accomplished for the SNMPv1 protocol and the Get operation. The processing time varies from 2 to 19 ms, which is not significant when compared to the transfer time. Even though the object lookup time depends on its position in the MIB, for this targeted platform, it is unlikely that the MIB will contain that many objects to change the results considerably.

Conclusions

An implementation of the Simple Network Management Protocol for resource constrained devices under the Contiki embedded operating system has been presented. The implementation is modular and extensible by design. It supports the Get, GetNext and Set operations, the SNMPv1 and SNMPv3 message processing models and the User-based Security Model (with the HMAC-MD5-96 authentication and the CFB128-AES-128 symmetric encryption protocols). The implementation provides an interface to define and configure accessible managed objects. A couple of the existing MIB modules have been implemented as part of the agent. The evaluation of the implementation has been carried out on the AVR Raven hardware platform. The experimental results reveal that the request processing time for SNMPv1 and SNMPv3 with the noAuthNoPriv security level is relatively small compared to the transfer time. Using the authentication protocol results in a significant increase of this metric, while the encryption protocol does not have that much impact on it. The RAM and flash ROM usage has been estimated by using three different approaches.

Possible further work would be to implement the GetBulk operation, notifications (Trap and Inform), and the SNMPv2c message processing model. It is also possible to use this platform to develop and prototype additional MIB objects for 6LoWPAN networks and related protocols.

Fig. 1 .

 1 Fig. 1. Architectural options for using SNMP in 6LoWPAN networks

Fig. 2 .

 2 Fig. 2. Key data structures representing SNMP messages

Fig. 3 .

 3 Fig. 3. MIB data structures representing MIB objects

  Time taken for transferring and processing an SNMP request with different message processing models and security levels Time spent in transferring and processing SNMPv1 requests and responses as a function of the number of variable bindings in a request

Table 1 .

 1 Flash ROM and static RAM memory usage of the agent (bytes)

	Module	Flash ROM RAM (static)
	snmpd.c	172	2
	dispatch.c	1076	26
	msg-proc-v1.c	634	6
	msg-proc-v3.c	1184	30
	cmd-responder.c	302	0
	mib.c	1996	6
	ber.c	4264	3
	usm.c	1160	122
	aes cfb.c	9752	40
	md5.c	10264	0
	utils.c	416	0

Table 2 .

 2 Maximum runtime stack size usage (bytes)

	Version Security level Max. stack size
	v1	-	688
	v3 noAuthNoPriv	708
	v3	authNoPriv	1140
	v3	authPriv	1144

Table 3 .

 3 Memory usage of key data structures

	(a) Memory estimation for the	(b) Memory estimation for the
	message t structure (13 bytes)	mib object t structure (16 bytes)
	Member	Size (bytes)	Member	Size (bytes)
	version	1	attrs	1
	pdu.request type	1	get fnc ptr	2
	pdu.response type	1	set fnc ptr	2
	pdu.request id	4	get next oid fnc ptr	2
	pdu.error status	1	next ptr	2
	pdu.error index	1	varbind.oid ptr	2
	pdu.varbind first ptr	2	varbind.value type	1
	pdu.varbind index	2	varbind.value	4
	(c) Memory estimation for a vari-
	able binding (9 bytes)
		Member	Size (bytes)
		next ptr	2
		varbind.oid ptr	2
		varbind.value type	1
		varbind.value	4

Table 4

 4

Table 4 .

 4 Round-trip time (RTT) measured with udp-echo

	Payload (bytes) 802.15.4 frames RTT (ms) Variance
	1	1	30.75	2.07
	90	1	38.87	6.58
	91	2	49.90	6.54
	175	2	58.93	6.63

Table 5 .

 5 Experimental results obtained by measuring the response latency (presented in the latency and variance columns) for SNMP requests. The round-trip time (RTT) is estimated using udp-echo. The last column is the processing time taken by the agent.

	All time measurements are given in milliseconds
	Version Operation Security level Latency Variance RTT	∆
	v1	Get	-	37.05	5.69	34.70 2.35
	v1	GetNext	-	36.98	6.58	34.70 2.28
	v1	Set	-	37.14	4.39	34.70 2.44
	v3	Get	noAuthNoPriv 56.64	4.05	52.62 4.02
	v3	GetNext noAuthNoPriv 56.58	2.72	52.62 3.96
	v3	Set	noAuthNoPriv 56.78	3.00	52.62 4.16
	v3	Get	authNoPriv	91.41	3.45	53.02 38.39
	v3	GetNext	authNoPriv	91.95	3.75	53.02 38.93
	v3	Set	authNoPriv	92.41	3.22	53.02 39.39
	v3	Get	authPriv	105.70	5.38	55.03 50.67
	v3	GetNext	authPriv	106.46	2.59	55.03 51.43
	v3	Set	authPriv	106.73	3.59	55.03 51.70

http://www.net-snmp.org/


Fei Peng

Apostolos Malatras

Optimising P2P Overlays for Pervasive Environments

In this paper we propose a topology optimisation algorithm for multi-layer P2P overlays on top of pervasive computing environments based on ant algorithms for the distributed network-wide collection of information. Our goal is to construct a robust and responsive overlay with low overhead so that it suits the highly dynamic and heterogeneous characteristics of pervasive environments.

Introduction

Pervasive computing environments are built over highly dynamic heterogeneous networks. Moreover, diversity exists in all aspects of such environments, including computing performance, network connections, mobility, etc. In order to reduce the perceived complexity of the underlying network, P2P overlays are usually adopted by large-scale network applications for resource discovery and network management [START_REF] Lua | A survey and comparison of peer-to-peer overlay network schemes[END_REF]. However, the robustness of P2P overlays can be adversely affected under dynamic conditions. Existing works have made attempts to optimise overlay topologies in different ways, e.g. by considering superpeer architectures [START_REF] Snyder | Myconet: A fungi-inspired model for superpeer-based peer-to-peer overlay topologies[END_REF] or self-organised approaches [START_REF] Brocco | Bounded diameter overlay construction: A self organized approach[END_REF] inspired by sophisticated and robust solutions found in nature. Nonetheless, these approaches consider environments with low dynamicity.

The responsiveness and overhead traffic of P2P overlays are critical concerns in pervasive computing. We propose a topology optimisation algorithm called X-Ant that is based on the theory of Ant Colony Optimisation (ACO) [START_REF] Dorigo | Ant colony optimization[END_REF]. By developing different families of artificial ants with unique features, network information can be collected rapidly with low overhead traffic, hence supporting responsive overlay topology optimisation over dynamic underlying networks. Moreover, considering the wide range of information collected by ants, overlay layers with different links of diverse quality features can be simultaneously maintained, therefore increasing the overall robustness. A similar approach was used by the CAN [START_REF] Ratnasamy | A scalable contentaddressable network[END_REF] overlay on top of a low dynamicity underlying network.

The rest of this paper is as follows. Section 2 presents the research problem by describing the goal of this project and the proposed methodology. In section 3 we discuss our proposed X-Ant algorithm by describing its multi-layer overlay design, the ant families used for network parameter collection, and the corresponding topology optimisation. Section 4 concludes this paper by presenting our current work as well as giving insight to future plans.

Our goal is to promote the responsiveness, efficiency and robustness of P2P overlay networks built on top of pervasive environments by employing bio-inspired methods. Although no special restriction is imposed on the type of applications, those for semi-public urban spaces, supporting socialization by enabling people to meet, work, learn and have fun, will be considered with high priority.

Our research is based on the theory of ACO, which has shown fruitful outcomes utilising artificial ants to optimise overlays, e.g. the BlatAnt algorithm [START_REF] Brocco | Bounded diameter overlay construction: A self organized approach[END_REF] that effectively bounds the diameter of grid overlays. However, the characteristics of our considered underlying networks are essentially different from grids in that the dynamicity and device heterogeneity are much higher. To address these unique features, we first aim at reducing the overhead traffic by creating new ant families and new types of pheromones to optimise information collection. This information will then be used to restructure and optimise overlay topology. Additionally, maintaining a multi-layer overlay composed of diverse types of virtual links according to different quality criteria, complemented by an adaptive layer switching mechanism, are expected to increase the overall overlay robustness.

X-Ant Algorithm

Multi-layer Overlay

To tackle the multifold requirements of different pervasive applications, we propose an overlay structure composed of different layers each of which being optimised in terms of different network parameters, such as bandwidth, latency, packet loss rate, link type (wired or wireless), etc.

According to the requirements from pervasive applications, these layers can be maintained with identical or near identical priority so that all of them can simultaneously serve different applications' needs. Alternatively, as illustrated in Fig. 1, a selected layer can be given the highest priority (active), while other layers are maintained in the background (standby). The latter mode generates less overhead traffic, making it particularly suitable for networks with restrained bandwidth. An advantage shared by both modes of operation is that the topology of one layer is not likely to overlap with another, thus increasing the overall robustness by means of available backup paths for recovery.

Layer switching is triggered by applications. Whenever an overlay optimised for a different parameter is needed, the corresponding standby layer will become the active one. Furthermore, standby layers also serve as backup layers. In case of link disconnections in the active layer, links in backup layers can be temporarily exploited as alternatives to ensure connectivity. Therefore backup layers can help the recovery of the active layer.

Ant Families

For the collection of multiple network parameters, we propose a bio-inspired, lightweight and responsive information collection mechanism. We draw inspira- tion from ant algorithms and plan to expoit three families of ants. Ants migrate from node to node and gather new information regarding the node and its neighbourhood, while also exchanging their stored information with the node they are visiting, leading thus to information dissemination across the network. Ants indirectly interact with each other via several types of pheromones.

Long-range Ants are responsible for network-wide information collection and exchange. They have a large TTL (Time-To-Live) and are capable of collecting multiple parameters during their life time. Migration of ants is biased by the pheromone concentration of the node's outgoing links. During migration, long-range ants reinforce outgoing and incoming pheromone concentration on the two connected nodes to reflect the latest status of the link. High pheromone concentration indicates links with relatively optimal quality characteristics in regard to the aforementioned network parameters. Pheromones evaporate at a constant rate; complete evaporation implies that a link is no longer active. The overhead traffic generated by long-range ants is composed of a standard 384 bits IPv6 (UDP) packet header, 96 bits ant header (ID, timing) and data payload. The payload contains information of visited nodes and their neighbours. Each visited node contributes 272 bits, plus 192 bits for every neighour.

Short-range Ants monitor the mobility of neighbouring nodes by frequently collecting relevant information. They differ from long-range ants in three aspects, i.e. the ant size, the activity frequency, and their migration behaviour. Their activity range is restricted to 2 hops, effectively leading to the collection of fewer information. This limits the short-range ants size to around 1/9 of the average size of long-range ants, and therefore we can increase their dispatch frequency without incurring too much additional overhead. The migration of short-range ants differs from that of long-range ants in that they leave pheromone trails labeled with their nest IDs, i.e. the dispatching node, to ensure that ants always return to the nest.

Messenger Ants are responsible for enforcing management decisions such as layer switching as instructed by higher-level applications. Messenger ants are in charge of propagating the decisions across the network, i.e. they do not collect information. This means that messenger ants should avoid following the footsteps of others. In this respect, we use a negative pheromone to guide the messenger ants to visit less explored links and nodes.

Topology Optimisation

Based on parameter information collected by ants, each node periodically optimises its overlay links to other nodes by initiating connections and disconnections and maintaining its neighbours. Each node keeps a local view of the network topology based on the information provided by long-range and short-range ants. This helps nodes to optimise their neighbour sets by comparing properties of the links to their current neighbours to those of other nodes in the local view. Better qualified nodes replace existing neighbours by setting up new overlay links to remote nodes and removing existing links to old neighbours, while additionally ensuring that all neighbours of the requesting node are kept connected. Although any change to a node's neighbour set can eventually be detected by ants, it is more efficient for the node to directly notify its neighbours via a simple message when a new neighbour has been detected. These messages do not flood the whole network and only affect the routing table of direct neighbours. Long-range ants will eventually propagate the change to other nodes.

Conclusion and Future Works

We report here the key concepts of our ongoing research work. Currently, the algorithm including the long-range and short-range ants have been implemented, while messenger ants are under development. Initial simulations using OM-NeT++ in low dynamicity environments have shown promising results in constructing P2P overlays with desired characteristics and with low overhead. Our future work mainly focuses on three aspects. First, the model of ants needs to be further improved to eliminate any unnecessary information. Second, a better topology optimising algorithm utilising the information collected by all ants and taking into account the different layers is necessary. Last, balancing the performance of the algorithm and its overhead traffic is also an open issue.

Fig. 1 .

 1 Fig. 1. Multi-layer overlay deployment scenario.

Acknowledgements

This work was conducted in the context of the BioMPE project financially supported by the Swiss National Science Foundation (SNF), grant 200021 130132.


Matthijs Polen
email: matthijs@vanpolen.biz

Giovane C M Moura

Aiko Pras
email: a.pras@utwente.nl

Matthijs G T Van Polen

Finding and Analyzing Evil Cities on the Internet

Keywords: Geographical Analysis, Bad Neighborhoods, Internet Geolocation, IP Geolocation, Spam, Network Attacks, Honeypots

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

IP Geolocation aims to determine the Internet users' geographical location based on their IP address [START_REF] Muir | Internet geolocation: Evasion and counterevasion[END_REF]. It has been used by industries and businesses for many purposes, including targeted advertisement (e.g., a global portal can deliver customized ads according to the user's location), fraud detection (e.g., online stores can check the physical location of a client against its billing address), media licensing (e.g, broadcasters, such as those on Hulu [START_REF] Hulu | Hulu -What your favorites[END_REF], only stream content to IPs belonging to certain countries) and even spam filtering [START_REF] Sobel | Use of Geo-Location Data for Spam Detection[END_REF].

In relation to security, most of the current Internet Geolocation analysis is done only at the country level. For example, the latest 'State of the Internet' report by Akamai shows only the top 10 countries from where attacks originated [START_REF] Akamai | The State of the Internet, 3rd Quarter[END_REF] 1 . Another example of country-level analysis is the daily generated map provided by Quarantainenet BV [START_REF] Quarantainenet | Virus attacks[END_REF].

In this paper, we address the Internet Geolocation for security on a city level instead. The assumption is that countries are too big and heterogeneous so their cities/towns are expected to exhibit different behavior in relation to security. The motivation for doing so is that it would allow provide security developers with hints on how to better tweak/improve their tools. Therefore, the main research question addressed in this paper is: "Which cities in the world are responsible for most of the security incidents?" Following the main research question, in this paper we address other sub questions:

-Are there cities that are relatively more 'evil' than others? Some cities might be more evil than others (that is, they generate more attacks than others), in some cases just because this city has more inhabitants, which leads to more computers and a higher probability of starting attacks. This sub research question addresses the evilness of cities taking into account its number of attackers per inhabitants.

The idea is to observe if and how the evilness of a city changes according to its population. -Are the cities where the most attacks originated located in the countries where the most attacks originated? If this would be the case, then filtering on a city level would not be very necessary, since filtering on a country level would yield the same results. However, if the answer to this question is 'no', then filtering on a city level might lead to more accurate results. If there are countries that cause a small number of attacks, but there is a city in that country that does cause a relatively large number of attacks, it might be a good idea to mistrust only the city and not the whole country. -Is there much change over time in the list of the most evil cities? The list of countries where the most attacks come from doesn't change much, as can be observed for the map generated by Quarantainenet [START_REF] Quarantainenet | Virus attacks[END_REF]. There is a mild variation during the day (probably due to day/night), but seen over the course of a week this list stays mostly the same. Would this behavior hold when cities are evaluated? -Do the evil cities change according to the type of attack? In this question we verify whether the list of evil cities remains the same for different types of security attacks.

If the list remains the same, it suggests, for example, that a list of cities where the most SSH attacks originate can be fed into a spam filter when scoring IPs based on their geolocation. If not, then a list of evil cities should be obtained per application.

The remainder of this paper is organized as follows: Section 2 discusses the related work. Section 3 presents our approach on how to find evil cities and describes our data sets. Section 4 addresses the main research question, providing analysis on the most malicious cities. Section 5 aims at the first sub research questions, in which the evilness of cities is evaluated taking into account its population. Section 6 presents results on the second sub question, evaluating whether the most evil cities belong to the most evil countries. Next, Section 7 covers the third sub question, in which the list of evil cities changes over time. After that, we evaluate how the evil cities change according to the type of attack in Section 8. Finally, Section 9 presents our conclusions and remarks for future work.

Related Work

Most of the current research works focusses on geographical location at the country level. For example, Jiang et al. [START_REF] Jiang | An email geographic Path-Based technique for spam filtering[END_REF] propose a spam filtering technique that uses countrylevel geographical information, which lead to a reduction of 13.9% in their experiments.

Even though they were able to reduce the number of spam messages, the authors do not describe what could happen if city-level information would be used instead of country level for filtering spam.

Sobel et al. [START_REF] Sobel | Use of Geo-Location Data for Spam Detection[END_REF], on the other hand, hold a U.S. patent for use of geolocation data for spam detection. It is stated in the patent that "the geolocation data may be any type of geographical information such as city, country, state or presence within a pre-selected radius of a geographical point". As a patent, the method is only described while its effectiveness is not addressed. Other non-scientific reports on the number of attacks per country also exist. For example, the Internet hosting company Akamai provides a quartely report named 'The State of the Internet' [START_REF] Akamai | The State of the Internet, 3rd Quarter[END_REF], which is obtained from the analysis of users that access Akamai servers (many sites, such as Hulu, BBC iPlayer and the White House use the Akamai content distribution network). In their latest report, they have observed attacks from 209 countries/regions, with the U.S. being the first one, in terms of traffic (12%). However, only 10 countries are mentioned in the report, and they do not provide analysis at city-level. Quarantainenet also provides a daily map of the countries that have attacked their honeypot infrastructure [START_REF] Quarantainenet | Virus attacks[END_REF].

Other work is also related to ours. In a previous piece of work, Van Wanrooij and Pras [START_REF] Van Wanrooij | Filtering spam from bad neighborhoods[END_REF] employ the concept of 'Internet bad neighborhood' -that is, there are certain IP blocks on the Internet more evil than others -to filter mail messages. Using data from blacklists, the authors were able to filter detect 95% of the spam messages. However, in their work, no geographical information is used. The research questions in our work address the existence of malicious cities on the Internet, instead of network blocks. In another work , Koike et al. [START_REF] Koike | Visualizing cyber attacks using IP matrix[END_REF] perform data visualization on the origin of attacks at IP block level or country level. Finally, Muir et al. [START_REF] Muir | Internet geolocation: Evasion and counterevasion[END_REF] present a survey on the current Internet geolocation methods.

In the next section we describe the dataset and the approach used in our study to find evil cities on the Internet.

Dataset and Approach

Quarantainenet Honeypot Data

In order to answer our research questions, the first step was to obtain reliable data from real world attacks. In our case, we have obtained full non-anonymized data from Quarantainenet B.V [START_REF] Quarantainenet | [END_REF], a Dutch company that develops network management and security tools and provides admission control and malware detection for their customers, including more than half of Dutch universities. Quarantainenet has a honeypot infrastructure which is distributed mostly over the Netherlands. In total, 125 machines are used for this purpose. Each has multiple IP addresses assigned to it to increase the chance of it being targeted by attackers.

Quarantainenet collects information from each honeypot and combines it into one single database. By definition, every new attack is logged. However, if the same IP address attacks a same honeypot multiple times within 48 hours, only the first incident is recorded. This is employed in order to keep the database more concise. For example, a host performing SSH dictionary attacks could be logged many times if this would not be employed. However, for our research, this does not represent a problem, since we are interested in the IP addresses of attackers, instead of the number of attacks.

Each honeypot is able to log many different type of attacks. Among them are SSHattacks, Conficker [10], known exploits of Microsoft Windows and others. Attacks that are as of yet unknown, are forwarded to Qnetlabs, the sister company of Quarantainenet, for further analysis. The honeypots used are passive, which means they wait for incoming connections that are then analyzed to see whether they are malicious.

The data provided by Quarantainenet is not publicly available, as it, of course, contains IP addresses of the attackers. Under Dutch law IP addresses can be 'persoonsgegevens', personal data. It is illegal to make them public. Therefore all IP addresses were processed automatically. Then they were discarded, leaving only an internal ID and a location.

For this research, we have evaluated a one week period from Quarantainet database -from October 29th to November 4th, 2010. During this period 25474 attacks were logged, from 23814 different IP addresses. Of these attacks, 20174 came from a form of the Conficker worm, a worm that targets the Windows operating system. The next largest number of attacks, namely 2052, were attacks trying to take advantage of the vulnerability in certain Windows-versions dubbed MS08-067 by Microsoft2 .

In the Sections 7 and 8 we have used different periods, which are detailed in the same sections. Next we describe the method we have employed to obtain Internet Geolocation information.

Method for obtaining IP Geolocation

After having obtained the IP addresses for the monitoring period, we have mapped them to their geographical location using GeoPlugin [START_REF] Geoplugin | [END_REF]. GeoPlugin is a free online API which uses Maxmind database [START_REF]Maxmind. Maxmind[END_REF] to resolve Internet Geolocation. They provide the following data for a particular address: city, region, area code, dma code , country name, country code, longitude, latitude, currency code, currency symbol and exchange rate. For our experiments, we needed only city and country code.

The main problem with using GeoPlugin that it relies on the accuracy of Maxmind database [START_REF]Maxmind. Maxmind[END_REF], of which numbers on accuracy are available [START_REF]Maxmind. Geolite city accuracy[END_REF]. Even though the database is not 100% precise, (Maxmind claims that their "GeoIP databases are 99.8% accurate on a country level, 90% accurate on a state level and 83% accurate for the US within a 25 mile radius"), we believe the results obtained would still hold, even though with some margin for errors.

For the sub-research question in which the number of inhabitants is taken into account, this was manually done using numbers obtained from Wikipedia. We intend as future work to develop a more automated and precise way to perform this using an online database, so that all cities can be checked, and not just the top 20. It would also be fitting to use the number of internet subscribers in a certain city, but at the time of writing this paper a database with information on the number of internet subscribers per city could not be found.

In the next sections we present the analysis for the research questions addressed in this paper. [START_REF] Akamai | The State of the Internet, 3rd Quarter[END_REF] Which cities are responsible for most of the security incidents?

To answer this question, we have evaluated the dataset described in Section 3. Table 1 shows the top 20 cities from which most of attackers were present, in absolute numbers. Analyzing this table, we can observe that, despite most of Quarantainenet's honeypot infrastructure being located in Europe, we have observed only one European city (Bucharest) among the top 20 evil cities. In addition, 9 of the top attacking cities are located in Asia and other 6 in South America, while no evil city from North America was found among the top 20. Three evil cities are located in Russia and other three in China. Figure 1 shows the attackers concentration in the world map, from the top 20 cities. As can be seen, most of attackers are located in Asia.

Taking the numbers into account, we observe that for that evaluated period most of attacks were originated in Seoul. The reasons for that might be due to Seoul has a huge number of inhabitants -Seoul metropolitan area has more than 24 million people (that is more than the population of the Netherlands, for example) combined with a high Internet penetration level [START_REF] Akamai | The State of the Internet, 3rd Quarter[END_REF]. Another reason could be the precision of the MaxMind database -they claim that 75% of all IP addresses that are located in South Korea are correctly placed within 25 miles of their true location [START_REF]Maxmind. Geolite city accuracy[END_REF]. However, even with such precision, Seoul would still be responsible for many attacks in absolute numbers.

On the next section we present the results for the most evil cities taking into account its number of inhabitants.

5 Are there cities that are relatively more 'evil' than others?

In the previous section we have presented the most evil cities ranked according to the number of attackers observed. In this section we present how evil they are, taking into account the number of inhabitants of each city. Table 2 shows the results. In this table, each city is ranked according to the number of attackers per million inhabitants. In the third column, the number behind each city name shows the position the city was in Table 1, which only takes into account the absolute number of attackers. One can notice that results change when the population is taken into account. Chelyabinsk, in Russia, is the city with more attackers per inhabitants, while it was number 20 in absolute numbers. Seoul, which was the first, is ranked as 5th in this table. Chelyabinsk has ten times more attacks per inhabitant than Shanghai does, which was not clear looking only at the previous section.

However, we do see that the top four cities don't differ that much; at least not enough to call Chelyabinsk a more evil city than Buenos Aires, for example. Lower down the list the results change. For example, Shanghai, while being on the twelfth position for absolute number of attacks, is on the twentieth position on the relative table. This might be a relatively small drop, however this is because only the absolute top twenty of cities was evaluated.

Finally, looking at these results, one can conclude that there are also significant differences when evaluating cities' evilness according to the number of inhabitants.

6 Are the cities where the most attacks originated located in the countries where the most attacks originated?

Table 3 shows the 20 countries that have started more attacks to the Quarantainenet honeypots. As one can notice, China is the leading country, followed by Brazil, U.S. and Russia. This table can be compared with the the list provided by Akamai in their report [START_REF] Akamai | The State of the Internet, 3rd Quarter[END_REF]. In this report, they present the top 10 countries originating attacks, using a different metric: volume traffic, instead of number of incidents. In their report, 6 of Table 2: Top 20 evil cities taking into account the population the top 10 countries match our results (China, Brazil, U.S., Russia, Taiwan and Italy), despite different ordering, being the U.S. the first country in their results.

To answer the research question addressed in this section, we should compare Table 3 to Table 1. In Table 1, the most evil city is Seoul. However, The Republic of Korea (South Korea) ranks at the 7th position when we aggregate the number of attackers per country. On the other hand, China tops the list as the most evil country, while it has 3 cities among the top 20 (Beijin, Guangzhou and Shanghai). While only one European city is among the top 20 cities, 8 countries are among the top 20 most evil countries. Finally, there are countries among the top 20 that have no city among the top 20 (e.g., Italy and Spain).

This results shows that there is little correlation between the most evil cities and the most evil countries. There are countries (e.g, Italy, U.S.) that have no cities among the most evil, but when attacks are aggregated at the country level their evilness is revealed. Therefore, filtering traffic taking into account the originating country is a risky approach, and a much more precise solution is to use cities instead.

7 Is there much change over time in the list of top offenders?

In order to answer this research question, we have obtained a list of the top 20 cities for each day of the evaluated week. Table 4 shows the obtained results. Due to space constraints, we do not show the number of attackers. Then, we have used Geoplugin [START_REF] Geoplugin | [END_REF] which, in turn, employs the Maxmind database to obtain the geographical information associated to a particular IP address.

The main research question addressed in this paper is: "Which cities in the world are responsible for most of the security incidents?". As detailed in Section 4, Seoul is the most dangerous city on the Internet, having 735 malicious hosts attacking Quarantainenet infrastructure. In addition, the results have shown that just one European city is among the top 20 most evil cities on the Internet, while 9 of the top 20 evil cities are located in Asia.

The main research question was followed by four sub-questions. The first one was if "Are there cities that are relatively more 'evil' than others?". In this sub-question we take into account the number of inhabitants per city to determine how evil they are. We can conclude that there are indeed cities that are relatively more evil than other cities. For example, Seoul caused the highest absolute number of attacks. When the number of inhabitants is taken into account, Seoul ends up on the fifth position. The number of attacks per inhabitant is lower than for example in Taipei.

The next addressed subquestion was "Are the cities where the most attacks originated located in the countries where the most attacks originated?". In our results, we have observed that most of the attackers are in China, Brazil and then in the U.S.. While only one European city is among the top 20 evil cities, 8 countries are among the top 20 most evil contries. The answer to this question is that there is little correlation between the most evil cities and most evil countries. This means that using a list of evil cities to finetune firewalls or filters would yield better results than using a list of countries.

The next sub-question investigated was "Is there much change over time in the list of top offenders?". The top twenty of evil cities is pretty invariable. While lower on the list changes do occur over time (e.g. looking at different weeks or different days within a week), Seoul is (almost) always on top, followed by Taipei, Bejing, etc. This makes using the data easier, as there is no need to gather new data on a daily basis.

Finally, the last sub-question was if "Do the evil cities change according to the type of attack?". To answer this question, we have compared the Quarantainenet database against the spam log files from two mail servers from the University of Twente for a period of one day. The answer to this question is that around 50% of the cities remain the same, independently from the type of attack. This suggests that geographical information from one type of attack might be used as input to other types of attacks.

As future work, we intend to improve our approach by using a online database for the number of inhabitants per city. In addition, we intend to conduct a evaluation over a longer period of data (a year) to observe how evil cities change according to time, if there is any sort of pattern. We also intend to perform the same analysis on different datasets. Finally, the next step is to to find out if spam filters and/or firewalls can indeed be made more precise by utilizing information about evil cities. One way might be to automate the process of calculating the most dangerous cities over, for example, the last week. The data gathered from this could be incorporated into automated generating of spam rules.

Fig. 1 :

 1 Fig. 1: Attacks on Dutch networks from 2010-10-29 until 2010-11-04

Table 1 :

 1 Top 20 attacking cities

	# City	Ctry # of attacks # City	Ctry # of attacks
	1 Seoul	(KP)	735	11 Guangzhou	(CN)	219
	2 Taipei	(TW)	618	12 Shanghai	(CN)	210
	3 Beijing	(CN)	563	13 Ho Chi Minh City (VN)	179
	4 Jakarta	(ID)	362	14 Kuala Lumpur	(MY)	177
	5 Buenos Aires (AR)	351	15 Bogota	(CO)	162
	6 Bangkok	(TH)	308	16 Saint Petersburg (RU)	160
	7 Moscow	(RU)	268	17 Rio De Janeiro	(BR)	152
	8 Hanoi	(VN)	267	18 Caracas	(VE)	143
	9 Santiago	(CL)	246	19 Bucharest	(RO)	139
	10 Sao Paulo	(BR)	229	20 Chelyabinsk	(RU)	129

Table 5 :

 5 Top 20 evil cities for differents type of attacks

	# QNET-Attacks Cities # of attackers # Spamming Cities # of spammers
	1 Seoul	190	1 Seoul	1759
	2 Beijing	176	2 Mumbai	1488
	3 Taipei	147	3 Hanoi	1364
	4 Buenos Aires	107	4 New Delhi	797
	5 Jakarta	106	5 Ho Chi Mihn	790
	6 Santiago	87	6 Delhi	752
	7 Guangzhou	75	7 Riyadh	731
	8 Sao Paulo	75	8 Bogota	717
	9 Bogota	75	9 Jiddah	682
	10 Moscow	73	10 Sao Paulo	677
	11 Saint Petersburg	70	11 Bangkok	677
	12 Bangkok	56	12 Bangalore	676
	13 Hanoi	50	13 Taipei	604
	14 Bucharest	50	14 Bucharest	593
	15 Shanghai	49	15 Madras	576
	16 Rio de Janeiro	49	16 Hyderabad	525
	17 Ho Chi Mihn	40	17 Santiago	516
	18 Rome	37	18 Kiev	467
	19 Caracas	35	19 Jakarta	429
	20 Shenzhen	32	20 Cairo	428

In this work, by originated we mean where the attack came from. We do not consider if there were other hosts controlling the attacking one.

Please see http://www.microsoft.com/technet/security/bulletin/ms08-067.mspx for details from Microsoft TechNet.

Seoul was ranked the 9th city in the world with the highest average measured connection speed by Akamai Networks [4] -an average of 14.4 Mpbs (all top 11 cities were in South Korea for the reporting period).

Acknowledgments The authors would like to thank Quarantainenet B.V. for granting us access to their honeypot data, in special Casper Joost Eyckelhof. Also, many thanks to Marc Berenschot for his suggestions and contribution to this work.

As can be seen, Seoul is the most malicious city for 6 of the 7 days. In addition, the top 3 cities are always Seoul, Taipei or Beijing for each day. The one time Taipei was number one, the difference between the two was only two attackers. However, the midsection was also quite stable. There were changes between cities already on the list, but only rarely did a city make the list for a day that wasn't already on the top twenty list of the entire week.

So, all in all, the top twenty list of cities is quite stable. This means that it can be used as the foundation of a set of rules for day-to-day use. There were no cases of a city making the overall top twenty list because there was a one-day spike of traffic. This suggests that is not necessary to update the list of malicious cities on a daily basis.

8 Do the evil cities change according to the type of attack?

To investigate if the evil cities differ or not according to type of attack, we have analyzed data from two different datasets: (i) Quarantainenet database and (ii) log files from e-mail servers of the Electrical Engineering, Mathematics and Computer Science Department at University of Twente (EWI/UT). The difference between the datasets is that the first one lists IP addresses of hosts performing different types of brute force/break-in attempts (as described in Section 3), while the second one lists spamming hosts.

In order to have a more fair comparison, we have evaluated the IP addresses of malicious hosts for the same day: April 22nd, 2010. In this very day, Quarantainenet dataset had 6,797 IPs as malicious. The mail log files from EWI/UT, on the other hand, contained 240,733 spam messages from 70,546 different IP addresses. The IP addresses of both datasets were resolved to city level and then analyzed.

Table 5 presents the Top 20 evil cities for both datasets. At a first glance, one could notice that 9 out of 20 cities are found in both cases (highlighted in boldface). In fact, out of top 100 evil cities, 50 are found for both datasets, and 105 cities are present in both cases when comparing the top 200 evil cities. Even though the position in tables might change for each city, around 50% of the cities remains the same. This could be used, for example, to application level filters (such as mail filters, http proxies), in which cities would get lower scores levels for a certain type of application just by being evil for other applications. However, further research is need to investigated the feasibility of this proposal.

In the table, we can also observe that, for both cases, Seoul is the city where most of attackers and spammers come from. This is an interesting fact that shows us a different side of Seoul (as in Section 4): South Korea is usually regarded as the country with the highest level of broadband adoption, including its capital Seoul 3 . However, as shown by our results, more broadband penetration does not mean higher security levels. Seoul network administrators should be aware of this fact in order to improve security levels in their networks.

Finally, we can conclude that around 50% of malicious cities remains the same for different types of attacks, even when analyzing data from different domains.

Conclusions and Future Work

In this paper we have employed Internet Geolocation in order to find what are the most evil cities on the Internet. To achieve this, we have obtained IP addresses from malicious hosts from 125 honeypots maintained by Quarantainenet [START_REF] Quarantainenet | Virus attacks[END_REF], over a period of one week.