國 立 交 通 大 學 網 路 工 程 研 究 所 碩 士 論 文 在 RFID Gen2 下 偵 測 Blocker Tag 之 研 究 A study of Blocker Tag Detection Based on RFID Gen2 Protocol 研 究 生 : 呂 安 勝 指 導 教 授 : 蔡 文 能 教 授 中 華 民 國 九 十 八 年 五 月
在 RFID Gen2 下 偵 測 Blocker Tag 之 研 究 A study of Blocker Tag Detection Based on RFID Gen2 Protocol 研 究 生 : 呂 安 勝 指 導 教 授 : 蔡 文 能 Student:An-Sheng Lu Advisor:Wen-Nung Tsai 國 立 交 通 大 學 網 路 工 程 研 究 所 碩 士 論 文 A Thesis Submitted to Institute of Network Engineering College of Computer Science National Chiao Tung University in partial Fulfillment of the Requirements for the Degree of Master in Computer Science May 2009 Hsinchu, Taiwan, Republic of China 中 華 民 國 九 十 八 年 五 月
中 文 摘 要 在 RFID Gen2 下 偵 測 Blocker Tag 之 研 究 學 生 : 呂 安 勝 指 導 教 授 : 蔡 文 能 國 立 交 通 大 學 資 訊 工 程 學 系 ( 研 究 所 ) 碩 士 班 摘 要 RFID( 無 線 射 頻 辨 識 ) 是 一 種 利 用 無 線 射 頻 傳 送 識 別 資 料 的 技 術, 提 供 小 型 且 非 接 觸 式 通 訊, 應 用 層 面 相 當 廣 泛, 被 視 為 未 來 生 活 上 的 基 礎 設 建 設 但 是,RFID Tag 硬 體 在 先 天 上 的 限 制, 引 發 許 多 威 脅 到 安 全 性 的 問 題 產 生, 如 : 隱 私 問 題 Tag 竊 聽 追 蹤 或 複 製 等 攻 擊 針 對 這 些 相 關 安 全 議 題, 許 多 的 相 關 研 究 被 提 出 來,Blocker Tag 便 是 其 中 之 一 Blocker tag 是 對 於 隱 私 權 保 護 的 一 個 解 決 方 案, 是 一 種 類 似 干 擾 訊 號 的 演 算 法, 利 用 這 個 演 算 法 來 保 護 tag 不 會 被 讀 取 但 是, 一 旦 這 個 方 案 被 人 惡 意 的 濫 用, 人 們 可 以 在 商 店 中 帶 走 商 品 並 巧 妙 的 避 過 結 帳 掃 描 等, 可 能 會 造 成 商 業 或 作 業 損 失 的 缺 失, 而 如 何 去 偵 測 出 是 否 有 存 在 Blocker tag, 即 是 一 種 需 要 解 決 的 問 題 為 了 解 決 這 個 問 題, 本 篇 論 文 設 計 出 SLN-algorithm 來 偵 測 存 在 的 Blocker tag, 經 由 模 擬 實 驗 結 果, 證 明 不 僅 能 有 效 的 偵 測 Blocker Tag 的 存 在, 並 且 與 [1] 比 較 後 偵 測 率 和 效 能 都 勝 出 i
英 文 摘 要 A study of Blocker Tag Detection Based on RFID Gen2 Protocol Student:An-Sheng Lu Advisor:Wen-Nung Tsai Institute of Computer Science and Information Engineering National Chiao-Tung University Abstact Radio Frequency Identification (RFID) is a sensor network technology to automate identification. RFID systems had been applied to many fields and have been considered as a key infrastructure for the ubiquitous society in the future. However, due to the inherent drawbacks, RFID causes various security threats like privacy problems, tag wiretapping, tracking or cloning, etc. To address these issues, lots of solutions had been proposed. The Blocker Tag is one of these. Blocker tag is a solution for privacy protection. It uses a kind of algorithm which is similar to using jamming signal. However, if this method is used in malicious way, the inventory process of the RFID reader might be stopped, and people in department store may carry some merchandise out without accounting. Find out a way to detect the Blocker Tag could be an important issue on RFID. To resolve this problem, we proposed a scheme SLN-algorithm to detect the existence of Blocker tags. In our experiments, the results have demonstrated that our detection mechanism is more effective than the mechanism proposed in [1] on detecting Blocker Tag. ii
致 謝 在 兩 年 的 努 力 之 下, 終 於 完 成 了 我 的 畢 業 論 文, 中 間 遇 到 了 許 多 的 困 難 與 問 題, 受 到 了 許 多 人 的 幫 助, 在 此 一 一 感 謝 首 先, 要 感 謝 的 是 我 的 指 導 教 授 蔡 文 能 教 授, 在 碩 士 班 的 兩 年 之 中, 老 師 給 我 許 多 方 面 的 指 導, 讓 我 獲 益 良 多, 本 身 也 因 此 成 長 了 不 少 再 者, 感 謝 我 的 父 母 與 兩 位 兄 弟 給 我 一 個 平 穩 的 環 境 在 背 後 支 持 我, 讓 我 能 夠 專 心 學 習 接 著 要 感 謝 實 驗 室 的 學 長 蔡 宗 易 學 長 和 陳 文 學 長, 和 學 長 們 一 起 討 論 與 研 究, 也 不 辭 辛 勞 的 指 引 我 研 究 的 方 向, 非 常 感 謝 最 後 要 感 謝 的 是 實 驗 室 的 同 學 們, 大 家 一 起 工 作 學 習, 並 且 互 相 幫 助, 讓 我 有 個 難 忘 的 碩 士 回 憶 需 要 感 謝 的 人 時 在 太 多 了, 在 我 難 過 或 沮 喪 時, 給 予 我 幫 助 與 支 持, 讓 我 度 過 種 種 難 關, 真 心 感 謝 曾 經 幫 助 過 我 的 人, 謝 謝 你 們 iii
目 錄 中 文 摘 要...i 英 文 摘 要...ii 致 謝...iii 圖 目 錄...vi 表 目 錄...viii 第 一 章 緒 論...1 1.1 研 究 動 機...1 1.2 論 文 架 構...1 第 二 章 背 景 知 識...3 2.1 RFID 系 統...3 2.1.1 RFID 系 統 元 件...3 2.1.2 RFID 系 統 應 用...4 2.1.3 RFID 隱 私 問 題...5 2.2 EPCglobal...6 2.2.1 EPCglobal Network...6 2.2.2 EPCglobal Class1 Gen2 Air Interface protocol...8 2.2.3 EPCglobal 安 全 防 護...13 Chapter 3 相 關 研 究...15 3.1 RSA Blocker tag...15 3.1.1 The Blocker Tag: Selective Blocking of RFID Tags for Consumer Privacy...15 3.1.2 Soft blocking: flexible blocker tags on the cheap...17 3.1.3 RFID privacy protect using blocker tag with anti-blocker tag scheme...18 Chapter 4 系 統 架 構...22 4.1 系 統 概 觀 與 假 設...22 4.2 系 統 設 計...25 4.2.1 Select 階 段...25 4.2.2 Inventory 階 段...25 4.2.3 Access 階 段...29 Chapter 5 分 析 與 實 驗 結 果...30 5.1 實 驗 環 境...30 5.2 系 統 元 件...31 5.2.1 標 籤...31 5.2.2 讀 取 器...32 5.3 分 析...33 iv
5.3.1 偵 測 率...35 5.3.2 時 間 性...37 Chapter 6 結 論...45 6.1 貢 獻...45 6.2 未 來 工 作...45 Reference...47 v
圖 目 錄 圖 1:RFID 系 統...3 圖 2:EPCglobal Network 架 構...7 圖 3: 讀 取 器 的 運 作 與 標 籤 的 狀 態...8 圖 4:Query 命 令 在 RFID 的 通 訊 協 定...9 圖 5: 標 籤 的 狀 態 圖...10 圖 6: 標 籤 的 記 憶 體 配 置...11 圖 7: 分 段 式 ALOHA 通 訊 協 定...12 圖 8:Q 演 算 法...12 圖 9: 標 籤 中 密 碼 的 記 憶 體 配 置...14 圖 10:Blocker Tag 示 意 圖...15 圖 11: 樹 狀 演 算 法...16 圖 12:Blocker Tag 機 制 在 樹 狀 演 算 法...17 圖 13: 軟 性 Blocker Tag 機 制 在 樹 狀 演 算 法...18 圖 14: 間 諜 標 籤 機 制...19 圖 15:Blocker tag 造 成 的 碰 撞...19 圖 16: 時 間 影 響 的 衝 突 率...20 圖 17:ACK 和 Query 的 數 量 比 例...21 圖 18:Query 命 令 訊 框...23 圖 19:QueryAdjust 命 令 訊 框...23 圖 20: 新 Query 命 令 訊 框...24 圖 21: 新 QueryAdjust 命 令 訊 框...24 圖 22:Gen 2 命 令 的 長 度...24 圖 23:SLN 演 算 法 的 流 程 圖...26 圖 24:SLN 變 數 控 制 的 運 作...27 圖 25:SLN=1 時,Rn = Rn-1...29 圖 26: 環 境 的 函 式...31 圖 27:Blocker Tag 的 案 例 1...33 圖 28:Blocker Tag 的 案 例 2-(1)...34 圖 29:Blocker Tag 的 案 例 2-(2)...34 圖 30:Blocker Tag 的 案 例 3-(1)...35 圖 31:Blocker Tag 的 案 例 3-(2)...35 圖 32: 正 常 的 RFID 系 統...37 圖 33: 笨 拙 的 Blocker Tag( 案 例 1)...38 圖 34: 各 演 算 法 在 案 例 1 的 效 能...38 圖 35:Q 演 算 法 在 案 例 2 的 效 能...39 圖 36:AQ 演 算 法 在 案 例 2 的 效 能...39 vi
圖 37:SLN 演 算 法 在 案 例 2 的 效 能...40 圖 38: 各 演 算 法 在 案 例 2 的 效 能...40 圖 39:Q 演 算 法 在 案 例 的 效 能...41 圖 40:AQ 演 算 法 在 案 例 3 的 效 能...42 圖 41:SLN 演 算 法 在 案 例 3 的 效 能...43 圖 42: 各 演 算 法 在 案 例 3-(2) 的 效 能...43 vii
表 目 錄 表 1: 實 驗 環 境...30 表 2: 標 籤 類 別 中 的 函 式...32 表 3: 讀 取 器 類 別 中 的 函 式...32 表 4: 各 案 例 的 比 較...44 viii
第 一 章 緒 論 無 線 射 頻 識 別 (Radio Frequency Identification,RFID) 是 一 種 次 世 代 的 辨 識 系 統, 具 有 快 速 辨 識 的 能 力, 其 功 能 足 以 取 代 條 碼, 成 為 現 今 社 會 最 適 合 的 辨 識 管 理 系 統 RFID 是 一 種 還 在 發 展 中 的 技 術, 目 前 在 安 全 性 尚 存 在 一 些 問 題 有 待 解 決 在 本 章 節 中, 會 先 於 1.1 節 介 紹 本 論 文 研 究 的 動 機 與 目 標 1.2 節 介 紹 本 論 文 的 組 織 架 構 1.1 研 究 動 機 RFID Tags 在 硬 體 上 有 所 限 制, 引 發 許 多 威 脅 到 安 全 性 的 問 題 產 生, 如 : 隱 私 問 題 Tag 竊 聽 追 蹤 或 複 製 等 攻 擊 為 了 解 決 這 些 相 關 安 全 問 題, 許 多 的 安 全 防 護 措 施 被 提 出 來, 其 中 部 分 的 安 全 研 究 是 建 立 在 EPCglobal RFID Class1 Gen2 標 準 的 環 境 下 實 施, 例 如 :Back-end hash scheme RSA Blocker tag 等 其 中, 我 認 為 RSA Blocker tag 是 比 較 符 合 標 準 且 能 夠 普 遍 性 推 廣 的 防 護 措 施 RSA Blocker tag 是 利 用 碰 撞 排 程 的 方 式 隔 絕 讀 取 器 讀 取 tags 的 資 訊 當 辨 識 物 品 在 一 定 範 圍 內 的 時 候, 只 要 貼 附 一 張 Blocker tag, 就 能 有 效 的 保 護 物 品 資 訊 不 被 外 漏 ; 然 而 若 是 有 人 惡 意 使 用 Blocker tag 隔 絕 物 品 並 且 攜 帶 離 開 保 護 場 所, 會 發 生 辨 識 物 品 在 不 被 察 覺 的 情 況 下 消 失, 這 樣 的 惡 意 攻 擊 並 無 有 效 的 偵 測 方 法 因 此 本 論 文 提 出 一 種 機 制 來 偵 測 Blocker Tag 的 惡 意 攻 擊 因 為 目 前 RFID 在 全 球 共 同 認 可 的 標 準 是 EPCglobal Class 1 Gen 2, 在 此 提 出 的 偵 測 機 制 是 基 於 Gen 2 標 準 的 環 境 上, 加 強 一 些 控 制 命 令 功 能, 希 望 能 夠 以 安 全 且 有 效 的 方 式 偵 測 出 Blocker Tag 的 存 在 1.2 論 文 架 構 本 篇 論 文 的 組 織 架 構 如 下 : 第 一 章 緒 論 介 紹 研 究 動 機 與 目 標 第 二 章 背 景 知 識 介 紹 RFID 系 統 的 運 作 原 理 應 用 與 隱 私 問 題, 以 及 EPCglobal 所 提 出 的 EPC 網 路 Gen2 標 準 和 安 全 防 護 功 能 第 三 章 相 關 研 究 依 序 介 紹 最 早 提 出 Blocker Tag 阻 擋 消 費 者 隱 私 的 論 文, 接 著 進 化 為 可 彈 性 阻 擋 的 Blocker Tag 的 論 文, 最 後 介 紹 有 人 提 出 偵 測 Blocker Tag 系 統 的 論 文 第 四 章 系 統 架 構 將 提 出 新 的 偵 測 方 法, 有 效 地 判 斷 Blocker Tag 的 存 在 第 五 章 分 析 與 實 驗 結 1
果 利 用 模 擬 實 驗 量 測 出 來 的 數 據 證 明 本 論 文 提 出 的 新 偵 測 機 制 不 僅 可 行, 並 且 比 3.1.3 節 的 論 文 [1] 更 安 全 有 效 率 第 六 章 結 論 提 出 研 究 機 制 的 整 理 與 總 結, 以 及 未 來 能 夠 繼 續 研 究 的 方 向 2
第 二 章 背 景 知 識 RFID(Radio Frequency Identification), 顧 名 思 義, 是 一 種 利 用 無 線 射 頻 來 傳 送 識 別 資 料 的 技 術, 藉 此 達 到 身 份 辨 識 的 目 的 此 技 術 的 優 點 在 其 可 提 供 小 型 非 接 觸 式 通 訊 以 及 加 密 技 術, 藉 由 讀 取 藏 於 RFID 裡 多 樣 且 具 可 辨 識 的 資 訊, 應 用 層 面 廣 泛 因 此, 有 一 個 EPCglobal 的 規 範 組 織 為 了 方 便 推 廣 RFID, 制 定 了 RFID 相 關 的 EPCglobal 標 準 在 此 章 節 中,2.1 會 介 紹 RFID 系 統 與 架 構 2.2 介 紹 EPCglobal, 以 及 其 制 定 的 RFID 標 準 協 定 和 安 全 防 護 2.1 RFID 系 統 RFID( 無 線 射 頻 辨 識 ) 是 一 種 有 未 來 發 展 性 的 技 術, 具 有 自 動 辨 識 技 術, 可 以 幫 助 人 們 利 用 無 線 射 頻 的 方 式 接 收 並 管 理 訊 息 此 系 統 主 要 由 一 個 無 線 通 訊 IC 以 及 天 線 當 作 標 籤, 利 用 讀 取 器 接 收 標 籤 傳 出 的 訊 號, 將 訊 號 傳 送 至 後 端 伺 服 器 作 管 理 許 多 利 用 RFID 的 應 用, 例 如 製 造 商 使 用 在 供 應 鏈 管 理 系 統 停 車 場 管 理 系 統 賣 場 購 物 系 統 和 機 場 行 李 管 控 系 統 等, 所 以 RFID 被 看 好 是 未 來 一 種 無 所 不 在 的 基 礎 建 設 建 置 在 社 會 上 底 下 先 介 紹 RFID 系 統 的 組 織 架 構 運 作 原 理 及 硬 體 設 備 2.1.1 RFID 系 統 元 件 RFID 系 統 的 運 作 方 式 是 先 將 標 籤 貼 附 在 需 要 辨 識 的 物 品 上, 讀 取 器 在 固 定 範 圍 內 發 送 無 線 射 頻 搜 尋 標 籤, 並 且 讀 取 儲 存 在 標 籤 裡 的 訊 息, 然 後 將 接 收 到 的 訊 息 傳 回 到 後 端 應 用 伺 服 器, 最 後 由 伺 服 器 將 蒐 集 的 資 料 應 用 在 各 種 不 同 的 功 能 上, 例 如 : 倉 儲 管 理 的 貨 物 資 料 寵 物 管 理 的 定 位 系 統 電 子 錢 包 的 帳 務 系 統 等 應 用 RFID 的 系 統 元 件 主 要 分 成 三 部 份 ( 圖 1), 分 別 是 : 標 籤 (Tags) 讀 取 器 (Readers) 和 後 端 應 用 伺 服 器 (Back-end Application) 圖 1:RFID 系 統 資 料 來 源 :[20] 3
1. RFID 標 籤 RFID 標 籤 (Tags) 是 由 晶 片 和 天 線 所 組 成 的, 它 能 夠 儲 存 物 品 的 訊 息, 像 是 : 產 品 種 類 產 品 製 造 商 和 產 品 身 分 等, 當 讀 取 器 發 出 要 求 的 時 候, 標 籤 便 會 將 這 些 訊 息 傳 送 出 去 標 籤 根 據 能 量 提 供 上 的 不 同 可 以 分 成 主 動 式 半 被 動 式 和 被 動 式 的 標 籤, 而 在 EPCglobal 標 準 下 是 採 用 被 動 式 標 籤 主 動 式 標 籤 擁 有 自 己 的 電 池 提 供 能 量, 通 常 伴 隨 著 較 強 大 的 運 算 能 力 和 較 長 的 傳 輸 距 離, 但 是 標 籤 的 生 命 週 期 被 電 池 所 控 制, 且 成 本 價 格 比 較 昂 貴 半 被 動 式 tag 使 用 電 池 能 量 提 供 給 晶 片 運 算 能 力, 溝 通 的 能 量 則 來 自 於 reader 所 發 送 的 電 磁 波 被 動 式 沒 有 自 己 的 電 池, 標 籤 的 主 要 能 量 來 自 於 讀 取 器 所 發 出 的 無 線 電 磁 波 訊 號, 標 籤 接 收 到 波 動 產 生 微 量 電 流, 透 過 微 量 電 流 讓 晶 片 運 算 處 理, 跟 主 動 式 標 籤 比 起 來, 被 動 式 標 籤 運 算 能 力 以 及 傳 輸 距 離 都 比 較 衰 弱, 被 動 式 標 籤 只 具 有 低 階 計 算 能 力, 不 具 有 高 階 計 算 功 能 如 :XOR,Hash function 對 稱 性 加 密 就 無 法 支 援 在 被 動 式 標 籤 上 優 點 在 於 生 命 週 期 沒 有 被 電 池 限 制 住, 成 本 價 格 便 宜 大 部 分 的 RFID 應 用 都 是 採 取 被 動 式 標 籤, 因 為 價 錢 上 的 考 量 通 常 可 以 接 受 的 標 籤 成 本 不 能 超 過 5 分 錢 ($USD) 2. RFID 讀 取 器 讀 取 器 (Reader) 會 詢 問 其 附 近 的 RFID 標 籤 並 讀 取 標 籤 裡 的 資 訊, 然 後 將 資 訊 再 往 前 傳 向 後 端 資 料 庫 提 供 給 更 前 線 的 應 用 讀 取 器 也 能 夠 透 過 下 達 指 令 的 方 式, 更 新 標 籤 裡 儲 存 的 資 訊, 以 達 到 動 態 更 新 且 重 複 利 用 的 功 能 3. RFID 後 端 應 用 伺 服 器 後 端 伺 服 器 儲 存 的 RFID 標 籤 資 訊 通 常 包 括 : 物 件 名 稱 價 值 位 置 製 造 商 和 擁 有 者 等, 根 據 相 關 的 應 用, 資 料 庫 會 變 動 標 籤 的 紀 錄 舉 例 來 說, 當 資 料 庫 是 在 幫 助 圖 書 館 管 理 的 時 候, 讀 者 租 借 書 本 將 會 更 新 資 料 庫 中 該 書 本 標 籤 的 時 間 紀 錄, 方 便 掌 控 圖 書 外 借 的 時 間 ; 其 它 像 零 售 商 倉 儲 系 統 的 管 理 機 場 行 李 運 送 的 管 制, 都 是 類 似 於 圖 書 館 的 應 用 方 式 這 些 不 同 類 的 工 作 型 態, 是 依 據 後 端 應 用 伺 服 器 的 應 用 方 向 而 有 所 不 同 2.1.2 RFID 系 統 應 用 RFID 最 主 要 的 功 能 是 在 與 辨 識 不 同 的 物 品 RFID 技 術 其 本 身 的 優 勢, 讓 RFID 系 統 以 各 種 形 式 出 現 於 日 常 生 活 中, 大 幅 提 升 生 活 的 便 利 性 目 前 於 市 面 上 的 4
RFID 系 統 隨 處 可 見, 門 禁 系 統 以 及 悠 遊 卡 算 是 我 們 耳 熟 能 詳 的 應 用 首 先 我 們 可 以 看 到 2006 所 舉 辦 的 世 界 盃 足 球 賽, 國 際 足 球 協 會 (FIFA) 與 飛 利 浦 半 導 體 合 作, 將 RFID 導 入 本 次 足 球 賽 的 售 票 系 統 中 ;2006 暑 假 台 北 市 新 開 幕 了 一 家 遊 樂 園 - 神 奇 寶 貝 樂 園 則 在 台 灣 率 先 將 RFID 導 入 遊 戲 中 利 用 此 項 技 術 的 特 性, 不 僅 可 用 來 杜 絕 假 門 票 的 發 生, 球 場 周 邊 亦 設 有 相 關 RFID 設 施, 觀 眾 可 利 用 門 票 儲 值, 來 進 行 購 物 付 款 停 車 寄 放 物 品 和 搭 乘 大 眾 交 通 工 具 等 的 服 務, 讓 門 票 更 有 價 值, 更 加 肯 定 了 RFID 系 統 在 有 價 證 券 上 的 應 用 實 力 近 年 來 出 現 許 多 整 合 型 的 RFID 晶 片 應 用, 有 些 校 園 與 金 融 業 者 合 作, 提 供 電 子 化 的 學 生 證, 使 學 生 證 除 了 可 以 做 為 進 出 校 園 的 辨 識, 也 提 供 許 多 小 額 金 融 服 務, 或 是 與 金 融 卡 合 併 的 服 務 台 北 市 南 湖 國 小 即 利 用 主 動 式 RFID 以 及 無 線 網 路 整 合 應 用, 來 提 升 校 園 安 全 ; 透 過 讓 每 一 位 學 生 身 上 配 戴 主 動 式 標 籤, 並 利 用 讀 卡 機 讀 取 後 將 辨 識 資 料 經 由 無 線 網 路 送 至 伺 服 器 進 行 資 料 的 篩 選 和 處 理 來 確 保 校 園 學 童 的 安 全 RFID 晶 片 植 入 技 術 近 來 也 漸 漸 地 嶄 露 頭 角, 娛 樂 產 業 在 這 股 RFID 的 浪 潮 下 也 開 發 新 的 應 用, 在 不 久 的 未 來,RFID 將 大 量 融 入 社 會 之 中, 與 人 們 生 活 息 息 相 關 2.1.3 RFID 隱 私 問 題 雖 然 RFID 帶 給 我 們 許 多 的 方 便, 但 卻 也 帶 來 了 某 些 程 度 上 的 風 險, 如 遭 到 惡 意 探 測, 就 有 可 能 將 個 人 資 料 或 是 金 融 卡 的 資 訊 洩 漏, 如 此 將 帶 給 使 用 者 不 少 安 全 性 上 的 威 脅 這 些 RFID 系 統 的 應 用, 其 背 後 卻 潛 藏 許 多 安 全 性 的 風 險 近 年 來 也 出 現 越 來 越 多 的 RFID 安 全 性 事 件 發 生, 如 國 外 就 發 生 破 解 護 照 上 RFID 晶 片 的 事 件 由 此 可 見, 隨 著 RFID 系 統 應 用 的 範 圍 愈 加 廣 泛, 其 系 統 的 安 全 性 就 備 受 考 驗,RFID 系 統 的 安 全 性 也 已 經 是 不 容 忽 視 的 一 項 議 題 隱 私 問 題 (privacy issues) 主 要 分 類 為 資 料 隱 私 (data privacy) 和 位 置 隱 私 (location privacy) 資 料 隱 私 的 情 況, 通 常 是 由 攻 擊 者 利 用 讀 取 器 在 不 被 發 現 的 情 況 下 讀 取 目 標 特 定 的 標 籤 資 料, 攻 擊 者 可 以 取 得 目 標 的 商 品 資 訊 物 品 價 值 甚 至 個 人 的 身 份 證 識 別 編 號 ; 位 置 隱 私 的 威 脅, 因 為 人 們 攜 帶 RFID 標 籤 在 身 上 活 動, 攻 擊 者 透 過 持 續 讀 取 目 標 標 籤 資 料 來 跟 蹤 目 標 標 籤 的 行 蹤, 可 以 得 到 目 標 所 有 的 移 動 路 徑, 且 人 們 也 很 難 發 現 自 己 已 經 被 鎖 定 追 蹤 了 美 國 國 家 標 準 技 術 局 (The National Institute of Standards and Technology,NIST) 便 針 對 RFID 技 術 公 佈 了 一 些 RFID 安 全 性 導 引, 並 且 在 此 報 告 中 呼 籲, 設 計 RFID 系 統 時 也 需 要 將 其 安 全 性 加 入 考 量, 避 免 造 成 許 多 安 全 性 上 的 問 題 RFID 系 統 的 基 本 架 構 中, 可 以 得 知 除 了 標 籤 與 讀 取 器 之 間 的 資 料 傳 輸 之 外, 仍 然 會 與 後 端 的 伺 服 器 中 介 軟 體 連 結, 這 之 中 也 將 潛 藏 一 些 原 本 就 存 在 的 網 路 安 全 議 題 經 由 以 上 的 分 析 後, 以 及 所 發 生 的 各 種 RFID 系 統 的 安 全 性 5
問 題, 可 以 得 知 現 今 的 RFID 系 統 其 安 全 性 依 然 不 足 2.2 EPCglobal EPCglobal 是 2003 年 11 月 建 立 的, 由 全 世 界 一 百 多 個 國 家, 經 過 六 年 的 研 究 工 作 才 建 立 起 來 的, 是 對 RFID 技 術 新 的 應 用 EPCglobal 是 一 個 全 球 組 織, 代 表 了 各 行 業 各 部 門 的 利 益, 目 的 是 開 發 由 用 戶 主 導 的 新 技 術, 實 現 多 行 業 跨 全 球 的 産 品 電 子 代 碼 技 術 目 前,EPCglobal 在 全 球 有 545 家 會 員, 其 中 20% 以 上 的 會 員 企 業 總 部 設 在 亞 洲, 亞 洲 也 是 EPCglobal 會 員 增 長 最 快 的 地 區 EPC 是 一 項 能 在 供 應 鏈 中 準 確 識 別 單 一 産 品 的 技 術, 在 信 息 可 辨 識 方 面 具 有 獨 特 的 優 勢 EPCglobal 的 主 要 工 作 是 制 定 標 準, 以 用 戶 需 求 為 驅 動, 標 準 的 制 定 也 是 為 了 滿 足 用 戶 的 要 求, 是 為 識 別 各 種 商 業 利 益 而 用 的 EPCglobal 跟 ISO 也 有 建 設 性 的 聯 系, 目 前,EPCglobal RFID Class-1 Generation-2 standard[4] 被 制 定 出 來, 並 且 ISO-18000-6 Type-C 以 此 標 準 為 主 制 定 規 格, 認 可 EPCglobal 標 準 在 900MHz RFID 頻 道 2.2.1 EPCglobal Network EPCglobal Network Framework)( 圖 2) 主 要 使 用 EPC code RFID 和 資 訊 網 絡 系 統 等 技 術, 建 立 RFID 全 球 標 準 架 構, 為 供 應 鏈 運 作 管 理 與 追 蹤 能 夠 提 高 效 率 與 準 確 性, 讓 企 業 間 透 過 電 子 方 式 共 享 資 料 在 圖 2 的 各 個 元 件 皆 有 制 定 該 元 件 的 標 準, 其 標 準 的 細 節 可 以 參 考 網 站 [17] 6
圖 2:EPCglobal Network 架 構 在 RFID 系 統 的 架 構 中, 由 標 籤 到 讀 取 器, 是 以 無 線 電 磁 波 進 行 資 訊 交 換, 並 在 使 用 被 動 式 標 籤 時, 需 要 以 電 磁 波 對 遠 端 標 籤 進 行 通 電 啟 動 其 運 作, 在 不 同 電 波 操 作 頻 率 135kHz 至 5.8GHz, 選 擇 適 當 的 標 籤 與 讀 取 器 系 統 以 及 配 備 周 邊 設 施, 建 立 一 個 RFID 系 統 進 行 資 訊 詢 答 之 區 域 (Interrogation zone), 這 是 RFID 在 硬 體 設 備 上 進 行 的 工 作 與 環 境 詢 問 區 建 立 之 後, 散 佈 的 標 籤 資 訊 (Tag Data), 經 由 EPC 規 範 之 編 碼 格 式 (Tag protocol UHF Class1 Gen2) 進 行 標 籤 資 訊 轉 譯 (Tag data translation), 讀 取 器 將 詢 問 區 中 Tag 資 訊 蒐 集 後, 整 合 為 有 意 義 的 資 訊, 作 為 辨 識 查 詢 管 理 等 應 用 之 依 據, 此 過 程 由 EPC architecture framework 建 構 成 三 層 網 路 架 構 : 識 別 (Identify) 擷 取 (Capture) 與 資 訊 交 換 (Exchange) 辨 識 層 定 義 EPC 實 體 物 件 交 換 標 準, 確 保 當 某 一 使 用 者 將 實 體 物 件 送 至 另 一 使 用 者 時, 接 收 方 能 知 道 這 個 實 體 物 件 的 EPC 碼 並 且 正 確 判 讀 在 擷 取 層 主 要 定 義 讀 取 器 資 訊 讀 取 解 碼 格 式 (Reader protocol & LLRP), 定 義 重 要 基 礎 建 設 元 素 需 要 收 集 與 紀 錄 的 EPC 資 料 之 介 面 標 準, 讓 會 員 能 以 相 容 互 通 的 構 件 配 置 自 己 的 內 部 系 統 最 後 在 資 訊 交 換 層, 使 用 者 藉 由 EPCglobal Network 相 互 交 換 資 料 而 受 惠, 定 義 出 EPC 資 料 交 換 標 準, 讓 單 一 使 用 者 能 與 另 一 位 使 用 者 之 間 藉 由 點 對 點 互 動 7
來 共 用 EPC 的 資 料, 並 得 以 使 用 EPCglobal 核 心 服 務 與 其 他 共 享 服 務 以 增 加 便 利 性 經 由 事 件 觸 發 (Application Level Event) 後, 透 過 物 件 命 名 服 務 (Object name service) 和 資 訊 儲 存 中 心 (EPCIS), 進 行 認 證 流 程 (Certificate profile), 流 程 履 歷 管 理 (Pedigree), 或 者 是 其 他 的 系 統 服 務 項 目 (Discovery services), 實 現 各 項 RFID 系 統 識 別 應 用 乃 至 於 感 測 器 網 路 的 發 展 與 智 慧 生 活 化 應 用 2.2.2 EPCglobal Class1 Gen2 Air Interface protocol EPCglobal Gen2 協 議 定 義 了 物 理 和 邏 輯 要 求 給 被 動 式 散 播 (passive-backscatter) 詢 問 者 優 先 (Interrogator-talk-first) RFID(radio-frequency identification) 在 860MHz 960MHz 的 頻 率 範 圍, 克 服 了 EPCglobal 以 前 Class0 和 Class1 的 很 多 限 制 它 具 有 全 面 的 框 架 和 加 強 的 功 能, 能 夠 在 高 密 度 讀 取 器 的 環 境 中 工 作, 符 合 全 球 管 制 條 例, 標 簽 讀 取 正 確 率 高, 讀 取 速 度 快, 安 全 性 和 隱 私 功 能 都 有 所 加 強 從 最 初 2005 年 1 月 26 日 公 佈 的 UHF Class 1 Gen 2 Standard v. 1.0.0, 直 到 最 近 2008 年 5 月 11 日 又 公 佈 了 最 新 版 本 UHF Class 1 Gen 2 Standard v. 1.2.0, 代 表 著 EPCglobal 的 Gen2 標 準 一 直 都 在 持 續 性 的 更 新 中 V. 1.2.0 擴 充 了 物 品 階 層 標 籤 的 能 力, 增 加 三 種 新 的 特 色 ; 當 使 用 者 記 憶 體 中 有 格 式 化 過 的 資 料, 現 在 可 以 透 過 指 示 器 的 方 式 顯 示 出 來 ; 附 加 一 個 阻 擋 階 層 在 使 用 者 記 憶 體 當 中, 用 以 保 護 被 寫 過 資 料 的 內 容 ; 經 過 POS(point of sale) 的 運 作 之 後, 現 在 能 夠 重 複 的 使 用, 此 重 複 使 用 的 動 作 決 定 在 一 個 擴 充 的 控 制 位 元 讀 取 器 可 ㄧ 次 讀 取 多 個 RFID, 但 細 看 其 通 訊 的 過 程 即 可 發 現, 讀 取 器 仍 然 是 以 一 次 讀 取 單 個 電 子 標 籤 的 方 式 進 行 方 法 大 致 是 由 讀 取 端 以 切 割 時 間 及 多 次 掃 描 (Multiple scans) 的 交 互 配 合 來 達 成 目 標 切 割 時 間 的 方 法 是 讓 電 子 標 籤 的 辨 識 資 料 (ID) 在 某 些 位 元 符 合 該 時 槽 所 指 定 的 位 元 時, 允 許 該 電 子 標 籤 可 進 行 資 料 通 信 ; 而 多 次 讀 取 的 目 的 在 於 讓 每 ㄧ 個 電 子 標 籤 都 有 機 會 被 允 許 通 訊 並 傳 送 資 料 讀 取 器 在 面 對 一 群 標 籤 時, 均 透 過 三 個 階 段 : select( 選 擇 )-->Inventory( 盤 點 )-->Access( 存 取 )( 如 圖 3[4]) 每 一 個 執 行 階 段 都 組 合 了 一 個 或 多 個 命 令 集, 這 些 階 段 的 定 義 如 下 : 圖 3: 讀 取 器 的 運 作 與 標 籤 的 狀 態 8
1.Select: 此 程 序 是 讓 詢 問 者 選 擇 一 特 定 數 量 標 籤 以 便 接 下 來 進 行 盤 點 及 存 取 尋 問 者 在 盤 點 之 前 可 能 會 使 用 一 個 或 多 個 Select 命 令 去 選 擇 特 定 目 標 的 標 籤 2.Inventory: 則 是 對 已 被 選 擇 的 標 籤 數 量 進 行 識 別 每 個 盤 點 回 合 由 詢 問 者 在 四 個 Session 中 的 一 個 發 出 Query 命 令 開 始, 然 後 由 一 或 多 個 標 籤 回 覆, 讀 取 器 偵 測 到 標 籤 回 覆 後, 再 要 求 標 籤 回 覆 資 料 內 容 ( 如 protocol control, EPC 號 碼, CRC-16 等 資 料 ), 每 個 盤 點 回 合 每 次 只 能 在 一 個 且 唯 一 的 session 中 進 行 本 論 文 所 進 行 的 研 究 便 是 處 在 此 階 段 的 當 中 Inventory 階 段 運 作 的 流 程, 從 讀 取 器 發 送 出 Query 命 令 之 後,Inventory 階 段 就 開 始 了, 讀 取 器 送 出 Query 命 令 的 之 後,Tag 會 進 行 傳 送 資 料 給 讀 取 器 的 排 程, 而 在 排 程 當 中, 可 能 會 產 生 三 種 情 況, 分 別 為 衝 突 (collision) 單 一 (single) 和 無 (empty) 下 圖 圖 4 所 示, 為 讀 取 器 和 tags 之 間 溝 通 交 流 的 通 訊 協 定 流 程, 讀 取 器 主 要 會 發 送 出 的 命 令 如 :Query Ack QueryRep 以 及 QueryAdjust 等, 流 程 的 順 序 依 圖 由 左 到 右, 讀 取 器 一 個 訊 號 發 送,tags 便 一 個 訊 號 傳 回, 只 有 當 讀 取 器 接 收 到 正 常 的 回 覆 訊 號 時, 才 會 進 行 下 一 步 的 命 令 ; 在 圖 中 也 呈 現 了 排 程 的 三 種 情 況 分 別 會 以 怎 樣 的 訊 號 傳 回, 如 圖 4[4] 裡 的 Single Tag Reply Cokkided Reply 和 No Reply 3.Access: 在 select 與 inventory 之 後, 讀 取 器 使 能 對 單 一 標 籤 進 行 存 取 ( 讀 取 或 寫 入 資 料 ) 在 access 之 前 每 個 單 獨 的 標 籤 必 須 被 獨 特 且 唯 一 的 被 辨 識 Access 程 序 是 由 多 樣 的 命 令 所 組 成 圖 4:Query 命 令 在 RFID 的 通 訊 協 定 9
在 前 面 圖 3 提 到 讀 取 器 所 進 行 的 三 個 步 驟 外, 標 籤 也 會 依 據 相 對 應 的 命 令 進 行 不 同 狀 態 的 切 換, 而 標 籤 的 狀 態 分 為 七 種 狀 態, 在 標 籤 的 各 個 狀 態 切 換 以 及 其 運 作 的 功 能, 都 在 下 圖 圖 5[4] 中 因 為 研 究 的 重 點 放 在 讀 取 器 的 Inventory, 所 以 在 此 不 詳 述 標 籤 的 狀 態 運 作 圖 5: 標 籤 的 狀 態 圖 在 Gen2 標 準 中, 除 了 上 述 的 通 訊 協 定 之 外, 對 標 籤 的 硬 體 規 格 也 有 一 致 的 統 一, 才 能 方 便 世 界 上 發 展 RFID 系 統 Gen2 標 籤 的 記 憶 體 主 要 由 四 個 儲 存 庫 (bank) 組 成, 如 下 ( 圖 6[4]): The Reserved memory (Bank 00), 包 含 了 兩 個 安 全 訊 息,32-bit KILL 和 ACCESS password The EPC memory (Bank 01), 包 含 code,pc(protocol control) 和 CRC-16 10
這 些 必 要 訊 息 The TID memory (Bank 10) 包 含 32-bit TID,TID 的 數 值 代 表 著 Tag 模 組 號 碼 或 是 販 售 者 的 訊 息 等 資 料 The User memory (Bank 11) 包 含 使 用 者 的 資 料, 此 資 料 也 可 以 為 使 用 者 本 身 自 己 的 設 定 圖 6: 標 籤 的 記 憶 體 配 置 2.2.2.1 分 段 式 ALOHA 當 讀 取 器 和 標 籤 之 間 在 傳 輸 資 料 的 時 候, 因 為 標 籤 數 量 龐 大 的 關 係, 一 定 會 產 生 許 多 的 標 籤 同 時 傳 送 資 料 給 讀 取 器 而 產 生 了 衝 突, 當 產 生 衝 突 的 時 候, 為 了 解 決 衝 突 發 生 的 情 況, 反 碰 撞 演 算 法 (anti-collision algorithm) 就 被 推 出 來 解 決 問 題,Gen2 標 準 當 然 也 要 一 致 統 一 演 算 法 的 執 行, 於 是 採 用 了 slotted ALOHA 演 算 法 ( 如 圖 7),ALOHA 演 算 法 是 利 用 排 程 的 方 式 使 所 有 的 標 籤 進 入 時 間 槽 (timeslots) 排 隊, 每 次 以 一 個 時 間 槽 為 計 算 單 位 進 行 讀 取, 時 間 槽 被 讀 取 器 讀 取 會 有 三 種 情 況 發 生, 分 別 是 : 衝 突 (collision) 單 一 (single) 和 無 (empty), 其 運 作 流 程 如 下 : 讀 取 器 週 期 性 地 送 出 訊 號 給 標 籤 標 籤 接 收 到 訊 號 之 後, 選 擇 某 一 個 時 段 的 時 間 槽 進 入, 等 待 讀 取 器 對 標 籤 做 讀 取 資 料 當 一 些 標 籤 處 在 同 一 格 時 間 槽 中 的 時 候, 則 讀 取 器 跳 過 產 生 碰 撞 的 時 間 槽, 先 採 用 單 一 存 在 時 間 槽 中 的 標 籤 讀 取 器 對 單 一 存 在 時 間 槽 的 標 籤 通 知 傳 送 資 料 標 籤 傳 送 資 料 給 讀 取 器 然 後 對 剩 下 的 標 籤 重 複 之 前 的 動 作, 直 到 所 有 標 籤 資 料 讀 取 完 畢 11
圖 7: 分 段 式 ALOHA 通 訊 協 定 因 為 衝 突 的 發 生 是 不 可 避 免 的, 所 以 在 RFID Gen 2 標 準 中, 加 入 了 另 一 個 演 算 法 幫 助 降 低 衝 突 的 發 生 讀 取 器 透 過 廣 播 發 送 出 Query 命 令 給 所 有 的 標 籤, 並 且 給 予 這 些 標 簽 一 個 變 數 Q, 如 果 標 籤 是 在 ready 狀 態 下 獲 得 了 命 令, 該 標 籤 將 會 等 待 一 個 隨 機 的 時 間 T,T 是 一 個 介 於 1-2 Q 的 ( 即 圖 7 中 看 到 的 時 間 槽 2 Q 為 最 大 值 ) 隨 機 數 字, 當 讀 取 器 偵 測 出 存 在 衝 突 的 時 候, 讀 取 器 會 增 加 Q 值 以 擴 大 時 間 槽 的 最 大 值 來 降 低 衝 突 發 生 率, 而 根 據 衝 突 的 發 生 紀 錄, 適 當 地 變 動 Q 值, 我 們 稱 此 增 加 Q 值 的 過 程 為 :Q 演 算 法 ( 如 圖 8[4]) 圖 8:Q 演 算 法 12
2.2.3 EPCglobal 安 全 防 護 在 Gen2 標 準 中, 除 了 對 硬 體 以 及 通 訊 協 定 的 標 準 制 定 外, 對 於 資 料 的 安 全 保 護, 有 提 供 兩 種 安 全 機 制 模 式 : 第 一 種 機 制 是 殺 掉 RFID Gen2 標 籤,Gen2 標 準 定 義 了 KILL password 和 KILL 命 令 去 執 行, 當 下 達 KILL 命 令 的 時 候, 標 籤 會 對 讀 取 器 所 送 出 的 KILL password 跟 標 籤 本 身 的 KILL password 作 確 認, 比 對 完 成 且 正 確 時, 標 籤 會 進 入 KILL 狀 態 ( 標 籤 擁 有 七 種 狀 態 ), 之 後 對 於 讀 取 器 所 下 達 的 任 何 指 令, 標 籤 永 遠 不 會 產 生 相 對 應 的 動 作 第 二 種 機 制 是 控 制 接 收 Gen2 的 記 憶 體,Gen2 標 準 定 義 了 ACCESS password 和 兩 個 指 令 去 執 行, 指 令 分 別 為 ACCESS 和 LOCK,ACCESS 指 令 可 以 命 令 標 籤 進 入 secured 狀 態, 當 在 secured 狀 態 的 時 候, 讀 取 器 需 要 讀 取 資 料 時, 只 能 先 透 過 ACCESS password 由 標 籤 確 認 之 後, 才 開 放 權 限 接 受 獨 取 記 憶 體, 通 常 是 搭 配 KILL 指 令 一 起 傳 達 至 標 籤, 標 籤 接 受 到 LOCK 指 令 便 可 以 轉 成 可 以 讀 寫 的 狀 態 2.2.3.1 KILL Tag KILL 命 令 是 被 設 計 來 取 消 掉 RFID 標 籤 接 受 命 令 的 能 力 當 RFID 標 籤 接 受 到 KILL 命 令 的 時 候, 標 籤 會 對 讀 取 器 所 送 出 的 KILL password 跟 RFID 標 籤 本 身 的 KILL password( 密 碼 儲 存 如 圖 9[4] 所 示 ) 作 確 認, 比 對 完 成 且 正 確 時,RFID 標 籤 會 進 入 KILL 狀 態 (Gen2 標 準 制 定 標 籤 有 七 種 狀 態 ), 之 後 對 於 讀 取 器 所 下 達 的 任 何 指 令, 標 籤 永 遠 不 會 產 生 相 對 應 的 動 作 且 不 再 接 受 或 傳 輸 資 料 在 KILL 命 令 安 全 防 護 機 制 下, 其 主 要 的 優 點 在 於 標 籤 的 資 料 可 以 被 有 效 的 防 護, 並 且 不 會 被 竊 聽 到 資 料 而 被 追 蹤 舉 個 例 子 來 說, 當 一 個 消 費 者 購 買 商 品 之 後, 其 商 品 的 標 籤 經 過 KILL 處 理, 原 本 屬 於 商 品 資 料 的 內 容, 就 不 會 再 被 傳 輸 出 去, 不 用 擔 心 自 己 購 買 的 商 品 會 被 其 他 人 所 知 道, 有 效 的 保 護 消 費 者 隱 私 安 全 但 是 缺 點 也 是 相 當 的 明 顯, 經 過 KILL 處 理 過 的 標 籤, 都 不 可 以 被 再 利 用 的 功 能, 不 能 回 收 性 地 成 為 一 次 性 拋 棄 物 品 13
圖 9: 標 籤 中 密 碼 的 記 憶 體 配 置 2.2.3.2 ACCESS Password 在 Gen2 標 準 中 制 定 的 記 憶 體 配 置, 其 中 有 32 位 元 的 空 間 被 提 供 來 存 放 Password, 稱 為 Reserved memory( 如 上 圖 圖 9), 並 且 定 義 了 ACCESS password 和 兩 個 指 令 去 執 行, 指 令 分 別 為 ACCESS 和 LOCK,ACCESS 指 令 可 以 命 令 標 籤 進 入 secured 狀 態 ; 當 在 secured 狀 態 的 時 候,Reader 需 要 讀 取 資 料 時, 只 能 先 透 過 ACCESS password 由 標 籤 確 認 之 後, 才 開 放 權 限 接 受 獨 取 記 憶 體 所 以 當 讀 取 器 需 要 讀 取 或 是 更 改 標 籤 資 料 的 時 候, 讀 取 器 送 出 的 Password 與 標 籤 儲 存 的 Password 必 須 經 過 標 籤 做 過 XOR 的 比 對 確 認, 確 認 過 後 判 斷 密 碼 為 正 確 者, 標 籤 才 允 許 讀 取 器 去 讀 取 或 是 修 改 資 料 優 點 在 於 不 知 道 密 碼 的 外 來 者, 將 無 法 讀 取 到 標 籤 的 資 料, 能 夠 有 效 的 防 護 ; 最 大 的 缺 點 在 密 碼 的 變 化 不 夠 龐 大, 其 內 容 只 有 32 位 元 的 組 合, 被 破 解 密 碼 的 可 能 性 不 低 在 上 述 的 Gen2 標 準 裡 的 安 全 防 護 機 制, 並 沒 有 任 何 防 護 有 關 訊 號 干 擾 的 問 題, 假 如 有 攻 擊 者 針 對 Inventory 階 段 進 行 讀 取 器 與 標 籤 之 間 的 無 線 訊 號 干 擾, Gen2 標 準 的 防 護 機 制 無 法 有 效 的 保 護 與 偵 測 攻 擊 方 的 威 脅, 此 處 在 標 準 的 安 全 當 中 算 是 一 種 安 全 漏 洞, 所 以 針 對 此 處 的 漏 洞, 本 論 文 研 究 提 出 了 一 種 改 善 此 弱 點 的 防 護 機 制 14
Chapter 3 相 關 研 究 本 章 將 介 紹 與 本 論 文 相 關 的 一 些 研 究, 並 於 第 四 章 中 針 對 這 些 研 究 加 以 改 善 且 引 用 其 方 法 3.1 介 紹 RSA Blocker tag 的 想 法 以 及 應 用, 透 過 Blocker tag 的 作 法 改 善 遭 到 惡 意 讀 取 隱 私 攻 擊 的 防 護 ; 由 最 初 的 Blocker tag 到 後 來 更 有 彈 性 的 soft blocker tag, 以 及 如 何 偵 測 惡 意 使 用 Blocker tag 的 anti blocker tag 研 究 3.1 RSA Blocker tag 阻 絕 式 攻 擊 (DDos) 是 一 種 在 通 訊 協 定 中 傳 統 的 攻 擊 方 法, 這 種 方 法 利 用 在 RFID 的 Air protocol 時, 被 稱 做 為 Blocker tag 這 種 方 法 的 利 用 是 由 RSA 率 先 提 倡, 藉 由 攻 擊 讀 取 器 讀 取 標 籤 的 通 訊 協 定,Blocker tag 可 以 阻 止 標 籤 被 讀 取 ; 衝 突 (collision) 的 發 生, 是 blocker tag 的 重 心, 在 RFID Class 1 Gen 1 是 利 用 同 時 傳 送 `0' 和 `1', 達 到 無 法 正 確 判 斷 標 籤 的 識 別 號 碼, 而 RFID Class 1 Gen 2 是 利 用 在 時 間 槽 中 發 生 排 隊 碰 撞 的 情 況, 做 到 無 法 單 一 傳 送 訊 號 Blocker Tag 的 防 護 示 意 圖 如 下 圖 10 接 下 來 的 小 節 中, 將 會 詳 細 的 介 紹 Blocker tag 的 理 論 圖 10:Blocker Tag 示 意 圖 3.1.1 The Blocker Tag: Selective Blocking of RFID Tags for Consumer Privacy [6] 在 此 篇 論 文 中 提 到,Blocker Tag 展 示 如 何 在 盤 存 階 段 (Inventory) 中 去 防 止 RFID 讀 取 器 去 讀 取 資 料, 舉 例 來 說,RFID Class 1 Gen 1 使 用 樹 狀 演 算 法, 利 用 產 品 的 ID 號 碼 在 樹 的 樹 枝 端 點 位 置 ( 如 圖 11); 藉 由 詢 問 所 有 tags 的 ID 前 序 15
號 碼, 如 果 發 送 出 詢 問 前 序 P 且 P 的 長 度 是 d, 則 tag 將 會 送 回 d+1 個 位 元 的 產 品 ID 給 讀 取 器 透 過 重 複 以 上 的 動 作, 讀 取 器 最 後 可 以 獲 得 所 有 現 存 在 的 tag ID, 但 是 當 一 個 tag 有 兩 個 天 線 且 總 是 送 出 位 元 0 和 1 給 讀 取 器 的 時 候, 讀 取 器 將 會 做 一 次 完 整 樹 的 遊 走, 因 為 讀 取 器 將 會 浪 費 時 間 且 導 致 盤 存 列 表 無 效 用 圖 11: 樹 狀 演 算 法 Blocker tag 的 基 本 運 作 是 很 簡 單 的 ( 如 下 圖 圖 12), 它 冒 充 所 有 的 RFID-tag 一 系 列 號 碼, 我 們 可 以 稱 這 種 tag 是 完 全 阻 擋 者 (full blocker) 或 是 全 體 的 阻 擋 (universal blocker) 在 樹 走 向 演 算 法 (tree-walking algorithm) 的 結 構 中, 阻 擋 是 很 簡 單 能 夠 達 到 地 每 當 讀 取 器 詢 問 tag 在 子 樹 結 點 B 去 尋 求 下 一 個 位 元 值,blocker tag 則 冒 充 地 廣 播 - 和 1 的 位 元 值 (Blocker tag 可 能 需 要 雙 天 線 去 做 這 件 事 情 ) 這 種 強 迫 衝 突 發 生, 迫 使 讀 取 器 去 深 入 所 有 節 點, 使 得 讀 取 器 去 探 勘 完 全 的 樹 如 果 讀 取 器 有 足 夠 的 時 間 記 憶 體 和 運 作 能 量 去 執 行 完 整 的 tree-walking 演 算 法 在 這 種 環 境 下, 讀 取 器 可 能 會 輸 出 所 有 的 編 號 集 合 種 類 網 狀 覆 蓋 是 完 全 的 blocker tag 阻 擋 所 有 在 讀 取 的 標 籤, 這 個 點 子 在 當 一 個 設 備 在 攻 擊 對 抗 盤 存 階 段 的 控 制 系 統, 並 且 控 制 系 統 相 信 已 經 被 偷 的 物 品 仍 舊 展 示 在 零 售 環 境 中 ; 而 且, 一 個 blocker tag 製 造 簡 單 且 造 價 不 貴, 能 夠 被 有 效 的 製 造 且 廣 大 應 用 在 社 會 上 但 是, 如 果 blocker tag 被 人 惡 意 使 用 在 偷 竊 物 品 上, 反 而 會 造 成 一 些 商 業 上 或 管 理 上 的 威 脅 16
圖 12:Blocker Tag 機 制 在 樹 狀 演 算 法 3.1.2 Soft blocking: flexible blocker tags on the cheap 此 論 文 [7] 牽 涉 到 軟 體 的 元 件, 該 部 份 提 供 了 一 個 不 同 於 平 常 的 Blocker tag 軟 性 阻 擋 提 供 一 種 弱 一 點 的 阻 擋 隱 私 方 式, 該 執 行 是 來 自 Blocker tag 本 身 這 是 個 有 意 義 的 優 點, 且 依 靠 RFID tags 標 準 此 外, 軟 性 阻 擋 也 提 供 彈 性 地 隱 私 機 制, 並 且 可 能 的 在 部 份 被 列 為 有 關 私 人 的 資 料 tags, 讓 blocker tag 做 到 警 戒 這 裡 將 介 紹 軟 性 阻 擋 的 想 法, 一 個 便 宜 且 在 原 本 的 Blocker tag 機 制 下 提 供 選 擇 Soft Blocker tag 不 能 夠 提 供 相 同 強 力 的 隱 私 保 證 在 全 阻 擋 式 的 Blocker tag 軟 性 Blocker tag 也 是 在 幾 乎 相 同 的 RFID tags 硬 體 和 函 式, 也 支 援 一 個 寬 廣 範 圍 給 隱 私 方 針 論 文 中 提 到, 我 們 可 以 將 tag 分 為 三 種 不 同 的 類 別, 分 別 為 blocker private 和 public 如 果 有 一 個 Blocker tag 在 蒐 集 的 資 料 當 中, 它 會 傳 回 像 是 public tag 的 訊 號, 以 及 private 的 訊 號 在 public 的 樹 節 點 中, 最 後 可 以 看 到 該 tag 的 ID 編 號, 但 是 在 private 的 樹 節 點, 卻 無 法 有 效 的 進 入 到 節 點 位 置 ; 因 為 軟 性 Blocker tag 現 在 是 針 對 該 特 定 領 域 內 的 ID 編 號 做 阻 擋 ( 如 圖 13), 當 被 阻 擋 起 來 的 tag 資 料 便 是 被 稱 做 為 private tag, 不 提 供 給 外 在 的 人 讀 取 資 料, 而 其 他 的 public 資 料 便 交 由 一 般 的 讀 取 器 正 常 讀 取 一 個 軟 性 Blocker tag 可 以 只 阻 擋 目 標 ID 的 樹 子 集, 而 不 是 所 有 的 樹 這 是 一 個 簡 單 的 方 法 去 保 護 我 們 的 隱 私, 而 且 不 需 要 額 外 增 加 硬 體 設 施, 但 是, 如 果 人 們 使 用 Blocker tag 在 惡 意 的 應 用, 他 們 能 夠 躲 過 商 店 行 竊 的 偵 測 系 統 在 這 17
種 情 況 下, 有 人 可 以 從 商 店 偷 東 西 不 經 過 掃 瞄 確 認, 這 是 一 個 非 常 嚴 重 的 問 題 在 RFID 結 帳 系 統 上 在 上 述 的 情 境 當 中, 當 我 們 想 要 對 tag 進 行 分 類 的 時 候, 會 分 做 重 要 物 品 以 及 非 貴 重 物 品, 此 時 候 我 們 便 可 以 透 過 軟 性 Blocker tag 的 方 式, 好 好 的 分 配 好 運 作 系 統, 如 此 一 來, 彈 性 的 阻 擋 特 定 tag 資 料, 大 大 提 高 軟 性 Blocker tag 的 價 值 舉 例 來 說, 一 般 人 在 使 用 悠 遊 卡 的 時 候, 應 該 是 要 能 夠 順 利 的 讓 讀 取 器 讀 取, 且 幽 遊 卡 可 以 放 在 身 上 的 任 何 地 方, 但 是 自 己 個 人 的 身 份 資 料 如 果 設 定 在 RFID 的 tag 當 中 的 時 候, 通 常 人 們 會 將 身 分 資 料 卡 和 悠 遊 卡 放 在 皮 包 當 中, 如 果 不 想 影 響 到 悠 遊 卡 的 存 取 且 不 想 讓 人 偷 看 到 身 分 卡 的 資 料, 這 時 候 軟 性 Blocker tag 就 可 以 被 拿 來 有 效 的 利 用 圖 13: 軟 性 Blocker Tag 機 制 在 樹 狀 演 算 法 3.1.3 RFID privacy protect using blocker tag with anti-blocker tag scheme 前 兩 篇 所 提 到 的 論 文, 是 Blocker Tag 發 展 的 演 進, 是 以 較 早 的 Gen 1 作 為 基 礎 開 發 的, 現 在 有 新 開 發 的 RFID 標 準 為 :RFID Class 1 Gen 2 不 同 的 標 準 有 著 不 同 的 通 訊 協 定,Gen 1 使 用 了 樹 演 算 法,Gen 2 使 用 了 分 段 式 ALOHA 演 算 法, 在 此 論 文 提 出 了 如 何 在 Gen 2 標 準 下 做 到 Blocker Tag 的 方 法 以 及 對 Blocker Tag 提 出 偵 測 防 護 的 探 討 18
1. Anti-blocker tag in RFID Class 1 Gen 1: 根 據 產 品 ID 的 原 則,Blocker tag 會 偽 裝 產 品 ID Blocker tag 利 用 同 時 回 應 '0' 和 '1' 的 動 作, 不 過 不 能 應 用 在 上 述 論 文 提 到 的 軟 性 Blocker tag, 因 為 我 們 不 能 知 道 哪 一 部 分 的 產 品 被 遮 蓋 在 此 種 情 況 下, 我 們 可 以 獲 得 警 戒 的 優 點 和 我 們 可 以 知 道 哪 些 ID 將 永 遠 不 會 回 應 我 們 的 詢 問 ; 如 果 我 們 發 出 詢 問 且 一 些 tag 宣 稱 該 警 戒 ID 是 存 在 的, 代 表 必 有 Blocker tag 存 在 ( 如 圖 14[1]) 我 們 稱 之 為 警 戒 系 統 圖 14: 間 諜 標 籤 機 制 在 軟 性 Blocker tag 系 統 中, 一 個 警 戒 tag 將 不 會 總 是 有 用 的, 我 們 可 以 透 過 先 行 定 義 所 有 的 數 量 大 小, 假 如 所 有 的 盤 存 數 量 超 過 最 大 門 檻 我 們 可 以 宣 稱 該 處 存 在 Blocker tag 2. Anti-blocker tag in RFID Class 1 Gen 2: 在 RFID Class 1 Gen 2 的 標 準 下, 是 利 用 分 段 式 ALOHA 的 演 算 法 作 為 基 礎 的 通 訊 協 定 利 用 時 間 槽 的 方 式 產 生 一 連 串 的 排 程, 再 由 時 間 槽 內 所 發 生 的 狀 態 做 是 否 順 利 進 入 盤 點 的 動 作 Blocker tag 在 Gen 2 的 環 境 下 建 立 的 方 法 如 圖 15[1], 雖 然 產 品 ID 進 入 時 間 槽 是 透 過 隨 機 取 樣 的 方 法 選 擇 的, 但 是 Blocker tag 將 所 有 的 時 間 槽 中 都 存 在 一 個 它 的 ID, 便 會 導 致 所 有 的 時 間 槽 發 生 衝 突 的 狀 況, 讀 取 器 即 無 法 盤 點 任 何 一 樣 產 品 ID, 這 就 是 在 Gen 2 的 標 準 下 做 到 Blocker tag 的 演 算 法 圖 15:Blocker tag 造 成 的 碰 撞 19
警 戒 系 統 的 方 法 不 能 夠 應 用 在 RFID Class 1 Gen 2 上, 因 為 反 碰 撞 演 算 法 在 Gen 2 的 時 候, 不 能 使 用 產 品 ID 區 別 所 有 的 產 品 我 們 可 以 偵 測 出 存 在 的 blocker tag, 藉 由 機 率 的 結 構 如 果 產 品 貨 物 中 存 在 Blocker tag, 會 有 很 高 的 衝 突 比 例 發 生, 而 我 們 偵 測 的 方 法 中 主 要 是 想 透 過 不 正 常 的 高 衝 突 比 例, 發 現 狀 況 一 旦 Blocker tag 存 在, 它 將 會 無 效 的 增 加 Q 值, 當 詢 問 在 Q 值 中 選 擇 一 個 門 檻, 且 衝 突 比 例 可 以 發 現 不 正 常 的 情 況 此 方 法 將 總 會 執 行 在 任 何 時 間 存 在 一 個 問 題 就 是 我 們 所 要 選 擇 的 門 檻 以 及 如 何 加 速 去 發 現 Blocker tag 的 存 在 換 句 話 說, 我 們 依 然 能 夠 支 持 警 戒 系 統, 只 是 該 警 戒 系 統 需 要 做 一 點 修 改 RFID Class 1 Gen 2 使 用 分 段 式 ALOHA 演 算 法 去 盤 存, 儘 管 該 演 算 法 不 能 使 用 產 品 的 ID 去 瀏 覽 所 有 的 tag, 我 們 可 以 藉 由 選 擇 命 令 中 明 確 指 定 一 個 特 定 的 產 品 ID 舉 例 來 說, 我 們 可 以 使 用 選 擇 命 令 去 選 擇 某 一 個 產 品 ID, 然 後 我 們 使 用 詢 問 用 我 們 所 選 擇 的 產 品, 然 後 我 們 將 獲 得 預 期 中 的 回 應, 如 果 我 們 確 定 該 回 應 是 一 個 沉 默 的 tag 且 我 們 獲 得 了 一 個 回 音, 則 可 以 判 斷 該 處 必 有 Blocker tag 存 在 在 進 行 實 驗 之 後, 我 們 知 道 衝 突 比 例 不 能 夠 被 使 用 作 為 門 檻 ( 如 圖 16[1]) 因 為 衝 突 率 不 只 會 受 到 Blocker rate 影 響, 還 會 受 到 tag 數 量 影 響 一 旦 tag 的 數 量 增 加, 衝 突 比 例 也 會 隨 之 上 升 此 外, 我 們 事 先 知 道 tag 的 數 量, 衝 突 比 例 不 能 代 表 Blocker tag 的 存 在 圖 16: 時 間 影 響 的 衝 突 率 定 義 了 一 個 比 例 處 在 ACK 的 數 量 和 被 盤 點 的 tag 當 作 A/Q 比 例 在 "Query Adjust" 的 方 案 下,Q 演 算 法 調 節 A/Q 的 比 例 從 0.3 到 0.5 最 大 的 A/Q 比 例 是 1 且 表 示 此 情 況 下 並 沒 有 衝 突 的 發 生 ; 如 果 Blocker tag 收 到 正 確 的 RN16 的 話, 一 個 聰 明 的 Blocker tag 一 定 會 回 應 ACK 給 讀 取 器, 因 為 blocker tag 送 出 "ACK" 太 多 的 話, 會 增 加 A/Q 的 比 例 如 果 Blocker tag 存 在, 則 A/Q 比 例 將 會 超 過 某 個 比 例, 根 據 此 論 文 的 實 驗 結 果 ( 如 圖 17[1]), 將 此 比 例 訂 定 為 0.4 20
圖 17:ACK 和 Query 的 數 量 比 例 一 個 Blocker tag 的 blocking rate 代 表 著 有 多 高 比 例 的 時 間 槽 被 Blocker tag 佔 據 偵 測 和 傷 害 是 成 正 比 的 : 如 果 blocking rate 較 低, 則 很 難 去 偵 測 出 來 ; 若 是 blocking rate 比 較 高, 雖 然 會 受 到 比 較 大 的 傷 害, 但 是 較 容 易 偵 測 出 Blocker tag 傷 害 的 意 義 以 有 多 大 的 時 間 我 們 需 要 去 將 盤 點,100% 的 blocking rate 將 會 停 止 所 有 的 盤 點 狀 態 但 是 如 果 blocking rate 少 於 100% 的 話, 在 盤 點 狀 態 的 時 候 一 定 會 在 一 個 有 限 時 間 內, 較 大 的 blocking rate 會 需 要 更 多 的 時 間, 我 們 的 工 作 室 製 造 一 個 正 過 的 門 檻, 並 且 此 門 檻 擁 有 合 理 的 時 間 和 偵 測 率 21
Chapter 4 系 統 架 構 本 論 文 提 供 一 個 新 的 偵 測 Blocker Tag 的 演 算 法 本 章 節 將 依 序 說 明 偵 測 機 制 的 流 程, 首 先 在 4.1 系 統 概 觀 與 假 設 中, 我 們 先 介 紹 整 個 系 統 架 構 的 流 程, 包 括 如 何 將 標 準 中 原 有 的 命 令 加 強 功 能 的 假 設, 到 將 下 達 命 令 執 行 動 作 的 內 容 等 等 接 著 4.2 節 介 紹 系 統 設 計, 把 執 行 步 驟 的 三 個 部 份 細 分 為 各 小 節 4.2.1 初 始 階 段, 展 示 標 籤 在 進 行 盤 點 之 前 的 初 始 化 動 作 4.2.2 交 流 階 段, 讀 取 器 與 標 籤 之 間 的 訊 號 交 流, 盤 點 各 個 標 籤 的 識 別 順 序, 偵 測 Blocker Tag 的 行 為 也 在 此 階 段 當 中, 詳 細 介 紹 本 論 文 偵 測 Blocker Tag 的 演 算 法 4.2.3 存 取 階 段, 盤 點 工 作 完 成 之 後, 就 是 單 純 的 讀 取 器 存 取 標 籤 中 存 的 資 料 4.1 系 統 概 觀 與 假 設 在 系 統 的 環 境 架 構 上, 是 基 於 EPCglobal Gen 2 標 準 上, 讀 取 器 經 由 三 個 階 段 去 存 取 標 籤 (tags) 的 資 料, 其 流 程 和 一 般 的 情 況 沒 有 任 何 的 不 同, 差 別 只 在 於 發 送 出 的 命 令 當 中, 我 們 加 入 了 一 些 額 外 的 資 訊 在 讀 取 器 的 命 令 當 中 透 過 利 用 控 制 位 元 的 方 式, 我 們 可 以 操 控 標 籤 在 時 間 槽 中 所 處 在 的 位 置 觀 察 並 統 計 每 格 時 間 槽 中 的 訊 號 資 料, 利 用 新 增 加 的 命 令 位 元 使 標 籤 的 時 間 槽 位 置 重 現, 然 後 比 較 該 回 合 和 上 回 合 的 時 間 槽 資 訊 是 否 相 同, 如 果 資 料 比 對 後 有 誤 差 產 生, 則 表 示 有 Blocker Tag 處 在 該 讀 取 範 圍 內 在 此 種 偵 測 方 法 下 能 夠 安 全 且 有 效 的 偵 測 出 Blocker Tag 的 存 在, 不 需 要 以 機 率 性 的 方 式 判 斷 是 否 存 在, 因 為 機 率 的 方 法 會 產 生 錯 誤 判 斷 的 問 題, 並 且 機 率 式 錯 誤 判 斷 只 能 以 降 低 發 生 機 率 的 方 式 減 少 錯 誤, 無 法 有 效 的 確 實 偵 測 ; 而 在 此 提 出 的 偵 測 方 式, 是 以 非 機 率 性 的 判 斷 方 法 偵 測, 能 夠 確 切 的 判 斷 有 惡 意 攻 擊 的 存 在, 已 達 到 安 全 有 效 的 偵 測 機 制 假 設 : 因 為 我 們 必 須 加 入 一 些 額 外 的 資 訊 於 EPCglobal Gen2 標 準 的 命 令 訊 框 中, 例 如 :slot counter 的 配 置 RNG 的 運 作 等 等, 並 且 不 影 響 到 原 有 的 運 作, 也 就 是 設 計 的 機 制 與 Gen 2 相 容 所 以 本 研 究 必 須 利 用 命 令 訊 框 新 增 欄 位 定 義 出 新 的 意 義 1. 所 有 的 標 籤 可 以 儲 存 slot counter 在 RESERVED 記 憶 體 當 中, 並 且 在 每 次 收 到 Query 或 是 QueryAdjust 命 令 的 時 候 執 行 在 前 面 圖 6 可 以 看 到 EPC 記 憶 體 原 有 的 配 置 空 間, 因 為 slot counter 是 一 個 16 位 元 的 數, 所 以 能 直 接 存 放 到 EPC 記 憶 體 的 一 個 欄 位 中 22
2. 我 們 會 額 外 增 加 Query 以 及 QueryAdjust 的 命 令 訊 框, 而 一 般 的 Gen 2 Query 和 QueryAdjust 命 令 訊 框 格 式 如 圖 18 所 示, 依 據 命 令 訊 框 裡 面 的 控 制 位 元,Tag 可 以 做 不 同 的 起 始 設 定 和 執 行 對 應 運 作 功 能, 其 中 Query command 的 位 元 長 度 為 22bits 而 QueryAdjust 的 位 元 長 度 是 9bits, 本 論 文 需 要 在 原 有 的 命 令 訊 框 當 中, 額 外 增 加 一 格 欄 位, 該 欄 位 主 要 是 控 制 tag 的 slot counter 是 否 需 要 從 RNG(Random Number Generator) 中 產 生, 或 者 是 利 用 標 籤 儲 存 在 記 憶 體 當 中 的 記 憶 體 送 出 圖 18:Query 命 令 訊 框 資 料 來 源 :[4] 圖 19:QueryAdjust 命 令 訊 框 資 料 來 源 :[4] 看 過 一 般 格 式 的 Query 命 令 訊 框 之 後, 本 偵 測 演 算 法 將 會 在 Q 的 旁 邊 加 上 一 個 新 的 參 數 值, 稱 之 為 SLN SLN 參 數 值 只 佔 有 一 位 元 的 長 度, 分 別 為 0 和 1 如 圖 20 和 圖 21 所 示 當 SLN 設 為 '0' 的 時 候,Tag 收 到 讀 取 器 送 出 的 Query 命 令, 除 了 依 照 原 本 的 Gen 2 標 準 Inventory 流 程 運 作 外, 標 籤 需 要 將 RNG 所 產 生 出 來 的 變 數 放 到 slot counter 當 中, 同 時 也 將 變 數 儲 存 到 記 憶 體 裡, 等 待 以 後 的 利 用 ; 當 SLN 設 為 '1' 的 時 候,Tag 收 到 Query 命 令 後, 不 會 採 用 RNG 所 產 生 出 來 的 變 數 存 到 slot counter 當 中, 而 是 從 記 憶 體 裡 取 出 上 一 回 合 Query 中 RNG 產 生 且 儲 存 的 變 數 相 同 地,QueryAdjust 的 命 令 框 架 上, 在 UpDn 的 欄 位 後 端 額 外 增 加 SLN 參 數 欄 位, 其 參 數 值 的 功 能 和 Query 命 令 一 致 23
圖 20: 新 Query 命 令 訊 框 圖 21: 新 QueryAdjust 命 令 訊 框 在 Gen 2 標 準 中 原 有 的 命 令 額 外 增 加 其 框 架 的 位 元 數, 並 不 會 對 Gen 2 標 準 的 運 作 以 及 硬 體 規 格 造 成 任 何 影 響 下 圖 圖 22 中, 展 示 了 Gen 2 標 準 命 令 的 命 令 碼 和 框 架 長 度, 從 圖 中 可 以 看 出 命 令 框 架 最 長 的 長 度 達 到 59 個 位 元, 最 少 也 有 4 個 位 元, 而 Query 以 及 QueryAdjust 的 長 度 分 別 為 22 個 位 元 和 9 個 位 元 ; 依 照 上 述 所 提 出 的 額 外 增 加 命 令 框 架 的 SLN 參 數 位 元, 將 其 Query 和 QueryAdjust 各 增 加 一 位 元 數, 由 原 本 22 位 元 和 9 位 元 數 擴 大 到 23 位 元 和 10 位 元, 其 位 元 數 沒 有 超 過 Gen 2 標 準 裡 已 規 劃 命 令 框 架 長 度 的 最 大 值, 代 表 著 本 論 文 提 出 新 增 加 參 數 位 元 數 的 方 法, 是 被 包 容 在 Gen 2 標 準 中 並 且 可 以 在 Gen 2 標 準 環 境 下 執 行 運 作 圖 22:Gen 2 命 令 的 長 度 資 料 來 源 :[4] 24
4.2 系 統 設 計 在 系 統 架 構 設 計 上, 遵 照 Gen2 標 準 讀 取 器 讀 取 標 籤 所 執 行 的 步 驟, 也 就 是 Select Inventory 和 Access 三 階 段, 其 中, 在 Inventory 的 階 段 中, 使 用 本 論 文 所 提 出 的 演 算 法 偵 測 Blocker tag, 當 無 偵 測 到 任 何 異 常 發 生 且 確 保 並 無 存 在 Blocker Tag 之 後, 再 繼 續 進 行 正 常 的 Q 演 算 法 盤 存 讀 取 範 圍 內 的 標 籤, 最 後 盤 存 結 束, 讀 取 器 便 可 以 正 常 的 在 Access 階 段 存 取 tag 的 資 料 接 下 來 各 小 節 將 詳 盡 的 介 紹 偵 測 演 算 法 的 各 個 步 驟 與 流 程 4.2.1 Select 階 段 依 據 EPCglobal Class 1 Gen 2 標 準, 當 讀 取 器 要 存 取 標 籤 (tags) 資 料 的 時 候, 會 依 照 三 個 階 段 運 作 ( 其 三 階 段 如 圖 3 所 示 ) 首 先, 會 進 入 Select 階 段, 在 此 階 段 當 中 讀 取 器 會 將 標 籤 分 為 四 個 sessions 以 及 設 定 selected flag 變 數 值, 利 用 session 和 flag 變 數 分 配 標 籤 給 各 個 讀 取 器, 以 及 判 別 該 標 籤 是 否 已 經 進 入 存 取 排 程 被 存 取 過 Select 階 段 運 作 結 束 之 後, 便 把 所 有 處 在 讀 取 範 圍 內 的 標 籤 分 配 給 該 存 取 的 讀 取 器, 設 定 好 標 籤 被 讀 取 器 開 始 存 取 的 初 始 化 設 定, 標 籤 設 定 完 成 才 能 夠 進 入 下 一 個 階 段 :Inventory 本 篇 論 文 所 提 出 的 演 算 法 沒 有 更 改 到 Select 階 段 原 有 的 運 作, 在 Inventory 階 段 才 開 始 進 入 本 論 文 演 算 法 的 執 行 4.2.2 Inventory 階 段 我 們 在 進 入 Inventory 階 段 的 時 候, 就 可 以 執 行 Blocker Tag 偵 測 演 算 法 的 運 作, 偵 測 的 運 作 重 心 主 要 在 讀 取 器 發 送 的 命 令, 因 為 在 此 提 出 的 Blocker Tag 偵 測 演 算 法 與 SLN 的 參 數 有 關, 所 以 之 後 都 稱 之 為 SLN 演 算 法 (SLN-algorithm) 在 Gen 2 標 準 的 運 作 流 程 下, 讀 取 器 會 先 將 Select 階 段 選 好 的 標 籤 發 送 Query 命 令, 此 時 我 們 稱 作 一 個 回 合 的 開 始, 標 籤 收 到 訊 號 之 後 會 自 行 從 RNG(Random Number Generator) 產 生 隨 機 數 字, 產 生 的 數 字 大 小 處 在 Query 命 令 中 Q 欄 位 參 數 以 二 為 底 的 指 數 次 方 範 圍 內, 標 籤 利 用 這 數 字 以 倒 數 的 方 式 依 序 排 隊 準 備 跟 讀 取 器 交 流 訊 號, 直 到 在 當 下 Query 回 合 中 的 時 間 槽 都 讀 取 過 後, 該 回 合 便 到 此 結 束 在 每 一 個 回 合 當 中, 讀 取 器 會 判 斷 時 間 槽 有 三 種 狀 態 (2.2.2 小 節 中 介 紹 到 ): 衝 突 (collision) 單 一 (single) 和 無 (empty), 針 對 時 間 槽 中 的 狀 態 統 計, 同 時 執 行 Q 演 算 法, 而 Q 演 算 法 的 結 束 都 表 示 該 回 合 的 結 束 ; 本 篇 論 文 的 偵 測 演 25
算 法, 是 以 Q 演 算 法 做 基 礎,Q 演 算 法 的 結 束 表 示 該 回 合 的 結 束, 之 後 準 備 進 入 下 一 回 合 的 Q 演 算 法, 我 們 便 在 Q 演 算 法 的 輸 入 與 輸 出 額 外 進 行 其 它 運 作 與 偵 測 判 斷 圖 23:SLN 演 算 法 的 流 程 圖 26
SLN 演 算 法 的 流 程 圖 如 上 圖 圖 23 SLN 演 算 法 可 以 分 為 兩 個 部 份, 分 別 在 Q 演 算 法 之 前 與 之 後 第 一 部 份 : Inventory 階 段 開 始 的 時 候, 讀 取 器 會 發 送 出 Query 命 令 訊 號, 代 表 開 啟 了 一 個 盤 點 回 合 (Inventory round), 在 第 一 次 發 送 完 Query 命 令 之 後, 之 後 每 回 合 開 始 都 會 發 送 QueryAdjust 的 命 令,Query 和 QueryAdjust 的 命 令 訊 框 中 有 Q 以 及 SLN 的 參 數, 因 為 只 有 此 兩 者 命 令 會 修 改 到 Q 的 參 數 值, 所 以 在 此 特 地 對 Query 和 QueryAdjust 命 令 進 行 關 注 動 作 標 籤 (tags) 收 到 了 Query 或 是 QueryAdjust 命 令 之 後, 會 根 據 其 命 令 訊 框 的 參 數 值 執 行 相 對 應 的 動 作, 其 中, 兩 者 命 令 當 中 SLN 變 數 則 是 SLN 演 算 法 的 運 作 重 心 所 在 SLN 的 參 數 值 只 有 兩 種, 分 別 是 0 和 1 透 過 一 個 位 元 表 示 之, 依 據 SLN 參 數 值 的 不 同,0 和 1 會 使 得 tag 執 行 的 兩 種 不 同 的 動 作 ( 如 圖 24): 當 SLN = 0 的 時 候,tag 的 slot counter 則 由 RNG(Random Number Generotor) 產 生 後 給 予, 另 一 方 面, 若 SLN = 1 的 時 候,slot counter 則 由 記 憶 體 (RESERVED Bank) 中 匯 出 數 值 給 予 Slot counter 的 起 始 數 值 資 料, 只 能 從 這 兩 種 來 源 地 方 取 得, 並 不 會 有 其 他 的 方 法 可 以 修 改 或 刪 除 slot counter 的 起 始 數 值, 而 SLN 的 預 設 參 數 是 0, 表 示 slot counter 數 值 的 預 設 來 源 是 從 RNG 取 得 圖 24:SLN 變 數 控 制 的 運 作 27
當 slot counter 有 了 起 始 數 值 之 後, 標 籤 則 將 當 下 clot counter 數 值 的 資 料 存 放 在 記 憶 體 當 中, 以 備 未 來 作 為 判 斷 是 否 有 Blocker Tag 存 在 的 工 具, 透 過 儲 存 起 來 的 數 值 資 料, 可 以 比 對 相 鄰 近 盤 點 回 合 的 識 別 情 況 是 否 相 同, 因 為 利 用 存 起 來 的 slot counter 數 值, 將 兩 個 盤 點 回 合 的 slot counter 設 置 相 同, 根 據 分 段 式 ALOHA 演 算 法 的 運 作, 兩 個 盤 點 回 合 的 盤 點 結 果 會 是 一 致 的 在 標 籤 儲 存 好 資 料 之 後, 即 可 進 入 Gen 2 標 準 的 反 碰 撞 演 算 法 :Q 演 算 法, 進 行 讀 取 器 識 別 時 間 槽 中 標 籤 的 編 碼 的 動 作 了 第 二 部 份 : Q 演 算 法 結 束 之 後, 讀 取 器 需 要 先 進 行 一 個 判 斷 動 作, 便 是 先 判 斷 該 盤 點 回 合 的 SLN 值 是 否 為 1, 如 果 是 的 話, 表 示 該 盤 點 回 合 是 有 要 進 行 偵 測 Blocker Tag 的 動 作 ; 若 SLN 沒 有 為 1 的 話, 代 表 該 次 盤 點 回 合, 乃 是 一 次 正 常 執 行 Gen 2 辨 識 標 籤 編 碼 的 演 算 法, 直 接 接 著 判 斷 是 否 讀 取 器 已 經 識 別 完 所 有 的 標 籤 編 碼, 假 如 識 別 完 畢, 則 可 以 結 束 Inventory 階 段 準 備 進 入 下 一 個 階 段 ; 相 反 地, 還 沒 有 辨 識 完 所 有 的 標 籤 編 碼, 就 可 以 進 入 到 下 一 個 盤 點 回 合, 進 行 下 一 次 的 SLN-algorithm 在 判 斷 SLN 為 1 的 情 況 時, 會 開 始 進 行 判 斷 是 否 有 Blocker Tag 干 擾 讀 取 器 識 別 標 籤 編 碼 ( 如 圖 25) 首 先 觀 察 是 否 有 不 合 法 的 訊 號 出 現 在 不 合 理 的 時 間 槽 (Sempty) 當 中, 因 為 SLN 為 1 的 關 係,tags 的 slot counter 數 值 都 和 上 一 次 盤 點 回 合 的 數 值 相 同, 根 據 分 段 式 ALOHA 演 算 法 (slotted ALOHA algorithm) 的 運 作, 該 次 盤 點 回 合 的 各 時 間 槽 訊 號 會 是 相 同 的, 所 以 時 間 槽 的 狀 態 統 計 資 料 也 會 一 致, 但 是 該 盤 點 回 合 的 Q 值 則 會 依 據 Q 演 算 法 的 影 響 而 變 動, 因 為 Blocker Tag 的 存 在 會 影 響 時 間 槽 的 衝 突 情 況 增 加, 所 以 Q 會 以 增 大 的 方 式 進 行, 在 Q 比 上 一 次 盤 點 回 合 還 要 大 且 slot counter 的 最 大 值 不 變 的 情 況 下, 上 一 次 時 間 槽 最 大 值 之 外 的 部 份, 都 必 須 都 是 屬 於 無 (empty), 如 果 在 這 些 必 須 是 無 的 時 間 槽 中 回 收 到 標 籤 的 訊 號, 代 表 必 有 干 擾 讀 取 的 訊 號 存 在, 也 就 是 有 Blocker Tag 的 存 在 判 斷 完 Sempty 之 後, 如 果 時 間 槽 的 狀 況 一 切 正 常, 沒 有 出 現 未 知 的 訊 號 後, 統 計 該 次 時 間 槽 的 狀 態 資 料 (Rn), 比 對 上 一 次 盤 點 回 合 時 間 槽 的 狀 態 資 料 (Rn-1) 是 否 一 致, 如 果 統 計 資 料 一 致, 表 示 讀 取 器 讀 取 標 籤 沒 有 受 到 干 擾, 也 表 示 沒 有 Blocker Tag 的 存 在 ; 若 並 不 相 同, 代 表 讀 取 器 受 到 干 擾, 導 致 兩 次 的 統 計 資 料 不 一 致, 讀 取 器 遭 受 到 Blocker Tag 的 影 響 在 此 多 判 斷 兩 個 盤 點 回 合 的 資 料 是 否 相 同, 是 為 了 防 止 有 點 聰 明 的 Blocker Tag 的 存 在 ; 如 果 Blocker Tag 以 機 率 性 的 方 式 處 在 時 間 槽 當 中, 很 湊 巧 的 干 擾 區 域 都 在 上 一 次 盤 點 回 合 的 時 間 槽 之 內, 則 Sempty 的 方 法 無 法 判 斷 出 是 否 有 Blocker Tag 的 存 在, 必 須 將 上 回 合 時 間 槽 範 圍 內 的 資 料 也 進 行 比 對, 才 可 以 偵 測 是 否 有 訊 號 干 擾 存 在 該 區 域 時 間 槽 之 內, 所 以 兼 具 觀 察 上 回 合 數 量 的 時 間 槽 和 此 回 合 新 增 加 的 時 間 槽 部 位, 才 是 安 全 完 善 的 偵 測 方 式 28
圖 25:SLN=1 時,Rn = Rn-1 以 上 的 情 況 都 沒 有 發 生 的 話, 最 後 在 判 斷 是 否 已 經 辨 識 完 所 有 的 標 籤 資 料, 尚 未 辨 識 完 畢 則 根 據 Q-algorithm 跑 完 的 結 果, 發 送 新 的 Query 命 令 給 標 籤 進 行 下 一 次 的 盤 點 回 合 ; 假 如 所 有 標 籤 辨 識 完 畢 之 後, 因 為 先 前 也 已 經 判 斷 過 沒 有 Blcoker tag 的 存 在, 所 以 沒 有 受 到 干 擾 而 導 致 缺 少 讀 取 標 籤 的 問 題, 那 麼 Inventory 階 段 的 運 作 便 順 利 完 成 了, 可 以 結 束 Inventory 階 段 準 備 進 入 下 一 個 階 段 :Access 4.2.3 Access 階 段 進 行 完 Inventory 階 段 的 動 作 後, 在 Access 階 段 就 可 以 進 行 RFID 系 統 最 主 要 的 功 能 動 作, 存 取 標 籤 儲 存 的 數 據 資 料, 其 數 據 資 料 可 能 有 : 產 品 訊 息 個 人 身 分 溫 度 溼 度 位 置 座 標, 儲 值 卡 金 額 等 資 訊, 可 以 讓 使 用 者 方 便 且 快 速 的 存 取 tags 資 料, 且 能 夠 一 次 存 取 多 張 標 籤 的 資 料 Access 階 段 中, 標 籤 的 資 料 可 能 會 有 密 碼 保 護 ( 在 2.2.3 中 有 介 紹 到 ), 當 讀 取 器 需 要 存 取 標 籤 資 料 時, 需 要 先 行 傳 送 ACCESS 密 碼 給 標 籤 進 行 比 對, 標 籤 便 會 將 收 到 的 資 料 與 記 憶 體 中 儲 存 的 ACCESS 密 碼 作 XOR 的 核 對, 然 後 標 籤 回 傳 比 對 密 碼 成 功 的 訊 號 給 讀 取 器 之 後, 讀 取 器 便 可 以 取 得 標 籤 資 料 直 到 讀 取 器 存 取 在 Inventory 階 段 中 識 別 的 所 有 標 籤 的 資 料 之 後,Access 階 段 便 可 以 結 束 了, 而 RFID 系 統 裡, 讀 取 器 存 取 標 籤 資 料 的 行 為 也 到 此 完 成 29
Chapter 5 分 析 與 實 驗 結 果 在 此 章 節 中, 我 門 將 利 用 實 驗 來 證 明 本 研 究 提 出 的 系 統 架 構 是 有 效 且 效 能 優 良 的 5.1 節 介 紹 實 驗 環 境, 使 用 Python 編 寫 EPCglobal Class 1 Generation 2 standard 的 環 境 5.2 節 介 紹 系 統 運 作 的 模 組 以 及 系 統 元 件, 在 其 小 節 中 會 呈 現 系 統 模 擬 的 元 件 5.3 節 分 析 本 論 文 和 其 他 的 偵 測 演 算 法 的 效 能, 實 驗 會 以 三 種 不 同 情 境 的 Blocker Tag 測 試, 並 且 在 其 小 節 中 分 別 以 偵 測 率 以 及 偵 測 速 度 分 析 比 較 5.1 實 驗 環 境 本 論 文 研 究 的 模 擬 環 境 如 表 1, 採 用 Python 的 程 式 語 言 來 撰 寫 模 擬 環 境, 因 為 模 擬 環 境 中 需 要 使 用 數 量 龐 大 的 class 才 能 表 示 系 統 環 境, 而 Python 提 供 了 簡 單 且 強 大 的 動 態 語 言, 動 態 語 言 的 意 思 表 示 為 直 譯 式 的 語 言, 所 以 幾 乎 任 何 東 西 都 可 以 在 執 行 時 動 態 決 定, 這 大 大 地 增 加 了 使 用 上 的 彈 性, 也 省 下 了 重 新 編 譯 的 時 間, 讓 開 發 週 期 更 短, 除 此 之 外,Python 也 是 良 好 的 物 件 導 向 程 式 語 言 可 讀 性 佳, 綜 合 以 上 的 原 因, 導 致 我 在 此 次 研 究 中 使 用 了 Python 作 為 開 發 系 統 表 1: 實 驗 環 境 CPU Intel Core 2 CPU 4400 @ 2.00GHz RAM 2.00 GB OS Windows XP professional SP3 Programming language Python 2.6.1 IDE Eclipse SDK Version:3.4.0 在 模 擬 環 境 的 設 定 上, 根 據 我 們 希 望 得 到 的 測 試 結 果 資 料, 影 響 模 擬 環 境 的 可 操 縱 變 數 在 系 統 中 有 三 個, 分 別 是 : 1. 正 常 Tag 的 數 量 (n_tag): 此 變 數 影 響 讀 取 器 總 共 需 要 存 取 的 標 籤 (tags) 總 數, 範 圍 由 50 到 400 且 間 距 50,50 和 100 的 參 數 選 擇 是 因 為 作 為 賣 場 購 買 物 品 的 數 量 為 限,100 以 上 是 考 慮 貨 物 倉 儲 管 理 系 統 的 數 量, 預 期 的 變 化 狀 態 是 和 時 間 成 正 比, 數 量 越 大 時 間 越 長 2. 異 常 Tag 的 數 量 (Blocker tag): 此 變 數 控 制 Blocker Tag 在 讀 取 範 圍 內 所 存 在 的 數 量, 預 期 的 變 化 狀 態 是 與 時 間 成 正 比, 數 量 越 多 時 間 耗 費 越 長 3. 阻 擋 率 (blocking rate): 此 變 數 操 作 Blocker Tag 的 阻 擋 機 率, 範 圍 由 0 到 1 的 小 數, 預 期 的 變 化 狀 態 是 與 時 間 成 正 比, 機 率 越 高 時 間 越 長 30
4.SLN 參 數 (SLN number): 此 變 數 操 作 是 否 執 行 SLN-algorithm, 變 數 資 料 只 有 0 和 1, 預 期 的 變 化 狀 態 是 在 1 的 時 候, 能 夠 確 實 的 找 出 Blocker Tag, 偵 測 攻 擊 時 間 的 長 短 並 不 受 到 阻 擋 率 ( 第 三 變 數 ) 以 及 數 量 ( 第 二 變 數 ) 的 影 響 5.2 系 統 元 件 在 系 統 環 境 上, 依 據 EPCglobal Class 1 Generation 2 standars 的 規 範 製 作, 在 Gen 2 標 準 轉 換 成 模 擬 環 境 ( 如 圖 26), 我 們 將 讀 取 器 以 及 Tag 規 劃 為 class, 其 中, 因 為 Tag 會 扮 演 兩 種 角 色, 分 別 是 一 般 正 常 的 Tag( 程 式 取 名 NORMAL_TAG) 和 有 阻 擋 性 的 Blocker Tag( 程 式 取 名 BLOCKER_TAG), 然 後 利 用 函 式 作 為 Gen 2 的 環 境 整 合 上 述 的 class 溝 通 在 環 境 的 建 構 上, 我 們 利 用 靜 態 變 數 控 制 訊 號 的 傳 遞, 分 別 代 表 讀 取 器 發 送 的 訊 號 以 及 標 籤 發 送 的 訊 號, 而 且 讀 取 器 會 從 標 籤 送 出 的 訊 號 中 觀 察 是 否 存 在 衝 突 的 狀 況, 相 同 地, 標 籤 也 會 從 讀 取 器 所 送 出 的 訊 號 切 換 自 身 的 狀 態 ; 在 運 作 的 流 程 上, 因 為 無 法 將 讀 取 器 所 發 送 出 的 訊 號 同 時 傳 遞 至 標 籤 的 身 上, 所 以 模 擬 實 驗 以 循 序 的 方 式 傳 遞 讓 標 籤 規 律 性 的 運 作, 如 此 一 來, 標 籤 可 以 被 當 作 是 同 時 收 到 訊 號, 並 且 同 時 做 完 標 籤 該 做 的 動 作 圖 26: 環 境 的 函 式 5.2.1 標 籤 RFID Tag 在 Gen 2 標 準 中 被 制 定 了 七 種 狀 態 ( 如 圖 3):Ready Arbitrate Replay Acknowledged Open Secured 和 Killed, 因 為 RFID Inventory 階 段 的 通 訊 協 定 只 包 含 了 前 五 種 狀 態, 所 以 我 們 的 模 擬 環 境 也 只 採 用 了 其 五 種 在 下 表 表 2 所 示, 是 在 Tag class 當 中 所 處 理 的 函 式 名 稱,Send 和 Recv 31
是 作 為 標 籤 送 出 和 接 收 命 令 的 功 能, 接 收 到 命 令 之 後, 接 下 來 是 執 行 Event 的 函 式 功 能,Event 裡 面 依 據 標 籤 的 狀 態 判 斷 不 同, 會 有 不 同 的 動 作,Event 執 行 完 畢 之 後, 最 後 要 將 訊 息 傳 送 去, 所 以 整 體 流 程 的 順 序 是 Recv->Event->Send; newround 是 當 接 收 到 Query 的 參 數 之 後, 會 重 新 產 生 新 的 回 合, 要 重 新 設 定 新 的 標 籤 參 數 Event Send Recv Newround 表 2: 標 籤 類 別 中 的 函 式 Tag 處 理 所 有 狀 態 中 的 命 令 傳 送 回 資 料 接 收 命 令 刷 新 Tag 的 起 始 資 料 5.2.2 讀 取 器 讀 取 器 在 RFID 的 系 統 中 是 扮 演 發 號 命 令 的 角 色, 所 以 在 模 擬 讀 取 器 的 類 別 (class) 程 式 裡, 會 依 據 各 種 不 同 的 命 令 進 行 不 同 的 參 數 資 料, 除 此 之 外, 程 式 觀 察 RFID 系 統 是 否 存 在 Blocker Tag 的 判 斷 式, 便 是 處 在 讀 取 器 (Reader) 的 類 別 (class) 裡 面, 因 為 只 有 讀 取 器 會 搜 集 到 標 籤 傳 送 回 來 的 訊 號, 所 以 就 在 收 到 標 籤 訊 號 之 後,Reader 程 式 也 同 時 進 行 判 斷 式 的 運 算 ; 在 現 實 環 境 的 時 候, 判 斷 式 的 運 算 工 作 也 是 執 行 在 讀 取 器 當 中, 這 樣 才 能 達 到 快 速 有 效 率 的 管 理, 如 果 需 要 後 端 伺 服 器 的 運 算 能 力 的 話, 將 統 計 資 料 送 回 到 伺 服 器 等 待 運 算 結 果 之 外, 還 要 等 候 資 料 傳 送 回 讀 取 器, 這 段 時 間 花 費 是 一 個 冗 長 的 間 隔, 會 嚴 重 影 響 到 RFID 管 理 系 統 的 效 率, 所 以 在 程 式 模 擬 上, 我 們 也 儘 量 做 到 運 算 過 程 簡 單 在 下 表 表 3 所 示, 是 在 Reader class 當 中 所 處 理 的 函 式 名 稱, 其 Send 和 Recv 的 功 能 和 Tag class 的 功 能 相 似, 差 別 在 於 Reader 送 出 的 是 命 令, 而 Event 是 處 理 不 同 命 令 之 間 如 何 去 做 切 換 的 動 作, 當 收 到 標 籤 的 資 料 後, 根 據 標 籤 的 資 料 內 容 更 改 當 下 Reader 所 需 要 送 出 的 命 令 資 料 ; 因 為 Reader 是 持 續 送 出 命 令 訊 號, 所 以 不 存 在 newround 這 個 功 能 函 式 Event Send Recv 表 3: 讀 取 器 類 別 中 的 函 式 READER 處 理 命 令 間 的 切 換 送 出 命 令 資 料 接 收 Tag 資 料 32
5.3 分 析 在 此 小 節 中, 將 針 對 三 種 不 同 的 演 算 法 以 及 三 種 不 同 的 情 況 的 Blocker Tag 做 分 析 與 比 較 其 中 三 種 演 算 法 分 別 是 Q 演 算 法 [4] AQ 演 算 法 [1] 和 本 篇 論 文 所 提 出 的 SLN 演 算 法 術 語 : Bn : 第 n th 個 Blocker Tag. ( 假 設 有 許 多 的 Blocker Tag 存 在 ) R : 符 合 Class 1 Gen 2 標 準 的 讀 取 器 Tn : 有 n 個 標 籤 (tags) 存 在 讀 取 範 圍 內 依 據 Blocker Tag 的 能 力 以 及 情 況 差 異, 我 們 把 Blocker Tag 規 劃 為 三 種 案 例, 以 下 將 說 明 各 種 Blocker Tag 的 情 況 : 個 案 1: 在 讀 取 範 圍 內 只 存 在 一 個 Blocker Tag, 該 Blocker Tag(B1) 是 比 較 原 始 且 愚 笨 的 Blocker Tag,B1 會 一 直 對 所 有 的 時 間 槽 發 送 回 覆 的 訊 號, 我 們 定 義 這 種 情 況 下 的 Blocker Tag 為 B α n ( 如 圖 27) 圖 27:Blocker Tag 的 案 例 1 案 例 2: 在 讀 取 範 圍 內 只 存 在 一 個 Blocker Tag, 該 Blocker Tag(B1) 是 一 種 比 較 聰 明 的 Blocker Tag,B1 只 會 對 某 些 的 時 間 槽 發 送 回 覆 的 訊 號, 並 且 回 傳 的 訊 號 可 以 是 衝 突 (collision) 的 訊 號, 我 們 定 義 這 種 Blocker Tag 為 B n β( 如 圖 28 和 圖 29) 此 種 情 況 下 的 Blocker Tag 有 著 兩 種 特 色 : (1)Blocker Tag 所 佔 的 百 分 比 ( 阻 擋 率 ) 33
(2)Blocker Tag 的 阻 擋 模 式 ( 回 傳 訊 號 型 態 ) 圖 28:Blocker Tag 的 案 例 2-(1) 圖 29:Blocker Tag 的 案 例 2-(2) 案 例 3: β 在 讀 取 範 圍 內 不 只 存 在 一 個 Blocker Tag, 該 Blocker Tag(B1) 是 屬 於 B n 的 Blocker Tag,n 的 數 量 則 不 一 定 ( 如 圖 30) 此 種 情 況 下 的 Blocker Tag 有 著 兩 種 特 色 : (1)Blocker Tag 所 佔 的 百 分 比 ( 阻 擋 率 ) (2)Blocker Tag 的 阻 擋 模 式 ( 回 傳 訊 號 型 態 ) (3)Blocker Tag 的 數 量 34
圖 30:Blocker Tag 的 案 例 3-(1) 圖 31:Blocker Tag 的 案 例 3-(2) 5.3.1 偵 測 率 在 此 小 節 中, 我 們 將 對 三 個 不 同 的 演 算 法 進 行 偵 測 率 的 比 較, 在 三 種 不 同 的 Blocker Tag 情 境 下, 是 否 能 夠 順 利 的 偵 測 出 有 Blocker Tag 的 存 在 (1) 案 例 1: Q 演 算 法 : 在 案 例 1 當 中 的 Blocker Tag 會 持 續 的 對 RFID 時 間 槽 做 出 發 送 訊 號 的 動 作, 而 Q 演 算 法 只 會 對 時 間 槽 中 的 狀 態 進 行 擴 大 縮 小 時 間 槽 空 間 的 動 作, 而 不 會 對 衝 突 率 過 高 產 生 其 他 應 對 措 施, 所 以 Q 演 算 法 只 會 永 無 止 盡 的 增 加 Q 的 值, 不 能 發 現 異 常 狀 態 的 訊 號 攻 擊 AQ 演 算 法 : 在 案 例 1 當 中 的 Blocker Tag 因 為 會 對 所 有 時 間 槽 發 出 訊 號, 所 以 當 Q 的 數 量 增 大 的 時 候,ACK(single) 的 訊 號 會 持 續 的 增 加, 因 此 達 到 A/Q 比 例 超 過 0.4, 即 可 有 效 偵 測 出 Blocker Tag 存 在 SLN 演 算 法 : 在 案 例 1 當 中 的 Blocker Tag 因 為 會 對 所 有 時 間 槽 發 出 訊 號, 而 SLN 35
演 算 法 會 設 定 正 常 的 tags 處 在 固 定 範 圍 內 的 時 間 槽, 只 要 發 現 固 定 時 間 槽 以 外 的 區 域 傳 回 訊 號, 則 表 示 有 Blocker Tag 的 存 在, 所 以 在 SLN 演 算 法 發 出 SLN 值 為 1 的 Query 訊 號 後, 觀 察 非 固 定 時 間 槽 的 區 域 是 否 回 應 訊 號, 便 可 以 有 效 偵 測 Blocker Tag 的 存 在 此 次 的 模 擬 實 驗 結 果,Q 演 算 法 的 模 擬 程 式 進 入 永 無 止 盡 的 運 作,AQ 演 算 法 和 SLN 演 算 法 的 模 擬 結 果 如 圖 33 所 示, 兩 者 演 算 法 所 提 供 的 偵 測 都 能 有 效 的 偵 測 出 Blocker Tag 的 存 在, 而 效 能 上 的 探 討 將 會 在 下 段 小 節 中 比 較 (2) 案 例 2: Q 演 算 法 : 在 案 例 2 當 中,Blocker Tag 會 將 阻 擋 時 間 槽 的 格 子 以 機 率 挑 選, 這 是 為 了 躲 過 一 些 偵 測 攻 擊 的 安 全 機 制, 而 Q 演 算 法 的 運 作 在 情 境 二 裡 可 以 完 整 的 讀 取 到 tags 的 編 碼, 只 是 在 效 能 執 行 上 花 費 龐 大 的 時 間, 但 是 Q 演 算 法 仍 舊 無 法 有 效 的 偵 測 出 Blocker tag 的 存 在 AQ 演 算 法 : 情 境 2 中 Blocker Tag 使 用 的 部 份 阻 擋 在 時 間 槽, 便 是 為 了 躲 過 此 演 算 法 的 偵 測 防 護 當 阻 擋 率 越 低 的 時 候,AQ 演 算 法 越 不 容 易 偵 測 出 Blocker Tag, 因 為 A/Q 比 例 上 升 的 速 度 較 慢 ; 相 反 地, 阻 擋 率 越 高 的 時 候,A/Q 比 例 上 升 較 快, 也 較 容 易 偵 測 出 Blocker Tag 的 存 在 除 此 之 外, 當 有 點 聰 明 的 Blocker Tag 可 以 發 送 出 衝 突 的 信 號 的 情 況 下,AQ 演 算 法 無 法 偵 測 出 是 否 有 Blocker Tag, 因 為 在 時 間 槽 總 是 衝 突 信 號 的 時 候, 不 存 在 任 何 的 Ack 訊 號 SLN 演 算 法 : 情 境 2 的 Blocker Tag 雖 然 是 以 機 率 性 的 方 式 阻 擋 在 時 間 槽 中, 但 是 當 我 們 以 限 定 正 常 tags 處 在 某 依 範 圍 內 的 時 間 槽, 雖 然 Blocker Tag 有 機 會 能 僅 存 在 正 常 tags 限 定 範 圍 內, 並 且 剛 好 只 落 在 有 產 生 衝 突 的 時 間 槽 當 中, 但 凡 機 率 越 低 的 時 候, 會 有 越 高 的 機 會 可 以 躲 過 偵 測, 經 過 實 驗 的 測 試 後 ( 如 圖 37), 在 此 建 議 連 續 執 行 兩 次 SLN=1; 除 此 之 外, 即 使 Blocker Tag 可 以 發 送 出 衝 突 的 信 號, 仍 舊 可 以 依 照 SLN 演 算 法 的 機 制 偵 測 出 Blocker Tag (3) 案 例 3: Q 演 算 法 : 在 情 境 3 的 狀 況 上, 只 要 不 存 在 情 境 1 的 Blocker Tag,Q 演 算 法 就 可 以 辨 認 出 所 有 的 標 籤 編 碼, 只 是 時 間 上 會 很 冗 長 測 試 的 實 驗 結 果 如 圖 39 AQ 演 算 法 : 情 境 3 的 組 合 上, 根 據 機 率 的 大 小 進 行 排 列 組 合, 會 有 不 同 的 情 況 發 生, 而 AQ 演 算 法 也 能 夠 有 效 的 偵 測 Blocker Tag, 但 是 在 一 種 情 況 下 會 發 生 偵 測 失 效, 就 是 在 如 果 有 兩 個 情 境 1 的 Blocker Tag 干 擾 下,AQ 演 算 法 無 法 依 據 AQ 比 例 做 為 判 斷 式 ; 實 驗 測 試 結 果 如 圖 40 36
SLN 演 算 法 : 在 情 境 3 的 環 境 中, 如 果 有 越 多 的 Blocker Tag 存 在 的 話, 越 能 偵 測 出 Blocker Tag 的 存 在, 因 為 SLN 演 算 法 所 設 置 的 非 固 定 區 域, 會 有 其 它 的 Blocker Tag 會 回 應, 提 高 了 偵 測 率 5.3.2 時 間 性 在 此 小 節 裡, 將 會 針 對 每 個 情 境 中, 需 要 辨 識 所 有 的 標 籤 須 要 的 時 間, 比 較 時 間 的 方 式 採 用 Query 命 令 的 數 量 為 時 間 單 位, 包 含 偵 測 Blocker Tag 的 時 間 單 位 一 起, 完 整 的 識 別 標 籤 編 碼 的 時 間 : 偵 測 Blocker Tag 所 花 費 的 時 間 + 無 Blocker Tag 識 別 標 籤 的 時 間 正 常 RFID 系 統 識 別 標 籤 所 需 要 的 Query 數 量 如 圖 32 Normal RFID syatem 1200 1000 Query 數 量 800 600 400 200 Q-algorithm 0 50 100 150 200 250 300 350 400 Tags 數 量 圖 32: 正 常 的 RFID 系 統 (1) 案 例 1: 在 案 例 1 的 環 境 下, 因 為 是 一 種 比 較 笨 的 Blocker Tag, 所 以 除 了 Gen2 標 準 裡 的 Q 演 算 法 無 法 識 別 全 部 的 tags 編 碼,AQ 以 及 SLN algorithm 其 偵 測 Blocker Tag 出 來 的 時 間 如 下 圖 33 識 別 完 目 標 範 圍 內 的 tags 所 需 要 的 時 間 : 偵 測 Blocker Tag 所 花 費 的 時 間 + 無 Blocker Tag 識 別 tags 的 時 間 37
Situation 1 25 20 Query 數 量 15 10 AQ-algorithm SLN-algorithm Q-algorithm is infinite 5 0 50 100 150 200 250 300 350 400 Tags 數 量 圖 33: 笨 拙 的 Blocker Tag( 案 例 1) 在 案 例 1 裡 面, 因 為 Q 演 算 法 無 法 識 別 且 偵 測 Blocker Tag 存 在, 所 以 Q 演 算 法 的 時 間 設 定 為 無 窮 大 按 例 1 的 時 間 比 較 圖 如 下 圖 圖 34 AQ 演 算 法 所 花 費 的 時 間 大 於 SLN 演 算 法, 而 SLN 演 算 法 的 時 間 接 近 於 一 般 情 況 下 的 RFID 系 統 Performance in Situation 1 Query 數 量 1000 900 800 700 600 500 400 300 200 100 0 50 100 150 200 250 300 350 400 Tags 數 量 Normal RFID system AQ-algorithm SLN-algorithm 圖 34: 各 演 算 法 在 案 例 1 的 效 能 (2) 案 例 2: 在 情 境 2 當 中,Q 演 算 法 可 以 順 利 的 識 別 所 有 的 標 籤 編 碼, 且 可 以 從 下 圖 圖 35 觀 察 到 識 別 的 時 間, 根 據 Blocker Tag 阻 擋 率 的 上 昇 而 增 加 接 著 圖 36 是 38
AQ 演 算 法 在 案 例 2 中 偵 測 Blocker Tag 所 花 費 的 Query 數 量 ; 然 後 圖 37 是 SLN 演 算 法 的 花 費 Query 數 量 Q-algorithm in Situation 2 Query 數 量 18000 16000 14000 12000 10000 8000 6000 4000 2000 0 0% 10% 20% 30% 40% 50% 60% 70% 80% 90% 100 % Blocker Tag 阻 擋 率 50 Tags 100 Tags 150 Tags 200 Tags 250 Tags 300 Tags 350 Tags 400 Tags 圖 35:Q 演 算 法 在 案 例 2 的 效 能 AQ-algorithm in Situation 2 Query 數 量 25 20 15 10 5 0 0% 10% 20% 30% 40% 50% 60% 70% 80% 90% 100 % Blocker Tag 阻 擋 率 50 Tags 100 Tags 150 Tags 200 Tags 250 Tags 300 Tags 350 Tags 400 Tags 圖 36:AQ 演 算 法 在 案 例 2 的 效 能 39
SLN-algorithm in Situation 2 Query 數 量 1.5 1 0.5 0 0% 10% 20% 30% 40% 50% 60% 70% 80% 90% 100 % Blocker Tag 阻 擋 率 50 Tags 100 Tags 150 Tags 200 Tags 250 Tags 300 Tags 350 Tags 400 Tags 圖 37:SLN 演 算 法 在 案 例 2 的 效 能 我 們 從 案 例 2 的 各 實 驗 結 果 當 中, 取 出 兩 個 參 數 值, 分 別 為 最 大 和 最 小 值, 作 為 比 較 Query 數 量 的 大 小, 因 為 最 大 最 小 可 以 作 為 最 佳 和 最 差 其 中, 在 AQ 演 算 法 的 實 驗 結 果 當 中,Query 的 數 量 隨 著 標 籤 的 數 量 大 小 增 加, 被 Blocker Tag 的 阻 擋 率 影 響 比 較 不 大 ;SLN 演 算 法 在 各 種 阻 擋 率 當 中, 並 不 會 被 影 響 偵 測 流 程, 所 以 花 費 的 時 間 和 情 境 1 相 同 下 圖 是 案 例 2 的 時 間 比 較 Performance in Situation 2 600 Query 數 量 400 200 Normal RFID system Q-algorithm_10% Q-algorithm_90% AQ-algorithm_10% AQ-algorithm_90% SLN-algorithm_10% SLN_algorithm_90% 0 50 100 150 200 250 300 350 400 Tags 數 量 (3) 案 例 3: 圖 38: 各 演 算 法 在 案 例 2 的 效 能 在 案 例 3 中, 觀 察 實 驗 的 測 試 結 果 ( 圖 39),Q 演 算 法 當 Blocker Tags 的 阻 40
擋 率 處 在 兩 個 Blocker Tag 阻 擋 率 相 加 為 1 的 時 候 具 有 最 大 的 攻 擊 力, 因 為 當 相 加 超 過 1 的 情 況 下, 根 據 鴿 籠 原 理,Blocker Tags 本 身 自 己 就 會 進 行 衝 突 狀 態, 而 對 於 相 加 小 於 1 的 情 況 來 說, 衝 突 發 生 的 機 率 沒 有 相 加 為 1 來 的 高, 所 以 使 得 相 加 為 1 的 時 候,Blocker Tags 的 攻 擊 性 最 強 圖 39:Q 演 算 法 在 案 例 的 效 能 AQ 演 算 法 處 在 案 例 3 的 環 境 中, 當 有 兩 個 Blocker Tags 一 起 進 行 訊 號 干 擾 的 情 況, 實 際 上 是 和 情 境 2 當 中 的 實 驗 結 果 相 似 ( 如 圖 40), 有 兩 個 Blocker Tags 在 一 起 的 時 候, 會 以 阻 擋 率 比 較 高 的 Blocker Tag 為 主, 因 為 阻 擋 率 比 較 高 的 Blocker Tag 會 有 比 較 大 的 機 會 傳 送 回 ACK; 但 是 當 兩 個 Blocker Tag 的 阻 擋 率 都 是 1 的 時 候, 就 和 情 境 2 當 中 的 問 題 一 樣,AQ-algorithm 的 ACK 收 不 到 訊 號 則 無 法 偵 測 Blocker Tag 的 存 在 41