2025/3/1-2025/3/2 に開催されたSECCON 13 Finalsの参加記。自分 (@zatsu308) ともやし先輩 (@oreha_senpai) の2人チーム AkihiroOmori(traP)で参加し、4897点で5位だった。
2日に跨るコンテストで両日Jeopardy/KoHがともに出題されておりHardware問も存在するなかなかにハードなCTFだったが、二人しかいない割にはなかなか健闘できたのではないかと思う。

チームについて

チーム AkihiroOmori(traP) は招待枠での参加となっている。 SECCON予選は二人とも予選落ちだったのだが、今年のSECCON決勝にはSANs NetWars Tournaments 2024の招待枠が存在し、もやし先輩がこのコンテストで優勝されたということで、同じく予選落ちで暇だった僕とチームを組むことにした、という経緯。当初はtraPの面々を誘って参加する予定だったらしいのだが、メンバーの都合が合わず危うくソロ参加になるところだったらしい。チームメンバーの得意分野はzatsuがPwn/Cryptoでもやし先輩がWeb。得意ジャンルの問題だけ担当を決めつつ他は適当に分担して解いていく、という流れを想定していた。

writeups

[Crypto] RSA+

初日前半の時点でInternational側のsolveが出ていたので取り組んだ。ソースコードは以下の通り。

import os
import signal
from secrets import randbelow

from Crypto.Util.number import isPrime

flag = os.getenv("FLAG", "SECCON{this_is_not_a_flag}")


if __name__ == "__main__":
    signal.alarm(120)

    p = int(input("Your favorite prime p (hex) > "), 16)
    print('p:', p)
    print(isPrime(p))
    if not isPrime(p) and p.bit_length() >= 512:
        print("p must be a prime")
        exit()
    q = int(input("Your favorite prime q (hex) > "), 16)
    print('q:', q)
    print(isPrime(p))
    if not isPrime(q) and q.bit_length() >= 512:
        print("q must be a prime")
        exit()
    n = p * q

    assert n == q

    g = n // 2
    h = n // 3
    x = randbelow(2**512)
    r = (pow(x, g, n) + pow(x, h, n)) % n
    print(f"{r = }")

    guess_x = int(input("Guess x > "))
    if x == guess_x:
        print(flag)
    else:
        print("Wrong...")

乱数によって生成された未知の $x$ を復元する問題であり、一定以上の大きさの素数 $p, q$ を任意に与えると $n = pq, f = \lfloor n/2 \rfloor , g = \lfloor n/3 \rfloor$ とおいたときの $r = (x^g + x^h) \bmod n$ を得ることができる。
一見真剣な問題に見えるが、実はよく見ると p, q のvalid判定部分のコード if not isPrime(p) and p.bit_length() >= 512 がおかしなことがわかる¹。これは二条件のandなので小さな非素数がチェックに引っかかることはなく、 $p=1$ とおくことで $n$ に任意の素数を入れることができる。
$n$ を直接入力するように改変したソースコードをChatGPTに渡してソルバを書いてもらった結果が以下のコード。アルゴリズムはよく分かっていないがこれをそのまま実行すると無事フラグが得られた。

from sympy import nextprime
n = nextprime(2**512)
while n % 3 != 2:
    n = nextprime(n + 1)

print(hex(n))
r = int(input('r:'))

