Lang Xie
email: langxie@item.ntnu.no

Poul E Heegaard
email: poul.heegaard@item.ntnu.no

Yuming Jiang
email: jiang@item.ntnu.no

Modeling and Analysis of the Survivability of an Infrastructure-based Wireless Network

Keywords: survivability, analytical models, disastrous failures

This paper focuses on survivability modeling to characterize the transient behavior of an infrastructure-based wireless network in the presence of disastrous failures and repairs. Two modeling approaches, an exact model and an approximate product-form model are presented. Numerical experiments with the two models demonstrates that the approximative product-form approach obtain close to exact results with a significant lower computational complexity. The product-form approach has been applied to study the impact of various system parameters on the survivability of the studied network.

Introduction

Network survivability has become a major concern of critical service providers and network operators. This includes infrastructure-based wireless networks such as IEEE 802.11 WLANs, IEEE 802.16 WiMAX, and cellular networks. Critical services in these networks should be continuously provided even when some undesired events such as attacks, natural disasters, and common failures has occurred. In general, infrastructure-based wireless networks rely on building infrastructure with access points (or base stations) to cover their service areas. Compared with wired networks, infrastructure-based wireless networks are less reliable and are vulnerable to various failures, especially failures occuring in access points. This gives rise to the need of specific survivable wireless network architectures and mechanisms. Furthermore, quantifying survivability metrics of wireless networks is important and necessary to meet the user requirements and compare different network designs.

During the last decade, the definitions, metrics, and quantification methods of survivability have been extensively studied in traditional telecommunication networks [START_REF] Zolfaghari | Framework for network survivability performance. Selected Areas in Communications[END_REF], [START_REF] Yun | Survivability analysis of telephone access network[END_REF], [START_REF] Heegaard | Network survivability modeling[END_REF]. Some related work in other wireless network types, for instance, ad-hoc networks [START_REF] Dongyan | Network survivability performance evaluation: a quantitative approach with applications in wireless ad-hoc networks[END_REF], [START_REF] Fei | On the Survivability of Wireless Ad Hoc Networks with Node Misbehaviors and Failures. Dependable and Secure Computing[END_REF], can provide a good insight in network survivability quantification. However, these works are not applicable in infrastructure-based wireless networks. In the literature, some works study the survivability quantification of wireless cellular networks. Tipper et al. [START_REF] Tipper | Survivability analysis for Mobile Cellular Networks[END_REF] and Dharmaraja et al. [START_REF] Dharmaraja | Reliability and Survivability Analysis for UMTS Networks: An Analytical Approach[END_REF] make extensive study for various failure scenarios and their effects on wireless cellular networks. However, these studies are limited in the structural aspects of cellular networks. They do not capture the transient performance variation from failure to normal mode. In addition, most of the above approaches assume the number of failures is small (e.g. one or two), and far less research has been conducted on scenarios of large-scale failures which may be caused by natural disasters or malicious attacks. These events occur with a low frequency but with severe consequences. It is necessary to take above rare events into account when analyzing network survivability.

Survivability models with disasters may seem to be appropriate in telecommunication network dimensioning and planning phase. Jindal et al. [START_REF] Jindal | Analytical survivability model for fault tolerant cellular networks supporting multiple services[END_REF] propose an analytical survivability model for base station exposed to channel failures and disastrous failures. Nevertheless, this model only considers one base station without extending to network level. In addition, most existing works may be limited in just one specific homogeneous wireless network scenario. However, in practice the heterogeneous network is probably a more common scenario, such as multimode handsets, overlay networks [START_REF] James | Modelling and Analysis of Network Resilience[END_REF]. This network architecture further complicates the survivability quantification.

In this paper, we conduct quantitative, model-based analysis of the survivability of a two-tier heterogeneous infrastructure-based wireless network subject to disastrous breakdowns and system repair. Specifically, the focus is on characterizing the transient behavior of the system immediately after disaster until the system restores and stablizes again. Two modeling approaches, an exact model and an approximate product-form model are presented. Furthermore, we compare both approaches numerically and examine the effect of different modeling assumptions on the defined performance measures.

The rest of this paper is organized as follows. In Section 2, the system model is given. Section 3 describes the disaster-based survivability model and two approaches for transient solution. Numerical results are presented in Section 4. Finally, Section 5 gives the closing remarks and discusses future research in this area.

System Model

Generally, the operation of infrastructure-based wireless networks relies on base stations (or called access points in this paper), which are vulnerable to various undesired events. The theme of this paper is survivability modeling and analysis on infrastructure with access points. We first describe the system model in this section.

Network Description

When local network operators decide to deploy infrastructure-based wireless networks in their communities, the first step is radio network dimensioning. This phase aims to estimate the number of required access points and is often based on the assumption of uniform distribution of user subscribers.

Consider the network deployed in one certain geographic area. It may be covered by more than one type of radio system which is in essence a survivable architecture. This means that if one radio system fails, other radio systems will maintain the service continuity provided that the subscriber terminals support multiple radio modes. For the sake of simplicity, the analysis is started from a two-tier radio system, network-1 and network-2 as shown in Fig. 1. Users uniformly distribute across this area and support to access both radio systems. In our context, network-1 is prioritized over network-2 from the users' perspective.

The above simple wireless scenario is considered by operators to improve survivability. For example, Wireless Trondheim has deployed Wi-Fi networks and implemented an experimental Mobile WiMAX network in the downtown area of Trondheim to provide ubiquitous Internet access [10].

Random Failure Model

In the dynamic wireless communication environment, access points of both network-1 and network-2 may have major or minor failures caused by a variety of undesired events. In this paper, we consider two types of failures as follows.

Independent Random Node Failures Access points in infrastructure-based wireless networks can be viewed as a set of nodes. Suppose the network is subject to random node failures where each access point fails, along with all associated links, with a probability q, independently of other nodes.

Disastrous Failures

We consider disastrous failures as external events. They have severe consequences. In this paper, only disastrous failures at which damages all network-1 access points are considered.

As we mentioned in the previous section, far less work has been conducted on the modeling and analysis of the transient behavior of an infrastructure-based wireless network subject to a disastrous failure scenario. The model in the next section aims at characterizing such disaster-based survivability.

Network Survivability Model

A model is required to quantitatively assess the network survivability. In this section, we present a continuous-time Markov chain (CTMC) model to characterize the transient network behavior after disaster until the system stabilizes again.

Survivability Definition

Survivability is defined as the system's ability to continuously deliver services in compliance with the given requirements in the presence of failures and other undesired events [START_REF] Heegaard | Network survivability modeling[END_REF].

In this paper, our objective is to quantify the survivability of infrastructurebased wireless networks subject to disastrous failures. For this, we define the (i) service to be the connections between access points and subscribers, (ii) service requirement to be a minimum number of access points that need to be operational for the service to be available, (iii) undesired events to be access points failures caused by disastrous failures. The network survivability is quantified by the transient performance from the instant an undesired event occurs until its steady state is reached. Survivability quantification can be used to compare different network architectures and survivable mechanisms. In order to deal with survivability in a quantitative way, it is necessary to have a mathematical description of the above temporal process. We use the survivability quantification definition given by ANSI T1A1.2 [START_REF]A1.2 Working Group on Network Survivability Performance[END_REF]:

The measure of interest M has the value m 0 before a failure occurs. The survivability behavior can be depicted by the following attributes: m a is the value of M just after the failure occurs; m u is the maximum difference between the value of M and m a after the failure; m r is the restored value of M after some time t r ; and t R is the relaxation time for the system to restore the value of M . Fig. 2 illustrates the above notations, which constitute the survivability quantification results. Since the breakdown of one access point may affect tens or hundreds of users, the connectivity of infrastructure-based wireless networks mostly depends on the operational status of access points. The measure of interest M in this paper will be the expected unavailability. Since our focus is the connectivity in large networks, we do not consider the dynamics brought by routing and traffic flows further in this paper.

Assumptions and Notations

Consider the two-tier hierarchical wireless network system described in Section 2. The following assumptions are made:

-Network-1 and network-2 access points have independent random node failures according to Poisson processes with rates λ 1 and λ 2 , respectively. -A faulty node can be recovered through repairment. The independent node repair times for network-1 and network-2 access points are exponentially distributed with parameters µ 1 and µ 2 , respectively. Assuming that there is only one repairman for each access point type.

-The system suffers disastrous breakdown resulting in all network-1 access points lost. Upon disaster, a global repair process starts immediately. The global repair time is exponentially distributed with mean 1/τ . -If too few network-1 access points are available, then network-2 access points will support the service.

Furthermore, a number of parameters related to the size of the system will affect the survivability, which include:

-I, the maximum number of network-1 access points in the system -J, the maximum number of network-2 access points in the system i, the current number of operational network-1 access points in the system j, the current number of operational network-2 access points in the system -C, the minimum required number of access points in the system Performance metric is the steady state unavailability U = P (i + j < C), which is the probability that less than C access points are available.

Disaster-based Survivability Model

