Shadow Stack を使った Stack Buffer Overflow 検知機構の実装

はじめに

FFRIリサーチエンジニアの中川です。今回は RISC-V の実装の 1 つ Rocket に Shadow Stack を実装し、それを使い Stack Buffer Overflow を検知する機構を作成しましたので、それについて紹介します。 なお、今回の実装は論文 [1] を参考に行っています。

まず、Rocket と Shadow Stack について紹介し、Rocket の拡張方法の一つ Rocket Custom Coprocessor (RoCC) について説明します。その後、RoCC を使った Shadow Stack の実装について、ソースコードと一緒に紹介していきます。

Rocket について

Rocket はカリフォルニア大学バークレイ校によって開発されている RISC-V の実装の 1 つです。RISC-V の仕様のほぼすべてが実装されているので、RISC-V を簡単に試したい場合によく利用されます。

特徴として

• ベーシックな 5 段パイプライン
• マシンモード・スーパーバイザーモード
• FPU 演算器

を備えているところが上げられます。RISC-V の実機評価ボードである HiFive1 や HiFive Unleashed には Rocket をベースに設計されたマイクロコントローラーが使われています。

また、設計に使われている言語にも特徴があります。ハードウェア記述言語として Verilog や VHDL が広く使われているかと思いますが、Rocket の設計には Chisel という言語が使われています。これは Scala の内部 DSL となっており、Scala の言語機能がそのままハードウェア設計において使えるようになっています。Scala での抽象度の高い記述が、ハードウェア記述言語においても利用できるのは大きなメリットと言えます。

Shadow Stack について

Shadow Stack は Stack Buffer Overflow によるリターンアドレスの破壊を検知するために利用される専用のスタック領域です。システムのコールスタックとは別に用意され、関数コール時のリターンアドレスのみが格納されています。

この Shadow Stack を使った、Stack Buffer Overflow の検知は次のような流れで実行されます。

1. 関数コール時に、システムのコールスタックと Shadow Stack の両方にリターンアドレスを push
2. 関数から戻ってくる直前に、システムのコールスタックから取り出したリターンアドレスと、Shadow Stack から取り出した値を比較
3. Stack Buffer Overflow によりシステムのコールスタックのリターンアドレスの値が書き換えられている場合、Shadow Stack とシステムのコールスタックから取り出されたリターンアドレスの値が異なるので、その場合にはプログラムの実行を停止 (同じ場合には、プログラムの実行を継続)

Stack Canary を使った検知の場合、Stack Canary のリーク、あるいは Bruteforce による値の特定により、回避させる可能性があります。Shadow Stack を使った検知の場合、Shadow Stack の内容が改ざんされない限り、回避されることはありません。

ちなみに、2016 年に Intel は Shadow Stack による脆弱性防御機構のハードウェアサポートを発表[2]するなど、採用事例も出始めているようです。

RoCC について

次に、RoCC を使った Rocket の拡張方法について説明しますが、その前に RISC-V にはカスタム命令を設定できるオペコードがあることをまず説明しておかなければなりません。

以下の表 1 は RISC-V Instruction Set Manual Volume 1 の Table 25.1 から転載したもので、各オペコードの値がどういった種類の命令に対応しているのかを示します。

表1 RISC-V の base opcode map (RISC-V Instruction Set Manual Volume 1 の Table 25.1 より転載)

表の見方について簡単に説明すると、column が命令コードの下位 2--4 ビット、row が命令コードの下位 5--6 に対応しています。例えば、下位 2--6 ビットが 00001 という命令があった場合、この表の column が 001、row が 00 に当たる箇所を見ればよく、LOAD-FP (つまり、メモリにある値を浮動小数点レジスタに読み込む命令) 命令が定義されているオペコードだとわかります。fld 命令のオペコード (命令の下位 0--6 ビット) を確認してみると、 0000111 となっており、下位 2--6 ビットは確かに 00001 となっていることがわかります。

この表をよく見てみると斜体で custom0 custom1 custom2 custom3 と書いている欄があることがわかります。これは CPU 設計者が独自命令を定義できるよう予約されたフィールドとなっています。カスタマイズ可能なように ISA をデザインしている RISC-V だからこそ存在するフィールドです。

RoCC はこの custom0--custom3 の命令実行時に、コプロセッサ (FPGAや機械学習のアクセラレーターなど) を実行できるようにするための仕組みになります。Rocket からコプロセッサを動かし、コプロセッサ内での計算結果を Rocket のレジスタに直接書き戻すなどが可能です。

RoCC ではインターフェースが仕様によって定められており、この仕様を満たせば任意のコプロセッサをつなぐことが可能になっています。

