株式会社Scalarの技術顧問に就任しました

2021年度IPA未踏IT人材発掘・育成事業公募概要の竹迫PMメッセージの中で略歴として記載のある通り、2020年6月より株式会社Scalarの技術顧問に就任しました。

株式会社Scalarの技術顧問として、セキュリティ技術やエンジニア組織に関する相談や方針・設計に関するレビューを行うパートタイムのアドバイザー契約が中心となりますが、急成長するITベンチャーでよく発生する組織課題の解決や運営の相談にも乗っています。技術発のベンチャー事業が成長するにつれて0→1、1→10、10→100のそれぞれのフェーズにおいて、組織と事業のギャップを乗り越えていく必要がありますが、将来スケールした100のフェーズの景色を明確にビジョンとして持っているScalarの共同創業者CEO深津さん・山田さんのお二方に惹かれ、技術顧問を引き受けることに決めました。

当初お話をいただいた時点ではまだ緊急事態宣言は発令されておらず、初回の打ち合わせだけ実際にオフィスに出向いて対面でミーティングする機会があったのですが、出社したのはその1度きりで後は全部Zoomでの会議になりました。新型コロナウイルス感染拡大防止のため日本の働き方が大きく変わる中、色々調整いただいて、本業の仕事はそのままで、月数回のフルリモートワークで兼業として携わっています。

なぜ?国産検索エンジン開発からデータベース技術への興味

1997年、最初の私のIT業界のファーストキャリアは大学在学中にアルバイトした広島にある日本ヒューレット・パッカードの子会社でのソフトウェア開発(ECサイト構築、社内業務システム開発、SSO基盤開発、Namazu for Win32検索システムの構築など)で、当時はHP-UX上に基幹系システムのOracleデータベースを構築する百戦錬磨の精鋭部隊が近くにいたり、Intelとhpが共同開発していたItaniumプロセッサーコンパイラやOS上で発生する様々な競合問題をトラブルシュートをするサポート部隊がいたりと、非常に貴重な体験を積むことができました。当時のhpはミドルウェアから下の低レイヤーまでネットワーク・サーバ・OS・ストレージも自社開発のハードウェアのフルスタックな技術で課題解決できる強みを持っていました。ただ顧客の新規ソリューション提案においては自社のハードウェアを絡めた範囲に縛られていたりという制約もあって、次は自由度の高い独立系のソフトウェアベンチャーに身を置きたいという思いがあり、次はエンタープライズ向けのグループウェアの開発に挑戦していたドリームアーツという会社に就職することにしました。そこで開発していたプロダクトは顧客のニーズ毎にOraclePostgreSQL、PowerGres Plusをバンクエンドとして選べて(古いDB2の対応コードも少し残っていました)、LinuxのAPサーバを複数台置いてmod_perlでスケールアウト出来るようなアーキテクチャとして設計開発していました。グループウェアは情報系システムではあるものの、バックエンドはミッションクリティカルなOracle RACの構成に対応できるようにしたりと、エンタープライズな運用文化にも対峙することができました。当時はRDBMSのblobの性能に課題があり、大きなファイルは裏側のNFSサーバに格納するようなシステム構造が残っており、性能要件と一貫性のバランスを保つのが非常に難しかった記憶があります。運用現場で発生する緊急度の高い課題に対して圧倒的当事者意識で対応することもあり多くの経験を積むことが出来ましたが、運用と開発のもっと前段階のソフトウェア設計時点で解決できるアーキテクチャを中長期のR&Dとして考えられないかという思いが芽生え、サイボウズ・ラボに転職しました。

そこで機会をいただいてセキュリティ&プログラミングキャンプ(一時期データベース開発者コースも検討されていたこともありました)やShibuya.pmなどのコミュニティ活動に関わるようになり、現在の株式会社Scalar共同創業者の山田浩之さん(CEO兼CTO)と知り合うきっかけがありました。2008年のIPA未踏プロジェクトで山田さんが全文検索エンジンLux IOの開発をしていたときに国産ストレージエンジン、データベースマネージャ開発コミュニティの一員として知り合っていたのですが(当時は経済産業省が国産検索エンジン開発を支援する3年間の情報大航海プロジェクトがあり、産学官の相互人材交流が盛んでした)、昨年2月頃に「最近、改ざん検知性(ビザンチン故障検知性)を持ったデータベースを研究・開発しているスタートアップを始めたんだけど」とお誘いのお話をいただいて、今では非常に珍しくなったデータベースのコアな技術者(※喜連川先生曰く絶滅危惧種)が株式会社Scalarに複数人在籍していることと、今後の事業の発展性・スケーラビリティに非常に興味があったので「ぜひ」と二つ返事で一緒に関わらせていただくことになりました。

Scalar DB 分散データベースマネージャをOSSで公開

株式会社Scalarの主力プロダクトの一つとして開発しているScalar DBはACID準拠でない分散データベースやストレージエンジンをACID準拠にするJavaライブラリで、オープンソースApache License 2.0)と商用ライセンスの元で公開されています。現時点でScalar DBが対応しているバックエンドの分散ストレージはCassandra、Azure Cosmos DB、Amazon DynamoDB(2021年2月時点)ですが、抽象化されたアーキテクチャとして設計されているため、対応コードを実装すれば理論的にはその他のデータベースにも対応できます。

github.com

先日のApacheCon@Home 2020でCassandra上でどのように分散トランザクションを実現しているかScalarのエンジニアによる国際発表がありました。

このレイヤーでトランザクションが担保できれば、顧客サイドでのバックエンドのデータベースの選択肢に自由が生まれるので(商用のRDBMSの他にNoSQLも選択できる)、エンタープライズの現場に導入するときのスケーラビリティと信頼性の技術課題が同時に解決できるメリットが大きく、将来性の非常に高いプロダクトだと思っています。

このアイディアを聞いた時は、20年前の商用tuxedoに対抗したOpen OLTP system MONTSUQIを思い出しました。信頼性の非常に高い大型汎用機用トランザクションモニタと最新ののモダンなクラウドの分散データベース技術が交差する温故知新なワクワクする技術です。

Scalar DL 改ざん耐性とスケーラビリティの両立を実現