for L in [1, -1]:
    try:
        inv_val = pow(r - L, -1, n)
    except ValueError:
        continue
    x_candidate = pow(inv_val, 3, n)
    if pow(x_candidate, (n-1)//2, n) == L:
        x = x_candidate
        break
print(x)

この提出がDomesticの（WelcomeとKotHを除く）全問題の中でのfirst bloodとなり、一瞬だけ一位に躍り出ることができた。ChatGPT万歳。

コンテスト中は何も考えずにコードを実行してフラグが出た時点で満足していたが、writeup記事でこれしか書かないのは流石に良くないので以下にこの解法の概要（をコンテスト終了後に理解したもの）を書くことにする。
$n$ を $2$ や $3$ で割った余りを自由に設定できることに着目して、 $n \equiv 2 \pmod 3$ の場合を考える。このときフェルマーの小定理より $x^{(n-2)} \equiv x^{-1} \pmod n$ が成り立つことから、 ${(x^h)}^3 \equiv x^{-1} \pmod n$ となる。また、 $x^{\frac{(n-1)}{2}} \bmod p \in \{ 1, -1\}$ より ${(x^h)}^3$ は $r+1$ か $r-1$ のどちらかだということが分かる。そのため $r+1,r-1$ の両方について逆元の3乗を調べることで $x$ を復元できるということらしい。

[Rev] simple_reversing

flag checkerのELFのみが渡される非常にシンプルな問題。とりあえずGhidraで開いて問題を読んでみると、main の中で RITE0300 という文字列を読んでいることが分かる。これはmrubyのバイトコードを表すヘッダーらしい。
そこから暫く詰まってしまったが、よく見るとバイナリ中の RITE0300 から始まる部分がそのままmrubyのバイトコードになっていることに気づき²、該当部分をファイルとして切り出して mruby --verbose tmp.mrb に与えることで以下のような命令列を得る事ができた。

irep 0x5651d96cead0 nregs=10 nlocals=4 pools=2 syms=6 reps=9 ilen=94
local variable names:
  R1:size_check
  R2:split
  R3:checker
      000 LAMBDA    R1  I[0]
      003 LAMBDA    R2  I[1]
      006 LAMBDA    R4  I[2]
      009 LAMBDA    R5  I[3]
      012 LAMBDA    R6  I[4]
      015 LAMBDA    R7  I[5]
      018 LAMBDA    R8  I[6]
      021 LAMBDA    R9  I[7]
      024 ARRAY     R3  R4  6   ; R3:checker
      028 MOVE      R4  R1      ; R1:size_check
      031 GETGV     R5  $input  
      034 SEND      R4  :call   n=1
      038 JMPNOT    R4  070 
      042 MOVE      R4  R2      ; R2:split
      045 GETGV     R5  $input  
      048 SEND      R4  :call   n=1
      052 MOVE      R5  R3      ; R3:checker
      055 SEND      R4  :zip    n=1
      059 BLOCK     R5  I[8]
      062 SENDB     R4  :map    n=0
      066 SEND      R4  :all?   n=0
      070 JMPNOT    R4  084 
      074 STRING    R5  L[0]    ; Correct!
      077 SSEND     R4  :puts   n=1
      081 JMP       091
      084 STRING    R5  L[1]    ; Incorrect...
      087 SSEND     R4  :puts   n=1
      091 RETURN    R4      
      093 STOP
...

これをChatGPTに読ませて「このflag checkerの処理を逆算してみて、正しいflagを求めるpythonコードを書いてみて」と丸投げした結果、66秒の試行の末にフラグの文字列をそのまま得ることができた。凄すぎる。

[Rev] SECCON_Glitch_Gate_1

SECCON決勝恒例の³HardWare問。 READMEと問題ページの説明に載っている問題概要は以下の通り。

各チームにArduino nanoと工作キットが配布される
配布されているArduino nanoとは別に、challenge room内に攻撃対象のArduino nanoが存在する
攻撃対象のArduino nanoでプログラムが動いており、その中に2つのフラグが存在する
- フラグの中身のみを変更したELFファイルが与えられるため、これを配布されているArduino nanoに書き込むことで、手元で攻撃のための環境を再現できる
一日に一度（つまり合計で二回）challenge roomに行って実機への攻撃に挑戦できる⁴

事前説明はこれぐらいで、ここから何をすればいいのか、そもそもフラグがどのようにして出力されるのかも分からなかった。そのため、初日はchallenge roomの中を見てArduinoの適当なピンにテスターを当てて遊ぶだけで挑戦権を浪費してしまった⁵。
ここから初日夜のホテルで色々調べながら動かしてみる。まずはArduino IDEなどの環境を整備し、二時間強の試行錯誤⁶の末にELFの書き込みとArduino IDEのシリアルポート出力設定を終えた。その結果、シリアル出力に以下のメッセージが出ていることが確認できた。

====================================================
|                                                   |
|                SECCON Glitch Gate                 |
|                                                   |
====================================================
[*] Welcome to the SECCON Glitch Gate!
[*] Initializing system...
[!] ERROR: Incorrect hardware configuration detected. No flag for you!

[*] Gathering inner strength........................

どうやらハードウェア設定が条件を満たしていないようだが、どのようにすればフラグが得られるかは載っていない。そこで、Ghidraや avr-objdump、ChatGPTなどの力を用いてELFの中身を解析していく。
avr-objdump の出力のうち [!] ERROR: Incorrect hardware configuration detected. No flag for you! の出力に関連する部分は以下のようになっている。

 8f8:    89 b1           in  r24, 0x09   ; 9
 8fa:   93 b1           in  r25, 0x03   ; 3
 8fc:   20 91 00 01     lds r18, 0x0100 ; 0x800100 <__data_start>
 900:   80 7e           andi    r24, 0xE0   ; 224
 902:   9f 71           andi    r25, 0x1F   ; 31
 904:   89 2b           or  r24, r25
 906:   82 27           eor r24, r18
 908:   83 36           cpi r24, 0x63   ; 99
 90a:   39 f5           brne    .+78        ; 0x95a <__stack+0x5b>
 90c:   8b ee           ldi r24, 0xEB   ; 235
 90e:   90 e0           ldi r25, 0x00   ; 0
 910:   0e 94 ea 02     call    0x5d4   ; 0x5d4 <_ZN5Print7printlnEPK19__FlashStringHelper.constprop.7>
 ...
 95a:   84 ea           ldi r24, 0xA4   ; 164
 95c:   90 e0           ldi r25, 0x00   ; 0
 95e:   d8 cf           rjmp    .-80        ; 0x910 <__stack+0x11>

.text 領域の 0x0a4 には [!] ERROR: Incorrect hardware configuration detected. No flag for you! という文字列が、0x0eb には [+] The hardware configuration is correct. The first flag: SECCON{*****************} という文字列が格納されている。また、Arduino nanoで用いているAVR命令セットでは in はI/Oからの値読み込みを意味しており、0x910 の println は r24,r25 に入ったアドレスに書いてある文字列のシリアル出力を行う関数になっている。
今回は .text 領域の 0x0eb に格納されているフラグを出力させたいため、 0x908,0x90a の比較→ジャンプを行っているところでジャンプをさせずに 0x91c にプログラムカウンタを飛ばすことが要求される。 andやxorを取って比較する部分を解読すると、r24 の値が 0x110***** であること、r25 の値が 0x***11101 であることがこの分岐を行わないための条件であることが分かる。
ここで、in で該当のレジスタに値を入れている部分の命令を再度確認する。

8f8:    89 b1        in  r24, 0x09    ; 9
8fa:    93 b1        in  r25, 0x03    ; 3

この命令について詳しく調べると、0x8f8 ではarduino nanoのPORTB入力、0x8fa ではPORTD入力の値をレジスタに保存しているらしい。また、PORTB,PORTDはそれぞれ各ピンの状態 (High/Low) をビット列で表しており、ボード上ではPORTBが D8-D13 と、PORTDが D0-D7 と対応していることが分かった。 PORTBに期待する出力が 0x***11101 であり、PORTDに期待される出力が 0x110***** なことから、これは D5,D9 をLowに、それ以外をHighに設定するべきだということが分かる⁷。
確か何も接続していない端子はHighになるよな・・・みたいなことを考えながら実際に D5, D9 ピンをArduino nanoのGNDと繋げて手元のArduinoで動作確認をすると、無事手元で（REDACTEDではあるが）フラグを入手することができた。

翌日は15:00-からchallenge roomを予約していたためそこでいざ実践。というところで、手元のArduino nanoで認識していたはずのCOMポートが攻撃対象との接続の際に認識されなくなるトラブルが発生してしまった。最初は原因が分からず10分ほどオロオロしていたが、暫くしたところでスタッフの方から

配布されたマイコンと攻撃対象のマイコンがが少し異なり、ポートが認識されていないのは恐らく必要なドライバがインストールされていないことが原因
これは運営側に原因があるためドライバを入れて再挑戦して良い

との連絡を受けた。その後ドライバをダウンロードし再度挑戦すると無事通信が行え、1つ目のフラグが得られた。これがdomesticのfirst bloodとなった⁸。
このまま謎のトラブルで数百点を落とす羽目になるのか・・・と内心かなり焦っていたため、運営の方に助け舟を出して頂いて大変助かった。ありがとうございました。

[Rev] SECCON_Glitch_Gate_2 (unsolved)

最終的には解けなかったが深夜のホテルで頑張ってコードを読んだので供養。 Arduino nano上で動いているプログラムは1つ目のフラグを出力した後に

[*] Gathering inner strength........................
[-] You lack discipline! No flag for you!
[*] Gathering inner strength........................
[-] You lack discipline! No flag for you!
[*] Gathering inner strength.......

のようなメッセージを繰り返し出力している。この部分での処理を上手く行って2つ目のフラグを得たい、というのが問題の趣旨。
ソースコードを前問と同じように頑張って読むと、以下のようなCコードで表せる処理を行っていることが確認できた。

#include <stdio.h>
#include <stdint.h>
#include <stdbool.h>

static uint16_t continueLoop = 1;

void printMessage(const char* msg) {
    printf("%s", msg);
}

void printFlag(void) {
    printf("[REDACTED]\n");
}

int main(void) 
{
    while (1) {
        printMessage("\n");

        if (continueLoop == 0) {
            goto PRINT_FLAG; 
        }

        uint16_t val = 0;

        printMessage("[*] Gathering inner strength........................");

        uint8_t loopVar = 24;

        while (loopVar != 0) {
            uint16_t temp = 0;
            while (temp < 0x0F0D) {
                temp++;
            }
            
            val++;

            printMessage(".");

            if (val > 255) {
                continueLoop = 0;
            }

            if (continueLoop == 0) {
                break;
            }
            loopVar--;
        } // while (loopVar != 0)

        printMessage("\n");

        if (continueLoop == 0) {
            goto PRINT_FLAG;
        }
        else {
            printMessage("[-] You lack discipline! No flag for you!\n");
        }
    }

PRINT_FLAG:
    printFlag();
    return 0;
}

一度の処理では loopVar を更新しながら24回ループを行い、ループ中の各ステップではゼロ初期化されている変数 val を毎回インクリメントしている。ループ中に val>255 になれば continueLoop が1になりフラグが得られる、という動作になっている。見れば分かる通り val は各試行で高々24にしかならず、バグが起きない限りどうしても continueLoop を1にすることはできない。そのため、電圧グリッチなどのハードウェアに干渉する攻撃によってフラグを得るものだと考え、以下のような構成での攻撃を考えてプログラムや回路の準備を行った。

配布されている手元Arduino nanoをglitcherとして、200nsぐらいだけ電圧をかけるようなプログラムを用意
Arduino nanoのピン出力からMOSFETをつなげて、MOSFETの出力を攻撃対象Arduino nanoの電源ピンに繋げる
ループ中に電圧をかけて攻撃対象の電圧を一瞬だけ0Vに落とし、バグによるレジスタ書き換えを狙う

とはいえこれを実機一発本番でやって成功するとは思えず、challengeの時間が最終日の終了2時間前で試行をする時間がない+前述のトラブルで時間を浪費してしまったために実際に攻撃を試みることは断念してしまった。残念。後程運営の方に話を伺ったところ、想定解はクロック波を与える電圧グリッチらしい。最終的に解けはしなかったものの、オンサイト環境でしかできない設定で非常に面白い問題だった。

[KoH] Allegro

競技期間中ずっと行われていたKoH問。問題は「低速なELFファイルが配布されるので、それを高速化しろ」というシンプルな内容で、詳しいルールは以下のようになっている⁹。

基本的なルール
- 配布されるファイルはELFとテストスクリプトのみ
  - テストスクリプト中には入出力サンプルが含まれている
- 各チームは競技サーバーに任意のバイナリをアップロードすることができる
- アップロードされたバイナリに入力を与えて配布ELFと同じ出力が得られたらその際の実行時間に応じて得点が得られる
  - 各入力の制約は明示されていないが、integer overflowなどのバグを起こすような入力は与えられないことが保証される
ラウンドについて
- 問題は合計6問で、Day1, Day2でそれぞれ3ラウンドが行われる
- 1ラウンドは90分～150分で、ラウンド中は経過時間によってテストケースの難易度が変化する
スコアリングについて
- 5分毎にPhaseが切り替わり、各Phase毎にスコアが与えられる
- 各Phaseではアップロードされたバイナリに同じ入力を与えて20回実行を行い、出力の正しさと実行時間を確認する
- 全実行で3sec以内に正しい答えを出力できればAcceptedとなる
- 各Phaseごとに全チームの提出が順位付けされ、順位に応じた点数が得られる
- 提出の順位付けの基準は以下の通り:
  - 提出がAcceptedとならなかったチームは一律で最下位
  - Acceptedとなったチームはが小さい順に順位付け（同じなら同率）
    - 点数は確か上から20,16,12,9,6,...みたいな感じ
計算機環境
- 計算機情報はRulesに詳しく記載あり
- 実環境へのsshなどは行えなえず、Dockerfileなどの配布もなし
- メモリ制限は256MBぐらい
  - ラウンド5辺りで512MBに増えた気もするがよく覚えていない
- 1チームの計算リソースは2コア分で、同時に3プロセスまで立ち上げることができる

以上。Reversingパートと高速化パートに分かれており、自分のようなRevが最低限できる競プロ出身勢には向いていそうな問題だと感じた。

Round 1

コンテスト開始と同時に始まった最初のラウンド。再序盤のKoHが得点の稼ぎどころになると考えて、コンテスト開始直後に張り付いて解いた。渡されたELFをGhidraで読んだ結果がこんな感じ。

#include <stdio.h>


long f(long n) {
    if(n == 0){
        return 1;
    }else if(n == 1){
        return 1;
    }else if(n == 2){
        return 1;
    }else{
        return n + f(n-3) + f(n-2) - f(n-1);
    }
}

int main(){
    unsigned long long a;
    scanf("%llu", &a);
    if(a > 3){
        sleep(5);
    }
    printf("%llu\n", f(a));
    return 0;
}

a > 3 で sleep(5) を挟んでいるのが最初の自明な高速化ポイント。最初はバイナリの該当部分を nop で置き換えようかと考えたが、よく考えると元のELFにパッチを当てて作る必要は全くなく、Cのコードを自分で書いてコンパイル結果を提出すればいいことに気づいた。ということで sleep(5) の処理を消してついでに指数時間ぐらいかかりそうな再帰呼び出しをループに置き換えたのが以下のコード。

#include <stdio.h>

long f(long n) {
    if (n < 3)
        return 1;
    long f0 = 1, f1 = 1, f2 = 1, f_current;
    for (long i = 3; i <= n; i++) {
        f_current = i + (f0 + f1 - f2);
        f0 = f1;
        f1 = f2;
        f2 = f_current;
    }
    return f2;
}

int main(){
    unsigned long long a;
    scanf("%llu", &a);
    printf("%llu\n", f(a));
    return 0;
}

これを提出することでTimeoutがAcceptedに切り替わり、無事に1位を取ることができた。

ラウンド1序盤の問題スコアボード。黄色がTimeout、緑がAcceptedを表している

一旦ここで終わりにしても良かったが、実は入力の型が unsigned long long であるため、実行に $O(n)$ 時間がかかる現在のコードではテストケースの難易度が上がった場合にTimeoutになると考えられる。このタイプの漸化式は行列累乗で $O(\log n)$ で解けることが知られているため、ChatGPTにその旨を伝えて高速なコードを書いてもらった。

#include <stdio.h>
#define N 5  // 行列のサイズ

typedef unsigned long long ull;

void multiply_matrix(ull A[N][N], ull B[N][N], ull C[N][N]) {
    int i, j, k;
    for(i = 0; i < N; i++) {
        for(j = 0; j < N; j++) {
            C[i][j] = 0;
            for(k = 0; k < N; k++) {
                C[i][j] += A[i][k] * B[k][j];
            }
        }
    }
}

void copy_matrix(ull dest[N][N], ull src[N][N]) {
    int i, j;
    for(i = 0; i < N; i++) {
        for(j = 0; j < N; j++) {
            dest[i][j] = src[i][j];
        }
    }
}

void matrix_power(ull M[N][N], ull p, ull result[N][N]) {
    int i, j;
    ull temp[N][N];
    ull M_copy[N][N];
    
    copy_matrix(M_copy, M);
    
    for(i = 0; i < N; i++) {
        for(j = 0; j < N; j++) {
            result[i][j] = (i == j) ? 1 : 0;
        }
    }
    
    while(p > 0) {
        if (p & 1) {
            multiply_matrix(result, M_copy, temp);
            copy_matrix(result, temp);
        }
        multiply_matrix(M_copy, M_copy, temp);
        copy_matrix(M_copy, temp);
        p /= 2;
    }
}

ull compute_f(ull n) {
    if(n < 3) return 1;
    
    ull M[N][N] = {
        {(ull)(-1), 1, 1, 1, 1},
        {1, 0, 0, 0, 0},
        {0, 1, 0, 0, 0},
        {0, 0, 0, 1, 1},
        {0, 0, 0, 0, 1}
    };

    ull X[N] = {1, 1, 1, 2, 1};
    
    ull M_exp[N][N];
    matrix_power(M, n - 2, M_exp);
    
    ull Y[N] = {0};
    int i, j;
    for (i = 0; i < N; i++) {
        for (j = 0; j < N; j++) {
            Y[i] += M_exp[i][j] * X[j];
        }
    }
    return Y[0];
}

int main(){
    unsigned long long a;
    scanf("%llu", &a);
    printf("%llu\n", compute_f(a));
    return 0;
}

このコードを提出するようにしてからしばらく待つと、Phaseの切り替わりで問題難易度がHardになった途端に複数チームの提出がタイムアウトしていることが確認できた。以降はこのまま最終時点まで0.1secでのAcceptedを続け、無事に全Phase1位で満点を得ることができた。嬉しい。
ちなみに想定解は漸化式を解いての $O(1)$ 解法だったらしい。とはいえ100ms単位でしか評価されない以上 $O(\log n)$ でも満点が取れる程度には高速であり、結果的にはこの解法でも十分だった。

Round 2

少し読んだが無理そうだったので撤退。これは完全に解けなかった言い訳なのだが、2人チームでKoHが2問あるのでお互いがずっとKoHに張り付いているとJeopardyに一切取り組めず、厳しそうなときは早めに撤退するようにしていた。

Round 3

VMっぽいELFファイルが与えられる。入出力例はこんな感じ。

=-----------INPUT-----------=
OP1 0,123
OP1 1,234
OP3 0,1
__EOF__

=-----------OUTPUT----------=
R0: 0x00000165
R1: 0x000000ea
R2: 0x00000000
R3: 0x00000000
R4: 0x00000000
R5: 0x00000000
R6: 0x00000000
R7: 0x00000000
R8: 0x00000000
R9: 0x00000000

Ghidraでデコンパイルしてそれっぽい変数名をつけたものの抜粋がこんな感じ。

    tuple[1] = py_list_getitem(list,(ulong)list_index & 0xffffffff);
    tuple[0] = py_tuple_getitem(tuple[1],0);
    tuple[1] = py_tuple_getitem(tuple[1],1);
    arg0_str = (char *)py_tostr(tuple[0]);
    iVar4 = strcmp(arg0_str,"OP1");
    if (iVar4 == 0) {
      vm_insn_op1(list_index,tuple[1]);
    }
    else {
      iVar4 = strcmp(arg0_str,"OP2");
      if (iVar4 == 0) {
        vm_insn_op2(list_index,tuple[1]);
      }

void vm_insn_op1(long param_1,undefined8 arg)

{
  undefined4 uVar1;
  undefined8 uVar2;
  long lVar3;
  
  uVar2 = py_list_getitem(arg,0);
  lVar3 = py_toint(uVar2);
  uVar2 = py_list_getitem(arg,1);
  uVar1 = py_toint(uVar2);
  *(undefined4 *)(param_1 + 8 + lVar3 * 4) = uVar1;
  return;
}

プログラム自体は入力を処理して最終的なレジスタの中身を出力する単純なVMになっているが、どうやら入力を処理するVM内でさらにPythonのVMを介しているらしい。各Opcodeの中身を確認すると四則演算とif/while程度しかなかったため、まずはOPcodeの中身を理解してからChatGPTにCで書き直してもらう。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>

#define MAX_LINE 256
#define INITIAL_PROG_SIZE 100

typedef enum {
    OP_1,
    OP_2,
    OP_3,
    OP_4,
    OP_5,
    OP_6,
    OP_7,
    OP_8,
    OP_9,
    OP_UNKNOWN
} Opcode;

typedef struct {
    Opcode opcode;
    int arg_count;
    unsigned long long args[3];  // 最大3個の引数を想定
} Instruction;

/* 文字列からOPcodeを判定 */
Opcode parseOpcode(const char *s) {
    if(strcmp(s, "OP1") == 0)
        return OP_1;
    if(strcmp(s, "OP2") == 0)
        return OP_2;
    if(strcmp(s, "OP3") == 0)
        return OP_3;
    if(strcmp(s, "OP4") == 0)
        return OP_4;
    if(strcmp(s, "OP5") == 0)
        return OP_5;
    if(strcmp(s, "OP6") == 0)
        return OP_6;
    if(strcmp(s, "OP7") == 0)
        return OP_7;
    if(strcmp(s, "OP8") == 0)
        return OP_8;
    if(strcmp(s, "OP9") == 0)
        return OP_9;
    return OP_UNKNOWN;
}

int main(void) {
    char line[MAX_LINE];
    Instruction *prog = malloc(sizeof(Instruction) * INITIAL_PROG_SIZE);
    if (!prog) {
        fprintf(stderr, "Memory allocation failed\n");
        return 1;
    }
    int progSize = INITIAL_PROG_SIZE;
    int progCount = 0;

    while(fgets(line, sizeof(line), stdin)) {
        /* 改行除去 */
        line[strcspn(line, "\r\n")] = '\0';
        if(strcmp(line, "__EOF__") == 0)
            break;
        if(strlen(line) == 0)
            continue;

        char opcodeStr[16];
        char argsStr[128] = {0};
        /* 最初の単語（OPcode）と残りの部分を読み取る */
        if(sscanf(line, "%15s %[^\n]", opcodeStr, argsStr) < 1)
            continue;
        Instruction inst;
        inst.opcode = parseOpcode(opcodeStr);
        inst.arg_count = 0;

        /* argsStr が空でなければ、カンマ区切りで解析 */
        if(strlen(argsStr) > 0) {
            char *token = strtok(argsStr, ",");
            while(token != NULL && inst.arg_count < 3) {
                /* 前後の空白を除去 */
                while(*token == ' ') token++;
                char *end = token + strlen(token) - 1;
                while(end > token && (*end == ' ')) {
                    *end = '\0';
                    end--;
                }
                inst.args[inst.arg_count] = strtoull(token, NULL, 10);
                inst.arg_count++;
                token = strtok(NULL, ",");
            }
        }

        /* 配列が足りなければ拡張 */
        if(progCount >= progSize) {
            progSize *= 2;
            prog = realloc(prog, sizeof(Instruction) * progSize);
            if (!prog) {
                fprintf(stderr, "Memory allocation failed\n");
                return 1;
            }
        }
        prog[progCount++] = inst;
    }

    /* レジスタファイル (R0～R9) の初期値（出力例に合わせた定数） */
    unsigned int R[10] = {
        0, 0, 0, 0, 0,
        0, 0, 0, 0, 0
    };

    /* プログラムカウンタ pc */
    int pc = 0;
    while(pc >= 0 && pc < progCount) {
        /* 最終的なレジスタの状態を出力 (各値は8桁の16進数) */
        // for (int i = 0; i < 10; i++) {
        //     printf("TMP_R%d: 0x%08x\n", i, R[i]);
        // }
        Instruction inst = prog[pc];
        // printf("opcode: %d", inst.opcode);
        // for (int i = 0; i < inst.arg_count; i++) {
        //     printf(", arg%d: %llu", i, inst.args[i]);
        // }
        // printf("\n");

        switch(inst.opcode) {
            case OP_1:
                /* OP1: R[arg0] = immediate value (arg1) */
                if(inst.arg_count == 2) {
                    unsigned long long regIndex = inst.args[0];
                    unsigned long long imm = inst.args[1];
                    if(regIndex < 10)
                        R[regIndex] = (unsigned int)imm;
                }
                pc++;
                break;
            case OP_2:
                /* OP2: R[arg0] = R[arg1] */
                if(inst.arg_count == 2) {
                    unsigned long long dest = inst.args[0];
                    unsigned long long src  = inst.args[1];
                    if(dest < 10 && src < 10)
                        R[dest] = R[src];
                }
                pc++;
                break;
            case OP_3:
                /* OP3: R[arg0] = R[arg0] + R[arg1] */
                if(inst.arg_count == 2) {
                    unsigned long long a = inst.args[0];
                    unsigned long long b = inst.args[1];
                    if(a < 10 && b < 10)
                        R[a] = R[a] + R[b];
                }
                pc++;
                break;
            case OP_4:
                /* OP4: R[arg0] = R[arg0] - R[arg1] */
                if(inst.arg_count == 2) {
                    unsigned long long a = inst.args[0];
                    unsigned long long b = inst.args[1];
                    if(a < 10 && b < 10)
                        R[a] = R[a] - R[b];
                }
                pc++;
                break;
            case OP_5:
                /* OP5: R[arg0] = R[arg0] * R[arg1] */
                if(inst.arg_count == 2) {
                    unsigned long long a = inst.args[0];
                    unsigned long long b = inst.args[1];
                    if(a < 10 && b < 10)
                        R[a] = R[a] * R[b];
                }
                pc++;
                break;
            case OP_6:
                /* OP6: R[arg0] = R[arg0] / R[arg1] (整数除算) */
                if(inst.arg_count == 2) {
                    unsigned long long a = inst.args[0];
                    unsigned long long b = inst.args[1];
                    if(a < 10 && b < 10) {
                        if(R[b] == 0) {
                            fprintf(stderr, "Division by zero error at instruction %d\n", pc);
                            free(prog);
                            return 1;
                        }
                        R[a] = R[a] / R[b];
                    }
                }
                pc++;
                break;
            case OP_7:
                /* OP7: if (R[arg0] == R[arg1]) jump to arg2 */
                if(inst.arg_count == 3) {
                    unsigned long long a = inst.args[0];
                    unsigned long long b = inst.args[1];
                    unsigned long long target = inst.args[2];
                    if(a < 10 && b < 10) {
                        if(R[a] == R[b])
                            pc = (int)target;
                        else
                            pc++;
                    } else {
                        pc++;
                    }
                } else {
                    pc++;
                }
                break;
            case OP_8:
                /* OP8: if (R[arg0] != R[arg1]) jump to arg2 */
                if(inst.arg_count == 3) {
                    unsigned long long a = inst.args[0];
                    unsigned long long b = inst.args[1];
                    unsigned long long target = inst.args[2];
                    if(a < 10 && b < 10) {
                        if(R[a] != R[b])
                            pc = (int)target;
                        else
                            pc++;
                    } else {
                        pc++;
                    }
                } else {
                    pc++;
                }
                break;
            case OP_9:
                /* OP9: Unconditional jump to arg0 */
                if(inst.arg_count == 1) {
                    unsigned long long target = inst.args[0];
                    pc = (int)target;
                } else {
                    pc++;
                }
                break;
            default:
                /* 不明な命令は無視 */
                pc++;
                break;
        }
    }

    /* 最終的なレジスタの状態を出力 (各値は8桁の16進数) */
    for (int i = 0; i < 10; i++) {
        printf("R%d: 0x%08x\n", i, R[i]);
    }

    free(prog);
    return 0;
}

これを提出するとAcceptedが得られたが、実行に1.5秒程度かかっておりさらなる高速化が必要だと分かった。オーダーレベルでの高速化を考えると int sum=0; for(int i=0;i<n;++i)sum+=i; のようなコードがあった場合に高速に処理を行ってほしいが、自前のプログラムにこのような最適化を入れるのは困難に感じる。そこで、「入力命令列を等価なソースコードに変換してgccの -Ofast でコンパイルしたバイナリをJust-In-Timeで生成し、そのバイナリをexecすることで高速に結果を得る」という戦略で高速化を図ることにした。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <unistd.h>   // for mkdtemp
#include <errno.h>

#define MAX_LINE 256
#define INITIAL_PROG_SIZE 100

typedef enum {
    OP_1,
    OP_2,
    OP_3,
    OP_4,
    OP_5,
    OP_6,
    OP_7,
    OP_8,
    OP_9,
    OP_UNKNOWN
} Opcode;

typedef struct {
    Opcode opcode;
    int arg_count;
    unsigned long long args[3];
} Instruction;

Opcode parseOpcode(const char *s) {
    if(strcmp(s, "OP1") == 0)
        return OP_1;
    if(strcmp(s, "OP2") == 0)
        return OP_2;
    if(strcmp(s, "OP3") == 0)
        return OP_3;
    if(strcmp(s, "OP4") == 0)
        return OP_4;
    if(strcmp(s, "OP5") == 0)
        return OP_5;
    if(strcmp(s, "OP6") == 0)
        return OP_6;
    if(strcmp(s, "OP7") == 0)
        return OP_7;
    if(strcmp(s, "OP8") == 0)
        return OP_8;
    if(strcmp(s, "OP9") == 0)
        return OP_9;
    return OP_UNKNOWN;
}

int main(void) {
    char line[MAX_LINE];
    Instruction *prog = malloc(sizeof(Instruction) * INITIAL_PROG_SIZE);
    if (!prog) {
        fprintf(stderr, "Memory allocation failed\n");
        return 1;
    }
    int progSize = INITIAL_PROG_SIZE;
    int progCount = 0;

    while(fgets(line, sizeof(line), stdin)) {
        line[strcspn(line, "\r\n")] = '\0';
        if(strcmp(line, "__EOF__") == 0)
            break;
        if(strlen(line) == 0)
            continue;
        char opcodeStr[16];
        char argsStr[128] = {0};
        if(sscanf(line, "%15s %[^\n]", opcodeStr, argsStr) < 1)
            continue;
        Instruction inst;
        inst.opcode = parseOpcode(opcodeStr);
        inst.arg_count = 0;
        if(strlen(argsStr) > 0) {
            char *token = strtok(argsStr, ",");
            while(token != NULL && inst.arg_count < 3) {
                while(*token == ' ') token++;
                char *end = token + strlen(token) - 1;
                while(end > token && (*end == ' ')) {
                    *end = '\0';
                    end--;
                }
                inst.args[inst.arg_count] = strtoull(token, NULL, 10);
                inst.arg_count++;
                token = strtok(NULL, ",");
            }
        }
        if(progCount >= progSize) {
            progSize *= 2;
            prog = realloc(prog, sizeof(Instruction) * progSize);
            if (!prog) {
                fprintf(stderr, "Memory allocation failed\n");
                return 1;
            }
        }
        prog[progCount++] = inst;
    }

    char tmpDirTemplate[] = "/tmp/vmXXXXXX";
    char *tmpDir = mkdtemp(tmpDirTemplate);
    if(tmpDir == NULL) {
        fprintf(stderr, "Failed to create temporary directory: %s\n", strerror(errno));
        free(prog);
        return 2;
    }

    char sourcePath[256];
    char binaryPath[256];
    snprintf(sourcePath, sizeof(sourcePath), "%s/vm_generated.c", tmpDir);
    snprintf(binaryPath, sizeof(binaryPath), "%s/vm_generated", tmpDir);

    FILE *fp = fopen(sourcePath, "w");
    if(!fp) {
        fprintf(stderr, "Failed to open output file %s: %s\n", sourcePath, strerror(errno));
        free(prog);
        return 3;
    }
    fprintf(fp, "#include <stdio.h>\n");
    fprintf(fp, "#include <stdlib.h>\n");
    fprintf(fp, "#include <stdint.h>\n\n");
    fprintf(fp, "int main(void) {\n");
    fprintf(fp, "    int i;\n");
    fprintf(fp, "    unsigned int R[10] = {0};\n\n");

    for (int i = 0; i < progCount; i++) {
        fprintf(fp, "L%d:\n", i);
        Instruction inst = prog[i];
        switch(inst.opcode) {
            case OP_1:
                if(inst.arg_count == 2)
                    fprintf(fp, "    R[%llu] = %lluU;\n", inst.args[0], inst.args[1]);
                break;
            case OP_2:
                if(inst.arg_count == 2)
                    fprintf(fp, "    R[%llu] = R[%llu];\n", inst.args[0], inst.args[1]);
                break;
            case OP_3:
                if(inst.arg_count == 2)
                    fprintf(fp, "    R[%llu] = R[%llu] + R[%llu];\n", inst.args[0], inst.args[0], inst.args[1]);
                break;
            case OP_4:
                if(inst.arg_count == 2)
                    fprintf(fp, "    R[%llu] = R[%llu] - R[%llu];\n", inst.args[0], inst.args[0], inst.args[1]);
                break;
            case OP_5:
                if(inst.arg_count == 2)
                    fprintf(fp, "    R[%llu] = R[%llu] * R[%llu];\n", inst.args[0], inst.args[0], inst.args[1]);
                break;
            case OP_6:
                if(inst.arg_count == 2) {
                    fprintf(fp, "    R[%llu] = R[%llu] / R[%llu];\n", inst.args[0], inst.args[0], inst.args[1]);
                }
                break;
            case OP_7: {
                if(inst.arg_count == 3) {
                    unsigned long long target = inst.args[2];
                    if(target >= (unsigned long long)progCount)
                        target = progCount;  // Lend（LprogCount）に飛ばす
                    fprintf(fp, "    if(R[%llu] == R[%llu]) goto L%llu; else goto L%d;\n",
                            inst.args[0], inst.args[1], target, i+1);
                }
                break;
            }
            case OP_8: {
                if(inst.arg_count == 3) {
                    unsigned long long target = inst.args[2];
                    if(target >= (unsigned long long)progCount)
                        target = progCount;
                    fprintf(fp, "    if(R[%llu] != R[%llu]) goto L%llu; else goto L%d;\n",
                            inst.args[0], inst.args[1], target, i+1);
                }
                break;
            }
            case OP_9: {
                if(inst.arg_count == 1) {
                    unsigned long long target = inst.args[0];
                    if(target >= (unsigned long long)progCount)
                        target = progCount;
                    fprintf(fp, "    goto L%llu;\n", target);
                }
                break;
            }
            default:
                break;
        }
        fprintf(fp, "\n");
    }
    fprintf(fp, "L%d:\n", progCount);
    fprintf(fp, "    for(i = 0; i < 10; i++) {\n");
    fprintf(fp, "        printf(\"R%%d: 0x%%08x\\n\", i, R[i]);\n");
    fprintf(fp, "    }\n");
    fprintf(fp, "    return 0;\n");
    fprintf(fp, "}\n");
    fclose(fp);
    free(prog);

    char compileCmd[1024];
    snprintf(compileCmd, sizeof(compileCmd),
             "gcc -Ofast \"%s\" -o \"%s\"",
             sourcePath, binaryPath);
    if(system(compileCmd) != 0) {
         return 4;
    }
    char execCmd[512];
    snprintf(execCmd, sizeof(execCmd), "\"%s\"", binaryPath);
    return system(execCmd);
}

このアイデアが通ったら大ウケだろうな、と思って投げたが gcc の実行でのエラーが取れないまま一時間ほど経過し、その間に他チームとの点差がどんどん離れてしまった。これ以上の点数差がつくのは避けたいのでこの方針は一旦諦め、JITの代替方針として「mmapでrwx 領域を確保してそこに機械語を書きこみ実行する」という方針に切り替えることにした。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <sys/mman.h>
#include <errno.h>

#define MAX_LINE 256
#define INITIAL_PROG_SIZE 100

typedef enum {
    OP_1,
    OP_2,
    OP_3,
    OP_4,
    OP_5,
    OP_6,
    OP_7,
    OP_8,
    OP_9,
    OP_UNKNOWN
} Opcode;

typedef struct {
    Opcode opcode;
    int arg_count;
    unsigned long long args[3];  // 最大3個の引数を想定
} Instruction;

Opcode parseOpcode(const char *s) {
    if(strcmp(s, "OP1") == 0) return OP_1;
    if(strcmp(s, "OP2") == 0) return OP_2;
    if(strcmp(s, "OP3") == 0) return OP_3;
    if(strcmp(s, "OP4") == 0) return OP_4;
    if(strcmp(s, "OP5") == 0) return OP_5;
    if(strcmp(s, "OP6") == 0) return OP_6;
    if(strcmp(s, "OP7") == 0) return OP_7;
    if(strcmp(s, "OP8") == 0) return OP_8;
    if(strcmp(s, "OP9") == 0) return OP_9;
    return OP_UNKNOWN;
}

/* ジャンプ命令のパッチ情報 */
typedef struct {
    int patch_offset;  // コードバッファ内でジャンプ先の相対オフセットを書き込む位置
    int target_vm;     // ジャンプ先のVM命令番号
} JumpPatch;

/* マシンコード生成用バッファ */
typedef struct {
    unsigned char *buf;
    size_t capacity;
    size_t size;
} CodeBuffer;

void initCodeBuffer(CodeBuffer *cb, size_t capacity) {
    cb->buf = malloc(capacity);
    if (!cb->buf) {
        perror("malloc");
        exit(1);
    }
    cb->capacity = capacity;
    cb->size = 0;
}

void freeCodeBuffer(CodeBuffer *cb) {
    free(cb->buf);
}

void emit_byte(CodeBuffer *cb, unsigned char byte) {
    if (cb->size + 1 > cb->capacity) {
        fprintf(stderr, "Code buffer overflow\n");
        exit(1);
    }
    cb->buf[cb->size++] = byte;
}

void emit_int32(CodeBuffer *cb, int value) {
    if (cb->size + 4 > cb->capacity) {
        fprintf(stderr, "Code buffer overflow\n");
        exit(1);
    }
    memcpy(cb->buf + cb->size, &value, 4);
    cb->size += 4;
}

/* 十分なコード領域（バッファサイズ）を確保 */
#define CODE_BUF_SIZE (4096*4)

int main(void) {
    char line[MAX_LINE];
    Instruction *prog = malloc(sizeof(Instruction) * INITIAL_PROG_SIZE);
    if (!prog) {
        fprintf(stderr, "Memory allocation failed\n");
        return 1;
    }
    int progSize = INITIAL_PROG_SIZE;
    int progCount = 0;

    /* 入力からVM命令をパース */
    while(fgets(line, sizeof(line), stdin)) {
        line[strcspn(line, "\r\n")] = '\0';
        if(strcmp(line, "__EOF__") == 0) {
            break;
        }
        if(strlen(line) == 0) {
            continue;
        }
        char opcodeStr[16];
        char argsStr[128] = {0};
        if(sscanf(line, "%15s %[^\n]", opcodeStr, argsStr) < 1) {
            continue;
        }
        Instruction inst;
        inst.opcode = parseOpcode(opcodeStr);
        inst.arg_count = 0;
        if(strlen(argsStr) > 0) {
            char *token = strtok(argsStr, ",");
            while(token != NULL && inst.arg_count < 3) {
                while(*token == ' ') token++;
                char *end = token + strlen(token) - 1;
                while(end > token && (*end == ' ')) {
                    *end = '\0';
                    end--;
                }
                inst.args[inst.arg_count] = strtoull(token, NULL, 10);
                inst.arg_count++;
                token = strtok(NULL, ",");
            }
        }
        if(progCount >= progSize) {
            progSize *= 2;
            prog = realloc(prog, sizeof(Instruction) * progSize);
            if (!prog) {
                fprintf(stderr, "Memory allocation failed\n");
                return 1;
            }
        }
        prog[progCount++] = inst;
    }

    /* レジスタファイル R0～R9 の初期化 */
    unsigned int R[10] = {0};

    /* mmapで実行可能なRWX領域を確保 */
    void *code_mem = mmap(NULL, CODE_BUF_SIZE,
                          PROT_READ | PROT_WRITE | PROT_EXEC,
                          MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
    if (code_mem == MAP_FAILED) {
        perror("mmap");
        free(prog);
        return 1;
    }

    CodeBuffer cb;
    cb.buf = (unsigned char*)code_mem;
    cb.capacity = CODE_BUF_SIZE;
    cb.size = 0;

    /* 各VM命令に対応するコードバッファ内のオフセットを記録 */
    int *labels = calloc(progCount, sizeof(int));
    if (!labels) {
        perror("calloc");
        free(prog);
        munmap(code_mem, CODE_BUF_SIZE);
        return 1;
    }

    /*
      “i番目の命令が終了したら (pc=i+1)” を実現するため、
      i+1 の先頭アドレスも飛べるようにしたい。
      i+1 == progCount の場合は「ret」を入れて終了にする。
    */
    int *labelsNext = calloc(progCount, sizeof(int)); // 次命令(i+1)ラベル用

    /*
      ジャンプ命令のパッチ情報:
        - 条件が成立したときのtargetジャンプ
        - (OP7/OP8 の場合) 条件不成立の fallback ジャンプ (i+1)
        - (OP1～OP6など) 処理後の pc++ ジャンプ (i+1)
        - (OP9 の場合) 無条件ジャンプ先
    */
    // 仮に「命令ごとに最大2つのジャンプパッチがありうる」として十分なサイズを確保
    JumpPatch *patches = calloc(progCount * 2, sizeof(JumpPatch));
    int patchCount = 0;

    /*
      マシンコード生成:
        1. 各VM命令の先頭ラベルを記録(labels[i] = cb.size)
        2. 命令に対応するマシンコードを生成
        3. （OP7/OP8/OP9等でターゲットがある場合は jump命令 + パッチ）
        4. それ以外＆OP7/OP8で条件が成立しなかった場合に備えて i+1 へ飛ぶ命令を生成
           （i+1 >= progCount なら ret）
    */
    for (int i = 0; i < progCount; i++) {
        labels[i] = cb.size;  // このVM命令開始位置

        Instruction inst = prog[i];
        int nextIndex = i + 1;

        // ========== まず、この命令本来の処理を生成 ==========
        switch(inst.opcode) {
            case OP_1: {
                // R[arg0] = immediate (arg1)
                if(inst.arg_count == 2) {
                    int reg = (int)inst.args[0];
                    int imm = (int)inst.args[1];
                    // mov eax, imm  → B8 imm32
                    emit_byte(&cb, 0xB8);
                    emit_int32(&cb, imm);
                    // mov [rdi + reg*4], eax  → 89 87 disp32
                    emit_byte(&cb, 0x89);
                    emit_byte(&cb, 0x87);
                    int disp = reg * 4;
                    emit_int32(&cb, disp);
                }
                break;
            }
            case OP_2: {
                // R[arg0] = R[arg1]
                if(inst.arg_count == 2) {
                    int dest = (int)inst.args[0];
                    int src  = (int)inst.args[1];
                    // mov eax, [rdi + src*4]  → 8B 87 disp32
                    emit_byte(&cb, 0x8B);
                    emit_byte(&cb, 0x87);
                    int disp = src * 4;
                    emit_int32(&cb, disp);
                    // mov [rdi + dest*4], eax  → 89 87 disp32
                    emit_byte(&cb, 0x89);
                    emit_byte(&cb, 0x87);
                    disp = dest * 4;
                    emit_int32(&cb, disp);
                }
                break;
            }
            case OP_3: {
                // R[arg0] = R[arg0] + R[arg1]
                if(inst.arg_count == 2) {
                    int reg0 = (int)inst.args[0];
                    int reg1 = (int)inst.args[1];
                    // mov eax, [rdi + reg0*4]
                    emit_byte(&cb, 0x8B);
                    emit_byte(&cb, 0x87);
                    int disp = reg0 * 4;
                    emit_int32(&cb, disp);
                    // add eax, [rdi + reg1*4] → 03 87 disp32
                    emit_byte(&cb, 0x03);
                    emit_byte(&cb, 0x87);
                    disp = reg1 * 4;
                    emit_int32(&cb, disp);
                    // mov [rdi + reg0*4], eax
                    emit_byte(&cb, 0x89);
                    emit_byte(&cb, 0x87);
                    disp = reg0 * 4;
                    emit_int32(&cb, disp);
                }
                break;
            }
            case OP_4: {
                // R[arg0] = R[arg0] - R[arg1]
                if(inst.arg_count == 2) {
                    int reg0 = (int)inst.args[0];
                    int reg1 = (int)inst.args[1];
                    // mov eax, [rdi + reg0*4]
                    emit_byte(&cb, 0x8B);
                    emit_byte(&cb, 0x87);
                    int disp = reg0 * 4;
                    emit_int32(&cb, disp);
                    // sub eax, [rdi + reg1*4] → 2B 87 disp32
                    emit_byte(&cb, 0x2B);
                    emit_byte(&cb, 0x87);
                    disp = reg1 * 4;
                    emit_int32(&cb, disp);
                    // mov [rdi + reg0*4], eax
                    emit_byte(&cb, 0x89);
                    emit_byte(&cb, 0x87);
                    disp = reg0 * 4;
                    emit_int32(&cb, disp);
                }
                break;
            }
            case OP_5: {
                // R[arg0] = R[arg0] * R[arg1]
                if(inst.arg_count == 2) {
                    int reg0 = (int)inst.args[0];
                    int reg1 = (int)inst.args[1];
                    // mov eax, [rdi + reg0*4]
                    emit_byte(&cb, 0x8B);
                    emit_byte(&cb, 0x87);
                    int disp = reg0 * 4;
                    emit_int32(&cb, disp);
                    // imul eax, [rdi + reg1*4] → 0F AF 87 disp32
                    emit_byte(&cb, 0x0F);
                    emit_byte(&cb, 0xAF);
                    emit_byte(&cb, 0x87);
                    disp = reg1 * 4;
                    emit_int32(&cb, disp);
                    // mov [rdi + reg0*4], eax
                    emit_byte(&cb, 0x89);
                    emit_byte(&cb, 0x87);
                    disp = reg0 * 4;
                    emit_int32(&cb, disp);
                }
                break;
            }
            case OP_6: {
                // R[arg0] = R[arg0] / R[arg1] (整数除算)
                if(inst.arg_count == 2) {
                    int reg0 = (int)inst.args[0];
                    int reg1 = (int)inst.args[1];
                    // mov eax, [rdi + reg0*4]
                    emit_byte(&cb, 0x8B);
                    emit_byte(&cb, 0x87);
                    int disp = reg0 * 4;
                    emit_int32(&cb, disp);
                    // xor edx, edx  → 31 D2
                    emit_byte(&cb, 0x31);
                    emit_byte(&cb, 0xD2);
                    // mov ecx, [rdi + reg1*4] → 8B 8F disp32
                    emit_byte(&cb, 0x8B);
                    emit_byte(&cb, 0x8F);
                    disp = reg1 * 4;
                    emit_int32(&cb, disp);
                    // div ecx  → F7 F9 (edx:eax / ecx)
                    emit_byte(&cb, 0xF7);
                    emit_byte(&cb, 0xF9);
                    // mov [rdi + reg0*4], eax
                    emit_byte(&cb, 0x89);
                    emit_byte(&cb, 0x87);
                    disp = reg0 * 4;
                    emit_int32(&cb, disp);
                }
                break;
            }
            case OP_7: {
                // if (R[arg0] == R[arg1]) pc = arg2; else pc++;
                if(inst.arg_count == 3) {
                    int reg0 = (int)inst.args[0];
                    int reg1 = (int)inst.args[1];
                    int target = (int)inst.args[2];
                    // mov eax, [rdi + reg0*4]
                    emit_byte(&cb, 0x8B);
                    emit_byte(&cb, 0x87);
                    int disp = reg0 * 4;
                    emit_int32(&cb, disp);
                    // cmp eax, [rdi + reg1*4] → 3B 87 disp32
                    emit_byte(&cb, 0x3B);
                    emit_byte(&cb, 0x87);
                    disp = reg1 * 4;
                    emit_int32(&cb, disp);

                    // je <target_vm> → 0F 84 disp32
                    emit_byte(&cb, 0x0F);
                    emit_byte(&cb, 0x84);
                    int patch_offset = cb.size;
                    emit_int32(&cb, 0);  // 後で相対オフセットをパッチ
                    // 記録
                    patches[patchCount].patch_offset = patch_offset;
                    patches[patchCount].target_vm = target;
                    patchCount++;
                }
                break;
            }
            case OP_8: {
                // if (R[arg0] != R[arg1]) pc = arg2; else pc++;
                if(inst.arg_count == 3) {
                    int reg0 = (int)inst.args[0];
                    int reg1 = (int)inst.args[1];
                    int target = (int)inst.args[2];
                    // mov eax, [rdi + reg0*4]
                    emit_byte(&cb, 0x8B);
                    emit_byte(&cb, 0x87);
                    int disp = reg0 * 4;
                    emit_int32(&cb, disp);
                    // cmp eax, [rdi + reg1*4]
                    emit_byte(&cb, 0x3B);
                    emit_byte(&cb, 0x87);
                    disp = reg1 * 4;
                    emit_int32(&cb, disp);

                    // jne <target_vm> → 0F 85 disp32
                    emit_byte(&cb, 0x0F);
                    emit_byte(&cb, 0x85);
                    int patch_offset = cb.size;
                    emit_int32(&cb, 0);  // 後でパッチ
                    // 記録
                    patches[patchCount].patch_offset = patch_offset;
                    patches[patchCount].target_vm = target;
                    patchCount++;
                }
                break;
            }
            case OP_9: {
                // pc = arg0; (無条件ジャンプ)
                if(inst.arg_count == 1) {
                    int target = (int)inst.args[0];
                    // jmp <target> → E9 disp32
                    emit_byte(&cb, 0xE9);
                    int patch_offset = cb.size;
                    emit_int32(&cb, 0);  // 後でパッチ
                    patches[patchCount].patch_offset = patch_offset;
                    patches[patchCount].target_vm = target;
                    patchCount++;
                }
                break;
            }
            default:
                // 不明な命令は何もしない
                break;
        }

        // ========== ここから「pc++」をエミュレートするジャンプを生成 ==========

        // OP9（無条件ジャンプ）は、上の生成だけで「常に target へ飛ぶ」ので、
        // ここで fallback ジャンプを入れてしまうと 2重ジャンプになるためスキップ。
        if (inst.opcode == OP_9) {
            // 何もしない → この命令は終了
            // つまり、次の命令へは進まない (pc++しない)
            continue;
        }

        if (nextIndex >= progCount) {
            // i+1 がプログラム末尾を超えるなら → ここで ret して終了
            emit_byte(&cb, 0xC3); // ret
        } else {
            // jmp <i+1> → E9 disp32
            emit_byte(&cb, 0xE9);
            int patch_offset = cb.size;
            emit_int32(&cb, 0);  // 後でパッチ
            patches[patchCount].patch_offset = patch_offset;
            patches[patchCount].target_vm = nextIndex;
            patchCount++;
        }
    }

    // 生成コードの末尾に ret を置いておく (念のため)
    emit_byte(&cb, 0xC3);

    // ========== ジャンプ先のパッチ ==========

    // labels[i] が「i番目のVM命令先頭オフセット」
    // patches[] に格納された各ジャンプ先 target_vm のラベルを使って
    // 相対オフセットを埋め込む
    for (int i = 0; i < patchCount; i++) {
        int target_vm = patches[i].target_vm;
        int patch_loc = patches[i].patch_offset;

        // 「progCount 番外」や「負数」をターゲットにしたら終了動作にしてもよいが、
        // ここでは簡単にエラーにしておく
        if (target_vm < 0 || target_vm > progCount) {
            // target_vm == progCount なら "終了" として ret へ飛ばす……
            // などの処理を入れてもよい
            fprintf(stderr, "Invalid jump target: %d\n", target_vm);
            continue;
        }

        // ターゲットがプログラム末尾 (== progCount) の場合は
        // 「ret 相当の場所へ飛ぶ」ようにパッチしてもよい。
        // 今回は簡単のため、末尾に emit_byte(&cb, 0xC3) した位置を使うか、
        // あるいは独自に「labels[progCount] = cb.size; // ret」みたいに用意してもOK
        int target_offset;
        if (target_vm == progCount) {
            // “末尾の ret” が cb.size-1 と確定しているならそこへ飛ばす
            // あるいは labels[progCount] を作っておいてそこに飛ばす
            target_offset = (int)(cb.size - 1); // 仮に末尾1バイトが ret
        } else {
            target_offset = labels[target_vm];
        }

        // 相対オフセット = (ジャンプ先) - (この命令の次のアドレス)
        int rel = target_offset - (patch_loc + 4);
        memcpy(cb.buf + patch_loc, &rel, 4);
    }

    /* 生成したコード領域を関数ポインタにキャストして実行 */
    typedef void (*jit_func_t)(unsigned int *);
    jit_func_t func = (jit_func_t)cb.buf;
    func(R);

    /* 最終的なレジスタの状態を出力 */
    for (int i = 0; i < 10; i++) {
        printf("R%d: 0x%08x\n", i, R[i]);
    }

    free(prog);
    free(labelsNext);
    free(labels);
    free(patches);
    munmap(code_mem, CODE_BUF_SIZE);

    return 0;
}

結果的にこれが8チーム中2位ぐらいの点数を出してくれて、大爆死をギリギリ免れることができた。
以下振り返り。この問題については反省する箇所が結構多い。まず、問題の意図を「オーダーレベルの最適化ができる例に対する高速化ができるか」というものだと誤解してしまい、その部分の最適化のためにgcc経由の比較的大がかりな解法に走ってしまった点が一点。また、Dockerfile配布もない環境で成功するか分からない方針に固執してしまった点、そこからの切り替えが遅かった点も反省。一旦mmap解法を出してみて良かったらそれで留める、という判断ができても良かったのではないかと思う。

Round 4

ここからはDay 2の問題。まずはghidraで読んでみて内容を確認すると、Could not load PyInstaller's embedded PKG archive from the executable (%s)\n のような文字列を確認できた。どうやらPyInstallerによって生成された実行ファイルのようで、調べてみるとバイナリ中にzlib headerから始まるPyInstallerのpkgファイルと思わしき部分を確認できた。そこで、Docker内にPyInstallerの実行環境を整備し¹⁰、pyi-archive_viewer によって main のバイトコードを読んでChatGPTに渡すと、main が以下のような処理を行っていることが分かった。

import hashlib
def crack(data_prefix: bytes, hash_prefix: str, offset: int, f) -> bytes:
    for c1 in range(256):
        for c2 in range(256):
            for c3 in range(256):
                for c4 in range(256):
                    data = bytes([c1, c2, c3, c4])
                    h = f(data_prefix + data).hexdigest()
                    if h[offset : offset + len(hash_prefix)] == hash_prefix.lower():
                        return data 

if __name__ == "__main__":
    args = input().split()
    data_prefix = bytes.fromhex(args[0])  
    hash_prefix = args[1]             
    offset = int(args[2])        

    f = hashlib.sha256

    if len(args) > 3:
        if args[3] == 'md5':
            f = hashlib.md5
        elif args[3] == 'sha512':
            f = hashlib.sha512

    print(crack(data_prefix, hash_prefix, offset, f).hex())

hash(data_pref + ABCD)[offset:offset+hash_pref] == hash_pref となるような ABCD を求める問題であり、一メモ化などによる高速化のしようが無いように見える。
打つ手がないのでとりあえずChatGPTにCのアルゴリズムを書いてもらい¹¹提出するとそこそこいい順位が取れたので、それで終了した。
ちなみに、想定は並列化とOpenSSLを使うものだったらしい。前日のgccで痛い目を見たこともありpureなC以外は書かず難しいこともしないという意思があったため、そこまでできないのはまあしょうがなかったのではないかと思う。 sshやDockerなどでリモートの実行環境をもっと詳しく確認できれば（＋さらに余力があれば）色々やる余地があったと思うので、実行環境に近いサンドボックスやコードテスト環境があれば嬉しかったなあと思わなくもない¹²。

Round 5

Ghidraでデコンパイルしたmainの中身がこんな感じ。

undefined8 main(void)

{
  int iVar1;
  undefined8 uVar2;
  long in_FS_OFFSET;
  ulong local_58;
  undefined8 local_50;
  ulong local_48;
  ulong local_40;
  ulong local_38;
  ulong local_30;
  ulong local_28;
  ulong local_20;
  long local_18;
  long local_10;
  
  local_10 = *(long *)(in_FS_OFFSET + 0x28);
  local_18 = luaL_newstate();
  if (local_18 == 0) {
    uVar2 = 1;
  }
  else {
    iVar1 = luaL_loadbufferx(local_18,&bytecode,0xfffffffff2e80000,"embedded",0);
    if ((iVar1 == 0) && (iVar1 = lua_pcallk(local_18,0,0xffffffff,0,0,0), iVar1 == 0)) {
      __isoc99_scanf(&%lu,&local_58);
      lua_getglobal(local_18,&G);
      lua_getglobal(local_18,&F);
      lua_getglobal(local_18,&F);
      lua_createtable(local_18,local_58 & 0xffffffff,0);
      for (local_48 = 0; local_48 < local_58; local_48 = local_48 + 1) {
        lua_createtable(local_18,local_58 & 0xffffffff,0);
        for (local_40 = 0; local_40 < local_58; local_40 = local_40 + 1) {
          __isoc99_scanf(&%lld,&local_50);
          lua_pushinteger(local_18,local_50);
          lua_rawseti(local_18,0xfffffffe,local_40 + 1);
        }
        lua_rawseti(local_18,0xfffffffe,local_48 + 1);
      }
      lua_createtable(local_18,local_58 & 0xffffffff,0);
      for (local_38 = 0; local_38 < local_58; local_38 = local_38 + 1) {
        lua_createtable(local_18,local_58 & 0xffffffff,0);
        for (local_30 = 0; local_30 < local_58; local_30 = local_30 + 1) {
          __isoc99_scanf(&%lld,&local_50);
          lua_pushinteger(local_18,local_50);
          lua_rawseti(local_18,0xfffffffe,local_30 + 1);
        }
        lua_rawseti(local_18,0xfffffffe,local_38 + 1);
      }
      iVar1 = lua_pcallk(local_18,2,1,0,0,0);
      if (iVar1 == 0) {
        lua_pushvalue(local_18,0xffffffff);
        iVar1 = lua_pcallk(local_18,2,1,0,0,0);
        if ((iVar1 == 0) && (iVar1 = lua_pcallk(local_18,1,1,0,0,0), iVar1 == 0)) {
          for (local_28 = 0; local_28 < local_58; local_28 = local_28 + 1) {
            lua_rawgeti(local_18,0xffffffff,local_28 + 1);
            putchar(0x5b);
            for (local_20 = 0; local_20 < local_58; local_20 = local_20 + 1) {
              lua_rawgeti(local_18,0xffffffff,local_20 + 1);
              if (local_20 == local_58 - 1) {
                uVar2 = lua_tointegerx(local_18,0xffffffff,0);
                printf("%lld",uVar2);
              }
              else {
                uVar2 = lua_tointegerx(local_18,0xffffffff,0);
                printf("%lld, ",uVar2);
              }
              lua_settop(local_18,0xfffffffe);
            }
            puts("]");
            lua_settop(local_18,0xfffffffe);
          }
        }
      }
    }
    lua_close(local_18);
    uVar2 = 0;
  }
  if (local_10 == *(long *)(in_FS_OFFSET + 0x28)) {
    return uVar2;
  }
                    /* WARNING: Subroutine does not return */
  __stack_chk_fail();
}

また他言語に投げるやつか・・・と思いながら bytecode の部分を見てみるとLuaのバイトコードがそのまま置いてあり、それを luac5.4 -l -l lua_bytecode でdisassembleしてから例によってChatGPTに読んでもらうと、どうやら行列積演算のvariantのような処理を行っているらしいということが分かった。まずはCへの移植を行い、その後はループで処理されている単純な足し算を掛け算に置き換えて $O(n^4)$ から $O(n^3)$ に高速化した。そこからはキャッシュラインを意識して行列を転置したり行列の再確保を行わないようにしたりという細々とした最適化を行い、最終的にはそこそこの順位でフィニッシュすることができた。

#include <stdio.h>
#include <stdlib.h>

/* 行列の転置（1次元配列として連続確保された n×n 行列）をインプレースで実施 */
void inplace_transpose(int n, long long *M) {
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            long long temp = M[i * n + j];
            M[i * n + j] = M[j * n + i];
            M[j * n + i] = temp;
        }
    }
}

/* 行列 B の転置を buf にコピーする */
void transpose_copy(int n, const long long *B, long long *buf) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            buf[j * n + i] = B[i * n + j];
        }
    }
}