Since the system we analyze resides in a dynamic environment, let (N i (t), N j (t)) define a continuous-time Markov chain (CTMC) with state space Ω = {(i, j); 0 ≤ i ≤ I, 0 ≤ j ≤ J}, where N i (t) and N j (t) denote the number of operational network-1 access points and that of network-2 access points at time t, respectively. The state transition diagram of this Markov chain is illustrated in Fig. 3. It is required that a minimum number of access points, C (0 < C ≤ I + J) are necessary for the system to be operational. The transition rate from state (i, j) to state (i -1, j) is iλ 1 . It corresponds to a random node failure in any of network-1 access points. The transition from state (i, j) to state (i, j -1) denotes a random node failure of one network-2 access point. The corresponding transition rate is jλ 2 . The transition from state (i -1, j) to state (i, j) corresponds to the repairment of one network-1 access point with rate µ 1 . The transition from state (i, j -1) to state (i, j) denotes the repairment of one network-2 access point with rate µ 2 .

For each state (i, j), there is a certain possibility to have disastrous failure causing all network-1 access points down and then the system will enter state (0, j). For disaster-based survivability analysis, particular attention should be given to the transient behavior after the disaster. This is the reason why disastrous failure is forced (dashed arc in Fig. 3). Specifically, a global repair restores the system to state (I, j) with rate τ from state (0, j). The various transition rates q (i,j),(i ′ ,j ′ ) of the process (N i (t), N j (t)) are

q (i,j),(i-1,j) = iλ 1 , i = 1, 2, • • • , I, j = 0, 1, • • • , J q (i,j),(i,j-1) = jλ 2 , i = 0, 1, • • • , I, j = 1, 2, • • • , J q (i-1,j),(i,j) = µ 1 , i = 2, • • • , I, j = 0, 1, • • • , J q (i,j-1),(i,j) = µ 2 , i = 0, 1, • • • , I, j = 1, 2, • • • , J q (0,j),(I,j) = τ, j = 0, 1, • • • , J (1)
Based on the above transition rate regulations, the state transition rate matrix of this model can be obtained as Q = [q (i,j),(i ′ ,j ′ ) ].

Survivability Analysis: Exact Model

Let P (t) = [P (0,0) (t) • • • P (i,j) (t) • • • P (I,J) (t)] denote a row vector of transient state probabilities at time t. In order to calculate P (t), the Kolmogorov-forward equation expressed in the matrix form should be satisfied as follows:

dP (t) dt = P (t)Q (2)
where Q is the transition rate matrix. Then the transient state probability vector can be obtained as follows: where e Qt is defined as follows:

P (t) = e Qt (3)
e Qt = ∞ i=0 Q i t i i! (4)
The simplest method to compute Eq. ( 4) is to truncate the summation to a large number (e.g., K), which can be expressed as follows:

e Qt = K i=0 Q i t i i! (5)
An alternative way to compute the transient probabilities is by using eigenvalues. In this method, Q is assumed to be diagonalizable,

Q = UVU -1 (6)
where V is a diagnoal matrix of eigenvalues. The transient probabilities can be defined as follows:

V =      e v1t e v2t
. . .

e vN t     
Then, the transition probabilities can be written as follows:

P (t) = U( ∞ i=0 V t i i! )U -1 = Ue Vt U -1 (7)
Based on the above calculated transient probabilities, the measure of interest M , service unavailability is obtained as reward measures from the CTMC model (N i (t), N j (t)). Let each state of the CTMC is associated with a reward rate. For a valid state (i, j), if i + j < C, the reward rate is assigned 1; otherwise the reward rate is assigned 0. Let U (t) represent the instantaneous reward rate of the model. Then, the expected instantaneous reward rate E[U (t)] gives the service unavailability of the system at time t, which is expressed as follows:

E[U (t)] = i+j<C P (i,j) (t) (8)
However, the above so called exact model approach for calculating the transition probabilities needs to visit each state and to repeat the transient state analysis, which could be computational challenging when the network size is growing.

Survivability Analysis: Product-Form Approximation

The transient analysis in the last section is too complex for a symbolic closed form solution, and even too difficult for a numerical solution. Since the random node failures and repairs of two types of access points are independent, we apply a decomposition approach to facilitate the calculation of the transient probability P (i,j) (t) for state (i, j). This is a product-form approach as follows:

P (i,j) (t) = P (t, i) • π(j) (9)
where P (t, i) is the transient probability of a state i (0 ≤ i ≤ I), and π(j) is the steady state probability of a state j (0 ≤ j ≤ J). The closed-form steady state probabilites π(j) can be derived:

π(j) = 1 j! ( µ 2 ρ 2 ) j π(0) (10)
where π(0) can be obtained according to the normalization condition,

π(0) = 1 J k=0 1 k! ( µ2 ρ2 ) k (11)
In order to calculate the transient probability P (t, i), the transition rate matrix Λ = [a i,i ′ ] is reduced as follows:

a i,i-1 = iλ 1 , i = 2, • • • , I a i-1,i = µ 1 , i = 2, • • • , I a 0,I = τ (12)
Then, the expected service unavailability E[U (t)] can be defined as follows:

E[U (t)] = i+j<C P (t, i) • π(j) (13)
In particular, this product-form approach requires only transient solution of evolution of network-1 access points, and the steady-state solution of evolution of network-2 access points.

Numerical Results

In this section, the numerical solutions to the proposed survivability quantification models in the above sections are presented using Mathematica [START_REF]Mathematica Guide[END_REF]. To demonstrate the applicability of the proposed product-form solution, we compare it with the exact model approach. In addition, we examine the effect of different modeling parameters on the defined performance measures. ). The required minimun number of access points C is defined as (I + J)/3.

To show the computational advantages of the product-form approach over the exact model approach, we compare the time needed for calculating transient probabilities using the two approaches. We run experiments with three network scales (case 1: I = 2, J = 2; case 2: I = 3, J = 2; case 3: I = 3, J = 3). In all the experiment cases, n = 30 runs are performed and the mean running time (unit: seconds) are recorded as shown in Table 2.

The observation from Table 2 suggests that the product-form approach is able to almost immediately give the transient probabilities. However, it may take about 0.6 seconds by using the exact model approach in case 1. Similar results can be obtained from experiments case 2 and case 3. For the exact model approach, it takes more time (about 2 seconds in case 2 and 8 seconds in case 3) than case 1. The growing of network size has significant impact on the computational complexity of the exact model approach. With regard to the solution Eq. ( 8), the exact model approach has a state space that is proportional to (I +1)(J +1). The product-form approach will reduce the state space of the transient solution to (I +1) as indicated in Eq. ( 13). This explains why the product-form approach has advantages in transient solution computation than the exact model approach. For large-scale networks, it can be easily realized that the exact model approach will be tough in transient solution computation while the product-form approach may be applicable.

Effect of Parameters on Survivability Performance

In the following, both approaches are used to numerically obtain the system survivability performance. First, we consider a small network case (I = 3, J = 3). We plot in a log-time way as shown in Fig. 4(a), solid curves I and II represent the results of product-form approach while the dashed curves III and IV are the results of exact model approach. As this figure suggests, the survivability quantification notations are displayed as m a , t R , m 0 .

We examine the way in which parameter τ affects the survivability model. When τ = 0.02(hour -1 ), the curve I coincides with III. However, when τ = 1(hour -1 ), there exist a relatively small difference gap between curves II and IV . The decomposition in the product-form approach is based on the assumption that the random node failures and repairs of two types of access points are independent. Thus, the above observation demonstrates that if the global recovery rate τ is not much less (i.e., more than one order of magnitude) than random single node repair rates (µ 1 , µ 2 ), the product-form approach is not perfectly but quite closely accurate. If τ is much less than single node repair rates, the product-form approach captures the exact results in the same way as the exact model approach. Therefore, the product-form approach is quite good in accuracy.

Then we extend the analysis to a larger network case (I = 20, J = 15). The survivability quantification results m a , t R , m 0 are shown as the notations in Fig. 4(b). Since it is quite time-consuming to calculate the transient solutions using exact model approach, only the results of the product-form approach are plotted. In both figures, curve II reaches steady state much faster than curve I. Since the mean time for a global repair is much longer than the mean repair time of one access point is obvious, it is naturally assumed that τ is much less than (µ 1 , µ 2 ). In summary, compared with the exact model approach which can be actually used for small size models only, the product-form approach is more scalable as well as quite good accuracy.

Conclusion

The CTMC analytical model for wireless network survivability quantification outlined in this paper enables us to model large-scale infrastructure-based wireless networks exposed to disastrous failures. Specifically, the focus has been on characterizing the transient behavior of the system immediately after the disaster until the system restores and stablizes again. In addition, numerical results have been presented to study the impact of the underlying system parameters and the explicit parametric relations. Future work are considered in several directions. The recovery time in the current model has for simplicity been assumed to be exponentially distributed which may be not true in real scenario. More general model, like phase-type model or semi-Markov model can be used. In addition, the locations of users and access points, which play a important role in wireless communication, are not included in our studied scenario and defined system state. In the future, we will extend the system state by adding more dimensions representing geographical characterizations.

Fig. 1 .

 1 Fig. 1. Reference scenario

Fig. 2 .

 2 Fig. 2. Temporal aspects of survivability (adapted from [3])

