Shaoying Cai
email: shaoyingcai.2009@smu.edu.sg

Yingjiu Li
email: yjli@smu.edu.sg

Yunlei Zhao
email: ylzhao@fudan.edu.cn

Distributed Path Authentication for Dynamic RFID-Enabled Supply Chains ⋆

In this paper, we propose a distributed path authentication solution for dynamic RFID-enabled supply chains to address the counterfeiting problem. Compared to existing general anti-counterfeiting solutions, our solution requires non sharing of item-level RFID information among supply chain parties, thus eliminating the requirement on high network bandwidth and fine-grained access control. Our solution is secure, privacy-preserving, and practical. It leverages on the standard EPCglobal network to share information about paths and parties in path authentication. Our solution can be implemented on standard EPC class 1 generation 2 tags with only 720 bits storage and no computational capability.

Introduction

Supply chain is a network involving multiple parties such as suppliers, transporters, storage facilities, distributors, and retailers that participate in the production, delivery, and sale of a product [5]. It is difficult to monitor a supply chain since the involving parties are distributed at multiple locations or even across countries. It is therefore critical to address the counterfeiting problem, where an adversary injects fake goods into a supply chain. The counterfeiting problem has become a major threat to supply chains. According to the 2011 report of International Chamber of Commerce, it is estimated that the counterfeiting accounts for 5-7% of world trade, or about 600 billion U.S. dollars per year [6]. The ratio of counterfeiting is even higher in dynamic supply chains where the involving parties and the paths of processed goods may not be fixed.

Radio Frequency IDentification (RFID) technology has been recently used to facilitate real-time monitoring of supply chains so as to thwart counterfeiting threats. Most existing solutions in industry rely on sharing and processing massive RFID information at item level collected by each supply chain party over the internet. Such solutions inevitably incur high network bandwidth (due to large volume of processed goods) and fine-grained access control (due to security requirements by different parties). It is therefore difficult, even impossible, to implement such solutions in dynamic supply chain environments, where the involving parties may not have pre-existing trust relationship for sharing their RFID information in a secure and efficient manner.

Since dynamic supply chains are prevalent in living supply chains [START_REF] Gattorna | Living Supply Chains[END_REF], we propose a new distributed path authentication scheme to thwart counterfeiting in such environment. Our scheme verifies whether a tag comes from a reliable source and has been precessed by a series of legitimate entities in a supply chain. Compare to existing solutions, our scheme eliminates the needs of sharing item-level information among supply chain parties; thus, it does not require preexisting trust relationship nor fine-grained access control. The verification of a tag's path is based on the information carried by the tag and certain auxiliary information obtained from a trusted server in EPCgloabel network, which is a standard infrastructure for RFID-enabled supply chains. While our scheme is designed for the most dynamic RFID-enabled supply chains, it is also suitable for a supply chain that has fix partnership or/and static goods processing procedure.

The challenges of designing our scheme come in two aspects. First, the tag storage is restricted to no more than 1088 bits for the most popular low-cost standard C1 G2 tags [4]. In order to prove that a tag has been processed by a series of entities, the tag should carry certain credentials generated by the entities. To avoid complicated key management at item level, a natural way is to use the entities' signatures on a tag's ID as the credentials. However, it is not practical to store all signatures and public keys on a tag as the tag's storage is limited, especially in the case that such information may continually increase as the tag goes through more entities. Our solution keeps the information stored on a tag in constant size, which is less than 1088 bits, satisfying the storage constraint for EPC C1 G2 standard tag. In our solution, an ordered multisignature scheme [START_REF] Boldyreva | Ordered multisignatures and identity-based sequential aggregate signatures, with applications to secure routing[END_REF] is adopted to generate a constant-size signature of the entities on the tag's ID. A path index is used to indicate the series of entities which have processed a tag. The index is stored on the tag instead of the entities' public keys, while the detailed information about the path is stored on a trusted server such as EPCglobal Discovery Server.

The second challenge is to reduce the communication load between an entity and the trusted server when verifying a signature. To verify a signature, an entity queries the trusted server with the index of the path. The server sends the public keys of the entities in the path to the entity. The communication load increases as the path getting longer in a naive solution. We reduce the communication load to a constant level regardless of path length in our solution. Due to the specific constructions of the underlying ordered multi-signature scheme, in our scheme, the server only needs to send an aggregated "path public key" instead of the public keys of the entities. With the "path public key", one can verify whether a signature is generated orderly by the entities in the path or not. The "path public key" even has smaller size than a single public key. In the case where a batch of tags share the same path, a verifier only needs to query the trusted server once for the aggregated "path public key" in practice.

The security of our scheme relies on the unforgeability of the underlying ordered multi-signature scheme. Our scheme is secure in a sense that an adversary cannot forge any valid tag or path. To protect the privacy of each tag, we take advantage of supply chain's batch processing property. In a batch, each tag's information is encrypted with the same key. The key is divided to several shares with a secret sharing scheme. Each tag stores a share of the key together with its encrypted information. Only authorized readers can access the whole batch of tags, recover the key and then decrypt the contents stored on the tags. Our scheme is privacy preserving in a sense that an adversary cannot identify any valid tag, or distinguish whether two valid tags have taken the same path or not. Our scheme leverages on standard EPCglobal network and can be implemented on standard EPC class 1 generation 2 tags with only 720 bits storage and no computational capability.

Background

Many protocols such as [START_REF] Li | Protecting rfid communications in supply chains[END_REF][START_REF] Song | RFID Authentication Protocol for Low-cost Tags[END_REF] have been designed to provide mutual authentication or tag authentication in RFID systems. These protocols can be used to prevent counterfeiting in supply chains. However, in order to monitor a supply chain, these proposals require the manager to access the databases of all the entities in the supply chain. Therefore, they rely on high quality network connection and fine-grained access control. These requirements are obstacles in deployment of dynamic supply chain management systems. In addition, most of the existing solutions rely on non-standard tags with certain computational abilities, such as hash operation. This will incur high cost for not using standard low-cost tags.

The most related work address the counterfeiting problem in RFID-enabled supply chains based on standard EPC class 1 Gen 2 tags. In Zanetti, Fellmann and Capkun's scheme [START_REF] Zanetti | Privacy-preserving Clone Detection for RFIDenabled Supply Chains[END_REF], the entities cooperate together to verify the tags' genuineness without revealing information to each other. This scheme cannot resist tracking attack since any reader can read out each tag's ID. Blass, Elkhiyaoui and Molva proposed TRACKER [START_REF] Blass | Tracker : security and privacy for RFID-based supply chains[END_REF] and its extension [START_REF] Blass | Tracker: Security and privacy for RFIDbased supply chains[END_REF]. In TRACKER system, each tag stores encrypted verifiable ID and path information. The manager decrypts the information and verifies whether the tag has gone through a valid path. TRACKER dose not need the entities in a supply chain to have any connection except the initialization phase. However, it requires the manager to possess the secret keys of all involving entities, the manager can only verify the tags from a set of pre-fixed paths. Therefore, it is difficult to implement TRACKER in dynamic supply chains.

Dynamic RFID-enabled supply chain

A supply chain consists of multiple entities. We model a dynamic supply chain according to three properties: the affiliation of each entity, the membership management of the supply chain and the logistics flow of the supply chain. In a dynamic supply chain, each entity is independent of each other; any entity can freely join or leave; the logistics flow is not fixed. An RFID-enabled dynamic supply chain management system should meet the requirements below.

-Each reader is independent with other readers and has an unique ID. Note that some readers may belong to a same entity. Even that, we assume the readers are independent with each other and have no pre-existing connections, such as network connection among themselves to cater for the most flexible deployment condition. -Each reader does not share its secret (eg. private key) with other readers.

-Each reader in the supply chain is isomorphic, with the same functionalities.

Each reader should be able to initialize the tags, identify the tags, verify the tags and update the tags.

Adversary model

Figure 1 illustrates our adversary model. The entities in a supply chain provide relative secure environments within their teritories, where the tags are beyond the accessible distance of an adversary. During the transportation of tagged goods between entities, a "hit and run" adversary can only approach the goods for a short period of time from a not-so-close distance. The "hit and run" adversary modle was firstly proposed by Ari Juels [START_REF] Juels | Minimalist cryptography for low-cost RFID tags[END_REF]. Several works [START_REF] Langheinrich | RFID privacy using spatially distributed shared secrets[END_REF][START_REF] Langheinrich | Practical Minimalist Cryptography for RFID Privacy[END_REF][START_REF] Juels | Unidirectional Key Distribution Across Time and Space with Applications to RFID Security[END_REF] have also adopted this model in designing secure RFID systems. The rationals to adopt this model in supply chains are: 1) the tagged goods usually rapid change their physical locations and ownerships so that it is difficult for an adversary to keep in the working distance of the tags (normally no more than ten meters); 2) as both readers and tags work in short range, an adversary bringing a reader into a monitored environment like a shop or warehouse might face difficulties in attempting prolonged intelligence gathering [START_REF] Juels | Minimalist cryptography for low-cost RFID tags[END_REF].

Requirements of RFID-enabled path authentication system

In dynamic supply chains, we list the following practice requirements for designing RFID-enabled path authentication:

-Any valid reader can extract a tag's ID and the exact path that the tag has passed through in the supply chain. However, no readers needs to store the information of all possible paths in its own database in advance. -An adversary cannot create new tag or modify existing one without being detected. A tag cannot pass the verification process for a path by which it has not passed. -No efficient adversary can link the state information stored in a tag to the tag's identity. No efficient adversary can distinguish whether two tags have taken the same path or not. -Path authentication can be performed on general EPC Class 1 Gen 2 tags, which have at most 1088 bits and no computational capability.

Our construction