/* 行列積を計算する関数
   ・A, B, C はそれぞれ連続確保された n×n 行列（1次元配列）
   ・buf は B の転置を一時保存するためのバッファ */
void matmul(int n, const long long *A, const long long *B, long long *C, long long *buf) {
    // B の転置を buf にコピー
    transpose_copy(n, B, buf);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            long long sum = 0;
            for (int k = 0; k < n; k++) {
                sum += A[i * n + k] * buf[j * n + k];
            }
            C[i * n + j] = sum;
        }
    }
}

/* 行列を指定形式で出力 */
void print_matrix(int n, const long long *M) {
    for (int i = 0; i < n; i++) {
        printf("[");
        for (int j = 0; j < n; j++) {
            printf("%lld", M[i * n + j]);
            if (j < n - 1) {
                printf(", ");
            }
        }
        printf("]\n");
    }
}

int main(void) {
    int n;
    if (scanf("%d", &n) != 1) {
        fprintf(stderr, "行列サイズの読み込みに失敗\n");
        return EXIT_FAILURE;
    }
    
    // 入力用行列 A, B、中間計算用行列 X、転置用一時バッファ buf の4つを確保
    long long *A   = malloc(n * n * sizeof(long long));
    long long *B   = malloc(n * n * sizeof(long long));
    long long *X   = malloc(n * n * sizeof(long long));
    long long *buf = malloc(n * n * sizeof(long long));
    if (!A || !B || !X || !buf) {
        fprintf(stderr, "メモリ確保失敗\n");
        exit(EXIT_FAILURE);
    }
    
    // 行列 A の読み込み
    for (int i = 0; i < n * n; i++) {
        if (scanf("%lld", &A[i]) != 1) {
            fprintf(stderr, "行列 A の読み込みに失敗\n");
            return EXIT_FAILURE;
        }
    }
    
    // 行列 B の読み込み
    for (int i = 0; i < n * n; i++) {
        if (scanf("%lld", &B[i]) != 1) {
            fprintf(stderr, "行列 B の読み込みに失敗\n");
            return EXIT_FAILURE;
        }
    }
    
    matmul(n, A, B, X, buf);
    
    matmul(n, X, X, B, buf);
    
    inplace_transpose(n, B);
    
    print_matrix(n, B);
    return 0;
}

