IEEE/ACM TRANSACTIONS ON NETWORKING r=5l=4 10102 Reade Tag Memory Model 11110100 Tags HemBank1:1010111011010010 01011100 Pointer s 011111009 1=4 01001000 MemBank3: 0111010101000110H() ak=10 01110110 Ot MemBank3 r=5 、bitmask S(4,3.1102） 100 11101100 Fig.6:Illustration of selective reading in Gen2 protocol.7 tags Fig.5:Illustration of a hash function.The figure shows a tag's two are covered by a reader.The reader initiates a Select command memory banks:MemBank1 and MemBank3,which store the tag's S(4,3,1102).As a result,tags of t2,ts,ts and t6 (highlighted in EPC t and the real hash value H(t)respectively.Given an input of red)are only selected to join in the incoming inventory because their r=5 and I=4,the output of h(4)(t,5)equals 10102,which exactly MemBank3s'sub-bitstring (highlighted in red)within 4,7)equals is the sub-bitstring of H(t)within 5,9)bits stored in MemBank3. 1102.Other tags do not meet the condition and remain silent. Acquiring a Bloom filter.Finally,we show how the reader ]as国ac builds a whole BF bit by bit through a series of intercepted P.RN1R inventories in three cases 7.2 Select Query Next,we introduce these issues with details. B.Emulating Hash Functions A hash function,denoted by h((t,r),outputs an I-bit hash 0. value when given a tag's EPC t and a random number r.It takes three inputs:(1)an l-bit tag's EPC number t;(2)an l,-bit random number r;and (3)the bit length of the hash value l.Formally, 10 121416 18 Time (ms) h四(t,r）:{0,1}×{0,1→{0,1} 1) Fig.7:Baseband signals of an intercepted inventory.The inventory where l is also called the dimension of the hash function.The contains a Select,a Query and an RN16 reply.T,T2 and Ts are output is randomly distributed in [0,2).Following a common key timing parameters,which are specified in the Gen2 protocol. The reader detects the presence of RN16 reply to determine if any practice,we create K hash functions by shuffling the output tag responds. using K different random numbers.The kth hash function is denoted byh(t,k).The superscript l is sometimes omitted, quality of randomness at each bit.If the upper application such as h(t,rk),hk(t)or hk,for clarity unless it should be needs a stronger randomness,one could store a truly ran- noted. dom bitstring in the MemBank3 rather than the real hash Memory Banks.Before introducing the hash design,we value,meanwhile save the mapping between the EPC and the need to introduce some background about the memory bank bitstrings in database for future query.In addition,to avoid of tag.The Gen2 air protocol specifies a simple tag memory the dependence of K hash values,one can tactfully choose model:each tag contains four types of non-volatile memory r1,...,rK such that [ri,r1+1)n...n[rk,rK +1)= blocks(called memory banks).The first three banks are used Secondly,The computation of H(t)is performed in a host to store the password,EPC number and TID number.The last computer rather than on tags,so its workload is almost memory bank(MemBank3)is reserved for user-defined data.neglected.Storing H(t)is also performed once until the tag's Fig.5 demonstrates the first and the third memory bank.The EPC is changed,which is unlikely to happen often in practice. Read or write commands are used to read or write data Although writing data into memory bank usually takes a longer from or into these banks respectively. time than reading them,the writing is performed in offline Hash Function.Initially,we compute the real hash value phase thereby its workload is not counted into the acquisition (denoted by H(t))of a tag's EPC by using SHA-1 for tag t, overhead.Thirdly,A possible concern is if today's RFID tags and then store H(t)in the tag's MemBank3 for future use. in the market can serve our design in terms of the operability Note both operations are performed once in the offline phase. of MemBank3.We investigate 40 tag chips from ImpinJ [48]. We define a tag's sub-bitstring within [r,+l)in MemBank3 Alien [49]and NXP [50],whose total market share exceeds as its 1-bit hash value challenged by the random number r. 80%[1].The investigation result suggests that TagMap is In other words,our hash value h((t,r)is a portion of H(t) completely compatible with the EPCglobal Gen2 air protocol stored in MemBank3.Fig.5 demonstrates the relation between and can serve 97.5%types of tags,except those that are read- the real hash value and our hash value,where the tag's 4-bit only(More details refer to Sec.VI.). hash value h(4)(t,5)=10102(the ()2 means a value in binary format.).Clearly,our design does not require a tag to equip a real hash function or gets its chip involved. C.Answering the Question of Presence Discussion.Evidently,h((t,r)is random and its random- A simple way to obtain a tag's hash value is to Read ness is derived from H(t).which is supposed to have good the corresponding sub-bitstring from its MemBank3.However,IEEE/ACM TRANSACTIONS ON NETWORKING 5 Tag Memory Model 0 1 1 1 0 1 0 1 1 1 0 0 0 1 1 0 H(t) MemBank1: 1 0 1 0 1 1 1 0 1 1 0 1 0 0 1 0 t MemBank3: 10102 1 0 1 0 l = 4 bitmask r = 5 r = 5,l = 4 Fig. 5: Illustration of a hash function. The figure shows a tag’s two memory banks: MemBank1 and MemBank3, which store the tag’s EPC t and the real hash value H(t) respectively. Given an input of r = 5 and l = 4, the output of h (4)(t, 5) equals 10102, which exactly is the sub-bitstring of H(t) within [5, 9) bits stored in MemBank3. • Acquiring a Bloom filter. Finally, we show how the reader builds a whole BF bit by bit through a series of intercepted inventories in three cases. Next, we introduce these issues with details. B. Emulating Hash Functions A hash function, denoted by h (l) (t, r), outputs an l-bit hash value when given a tag’s EPC t and a random number r. It takes three inputs: (1) an lt-bit tag’s EPC number t; (2) an lr-bit random number r; and (3) the bit length of the hash value l. Formally, h (l) (t, r) : {0, 1} lt × {0, 1} lr → {0, 1} l (1) where l is also called the dimension of the hash function. The output is randomly distributed in [0, 2 l ). Following a common practice, we create K hash functions by shuffling the output using K different random numbers. The k th hash function is denoted by h (l) k (t, rk). The superscript l is sometimes omitted, such as h(t, rk), hk(t) or hk, for clarity unless it should be noted. Memory Banks. Before introducing the hash design, we need to introduce some background about the memory bank of tag. The Gen2 air protocol specifies a simple tag memory model: each tag contains four types of non-volatile memory blocks (called memory banks). The first three banks are used to store the password, EPC number and TID number. The last memory bank (MemBank3) is reserved for user-defined data. Fig. 5 demonstrates the first and the third memory bank. The Read or Write commands are used to read or write data from or into these banks respectively. Hash Function. Initially, we compute the real hash value (denoted by H(t)) of a tag’s EPC by using SHA-1 for tag t, and then store H(t) in the tag’s MemBank3 for future use. Note both operations are performed once in the offline phase. We define a tag’s sub-bitstring within [r, r +l) in MemBank3 as its l-bit hash value challenged by the random number r. In other words, our hash value h (l) (t, r) is a portion of H(t) stored in MemBank3. Fig. 5 demonstrates the relation between the real hash value and our hash value, where the tag’s 4-bit hash value h (4)(t, 5) = 10102 (the (·)2 means a value in binary format.). Clearly, our design does not require a tag to equip a real hash function or gets its chip involved. Discussion. Evidently, h (l) (t, r) is random and its random￾ness is derived from H(t), which is supposed to have good MemBank3 Reader Tags Select 0 1 0 1 1 1 0 0 1 1 1 1 0 1 0 0 0 1 1 1 1 1 0 0 0 1 1 1 0 1 1 0 0 1 0 1 1 1 0 0 0 1 0 0 1 0 0 0 1 1 1 0 1 1 0 0 Select t1 t2 t3 t4 t5 t6 t7 Pointer =4 Length =3 Mask = 1102 S(4, 3, 1102) Reader Select Query RN16 Time Fig. 6: Illustration of selective reading in Gen2 protocol. 7 tags are covered by a reader. The reader initiates a Select command S(4, 3, 1102). As a result, tags of t2, t3, t5 and t6 (highlighted in red) are only selected to join in the incoming inventory because their MemBank3s’ sub-bitstring (highlighted in red) within [4, 7) equals 1102. Other tags do not meet the condition and remain silent. 0 2 4 6 8 10 12 14 16 18 Time (ms) 0 0.2 0.4 0.6 0.8 1 1.2 Amplitude (v) Intercepted inventory Select Query RN16 Preamble ⌧1 ⌧2 ⌧3 READER TAG P RN16 Select Query Select Time slot Fig. 7: Baseband signals of an intercepted inventory. The inventory contains a Select, a Query and an RN16 reply. τ1, τ2 and τ3 are key timing parameters, which are specified in the Gen2 protocol. The reader detects the presence of RN16 reply to determine if any tag responds. quality of randomness at each bit. If the upper application needs a stronger randomness, one could store a truly ran￾dom bitstring in the MemBank3 rather than the real hash value, meanwhile save the mapping between the EPC and the bitstrings in database for future query. In addition, to avoid the dependence of K hash values, one can tactfully choose r1, . . . , rK such that [r1, r1 + l) ∩ · · · ∩ [rK, rK + l) = ∅. Secondly, The computation of H(t) is performed in a host computer rather than on tags, so its workload is almost neglected. Storing H(t) is also performed once until the tag’s EPC is changed, which is unlikely to happen often in practice. Although writing data into memory bank usually takes a longer time than reading them, the writing is performed in offline phase thereby its workload is not counted into the acquisition overhead. Thirdly, A possible concern is if today’s RFID tags in the market can serve our design in terms of the operability of MemBank3. We investigate 40 tag chips from ImpinJ [48], Alien [49] and NXP [50], whose total market share exceeds 80% [1]. The investigation result suggests that TagMap is completely compatible with the EPCglobal Gen2 air protocol and can serve 97.5% types of tags, except those that are read￾only(More details refer to Sec.VI.). C. Answering the Question of Presence A simple way to obtain a tag’s hash value is to Read the corresponding sub-bitstring from its MemBank3. However