Our system contains three components: tags, readers and a trusted server. Each tag stores a tag ID, a path code, and a signature on the tag's ID generated by the readers in the path. Any valid reader has a pair of public key and private key and a random number used for generating the path code. A valid reader is able to extract each tag's ID and the path code; while to verify them, it needs to connect with the trusted server which stores the reader's public information and detailed path information. In designing a secure and privacy-preserving path authentication scheme, we use the following building tools. Path encoding method: Noubir et al. [START_REF] Noubir | Signature-based method for runtime fault detection in communication protocols[END_REF] proposes to encode a software's state machine using polynomials such that the exact sequence of states visited during run-time generates a unique "mark". We adopt this technique in generating the path code. Suppose there is a path

P v = {R v1 , • • • , R v lv }
, where l v is the length of path P v , v i represents the reader's identity of the ith step in path P v ; we assign each reader R j with a unique random number a j ∈ F q , where q is a large prime. A path is represented with a polynomial on Fq. Then the polynomial corresponding to a path

P v = -------→ R v1 • • • R v l is
defined below (all operations are in Fq.):

Q P (x) := l i=1 a vi x l-i
(1)

Given a generator x 0 of F q , we calculate the path code as φ(P v ) := Q Pv (x 0 ) and identify a path P v using its polynomial evaluation φ(P v ).

Secret Sharing Scheme A (τ, n)-secret sharing scheme is an algorithm that divides data D into n pieces in such a way that: 1) knowledge of any τ or more pieces makes D easily computable; 2) knowledge of any τ -1 or fewer pieces leaves D completely undetermined (in the sense that all its possible values are equally likely) [START_REF] Shamir | How to share a secret[END_REF]. We adopt the Tiny Secret Sharing (TSS) [START_REF] Juels | Unidirectional Key Distribution Across Time and Space with Applications to RFID Security[END_REF] proposed by Juels et al. in our construction.

Ordered Multisignature Scheme Ordered multisignature scheme (OMS) allows signers to attest to a common message as well as the order in which they signed. The concept is raised by Boldyreva et al. in [START_REF] Boldyreva | Ordered multisignatures and identity-based sequential aggregate signatures, with applications to secure routing[END_REF]. A construction of OMS is provided in [START_REF] Boldyreva | Ordered multisignatures and identity-based sequential aggregate signatures, with applications to secure routing[END_REF], and we denote it as BGOY-OMS scheme from now on. We summarize BGOY-OMS system as follows. Each BGOY-OMS system has global information I = (p, G, G T , e, g, H), where (p, G, G T , e) is generated by a bilinear-group generation algorithm G, g is a random generator of G, and H : {0, 1} * → G is cryptographic hash function.

-Key Generation: On input I, the algorithm chooses random s, t, u ∈ Z p and returns (S = g s , T = g t , U = g u ) as pk and (s, t, u) as sk. -Signing: On inputs sk i , m, σ, L = (pk 1 , • • • , pk i-1 ), the algorithm first verifies whether Equation 2 defined below holds and if not, outputs ⊥. (This step is skipped for the first signer, i.e. if i = 1, for whom σ is defined as (1 G , 1 G ).) Then it parses σ as (Q, W ) and chooses random w ∈ Z p and computes

W ′ = W • g w , X = (W ′ ) ti+iui , Y = ( i-1 j=1 T j (U j ) j ) w and Q ′ = H(m) si • Q • X • Y . Finally, it returns (Q ′ , W ′ ).
-Verification: On inputs {(pk 1 , • • • , pk n ), m, σ}, the algorithm first checks that all of pk 1 , • • • , pk n are distinct and outputs 0 if not. Then it parses σ as (Q, W ) and checks if e(Q, g)

? = e(H(m), n i=1 S i ) • e( n i=1 T i (U i ) i , W ). ( 2
)
If so, it outputs 1. If not, it outputs 0.

Protocol details

The tag information, including tag ID, path code, and signature is encrypted. The tags in the same batch share the same encryption key. Then the encryption key is distributed using TSS secret sharing scheme and each tag stores a share of the key together with encrypted data. A valid reader can collect enough shares, recover the key, and decrypts the information of each tag. For each tag, after decryption, a valid reader obtains the tag ID, a path code, and a signature on the tag ID. Querying a trusted server with the path code, the reader gets the aggregated "path public key" of the path which is computed from the readers' public keys, and uses it to verify the signature. If the tag is valid, then the reader can update the path code and the signature and encrypt them with a new random key. Finally, the reader stores the new tag information on the tag. The tags are processed by batch in supply chain management. Polynomial signature based path encoding method [START_REF] Noubir | Signature-based method for runtime fault detection in communication protocols[END_REF], BGOY-OMS [START_REF] Boldyreva | Ordered multisignatures and identity-based sequential aggregate signatures, with applications to secure routing[END_REF], and TSS [START_REF] Juels | Unidirectional Key Distribution Across Time and Space with Applications to RFID Security[END_REF] are incorporated in the design of our system. System Setup: A BGOY-OMS system is set up by running a bilinear-group generation algorithm G for output (p, G, G T , e, g, H). Choosing a large prime q, and a random number x 0 ∈ Z q , we get I = (p, q, G, G T , e, g, H, x 0 ), which is the global information for the scheme. Assume that there are m readers in total. Each reader R j is assigned with public key pk j = (S j , T j , U j ) and secret key sk j = (s j , t j , u j ), where s j , t j , u j are randomly chosen from Z p , 1 ≤ j ≤ m. Each reader R j is also assigned with a random number a j ∈ Z q , where a j will be used in generating a path code.

A trusted server publishes the global information I, each reader's public key pk j and random number a j . The trusted server also stores each path P v 's information, including "pathcode v , l v ,

P v = {R v1 , R v2 • • • , R v lv }, ppk v = (ppk1 v , ppk2 v ) = ( lv j=1 S vj , lv j=1 T vj (U vj ) j )"
, where l v is the number of readers in path P v , v j denotes the identity of the jth reader in path P v , pathcode v is the path code of P v generated using Equation (1) in F q , and ppk v = (ppk1 v , ppk2 v ) = ( lv j=1 S vj , lv j=1 T vj (U vj ) j ) is each path's public key stored in a path record. With ppk v , a valid reader can verify the signature on the tag without knowing any other reader's individual public key. This will reduce the communication load between a reader and the trust server. In case a reader needs to verify the signature on a tag based on all involving readers' public keys, it can also get the public keys from the trusted sever. Table 1 shows the contents stored on the trusted server.

• • • , Rv lv }, ppkv = (ppk1v, ppk2v) = ( lv j=1 Sv j , lv j=1 Tv j (Uv j ) j )
Batch initialization of the tags: Suppose that a batch T of n tags enters in a supply chain, where each tag is denoted as T i with unique ID id i , for i ∈ {1, • • • , n}. The tags can be initialized by a reader valid R x , 1 ≤ x ≤ m. In particular, R x generates a key k and n shares of k using TSS-scheme, where each share is denoted as s i , for 1 ≤ i ≤ n. For each tag T i , R x generates a signature σ i = (Q i , W i ) on the tag ID id i under its private key using BGOY-MOS scheme. Then R x sets pathcode i of each tag T i to a x . Finally, R x encrypts (id i , σ i , pathcode i ) with the key k, and stores {s i , E k (id i , σ i , pathcode i )} on T i . After initializing the batch of tags, R x queries the trust server to check whether the path P = {a x , 1, {R x }, ppk = (S x , T x U x )} already exists; if not, R x inserts path P to the database on the trust server. Then R x releases the batch of tags into the supply chain.

Interactions between reader and tag: When a batch T of tags in the supply chain arrives at reader R y , where 1 ≤ y ≤ m. Each tag T i in the batch stores a state st i = {s i , E k (id i , σ i = (Q i , W i ), pathcode i )}. Reader R y firstly reads all the tags in T to get st i for all 1 ≤ i ≤ n. Using at least τ shares, R y recovers a key k, and decrypts the information on each tag E k (id i , σ i , pathcode i ) and gets {id i , σ i = (Q i , R i ), pathcode i }. According to pathcode i , R y gets the path's information P = {pathcode i , l, {R P0 , • • • , R P l }, ppk = (ppk 1 , ppk 2 )} form the trusted server. If e(Q i , g) = e(H(id i ), ppk 1 ) • e(ppk 2 , W ), then T i passes the verification. To update the batch of tags, R y generates a new key k ′ and n shares of k ′ in TSS, where each share is denoted as s ′ i . For each tag T i , R y shall update both the signature σ i and the path code pathcode i . To do these, R y chooses a random number w in Z p , computes

W ′ i = W i • g w , Q ′ i = W ′ty+(l+1)uy i • ppk w 1 • Q • H(id i ) sy and pathcode ′ i = pathcode i • x 0 + a y . R y updates each tag T i by writing {s ′ i , E k ′ (id i , σ ′ i = (Q ′ i , W ′ i ), pathcode ′ i )
} to the tag. Finally, the reader queries the trusted server: if the path

P new = {pathcode ′ i , l + 1, {R P0 , • • • , R P l , R y }, ppk = (ppk 1 • S y , ppk 2 • T y U l+1
y )} does not exist in the trusted server, then path P new will be added for future queries.