想定解はSIMDだったらしい。まあ確かにそうだなあと思いつつも、やっぱり変なことをしてエラー落ちのまま点を落としてしまうのは怖いのであまり思い切ったことはできなかった。

Round 6

コンテスト残り数時間でHardware問の挑戦権も残っている上に解きたい問題を抱えており、一瞬で高速化のネタが浮かぶようなものでもなかったため手を付けずに撤退。

実は非想定だったらしい。↩
RITE0300\x00\x05... のような感じでそのままバイトコードになっていたのだが、最初に見たときはnull文字で区切れているせいで先頭8文字の存在にしか気づけなかった。そのまま何も分からないまま数時間が経過し、初日の夜にもやし先輩に指摘して頂き初めて気づいた。大反省・・・↩
今回が初めての決勝進出なので実機を触るHardware問も初めて。コンテスト開始直前に現物が配布されたときはかなりワクワクした。↩
challnge roomは問題ページを介した事前予約制になっていた。BunkyoWesternsなどのSECCON慣れしているっぽいチームが爆速で両日分のできる限り遅いtime windowを確保していて流石。↩
スタッフの人たちに「こいつら何も説明読まないまま来ちゃったんだろうな・・・」と思われる感じのムーブをしていて、今思い返すとちょっと恥ずかしい。↩
環境構築やドライバのインストール、シリアル出力のボーレート設定など↩
一部ピンはHigh/Lowのどちらでもよい↩
慣れているチームは最速で最後のtime windowを取りに行っていたため、結果的に予約枠取りバトルで出遅れた我々がいち早くフラグを提出することになった。↩
うろ覚えなのでもしかしたら違うところがあるかも↩
配布バイナリがPython3.12 (glibc 2.38) のもので環境構築に手間取ってしまった。そろそろUbuntu 22.04をやめるべきな気がする。↩
合計で600行ぐらいあるmd5/sha256/sha512のコードを一瞬で出してくれた。↩
Rulesのところにめちゃくちゃ詳しく書いてあるのを見落としているだけだったらすみません・・・↩