Cuckoo Filter:比 Bloom Filter 多了 Delete

在「Cuckoo Filter implementation in Go, better than Bloom Filters」這邊看到這個資料結構,有興趣的人也可以看「Cuckoo Filter:设计与实现」這篇介紹,下面是我抓重點整理。

Bloom Filter 支援的操作:

  • Add(element)
  • Query(element)

1970 年提出來的資料結構。優點是空間複雜度是 O(1),Query(element) 會有可接受的 false positive,缺點是不支援 Delete(element)、以及數量變多時誤判率的增加。

Cuckoo Filter 多了一組操作:

  • Delete(element)

2014 年提出來的資料結構。空間複雜度一樣是 O(1),但相同的空間用量下 false positive 變低,然後支援 Delete(element) 了。也因此論文直接寫「Cuckoo Filter: Practically Better Than Bloom」,表示可以直接替代。

WhatsApp 過濾關於出現「Telegram」的連結

WhatsApp (2014 年被 Facebook 買下) 過濾 Telegram 連結的消息在國外引發討論了:「As of today, WhatsApp is blocking Telegram links」。這讓維基百科裡「WhatsApp」這段說明看起來特別的奇特:

WhatsApp宗旨是給予人們一個不被竊聽的溝通橋樑,並從不存取用戶個人資料,像是姓名、性別、年齡或者聊天紀錄,這和烏克蘭裔的創辦人庫姆在有秘密警察的共產國家成長有關,他孩童時期的經歷讓他懂得通訊沒有被監聽的珍貴。

作者在 app 上測了幾個連結:

Whatsapp-blocks-Telegram-copy-yes

這張圖可以看出來 telegram.org 的連結無法點擊。弄了老半天後,發現程式直接針對 Telegram 相關的網域擋掉了:

nexus2cee_Screen-Shot-2015-12-01-at-10.11.09-2

拉張板凳來看看後續會變成什麼樣子...

PHP 5.5 的 Generators

在「Save memory by switching to generators」這邊提到了 PHP 5.5 開始提供的 Generators...

由於其他的程式語言有 Generators 的觀念,其實不會太難了解...

不過比較大的問題是,資料庫的查詢操作用 Generators 會把效能壓力壓回資料庫:因為資料庫需要把結果 buffering 在資料庫端,如果不趕快吐出去就是要找記憶體放... 也因此,比較常見到的解法是不要用 Generators。(因為 web 與 application 端相較於資料庫端,比較容易 scale)

後來用 Generators 比較多的印象中還是 filter 類的應用吧,Python 這邊的東西有陣子沒看了 :o

用 Intel 網卡上的 Flow Director 過濾封包

在「Traffic filtration using NIC capabilities on wire speed (10GE, 14Mpps)」這邊看到的技巧。

作者建議另外安裝 driver,因為 Linux kernel 內的 driver 功能有限:「Intel Ethernet Drivers and Utilities」。

重點在 ethtool 這個工具,可以看到條件設定:

ethtool --help:
        ethtool -N|-U|--config-nfc|--config-ntuple DEVNAME    Configure Rx network flow classification options or rules
        rx-flow-hash tcp4|udp4|ah4|esp4|sctp4|tcp6|udp6|ah6|esp6|sctp6 m|v|t|s|d|f|n|r... |
        flow-type ether|ip4|tcp4|udp4|sctp4|ah4|esp4
            [ src %x:%x:%x:%x:%x:%x [m %x:%x:%x:%x:%x:%x] ]
            [ dst %x:%x:%x:%x:%x:%x [m %x:%x:%x:%x:%x:%x] ]
            [ proto %d [m %x] ]
            [ src-ip %d.%d.%d.%d [m %d.%d.%d.%d] ]
            [ dst-ip %d.%d.%d.%d [m %d.%d.%d.%d] ]
            [ tos %d [m %x] ]
            [ l4proto %d [m %x] ]
            [ src-port %d [m %x] ]
            [ dst-port %d [m %x] ]
            [ spi %d [m %x] ]
            [ vlan-etype %x [m %x] ]
            [ vlan %x [m %x] ]
            [ user-def %x [m %x] ]
            [ action %d ]
            [ loc %d]] |
        delete %d

看起來 stateless 的過濾可以在上面做...

BPF (Berkeley Packet Filter)

