Home » Computer » Archive by category "Programming" (Page 3)

Rust 版本 Mercurial

看到「Mercurial: 964212780daf」這則 commit log,看起來 MercurialPython 換成 Rust 的計畫正在進行中:

rust: implementation of `hg`

This commit provides a mostly-working implementation of the `hg` script in Rust along with scaffolding to support Rust in the repository.

之前從朋友那邊聽到,在 F 公司用 Mercurial 用到覺得很厭世,主要是因為 repository 太大,一跑下去就會發現記憶體用量與速度都很無奈 (即使內部已經有不少工具改善速度),所以就啟動專案要換一個程式語言,直接拼最後那段的效能 XD

如果是隔壁棚的 Git... 就沒這個問題,一開始 Git 就用 C 寫,所以如果厭世的話也不太容易生出什麼進展了 XDDD

讀書時間:Spectre 的攻擊方式

上次寫了 Meltdown 攻擊的讀書心得 (參考「讀書時間:Meltdown 的攻擊方式」),結果後來中獎狂流鼻水,加上 Spectre 用的手法就更複雜,慢慢看的情況就拖到最近才看完... 這邊就以讀者看過 Meltdown 那篇心得的前提來描述 Spectre。

Spectre 的精華在於 CPU 支援 branch prediction 與 out-of-order execution,也就是 CPU 遇到 branch 時會學習怎麼跑,這個資訊提供給 out-of-order execution 就可以大幅提昇執行速度。可以參考以前在「CPU Branch Prediction 的成本...」提到的效率問題。

原理的部份可以看這段程式碼:

這類型程式碼常常出現在現代程式的各種安全檢查上:確認 x 沒問題後再實際將資料拉出來處理。而我們可以透過不斷的丟 x 值進去,讓 CPU 學到以為都是 TRUE,而在 CPU 學壞之後,突然丟進超出範圍的 x,產生 branch misprediction,但卻已經因為 out-of-order execution 而讓 CPU 執行過 y = ... 這段指令,進而導致 cache 的內容改變。

然後其中讓人最驚豔的攻擊,就是論文示範了透過瀏覽器的 JavaScript 就能打的讓人不要不要的...

圖片裡,上面這段是 JavaScript 程式碼,下面則是 Chrome V8JIT 後轉成的 assembly (這是 AT&T style):

可以從這段程式碼看到,他想要透過這段 JavaScript 取出本來無法存取到的祕密值 index,然後透過 probeTable 得知 cache 的變化。

在這樣的攻擊下,你就可以取得這個 process 裡可以看到的空間,甚至極端的 case 下有可能是 kernel space (配合 Meltdown 的條件)。

不過如果你不能跑 JavaScript 也沒關係,Spectre 的論文裡也提供各種變形方式提供攻擊。像是這樣的程式碼也可以被拿來攻擊:

if (false but mispredicts as true)
    read array1[R1]
read [R2]

其中 R1 是有帶有祕密值的 register,當 array[R1] 有 cache 時,讀 [R2] 就有機會比較快,而沒有 cache 時就會比較慢 (這是因為 memory bus 被佔用的關係),在這個情境下就能夠產生 timing attack:

Suppose register R1 contains a secret value. If the speculatively executed memory read of array1[R1] is a cache hit, then nothing will go on the memory bus and the read from [R2] will initiate quickly. If the read of array1[R1] is a cache miss, then the second read may take longer, resulting in different timing for the victim thread.

所以相同道理,利用乘法器被佔用的 timing attack 也可以產生攻擊:

if (false but mispredicts as true)
    multiply R1, R2
multiply R3, R4

在論文裡面提到相當多的方法 (甚至連 branch target buffers (BTB) 都可以拿來用),就麻煩去論文裡看了。現在用 cache 算是很有效的方式,所以攻擊手法主要都是透過 cache 在取得資訊。

Spectre 論文提到的 mitigation (workaround) 是透過 mfencelfence 強制程式碼的順序,但這表示 compiler 要針對所有的 branch 加上這段,對效能影響應該蠻明顯的:

In addition, of the three user-mode serializing instructions listed by Intel, only cpuid can be used in normal code, and it destroys many registers. The mfence and lfence (but not sfence) instructions also appear to work, with the added benefit that they do not destroy register contents. Their behavior with respect to speculative execution is not defined, however, so they may not work in all CPUs or system configurations.

Google 推出的 Retpoline 則是想要避免這個問題。Google 在「Retpoline: a software construct for preventing branch-target-injection」這邊詳細說明了 Retpoline 的原理與方法,採取的方向是控制 speculative execution:

However, we may manipulate its generation to control speculative execution while modifying the visible, on-stack value to direct how the branch is actually retired.

這個方式是抽換掉 jmpcall 兩個指令,以 *%r11 為例,他將 jmp *%r11call *%r11 改成 jmp retpoline_r11_trampolinecall retpoline_r11_trampoline (這邊的 jmp 指的是所有 jump 系列的指令,像是 jz 之類的):

retpoline_r11_trampoline:
  call set_up_target;
capture_spec:        
  pause;
  jmp capture_spec;
set_up_target:
  mov %r11, (%rsp); 
  ret;

藉由抽換 %rsp 內容跳回正確位置,然後也利用這樣的程式結構控制 CPU 的 speculative execution。

而在效能損失上,已經有測試報告出來了。其實並沒有像 Google 說的那麼無痛,還是會因為應用差異而有不同等級的效能損失... 可以看到有些應用其實還是很痛:「Benchmarking Linux With The Retpoline Patches For Spectre」。

下半年新出的 CPU 應該會考慮這些問題了吧,不過不知道怎麼提供解法 @_@

純 CSS 的追蹤技巧

Hacker News 上看到的 PoC,程式碼就放在 GitHubjbtronics/CrookedStyleSheets 上。能追蹤的細節當然比較少,不過透過 CSS 還是有不少資訊可以蒐集。

像是連結被觸發時:

#link2:active::after {
    content: url("track.php?action=link2_clicked");
}

瀏覽器的資訊:

@supports (-webkit-appearance:none) {
    #chrome_detect::after {
        content: url("track.php?action=browser_chrome");
    }
}

字型的 fingerprint:

/** Font detection **/@font-face {
    font-family: Font1;
    src: url("track.php?action=font1");
}

#font_detection1 {
    font-family: Calibri, Font1;
}

捲頁行為:

@keyframes pulsate {
    0% {background-image: url("track.php?duration=00")}
    20% {background-image: url("track.php?duration=20")}
    40% {background-image: url("track.php?duration=40")}
    60% {background-image: url("track.php?duration=60")}
    80% {background-image: url("track.php?duration=80")}
    100% {background-image: url("track.php?duration=100")}
}

算是提供了不少除了 <noscript></noscript> 外的手段,不過一般網站要引入這些技巧需要改不少東西就是了... (或是需要透過 server side plugin 的修改進行追蹤)

JVM 的各種調校

看到「JVM Anatomy Park」這篇,作者是 Red HatOpenJDK 團隊的人,寫了二十則與 JVM 效能相關的主題,裡面提到每則大約花五到十分鐘可以看完,不過我覺得應該會再久一點 (需要翻資料交叉查)。

除了網頁版外,也提供 EPUB、MOBI 與 PDF 格式可以下載。

都是講效能相關的,從不同角度看。以第一個 Lock Coarsening and Loops 來說,已知這段程式碼:

synchronized (obj) {
  // statements 1
}
synchronized (obj) {
  // statements 2
}

會被轉換成這樣等效的程式碼:

synchronized (obj) {
  // statements 1
  // statements 2
}

作者就問了,那這樣的話,這段:

for (...) {
  synchronized (obj) {
    // something
  }
}

會不會轉成這段呢:

synchronized (this) {
  for (...) {
     // something
  }
}

答案是不會,但可以橋:

While lock coarsening does not work on the entire loop, another loop optimization — loop unrolling — sets up the stage for the regular lock coarsening, once the intermediate representation starts to look as if there are N adjacent lock-unlock sequences. This reaps the performance benefits, and helps to limit the scope of coarsening, to avoid over-coarsening over fat loops.

就大概是這樣的主題 XD 每天看個一兩篇慢慢消化還不錯...