Fig. 3 .

 3 Fig. 3. State transition diagram for the reference scenario

(a) Scale 1 :Fig. 4 .

 14 Fig. 4. Log-plot of unavailability E[U (t)] versus time t

Table 1 .

 1 Default values of failure/repair parameters

	Parameter	λ1	λ2	µ1	µ2	τ
	Value(hour -1 )	0.01	0.005 2	2	0.02
	4.1 Computational Complexity Analysis

Table 1

 1 lists the default value of part of parameters. It is a natural assumption to say that (λ 1 , λ 2 ) < τ ≪ (µ 1 , µ 2

Table 2 .

 2 Comparison of computational time for transient probabilities using the two approaches under three cases (mean ± standard error, unit: seconds).

		case 1	case 2	case 3
	Exact model	0.581 ± 0.316	1.997 ± 0.890	7.899 ± 0.895
	Product-form	0.021 ± 0.017	0.041 ± 0.026	0.041 ± 0.016


Albert Domingo
email: albert.domingo@upf.edu

Boris Bellalta
email: boris.bellalta@upf.edu

Miquel Oliver
email: miquel.oliver@upf.edu

White Spaces in UHF band: Catalonia case study and impact of the Digital Dividend

Keywords: White Spaces, UHF, Digital Dividend, Spectrum availability

White Spaces in the UHF bands are very interesting because of their potential use in rural communications, but their feasibility needs to be proven. This paper analyses the TV spectrum occupation in the region of Catalonia, Spain, because it will be one of the first EU regions where changes in the UHF band are going to be implemented. Those changes are derived from the implementation of the Digital Dividend. The goal of this paper is to correlate population density with future free channel availability, and to proof that communications through TV White Spaces equipment is a good candidate for low density population areas.

Introduction

White Spaces -WSis the term that refers to the non-occupied frequencies in the spectrum. In particular, bandwidth availability on the television broadcasting frequency bands is the focus of this paper. Both Very High Frequency -VHFand Ultra High Frequency -UHFare used, however, we will only focus on the UHF part of the spectrum.

The occupancy of those bands has been reduced after implementing the digital television signal, which uses less spectrum to provide more channels. Only when both signal types (analog and digital) were broadcasted over the same area it could be stated that the spectrum was scarce on the studied bands.

The high value of those frequencies is due to their physical properties and some attributes can describe why: they can cover large areas from a single emission point, they can penetrate physical objects in contrast to higher frequencies (e.g.: thick concrete/brick/stone walls) and thus improve the in-building signal strength, and costs over a covered area can decrease in comparison to other technological solutions based on higher frequencies. However, this will depend on the business model and policies implemented.

The Digital Dividend will bring a reduction in the UHF band usage and has been considered by the European Commission as a way of boosting the economic growth of the region [START_REF]European Commission: 586 final: Transforming the digital dividend opportunity into social benefits and economic growth in Europe[END_REF]. The shift in spectrum will take place in TV channels from 61 to 69 (790 MHz to 862 MHz). Previous to the Digital Dividend the Commission resolved to take part of the spectrum released by the digital switchover, as shown in their paragraphs 30 to 37, to promote among the European countries special licenses for White Space frequencies [START_REF]European Commission: Resolution: Common approach to the use of the spectrum released by the digital switchover[END_REF].

This paper aims to study if there will be differences between rural and urban areas in the usage of these frequencies. It contributes to understand the availability of WS, taking into account the Digital Dividend, and the possible link established between inhabitants density and spectrum availability, something that would complete the study made in [START_REF] Van De Beek | UHF white space in Europea quantitative study into the potential of the 470-790 MHz band[END_REF] by focusing the area of study. Our contribution in this area is to assure feasibility for rural areas and to allow new standards of communication to be deployed taking advantage of WS.

This paper is structured as follows. We first describe in Section 2 the evolution of the UHF band in Spain until the Digital Dividend will be applied. Section 3 describes the methodology followed to obtain the results for UHF spectrum availability in Catalonia. Main results are shown in Section 4. Our conclusions are given in Section 5 which also includes some future work that we will carry on in the same area.

Evolution of the UHF band in Spain

Spain was the forth country adopting Digital Television and the third to implement it (the first countries to adopt it were USA, UK, and Sweden. Implementation had the same actors but Spain installed the required infrastructure before Sweden).

Spain started to assign digital television channels in 1999. Different levels of granularity were used to assign the channels: State, Regional and Local levels.

The digital switchover in Spain has come with a reduction of the local television coverage, where most of the cities, towns and villages were broadcasting a local signal with content based on local interest.

Televisió de Catalunya carried out the first emission in Spain in 1998 under a trial license. Then, in 1999 Onda Digital S.L., which since has been re-named Quiero TV, obtained the first private license to broadcast 14 channels [START_REF]2 de septiembre de 1999[END_REF]. Those channels included all the satellite contents and were offered under the pay-per-view option. Some problems arose in Spain after the launch because the payment platform was not having the expected take-up rate, which lead to its closure in 2002. After this first end of digital TV, public television started broadcasting their content as a digital signal.

Spain started to design its digital transition in 2005 [5]. In July of the same year the Implementation Plan was published. In 2007, the transition plan was ratified and it was planned that before April 2010, all the analog TV channels should be switched off [START_REF]Acuerdo del consejo de ministros por el que se aprueba el plan nacional de transición a la televisión digital terrestre[END_REF].

As the digital switchover came closer, it was necessary to accept that 1,5% of the population would not receive the digital signal and a law was passed to fix this problem by using satellites to broadcast the service [START_REF]LEY 7/2009, de 3 de Julio, de medidas urgentes en materia de telecomunicaciones, que[END_REF].

The implementation of the European mandate of its article 6 to free the spectrum around 800 MHz, called Digital Dividend, for providing digital communications over those frequencies is the current channel switching that will be applied to the UHF band ( [START_REF]Communication from the commission to the European parliament, the council, the European economic and social committee and the committee of the regions, A Digital Agenda for Europe[END_REF] and[9]). Spain has implemented this directive in its law and wants to make available channels from 61 to 69 (790 MHz to 862 MHz) before January 1st, 2015. According to the European Union, this should allow new possibilities for rural areas and less favoured users.

As long as this spectrum was seen by regulation as TV bands, it has never been allowed to be used for anything else than broadcasting television in Spain. Before 2009, FCC, OFCOM and private companies were doing research on this area and conducted real-life tests (see [START_REF] Chandra | A campus-wide testbed over the TV white spaces[END_REF], [START_REF] Davies | Field Trials Of DVB-T Sensing For TV White Spaces[END_REF], [12] and [START_REF]Statement: Digital dividend: cognitive access Statement on licence-exempting cognitive devices using interleaved spectrum[END_REF]). Currently, there are some standards suitable to be implemented for those frequencies that can operate within a UHF channel (e.g.: LTE, 802.22 and 802.11af). Regulation will be applied to guarantee that no interference is seen on the TV licensed channels and to model the use of the WS. Some research is done on the use of beacons to announce a free TV channel [START_REF] Goratti | An Urn Occupancy Approach for Cognitive Radio Networks in DTVB White Spaces[END_REF], and on the use of a sensor to find WS which would be defined under cognitive equipment [START_REF] Shin | Cognitive Radios for Dynamic Spectrum Access: From Concept to Reality[END_REF]. The interest of our research is the implementation of a database that informs about channel availability in every area [START_REF]Public Notice: FCC's Office of Engineering and Technology Issues Public Notice to Start Public Testing for Spectrum Bridge's TV White Spaces Database System[END_REF].

Methodology and example to predict availability

In Spain the use of licensed-free equipment is not allowed in the UHF bands as it is only permitted on the ISM1 bands defined by the ITU-T. Currently, the Spanish TV band is only operated under license requirement.

To identify the unused channels, we first included the licensed channels per area. Such information is obtained from official published sources. National channels are licensed directly from the "Ministerio de Industria, Energía y Turismo", which has a section devoted to allocate and assign frequencies that is held by the "Secretaria de Estado de las Telecomunicaciones". As this first study is focusing on Catalonia, we have to consult and add the Catalan regional channels that are licensed by the "Generalitat de Catalunya". Finally we have also checked all the local televisions that are broadcasted in the region.

The number of occupied channels is obtained after adding the 9 channels that will be devoted to LTE communications and will reduce the Digital Dividend. After that we have also added the number of occupied channels that cognitive equipment can sense, between 4 and 6 more channels than the licensed ones. Finally, an approximation of the worst case for the area is done by adding 4 interference channels licensed in neighbouring areas of the analysed region. This is done because the strength of their signals usually covers more area than the city, town or village where they were licensed.

As an example of our study we show the results for the dense urban Barcelona area in Table 1, and a detailed list of the channel's occupancy is shown in the Appendix.

It can be seen in Table 1 that the effect of the Digital Dividend on the number of available channels in Barcelona will suffer a decrease from 27 to 12 according to our predictions for the year 2015. The equivalent space in MHz for WS is set around 96 MHz, which is more than the 60 MHz freed by the Digital Dividend on the band of 800 MHz [START_REF]DECISION OF THE EUROPEAN PARLIAMENT AND[END_REF].

The middle column was obtained by using a Promax spectrum analyzer, model AE-766, to verify in-the-field the real channel occupancy. The result was that some channels were occupied without being licensed and some licensed channels were not broadcasting on that day. This result is similar to what would be sensed by cognitive equipment [START_REF]IEEE Standard for Wireless Regional Area Networks Part 22: Cognitive Wireless RAN Medium Access Control (MAC) and Physical Layer (PHY) specifications: Policies and procedures for operation in the TV Bands[END_REF]. * Regional interference approximation (-4 channels). These interferences come from local channels that are emitting in the surroundings of Barcelona and that can affect the region. Therefore, if cognitive radio equipment is applied it will show occupancy in those channels.

Current and future availability: population density and UHF channels in the Region of Catalonia

The same methodology that is used in Section 3 can be extended to any other region where the Digital Dividend is going to be applied. Our approximation of availability inside the UHF band after 2015 is shown in Figure 1.a). It shows the number of 8 MHz spaced channels available, superimposed over the Catalonia map.

