Google 與 Cloudflare 測試 Post-Quantum 演算法的成果

這幾年量子電腦的進展不斷有突破,雖然到對於攻擊現有的密碼學看起來還有一段時間,但總是得先開始研究對量子電腦有抵抗性的演算法...

其中 Google Chrome 的團隊與 Cloudflare 的團隊手上都有夠大的產品,兩個團隊合作測試的結果在學界與業界都還蠻重視的:「Real-world measurements of structured-lattices and supersingular isogenies in TLS」、「The TLS Post-Quantum Experiment」。

Google Chrome 這邊是使用了 Canary 與 Dev 兩個 channel,有控制組與兩個新的演算法:

Google Chrome installs, on Dev and Canary channels, and on all platforms except iOS, were randomly assigned to one of three groups: control (30%), CECPQ2 (30%), or CECPQ2b (30%). (A random ten percent of installs did not take part in the experiment so the numbers only add up to 90.)

這兩個演算法有優點也有缺點。一個是 key 比較小,但運算起來比較慢 (SIKE,CECPQ2b);另外一個是 key 比較大,但是運算比較快 (HRSS,CECPQ2):

For our experiment, we chose two algorithms: isogeny-based SIKE and lattice-based HRSS. The former has short key sizes (~330 bytes) but has a high computational cost; the latter has larger key sizes (~1100 bytes), but is a few orders of magnitude faster.

We enabled both CECPQ2 (HRSS + X25519) and CECPQ2b (SIKE/p434 + X25519) key-agreement algorithms on all TLS-terminating edge servers.

感覺還是會繼續嘗試,因為這兩個演算法的缺點都還是有點致命...

Leslie Lamport 講 Paxos 與 TLA+

在「The Paxos Algorithm or How to Win a Turing Award」這邊看到 Leslie Lamport 在今年七月時親自講解 Paxos 這個經典演算法的錄影。另外一個有提到的主題是講形式規範的 TLA+,也是他的力作...

Leslie Lamport 是 2013 年的 Turing Award 得主,除了上面提到的事蹟外,LaTeX 也是他弄出來的東西,軟體名稱開頭的 La 就是他本人...

花些時間聽看看還不錯 (去聽看看他怎麼描述),不過現在的新軟體比較常實做 Raft,Paxos 比較少人選擇了...

Facebook 修正錯字的新演算法

先前 Facebook 已經先發表過 fastText 了,在這個月的月初又發表了另外一個演算法 Misspelling Oblivious Embeddings (MOE),是搭著本來的 fastText 而得到的改善:「A new model for word embeddings that are resilient to misspellings」。

Facebook 的說明提到在 user-generated text 的內容上,MOE 的效果比 fastText 好:

We checked the effectiveness of this approach considering different intrinsic and extrinsic tasks, and found that MOE outperforms fastText for user-generated text.

論文發表在 arXiv 上:「Misspelling Oblivious Word Embeddings」。

依照介紹,fastText 的重點在於 semantic loss,而 MOE 則多了 spell correction loss:

The loss function of fastText aims to more closely embed words that occur in the same context. We call this semantic loss. In addition to the semantic loss, MOE also considers an additional supervisedloss that we call spell correction loss. The spell correction loss aims to embed misspellings close to their correct versions by minimizing the weighted sum of semantic loss and spell correction loss.

不過目前 GitHub 上的 facebookresearch/moe 只有放 dataset,沒有 open source 出來讓人直接用,可能得自己刻...

用 Machine Learning 改善 Streaming 品質的服務與論文

Hacker News 上看到「Puffer」這個服務,裡面利用了 machine learning algorithm 動態調整 bitrate,以提昇傳輸品質。

測試得到的數據後來被整理起來一起放進論文:「Continual learning improves Internet video streaming」。

在開頭介紹了 Fugu 這個演算法:

We describe Fugu, a continual learning algorithm for bitrate selection in streaming video.

而 Puffer 就是實驗網站:

We evaluate Fugu with Puffer, a public website we built that streams live TV using Fugu and existing algorithms. Over a nine-day period in January 2019, Puffer streamed 8,131 hours of video to 3,719 unique users.

這個站台提供了許多真實的頻道進行測試:

Stream live TV in your browser. There's no charge. You can watch U.S. TV stations affiliated with the NBC, CBS, ABC, PBS, FOX, and Univision networks.

可以看到 Fugu 的結果很好,比起其他提出的方案是全面性的改善:

這邊是用 WebSocket 測試,並且配合了不同的 TCP congestion algorithm,沒有太考慮額外的計算成本...

