vector

Vector embedding

最近累積起來的東西，都跟 vector embedding 有關，第二篇甚至有提到透過 embedding 切入可以找到不少 LLM 有趣的使用方式：

自己編 llama.cpp 的時候會產生出 embeeding 這隻程式，就可以測試把文字轉成 vector 的功能，接著就可以套用高維空間的數學運算了，像是最常被提到的是利用兩個 vector 的夾角來判斷相似度。

因為是對一堆 vector 處理，就不太需要去管輸出格式的問題 (像是 ChatGPT 會自由輸出任何東西)，對程式開發上會方便不少...

Vector clock 的發明時間軸

一樣是在 Hacker News 上看到「Who invented vector clocks? (decomposition.al)」這篇文章，在找出誰發明了 vector clock，原文在「Who invented vector clocks?」。

主要有兩個不同的時間點，一個是 vector clock 概念的提出，另外一個是第一次用到 vector 這個詞。

這篇讓我覺得有趣的地方是，vector clock 本來就是在處理分散式系統裡面事件順序的問題，而這篇文章則是在找出真實世界裡面這些發明的先後順序，而且也牽扯到了各種 citation (類比到分散式系統裡事件的 dependency)。

分散式系統的 clock

前幾天在 Hacker News 上看到「Clocks and Causality – Ordering Events in Distributed Systems (2022) (exhypothesi.com)」這篇，講分散式系統上 clock 的設計，作者也有跑出來在 Hacker News 上面跟大家聊一下 (帳號是 thoughtlede)，原文在「Clocks and Causality - Ordering Events in Distributed Systems」這邊。

文章裡面主要講空間是 $O(1)$ 的 Lamport timestamp 與空間是 $O(n)$ 的 Vector clock (這邊的 $n$ 相對於節點數量)，以及這兩個對應的擴充版本：

作者會整理這些資料的原因是因為在研究 CRDT 的時候看到演算法中常常會需要處理分散式系統裡面事件的順序，所以花了一些時間整理常見的方式：

Author here. Pleasantly surprised to see the article here.

Some context behind the article. I studied CRDTs for a few months, and noticed that different CRDT designs use logical clocks in different and clever ways. And I haven't seen anyone narrate all those ways of use in one article. My attempt with this article was to dredge up those flavors of logical clocks into one article and give them names for future reference.

(To respond to a couple of other comments, I ignored atomic (and gps-based) clocks in this discussion, as indicated in my footnote 3).

我記得還有一個 Interval Tree Clocks 可以參考 (在「Interval Tree Clocks」這邊講的比較清楚)，是針對節點的動態增刪而改善的演算法，但不確定有什麼比較有名的系統有用。

大多數應該都是用 Vector clock，畢竟是在 2007 年的「Dynamo: Amazon’s Highly Available Key-value Store」被發揚光大，而且也算是還不錯的演算法？

Log4j2 的 RCE

昨天爆出來 Log4j2 的 RCE，看了一下 pattern，只要是 Java stack 應該都很容易中獎：「Log4Shell: RCE 0-day exploit found in log4j2, a popular Java logging package」，Hacker News 上對應的討論在「Log4j RCE Found (lunasec.io)」這邊可以看。

LunaSec 宣稱這是 0-day RCE，不過 Log4j2 的修正版本 2.15.0 在 2021/12/06 出了，而 exploit 被丟出來是 2021/12/09，但不確定在這之前是不是已經有 exploit 在 internet 上飛來飛去了...

丟出來的 exploit sample (CVE-2021-44228-Apache-Log4j-Rce) 是用 LDAP 來打，雖然大多數的 Java 版本不受影響，但還是有其他的面可以攻擊，所以整體上還是很容易打穿，該升級的還是得趕快升級：

Updates (3 hours after posting): According to this blog post (see translation), JDK versions greater than 6u211, 7u201, 8u191, and 11.0.1 are not affected by the LDAP attack vector. In these versions com.sun.jndi.ldap.object.trustURLCodebase is set to false meaning JNDI cannot load remote code using LDAP.

However, there are other attack vectors targeting this vulnerability which can result in RCE. An attacker could still leverage existing code on the server to execute a payload. An attack targeting the class org.apache.naming.factory.BeanFactory, present on Apache Tomcat servers, is discussed in this blog post.