It can be discerned that the occupancy is higher in the city of Barcelona and its surroundings. There will be only between 12 and 14 channels available to implement WS communication solutions. The same situation occurs on the borders of the region. In those cases the interference of other regional TV channels (those of Aragon and the Comunitat Valenciana) will increase the occupied channels to levels of big cities like Barcelona. The Catalan central region and the north, with the Pyrenees, will have less interference and will have an average amount of free channels between 15 and 16. The case of Andorra, also analysed, shows that 22 channels will be available there and is the best case analysed after applying the methodology described in Section 3.

As we want to know future availability per user we include the inhabitant density map2 , Figure 1.b), to be compared with the WS availability map. High density areas are defined with more than 1000 inhabitants per square kilometre and rural ones with less than 150 inhabitants per square kilometre.

If we compare the density map and the availability map, only the boarders with other regions do not show a correlation with population density. From that point of view, without quantification, it would seem suitable to state that the use of WS could have a bigger effect in rural areas than in urban ones. To quantify the relation between the two maps the best availability per person has been calculated. Table 2 shows that the average number of available channels is higher in rural areas than in urban ones, as expected from the observed data. Rural areas will have the best availability of 2.26 MHz per person, compared to the worst availability of 0.05 MHz per person in dense urban areas.

Conclusions and future work

In this paper, we have shown that even after the Digital Dividend is applied, there will be available UHF channels beyond 2015. We have shown that the relation between the number of inhabitants and the number of available channels (i.e., more inhabitants means less WS) also holds in the Catalan region, with 2.26 MHz per inhabitant in rural areas in contrast to the 0.05 MHz per inhabitant in urban ones. Finally, the results have shown that the use of a database to avoid interferences with licensed channels is highly recommended. However, as some of the licensed channels were not found during our spectrum measurements, which was acting like cognitive equipment and, on the other hand, we found occupied channels that were supposed to be not in use. This shows that cognitive radio has to be combined with a list of licensed channels to regulate a solution that do not affect the current UHF TV channels. This paper opens the door to a policy that will enable for the first time in Spain the use of exchanging data in an entire UHF channel, although the creation of a database and a license manager would be the first step to implement WS equipment.

A further study over the Spanish region is currently undertaken by us to obtain a better relation between rural areas, urban areas and their availability of spectrum. Currently, 83 Spanish regions have been analysed, and the average result is close to the one shown in the Barcelona area with an average number of 14 available channels, which supposes an averaged free spectrum of 112MHz in the Spanish UHF band.

The conclusions obtained for the Region of Catalonia, but also for the current research over Spain, a larger area, makes that the results obtained in here will also be extended to European regions were the same amount of spectrum is devoted to television inside the UHF band.

Fig. 1 .

 1 Fig. 1. 2015 Catalonian UHF channel availability map made by the authors (left map) and Catalan density map (right map), white or yellow areas are for density below 50 inhabitants per square km and black or red areas for densities higher than 1000 inhabitants per square km

Table 1 .

 1 Barcelona area occupancy results

	Current	licensed	Observed	UPF	forecast
	channels Feb 2012	measurement 2012	for year 2015
	Occupied channels	18	14		25
	Occupancy percentage (%)	36,7	28,6		61,0
	Availability percentage (%)	63,3	71,4		39,0
	Free channels	31	35		16
	Approximation of free channels *	27	31		12
	Availability approximation percentage (%)	55,1	63,3		29,3

Table 2 .

 2 Mega Hertz availability in WS after Digital Dividend is applied in 2015 in Catalonia

		Rural	Urban
	MHz available per inhabitant	2.26 to 0.80 MHz/person 0.11 to 0,05 MHz/person
	Inhabitants in each Km 2	50 to 150 inhabitants	1000 to 2000 inhabitants
	Channels available in 2015	15 to 16 channels	12 to 14 channels

Table A .

 A Barcelona channel occupancy analysis. A number 1 in the grid identifies occupation

	Channel	Video frequency	Barcelona Licensed	Observed measures
			2012	2012

Industrial Scientific and Medical radio bands defined by the International Telecommunication Union Radiocommunication -ITU-R. European, Region 1, UHF IMS band is set at 433.05 to 434.79 MHz

Map extracted from "Anuari Estadístic de l'Institut Cartogràfic de Catalunya", by C. Marti and J. Feliu. and created with data from 2007.

Acknowledgments. This work was partially supported by the Spanish government and by the European Commission through the projects GEPETO (TEC2008-06055/TEC) and Commons for Europe (CIP-ICT-PSP-2011-5-297191), respectively.

Appendix: Methodology example

This Appendix is an example of our methodology and how we have assumed the possible 2015 spectrum availability. We have taken into account three different columns. The first one is the official licensed channels occupancy that would be the official database. The second column exposes the values obtained with measurement equipment at UPF on February of 2012 that would act as cognitive equipment. The last column relates our approximated channel availability, also considered as a forecast of occupancy for 2015.


Christiaan Ottow

Frank Van Vliet

Pieter-Tjerk De Boer

Aiko Pras
email: a.pras@utwente.nl

Frank Van Vliet
email: frank.vanvliet@pine.nl

The Impact of IPv6 on Penetration Testing

Keywords: IPv6, security, penetration testing, host discovery, transition mechanisms

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

Introduction

IPv4 address space is nearing depletion in some regions [START_REF]APNIC IPv4 address pool reaches final /8[END_REF][START_REF] Ncc | IPv4 exhaustion[END_REF] and adoption of its successor, IPv6, is increasing [START_REF] Huston | Active BGP entries (FIB)[END_REF]. At recent security conferences, security researchers have discussed flaws in both the IPv6 protocol and its implementations [START_REF] Atlasis | Attacking ipv6 implementation using fragmentation[END_REF][START_REF] Gont | Results of a security assessment of the internet protocol version 6[END_REF][START_REF] Heuse | Recent advances in IPv6 insecurities[END_REF]. Since IPv6 replaces IPv4 as network layer protocol, future network security activities can also be subject to change. Penetration testing is one such activity; companies that provide penetration testing services need to know how to change their process in order to perform penetration tests on IPv6 targets.

In this paper we will answer the following question:

"How will the use of IPv6 change remote penetration testing of webapplications and servers?"

Penetration testing can be performed in many ways, from physically breaking into structures to social engineering attacks and the hacking of web applications. Although there are some efforts [START_REF] Herzog | The Open Source Security Testing Methodology Manual[END_REF][START_REF]PTES: The Penetration Testing Execution Standard[END_REF][START_REF] Scarfone | Technical guide to information security testing and assessment[END_REF] to standardize the process of penetration testing, none of them is commonly accepted as such. We therefore base our discussion on the case study of Pine Digital Security. Pine is a company in the Netherlands that performs remote penetration testing on web applications and servers. They use public checklists of vulnerabilities, combined with clear defined methods to check for each vulnerability on those checklists. This results in a penetration testing process that can be used in this research to determine the impact IPv6 will have.

The following sub-questions will be used to answer the main question:

-What components of the current penetration testing process need to be changed for IPv6 targets? -What new components can be added to the penetration testing process for IPv6 targets?

The first sub-question concerns how the current penetration testing process is affected when IPv6 is used: what components need to be modified in order to achieve their goal, or can be removed because they become obsolete. For each component of Pine's penetration testing process, the performed activities are examined to determine how they are affected by a change to IPv6. This is done by analyzing the dependencies of every action performed, to see if functions specific to IPv4 are relied upon. A suggestion for removal from the process or modification is made per activity that is found to be affected. By following this approach, we determine what components of the current penetration testing process are affected, but we do not discover new additions.

The second sub-question concerns what new vulnerabilities IPv6 introduces that are not currently tested for in Pine's penetration testing process. From existing literature and community sources such as protocol standards, conference presentations and weblogs, we collect documented IPv6 vulnerabilities. When these would be applicable within the scope of penetration testing as defined in this research (see Section 2), we propose a check for them as an addition to the process.

In the next section, we discuss our choice of Pine as a case study and Pine's penetration testing process. Components of this process that should be modified for IPv6 or can be removed are discussed in Section 3. Section 4 discusses proposed additions to the process. Finally, conclusions and suggestions for future work are presented in Section 5.