株式会社Scalarが開発するもう一つの主力プロダクトScalar DLは、電子署名が付与されたスマートコントラクトを分散トランザクションの形式で実行する分散型台帳ソフトウェアです。

高い改ざん耐性とスケーラビリティの両立を実現する独自の分散データベース管理技術で、帳簿など保管義務がある書類をデジタル化して改ざんされていないことを証明する必要のあるユースケースに適しています。主なアプリケーションとして、エンタープライズ向けの契約管理・情報銀行・企業間連携システム・ERPなどへの応用があります。

Scalar DL サンプルアプリケーション

分散型台帳ソフトウェアScalar DLでいくつかのアプリケーションを実装するサンプルはQiita上に記事があります。

qiita.com

モダンな技術スタックで基盤の技術を構築しているので、実際に手元でコードを動かしてみると非常に面白いです。

余談

(本業ではまだ紙の書類への捺印のために毎月オフィスに出社する必要があるのですが)株式会社Scalarとの契約ではクラウド電子署名サービスを用いて業務委託契約書を締結しました。私の中で電子署名は初めての体験でしたが、こういった新しいことを積極的に会社の業務として取り入れていくバックオフィスの柔軟かつ堅実な姿勢に感銘を受けました。今後、日本のデジタルトランスフォーメーション(DX)を進めていくためには、他社の技術も含めて、従来の紙ではない新しい電子契約の在り方をドッグフーディングして自分の身の回りでできることから地道に置き換えていくことが重要だと思っています。

Scalarでは人材を募集しています

そんな株式会社Scalarではエンジニアリングチームで一緒に働くメンバーを絶賛募集中です。データベースのコアな技術に携わりたい人、SREでクラウドの最新技術に触りたい人、コアなチームをまとめて価値を最大化したいエンジニアリングマネージャーなど様々なポジションがあります。実際どんな感じなのか、質問や相談がありましたら、ぜひ気軽に竹迫のTwitterまで直接DMください。

https://angel.co/company/scalar-inc/jobs

今後Scalarではデータベース系の学会へのスポンサーや、論文発表なども積極的に取り組んでいきたいと思います。よろしくお願いいたします。

Donuts Radio #003【竹迫良範さん】podcast出演

Donuts Radio(根岸心さんが聞くエンジニアの人生の軌跡。 子ども時代の貴重なエピソードから、心に秘めている将来の展望までとことん語りつくすpodcast)に出演しました。

waffles.donuts.ne.jp

8人きょうだいの長男として大家族で育った竹迫さんは、中学生の頃、父親が購入したパソコンを譲り受け、独学でゲームを作成したことでプログラミングと出会いました。一方で幼少期の入院経験から医者を志したこともあったといいます。エンジニアと医者、一見するとかけ離れた職業ですが、そこには意外な共通点が…?! 大家族ならではの家庭事情や、数々の偶然が重なって広島から上京した経緯など、根岸も知らなかった話はもちろん、「若い人が挑戦できる場所」を積極的に提供したいと語る竹迫さんの、熱意あふれる対談となりました。

f:id:TAKESAKO:20210212172104j:plain
Donuts Radio #003【竹迫良範さん】

ドメイン名にwafflesが入っているのが非常に良いですね。わっふるわっふる。

情熱大陸#1140 登大遊さん(サイバー技術開発集団)

2021年2月7日(日)23:00~毎日放送情熱大陸」で日本が誇るIPA未踏OB天才プログラマー登さんがピックアップされていました。本邦初公開の貴重な映像もあり、必見です。

情熱大陸#1140 登大遊IPANTT東日本/サイバー技術開発集団 統括)コロナ禍であえぐ全国の自治体を救え!天才プログラマーが挑む緊急テレワークシステム開発

放送を見逃した方は1週間ほどTVerで視聴できるので、ぜひご覧ください。
※ 2月14日(日) 22:59 終了予定 tver.jp

放送中のTwitterのまとめ togetter.com

主役は登さんはじめシンテレワークシステムの構築に貢献されたNTT東日本IPA関係者・J-LISの皆さんですが、サイバー技術研究室のモブ役として少しだけ竹迫も映っていました。

f:id:TAKESAKO:20210210000326j:plain
けしからん定例会議
本当にありがとうございました。けしからんをスローガンに挑戦し続けたいと思います。

SECCON 2019 Final write-up (Factor the flag, Bad Mouse)

SECCON 2019 Finalでは、サーバ6のJeopardy問題2つ「Factor the flag」と「Bad Mouse」を作問しましたので、出題者の立場からの想定解write-upを公開します。

今年はCTFの競技ネットワークをクラウド環境に移行チャレンジした背景もあり、私が担当する出題テーマとして、ネットワークに依存せず、軽量で小さな問題であることを意識して作問しました。(万が一ネットワークトラブルがあっても解ける、お持ち帰りでも解析できる)

Jeopardy 6-3: Factor the flag

問題文:

I hid the SECCON{} flag in a big prime number.

1401111111111111111111111111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111111111111111111111111112220791111111111111111
1111111111111111111111111111122207911223089031988903088023088023088920012001200
2319889030879222080230880230890319887911122318879211992120012999912120013000013
0000131008920012001199121200120022089200130000119912119911121200120011992119912
1199121199121199121200130101000012001199121200120930009200130000119921199111121
2001200119921199121199121199121199121200130010208012002318879112120929999112120
9299991212103188892001200119912230890318889199121199121200130000131007911112119
9212092091991211992119912120013010111188791222079112129999121199121199121200130
0001200119911121200120012091992119921299992120013010099991112119911112129999121
1991211991212001300001200120012001209199223198889199212001209199213010099991112
1199212001299991212001300001300001300001200120012001299991111212091991212001209
1992130100999911121199122308903198890308802308802308892001200119922308903198879
2121031988903088011992130100999911121199111111111111111111111111111111111111111
2220791111111111111111111111111111111111111111111112220791111111111111111111111
1111111111111111111111111111111111111111111111111111111111111111111111111239593

出題の意図:

64bitを超える巨大な数に対して、素因数分解をパッとできるプログラム・ツールが手元に揃っているかどうかというサービス問題です。