Cloudflare 因為 Regular Expression 炸掉的問題

先前 Cloudflare 就有先說明七月二日的 outage 是因為 regular expression 造成的 (ReDoS),不過昨天發的文章更完整了,導致爆炸的 regular expression 都給出來了:「Details of the Cloudflare outage on July 2, 2019」。

ReDoS 不算是新的問題,但卻是不太好避免的問題,因為需要有經驗的工程師 (中過獎的工程師) 才比較容易知道哪些 regular expression 是有問題的... 另外就是有花時間研究 regular expression 演算法的工程師也比較容易避開。

也因次,ReDoS 算是這十年來大家在還的債,各家 framework 都因為這個問題改寫了不少 regular expression。

這次的重點在這串式子導致了 ReDoS:

(?:(?:\"|'|\]|\}|\\|\d|(?:nan|infinity|true|false|null|undefined|symbol|math)|\`|\-|\+)+[)]*;?((?:\s|-|~|!|{}|\|\||\+)*.*(?:.*=.*)))

通常容易中獎的地方就是無限制字元與 * & + 連發的地方,後面這塊 )*.*(?:.*=.*))) 看起來就不太妙,果然在後面的分析也有提到:

The critical part is .*(?:.*=.*).

以前應該是在 Formal language 裡學到的,在課堂裡面其實會學到不少業界常用工具的基礎理論...

JavaScript 的 sort 變成 stable

看到「Stable Array.prototype.sort」這篇在講 JavaScript 規格書裡的 sort...

本來 JavaScript 的規格書裡,各種 sort 都沒有保證 stable,而在「[Normative] Make Array.prototype.sort stable #1340」與「[Normative] Make %TypedArray%.prototype.sort stable #1433」這兩個地方則有了變化,提案在規格裡加入 stable 的要求,可以減少開發者因為不知道 unstable 而造成的問題...

Firefox 則是很久前就決定使用 Merge sort 了 (看了一下,當時還在從 Firebird 轉換名稱到 Firefox 的時期):「Array.sort isn't a stable sort (switch to MergeSort)」。

另外這篇也剛好提到了 V8 使用 Timsort 當作 stable sorting algorithm,之前就有看到但發現沒在 blog 上提過...

Timsort 是 1993 年發明出來的演算法,與 Merge sort 的情況類似,除了 stable 外,還可以保證最差的情境下的時間複雜度是 O(n*log(n))

Timsort is a hybrid stable sorting algorithm, derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data.

這個演算法的重點是善用已經排好的子序列,藉此降低記憶體操作次數而提昇效能,符合真實環境裡常見到的資料:

The algorithm finds subsequences of the data that are already ordered, and uses that knowledge to sort the remainder more efficiently.

除了 V8 採用這個演算法以外,其他常見的包括了 PythonAndroid 上的 Java SE:

Timsort has been Python's standard sorting algorithm since version 2.3. It is also used to sort arrays of non-primitive type in Java SE 7, on the Android platform, in GNU Octave, and Google Chrome.

iOS 13 與 macOS 10.15 對憑證的限制

Slack 上看到同事丟出來的,關於之後要推出的 iOS 13 與 macOS 10.15 會對憑證限制的項目:「Requirements for trusted certificates in iOS 13 and macOS 10.15」。

主要是把不安全的演算法淘汰掉 (RSA 小於 2048 bits,以及 SHA-1 類的 hash algorithm),這兩個部份相關的新聞應該不少,沒有什麼太大問題:

TLS server certificates and issuing CAs using RSA keys must use key sizes greater than or equal to 2048 bits. Certificates using RSA key sizes smaller than 2048 bits are no longer trusted for TLS.

TLS server certificates and issuing CAs must use a hash algorithm from the SHA-2 family in the signature algorithm. SHA-1 signed certificates are no longer trusted for TLS.

然後是要求憑證使用 SAN (Subject Alternative Name),舊的標準 CN (CommonName) 將不會再被信任。