Backgrounds on Penetration Testing and the Case Study

In this section we discuss our choice of case study and describe their process of penetration testing for servers and web applications. Pine Digital Security performs various security services to companies, among which penetration testing. Penetration testing at Pine is described as finding vulnerabilities in servers and web applications using checklists of vulnerability classes, from the perspective of certain types of attackers. Most often this is the perspective of an outsider at a remote location (somewhere on the Internet). Vulnerabilities qualify if they can be used to compromise the confidentiality or integrity of the protected assets. This implies that the penetration test does not focus on availability, although exceptions are made for availability vulnerabilities that can be exploited without large force, and that can be tested for in a nondestructive manner.

The process of penetration testing at Pine follows the phases described by several sources [START_REF] Scarfone | Technical guide to information security testing and assessment[END_REF][START_REF] Wai | Conducting a penetration test on an organization[END_REF]: planning, execution, post-execution. In the planning phase, apart from commercial activities, an assessment of the customer's systems and risks is made to determine the test targets and scope. Sometimes it is necessary to perform host and service discovery on the target to determine the size of the attack surface. In the execution phase, the penetration tester finds and exploits vulnerabilities in the targets, making sure that every vulnerability on the applicable checklists is checked for. Discovery and attack are executed in cycles, as described in [START_REF] Saindane | Penetration testing -a systematic approach[END_REF]. In the post-execution phase, the results are formulated along with recommendations for mitigation, and are discussed with the client. Cleaning up and quality assurance also take place in this phase.

Pine is representative as a case study of remote penetration testing of web applications and servers. Since Pine uses public [START_REF]Certified Secure: Certified Secure Checklists[END_REF] checklists and the description of their penetration testing process is available, the impact that IPv6 will have can be determined in a structured way. As described, the phases of Pine's penetration testing process follow a recognized model. The checklists have been assembled by independent security experts with years of penetration testing experience. They contain the most prevalent security issues such as those from the OWASP Top Ten [START_REF]OWASP[END_REF] and those exploited by popular automated testing tools, as well as lesser-known issues.

Impact of IPv6 on the current penetration testing process

In this section we discuss the components of Pine's current penetration testing process that either need to be changed in order to be applicable to IPv6, or become obsolete and can be removed from the process. We go through the three phases described in the previous section, and discuss the activities that take place. For each of these activities, we analyze its dependencies to see if it relies on features specific to IPv4. We only discuss those items that would need change or can be removed.

Preparation phase

In the preparation phase, little activity involving the target systems of the penetration test takes place. Normally the customer will give an exact list of IP addresses that form the scope of the penetration test. When the customer however gives a network range instead of an exact list, a scan to detect the number of hosts in a network needs to be performed.

Host and service discovery When performing host discovery in a subnet, all TCP ports and some UDP ports on all hosts are probed. This is done since many hosts do not respond to various kinds of alive polls (like ping requests), but do offer services on some ports. Alive detection can stop once a proof of aliveness is received from the server. A server without firewall will respond to a TCP connection request to a closed port by sending a TCP packet with the RST flag set, which indicates its aliveness. However, many servers have firewalls that are configured to ignore connection requests to all ports by default, and make exceptions for ports that are on a whitelist. In this case, scanning will have to continue until the first whitelisted port is probed, which will evoke a proof of aliveness from the server in the form of a TCP packet with either the SYN and ACK flags or the RST flag set. Scanning in this case can take very long since the scanner cannot distinguish a lost transmission from a dropped one and has to retry probes multiple times after waiting for a timeout.

This type of scanning is especially problematic in IPv6 networks [START_REF] Chown | RFC 5157: IPv6 implications for network scanning[END_REF][START_REF] Vyncke | IPv6 Security[END_REF] because of the large IP space typically in use. The standardised netmask size for an IPv6 subnet is 64 bits, leaving 64 bits for numbering hosts [START_REF] Hinden | RFC 4291: IP version 6 addressing architecture[END_REF]. To scan those 64 bits of address space as described would take an infeasible amount of time: 28 years under conditions that favor the scanner [START_REF] Vyncke | IPv6 Security[END_REF]. Therefore, exhaustive scanning of all addresses in the network is infeasible within the scope of a penetration test, unless an extremely small prefix has been given.

There are alternatives to exhaustive scanning. Address information can often be retrieved from external sources such as the Domain Name System (DNS) and online directories. Several websites track changes in WHOIS and DNS, and map virtual hosts to IP addresses. Other services index networks by found services. Address information can be taken from these websites. DNS can be used in multiple ways to find addresses. Some servers allow AXFR queries that enable an attacker to download the whole zone. Guessing hostnames using wordlists can also be used. When DNSSEC is used, both NSEC and its successor NSEC3 [START_REF] Laurie | RFC 5155: DNS security (DNSSEC) hashed authenticated denial of existence[END_REF] offer possibilities to enumerate zones [START_REF] Bernstein | Breaking dnssec[END_REF]. Additionally, the tree of PTR records can be queried to find addresses that are in use when the nameserver returns NOERROR for empty non-terminals. This behavior is RFC-compliant, and implemented by most nameservers [START_REF] Van Dijk | Finding v6 hosts by efficiently mapping ip6.arpa[END_REF]. PTR records need to be configured for this enumeration technique to work however, which is not the case in all networks.

Furthermore, assumptions can be made about address assignment policies. Different sources suggest that servers and routers are usually numbered through manual assignment or DHCPv6, not using SLAAC or privacy extensions [START_REF] Gont | Results of a security assessment of the internet protocol version 6[END_REF][START_REF] Heuse | Recent advances in IPv6 insecurities[END_REF][START_REF] Malone | Observations of IPv6 addresses[END_REF]. In fact, DHCPv6 and manual assignment are even recommended [START_REF]SURFnet: IPv6 numberplan[END_REF]. Research indicates that manual assignment is often based on sequential numbering, numbering with the service port (e.g. assigning an address ending in ::80 to a webserver), wordiness (using hexadecimal characters to form words) and IPv4 addresses in IPv6 addresses. Since the focus of our host discovery is on servers and web applications, manual assignment and DHCPv6 are expected to be prevalent among the targets [START_REF] Chown | RFC 5157: IPv6 implications for network scanning[END_REF][START_REF] Heuse | Recent advances in IPv6 insecurities[END_REF]. To find alive hosts, one could assume that these schemes are used for assignment, and guess what other addresses are in use. Based on given or found addresses, address ranges can be found in which sequential numbering, hex-word, service port and IPv4-address based addresses are in use. For each of the suggestions that this "smart guessing" algorithm generates, alive detection needs to be performed. For a small number of suggestions, traditional alive detection could be performed by scanning all TCP and UDP ports. As the number of suggestions increases, this approach becomes less feasible. A limited number of ports could be probed, alongside generic methods (ICMP ping for instance).

An algorithm using the above methods for "smart guessing" cannot guarantee to find all hosts in a network. If a host has a DNS record that is not easily guessable or no DNS record at all, and has an unpredictable IPv6 address, it may not be found. An early test with such an algorithm reports finding 90-95% of servers on public networks [START_REF] Heuse | Vulnerabilities, failures -and a future[END_REF]. If a guarantee is required that 100% of the hosts have been included in the test, the only option as of yet is to require an exhaustive list of IP addresses from the customer.

Execution phase

In the execution phase, the penetration tester attempts to hack the targets and makes sure that each vulnerability on the checklists is checked for. Pine has defined methods for each check, and has documented tools that can be used. These tools are free, commercial or in-house developed. In order to use the tools on IPv6 targets, they need to have basic IPv6 support that includes specifying IPv6 hosts, resolving names to IPv6 addresses and transmitting data over IPv6 sockets. This is a change that affects every tool used, and will not be mentioned separately for every checklist item.

DNS information gathering

In two items on the checklists, the Domain Name System (DNS) is queried for (possibly sensitive) information. The goal is not host discovery as was covered in the previous section, but to check if the DNS contains information that should not be stored there, and if the nameservers don't leak the entire zone to attackers. These items are checked by querying the nameservers for the domains in scope, and attempting to download the complete zone (AXFR) or failing that, find certain hosts by guessing hostnames. Reverse hostnames of known IP addresses are resolved as well.

A target that uses IPv6 might have nameservers that are accessible over IPv6, and might have AAAA records in associated zones. The checklist item can remain the same, but the procedure for testing should be changed to include checking both the IPv6 addresses and IPv4 addresses for the nameservers, as they might point to different systems. For all records that are resolved, both the AAAA and A records should be queried. Reverse lookups for both IPv4 and IPv6 addresses should be performed. Wordlists used for brute-force guessing of system names should be updated to contain names relevant to IPv6, such as words containing "ipv6" and the names of popular transition mechanisms such as Teredo and ISATAP.

Fragmentation to bypass firewalls Fragmentation in IPv6 works similar to fragmentation in IPv4. In IPv6 however, fragment information is transmitted in an extension header that is only present when an IP packet is a fragment, and only end nodes perform fragmentation and reassembly.