看到 CloudFlare 的「BPF - the forgotten bytecode」在文章裡提到 BPF (Berkeley Packet Filter),發現從大學畢業後就沒再看過... (然後也沒什麼印象了)

tcpdump 可以把 expression 轉成 BPF bytecode,再丟進 kernel 執行,拿 CloudFlare 文章裡的例子在自己電腦上跑:

gslin@GSLIN-DESKTOP [~] [07:27/W4] sudo tcpdump -p -ni eth1 -d "ip and udp"
(000) ldh      [12]
(001) jeq      #0x800           jt 2    jf 5
(002) ldb      [23]
(003) jeq      #0x11            jt 4    jf 5
(004) ret      #65535
(005) ret      #0

而對於複雜的過濾邏輯而需要拼效能時,可能會需要手動寫 bytecode (像是優先先判斷某些比較容易過濾的欄位,藉以降低判斷的量),可以透過 SOCK_RAWSO_ATTACH_FILTER 直接寫 bytecode 給 kernel 執行。

雖然文章內沒有明講,不過看起來 CloudFlare 有這樣做,尤其後面又有提到:

These kind of rules are very useful, they allow us to pinpoint the malicious traffic and drop it early. Just in the last couple of weeks we dropped 870,213,889,941 packets with few BPF rules. Recently during a flood we saw 41 billion packets dropped throughout a night due to a single well placed rule.

記起來以後說不定用的到...

圖片的去背...

Lyst 的「Image Background Removal」這篇在講圖片去背的方法。

Lyst 是把這個演算法用在上架自動分類的一環:圖片先去背,然後再用 classifier 綜合其他的 metadata 判斷要分到那一類。

這邊去背的演算法很簡單:

其實 Lyst 這篇是在說「要怎麼打組合拳」:利用現有最簡單的技術去堆積木,想辦法找出一套合理的解。而不是像學術上的那樣要求做到極致。所以也有像這樣不是處理的很好的:

這種組合拳反倒還蠻適合在學校裡教?

關於 Non-null string 的處理...

上一篇「Filter Input & Escape Output...」有提到 Non-null UTF-8 string 的 filter,結果剛剛洗澡的時候想了想,好像寫錯了?

問題在於「到底是先 de-null 再 iconv(),還是先 iconv() 再 de-null」的問題。

這個問題其實跟 iconv() 成 UTF-8 時遇到不合法字元時怎麼實做有關,也就是 undefined behavior... 由於 \0 是合法的 UTF-8 character,所以我們假設某一種實做是當 iconv() 遇到不合法字元時會用 \0 帶進去:

先 de-null 再 iconv()

這是上一篇文章提到的方法。但在上面提到的 iconv() 實做下卻是有問題的方法。原因很簡單,de-null 後沒有 \0 的字串,卻會因為 iconv() 而產生 \0

先 iconv() 再 de-null

這邊要考慮的是最後 de-null 後會不會變成 invalid UTF-8 string。答案是不可能,因為 iconv() 轉出來後保證是 UTF-8 string (不論如何處理非 UTF-8 character 的部份),而 UTF-8 string 內的 \0 一定可以當 separator,所以切下去一定還是 UTF-8 string。(可以參考下圖關於 UTF-8 character 的規則)

所以?

可能以現在的 iconv() 實做來說,兩者都不會有問題,但寫程式的時候總是要避免 side-effect,所以後者的方法會比前者好。

Filter Input & Escape Output...

維基百科上有一篇「Secure input and output handling」說明要怎麼處理 input 與 output (對資安方面的說明)。標題的 Filter Input 與 Escape Output 是 Gasol 之前提到後才知道的名詞,以前只知道要 validate & escape,沒想過一個比較好記的念法...

這邊都以 PHP 為主,其他程式語言也應該會有對應的方式...

Input 有很多管道,有可能是使用者或是 3rd party 廠商透過 Form 傳進來的資料 (在 PHP 裡可能是 $_GET 或是 $_POST),也有可能是 cookie 的資料 (因為使用者可以修改,所以視為不安全的資料)。從檔案讀資料進來 (可能是普通的文字檔,或是 XML,也可能是圖片) 也算是 input。

Output 也有很多管道,像是 HTML、JSON,或是組 SQL statement 時使用變數。

Filter Input

在處理 input data 時,一般常常忘記的是「先強制轉成 Non-null UTF-8 string」(現在一般都是用 UTF-8,所以這邊就只講 UTF-8)。