如果是公開簽發的憑證應該都沒問題 (像是 Let's Encrypt,或是花錢買的那些),主要的問題應該會出現在自己建立的憑證,網路上蠻多舊資料還是產生 CN...

TLS server certificates must present the DNS name of the server in the Subject Alternative Name extension of the certificate. DNS names in the CommonName of a certificate are no longer trusted.

另外是 2019/7/1 之後發出的憑證,有額外兩個規範要注意,第一個是強制要透過 EKU 指定 id-kp-serverAuth,這是出自 RFC 5280

   id-kp-serverAuth             OBJECT IDENTIFIER ::= { id-kp 1 }
   -- TLS WWW server authentication
   -- Key usage bits that may be consistent: digitalSignature,
   -- keyEncipherment or keyAgreement

TLS server certificates must contain an ExtendedKeyUsage (EKU) extension containing the id-kp-serverAuth OID.

再來是時間的限制,接下來的憑證最長只認得 825 天 (大約 27 個月多一些),以前都惡搞 -days 3650,現在得兩年簽一次了:

TLS server certificates must have a validity period of 825 days or fewer (as expressed in the NotBefore and NotAfter fields of the certificate).

整體看起來主要是影響自己簽的部份...

GrabFood 用定位資料修正餐廳的資訊

Grab 的「How we harnessed the wisdom of crowds to improve restaurant location accuracy」這篇是他們的 data team 整理出來,如何使用既有的資料快速的修正餐廳資訊。裡面提到的方法不需要用到 machine learning,光是一些簡單的統計算法就可以快速修正現有的架構。

這些資訊其實是透過司機用的 driver app 蒐集來的,在 driver app 上有大量的資訊傳回伺服器 (像是定時回報的 GPS 位置,以及取餐狀態),而這些司機因為地緣關係,腦袋裡的資訊比地圖會準不少:

One of the biggest advantages we have is the huge driver-partner fleet we have on the ground in cities across Southeast Asia. They know the roads and cities like the back of their hand, and they are resourceful. As a result, they are often able to find the restaurants and complete orders even if the location was registered incorrectly.

所以透過這些資訊他們就可以反過來改善地圖資料,像是透過司機按下「取餐」的按鈕的地點與待的時間,就可以估算餐聽可能的位置,然後拿這個資訊比對地圖上的資料,就很容易發現搬家但是地圖上沒更新的情況:

Fraction of the orders where the pick-up location was not “at” the restaurant: This fraction indicates the number of orders with a pick-up location not near the registered restaurant location (with near being defined both spatially and temporally as above). A higher value indicates a higher likelihood of the restaurant not being in the registered location subject to order volume

Median distance between registered and estimated locations: This factor is used to rank restaurants by a notion of “importance”. A restaurant which is just outside the fixed radius from above can be addressed after another restaurant which is a kilometer away.

另外也有不少其他的改善 (像是必須在離餐聽某個距離內才能點「取餐」,這個「距離」會因為餐聽可能在室內商場而需要的調整),整個成果就會反應在訂單的取消率大幅下降:

整體看起來是系統產生清單後讓人工後續處理 (像是打電話去店家問?),但這個方式所提供的清單準確度應該很高 (因為司機不會沒事跟自己時間過不去,跑到奇怪地方按下取餐),用這些資料跑簡單的演算法就能夠快速修正不少問題...

Word2Vec:透過向量猜測其他詞彙的意思

2013 年時在「Automatic Translation Without Dictionaries」這邊看到關於機器翻譯時的自我學習方式,裡面提到了「How Google Converted Language Translation Into a Problem of Vector Space Mathematics」這篇報導,而裡面提到的論文則是 Google 發表在 arXiv 上的「Exploiting Similarities among Languages for Machine Translation」這篇。

最近看到「The Illustrated Word2vec」這篇,把五年多前的記錄交叉拉出來看... 這個算式算是給了大家基本的想法,透過公式來解釋文字的意義:

拉出這樣的關係後,就有機會學習新的詞彙... 進而用在其他語言的翻譯上。

用 NN 演算法重製 Full HD 版的 Star Trek: DS9

看到「Remastering Star Trek: Deep Space Nine With Machine Learning」這篇,裡面用了類神經網路演算法,將本來只有 480p (SD) 的 Star Trek: DS9 升到 1080p (Full HD) 的版本,而且看起來效果還不錯...

意外的看到有人拿 Star Trek 的材料來玩... 依照作者的說明,DS9 一直沒有 Full HD 版的其中一個原因反而是因為「數位化」了。使用類比膠卷的母帶可以透過更高規格的重新掃描而得到高畫質版本,但 DS9 的母帶似乎已經是數位版了,所以反而造成無法透過重新掃描的方式取得 Full HD 版本:

While you can rescan analog film at a higher resolution, video is digital and can't be rescanned. This makes it much costlier to remaster this TV show, which is one of the reasons why it hasn't happened.

現有的 upscale 技術主要都還是以圖片為主,所以作者本來以為對於動態畫面的處理會遇到問題,但蠻意外的超出預期,從影片可以看出來:

看起來之後的 remaster 版本有可能可以靠這個方法先做初步,然後再讓人進去修?