Fragmentation attacks in IPv4 have been known for years. RFC 1858 [START_REF] Ziemba | RFC 1858 -security considerations for IP fragment filtering[END_REF] describes two attacks that can be used to bypass firewalls using fragmentation: tiny fragments and overlapping fragments. The RFC also suggests mitigations against these attacks.

In the case of tiny fragments, the packet that contains the first step of the TCP handshake (SYN flag) is fragmented across two packets such that the SYN flag, which is at the end of the TCP header, falls within the second fragment. A firewall that tests if a packet constitutes a TCP connection request, will not be able to judge this having just the first fragment. It is possible that no rule will be matched, and the packet let through. The suggested mitigation against this attack is to discard fragments smaller than a minimum size to make sure the TCP flags always fall in the first fragment.

Overlapping fragments can be used to smuggle a connection request past a firewall as well. The first fragment can contain a TCP header with a certain source and destination port but no SYN flag. The firewall may allow this fragment to pass since it is not a connection request. The offset of the second fragment can be tailored to cause reassembly to overwrite the flags field of the TCP header with the data from the second fragment. In this second fragment, a flags field could be set that includes a SYN flag. The firewall might allow the fragment through since it is not the first fragment, while the host reassembling the packet (and parsing the overlap in a favorable way) will read a connection request. The suggested mitigation is to drop fragments with an offset value of 1, since higher offsets do not cause the flags field to be overwritten.

The original IPv6 specification allows overlapping fragments. A later RFC [START_REF] Krishnan | RFC 5722 -Handling of overlapping IPv6 fragments[END_REF] forbids overlapping fragments, but as this is a relatively recent change, not all implementations follow it. As for tiny fragment attacks, many IPv6 implementations accept non-last fragments smaller than 1280 bytes [START_REF] Atlasis | Attacking ipv6 implementation using fragmentation[END_REF]. Additionally, the IPv6 specification dictates that extension headers occurring any number of times in the same packet must be parsed. This requirement can be used to fill a first fragment with extension headers, and put the TCP header in the second fragment. Many implementations already follow a proposed standard [START_REF] Gont | Security and interoperability implications of oversized ipv6 header chains[END_REF] the specifies that all headers, including the upper layer header, must be in the first fragment. This mitigates the tiny fragment attack, but is not the standard yet. Other solutions to the tiny fragment problem are being discussed in [START_REF] Manral | Tiny fragments in ipv6[END_REF].

When using fragmentation attacks in IPv6, extension headers can be used as described above in addition to the known IPv4 methods.

Evaluation phase

In the evaluation phase, the report is written and discussed with the customer. This report includes recommendations for mitigation of the found vulnerabilities.

Like the checklist items, these recommendations may have to change to achieve their goal on an IPv6 target.

Automated attacks

The recommendation made by Pine against brute-force attacks is to implement an anti-automation measure in the form of rate-limiting or CAPTCHA solving, based on the client's IP address. Several items on the checklist have this recommendation, for instance those that check for bruteforcing user names and passwords or spamming via feedback forms.

This recommendation works in an IPv4 world where an IP address can be assumed to identify a user, since most users have at most one address per person at a point in time. With IPv6 however, a standard network has a 64-bit netmask (a "/64"), and a standard end-user assignment is a multiple of that [START_REF] Narten | RFC 6177 -IPv6 address assignments to end sites[END_REF]. An organization is likely to receive a /48, while a home user is more likely to receive a /56. Since March 2011, the exact allocations are left up to the ISP and are no longer defined in an RFC [START_REF] Narten | RFC 6177 -IPv6 address assignments to end sites[END_REF]. In any case, an attacker has a very large IPv6 address space compared to the IPv4 situation. Therefore, acting on a single IP address is not enough: the attacker can change IP addresses very often to circumvent anti-automation measures.

We suggest using a "smarter" algorithm for anti-automation measures, that takes into account the large address space an attacker has. This algorithm is based on "taint" actions: actions that are a trigger to the anti-automation system, such as a failed login attempt. After a defined number of taints in a /64, the whole /64 is blocked. Say the attacker has multiple /64 ranges, he can use multiple to begin with, or move to the next after the first has been blocked. Therefore, a threshold is also set for a /56, for a /48, and so on. After each taint, the algorithm checks for all prefix sizes if its taint threshold has been reached. If so, the prefix can be added to a blacklist.

Session hijacking Another recommendation that needs to change, is the recommendation made for web applications to allow the use of a session from only one IP address. Pine recommends that when a session is started (a session identifier is generated and sent to the user), the IP address of the user is stored on the server along with the session. Upon each subsequent request with that session identifier, the server checks if the IP address where the request came from is the same as the stored IP address. If not, access to the session is denied.

With IPv6, privacy extensions [START_REF] Narten | RFC 4941: Privacy extensions for stateless address autoconfiguration in IPv6[END_REF] are often used for end-user systems [START_REF] Kaps | Ipv6: Privacy extensions einschalten[END_REF]. The addresses that are generated have a limited preferred lifetime, which means they are used for outgoing connections for a limited time of often only hours. When the preferred lifetime is over, a new address is generated and the address is not used for outgoing connections anymore.

The described behavior poses a problem for session management according to Pine's recommendation. A user may use different addresses for his requests to the web application during his session, since sessions typically run for longer than a few hours. Therefore, the IP address cannot be used to lock the user's session anymore. The /64 prefix in which the random addresses are generated, remains constant in the address, but may be used by many more users. A tradeoff has to be made between usability and security: if the current recommendation is applied to IPv6, users with privacy addresses will have trouble using the web application. If the /64 prefix is used, abuse of the session by remote attackers is prevented, but attackers on the same LAN may still hijack the session. With IPv4 this situation often already exists, since many networks use NAT, which results in a network segment having one external address.

We recommend tracking the session using the /64 prefix. The measure is for defense-in-depth: stealing of the session identifier should be made impossible by other means such as proper output escaping to prevent Cross-site Scripting (XSS), the use of SSL and setting proper flags on session cookies. Additionally, in IPv4, many users share the same public IP address with the whole LAN already, so the use of the IPv6 /64 does not offer less protection.

Additions to the penetration testing process

In this section we describe additions that should be made to the penetration testing process, based on existing literature, protocol standards and community sources. Proposed additions need to be within our scope of penetration testing. As such, vulnerabilities that are specific to the LAN (such as Neighbor Discovery and Multicast Listener Discovery vulnerabilities) are not considered, since they cannot be abused from a remote perspective. Vulnerabilities that can only be used for denial of service attacks and cannot be tested for in a non-destructive manner are out of scope as well.

Using extension headers to bypass router ACLs

Extension headers in IPv6 packets are placed between the fixed-size IPv6 header and the payload. The IPv6 standard dictates that any number of extension headers must be processed by receiving nodes.

Most routers can enforce packet filtering policies based on Access Control Lists (ACLs). Filters are usually composed of not only source and destination IP address, but also TCP/UDP ports and flags. To read this information, the router needs to read past the complete IP header in the packet, including extension headers. High-end routers achieve high throughput by implementing the forwarding plane (where ACL checking takes place) in hardware instead of in software. This hardware has a fixed-size view on the packet: often only the first 64, 128 or 256 bytes are evaluated to make a routing or policy decision [START_REF] Ytti | IPv6 ACL bypass[END_REF].

This limited packet view can introduce a security problem. A packet can have so many extension headers that the upper layer header is moved outside of the view of the forwarding plane, meaning that the information required for a policy decision is not available. Some routers choose to pass such a packet on to the control plane, which is software-based and can handle dynamic lengths. Others just let the packet pass [START_REF] Ytti | IPv6 ACL bypass[END_REF], which provides an easy way to bypass policy enforcement.

An addition should be made to the checklists for checking whether adding a large number of extension headers leads to bypasses ACL restrictions as described above.

Unintended exposure due to transition mechanisms

Various mechanisms have been defined to ease the transition from IPv4 to IPv6. Some of these transition mechanisms provide automatic tunneling for hosts that want to use IPv6 in an IPv4-only network. These mechanisms are either based on existing IPv4 tunneling techniques such as IP-in-IP and GRE or encapsulating IPv6 packets inside layer 4 protocols such as UDP.

Hosts that are not reachable by a global IPv4 address, might become globally reachable over IPv6 by the use of these transition mechanisms. This poses a security risk [START_REF] Davies | IPv6 transition/coexistence security considerations[END_REF][START_REF] Gont | Security implications of ipv6 on ipv4 networks[END_REF]. An addition should be made to the checklists to check for the reachability of hosts in the target network using IPv6 transition mechanisms. This could be achieved by performing alive detection on guessed addresses, based on assumptions about the transition mechanism used. Assumptions about the addresses can be made when ISATAP, Teredo or 6to4 are in use, since these transition mechanisms use predictable information in the IPv6 addresses that are generated.

ISATAP ISATAP is used to provide hosts in a network with IPv6 support, while not migrating the entire network to IPv6. The network itself must have an IPv6 prefix routed to it, but not all infrastructure inside the network needs to support IPv6. The IPv4 network is used as a link layer for IPv6. Hosts in the network use the IPv6 prefix combined with their own IPv4 address v4addr to generate an IPv6 address, that ends with the 48 bits :5efe:v4addr.