今回はこのコプロセッサとして FPGA を使い、Shadow Stack の内容はこの FPGA が管理する構成を想定しています (図 1 を参照。ただ、検証自体はシミュレーションで行っています。)。CPU のメモリから物理的に離れたところで Shadow Stack を管理しているため、Shadow Stack が保持しているリターンアドレスの値がより改ざんされにくい構成になっています。

図 1 Shadow Stack を実装するに想定したハードウェア構成。Rocket RISC-V CPU に加え、コプロセッサとなる FPGA が付いた構成となっている。

RoCC を使った Rocket のカスタマイズ方法

RoCC を使った Rocket Chip の具体的なカスタマイズ方法について見ていきましょう。

riscv-tools とクロスコンパイラがインストールされていることを前提とします。インストール手順についてはブログ記事を参考にしてください。

最初に、custom 命令を使えるようにするために、riscv-toolsに含まれるriscv-pkを書き換えます。riscv-pk/machine/minit.c ファイルを開き、CSR レジスタの XS fields を 1 に設定します。

static void mstatus_init()
{
  // Enable FPU
  if (supports_extension('D') || supports_extension('F'))
    write_csr(mstatus, MSTATUS_FS);

  // 以下の二行を追加
  if (supports_extension('X'))
    set_csr(mstatus, (MSTATUS_XS & (MSTATUS_XS >> 1)));

  // Enable user/supervisor use of perf counters
  if (supports_extension('S'))
    write_csr(scounteren, -1);
  write_csr(mcounteren, -1);

この書き換えを実行した後、riscv-pk をコンパイルし直し、インストールし直します。

$ cd riscv-tools
$ ./build.sh

次に、Rocket のソースコードを書き換えていきます。デフォルトで RoCC を使ったカスタマイズ用のテンプレートが用意されているので、そちらを修正し、独自の処理に書き換えていきます。

書き換える必要のあるファイルは以下の２つです。

• src/main/scala/subsystem/Configs.scala
• src/main/scala/tile/LazyRoCC.scala

LazyRoCC.scala にはコプロセッサで実行する処理を書き、Config.scala にはどの実装を用いるのかの設定を記述します。

Config.scala を見てみましょう。custom0--custom3 命令ごとに実行する処理が登録されています。

class WithRoccExample extends Config((site, here, up) => {
  case BuildRoCC => List(
    (p: Parameters) => { // custom0 命令を実行したときに呼び出されるモジュールを設定
        val accumulator = LazyModule(new AccumulatorExample(OpcodeSet.custom0, n = 4)(p))
        accumulator
    },
    (p: Parameters) => { // custom1 命令を実行したときに呼び出されるモジュールを設定 (以下同様)
        val translator = LazyModule(new TranslatorExample(OpcodeSet.custom1)(p))
        translator
    },
    (p: Parameters) => {
        val counter = LazyModule(new CharacterCountExample(OpcodeSet.custom2)(p))
        counter
    },
    (p: Parameters) => {
      val blackbox = LazyModule(new BlackBoxExample(OpcodeSet.custom3, "RoccBlackBox")(p))
      blackbox
    })
})

今回は AccumulatorExample となっている部分を書き換え、Shadow Stack へ push/pop 命令が実行できるよう書き換えていきます。

RoCC を使った Shadow Stack の実装

新規に追加する命令の仕様

今回新規に 2 つの命令を定義します。

• sspush rs1: rs1 の値を Shadow Stack に push
• sspop rd: Shadow Stack の top に積まれた値を rd に pop

sspush は関数のプロローグで呼び出し、リターンアドレスの値を Shadow Stack に push します。sspop は関数のエピローグで呼び出し、取り出した Shadow Stack の値は t0 レジスタに格納、システムのコールスタックから取り出されたリターンアドレスと比較を行い、Buffer Overflow の有無を検知します。

実装

では、早速 Shadow Stack を実装していきましょう。

まずモジュール名を AccumulatorExample から ShadowStackExample にすべて書き換えてしまいます。

次に src/main/scala/tile/LazyRoCC.scala のモジュールに Stack を実装していきます。最初に必要なメモリ、スタックトップのアドレスの値を保持するレジスタの 2 つを、ハードウェアモジュールとして宣言します。

class ShadowStackExampleModuleImp(outer: ShadowStackExample)(implicit p: Parameters) extends LazyRoCCModuleImp(outer)
    with HasCoreParameters {
  val regfile = Mem(outer.n, UInt(width = xLen)) // return addressの値を保持するShadow Stack領域
  val busy = Reg(init = Vec.fill(outer.n){Bool(false)})

  val cmd = Queue(io.cmd)
  val funct = cmd.bits.inst.funct
  val addr = RegInit(0.U(log2Up(outer.n).W)) // スタックのトップアドレスを保存するレジスタ

どのコマンドが実行されたのかを判定する部分を追加します。 sspush と sspop 命令とで funct フィールドの値を変えているので (sspush の場合には 0、sspop の場合には 1)、そこから判定します。

  val cmd = Queue(io.cmd)
  val funct = cmd.bits.inst.funct
  val addr = RegInit(0.U(log2Up(outer.n).W))
  val doPush = funct === UInt(0) // funct7が1の場合にはsspush命令を実行
  val doPop = funct === UInt(1)  // funct7が0の場合にはsspop命令を実行
  val memRespTag = io.mem.resp.bits.tag(log2Up(outer.n)-1,0)

Shadow Stack に push/pop する処理を実装していきます。

  // datapath
  val output = Wire(UInt(xLen.W))
  output := regfile(addr)
  val wdata = cmd.bits.rs1

  when (cmd.fire()) {
    when(doPush) {
      regfile(addr) := wdata
      when(addr < outer.n.asUInt) {
        addr := addr +% 1.U
      }
    }.elsewhen(doPop) {
      output := regfile(addr -% 1.U)
      when(addr > 0.U) {
        addr := addr -% 1.U
      }
    }
  }

cmd はハードウェアキューで、Rocket から RoCC 経由で実行された命令、ソース・デスティネーションのレジスタの値が入っています。ハードウェアキューが値を取り出せる状態になると、cmd.fire() は true になり、 sspush/sspop の命令が実行されます。

funct の値が 0 (すなわち、sspush 命令が Rocket で実行された) の場合、stack のトップにソースレジスタの値を書き込み、スタックトップのアドレスをインクリメントします。funct の値が 1 (すなわち、sspop 命令が Rocket で実行された) の場合、Shadow Stack のトップに積まれた値を出力とします。

関数呼び出しの直前とリターン前に sspush/sspop 命令の追加

ここまでで、RoCC を使って Shadow Stack に sspush と sspop 命令が追加できました。次に、実行プログラムに sspush 命令を関数のプロローグに、sspop 命令とシステムのコールスタックの値との比較処理を関数のエピローグに挿入していきます。

今回は LLVM バックエンドの書き換えにより、 sspush sspop が関数のエピローグとプロローグに自動的に挿入されるようにしました。

LLVM バックエンドのカスタマイズ方法に関しては、記事が長くなることから、次の記事で紹介することにします。ここでは、sspush と sspop が自動的に挿入されるようになった結果だけを示します。

以下のような C 言語のソースコードを用意し、ビルドします。関数マクロとして VULN を定義すると、Stack Buffer Overflow が発生するプログラムになっています。

// vuln.c
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int main() {
    char buffer[16];
#ifdef VULN
    const char* input = "0123456789abcdefghijklmn0000000000000000000"; // Buffer Overflow を意図的に起こす場合
#else
    const char* input = "012000"; // 正常終了する場合
#endif

    strcpy(buffer, input);
    printf("%d\n", buffer[3]);
    return 0;
}

バックエンドに修正を加えた llvm を clang 経由で実行します。

$ clang -march=rv64gc -mabi=lp64d -c vuln.c
$ riscv64-unknown-elf-gcc -march=rv64gc -mabi=lp64d vuln.o

アセンブリ結果を見ると、関数のエピローグとプロローグに Shadow Stack への push/pop 命令が挿入されていることがわかります。

main:                                   # @main
        sspush  zero, ra, zero ; <--- リターンアドレスの値を shadow stack に push
        addi    sp, sp, -80
        sd      ra, 72(sp)
        sd      s0, 64(sp)
        addi    s0, sp, 80
        mv      a0, zero
        sw      a0, -20(s0)
        lui     a1, %hi(.L.str.1)
        addi    a1, a1, %lo(.L.str.1)
        sd      a1, -48(s0)
        ld      a1, -48(s0)
        addi    a2, s0, -36
        sd      a0, -56(s0)
        mv      a0, a2
        call    strcpy
        lbu     a1, -33(s0)
        lui     a2, %hi(.L.str.2)
        addi    a2, a2, %lo(.L.str.2)
        sd      a0, -64(s0)
        mv      a0, a2
        call    printf
        ld      a1, -56(s0)
        sd      a0, -72(s0)
        mv      a0, a1
        ld      s0, 64(sp)
        ld      ra, 72(sp)
        addi    sp, sp, 80
        sspop   t0, zero, zero ; <--- t0 に shadow stack の top
        bne     ra, t0, stack_failure ; <--- 比較結果が等しくなかった場合には、プログラムを終了する関数 (stack_failure) へ飛ぶ
        ret

シミュレーターで Stack Buffer Overflow を検知できることを確認

Shadow Stack を使い、実際に Stack Buffer Overflow を検知出来るのかを確認していきます。

まず、先程の vuln.c のソースコードで、Stack Buffer Overflow が起きる場合とそうでない場合でそれぞれバイナリを作成します。

$ clang -DVULN -march=rv64gc -mabi=lp64d -c vuln.c
$ riscv64-unknown-elf-gcc -march=rv64gc -mabi=lp64d vuln.o -o vuln.out # Buffer Overflow が起きるプログラムをビルド
$ clang -march=rv64gc -mabi=lp64d -c vuln.c
$ riscv64-unknown-elf-gcc -march=rv64gc -mabi=lp64d vuln.o -o normal.out # Buffer Overflow が発生せず正常終了するプログラムをビルド

今回は Verilator を使ったシミュレーションにより、Stack Buffer Overflow 検知機構が働くか否かを見てみましょう。

# 最初に Buffer Overflow が起きないプログラムを実行
$ ./emulator-freechips.rocketchip.system-RoccExampleConfig -c pk ./normal.out
This emulator compiled with JTAG Remote Bitbang client. To enable, use +jtag_rbb_enable=1.
Listening on port 58342
48
*** PASSED *** Completed after 1927302 cycles
# 次に Buffer Overflow が起きるプログラムを実行
$ ./emulator-freechips.rocketchip.system-RoccExampleConfig -c pk ./vuln.out
This emulator compiled with JTAG Remote Bitbang client. To enable, use +jtag_rbb_enable=1.
Listening on port 58419
51
stack smashing detected # <-- Buffer Overflow によるリターンアドレス破壊を検知し、プログラムの実行が停止
*** FAILED *** via dtm (code = -1, seed 1568691995) after 1956482 cycles

脆弱性のない normal.out の方は正常終了していますが、Buffer Overflow 脆弱性のある vuln.out の方は stack smashing detected と表示されプログラムが強制終了していることがわかります。

考察

今回は、RoCC を使い Shadow Stack 操作用の sspush と sspop 命令を追加し、それらが関数の開始と終了時に適切に呼び出されるようにし、Stack Buffer Overflow を検知する機構を実装しました。

この方法のメリットとしては、Rocket 本体を書き換えることなく Shadow Stack による Stack Buffer Overflow 検知機構を追加できる点にあります。

この方法のデメリットは、sspush と sspop 命令を関数のエピローグとプロローグに自動的に挿入するために、コンパイラの書き換えが必要になる点です。また、ソースコードの再ビルドが必要になってしまう点もあり、実行バイナリしか提供されていない場合、この方法をそのまま適用することは難しくなります。その場合、静的もしくは動的に命令 instrument を行う必要が出てきます。

その他、今回の実装には以下の制約があります。 - コンテキストスイッチが起きる場合が考慮されておらず、誤検知してしまう - 例外が投げられコールバック関数が呼び出される場合が考慮されておらず、誤検知してしまう

コンテキストスイッチが起きる場合でも正しく動作するようにするためには、Shadow Stack 領域に格納されたリターンアドレスの値の退避が別途必要です。

例外が投げられコールバック関数が呼び出される場合での動作の保証には、Shadow Stack の値のチェック処理の緩和などが考えられます。例えば、Shadow Stackに格納されたリターンアドレスを pop し続け、一致するものが現れたら、Buffer Overflow が発生していないと判断するなどです [3]。

また、Rocket の CPU Core 部分を書き換えるのであれば、call と ret 命令の実行時に自動的に Shadow Stack へ push pop し、リターンアドレスの値の比較もハードウェアで行い、違っていたら例外を投げる方法を採ることもできます。この方法であれば、コンパイラの書き換え・ソースコードの再ビルドも不要になりますが、一方で Rocket の CPU Core 部分の大幅な書き換えが必要になる点がデメリットとなります。

おわりに

Shadow Stack を使った Stack Buffer Overflow 検知機構の実装について紹介しました。提案した方法により、Stack Buffer Overflow によるリターンアドレス破壊を検知できることを確認しました。

今後の課題としては、考察のところに書いたとおり、Rocket 本体の書き換えによる Shadow Stack の実装です。また、Shadow Stack は Control Flow の乗っ取りに対しては効果を発揮しますが、Buffer Overread による Information Leak への対策を行うことはできません。Control Flow の乗っ取り以外の攻撃へのハードウェアレベルでの対策は今後の課題です。

参考文献

[1] De, Asmit, et al. "FIXER: Flow Integrity Extensions for Embedded RISC-V." 2019 Design, Automation & Test in Europe Conference & Exhibition (DATE). IEEE, 2019.

[2] Patel, Baiju. "Intel releases new technology specifications to protect against ROP attacks." Retrieved March 1 (2016): 2017.

[3] Sinnadurai, Saravanan, Qin Zhao, and Weng fai Wong. "Transparent runtime shadow stack: Protection against malicious return address modifications." 2008.