這是因為很多 PHP function 對非 Non-null UTF-8 string 有非定義行為 (undefined behavior,不保證效果與輸出結果的正確性),加上一般常見的產品需求可以用 Non-null UTF-8 string 滿足,所以在 PHP 內拿到資料時可以先 filter 過。

Update:下面說的步驟錯了,請參考「關於 Non-null string 的處理...」這篇的說明。

有兩個步驟要做,第一個是確保他是 Non-null,直接把 \0 以及以後的東西幹掉:

$str_out = preg_replace('/\0.*/g', '', $str_in);
$str = preg_replace('/\0.*/g', '', $str); // 直接取代原來字串

第二個是確保他是 UTF-8 string。這點可以直接用 iconv() 轉,而不用自己寫 regex 處理了:

$str_out = iconv('UTF-8', 'UTF-8', $str_in);
$str = iconv('UTF-8', 'UTF-8', $str);

iconv() 從 UTF-8 轉到 UTF-8 是一個特別的用法,我是在 Cal Henderson 的「Building Scalable Web Sites: Building, Scaling, and Optimizing the Next Generation of Web Applications」上看到的 (有中譯版)。

如果傳進來的值本來就假設是整數,那麼就用 intval() 轉一次。如果假設是非負整數 (包含 0),那麼就用 abs()intval()。如果是文字類的 (像是 e-mail),可以再用其他的 regex 檢查。

一般來說,白名單會比黑名單好。不過這也是一般性,很多時候還是很囧的...

Escape Output

Escape 指的是 Escape character (轉義字元)。不同的情況下會有不同的 escape character,所以保護的方式也不一樣。

以 HTML 來說,想要顯示小於符號 <,實際上要用 &lt; 表示。而在 PHP 裡面常用的 htmlspecialchars() 定義了「只 escape 五個符號」,剛好可以拿來用:

<div><?= htmlspecialchars($str) ?></div>

也有人推薦 htmlentities(),不過因為轉的比較多 (所以要考慮的行為比較多),我比較不喜歡...

對於 XML,在 XML 的規範裡規定一定要把 <& 換成 &lt;&amp; (Character Data and Markup),但 > 則可以 (非必要) 換成 &gt;。也允許把雙引號 " 換成 &quot;,以及單引號 ' 換成 &apos;

所以 XML 剛好可以直接用 htmlspecialchars() (確認完全符合 spec 要求),反過來 htmlentities() 就不保證了。

再來是 MySQL 的 escape 與 charset 有關,所以要用 mysql_real_escape_string() 或是 PDO::quote(),但更好的方法應該是使用 prepare & execute (binding variables)...

而 shell 的 escape 則應該用 escapeshellarg() 再帶入 string 裡。

每一種 output 所需要的 escape function 不同,都不能直接拿 addslashes() 來用... (這個 function 的設計就很 PHP...)

純粹 JSON 的話,用 json_encode() 就可以幫你處理好。問題是在 HTML + JSON 時會讓你處理到抱頭痛哭... 這就是另外的故事了 +_+

結論?

Filter Input + Escape Output 只是最基本的一步,不過在大多數的狀況下,這個方法就可以擋下不少問題了,算是很實用的 policy...

Protocol Preserve URI 的過濾

雖然知道 //host.domain/path 這種 Relative Protocol 用法 (而且也用很久了),不過最近在 irc.perl.org 上的 #plack 剛好有人提到,再加上最近剛好有人在探討安全性問題:「Bypassing "RequestPolicy" Using Protocol Relative URLs」,剛好可以拿出來再說一次。

簡單來說就是「以 / 開頭的 URI 並非一定是 same origin,不可以以此當作 same origin 的判斷」。因為「//ajax.googleapis.com/ajax/libs/jquery/1.5.0/jquery.min.js」這種用法是正確的用法,表示保留 Protocol。

另外講些題外話,這個用法也還是有缺點,用在 IE 的 css 時會造成重複抓取 (到 IE9 都還是):「CSS files downloaded twice in Internet Explorer with protocol relative URLs」,script 或是 relative path 都不會,只有 css 會...

反過來說,因為 js 的部份大家都沒問題,所以當使用 Google 提供的 jQuery 時,「永遠」都應該使用「//ajax.googleapis.com/...」,因為 Google Libraries API 是同時支援 HTTP 與 HTTPS 的。