If the network prefix is known, for instance from other IPv6 enabled hosts or a WHOIS service, the generated IPv6 addresses can be guessed based on the IPv4 addresses that are in use. Private IPv4 addresses can even be accessed using this method: if a host has IP address 10.0.0.2 on the LAN and it uses ISATAP in prefix 2001:db8::/32, it will have IPv6 address 2001:db8::5efe:a00:2 (0a00:0002 is 10.0.0.2 in hexadecimal notation) which is globally reachable by default.

6to4 A host that has IPv4 address v4addr can have the prefix 2002:v4addr::/48 routed to it by setting up a 6to4 tunnel. By substituting known IPv4 addresses of the target into 2002:v4addr::/48, prefixes are acquired wherein host discovery can be performed.

Teredo Teredo addresses contain more variables than just the v4addr, such as the UDP port number. By making assumptions about these variables, addresses could be guessed. However, since there are 2 16 possible port numbers, one would need to test 2 16 2 n guesses on average, where n is the number of IPv4 addresses in use. This will very quickly become infeasible.

An addition to the penetration testing process should be made to discover hosts reachable via the 6to4 and ISATAP transition mechanisms. Within ISA-TAP prefixes, known IPv4 addresses and commonly used private ranges should be tried. Within 6to4, the IPv4 addresses of border routers in the target network should be used to generate prefixes in which host discovery can be performed.

Evading policy enforcement using routing headers

One of the IPv6 extension headers is the Routing Header (RH). There are two types of routing headers, of which RH0 (type 0) can be used to specify a list of addresses that should be visited by the packet.

This feature offers the same functionality as the "Loose Source Route Record (LSRR)" option in IPv4, and poses the same security risk. With RH0 enabled, an attacker could craft a packet that follows a certain path into a network, bypassing a firewall. Or, the destination according to the destination address could be allowed by the firewall, while the real final destination specified inside the RH0 header is not [START_REF] Abley | Deprecation of type 0 routing headers in IPv6[END_REF][START_REF] Biondi | IPv6 routing header security[END_REF]. The first destination host would then forward the packet over the internal network.

Because of the vulnerabilities identified in the RH0 functionality, the IPv6 standard was updated in 2007 [START_REF] Abley | Deprecation of type 0 routing headers in IPv6[END_REF] to deprecate RH0 extension headers. However, many IPv6 implementations already contained the RH0 functionality, and there is no guarantee that all of them have been updated to reflect the change. Therefore an addition to the penetration testing process should be made to check for firewall bypassing using RH0 headers.

Conclusions and Future Work

This paper shows that when IPv6 is used, changes to the penetration testing process are needed. Some activities need to be performed in a different way for IPv6 targets, and some new checks should be added to the process. None of the activities of the current penetration testing process need to be removed from the process.

The following elements of the process need to be changed. Host discovery by exhaustively scanning the entire IP space will not work for normal-sized IPv6 networks. We have described an algorithm that combines different sources of address information with assumptions about address assignment, to replace exhaustive scanning. DNS information gathering should be changed to also search for IPv6 (AAAA) records, and include IPv6-specific wordlists. Fragmentation attacks that aim to bypass firewalls should be changed to include IPv6-specific fragmentation attacks. Recommendations for mitigation of vulnerabilities are also affected: brute-force attacks cannot be stopped by blocking single IPv6 addresses. We described an algorithm that takes into account the address space an attacker may have. Furthermore, users cannot be expected to keep the same IPv6 address throughout the lifetime of their session, so the user's network prefix must be taken into account when restricting access to the session.

Additions to the penetration testing process should be made to target several IPv6-specific vulnerabilities. The use of IPv6 extension headers in general allows for router ACL bypassing on some systems. If Routing Headers are allowed, firewalls might be bypassed as well. When certain transition mechanisms are in use, internal systems may be directly accessible to attackers. Additions to the checklists are proposed for these IPv6-specific vulnerabilities.

Using Pine's penetration testing process provided us with a structured way to examine the impact IPv6 may have, but may not be applicable to penetration testing as performed by others than Pine. As future work, the impact of IPv6 on other forms of penetration testing, such as Local Area Network penetration testing, could be investigated. Future research could also verify our findings by performing penetration tests on IPv6 targets with the checks and algorithms proposed here.

Acknowledgements The authors would like to thank Peter van Dijk, Frank Kargl and Job Snijders for their valuable feedback and suggestions, and Pine Digital Security for their support of this work.


Péter Megyesi
email: megyesi@tmit.bme.hu

Sándor Molnár
email: molnar@tmit.bme.hu

Finding typical Internet user behaviors

Keywords: Internet, user behavior, traffic analysis

In various network tests we often need to use different trace files in order to get the most comprehensive result. This procedure requires multiple input files which were generated in different ways. In this paper we suggest a method for analyzing a traffic measurement and extracting the most typical user behaviors. We introduce the Traffic Descriptive Strings (TDS) which is a projection of measurement data. We present an algorithm which is able to score the similarities between two TDSs.

Introduction

Testing various network devices often leads to a point where captured trace files have to be used. The choice of the right input raises the question of using traces which are available on the Internet for everyone or generate them manually. The first method is usually useful at final stage of testing for making the results comparable. The second technique is applied at early stages during the tuning of the different parameters as the usage of manually generated trace files have the benefit that we know what the input contains, therefore we know what to expect as a result. However, in order to create the most general and realistic input files we have to know the usual way of how users use the Internet.

In this paper we present a method for extracting typical user behaviors from Internet traffic measurements. We introduce the Traffic Descriptive Strings (TDS) which are a projection of traffic measurements and can be used for representing a user's traffic stream. We have implemented a scoring scheme which is able to evaluate the similarities between two traffic streams represented by TDSs. This scoring scheme is used by an algorithm which is able to find the most similar typical user behavior for any given TDS. Our method is novel since according to our knowledge the current literature lacks methods representing user traffic by such string descriptors.

In the next section we discuss the general way of creating Traffic Description Strings from a traffic measurement report. Section 3 presents the algorithm which is able to extract typical patterns from a measurement results converted into TDSs. In Section 4 we present the TDS scoring scheme and we give some examples for its result using an artificially created database. Finally, we summarize our work in Section 5.

Traffic Descriptive Strings

During the creation of the Traffic Descriptive Strings we have to run a traffic classification algorithm on the input raw measurement. The efficiency of the various traffic classification algorithms covers a wide range, but Deep Packet Inspection (DPI) solutions tend to generate the best results. DPI is a form of classification that also examines the data part of the packets not just the headers. Although the source of the most sophisticated industrial DPI tools are closed to the public, there are many open source DPI projects [START_REF]Open source Deep Packet Inspection projects[END_REF]. One of the most popular open sourced DPI is OpenDPI.

OpenDPI is the open source version of Ipoque's DPI engine [4]. Ipoque is a provider of DPI solutions for internet traffic management and analysis. OpenDPI supports most of today's popular network protocols [START_REF]OpenDPI manual[END_REF].

Before the processing of the report generated by the traffic classification tool, the definition of the traffic classes has to be made. This process is highly dependent on the classification tool we use since the application might not be able to distinguish certain traffic classes we have defined. In the followings we will use the traffic classes found in Ipoque's Internet study [START_REF] Schulz | Internet Study 2008/2009[END_REF] as these classes are also distinguishable by OpenDPI. Thus the defined traffic classes can be found in Table 1 where we have assigned a character to each of them. After the definition of the traffic classes the creation of the Traffic Descriptive Strings is implemented as follows. Firstly, a time resolution has to be chosen. This will serve as a time interval that the algorithm parcels the measurement. Each time slot will be handled independently, thus the choice of the resolution has to be adjusted for the required results. A too short time interval can result in an output where typical patterns are not extractable. On the other hand, using a too long time unit could hide the differences between distant inputs. In our early tests we chose this time resolution to one minute. However, this decision will be further investigated based on the range of human user reactions with controlled applications.

As a next step, we disassociate the input to individual users in case of an aggregated measurement. Then the algorithm examines for every user that which of the defined traffic classes were used in every time slot. If the transmitted data of one traffic class is larger than a given limit (e.g. 100 Kbytes) its character is written into the Traffic Descriptive String of the user. We separate the time slots with the semicolon character. Thus a suitable input format for the typical user behavior extractor algorithm is given in Figure 1. The example in Figure 1 describes three users for 12 time units (12 minutes in our example); the first user was running a peer-to-peer file sharing client while browsing the Internet; the second one was using a VoIP and a gaming application simultaneously; and the third user was streaming online media content. We also add the UNIX timestamp of the beginning of the given user's activity for possible future processing.

Extracting typical user behaviors

During the extract of typical behaviors we tend to find frequently occurring shorter term periods in the input. In this procedure the algorithm examines every fixed time length patterns between a lower and a higher time limit. The reason for the lower limit is that too short time periods wouldn't generate stabile traffic. For example, if a torrent client runs for only one minute the number of the peer-to-peer connections wouldn't reach its maximum value. On the other hand, the longer a pattern is the lesser it would occur in the traffic stream. In our test we have defined the lower limit in 4 minutes and the higher limit in 10 minutes.