Implementation details: TSS scheme can be implemented with Reed-Solomon code [START_REF] Reed | Polynomial codes Over Certain Finite Fields[END_REF]. A Reed-Solomon code is specified as RS(N, K) S . A codeword has S bits. A reader chooses a pre-key with K • S bits and encodes the pre-key to N shares with each share S bits. A hash value of the pre-key is used as the encryption key for a batch of N tags. Reed Solomon encoding and decoding have been implemented on an Intel Core 2 CPU 6320 1.86GHz in [2]. Choosing the parameters (N, K, S) as (32768, 16384, 16), the fastest algorithm achieves 6.17 Mbytes throughput per second for encoding, and 2.73 Mbytes throughput per second for decoding. Both encoding procedure and decoding procedure consume less than one second. Suppose there are 20000 tags in a batch, one can firstly choose a pre-key with 16 * 16384 bits, encode them to 32768 symbols. Each share contains one symbol. Then one can select 20000 shares, randomly store on share on each tag. Any reader that can successfully read more than 16384 tags is able to get the pre-key. Regarding the encryption algorithm, Blowfish [3] is an appropriate choice. According to [3], Blowfish has good performance that achieves 64.386MB per second of encryption throughput on a Pentium 4 2.1 GHz processor under Windows XP SP 1.

to prevent an adversary from forging a tag's internal state so that the tag is considered from a reliable source and has gone through a valid path that has not actually been taken by the tag in the supply chain.

The security of our solution is based on the unforgeability of the BGOY-OMS scheme. Intuitively, the unforgeability of BGOY-OMS scheme can be described as follows: given an uncorrupted party with key pair (pk, sk), a forger cannot generate a valid BGOY-OMS signature of the uncorrupted party on any message m ′ if the forger does not know the party's signature on m ′ . Note that in the original BGOY-OMS unforgeability game, given a key pair (pk, sk), the adversary is able to get signature on any tag's ID under the key sk so as to learn useful information. In our system, the adversary cannot get a valid reader's signature on any ID it chooses since the valid reader will verify the genuineness of any tag before generating a signature on its ID. Hence, the adversary in our system is weaker than the adversary in the BGOY-OMS unforgeability game. BGOY-OMS scheme is secure against the forger; hence it is also secure against the adversary in our system. Unless an adversary has corrupted all the readers in a path with path code pathcode, it cannot forge a tuple (ID, σ, pathcode) such that σ is a valid signature on ID generated by the readers in the path.

While an adversary cannot forge any valid new tuple (ID, σ, pathcode) by itself, another way to counterfeit an tag is to use an existing valid tuple in the supply chain. From this aspect, the counterfeiting countermeasure of our system relies on the batch processing property. Only can valid readers read the whole batch of tags and decrypt the contents of the tags. A "hit and run" adversary is not able to read more than τ -1 tags in a batch , thus cannot recover the decryption key. In EPC Class 1 Gen 2 tags, the user memory bank can be protected by access pin. We use the encryption/decryption key as the access pin for the tags; therefore, an adversary cannot get the complete content stored on a tag and our system is secure against the counterfeiting attack.

Privacy

The privacy of RFID path authentication can be considered at two levels: tag unlinkability and path unlinkability. Tag unlinkability requires that no efficient adversary can link the state information stored in a tag to the tag's identity. Path unlinkability requires that no efficient adversary can distinguish whether two tags have taken the same path or not. In our scheme, each tag stores a copy of encrypted ID, pathcode and signature together with a single share of the encryption key. The privacy of our system relies on honest behaving of valid readers. Each valid reader uses a new random key to encrypt the updated state for each tag. An hit-and-run adversary who cannot collect enough shares for recovering the encryption keys cannot distinguish between any two ciphertexts of the same tag and any two ciphertexts of different tags. Thus our scheme preserves tag unlinkability. Similarly, our scheme preserves path unlinkability since an adversary cannot obtain any information about a tag's path from the content of the tag.

Performance

We analyze the performance of our solution in three aspects: computation requirements, communication requirements and storage requirements. Computational requirements: Our scheme does not require tag to perform any computation. All the computation can be performed at RFID reader side. In computing the computational load of a reader, we omit the cheap operations such as Reed Solomon encoding, decoding, encryption and decryption using Blowfish, hash operation, and point addition on elliptic curve. We only count the relative expensive operations such as point multiplication on elliptic curve and paring. A reader needs to perform three paring operations to verify the signature and four point multiplication four updating the signature in each tag.

Due to batch processing in supply chain, we can reduce the computational cost if a batch of tags share the same path. Assuming that a batch of tagged goods is transferred in a supply chain without being mixed with other goods, then a reader can sign the batch of tags with the same random number. That is, each tag shares the same randomization factor W in the signature. To update the signature, the reader firstly computes (W ′ , X, Y ), which requires three point multiplication operations, and uses (W ′ , X, Y ) to generate each tag's signature. With (W ′ , X, Y ), the reader's computational load is reduced to one point multiplication in generating each tag's signature. For signature verification, since each tag in the batch stores the same randomization factor W in the signature, a reader can pre-compute e(ppk 2 , W ) and store the value. The computational requirements for each tag is reduced to two paring operations. Since all the computation can be performed on reader side, our solution is applicable on standard low-cost tags with no computation capability. Communication requirement: The verification of each tag's ID and path code requires a valid reader to connect to the trusted server. The reader sends the path code to the server, then the server returns necessary path's information. In the case that a batch of tags passed the same path, the reader needs only one path information from the server. Since batch processing is commonly used in supply chain practice, the communication load required for processing a batch of tags should be almost constant. The communication load can be further reduced if a reader stores path information for frequently used paths in its own database. Storage requirement: In each tag T i , we need to store {s i , E k (id i , σ i = (Q i , W i ), pathcode i )}. s i is a share of encryption key k. As we implement TSS scheme with Reed-Solomon code, s i can be a symbol, which we use 16-bit string (a symbol's length depends on the parameters of Reed-Solomon code). Tag ID id i is an EPC code, which has 96 bits. Tag signature σ i generated by BGOY-OMS scheme consists of two elements on G. For 80-bit security level with embedding degree k = 2, an element in G can be represented in 512 bits. For embedding degree k = 6, the length can be reduced to 237 bits [START_REF] Boneh | Short signatures from the weil pairing[END_REF]. Hence, the storage requirement for σ i is at least 474 bits. We use 80 bits to represent a path ID, which supports at most 2 80 different path codes. We adopt Blowfish block cipher [START_REF] Schneier | Description of a new variable-length key, 64-bit block cipher (blowfish)[END_REF] for encryption which has a block size of 64-bits. Thus, we need 720 bits in total. Our system can thus be implemented with EPC Class 1 Gen 2 tags with an extensible EPC memory bank (scalable between 16-480 bits), a scalable user memory bank (64-512 bits), a TID bank (32 bits), and a reserved bank (64 bits), which are available on the market [4].

Conclusions

In this paper, we proposed a distributed path authentication scheme for dynamic supply chains. Dynamic supply chain is a prevalent supply chain structure in real world that is inherently vulnerable to the injection of counterfeiting goods and at same time challengeable to design an RFID-enabled system which can monitor the whole supply chain. We design a path authentication scheme to enable any valid reader to verify the exact path that a tag has taken without requiring the reader to have any kind of connection with other readers; it is thus suitable for dynamic supply chains where supply chain partners (or readers) may not have pre-existing trust relationship. Our scheme is built upon tiny secret sharing scheme, multisignature scheme, polynomial signature scheme, and encryption scheme. Our system is secure, privacy-preserving and practical. Our scheme leverages on sharing path information on standard EPCglobal network, and can be implemented on standard low-cost RFID tags with no computation capability and limited memory.

Fig. 1 .

 1 Fig. 1. Adversary Model of Supply Chain

3. 1

 1 Building tools Bilinear map: A bilinear map is a map e : G × G → G T , where: (a) G is a (multiplicative) cyclic groups of prime order p; (b) |G| = |G T |; (c) g is a generator of G. The bilinear map e : G × G → G T satisfies the following properties: (a) Bilinear: for all x, y ∈ G and a, b ∈ Z p , e(x a , y b ) = e(x, y) ab ; (b) Non-degenerate: e(g, g) = 1. We call an algorithm G that outputs (p, G, G T , e) as above a bilinear-group generation algorithm.

