在繼續討論更多 browser fingerprinting 技術前，我想做個小小的 detour，討論與 browser fingerprinting 密切相關的主題：bot detection。此文我們將介紹 Picasso，一款基於 canvas fingerprinting 的 bot detection 技術，這個技術雖然不多人知道，但大家肯定都用過（或被用過），所以我想值得花一些時間討論。
Bot detection 是指偵測機器人的一系列的技術。由於網路上充滿了有價值的資訊，有些人會寫個程式去自動化地爬這些資料，或做自動操作。常見的情境包含使用程式大量下載網頁內容、電商上特定商品的售價等，或是使用程式搶火車票等。通常我們稱這些程式為「機器人」（bot）或「爬蟲」（crawler），兩者略有不同但這裡不細分，以下就統稱 bot。一般來說，避免這些 bot，大家就開發了一系列的技術去識別 bot，也就是 bot detection。Bot detection 大致可以分為主動與被動，主動的有常見的 Captcha（就是那些歪歪扭扭的字或是「我不是機器人」的鬼東西），但這對使用者體驗不太好，看到驗證碼就覺得煩躁，如果不希望影響使用者體驗，另一種是被動的 bot detection，也就是在背後低調蒐集各種資料，去猜這個使用者是不是 bot。
今天我們要討論的技術是 Picasso，它是一種被動的 bot detection，其利用 canvas fingerprinting 的特色，去識別一個訪客是否有造假它的 user agent。舉例來說，一個宣稱自己是 iOS + Safari 的訪客，他可能真的是拿 iPhone，也可能是跑在 iOS Simulator 裡面，也可能從頭到尾就是胡扯，他根本是 Puppeteer（一款基於 Chrome 的 bot）。
Picasso 是一款由 Google 的 anti-abuse 團隊開發的 bot detection 技術，目前大家最常遇到的應用可能是 Cloudflare 的 bot detection，如果有遇到 Cloudflare 畫面說要稍等幾秒，他就是在背景偷偷跑 Picasso。
Picasso 主要的目標是，根據軟硬體（從 CPU、顯卡一路到 browser）的差異，找出裝置分類。換言之，Picasso 的目標不是唯一地識別每個訪客（這是 browser fingerprinting 的目標），而是區別不同類型的裝置。區別裝置類型之所以重要，在於許多 bot 為了避免自己被發現，會改變 user agent 或是 browser behavior，使自己隱藏在眾多其他正常訪客之中。例如，bot 可能會假裝自己是 iOS 上跑著 Safari 的訪客，正如所有其他 iPhone 使用者。於是我們需要找到一個沒那麼容易偽造的資料點，於是 Picasso 訴諸於 canvas 的細微差異：假裝自己是 iPhone 的 bot 沒有辦法輕易模仿 iPhone 生產出來的 canvas。
Picasso 的第二個目標是 proof of work：要完成驗證，訪客要完成一定程度的計算，如此則會拖慢 bot 的執行速度，但又不至於慢到被一般使用者察覺。以 Picasso 來說，每次計算會拖慢 20ms 左右，這對於爬網站來說已經是個可觀的延遲，但一般使用者很可能根本沒感覺到。
Picasso 是個 challenge-response 系統：服務端提出一個挑戰，客戶端接受挑戰，把答案算出來，供服務端驗證。
一開始，服務端與客戶端要共同約定好一個 PRNG 以及一個畫圖的 function F（畫出特定字型、圖形、quadratic curve、bezier curve 等），F 可以根據亂數結果 deterministically 地輸出一張 canvas。對於 F 主要有兩個要求：在同類型的裝置上要產生一樣的結果，且輸出必須足夠 stable，可以預期每次產生的結果都是一樣的。
每一個挑戰包含了 random seed 與要畫幾次，客戶端收到挑戰後，首先會將 random seed 餵進 PRNG，然後使用 F 將挑戰所要求的圖形繪製出來，並重複多次，並將每一次 canvas 的輸出和前一次連接在一起算 hash，最後一輪時直接把 hash 結果輸出。因此我們會發現這本質上是個 one-way function：
（圖取自 Bursztein et al.）
如此做有幾個好處：首先，因為整個過程都是 deterministic 的，所以一樣的輸入會有一樣的輸出；此外，我根據 random seed a 算出來結果之後，如果要推出 random seed b 算出來的結果，只能全部重算，因此藉由 random seed 可以避免 replay attack；最後，藉由控制繪圖次數，可以達到 proof of work 的效果。
但有個 response 還是沒解決問題啊，我怎麼知道這個 response 是不是真的。說來簡單：我自己也算一次啊。Picasso 的確要求服務端要先自己準備好一些裝置以及參數，預先算好結果，然後存在 DB 裡面供驗證用。也就是說，在一開始，DB 裡面會有 (challenge, response) -> user agent or device class 的 mapping 關係。
有了最基本的數據之後，接下來的部份就與 reCAPTCHA 很像了。服務端會先偵測客戶端的裝置類型（通常根據 user agent），並給客戶端兩個 challenge，一個是在 DB 裡面已經有答案的 challenge，一個則是未知的 challenge，但客戶端不會知道哪個是未知的，於是他只能解開兩個 challenge 並回傳。
服務端收到回傳之後，會先驗證已知的部份，確定他沒有說謊。如果已知的部份未能通過驗證（也就是給的 response 是錯的），大概就代表 user agent 是假的，該訪客所使用的裝置類型並非如他所宣稱的那樣。
如果通過驗證，則猜測這個訪客不是 bot，並把未知的部份預留下來。如果有足夠多的相同類型的裝置（相同 user agent 的裝置）在遇到同一個 challenge 時都回傳同一個 response，就可以大膽猜測這個 response 是對的，於是就可以在 DB 新增一筆 (challenge, response) -> user agent or device class 的關係。藉由不但新增 challenge 的 pool，服務方可以避免 replay attack，畢竟隨著 pool 越來越大，要遇到同個 challenge 的機率很低。
舉例來說，同樣宣稱自己是 iOS + Safari，真正的 iPhone 跟在模擬器中的 iPhone 便會產生不同的結果，於是就可以猜測後者是 bot。
（圖取自 Bursztein et al.）
Google 的研究團隊做了很多實驗，證明這個方法真的有效，但這部份就留給有興趣的讀者去讀他們的論文吧。
Bursztein, Elie, et al. "Picasso: Lightweight device class fingerprinting for web clients." Proceedings of the 6th Workshop on Security and Privacy in Smartphones and Mobile Devices. 2016.
Overview of Google’s Picasso
看影片追技術