解法:

素因数分解(factor)すると 13 x 97 x 1261桁の素数の掛け算となります。 1261桁の素数は、奇遇にもちょうど97文字で折り返すと13行になります。

1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111111111991111111111111111111111111111111111111111111111111991111
1199911999991199911199911199911911191119111999991199911119911199911199911999991111111999911119111
1911191911111911191911191911191991191119111911111911191119911911191911191111191111111911191119111
1911111911111911111911111911191919191119111911111911191191911911191911191111911111111911191119111
1911111911111911111911111911191911991119111999911111191191911111191191911111911999911911191119111
1199911999911911111911111911191911191991111111191111911911911111911119111119111919191999911111991
1111191911111911111911111911191911191119111111191119111911911119111191911119111919191911111119111
1111191911111911111911111911191911191119111911191191111999991191111911191191111919191911111119111
1911191911111911191911191911191911191119111911191911111111911911111911191191111919191911111119111
1199911999991199911199911199911911191119111199911999991111911999991199911191111919191911111119111
1111111111111111111111111111111111111111991111111111111111111111111111111111111111111111111991111
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111213

フォントを小さくして1と9の文字を白黒のドットに見立てるとSECCON{524287mP}のフラグが見えます。 ペイントソフトで塗りつぶししても良いです。

スクリプト:find_the_factor.pl

素因数分解をして1を.に9を#に置き換えて表示する攻略スクリプトPerlワンライナーに近い記法で書いてみます。

