Tag Archives: 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」,表示可以直接替代。

Posted in Computer, Murmuring, Programming | Tagged , , , , , , , | Leave a comment

Google Chrome Developer Tools 裡的 Network Filter

在「Chrome Network Panel Filter: Domain」這篇看到有趣的用法: 輸入完 domain: 後會列出許多選擇讓你選,還包括了 wildcard... 這功能真不錯 @_@

Posted in Browser, Computer, GoogleChrome, Murmuring, Network, Software, WWW | Tagged , , , , , , , | Leave a comment

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

WhatsApp (2014 年被 Facebook 買下) 過濾 Telegram 連結的消息在國外引發討論了:「As of today, WhatsApp is blocking Telegram links」。這讓維基百科裡「WhatsApp」這段說明看起來特別的奇特: WhatsApp宗旨是給予人們一個不被竊聽的溝通橋樑,並從不存取用戶個人資料,像是姓名、性別、年齡或者聊天紀錄,這和烏克蘭裔的創辦人庫姆在有秘密警察的共產國家成長有關,他孩童時期的經歷讓他懂得通訊沒有被監聽的珍貴。 作者在 app 上測了幾個連結: 這張圖可以看出來 telegram.org 的連結無法點擊。弄了老半天後,發現程式直接針對 Telegram 相關的網域擋掉了: 拉張板凳來看看後續會變成什麼樣子...

Posted in Computer, Murmuring, Network, Political, Social, Software | Tagged , , , , , | 2 Comments

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

Posted in Computer, Database, Murmuring, Programming, Software | Tagged , , , , , , , , , | Leave a comment

用 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... … Continue reading

Posted in Computer, Hardware, Linux, Murmuring, Network, OS, Security, Software | Tagged , , , , , , , , , , , , | Leave a comment

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 … Continue reading

Posted in Computer, Murmuring, Network, Security | Tagged , , , , , , , , | Leave a comment

圖片的去背...

Lyst 的「Image Background Removal」這篇在講圖片去背的方法。 Lyst 是把這個演算法用在上架自動分類的一環:圖片先去背,然後再用 classifier 綜合其他的 metadata 判斷要分到那一類。 這邊去背的演算法很簡單: 其實 Lyst 這篇是在說「要怎麼打組合拳」:利用現有最簡單的技術去堆積木,想辦法找出一套合理的解。而不是像學術上的那樣要求做到極致。所以也有像這樣不是處理的很好的: 這種組合拳反倒還蠻適合在學校裡教?

Posted in Computer, Murmuring, Programming, Software | Tagged , , , , , , , , , , , , , | Leave a comment

關於 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 … Continue reading

Posted in Computer, Murmuring, Programming, Security, Software | Tagged , , , , , , , , , | 2 Comments

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 的資料 (因為使用者可以修改,所以視為不安全的資料)。從檔案讀資料進來 (可能是普通的文字檔,或是 … Continue reading

Posted in Computer, Murmuring, Network, Security, WWW | Tagged , , , , , , , | 3 Comments

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 … Continue reading

Posted in Browser, Computer, IE, Murmuring, Network, Security, Software, WWW | Tagged , , , , , , , , , , , | Leave a comment