週末苦命時間...

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」這篇，把五年多前的記錄交叉拉出來看... 這個算式算是給了大家基本的想法，透過公式來解釋文字的意義：

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

GitHub 在計畫讓使用者可以用自然語言搜尋...

GitHub 計畫讓使用者可以用自然語言搜尋，目前還在測試階段：「Towards Natural Language Semantic Code Search」。

看起來是透過不同的 encoder，轉到 vector space 後查詢：

在文章裡是拿「ping REST api and return results」當作範例：

之後找範例與用法就不用只在 StackOverflow 上找了... (咦)

在 HTML 內嵌 JSON object 時要注意的事情...

有時候我們會因為效能問題，在 HTML 內嵌入 JSON object，而不是再多一個 HTTP request 取得。

但「嵌入」的行為如果沒有處理好，就產生非常多 XSS attack vector 可以玩。

首先最常犯的錯誤是使用錯誤的 escape function：

<!DOCTYPE HTML>
<html>
<body>
<script>
var a = "<?= addslashes($str) ?>";
</script>
</body>
</html>

這樣可以用 </script><script>alert(1);// 攻擊 $str。因為 addslashes() 並不會過濾到這個字串，而產生這樣的 HTML：

<!DOCTYPE HTML>
<html>
<body>
<script>
var a = "</script><script>alert(1);//";
</script>
</body>
</html>

而這個字串會造成 DOM parser 解讀上產生不是我們預期的行為：

可以看到在字串裡面的 </script> 被拆開了。

這是因為瀏覽器會先拆解產生 DOM tree，再把 <script></script> 內的程式碼交給 JavaScript engine 處理。所以在一開始產生 DOM tree 的時候，是看不懂 JavaScript 程式邏輯的...

正確的方法是用 json_encode() 處理，因為 PHP 的 json_encode() 預設會把 / (slash) 變成 \/ (這是 JSON spec 裡合法的轉換)：

<!DOCTYPE HTML>
<html>
<body>
<script>
var a = <?= json_encode($str) ?>;
</script>
</body>
</html>

這會產生出：

<!DOCTYPE HTML>
<html>
<body>
<script>
var a = "<\/script><script>alert(1);//";
</script>
</body>
</html>

但上面這段 HTML 與 PHP code 仍然有問題，如果 $str 是 <!--<script 時，你會發現 DOM 又爛掉了：

<!DOCTYPE HTML>
<html>
<body>
<script>
var a = "<!--<script>";
</script>
</body>
</html>

而 escape.alf.nu 的 Level 15 就是利用這個問題，再加上其他的漏洞而完成 XSS 攻擊。

為了這個問題去 StackOverflow 上問：「Why does <!--<script> cause a DOM tree break on the browser?」，才又發現上面這段 code 並不是合法的 HTML5 (先不管 head & title 的部份，補上後仍然不是合法的 HTML5)。

原因在於 DOM parser 對 <script></script> 的特殊處理：「4.3.1.2 Restrictions for contents of script elements」。(話說這段 ABNF 差點讓我翻桌...)

解法是在 <script></script> 的開頭與結尾加上 HTML 註解：(這剛好是 HTML 4.01 建議的方法)

<!DOCTYPE HTML>
<html>
<body>
<script>
<!--
var a = "<!--<script>";
-->
</script>
</body>
</html>

那段 ABNF 的目的是希望可以盡可能往後找到 --> 與 </script> 結尾的地方。

當然你也可以用 json_encode() 的 JSON_HEX_TAG 把 < 與 > 硬轉成 \u003c 與 \u003e 避開這個問題，但這使得呼叫 json_encode() 時要多一個參數 (而非預設參數)，用起來比較卡...

這個問題會變得這麼討厭，是因為 DOM parser 與 JavaScript 語法之間有各自的處理方式，然後又有些 pattern 是之前的 spec 遺留下來的包袱 (像是 HTML 4.01 在「18.3.2 Hiding script data from user agents」裡有提到用  包裝 <script></script>)，變成在設計 HTML5 時都要考慮進去相容...

之前會習慣用  包裝 <script></script> 倒不是這個原因，而是因為不這樣做的話，jQuery 在 IE 使用 html() 時遇到有 <script></script> 的字串會爛掉，所以後來寫的時候變成習慣了...

反而因為這個習慣而避開了這個問題...

超難搞啊...