#!/usr/bin/perl
use bigint try => 'GMP';
use Math::Prime::Util ':all';
my $p=join"",<DATA>; $p=~s/\s//g;
print join" x\n",map{s/(\d{97})/$1\n/g;s/9/#/g;s/1/./g;$_;}factor($p);
__DATA__
1401111111111111111111111111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111111111111111111111111112220791111111111111111
1111111111111111111111111111122207911223089031988903088023088023088920012001200
2319889030879222080230880230890319887911122318879211992120012999912120013000013
0000131008920012001199121200120022089200130000119912119911121200120011992119912
1199121199121199121200130101000012001199121200120930009200130000119921199111121
2001200119921199121199121199121199121200130010208012002318879112120929999112120
9299991212103188892001200119912230890318889199121199121200130000131007911112119
9212092091991211992119912120013010111188791222079112129999121199121199121200130
0001200119911121200120012091992119921299992120013010099991112119911112129999121
1991211991212001300001200120012001209199223198889199212001209199213010099991112
1199212001299991212001300001300001300001200120012001299991111212091991212001209
1992130100999911121199122308903198890308802308802308892001200119922308903198879
2121031988903088011992130100999911121199111111111111111111111111111111111111111
2220791111111111111111111111111111111111111111111112220791111111111111111111111
1111111111111111111111111111111111111111111111111111111111111111111111111239593

実行結果

$ sudo apt install libmath-prime-util-gmp-perl
$ perl find_the_factor.pl
.3 x
#7 x
.................................................................................................
........................................##.................................................##....
..###..#####..###...###...###..#...#...#...#####..###....##...###...###..#####.......####....#...
.#...#.#.....#...#.#...#.#...#.##..#...#...#.....#...#...##..#...#.#...#.....#.......#...#...#...
.#.....#.....#.....#.....#...#.#.#.#...#...#.....#...#..#.#..#...#.#...#....#........#...#...#...
.#.....#.....#.....#.....#...#.#..##...#...####......#..#.#......#..#.#.....#..####..#...#...#...
..###..####..#.....#.....#...#.#...#.##........#....#..#..#.....#....#.....#...#.#.#.####.....##.
.....#.#.....#.....#.....#...#.#...#...#.......#...#...#..#....#....#.#....#...#.#.#.#.......#...
.....#.#.....#.....#.....#...#.#...#...#...#...#..#....#####..#....#...#..#....#.#.#.#.......#...
.#...#.#.....#...#.#...#.#...#.#...#...#...#...#.#........#..#.....#...#..#....#.#.#.#.......#...
..###..#####..###...###...###..#...#...#....###..#####....#..#####..###...#....#.#.#.#.......#...
........................................##.................................................##....
..............................................................................................2.3

正解:SECCON{524287mP}

解けたチーム数:国内:15チーム、国際1314チーム

決勝に出場しても得点がゼロだと職場に戻れない、という過去の出場者の声を反映したサービス問題でした。

実際のところ出場した全チームが解けている問題で、練習問題相当として出題しました。簡単ですね。

回答者:@stereotype32さんによるwrite-up https://pub.harold.kim/ctf/SECCON-CTF-Finals-2019/chal6-challenges/factortheflag.html

Jeopardy 6-4: Bad Mouse

問題文:

Hack the USB HID device. (配布デバイスの写真)

No claim no return. Firmware dump list is as follows:

:10000000A5C1C9C1F5C1C7C194C5C5C1C4C1C3C1DA
:10001000C2C1C1C1C0C1BFC1BEC1BDC1BCC13D3EE5
:100020003F4061426344415569486B4A4B4C4D4ED9
:1000300051504F61535C5556575859606B656D6709
:100040006F69417163644579774C794E7B505D4DA2
:100050006F707172737475767778797A7B7C7D7E38
:100060004F487251434C45464748694E5B555D5772
:100070005F597158535455565758595A5B5C5D5ED9
:100080005F607D66456C476E49706D716B6C6B7D12
:100090005178537A557C777E777875417D443F4619
:1000A000414845464344414D49504B524D545152AD
:1000B0004F504D59555C575E596055615B5C5B6DA7
:(省略)
:100F90000895EE0FFF1F0590F491E02D0994FB01D9
:100FA000DC0104C08D910190801921F44150504022
:0C0FB000C8F7881B990B0895F894FFCF38
:040FBC000105FF5AD2
:00000001FF

ダウンロード先:badmouse.hex https://gist.githubusercontent.com/takesako/9171fd0111b37dcc9ee775ae23f3fad2/raw/16f10cc55bc3106f57d66f3c1cddb20d650affb6/badmouse.hex

出題の意図:

AVRアセンブリ読解、ファームウェアリバースエンジニアリング問題。

ハードウェア情報:

Digispark - USB Development Board ATtiny85マイコン搭載

プログラムメモリ: 8KByte → すごい大容量!
EEPROM: 512Byte 
SRAM: 512Byte 
内部クロック: 12.8/16.5MHz
動作電圧: 2.7V~5.5V

V-USBというライブラリを使って、AVRマイコンのGPIO端子からUSBプロトコルの信号を直接出力しているという低レイヤーハッカー向けの開発ボードです。eBayやAliExpressで中国から1個200円前後でDigispark互換機を安価に購入できます。このような素敵な開発ボードが安価に入手できる中国が本当に大好きです。私はこういった基板に触るのが好きで深センに2回訪問しました。

解法1:忍耐で突破(おススメできない)

Bad MouseをUSBポートに挿すと、マウスが勝手に動いてマウスが自動でクリックされます。マウスカーソルの動くスピードが徐々に遅くなっていくのですが、ペイントソフトを起動してBad MouseをUSBポートに挿したままずっと待てば正解のフラグが描かれます。ただ、このためには辛抱強く待つ必要があり、このアプローチだとフラグ文字列の横の長さがどこまであるのかわからないので途中大変不安になります。

回答者:@hikariumさんによるwrite-up https://hikalium.hatenablog.jp/entry/2019/12/22/232138

実はこの文字描画フォントがFactor the Flag問題と同じであることに気づくと、ビットマップデータがどういう形式で埋め込まれているかのヒントとなります(伏線)。

解法2:ビットマップデータを抽出

HEX形式の16進ダンプをリバースエンジニアリングしてビットマップデータを抽出します。

先頭の3行目以降のバイナリのASCII文字列を見るとopqrstuvwxyz{|}~のように1ずつ増えているパターンが見えます。 これはマルウェアの簡単な暗号化で見ることがあるunrollingという手法だと目grep時点で気づくことができます。

実際に逆アセンブルすると、64の剰余を計算してこの文字列テーブルから63引いた値から1ずつ減らしながら6bitの剰余を2回デコードしてY座標を12ドット描いてから右のX座標にずれて、またY座標の描画を繰り返していることがわかります。

C言語でビットパターンをデコードするプログラムを書くと以下になります。

#include <stdio.h>

const char a[] = "?@aBcDAUiHkJKLMNQPOaS\\UVWXY`kemgoiAqcdEywLyN{P]Mopqrstuvwxyz{|}~"
"OHrQCLEFGHiN[U]W_YqXSTUVWXYZ[\\]^_`}fElGnIpmqklk}QxSzU|w~wxuA}D?FAHEFCDAMIPKRMTQRO"
"PMYU\\W^Y`Ua[\\[mc`ibsdcughIjKlK}p@rBstwzY@kBeDCE?@CBERgGaHOJKLINQYS[UYQYWXyakemgo"
"iAgcdelwqys{uM}opw~KwUvO{?F{|IDQIcJUMQLGHgP]T_VaXsYSTSeg`ibkd}e_`cbedcuihkjklmt?yA"
"{C}UEwxuz}E?GAE}ECDAFIQKSMQIQOPqYc\\e^g`y^[\\UeshsjulEmghejmuowqumustS|I@KBMD_E?@?"
"QSLUNWPiQKLORqXCZ}\\[]WXQaodofqhAicdqlyqKr}uytopOxE|G~I@[A{|[DQHSJULgMGHIJ[T~]OXQR"
"STuYoZ_\\Yk]`_`gb{dEu?hojklMu?xAzC|UzwxYz[|yMa@cBCDELWQYS[Um]OPoXe\\g^i`{a[\\[mohq"
"jslEmghGp}t?vAxSystvFxHWI[|]~?@B";

int main()
{
    for (int i = 0; i < sizeof(a)-2; i += 2) {
        for (int j = 12-1; j >= 0; j--) {
            putchar((((a[i+(j/6)]-63-(i+(j/6)))%64)>>(j%6))&1 ? '#' : '.');
        }
        putchar('\n');
    }
}

実行結果:

$ gcc decode.c && ./a.out
............
......#.....
......#.....
..########..
......#...#.
......#...#.
............
............
..........#.
..#########.
..#.........
............
............
...##.......
..#..#.#....
..#..#.#....
..#..#.#....
..#####.....
............
.#..###.....
#..#...#....
#..#...#....
#..#...#....
.#######....
:
(略)

ダウンロード先: https://gist.github.com/takesako/be0abea85a75b07b3fd9b63744f736dd

AVRは初見だとハーバードアーキテクチャで16bit単位のメモリアクセスでI/O命令の扱いが少し特殊で読むのは大変なのですが、 Arduinoで使われている世界標準のマイコンなので(今やPICより主流)IoT時代に覚えておいて損はないと思います。 GhidraがAVRに対応していて便利な世の中になりましたが、プリミティブな命令が多いので、慣れないとちょっと時間がかかります。

回答者:@ptr-yudaiさんによるwrite-up https://ptr-yudai.hatenablog.com/entry/2019/12/23/001203

正攻法で頑張って解いていて本当に素晴らしいです。

解法3:

ファームウェアを書き換えてwaitの待ち時間を短縮させてフラグを表示する方法も想定解です。

リバースエンジニアリングすると、プログラムメモリの特定の番地を読み込んで0x3Dと比較して一致していなかったら待ち時間を延ばさない、といった処理が見えます。0x3Dが出現するのはプログラム中1個所のみで、HEXファイルで言うと2行目の後尾の方です。

micronucleusのビルド

Arduino IDEを使って書き込んでも良いのですが、今回はmicronucleusという軽量なコマンドラインツールを使ってDigisparkのファームウェアを書き込みます。micronucleusは、原理的にファームウェア上書き一方向のみの書き込みができて、読み込みには対応していません。

$ sudo apt install -y libusb-dev
$ git clone https://github.com/micronucleus/micronucleus.git
$ cd micronucleus/commandline
$ make

ファームウェアの更新

アセンブルの結果より、HEXファイル中の2行目の3Dを1bit書き換えます。

$ sed -i -e "s/3D3E/2D3E/" badmouse.hex
$ ./micronucleus --timeout 60 badmouse.hex
> Please plug in the device ...
> Press CTRL+C to terminate the program.
> Device is found!
connecting: 40% complete
> Device has firmware version 2.4
> Device signature: 0x1e930b
> Available space for user applications: 6522 bytes
> Suggested sleep time between sending pages: 7ms
> Whole page count: 102  page size: 64
> Erase function sleep duration: 714ms
parsing: 40% complete
parsing: 60% complete
> Erasing the memory ...
erasing: 80% complete
> Starting to upload ...
writing: 100% complete
>> Micronucleus done. Thank you!

正解:

SECCON{379eaX85bTa99c695b36855i4Ycfa5b5}

勝手に解けている動画(約10分)

解けたチーム数:国内2チーム、国際6チーム

懇親会で余った予備のBad USB欲しい人いる?と言ったところ全部すぐなくなり人気でした。 ハードウェア問題に挑戦した人は総じて楽しかったと言っていただけて出題者としては嬉しかったです。

出題者:

Perlが第二母国語で、TMTOWTDI (There's More Than One Way To Do It)「やり方はひとつじゃない」の哲学が好きです。SECCON創設者の一人で初代実行委員長です。

DAY2にNICTブースに立ち寄ったら@kamapuさんに撮影していただきました。

挑戦していただいたCTF playerの皆様、ありがとうございました。

コンパイル時計算完全に理解した

コンパイル時計算完全に理解したリクルートテクノロジーズの竹迫です。

この記事はRecruit Engineers Advent Calendar 2019の4日目(12/4)のエントリーです。先月、社内のTGIFで飛び入り発表したスライドを記事にまとめなおしました。

adventar.org

皆さんは素数を数えることが好きでしょうか?私は大好きです。

問題:MAX以下の素数の個数を数えよ。

与えられた数以下の素数の個数を予測する「ガウス素数階段」を作る簡単な問題です。素数かどうかを判別するにはどんな数字でも割り切れないことを確認する必要があるため、ナイーブに素数判別を計算するとどうしても時間がかかってしまいます。(※厳密に素数の個数を予測する魔法の「リーマンの素数公式」はとても面白いのですが、今回の記事では解説対象外です。)

f:id:TAKESAKO:20191204230408p:plain

引用元:http://tsujimotter.hatenablog.com/entry/riemann-prime-number-formula

ガウス素数階段を改良した)リーマンの素数公式に興味のある方は上記URLに日曜数学者のtsujimotterさんによる可視化アプリもあるので(ぜひ解説も含めて)お楽しみください。

そこでコンパイル時計算ですよ

C++コンパイル時計算というテクニックを使うと、コンパイル時に計算結果が定数として出力され、プログラム実行時に計算コストが一切かからないというメリットがあります。

C++03のテンプレートメタプログラミングでMAX以下の素数の個数を計算してみます。

#include <iostream>

template<int N, int n=N-1, int m=N%n> struct isPrime { 
  enum { ok = isPrime<N, n-1>::ok }; 
};
template<int N, int n> struct isPrime<N, n, 0> { 
  enum { ok = 0 }; 
};
template<int N> struct isPrime<N, 1, 0> { 
  enum { ok = 1 }; 
};

template<int N> struct countPrime { 
  enum { sum = isPrime<N>::ok + countPrime<N-1>::sum };
};
template<> struct countPrime<1> {
  enum { sum = 0 };
};

int main() { 
  std::cout << countPrime<MAX>::sum << std::endl;
}

複雑にならないよう以前herumiさんに教えてもらったenumを使うテクニックを使っています。

このプログラム prime.cpp をコンパイルして、整数MAX=100までの素数の個数を数えてみます。

$ g++ -DMAX=100 prime.cpp && ./a.out
25

100までの素数の個数25が出力されました。

objdumpでディスアセンブルしてみる

本当にコンパイル時に計算されているのかどうか、実行時に計算しているのではないかという疑惑を払拭するため、コンパイルされた結果のバイナリをobjdumpコマンドでディスアセンブルして中身を見てみます。

$ objdump -d a.out
<抜粋>
000000000000088a <main>:
 88a:   55                      push   %rbp
 88b:   48 89 e5                mov    %rsp,%rbp
 88e:   be 19 00 00 00          mov    $0x19,%esi
 893:   48 8d 3d 86 07 20 00    lea    0x200786(%rip),%rdi        # 201020 
 89a:   e8 c1 fe ff ff          callq  760 <_ZNSolsEi@plt>
 89f:   48 89 c2                mov    %rax,%rdx
 8a2:   48 8b 05 27 07 20 00    mov    0x200727(%rip),%rax        # 200fd0 
 8a9:   48 89 c6                mov    %rax,%rsi
 8ac:   48 89 d7                mov    %rdx,%rdi
 8af:   e8 8c fe ff ff          callq  740 <_ZNSolsEPFRSoS_E@plt>
 8b4:   b8 00 00 00 00          mov    $0x0,%eax
 8b9:   5d                      pop    %rbp
 8ba:   c3                      retq

ちなみにobjdumpのデフォルトはGAS形式のAT&T表記で出力されるため、私にとって読みやすいIntel表記で出力するにはobjdumpに-M intelオプションを指定します。

$ objdump -M intel -d a.out
<抜粋>
000000000000088a <main>:
 88a:   55                      push   rbp
 88b:   48 89 e5                mov    rbp,rsp
 88e:   be 19 00 00 00          mov    esi,0x19
 893:   48 8d 3d 86 07 20 00    lea    rdi,[rip+0x200786]            # 201020
 89a:   e8 c1 fe ff ff          call   760 <_ZNSolsEi@plt>
 89f:   48 89 c2                mov    rdx,rax
 8a2:   48 8b 05 27 07 20 00    mov    rax,QWORD PTR [rip+0x200727]  # 200fd0 
 8a9:   48 89 c6                mov    rsi,rax
 8ac:   48 89 d7                mov    rdi,rdx
 8af:   e8 8c fe ff ff          call   740 <_ZNSolsEPFRSoS_E@plt>
 8b4:   b8 00 00 00 00          mov    eax,0x0
 8b9:   5d                      pop    rbp
 8ba:   c3                      ret

これを見ると「mov esi,0x19」のコードがあり、100までの素数の個数(25=0x19)がコンパイル時に定数となってバイナリに埋め込まれていることがわかります。コンパイル時計算すごいですね。

線形再帰の問題

ここで、調子に乗ってMAX=1000までの素数の個数を計算してみます。

$ g++ -DMAX=1000 prime.cpp
prime.cpp: In instantiation of ‘struct isPrime<997, 101, 88>’:
prime.cpp:5:8:   recursively required from ‘struct isPrime<997, 995, 2>’
prime.cpp:15:31:   recursively required from ‘struct countPrime<999>’
prime.cpp:15:31:   required from ‘struct countPrime<1000>’
prime.cpp:60:31:   required from here
prime.cpp:5:8: fatal error: template instantiation depth exceeds maximum of 900 
                            (use -ftemplate-depth= to increase the maximum)
   enum { ok = isPrime<N, n-1>::ok };
        ^
compilation terminated.

おっと。コンパイル時にfatal errorが出て止まりました!

よくエラーメッセージを見ると「template instantiation depth exceeds maximum of 900」と書いてあり、ご丁寧にも(use -ftemplate-depth= to increase the maximum)と深さを増やすオプション指定をコンパイラが教えてくれています。

$ g++ -ftemplate-depth=1000 -DMAX=1000 prime.cpp
$  ./a.out
168

このようにC++03の古典的なテンプレートメタプログラミングにおいては、線形再帰だと探索の深さが問題になるので、わざわざ二分再帰の形に書き直して深さではなく幅を広く探索するようにプログラムを書きなおすテクニックが必要でした。テンプレートメタプログラミングが魔術と言われる所以はこういうところにもありました。

C++14 constexpr を使おう

C++11の言語仕様からconstexprが追加され、コンパイル時定数式として評価できる関数を定義できるようになりました。ただ、C+11ではconstexpr関数の中で事実上return文一個しか書くことができず、変数を使った処理やif文やforループの繰り返しを書くことが困難で、変数は引数を使って表現し直して、繰り返しのループは再帰関数呼び出しに置き換えたりする必要があり、実際のところかなり面倒でした。

そこで、C++14の仕様ではconstexpr関数の制限が大きく緩和され、変数やif文の条件分岐や繰り返しのforループなどが使えるようになりました。これで普通の人でもカジュアルにconstexprを書くことができます。

わかりやすくなるよう、いったんコンパイル速度は気にせずナイーブに、C++14 constexpr関数を使ってコンパイル時計算で素数の個数を数えるプログラムを書いてみました。

#include <iostream>

template<size_t N>
struct constexpr_Prime {
  int debug = 0x33333333;
  int isPrime[N+1];
  constexpr constexpr_Prime() : isPrime() {
    int ok = 0;
    isPrime[0] = 0;
    isPrime[1] = 0;
    for(int i = 2; i <= N; i++) {
      for (int j = 2; j <= i/2; j++) {
        if (i % j == 0) { --ok; break; }
      }
      isPrime[i] = ++ok;
    }
  }
};

int main() { 
  constexpr auto cp = constexpr_Prime<MAX>();
  std::cout << cp.isPrime[MAX] << std::endl;
}

ここではMAX以下の素数の個数をすべてコンパイル時にisPrimeの定数配列に計算して格納しています。実行時に使うときは、constexpr auto cp = constexpr_Prime<MAX>();で実体化してから

  for (int i = 0; i <= MAX; i++) {
    std::cout << i << ":" << cp.isPrime[i] << std::endl;
  }

のようにして呼び出します。実行時は定数配列を添え字で参照するだけなので超高速です。

$ g++ -DMAX=100 prime.cpp && ./a.out
25

実際にobjdumpコマンドで定数配列が生成されているかどうかを確認してみます。

$ g++ -DMAX=100 prime.cpp && ./a.out
25
$ objdump -z -S -j .rodata a.out

a.out:     file format elf64-x86-64


Disassembly of section .rodata:

0000000000000a60 <_IO_stdin_used>:
 a60:   01 00 02 00 00 00 00 00 00 00 00 00 00 00 00 00     ................
 a70:   00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00     ................

0000000000000a80 <_ZStL19piecewise_construct>:
 a80:   00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00     ................
 a90:   00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00     ................
 aa0:   33 33 33 33 00 00 00 00 00 00 00 00 01 00 00 00     3333............
 ab0:   02 00 00 00 02 00 00 00 03 00 00 00 03 00 00 00     ................
 ac0:   04 00 00 00 04 00 00 00 04 00 00 00 04 00 00 00     ................
 ad0:   05 00 00 00 05 00 00 00 06 00 00 00 06 00 00 00     ................
 ae0:   06 00 00 00 06 00 00 00 07 00 00 00 07 00 00 00     ................
 af0:   08 00 00 00 08 00 00 00 08 00 00 00 08 00 00 00     ................
 b00:   09 00 00 00 09 00 00 00 09 00 00 00 09 00 00 00     ................
 b10:   09 00 00 00 09 00 00 00 0a 00 00 00 0a 00 00 00     ................
 b20:   0b 00 00 00 0b 00 00 00 0b 00 00 00 0b 00 00 00     ................
 b30:   0b 00 00 00 0b 00 00 00 0c 00 00 00 0c 00 00 00     ................
 b40:   0c 00 00 00 0c 00 00 00 0d 00 00 00 0d 00 00 00     ................
 b50:   0e 00 00 00 0e 00 00 00 0e 00 00 00 0e 00 00 00     ................
 b60:   0f 00 00 00 0f 00 00 00 0f 00 00 00 0f 00 00 00     ................
 b70:   0f 00 00 00 0f 00 00 00 10 00 00 00 10 00 00 00     ................
 b80:   10 00 00 00 10 00 00 00 10 00 00 00 10 00 00 00     ................
 b90:   11 00 00 00 11 00 00 00 12 00 00 00 12 00 00 00     ................
 ba0:   12 00 00 00 12 00 00 00 12 00 00 00 12 00 00 00     ................
 bb0:   13 00 00 00 13 00 00 00 13 00 00 00 13 00 00 00     ................
 bc0:   14 00 00 00 14 00 00 00 15 00 00 00 15 00 00 00     ................
 bd0:   15 00 00 00 15 00 00 00 15 00 00 00 15 00 00 00     ................
 be0:   16 00 00 00 16 00 00 00 16 00 00 00 16 00 00 00     ................
 bf0:   17 00 00 00 17 00 00 00 17 00 00 00 17 00 00 00     ................
 c00:   17 00 00 00 17 00 00 00 18 00 00 00 18 00 00 00     ................
 c10:   18 00 00 00 18 00 00 00 18 00 00 00 18 00 00 00     ................
 c20:   18 00 00 00 18 00 00 00 19 00 00 00 19 00 00 00     ................
 c30:   19 00 00 00 19 00 00 00                             ........

_ZStL19piecewise_constructのシンボル上に100個までの素数の個数が定数展開されていることがわかります。

ここまで自力で出来たので「C++完全に理解した」Tシャツを着ることができる人権が得られました。 f:id:TAKESAKO:20191204225330p:plain 引用元:https://twitter.com/shapoco/status/958302684880109568

最近のC++20では、constexprにtry-catchブロックが書けるようになったり、インラインアセンブリ(!)が書けるようになったりしています。C++の進化はすごいですね。 C++の言語仕様とコンパイラの対応状況などは以下のページでまとめられています。 cpprefjp.github.io

ちなみに、ワタシハC++チョットデキルTシャツはこの世界に存在してはならないと個人的には思います。

実行時間は?

さきほどのコンパイル時に素数を計算する時間をシェルスクリプトを書いて計測してみました。

#!/bin/bash
n="10 100 1000 5000 10000 20000 30000 40000 50000"
for i in $n
do
  echo -n "$i, "
  /usr/bin/time -f "%U" g++ -DMAX=$i prime.cpp
done

実行結果

10, 0.20
100, 0.21
1000, 0.32
5000, 1.65
10000, 5.29
20000, 20.65
30000, 45.87
40000, 81.28
50000, 129.12

グラフにすると以下のような形に

f:id:TAKESAKO:20191204225345p:plain

素数の数え上げにアトキンのふるいアルゴリズムを実装するなどすれば、もう少しまともに早くなりますが。 コンパイル時計算は、プログラム実行時を超高速に処理するために、事前コンパイルをものすごく頑張るというポリシーです。

さいごに:素数表を持ち歩こう

私は歩いているときに視界に入ってきた数字が素数かどうかをパッと見で判別するのが趣味で、暗黒通信団素数表をいつもカバンの中に入れて持ち歩いています。

f:id:TAKESAKO:20191204225253j:plain

引用元:https://www.amazon.co.jp/dp/4873101565/

本体価格は税別で357円とお買い求めしやすい素数となっております。(いや、3で割り切れるので違いますね) 計算機資源を使わない最高のキャッシュとして、紙を使った素数表、一家に一冊いかがでしょうか?

f:id:TAKESAKO:20191204225240j:plain

おわり

alpine-iot演習環境の構築手順

alpine-iot環境の構築手順について解説します。Arduino互換機Digispark開発ボードを使ってBadUSBを作る演習で必要となります。

1. VirtualBox本体のインストール

Downloads – Oracle VM VirtualBoxから自分のOS環境にあった最新のVirtualBoxをダウンロードしてインストールしてください。

f:id:TAKESAKO:20190827161225p:plain

セットアップ途中のCustom Setup画面で「VirtualBox USB Support」が選択されていることを確認してください。

f:id:TAKESAKO:20190827152449p:plain

初めてインストールするときに「このデバイス ソフトウェアをインストールしますか?」(名前:Oracle Corporation ユニバーサル シリアル バス コントローラ)という確認画面が表示されたら「インストール」をクリックしてOracle社のUSBコントローラを必ずインストールするようにしてください。

f:id:TAKESAKO:20190827153026p:plain

このUSBコントローラのインストールが完了できていないと、ホスト側に接続されたUSBデバイスをゲストOSから認識できなくなります。

2. Extension Pack のインストール

VirtualBox本体のインストールが終わった後、上記と同じVirtualBoxのダウンロードページから「VirtualBox x.y.z Oracle VM VirtualBox Extension Pack」の下にあるリンク「All supported platforms」をクリックして、Extension Packをダウンロードしてファイルをダブルクリックしてインストールしてください。ダブルクリック後にインストール画面が表示されるまで少し時間がかかります。このとき、必ずVirtualBox本体のバージョンと一致するExtension Packをインストールしてください。

3. Vagrant本体のインストール

Download - Vagrant by HashiCorpから最新のVagrantをインストールしてください。

f:id:TAKESAKO:20190827163953p:plain

初回インストール時はファイルの展開にものすごい時間がかかりますが、気長に待っていれば終わります。 SSDではなくHDDの場合、インストールが完了するまで数分から十数分ぐらい待つ必要があります。 Vagrantのインストールが終わったらOSの再起動が必要となります。

# 4. alpine-iot.zip の解凍 勉強会会場にてUSBメモリで配布している alpine-iot.zip を解凍してください。 ※日本語を含むフォルダ名がフルパスの途中にあるとVagrantssh鍵生成に失敗する不具合が報告されているので、英語名のみのパス上で解凍してください。

5. コマンドプロンプトの起動

cmd.batをダブルクリックして、解凍フォルダ上でコマンドプロンプトを起動します。 (macOSの場合は、コマンドを開いて解凍ディレクトリに cd alpine-iot してください。)

4. alpine-iot 作業ディレクトリの作成

mkdir alpine-iot
cd alpine-iot

※日本語を含むフォルダ名がフルパスの途中にあるとVagrantssh鍵生成に失敗する不具合が報告されているので、英語名のみのパス上で解凍してください。

5. 演習で使う Vagrant box のインストール

コマンドプロンプトから以下のコマンドを実行してください。

vagrant init takesako/alpine-iot

テンプレートのVagrantfileファイルが自動で作成されます。

【実行結果】

C:\alpine-iot>vagrant init takesako/alpine-iot
A `Vagrantfile` has been placed in this directory. You are now
ready to `vagrant up` your first virtual environment! Please read
the comments in the Vagrantfile as well as documentation on
`vagrantup.com` for more information on using Vagrant.

6. VMの起動

Vagrantfileのあるディレクトリで以下のコマンドを実行してください。

vagrant up

Vagrantfileに書かれた該当のboxイメージからVMが自動で起動します。

【実行結果】

C:\alpine-iot>vagrant up
Bringing machine 'default' up with 'virtualbox' provider...
==> default: Box 'takesako/alpine-iot' could not be found. Attempting to find and install...
    default: Box Provider: virtualbox
    default: Box Version: >= 0
==> default: Successfully added box 'takesako/alpine-iot' (v3.9.4) for 'virtualbox'!
==> default: Importing base box 'takesako/alpine-iot'...
==> default: Matching MAC address for NAT networking...
==> default: Checking if box 'takesako/alpine-iot' version '3.9.4' is up to date...
==> default: Setting the name of the VM: alpine-iot_default_1566895136480_97807
==> default: Clearing any previously set network interfaces...
==> default: Preparing network interfaces based on configuration...
    default: Adapter 1: nat
==> default: Forwarding ports...
    default: 22 (guest) => 2222 (host) (adapter 1)
==> default: Booting VM...
==> default: Waiting for machine to boot. This may take a few minutes...
    default: SSH address: 127.0.0.1:2222
    default: SSH username: vagrant
    default: SSH auth method: private key
    default:
    default: Vagrant insecure key detected. Vagrant will automatically replace
    default: this with a newly generated keypair for better security.
    default:
    default: Inserting generated public key within guest...
    default: Removing insecure key from the guest if it's present...
    default: Key inserted! Disconnecting and reconnecting using new SSH key...
==> default: Machine booted and ready!
==> default: Checking for guest additions in VM...
==> default: Mounting shared folders...
    default: /vagrant => C:/alpine-iot

7. VMの接続

以下のコマンドを実行してsshログインします。

vagrant ssh

コンソールに「Welcome to Alpine Linux!」が表示されたらログインに成功です。 ログインに成功したらexitと入力して、ゲストOSのLinuxからログアウトします。

exit

【実行結果】

C:\alpine-iot>vagrant ssh
Welcome to Alpine Linux!
alpine:~$ exit
Connection to 127.0.0.1 closed.

ゲストOSとホストOS間でのファイル共有の確認(任意:この項目は作業しなくて良いです)

ゲストOS上の /vagrant フォルダは、ホストOSでVagrantfileが存在するフォルダとファイルが共有されています。 以下のコマンドを実行してゲストOSのLinuxからファイルを作成し、ホストOSからそのファイルを読み込めることを確認してください。

echo host > host.txt
vagrant ssh
cd /vagrant
ls
cat host.txt
echo guest > guest.txt
exit
type guest.txt

【実行結果】

C:\alpine-iot>echo host > host.txt
C:\alpine-iot>vagrant ssh
Welcome to Alpine Linux!
alpine:~$ cd /vagrant
alpine:/vagrant$ ls
Vagrantfile  host.txt
alpine:/vagrant$ cat host.txt
host
alpine:/vagrant$ echo guest > guest.txt
alpine:/vagrant$ exit
Connection to 127.0.0.1 closed.

C:\alpine-iot>type guest.txt
guest

8. VMの停止(ここまで実施する)

以下のコマンドを入力してゲストOSを安全にシャットダウンします。

vagrant halt

【実行結果】

C:\alpine-iot>vagrant halt
==> default: Attempting graceful shutdown of VM...

→これで演習環境の確認は終了です。お疲れ様でした。

9. VMイメージの削除(これは実行しないでください)

もしも、VMイメージを削除したいときは以下のコマンドを実行してください。

vagrant destroy
vagrant box remove takesako/alpine-iot

→これは演習環境を完全に消去したいときだけ実行してください。

EMFMのpodcastに出演してギルドマスターについてアツく語ってきました

生まれて初めてpodcastに出演しました。EMFMという、Engineering ManagerによるEngineering ManagerのためのPodcastです。

EMFM ep13. 人事制度の制約は悪なのか? ゲスト: 竹迫良範(@takesako)さん

https://anchor.fm/em-fm/episodes/ep13----takesako-e2v1v2

f:id:TAKESAKO:20190117224659p:plain
EMFM ep13. 人事制度の制約は悪なのか? ゲスト: 竹迫良範(@takesako)さん

Shibuya.pm、リリースマネージャーとしての活動、
セキュリティ・キャンプの卒業生はどこに行くのか、
Engineering Manager 10人登用、
人事制度とプログラムの関係、
評価制度の正しい使い方とは、
これからあるべきマネージメント組織とは、
ゲームで学ぶマネージメント、
などについて語ります。

anchor.fm

ep13.では、幻のハッカー甲子園の炎上事件と事業仕分けについても語っていて、私が3年前に前職のサイボウズ・ラボを辞めて、リクルートに転職した経緯・思いを語っています。 マネジメントについてはあまり表で語られない内容だと思いますので、エンジニアリングマネージャの人たちがこうして普段やっていること意識している暗黙知言語化して形式化いくことは非常に価値があることだと思っています。 今回は約3回分の収録をしましたので、残り2回ep14.とas.7で次のネタがまた配信されると思います。

メインパーソナリティのひろき(@hiroki_daichi)さん、ゆのん(@yunon_phys) さん、呼んでいただいてありがとうございました!

※2019/01/27追記 ep14. が配信されました。

ep14. スペシャリストとプロフェッショナリストの違いとは ゲスト: 竹迫良範(@takesako)さん anchor.fm

エンジニア35歳定年説、竹迫さんのキャリア形成のやり方、アウトプットとは、
スペシャリストとプロフェッショナリストの違いとは、
ニュートンの万有引力の法則、新しいパラダイムが出たときの対処方法、
理論を作る人と言語化する人は同じ人であるべきか、
メタ認知とニューラルネットワーク、ハードウェアとソフトウェア、
クラウド型言語がやってくる?、これから生き残れるエンジニア、
について語ります。