在 Git/Mercurial/Subversion 上 "-" 發生的問題

在「[ANNOUNCE] Git v2.14.1, v2.13.5, and others」這邊看到 - 開頭產生的問題:

These contain a security fix for CVE-2017-1000117, and are released in coordination with Subversion and Mercurial that share a similar issue. CVE-2017-9800 and CVE-2017-1000116 are assigned to these systems, respectively, for issues similar to it that are now addressed in their part of this coordinated release.

這算是老問題了,Git 對應的修正主要是朝 filter input 的方向修正,包括了禁用 - 開頭的 hostname,以及禁止 GIT_PROXY_COMMAND- 開頭,另外是禁止開頭是 - 的 repository name:

  • A "ssh://..." URL can result in a "ssh" command line with a hostname that begins with a dash "-", which would cause the "ssh" command to instead (mis)treat it as an option. This is now prevented by forbidding such a hostname (which should not impact any real-world usage).
  • Similarly, when GIT_PROXY_COMMAND is configured, the command is run with host and port that are parsed out from "ssh://..." URL; a poorly written GIT_PROXY_COMMAND could be tricked into treating a string that begins with a dash "-" as an option. This is now prevented by forbidding such a hostname and port number (again, which should not impact any real-world usage).
  • In the same spirit, a repository name that begins with a dash "-" is also forbidden now.

然後中華電信的 DNS server (168.95.1.1 & 168.95.192.1) 都查不到 marc.info,改用 Google 的 8.8.8.8 才查得到... =_=

Quotient filter

之前有提過「Cuckoo Filter:比 Bloom Filter 多了 Delete」,最近在「A general purpose counting filter: making every bit count」這邊看到 Quotient filter,也是類似 Bloom filter 的資料結構,但想要解決更多問題。

一般的 Bloom filter (BF) 會有這些問題:

  • The inability to delete items
  • Poor scaling out of RAM
  • The inability to resize dynamically
  • The inability to count the number of occurrences of each item, especially with skewed input distributions.

而文章裡提到的 Quotient filter (QF) 就是要解這些問題。另外還提到了 Rank-and-Select-based Quotient filter (RSQF) 以及 Counting Quotient filter (CQF)。雖然多了一些空間需求,但看起來解掉不少問題... (尤其是刪除的能力)

效能上也還不錯,尤其是讀取速度的部份... 不過不知道相對於 Cuckoo filter 差多少。

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

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