As a first appealing solution we have inspected existing motif finding methods used in bioinformatics problems. In bioinformatics algorithms tend to find similarities in protein chains. These algorithms usually use a simple string input which contains the markings of the four proteins: A for Adenine, T for Thymine, G for Guanine and C for Cytosine. Thus the principal of the task is the same: finding typical motifs in a string array. The idea of using bioinformatics algorithms for motif finding is presented in [START_REF] Szabó | Automatic Protocol Signature Generation Framework for Deep Packet Inspection[END_REF]. In this paper the authors present a framework using Glam2 for signature generation. Glam2 is a software package for finding motifs in sequences, typically amino-acid or nucleotide sequences [START_REF]Glam2 manual[END_REF]. Glam2Scan is a part of the Glam2 software package which can find matches in a sequence database to a motif discovered by Glam2 [START_REF]Glam2Scan manual[END_REF]. Glam2Scan gives a score for each match indicating how well it fits the given motif so it also could be the base an approximately match algorithm.

We have examined the possibility of applying the same architecture presented in [START_REF] Szabó | Automatic Protocol Signature Generation Framework for Deep Packet Inspection[END_REF] with a different preprocessing method. However, after a long investigation process we have found that this technique is not appropriate for our work. The main reason behind this is that bioinformatics algorithm use alphabet where the role characters are the same. In a Traffic Descriptive String the time delimiter semicolon character has completely different meaning than the others. Moreover, in our case we would like to have a flexible method for defining suitable replacements for certain traffic classes (e.g. assigning different characters for applications which generates the same type of traffic, but we would like to distinguish them in the result, such as web browsers) and also complete exclusions (e.g. give low score when replacing web to P2P).

Thus we implemented a unique algorithm for the Traffic Emulation Tool which can extract typical user behaviors from the input files. Firstly, it filters out the long idle periods (multiple consecutive semicolon characters) from the input thus the results won't contain patterns in which the idle period is longer than the active period.

Secondly, for symmetric TDS patterns (where the same characters occur in every time unit) the algorithm recalculates the real number occurrences by dividing the total run length with the time length of the pattern.

In the algorithm two limits have to be declared: a hard limit and soft limit. Firstly, the tool counts the occurrences for every occurring TDS substring which has the given time length. Then the algorithm discards patterns below the soft limit. After that, following iteration is repeated. The algorithm calculates the most similar pattern for the substring which occurrence is equal to the soft limit using the scoring mechanism presented in Section 4 and increases the result's occurrence by the soft limit. Then the soft limit is increased by one. This procedure is repeated until the soft limit reaches the hard limit. After that, the remaining TDS substrings occurring more than the hard limit are added into the typical behavior pool.

The choice of the limits is dependent on the result we would like to achieve. For example, setting the two limits to the same value will avoid the usage of the scoring mechanism and result in only the TDSs which occurrence is greater than then the given hard limit. On the other hand, setting the soft limit to 1 will give the most detailed result but it can significantly increase the run time of the algorithm.

The TDS scoring algorithm

When we were designing the TDS scoring algorithm the following rules were laid down:

1. If we compare an A string to a B string, the returned score must be less than or equal to score the algorithm returns comparing the A string with itself. 2. The equality must only stand if the same characters with the same amount are in both A and B. 3. The algorithm must inspect the time length of the TDSs and give lesser score if it differs. 4. We must have a way of setting unique values for which traffic types are suitable substitutions for each other and which are completely excluded.

Taking these considerations into account, we have defined a scoring matrix labeling its rows and columns with the defined traffic classes' characters. We also add the "X" character which will refer to no action. If we substitute an "A" character from the first string to a "B" character in the second string the score under the "A" row and "B" column will be added to the total score. Firstly, the algorithm concatenates "X" characters to the shorter string until both of them contain the same amount of characters. After this, a dynamic programming algorithm finds the best substitution solution for the characters calculating the maximal possible score [START_REF] Megyesi | Matching Algorithm for Network Traffic Descriptive Strings[END_REF], [START_REF]Dynamic Programming[END_REF]. As the last step the algorithm modifies the given score with a divider if the time lengths of two strings differ.

In order to get the most ideal values of the scoring matrix and the length modifier we created a test database of Traffic Descriptive Strings. In contrast with the typical user behaviors this artificial database contains only TDSs in which the actions are the same in every time slot. We integrated every variation of minimum four maximum ten time unit long scenarios which contains maximum 4 classes of traffic simultaneously.

An example for the scoring matrix can be found in Table 2. The ideas behind the definition of the individual values were the followings. The values in the "X" row represent the scores given for extra traffic. These numbers have to be negative otherwise the first rule wouldn't apply. Here we give lesser values for classes with higher bandwidth as adding them into the traffic stream would suppress the others. Similar considerations were made for the values in the "X" column. These numbers represents the absence of a class without substitution. Here we also give lesser values for the classes with higher bandwidth as their absence from the traffic stream would make the dominant flow disappear. The other values in the main diagonal are set to 4 thus if a character is substituted for itself the algorithm gives 4 points. The remaining values in the matrix are close to zero. The main reason for this idea is that these traffic classes are fairly different from each other thus none is a suitable replacement for another. However, a slight preference sequence can be given by small values. Two examples are given for the result in Table 3 andTable 4. In these cases we allow one minute time different between the compared strings and divide the final score the by 1.2 if the time difference consists. In both table the 0 th row shows the score with the input itself. In case of Table 3 the input was a six-minute-long VoIP activity. Since this is a symmetrical TDS this string is in the test database thus the most similar pattern is itself. As the results show, the second most similar TDS is the seven-minute-long VoIP activity. After that the given scoring scheme prefers the addition of low bandwidth classes, the Instant messaging (E) and the Standard protocols (G).

X A B C D E F G H X 0 -3 -2 -3 -2 -1 -2 -1 -2 A -3 4
In case of Table 4 the input was again a six-minute-long activity, but here the first three minutes contained VoIP while last three Streaming. In the results we can see that the six-minute-long only VoIP and only Streaming got the same amount of points being equally similar to the input. The next two results are the simultaneous VoIP and Streaming, the five-minute-long in the 3 rd place while the six-minute-long in the 4 th place. The reason for this succession is that even thought the five-minute-long TDS is shorter in time, but the sum of the generated traffic would be closer to the input. These examples describe one possible way of choosing the scoring values. If we would like to prefer e.g. the longer scenarios against the additions, we could easily adjust the values for our purpose. The adjustment of the scoring values from different point of views can be found in [START_REF] Megyesi | Matching Algorithm for Network Traffic Descriptive Strings[END_REF].

Conclusion

In this paper we introduced the Traffic Description Strings (TDS) which is a projection of traffic measurement result. We have presented an algorithm which is able to extract typical user behaviors from real traffic measurement. This method uses a unique scoring scheme which is able determine similarities between two arbitrary given TDSs.

The knowledge of the typical way of how users use the Internet could benefit us in several ways. For example, we can generate up to date trace for various testing purposes since we know in which combinations the different type of applications have to be launched.

  1223378304 AB;AB;AB;AB;AB;AB;AB;AB;AB;AB;AB;AB; 1223378343 DH;DH;DH;DH;DH;DH;DH;DH;DH;DH;DH;DH; 1223378892 C;C;C;C;C;C;C;C;C;C;C;C;

Fig. 1 .

 1 Fig. 1. Measurement results converted into TDS format.

Table 1 .

 1 Defined traffic classes.

	Traffic Class	Assigned Character	Description
	P2P	A	Peer-to-peer file sharing
	Web	B	Web browsing incl. file download
	Streaming	C	Audio and video streaming
	VoIP	D	Voice over IP
	IM	E	Instant messaging
	Tunnel	F	Encrypted tunneling protocols
	Standard	G	Legacy Internet protocols
	Gaming	H	Multiplayer and network games

Table 2 .

 2 Example for the scoring matrix.

Table 3 .

 3 Scoring algorithm, example 1.

	#	score	ratio	time length	TDS
	0	24	1	6	D;D;D;D;D;D;
	1	24	1	6	D;D;D;D;D;D;
	2	18.33	0.76	7	D;D;D;D;D;D;D;
	3	18	0.75	6	DG;DG;DG;DG;DG;DG;
	4	18	0.75	6	DE;DE;DE;DE;DE;DE;
	5	15	0.62	5	D;D;D;D;D;

Table 4 .

 4 Scoring algorithm, example 2.

	#	score	ratio	time length	TDS
	0	24	1	6	D;D;D;C;C;C;
	1	12.6	0.52	6	D;D;D;D;D;D;
	2	12.6	0.52	6	C;C;C;C;C;C;
	3	11.66	0.48	5	CD;CD;CD;CD;CD;
	4	9	0.37	6	CD;CD;CD;CD;CD;CD;
	5	8.83	0.36	7	D;D;D;D;D;D;D;

Acknowledgments. The authors would like to thank Dr. Géza Szabó, TrafficLab, Ericsson Research Hungary for his contribution and constant support for this project. This research was supported by OTKA-KTIA grant CNK77082.