Table 1 .

 1 Contents on Trusted Server

	System Parameters	(p, q, G, GT , e, g, H, x0)
	Reader Information
	Rj,	pkj = (Sj, Tj, Uj), aj
	for 1 < j < m
	m is the number of readers
	Path Information
	Pv	pathcodev, lv, Pv = {Rv 1 , Rv 2

AnalysisBoth the security and privacy of our scheme rely on the security and privacy properties of the underlying secret sharing scheme, encryption scheme and OMS scheme. Due to space limit, we leave detailed proof to an extended version of this paper.4.1 SecurityWe assume that in supply chain management, an adversary's goal is to insert counterfeited goods into the supply chain. The security goal of our system is

⋆ The second author's work is supported in part by the Office of Research at Singapore Management University. The third author is supported in part by an NSFC grant No. 61070248, and a grant from Shanghai Municipal Education Commission.


Weihan Li

Brajendra Panda
email: bpanda@uark.edu

Qussai Yaseen
email: qyaseen@uark.edu

Malicious Users' Transactions: Tackling Insider Threat

Keywords: Insider Threat, Transactions, Database, Security 1

This paper investigates the issues of malicious transactions by insiders in database systems. It establishes a number of rule sets to constrain the relationship between data items and transactions. A type of graph, called Predictive Dependency Graph, has been developed to determine data flow patterns among data items. This helps in foretelling which operation of a transaction has the ability to subsequently affect a sensitive data item. In addition, the paper proposes a mechanism to monitor suspicious insiders' activities and potential harm to the database. With the help of the Predictive Dependency Graphs, the presented model predicts and prevents potential damage caused by malicious transactions.

INTRODUCTION

Organizations face the continual possibility of outside (external) and inside (internal) attacks. In the current context that risks and chances of malicious attacks from intruders are limitless, it is very important that database systems that store critical data provide confidentiality, integrity and availability. Although a lot of work in security is related to the outsider threat problem, the growing reliance on technological infrastructures has made organizations increasingly vulnerable to threats from insiders. Identification of insider threats is a major challenge, because by definition [START_REF] Mills | Insider Threat Prevention, Detection and Mitigation. Cyber Security and Global Information Assurance: Threat Analysis and Response Solution[END_REF], given a wide range of activities, insiders have been granted certain authority and trust. In addition, they have superior knowledge of the organization's inner control and security systems.

Although insiders can perform tasks as authorized users, they should not manipulate data items arbitrarily, but only in constrained ways that preserve or ensure the integrity of the data item. Since there are different sets of data items that are necessarily associated with a set of certain transactions permitted to manipulate them, even though the transactions could be from authorized users, any data item modifications should be constricted to the transactions assigned, and those transactions should be executed following the correct sequence [START_REF] Wilson | A comparison of Commercial and Military Computer Security Policies[END_REF].

This paper considers transactions that inject malicious attacks into the system and corrupt other transactions and data items. The threat mitigation technique presented in this paper attempts to remove the malicious effects of an insider and to provide mitigation service. The contribution of this paper is summarized as follows. First, Normal Activity Rules are established to constrain the relationship between data items and transactions that depend upon different security levels. Second, a graph called Predictive Dependency Graph is developed to investigate different patterns of data flows among the data items. Third, The Labeling Mechanism is adopted to flag any unverified data items in order to predict and stop any malicious data flow. Fourth, the idea of a Real Event Analyzer (REA) is used to check the transactions' effect actions matching to real world. The advantage of using the REA is that it permits monitoring of the suspicious users' activities and potential harm to the database.

The rest of the paper is organized as follows. Section 2 discusses some related work. Section 3 introduces the insider threat problem and describes the proposed model. Finally, section 4 provides the conclusions and mentions some future work.

Related Work

The increasing awareness of the insider threat problem has led to significant interest in techniques which can effectively detect malicious insiders' activities. Unfortunately, the techniques for mitigating insider threat are relatively immature and have not gained wide acceptance or use.

A significant amount of research on intrusion detection systems has been conducted for almost twenty years [START_REF] Chung | Demids: A misuse detection system for database systems[END_REF]

[4][5][6][7][8][9]
, however, most of them focus on the capability of identifying intrusions by outsiders. In recent years, several works have been done in the area of detecting insider threats [START_REF] Ray | Using Attack Trees to Identify Malicious Attacks from Authorized Insiders[END_REF] [START_REF] Martinez-Moyano | A Behavioral Theory of Insider-Threat Risk: A System Dynamic Approach[END_REF]. However, they are not adequate for protecting the database from "denial of service" and they tend to generate low "false alarms". Yaseen and Panda [START_REF] Yaseen | Predicting and Preventing Insider Threat in Relational Databases[END_REF][13] discussed how insiders can use dependencies to infer sensitive information and make malicious modifications in sensitive data items. In addition, they proposed models to detect and prevent those types of insider attacks.

Database Activity Monitoring [14][15] is an emerging technology that monitors and analyzes individuals or organizations' databases for potential leaks and compromises. Database Activity Monitoring operates independently of the database management system and does not rely on any form of native (DBMS-resident) auditing or native logs such as trace or transaction logs. Database Activity Monitors capture and record, at a minimum, all Structured Query Language (SQL) activity in real time or near real time, including database administrator activity across multiple database platforms, and can generate alerts on policy violations. There are several DAM products on the market. This paper adopts the concept of DAM to propose a new Real Event Analyzer with similar functionality. The architecture technique, management policy and other features are beyond the discussion of this work.

Insider Threat and Malicious Transactions

The goal of this paper is to design models that can detect and stop malicious transactions submitted to the DBMS by a malicious insider masquerading as a legitimate user. Since there can only be a finite set of tasks to be performed for inside users, this paper assumes that the "Normal Activity Rules" (discussed in the next section), which are predefined and established respectively by the application program and administrators /database experts, are stored separately for predicting any further da mage. Before going further, let us introduce some definitions. Definition 1. A Critical Data Item (CDI) is defined as a data item to which a change would induce significant effect. The CDIs therefore are usually the target of malicious attackers. Besides, any data items outside the CDI set are therefore termed as Regular Data Item Set (RDI). Definition 2. A Predefined Transaction is an authorized transaction that is allowed to update data items to which it is assigned. A Predefined transaction is categorized into two different types:

1. Predefined Trusted Transaction (PTT) is the transaction that has authorization to access both critical data items and regular data items, and it is executed by trusted users such as DB Administrators or other high-level employees.

Predefined Normal Transaction (PNT)

is the transaction that can access and update only regular data items, and it is executed by normal-level users who might occasionally spread the potential damage, or a malicious normal-level user who intends to carry out malicious activities by breaching the system security.

For each transaction that has access to a mount of data items, whether Critical Data Item Set and/or Regular Data Item Set, those data items in that transaction are categorized with relation pairs of Read Set and Write Set. Data dependency is defined as follow. Definition 3. A write operation w i [x] of a transaction T i is dependent on a read operation r i [y] of T i if w i [x] is computed using the value obtained by r i [y]. A data value v 1 is dependent on another data value v 2 if the write operation that wrote v 1 was dependent on a read operation on v 2 . Notice that v 1 and v 2 may be two different versions of same data item.

The semantics information is insufficient; it is reasonable to presume that a write operation of a transaction depends on all read operations of the same transaction that precede the write operation in a particular pair in transaction T. For example, the Write Set containing write operation w[x] is dependent on a set of data items in the corresponding Read Set if x=f(Read Set), the values of data items in that Read Set are used in calculating the new value of x (Previous value of x is the value before current operation). There are three cases for the set of data items in Read Set, which are as follows.

Case1: Read Set = Ø. This means that no data item is used in calculating the new value of x. Such an operation is denoted as a fresh write. If w[x] is a fresh write and if the previous value of x is updated maliciously, the value of x will be refreshed after this write operation.

Case2: x鞄 Read Set. Then w[x] is called a blind write. If w[x]
is a blind write and if the previous value of x is updated by a malicious transaction and none of the data items in Read Set are updated maliciously, then the value of x will be refreshed after this write operation. If any data items in Read Set are modified, the value of x will be modified.

Case3: x樺 Read Set. If the previous value of x is updated maliciously, then x remains contaminated. Otherwise, if any other item in Read Set is contaminated, x is thus affected.

These actually show the data dependency between the data items in related Read Set and the Write Set. The dependency of different relations of Read and Write sets, defined as Normal Activity States, are identified and denoted like this: {(R_Set 1 :W_Set 1 ), (R_Set 2 : W_Set 2 ), ... , (R_Set n : W_Set n )}. For instance, consider a transaction T with query statements in the given sequence as shown below: UPDATE Table1 set x = a + b + x; UPDATE Table1 set y = x + u; UPDATE Table1 set z = v *0.9;

After analyzing the transaction, the Normal Activity States of transaction T is as following:

T: {({a, b, x}: {x}), ({x, u}: {y}), ({v}: {z})}

The transaction T consists of three related pairs. Each pair represents the data dependency that once any data in the Read Set is modified, all or parts of the data items in the Write Set of the same pair are affected. Consider that once data item x in the Read Set is about to be modified by a previous transaction T'. Both the data items y and x in the related Write Sets of T are considered to be potentially affected when the transaction T' is in the process of being executed. This is because both data items x and y are partially dependent on data item x. So if any one or more data item sets in Read Set of T is/are updated by a previous transaction T', the value of at least one data item in the Write Set will be presumably influenced. This kind of situation is considered as potential damage to the critical data items in the database system. Definition 4. The Predictive Dependency Graph PDG is a graph adopted to demonstrate the prediction of a particular transaction's impact or pathway in the database. Figure 1 shows an example of a PDG. A rectangular node in the graph contains information such as transaction's ID and its operation sequence; an oval node in the graph denotes the data items in the Write Set of the transaction from which the arrows come. A firm edge from transaction to data item represents that transaction updates the data item to which the arrow points. The predictable transactions which might probably be affected by data items being updated are denoted by a dash edge from data item to transaction. It is necessary to mention that the subscript for each transaction only means the transaction id in the Normal Activity States not the time sequence of transactions. As seen in Figure 1, the procedure starts from the rectangular node of transaction, and ends at rectangular nodes which represent all the affected transactions presumably determined by data dependencies. Definition 5. Average Time, time avg , is defined as the average time needed for the execution of a particular transaction, which is measured using the following formula:

time avg = デ 岫担 套貼刀灯刀 貸担 套貼棟冬塘 岻 登 套転迭 択 (1)
Where t i-exe denotes the time when it was executed and t i-sch represents the time when it was scheduled, N is the number of total transactions executed. Definition 6. Assurance time t A is preset by the database experts and is defined to be used with the information of the average time of execution of particular transaction, which is measured using the following formula.

t A = デ 岫担 套貼刀灯刀 貸担 套貼棟冬塘 岻 登 套転迭 択 *Avg Ts *n STEP ( 2
)
Where N is the number of steps used for generating the PDG graph and Avg Ts represents the average number of potential affected transactions in each step. ------------------step1---------------> ----------------step2------------->|

Figure 1. Predictive Dependency Graph

Notice that in the proposed PDG graph, the one complete procedure of a step starts with the rectangular node of transaction and passes through the circular nodes of data items in its Write Set. Hence, in order to predict any further potential damage from an incoming transaction, the Predictive Dependency Graph is produced based on the combined information of real execution time time avg and threshold number n. Hence, for each incoming transaction T, the possibility of potential damage (as mentioned on the previous page) is predicted and measured within the time period of t A : For the Predefined Normal Transaction, it only has authorization over access to and update of the RDI Set. Since PNT is needed to be judged whether it is from an innocent insider or a masqueraded insider, PNT should be examined before scheduling it to commit. In the real world, however, thousands of PNT from different users can be executed per second in the database application program. In order to avoid slowing down the system, transactions are scheduled to be executed and examined simultaneously. Meanwhile, since the Predefined Trusted Transactions are considered from trusted user by default, any access or update merely within the range of CDI Set can be executed without any supervising action. However, any PTT update, involving both the Critical Data Item Set and at least one other data item from Regular Data Item Set, is needed to be checked carefully and thoroughly. It is the upmost requirement since before allowing any update, all data items to be read are verified to make sure that there are no damaged data from previous transactions. In addition, no more potential damage in future can result from the execution.

Definition 7. Normal

The Proposed Model

The goal of this model is to develop a Predictive Insider Threat Detection Mechanism that can be implemented within the database server and is capable of detecting any anomalous users' requests to a DBMS. Suppose that the Normal Activities States are as shown in Figure 3 (for each T x , x is the transaction id, not the sequence of events).

For instance, PNT Transaction T 5 has 2 pairs of Read Sets and Write Sets. Once a data item m is updated in the previous PNT Transaction T', data items l and a are all considered to be potentially affected. On the other hand, once data item l in pair 2 is updated beforehand, only data item l in the related Write Set will be presumed to be the affected one. In PTT Transaction T 200 , the data item z in bold is defined as a critical data item, and this PTT Transaction T 200 follows the Rule 10 in the In Figure 4, suppose the incoming PNT Transaction T is the one that is to be scheduled to update data items a, b, d, and data item z is a critical data item. There are N steps after any updates on them. Similarly there are also countless transactions and data items that need to be checked. However, in this model, only 2 steps are analyzed for that particular Transaction T which might change data item a , b, d. From this graph, once the PNT Transaction T on data items a, b, and d is executed, there is a possibility that the critical data item z might be manipulated by the effect of previous events through T 7 to T 200 . However, since only the first 2 steps are checked in this graph, the PNT Transaction is considered to be safe in the time range we preset. If we further analyze it to 3 steps, T 200 might be detected since it has indirect potential damage on critical data item z. In light of the situation of Transaction T 3 and T 15 , for which the same data item appears in both the Read Set and Write Set, in order to keep the limited account of the considered affected transactions, the predictive dependency between the data item and the transaction which updates the same data item is not considered in the model.

The Labeling Mechanism

The data item is labeled and stored into the unverified data items set in two situations. The first situation is that the PNT Transaction whose Read Set is all verified and is still considered to be a threat. This is because it gets too close to CDI Set and all the following transactions needs to be alerted by labeling process before any direct damage to CDI. Accordingly, all of the data items in the Write Set of that PNT Transaction are initially labeled as unverified "dirty" data items and stored once it gets executed. The second situation is when a damage spread might happen. In order to keep the both efficiency and availability of database and store the further impact of the tobe-verified data item, some of the data items in the Write Set whose corresponding Read Set are not verified are labeled as unverified "dirty" data items.

The Damage Predictor

The Damage Predictor is used to predict any potential impact on data items in the Critical Data Item Set within a certain time of period t A . For all the transactions, PNTs or PTTs, which are submitted to the database application program, before scheduling them to be executed, the prediction of affected transactions and its data items can be made by using the Damage Predictor. First, the data items in the Read Set of that particular Transaction are checked and verified, and then, data dependency relation among other transactions in the Normal Activity States list is found. Second, a PDG graph can be produced with all the possible paths of the dataflow initialed from the incoming transaction. With enough information and in cooperation with the threshold time t A , if the PDG graph of incoming transactions show indirect access to the CDI, or as also termed "potential damage", the transaction might be considered to be from a user with malicious motivation, and thus, a more strict and harsh action will respond to it. For the PTT transaction that has more than one related pair, there might be more complicated situations that may hinder the Damage Predictor process. For example, since PTT has privilege over the CDI Set, the Read Set of PTT can either be the combination of CDI and RDI, or only contain the RDI. In this case, in order to simplify the process, the graph is checked using the same strategy instead of checking the pairs separately.

3.4

Real Events Analyzer

The Real Event Analyzer is used separately during the transaction activity-monitor process of the proposed Insider Detection System. In order to detect an attack, the Real Event Analyzer will examine the real events that correspond to each query and judge whether the transaction is from a legitimate user based on the query information. If the presumed malicious transaction turns out to be innocent, all the data items in the Write Set of that transaction will be cleared and all the labels will be removed from the unverified data item set. Another function for the Real Events Analyzer is its ability to calculate the recovery time for the cleaning process of each data item x. So once potential damage is found in the PDG within the time period t A , the average recovery time t R should be checked:

t R = デ 岫建 沈貸陳銚掴 髪 建 沈貸陳沈津 岻 津 沈退怠 *Avg OP /2 ( 3)
where t i-max and t i-min are the maximum and minimum recovery time of labeled data items for a single step respectively, and Avg OP is the average number of operations. The recovery time t R is calculated as average time length used for recovering data items during each step and t. If the recovery time t R for the data item is beyond the assurance time t A , which means that the unverified data items usually cannot be cleaned by the time it has spread the damage to the CDI indirectly, the transaction will be rejected. The advantage of the Real Event Analyzer lies in the fact that the examination process is arranged after the execution of the transaction, thus the speed of the DBMS system can be guaranteed. For those PTT Transactions whose Read_Set are not cleared, the transactions will be on hold unless all the data items are safe to use.

System Architecture

Figure 5 shows the architecture of the proposed approach. Figure 6 shows the flow chart incorporated with Damage Predictor and Real Events Analyzer. The Transaction Scheduler schedules PNT or PTT as to be executed or not. The ID mechanism is adopted to identify if the transaction is from a normal user or a trusted high level user. If the transaction is PNT, all Read Sets in R/W Set pairs are checked to see if there is any "bad" data item x which is damaged in previous executed transaction. If the system is not sure whether the transaction is from an innocent user, the labeling mechanism is initialized after the execution of T x , so that the data items in the Write Sets will be cleaned during the next verification process. The time t R and t A are generated in the Damage Predictor and the Real Events Analyzer respectively. For instance, if threshold t A is set to 15 seconds when the PDG is generated, and recovery time t R is 12 seconds by consulting the individual recovery time for data items, such transaction will be rejected since once data flow reaches the Critical Data Item Set, the verification is still in process and the value of the Critical Data Item will be compromised. In the case of the transaction from trusted user (PTT), if the transaction only reads data items from CDI (like the rules 7 and 8 in Figure 2), it will be executed without any check. If the transaction has direct access to CDI (like the rules 6 and 10 in Figure 2), the transaction should wait until all the labeled data items in Read Sets to be verified by REA. The system must be aware of the data flows between trusted users and suspicious users. Thus, the identity of the transactions and data items that T x depends upon needs to be checked beforehand. Moreover, since Predefined Normal Transactions play an important role numerically in the database system, and any "block" action might significantly reduce the efficiency, labeling mechanism and the Real Events Analyzer are adopted here, instead of simply discarding the normal transaction. Meanwhile, on the other side of the Presumed Trusted Transaction, identification is also a mandatory step in the proposed approach. In addition, since critical data items always have extreme influence on regular data items and it is assumed that all the PTTs are from the trusted users that take more responsibility. CDIs should avoid any damage flow from RDI before any PTT is executed.

CONCLUSIONS

This paper has addressed the problem of malicious transactions by insiders in database systems. It has established a number of rule sets to constrain the relationship between data items and transactions, which are called Normal Activity Rules. Moreover, it has used a graph model, called Predictive Dependency Graph (PDG), to determine data flow patterns among data items. The PDG has been used to look for the data items that might be affected once an update to a particular set of data items occurs. That is, PDG has been used to detect any indirect damage to particular data items. The Labeling Mechanism and Real Event Analyzer have been used to detect and prevent malicious transactions. The Labeling Mechanism has been employed to flag any unverified data items in order to predict and stop any malicious data flow. The Real Event Analyzer has been used to permit monitoring of suspicious users' activities and potential harm to databases. As a future work, we plan to formally define and develop the Real Event Analyzer and analyze its performance.

Figure 2

 2 Figure 2. Normal Activity Rules Table

Figure 4 .Figure 3 .

 43 Figure 4. Predictive Dependency Graph Model

  Activity Rules is a predefined profile that contains a group of relation rules, each relation is of the form: Rule, Transaction, Read Set, Write Set, Potential Damage, Assessment, Action, where a transaction is categorized by different user's security levels, and Read and Write Sets are the constrained accessible data item sets that correspond to that security level. Based on definition 1 and 4, there is a number of Preformed Transaction and Read/Write Set rules in the Normal Activity Rules Table in Figure 2. Predefined Trusted Transactions and Predefined Normal Transactions are denoted by PTTs and PNTs respectively. RDI and CDI represent Regular Data Item and Critical Data Item. We should mention here that Normal Activity Rules are constrained by application program or database administrator and is based on security issues and users' privileges.

  It has two main processing parts: the Damage Predictor and the Real Event Analyzer. Transactions are first compared with Normal Activities States (NAS) and sorted into PNT and PTT Transactions for further detection. The Damage Predictor processes transactions and generates Predictive Dependency Graph to predict potential damage and to report alerts to the Real Event Analyzer and the Scheduler. The Real Event Analyzer (REA) examines the executed transaction and verifies the data items, and then reports back to the scheduler.

	User	States Compare	Damage Predictor	Scheduler
		NAS	Real Events Analyzer (REA)
			Figure 5. System Architecture

  6. Dataflow Chart of the Model

			Tx
		PNT	PTT
			PTT or PNT?
	R_Set Verified?	Only Read CDI?
			Yes	Yes
	Yes	No		Execute it
	Damage Predictor	R_Set Verified?
			No	Yes
				Execute it
			Update a CDI?
	Potential Damage?	No	Yes
	No	Yes	Damage Predictor
				Block until R Set is
	Execute it	Potential Damage?	verified, then execute it
		No	Yes
			Real Event Analyzer
		Execute it
			t R > t A ?
		Label data items	No	Yes
		in W Set with value	Execute it	Reject
		and time		it

ACKNOWLEDGMENTS. This work has been supported in part by US AFOSR under grant FA 9550-08-1-0255. We are thankful to Dr. Robert. L. Herklotz for his support, which made this work possible.


Christian Banse
email: christian.banse@aisec.fraunhofer.de

Dominik Herrmann

Hannes Federrath

Herrmann Dominik

Tracking Users on the Internet with Behavioral Patterns: Evaluation of Its Practical Feasibility

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

Introduction

Tracking users on the Internet is perceived as a serious infringement of their privacy, especially when it is done without their consent. Nevertheless, tracking cookies, which allow content providers to link multiple sessions of a user, are used on many popular websites today [START_REF] Ayenson | Flash Cookies and Privacy II: Now with HTML5 and ETag Respawning[END_REF]. This allows ad networks such as Google Analytics, Doubleclick or Facebook to create usage profiles from the websites a user interacts with over time. Service providers that require authentication can also track the actions of their users. Apart from the Internet Service Provider this applies to, among others, commercial anonymization services that rely on singlehop proxies or VPNs (e. g., anonymizer.com and ipredator.se) and the providers of browser toolbars (e. g., Alexa and Web of Trust). We call this practice explicit tracking, because it uses well-known techniques, relies on the cooperation of the web browser or the user and can be detected rather easily.

Instead of explicit tracking we are interested in the feasibility of behaviorbased tracking techniques, which rely on characteristic patterns within the activities of the users. In contrast to explicit tracking it can be used to link multiple Internet sessions of a user passively, i. e., without the user's cooperation and even in the absence of unique identifiers or tracking cookies. Behavior-based tracking constitutes a considerable privacy threat, because it can not only be carried out without consent, but it is also imperceptible, i. e., it cannot be detected. As the recent discussions regarding the Do-not-Track initiative revolved mainly around tracking cookies, behavior-based tracking may come as a surprise even for well-informed users. For example, users of an alternative DNS resolver (like OpenDNS or Google DNS) 3 , a service provider that cannot use explicit tracking for technical reasons, do probably not expect that their resolver can track their activities. As our results show, DNS resolvers are in a good position for behavior-based tracking, though.

Behavior-based tracking of users is "challenging" because many Internet Service Providers assign their customers dynamic, periodically changing IP addresses [START_REF] Xie | How dynamic are IP addresses?[END_REF][START_REF] Xie | De-anonymizing the internet using unreliable IDs[END_REF]. Recent research on user profiling techniques may help curious service providers to overcome this hurdle: given a database with traffic profiles of a set of users, data mining techniques can be used to map traffic with unknown origin to one of the users from the database [START_REF] Kumpošt | User Profiling and Re-identification: Case of University-Wide Network Analysis[END_REF][START_REF] Yang | Web user behavioral profiling for user identification[END_REF][START_REF] Herrmann | Analyzing Characteristic Host Access Patterns for Re-Identification of Web User Sessions[END_REF]. The mapping becomes more difficult for larger numbers of users and for smaller amounts of training data [START_REF] Yang | Web user behavioral profiling for user identification[END_REF]. The actual privacy threat of behavioral profiles is unknown so far, because previously published results were obtained with a limited number of concurrent users (up to 100 in [START_REF] Yang | Web user behavioral profiling for user identification[END_REF]) in a closed-world evaluation setting. Therefore, we address the following research question in this paper: To what degree is behavior-based tracking feasible in practice and how can users protect themselves against it? This question can be tackled by applying techniques that are known to work well for behavioral profiling to traffic of a large number of Internet users. Existing profiling techniques are not suitable for our tracking problem, though (cf. Sect. 2). Therefore, based on previous work we start out by devising a tracking technique and establish its suitability for behavioral profiling. We then analyze the real-world feasibility within an evaluation setup that incorporates the challenges to be faced in practice.

Our contribution. We design a tracking technique that exploits behavioral characteristics, implement a scalable evaluation environment with a MapReduce framework and evaluate our technique in a realistic setting with a large-scale dataset. Given more than 2100 concurrent users on average per day, we find that behavior-based tracking is feasible with very high accuracy for a third of the users and with moderate accuracy for the remaining ones. On overall 88.2 % of all session are linked correctly. The high accuracy is achieved by resolving ambiguous results caused by fluctuating users. To the best of our knowledge we are the first to assess large-scale behavior-based tracking in a real-world setting.

The paper is structured as follows. We present related work in Sect. 2 before modeling the tracking problem in Sect. 3 and describing our dataset in Sect. 4. Our tracking technique is illustrated in Sect. 5 and evaluated in Sect. 6. Finally, we discuss countermeasures in Sect. 7 before we conclude in Sect. 8.

In the following we outline related research efforts that analyze the possibility to re-identify users based on their traffic or behavioral profiles. They differ from our work in terms of application, techniques and evaluation methodology as well as the size of their dataset.

Yang [START_REF] Padmanabhan | Clickprints on the Web: Are there signatures in Web Browsing Data[END_REF][START_REF] Yang | Toward user patterns for online security: Observation time and online user identification[END_REF][START_REF] Yang | Web user behavioral profiling for user identification[END_REF] analyzes visitation patterns of web users as an additional authentication factor to tackle identity theft and fraud in e-commerce applications. She assumes that an e-commerce provider (e. g., a web shop) has access to user profiles built from multiple surfing sessions of its users. Each time a user logs into the web shop the provider is supposed to retrieve the most recent surfing sessions from the user in order to confirm the user's identity. To this end Yang constructs user profiles from the hostnames of the web sites visited within a surfing session. She proposes two profiling techniques based on support and lift, which are common measures in the field of association rule mining. The effectiveness of the techniques is evaluated and compared with the J4.8 decision tree classifier from Weka [START_REF] Hall | The WEKA data mining software: an update[END_REF] and with Support Vector Machines [START_REF] Cortes | Support-Vector Networks[END_REF]. In a scenario with 100 concurrent users the predictive accuracy of her techniques reaches 87 % for profiles built from 100 training sessions. The accuracy drops to 62 %, if only one training session is available, which corresponds to our behavior-based tracking scenario. Yang's results demonstrate that characteristic behavior can be exploited for user re-identification in her e-commerce scenario with a limited number of users. Its feasibility for large-scale re-identification problems or behavior-based tracking with many users cannot be deduced from her results, though.

Kumpost's user re-identification technique relies on the destination IP addresses for HTTP(S) and SSH connections of each user [START_REF] Kumpošt | User Profiling and Re-identification: Case of University-Wide Network Analysis[END_REF]. His user profiles consist of sparse access frequency vectors that contain the number of connections to each destination IP address. This is similar to our hostname-based profiles. Kumpost's re-identification methodology employs the inverse document frequency transformation and the cosine similarity metric. Kumpost evaluates the effectiveness of the technique using monthly aggregated NetFlow logs. Unfortunately, he fails to provide statistics regarding the size of the dataset, i. e., the number of concurrent users. Although monthly profiles should contain a considerable amount of information, Kumpost reports rather high false-positive rates of 68 % for HTTP traffic and 21 % for SSH traffic.

In a previous publication we proposed a user re-identification technique based on the Multinomial Naïve Bayes classifier from Weka [START_REF] Herrmann | Analyzing Characteristic Host Access Patterns for Re-Identification of Web User Sessions[END_REF]. The classifier was evaluated using the HTTP traffic of 28 volunteering users. Given one training session per user, up to 73 % of sessions were classified correctly. In comparison to [START_REF] Herrmann | Analyzing Characteristic Host Access Patterns for Re-Identification of Web User Sessions[END_REF] the tracking technique presented in Sect. 5 utilizes an improved feature extraction technique with n-grams and incorporates an additional cosine similarity decision engine. Moreover, the evaluation in Sect. 6 is carried out on a much larger dataset.

Modeling Behavior-Based Tracking

Building on the promising results of previous studies described in Sect. 2, our behavior-based tracking scheme solely relies on the web sites visited within a surfing session. Order of requests and exact timings are neglected in this model.

We assume that each user is represented by a dynamic IP address that is replaced by a different one after a fixed amount of time, i. e., there are epochs e i ∈ E of constant length (e. g., 24 hours, beginning at 4:00 am each day). Moreover we assume that the service provider that wants to use behavior-based tracking can record the interactions of its users with a set of destination hosts H. Each interaction is stored as a triplet (e, s, h) consisting of the epoch e it was observed in, as well as the corresponding source address s and the destination host h (in our case: a hostname). A user session is then obtained by aggregating all events that share the same e and s to obtain the access frequency of each destination h. Each user session can be mapped to an |H|-dimensional vector, where the i-th component corresponds to the access frequency of the i-th destination according to a totally ordered list of all observed destinations H. Figure 1 summarizes the transition from the real-world view of the service provider to our model.

Dataset

We evaluate the feasibility of behavior-based tracking using DNS queries, i. e., from the viewpoint of a curious DNS resolver. Our dataset was obtained in cooperation with the computer center of the University of Regensburg, Germany. It contains all DNS requests, which were received by the two DNS resolvers of the university network between February 1, 2010 and June 30, 2010. In order to maintain a high level of privacy, every source IP address s was replaced by a pseudonym u = h(s|r const ) using a hash function h before the record was stored. The actual salt value r was not disclosed to us and thrown away once data collection was completed. Nevertheless, this practice cannot ensure a satisfactory level of privacy for all users: some users may issue personally identifying queries (e. g., for their weblog at username.blogspot.com), which undermine our pseudonymization efforts. Therefore, we limit access to the dataset to a small group of researchers.

In total the dataset contains 2,645,748,393 queries for 77,662,943 unique hostnames issued by 18,904 unique source IP addresses. To maintain a high data quality we only consider queries originating from the student housing network segment in this paper. Each network device must be personally registered by its resident and is assigned a unique, static IP address. 4 The majority of the 4153 considered users in our dataset are students of the University of Regensburg, which use their Internet access for research and studying as well as private browsing. On average 2123 users were active per day.

During the evaluation of the tracking technique we simulate dynamically changing IP addresses, i. e., a priori our classifier (cf. Sect. 5) does not know which sessions belong to a given user. Of course, due to the static IP addresses used within the campus network, we do know all the sessions that belong to a given user. Thus, we can compare the predictions of our tracking technique with the actual set of sessions of each user to measure its accuracy.

Behavior-Based Tracking Technique

Multinomial Naïve Bayes Classifier

The behavior-based tracking problem can be formulated as a classification problem [START_REF] Manning | Introduction to Information Retrieval[END_REF]. Every session corresponds to a single instance x ∈ X which is represented by its attribute vector (cf. Sect. 3). Each instance belongs to a class c ∈ C, which corresponds to a certain user u (cf. Sect. 4). A set of training instances, whose class assignments are known (Sessions 1 and 2 in Fig. 1), is used to build a predictive model. Based on the model the classifier assigns the most probable class to each test instance, whose class is supposed to be unknown in the experiment (Sessions 3 and 4 in the example).

For the Multinomial Naïve Bayes classifier (MNB classifier) [START_REF] Manning | Introduction to Information Retrieval[END_REF] used in this paper the probability that a test instance x belongs to a certain class c i is defined as

P (c i |x) ∼ h∈H P (h|c i ) f h,x .
The classifier assigns the test instance x to the class with the highest probability P (c i |x). In our case P (h|c i ) represents the probability that a hostname h is to be found in the training instances of class c i . f h,x specifies the frequency with which h occurs in the given test instance x. The rationale behind this formula is: the more often frequently accessed hosts seen during training of a class do appear in the given test instance, the more likely does the test instance belong to that class.

The selection of the MNB classifier for behavior-based tracking may seem unintuitive at first sight. After all, it is usually only applied to text categorization problems (e. g., in spam filters) [START_REF] Manning | Introduction to Information Retrieval[END_REF]. One aspect that motivates the application of the MNB classifier for the problem at hand is the fact that the features used in our model (access frequencies of hostnames) and the features used for text categorization (term frequencies) have an important similarity: both of them are subject to power law distributions [START_REF] Adamic | Zipf's Law and the Internet[END_REF][START_REF] Zipf | The psycho-biology of language. An introduction to dynamic philology[END_REF]. Another argument in favor of the MNB classifier is its little computation complexity in comparison to more sophisticated classifiers such as Support Vector Machines (SVMs) [START_REF] Cortes | Support-Vector Networks[END_REF]. In Yang's experiments the application of SVMs increased classification runtimes by 300 % [START_REF] Yang | Web user behavioral profiling for user identification[END_REF].

Transformation of Frequency Vectors

The text categorization discipline makes use of numerous transformation techniques in order to boost classification accuracy. We implemented the most promising techniques as described below.

The first technique consists of a transformation of the individual access frequencies f h,x of an instance vector. In our case f h,x specifies how often a hostname h occurs in a session x. The frequencies are scaled down by a sub-linear transformation log(1+f h,x ) in order to minimize the influence of extremely large frequency values [23, p. 311]. Additionally, the frequency vectors of all classes are normalized to a uniform Euclidean length [23, p. 310]. The application of the two transformations is indicated by the use of TFN in this paper.

Additionally, the frequencies f h,x can be multiplied by the Inverse Document Frequency idf h = log N n h [23, p. 311], where N is the number of all instances and n h the number of all instances containing the hostname h. The application of the IDF reduces the weight of common hostnames that are accessed by a large number of different users. The combination of the IDF and TFN transformation is designated by TFIDFN.

Finally, n-grams are known to increase the accuracy for many text mining problems [START_REF] Beesley | Language identifier: A computer program for automatic naturallanguage identification of on-line text[END_REF][START_REF] Cavnar | N-Gram-Based Text Categorization[END_REF][START_REF] Damashek | Gauging Similarity with n-Grams: Language-Independent Categorization of Text[END_REF]. They have also been used for traffic analysis problems with success [START_REF] Rieck | Language Models for Detection of Unknown Attacks in Network Traffic[END_REF]. This technique combines the hostnames of n adjacent events to obtain a composite hostname. We denote the usage of n-grams by appending a suffix to the configuration name, e. g., TFN-1+2 indicates that -in addition to the original hostnames -bi-grams are added to the instances.

Resolving Ambiguous Predictions with Cosine Similarity

According to our model only a single user can issue queries from a certain IP address within an epoch (cf. Sect. 3). Therefore, not more than one instance should be mapped to each class within an epoch. If the classifier does assign more than one test instance to a given class, we resort to an additional decision criterion to resolve the ambiguous prediction, i. e., to single out the instance that fits best (cf. Sect. 6.3). For this purpose we employ the cosine similarity metric.

The cosine similarity is a [0;1]-normalized similarity measure between two vectors x and y that reflects the angle θ which is spanned by them. A smaller θ corresponds to a larger value of the cosine similarity. The similarity s is equal to the quotient of the dot product of x and y and the product of their magnitudes:

s x,y = cos θ x,y = x • y |x||y|
Ambiguous predictions are resolved by computing the similarity values between the training instance of the class and all the test instances that have been assigned to it. The test instance that achieves the highest similarity value is assigned to the class, all other instances are discarded.

Evaluation

Due to the large size of the dataset we did not use off-the-shelf data mining tools such as Weka [START_REF] Hall | The WEKA data mining software: an update[END_REF] for the evaluation. Instead, we ported the MNB classifier based on the Weka source code to Apache Hadoop [START_REF] White | Hadoop -The Definitive Guide: Storage and Analysis at Internet Scale[END_REF], a MapReduce [START_REF] Dean | MapReduce: Simplified data processing on large clusters[END_REF] framework implemented in Java. We obtained the results presented in this paper on a cluster of 12 quad-core machines (Intel Core i5, 3.1 GHz, 8 GB RAM). The running time of individual experiments was below 24 hours most of the time, which enabled us to try out many parameters. In the following we will report our evaluation methodology and the most significant results.

Cross Validation

Firstly, we analyze the effectiveness of the classifier and the transformations presented in Sect. 5.2 with a series of cross validation experiments. Cross validation ensures that the results obtained are not biased due to selection of peculiar training instances [START_REF] Kohavi | A Study of Cross-Validation and Bootstrap for Accuracy Estimation and Model Selection[END_REF]. In order to obtain meaningful results, a stratified dataset is used, which contains the same number of instances for all classes.

For the cross validation experiments we focused on the very active period between March 1, 2010 and June 30, 2010, to include as many users as possible. We randomly selected 3000 users u ∈ U , which were able to contribute at least 20 instances of 24 hours length in the mentioned period. 20 instances were randomly selected from each user resulting in a cross validation dataset D of 60,000 instances in total.

In the following we illustrate the evaluation procedure for the case of For each experiment we compute the average precision and recall values, two metrics, which are used to analyze the prediction accuracy of data mining techniques. Both metrics are bound to the interval [0;1]. Assuming the classifier assigned n instances to some class c i , where m ≤ n of the instances actually do belong to c i , then the precision of this result is given by the ratio m n , i. e., it expresses the pureness of the result. On the other hand, the recall expresses whether the classifier "found" all test instances of c i : given l test instances of c i the recall value is equal to m l . Thus, a service provider that tries to track a user as extensively as possible over a period of time is primarily interested in high recall values. If the objective is to minimize the number of false mappings, a high precision value is of high importance.

For ease of exposition we only report the average recall values in the following. In all experiments the average precision values were constantly above the recall values by about 3 percentage points. Figure 2a shows the results for different configurations of the classifier with |I train | = 18 training and 2 test instances per user. For 1-grams we obtain a recall of 83.1 % using the TFN transformation. The remaining transformations increase the recall further. The configuration TFIDFN-1+2 achieves the best result with an average recall of 89.0 %. Higherorder n-grams have no more positive effects.

According to the results the selected text mining techniques are suitable for behavioral user profiling. The high accuracy obtained in the previous experiment is of little relevance for behavior-based tracking in practice, though, because we do not expect the service provider to have |I train | = 18 training instances for each user at his disposal. Hence, we repeated the cross validation experiments with a smaller amount of training data. As expected, the recall values of these experiments show that with a decreasing number of training instances it is increasingly difficult for the classifier to assign the test instances to the correct class. In case of a single training instance the recall drops to 69.2 %. Even for a large user group the behavior of most Internet users seems to exhibit sufficiently characteristic attributes, which are present in a large share of their sessions. Exploited Characteristics. We manually reviewed a sample of the trained model to understand the patterns the classifier relies on. As expected the classifier mainly exploits patterns in the web surfing behavior of the users, which are reflected by the DNS queries pretty well; only repeated queries for the same hostnames cannot be observed due to caching. For some users the classifier also relies on patterns introduced by the installed applications on their machine (visible due to update checks) or environmental peculiarities (e. g., the Windows Network Browser looking up its neighbors).

Evaluation in Real-World Setting

After having demonstrated the fundamental suitability of our technique in Sect. 6.1, we proceed with experiments that apply it to the actually recorded traffic. This will allow us to study its feasibility in a real-world setting. To this end, we have implemented a fully-automated experimental environment with the Hadoop framework that allows us to simulate a service provider that tries to track all users from one day to the following day, i. e., the epochs (cf. Sect. 6.2) start at midnight and last 24 hours. 5 The simulation iterates over all days t in chronological order. On a given day t a class c i is set up for each active user u i and the MNB classifier is trained with all instances x present on that day. The learned model is used to predict the most probable classes for all instances from the following day t + 1, i. e., to link the sessions of the two consecutive days.

In the case that user u i is active on two consecutive days, the simulated observer scores a correct mapping (C) within an iteration, if the classifier predicts that the instance of user u i on day t + 1 belongs to the class c i , which was set up using the instance of u i from the previous day, and if no other instance from t + 1 is assigned to c i . If the classifier assigns exactly one instance x j , which belongs to a different user u j , j = i, to c i , we record a non-detectable error (E 1 ). We record a detectable error (E 2 ) for ambiguous results, i. e., if instances from multiple users (possibly including u i ) are assigned to c i . In the case that user u i is not active on day t + 1 any more, a correct mapping is scored, if no instances are assigned to c i at all. The overall accuracy of the classifier is given by counting all mappings of an experiment and computing |C| /(|C|+|E1|+|E2|).

We evaluate the MNB classifier with this scheme for the month of May, which sports the largest number of active users. As we want to report results that are significant for typical users we ranked the users according to their daily query volume and removed the instances of the top 5 % and bottom 5 % of the list. Accuracy decreases by about 2.5 percentage points if this step is skipped.

Using the TFIDFN-1+2 configuration the classifier achieves an average accuracy of 76.6 %. Thus, tracking users in the real-world setting works better than the recall value of 69.2 % obtained for the cross validation experiment with a single training instance suggests. This counterintuitive result can be explained by the average number of active users per day (average: 2412, standard deviation: 695) being smaller than the 3000 concurrent users used in Sect. 6.1.

Robustness of profiles.

We also studied the effect of the age of the trained profiles. To this end we randomly drew tuples with two dates (t i , t i+δ ), which were exactly δ ∈ {5, 15, 30, 60, 90} days apart. The instances on t i were used for training and the classifier had to predict the classes of the instances on t i+δ . Accuracy values degraded rather slowly: from 78.3 % for δ = 5 to 44.7 % for δ = 90. The results suggest that the behavior of many users is rather stable, i. e., tracking is also possible with outdated profiles.

Dealing with Fluctuating Activity

The real-world setting is more challenging than the cross validation experiment because the classifier is faced with user fluctuation. The classifier will encounter instances, for which no class has been trained on the previous day, because the respective user was inactive on that day. Nevertheless, the default implementation of the MNB classifier will assign such an instance to the most likely class, which causes a (non-)detectable error. In our dataset the fluctuation is caused by students that leave the city on weekends. Once they become active again accuracy drops to about 60 %, while it reaches more than 80 % during the week (cf. Fig. 3a, MNB graph). Further analysis of the results of the initial experiment from Sect. 6.2 reveals the extent of this problem: ambiguous mappings account for 13.6 % of all cases (44.6 % of all errors), and in 90.4 % of the ambiguous mappings the correct test instance was in fact part of the set of assigned test instances. Therefore, resolving ambiguous results with the cosine similarity is promising (cf. Sect. 5.3). The effect of this optimization is shown in the graph labeled MNB+COSIM in Fig. 3a. On overall the accuracy increases to 88.2 %, i. e., about 85 % of the ambiguous results are resolved correctly. Not all users exhibit enough characteristic patterns for the behavior-based tracking to be effective. Figure 3b shows the accuracy levels that can be obtained for a certain fraction of users. The MNB+COSIM configuration is able to establish a correct mapping for all sessions of 35 % of the users. For 90 % of the users at least 60 % of their sessions were linked correctly.

Future Work

According to our results tracking students based on their DNS queries works quite well. A globally distributed service provider, such as Google's DNS resolver, is faced with additional challenges, though. The queries of multiple users may be issued from a single source IP in case they are hidden behind a NAT gateway, a typical scenario for domestic broadband connections. Moreover, users may be located in different time zones, i. e., queries must be assigned to epochs depending on the location of the respective user. In future work we will study the impact of these issues on the feasibility of our technique.

Another important area of work is the evaluation of our technique in different attack scenarios. Especially concerning is the question whether third-party tracking networks such as Doubleclick, Google Analytics or Facebook can exploit behavioral analysis to overcome privacy-enhancing techniques. Today, visits of different websites within a session can be mapped to a specific user due to a tracking cookie. If users delete their cookies between sessions or if they enable the Private Browsing mode, recurring visits in different sessions cannot be linked any more. With our behavior-based technique third-party trackers may be able to overcome this limitation, though.

Countermeasures

In this section we present initial findings from our search for countermeasures that potentially mitigate the effectiveness of behavior-based tracking. The results reported below are obtained by repeating the experiment described in Sect. 6.3.

A generic protective measure is to use anonymizers like Tor or AN.ON (JonDonym) [START_REF] Dingledine | Tor: The Second-Generation Onion Router[END_REF][START_REF] Berthold | Web MIXes: a system for anonymous and unobservable Internet access[END_REF] that hide communication patterns from eavesdroppers. We will not discuss anonymizers any further in this paper, as we are interested in countermeasures that directly target the behavior-based tracking technique.

If the data requested by the users is valid for a certain amount of time, which is the case for many DNS records, a caching system may be a viable countermeasure to hide repeated queries from the observer. Thus, the user profiles would consist of queries for data that hasn't been requested before and queries for expired entries only. Motivated by the fact that many DNS records have a time-to-live (TTL) value of 24 hours, we can simulate a cache, whose entries expire at the end of each day. As a result instance vectors do not contain the actual number of queries per hostname any more. The effect of such a cache is very limited, though: accuracy only drops from 88.2 % to 80.5 %. While keeping records in the cache for a longer time may further decrease accuracy, this practice may introduce usability and security issues due to stale information.

Another countermeasure that reduces the amount of information available to the classifier may be to change IP addresses frequently. We study the effect of shorter sessions by pretending that our users change their IP addresses multiple times per day. This strategy proves to be quite effective: for sessions with a length of three hours we observe an accuracy of 60.4 %, which decreases further to 49.5 % for a length of one hour. Time-based address changes have the drawback that all existing connections are terminated, though. The large address space of IPv6 may allow the design of more sophisticated countermeasures in the future [START_REF] Raghavan | Enlisting ISPs to Improve Online Privacy: IP Address Mixing by Default[END_REF]. The extreme case would be to issue each query from a different IP address (each having a different IPv6 address prefix) to minimize linkability.

Finally, we consider the effectiveness of Range Queries, a technique that has been proposed to protect the privacy of DNS queries [START_REF] Castillo-Perez | Evaluation of Two Privacy-Preserving Protocols for the DNS[END_REF][START_REF] Zhao | Analysis of Existing Privacy-Preserving Protocols in Domain Name System[END_REF][START_REF] Lu | Towards Plugging Privacy Leaks in the Domain Name System[END_REF]. It is based on the principle of Private Information Retrieval [START_REF] Chor | Private Information Retrieval[END_REF][START_REF] Kushilevitz | Replication is Not Needed: Single Database, Computationally-Private Information Retrieval[END_REF] and aims to achieve privacy by hiding each query of a user within a set of n random dummy queries. We implemented a Range Query engine, which adds dummy queries to the instances, and found that the effectiveness of Range Queries largely depends on the values of various parameters, among them the number of dummies n, the size of the pool of hostnames to choose the dummies from (N ), and the actual hostnames used as dummies. As a first result we can report that accuracy can be reduced to as low as 10 %, if n = 5 dummies are used per query and dummies are drawn from a set of N = 5000 randomly selected hostnames. In future work we will search for configurations that offer a good trade-off between security and bandwidth.

Conclusion

The behavior-based tracking scheme studied in this paper enables service providers, which have access to the (web) requests of users, to link multiple sessions without cookies or other explicit identifiers. Our analysis shows that behavior-based tracking is feasible in a real-world setting for a large user group: in our DNS query log, in which more than 2000 users are active each day, we correctly link up to 88.2 % of all sessions on a day-to-day basis. Our design manages to achieve this high accuracy, because it is able to resolve ambiguous classification that are caused by fluctuating numbers of users.

Daily changing IP addresses, which are sometimes cited to be important for users' privacy, offer only limited protection against behavior-based tracking. While there are no practical countermeasures so far, we see the introduction of IPv6 as an opportunity to design effective and lightweight techniques that help to prevent profiling and tracking users without their consent.

Fig. 1 :

 1 Fig. 1: Behavior-based tracking scenario

  10-Fold Stratified Cross Validation: first of all, the 20 instances of each class are split randomly, yet equally to obtain 10 disjoint sets (folds): D = D 1 ∪ D 2 ∪ . . . ∪ D 10 . The evaluation takes place in 10 runs k ∈ 1, . . . , 10. In the k -th experiment the instances D train = D \ D k are used to train the classifier. D train contains 9 10 of all instances of every user u. With I u train denoting the training instances of one user, we have D train = I u1 train ∪ . . . ∪ I u3000 train . Based on the supplied training data the classifier has to predict the appropriate classes for the instances in D k . The overall accuracy is finally obtained as average of all 10 runs.

Fig. 2 :

 2 Fig. 2: Cross validation: observed recall values for 3000 users

Fig. 3 :

 3 Fig. 3: Tracking in the real-world setting

cf. http://www.opendns.com and http://code.google.com/speed/public-dns

Each address is supposed to be exclusively used by one resident; in some rare cases devices may be used by multiple users, though.

We found that the actual time of day at which the epochs start has a negligible effect on the accuracy.

Acknowledgments. We thank Martin Wimmer, head of the computing center of the University of Regensburg and his employees, who enabled the compilation of our dataset. We are grateful to the anonymous reviewers, to Arvind Narayanan, to Christopher Piosecny and to our colleagues Karl-Peter Fuchs and Christoph Gerber for their critical feedback and constructive comments.