Microsoft 的 TTD 與 Mozilla 的 RR

也是個在瀏覽器 tab 上放了一陣子的連結... 先前看到 MicrosoftTime Travel Debugger (TTD),可以錄下程式執行的狀態,然後回放與搜尋:「Thoughts On Microsoft's Time-Travel Debugger」,另外有 CppCon 2017 上的影片,在 YouTube 上:

另外 Mozilla 也有類似的工具,叫做 rr (在影片開頭就有人問類似的問題 XD),程式碼在 GitHub 上:「mozilla/rr」。

而 TTD 與 rr 兩者最大的差異當然是平台支援的情況:

The most important and obvious difference between TTD and rr is that TTD is for Windows and rr is for Linux (though a few crazy people have had success debugging Windows applications in Wine under rr).

但另外一個也很重要的差異是 TTD 支援完整的 multi-threading,這對於現代的程式來說還蠻常見的:

TTD supports recording of multiple threads in parallel, while rr is limited to a single core.

當然,更完整的錄影也是要付出效能代價的:

On the other hand, per-thread recording overhead seems to be much higher in TTD than in rr. It's hard to make a direct comparison, but a simple "start Firefox, display mozilla.org, shut down" test run on similar hardware takes about 250 seconds under TTD and 26 seconds under rr.

不過有需要的時候應該會很方便?工具總是愈多愈好...

也是拿來掃 PHP 程式碼的 PHPStan...

PHPStan 也是 PHP 的靜態分析工具,官方給的 slogan 是「PHP Static Analysis Tool - discover bugs in your code without running it!」。然後官方給了一個 GIF,直接看就大概知道在幹什麼了:

Phan 類似,也是要 PHP 7+ 才能跑,不過實際測試發現不像 Phan 需要 php-ast

PHPStan requires PHP ^gt;= 7.0. You have to run it in environment with PHP 7.x but the actual code does not have to use PHP 7.x features. (Code written for PHP 5.6 and earlier can run on 7.x mostly unmodified.)

PHPStan works best with modern object-oriented code. The more strongly-typed your code is, the more information you give PHPStan to work with.

Properly annotated and typehinted code (class properties, function and method arguments, return types) helps not only static analysis tools but also other people that work with the code to understand it.

拿上一篇「用 Phan 檢查 PHP 程式的正確性」的例子測試,也可以抓到類似的問題:

vendor/bin/phpstan analyse -l 7 src/
 1/1 [▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓] 100%

 ------ --------------------------------------------------------------
  Line   src/Foo.php
 ------ --------------------------------------------------------------
  13     Method Gslin\Foo::g() should return string but returns null.
 ------ --------------------------------------------------------------


 [ERROR] Found 1 error

這樣總算把積壓在 tab 上關於 PHP 工具都寫完了,之後要用才有地方可以翻... XD

用 Phan 檢查 PHP 程式的正確性

Phan 這套也是拿來檢查 PHP 程式用的,也是儘量避免丟出 false alarm。不過 Phan 只能用在 PHP 7+ 環境,原因是使用 php-ast,另外有一些額外建議要裝的套件:

This version (branch) of Phan depends on PHP 7.1.x with the php-ast extension (0.1.5 or newer, uses AST version 50) and supports PHP version 7.1+ syntax. Installation instructions for php-ast can be found here. For PHP 7.0.x use the 0.8 branch. Having PHP's pcntl extension installed is strongly recommended (not available on Windows), in order to support using parallel processes for analysis (or to support daemon mode).

最新版還只能跑在 PHP 7.2 上面,用的時候要注意一下 XD (我在測試時,require-dev 指定 0.11.0,結果被說只有 PHP 7.1 不符合 dependency,後來放 * 讓他去抓適合的版本)

像是這樣的程式碼:

class Foo
{
    /**
     * @param string $p
     * @return string
     */    function g($p) {
        if (!$p) {
            return null;
        }
        return $p;
    }
}

就會產生出對應的警告訊息:

src/Foo.php:13 PhanTypeMismatchReturn Returning type null but g() is declared to return string

也是掛進 CI 裡面的好東西...

Archives