正規表現エンジンの話
seccamp'20 アドベントカレンダー 13日目の記事です
2週間ほど遅刻しました。
DFAエンジンとNFAエンジン
正規表現には2つのエンジンがある。DFAエンジンとNFAエンジンである。
このうち、ReDoS脆弱性が起こるのはNFAエンジンであり、DFAエンジンは仕組み上起こりえない。
というのも、DFAエンジンの正規表現はどんな書き方をしても同じ処理になるため、NFAと違って「脆弱性がないように気を付けて書く」という必要がない。
ついでに、DFAエンジンの方がマッチングも高速である。
ここまで行くと、NFAエンジンいらなくね？となるが、現状プログラム言語でメジャーに使われているのはNFAエンジンの方である。
応用範囲が広いNFA
何かプログラムを書いていて正規表現を使う場合、その目的が「特定の文字列にマッチングするか」だけであることはあまりない。
例えばログやメールの抽出、特定の文字列の置換など「マッチングするか確かめた上で文字列を抽出・置換する」ということをよく行うことになる。
ここでDFAの問題が出てくる。DFAはその仕組み上、マッチングした文字列が何かを調べることができないのである。
つまり、その文字列が正規表現にマッチするかしないか以外の結果を何も得られない。
例えばフォーマットが正しいかどうか、を調べるのであればDFAエンジンは高速かつ安全だが、フォーマットに合うように文字列を修正する、となるとそれはDFAエンジンではできない。
そして、昨今のプログラミング言語は言語自体に文字列を扱う関数が充実している場合が多い。つまり、基本的に正規表現を積極的に使う場合は、あまり単純でない処理をしたい場合になりがちである。
そういった観点からも、多くのプログラミング言語でNFAエンジンが採用されているのは自然な流れでもある。
DFAエンジンに価値はないのか
応用性はNFAエンジンに比べ少ないとはいえ、DFAエンジンにできることであればDFAエンジンを使った方が大抵の場合ベターである。
そこで、言語によってはNFAエンジンとDFAエンジンを併用しているものもある。
GNUのgrepやawkはその最たる例で、DFAができることはDFAで、できないことはNFAで行う、という効率的な手法を採用している。
大抵の人はプログラムを書くときにゴリゴリ正規表現を書くことは少ないと思うので、普段知っておく必要はあまりないけど知っているとたまーーーーに役立つ。
最近読んだ技術書
この記事はHUITアドベントカレンダー2020 19日目の記事です
アドカレ2枠目
seccampネタは既に3記事あって食傷気味だし、最近の技術書ネタでいくことにした。
最近勉強していること、やっていることを改めて纏めることで ネタ切れを隠し 記事の嵩増し 今どんなことをしているか知ってもらおうという魂胆。
最近何してるの
Goとjavascriptの学習を主に行っている。
といってもコードを書いているというよりは、基礎文法の理解を進めている段階。
手を動かしてみても基本的なところで止まってしまい、うまくいかないことが多くなったので、心機一転ちゃんと体系的に学ぼうとしている。
とはいえ飽き性の自分は暇さえあればURL欄にtwiとかyoutとか入力してしまうので、最近は風呂に浸かりながらkindleを読むことで強制的に本を読むことにしている。
中々これが良くて、kindle端末はkindleを読むこと以外何もできないので、読み始めると風呂を出るまで他のことをしなくてすむ。
最近読んだあれこれ
やっと本題。まずちょっと前から読んでたのはこれ。
Goプログラミング実践入門 標準ライブラリでゼロからWebアプリを作る impress top gearシリーズ
- 作者:Sau Sheong Chang,武舎 広幸,阿部 和也,上西 昌弘
- 発売日: 2017/03/17
- メディア: Kindle版
Goの標準ライブラリだけでwebアプリを作ろう、という本。
ブログにも1日目だけ載せたが、実はあの後一旦読むのを止めている。
本自体が3年前に出版されたものであり、今の環境だと動かないことが頻発しているためである。
特にgo mod がなかった時代の本なので、この辺のツールについての最新の知識を入れてから臨もうと思った。
そこで、
![みんなのGo言語[現場で使える実践テクニック]](https://m.media-amazon.com/images/I/51lqgv+WyxL.jpg "みんなのGo言語[現場で使える実践テクニック]")
を読んだ。これは実践tips集でいわゆる「小手先の技術」とか言われがちなタイプの本ではある。(特に1冊目が標準ライブラリを使う基礎基本をしっかりと固めるための本なので)
でも実際問題こういうベストプラクティスがまとまった本がないと、情報がなくて先に進めなかったり、形骸化した方法で先に進んで後で困ることが往々にしてある。
最新の公式情報を追うにも、最近どんな感じで言語やその技術が推移してきたのかある程度知っておかなければならないし。
そんなわけでざっと読んだ感想としては、tips集と言うだけあり実用的な話があるなぁ、という感じ。
個人的に刺さったのは
- クロスプラットフォームのためのコーディング
- os/execパッケージの安全な使い方
- ORMの速度比較
- シグナルの扱い方
- テスト(testingパッケージ)について
辺りだろうか。ツール作成に使えそうな話が詰まっていて、とても面白かった。
こういった細々としたところは、どうしてもうまく使えてるか心配で疑心暗鬼になることが多いので、日本語でちゃんとまとまった本があるのはとても助かる。
こちらはうってかわってjavascriptの本。
NodeやTypescriptなどを学ぶにあたって、しっかりjavascriptの基礎固めをしたかったので読んだ。内容は言語仕様の話が7割、フロントの話が3割ほど。
ボリュームはあり、しかも参照の話など他の言語が分かることを前提にしてくる部分もあるので、かなり歯ごたえはあった。
割と序盤からデータ型のうち配列やオブジェクト、関数は参照型で、アドレスを格納している…などポインタを知らないと理解できない概念が出てくるので、Typescriptを使いたい人や、大規模なJSアプリケーションを書きたい人向けの本だという感覚はあった。
以下は内容についての話になる。
まず言語仕様の話では、ES5とES6を両方とも解説するスタイルになっている。
このスタイルは個人的には良いと思う。ES5の書き方もまだ見るのである程度は読めないと困るし、そもそもES6でなぜ文法が変わったのか？という部分も掴めるのでより頭に入りやすかった。
例えば、プロトタイプベースのオブジェクト指向の話が出た後、ES6のクラスベースのオブジェクト指向の話が出てくる。
プロトタイプの実態は、なんてことはないただの関数である、という話の後に、より詳しいクラスベースのオブジェクト指向との差異を説明し、その後ES6のクラスの話やJavaなど他言語の話が少しだけ出てくる、という順序になっている。
こういう順序だと、なんでこんな複雑なやり方を…？となった後に、スッキリしたES6のコードが出てくるので、ああこれを改善するためにこの文法を採用したのか、と納得して先に進める。この書き方はとてもありがたい。
ただしこれを読んですぐ実用的なコードが書けるわけではない。あくまで基礎固め用という感じ。
あとは技術書とは少し違うのかもしれないが、
学生・研究者のための 使える!PowerPointスライドデザイン 伝わるプレゼン1つの原理と3つの技術
- 作者:宮野 公樹
- 発売日: 2009/04/10
- メディア: 単行本
なんかも読んだ。良い感じのスライドデザインを作る本。
これはseccampのスライドを見ていて、人によってとても見やすいスライドと、あまり見やすくないスライドがあるなと感じたので、何が違うのかをなんとなく理解したかった。
グルーピング、図/イラストの活用、コントラストなどの話はUIデザインにも通じるものがあると思う。
まぁ自分はデザインが苦手なので、テンプレート的なものをこの本に求めていたが、テーマが生物系のスライドが多かったり、悪いスライドを納得できる方向に改善していく、というこの本のスタイルが自分に合っていて、通学中などにたまに目を通している。
積読
積読は文化。
- 作者:株式会社日本レジストリサービス(JPRS) 渡邉結衣、佐藤新太、藤原和典
- 発売日: 2018/11/22
- メディア: 単行本
JPNICの本。DNSの講義を受講していたが、その人がJPNICの人だったのでkindle半額セールの時に買ってみた。
当分積むことになるが、半額だったので買って正解だったと思う。どうせ欲しかったし。
SQLの本。モダンSQLというところに惹かれて買った。これもkindle半額セールの時に買った。
isucon以降SQLのパフォーマンスチューニング知識が欲しかったので、これもそのうち読むと思う。今はまだ積むけど。
↑と紹介順序逆な気がするが、これは半額セール時じゃない時に普通に買った。
3割ぐらい読んで放置している。ちょっと簡単すぎたかなぁという感じ。読むモチベはあるが、今はとりあえずGoとjavascript頑張りたい気分なので、 SQLについては当分積んでも良いかなという気持ちではある。
ようこそ pic.twitter.com/uJ8VIVNeW4
— 電気ひつじ (@teru0x1) 2020年12月7日
上級国民への道のりは遠い。
今後の展望
とりあえずjavascript完全理解者になってきたので、Typescriptで小さめのDiscord botを書いている。
あとはここに乗せていない詳説正規表現やらマスタリングTCP/IPがあるので、ゆっくり読み進めていきたい。
時間ある今のうちにあらかた終わらせたいな、とは思っている。
seccamp参加録
HUITアドベントカレンダー2020 17日目の記事です。
seccamp'20が終わった
修了しました お疲れ様でした！#seccamp
— ayumin (@shoumoji) 2020年12月6日
とても濃い1か月半だった。
何をやったか
正規表現のReDoS対策を行うLinterを書いた。
正規表現エンジンのアルゴリズムを実装し、オートマトン理論によってReDoSの検出アルゴリズムを作るアルゴリズム班と、
Linterや実際のOSSプロジェクトにそれを適用し、OSSへの貢献を行うLinter班があり、
自分は後者の方に属して開発を行った。
開発言語はTypescriptだが、Linterに直接関係ないコードは言語指定がなかったので、自分はシェルスクリプトでGitHubのスクレイピングを行った。
もう一人の方はPythonで行っていた。
正規表現エンジンは難しい
そもそもアルゴリズム知識を前提にしているので、スタート位置に立ててもいなかった。永遠に力不足を感じた。
概要を把握することがやっとで、更にTypescriptの知識もなくLinterも動かせなかったので、チームの人におんぶにだっこ状態であった。
正規表現というと.や*や+を使って…という感じを想像するかもしれないが、どちらかというと正則言語そのものの話で、普通に数式が出てくる。
CSに詳しい人なら、オートマトンの受理状態、ε遷移、強連結成分分解みたいな単語は知っていると思う。そんな感じの話だった。LT会で頑張って説明する。
他の講義について
今回はオンラインで開催期間が長くなり、更に選択コースの講義も受けられたので、インフラやネットワーク関係の講義も受講した。
その中でもJPNICの方から体系的なネットワークについて教わったのはとても面白かった。
4時間にもわたる講義+ハンズオンだったが、ネットワークを支える人の存在や、ルーティングアルゴリズムなどはやっていて興味深い内容ばかりだった。
VyOSを使ってネットワークに触り、経路広告に関わるセキュリティの問題などを学んだ。
SSL/TLSすら破れる(厳密には破れてないが、一般人から見れば鍵マークはつくのでちゃんと詳細を確認しない限り気づけないレベル)脆弱性を実際に触ったときはネットワークちゃんと分からないと危ないなと思った。
今とある理由でネットワークプロトコルの勉強をしているが、この辺はレベルが高くて難しい。
最近は、これと並行してTypescript(というよりjavascript)について調べながら、今回のReDoS検出の学習を再挑戦している。
改善してほしいな、と思ったこと
まず、グループワークが難しい。というよりグループで何かをすること自体がオンラインでは厳しい。 オンラインのコミュニケーションコストは想像以上だ。実際で会う数倍以上に時間をかけなければならない。
ちなみに自分はVRを買ったので、そこで仲良くなれることを期待していたが、色々あったのでまだVR沼にハマっていない。
この記事を書いた時点(12月頭)はまだだったが、結局seccampが終わった翌週に届いた。今はVRChatをたまにしている。
他には、時間ごとにGoogle Meetが変わるので、どこに行けばよいのかわかりにくい。
それぞれに分かれて別のGoogle Meetに移動ならわかるが、全員一斉に別の部屋に行く意味があるのかなと思った。
これに拍車をかけるのが、kintone通知の分かりにくさだ。slackで通知してくれれば…と何度も思った。
今回が初のオンラインseccampなので、次回はもっと良くなっていると思う。良い人柱になりたいところ。
これはサークル活動でもそうで、オンライン活動では仲良くなるまでに通常活動の数倍の時間が必要になる。
seccampの活動日は週1日とはいえ、ちゃんとチームの人と話したのは初めて会ってから2か月近くかかった。
共通の話題があってもここまで時間がかかるので、オンラインのサークル活動は本当に難しいと思う。
いっそ全員VRでもできれば楽なんだけどなぁ…。全員分のQuest2用意できるお金降ってこないかな。
最後に
Z-IIIチームの方々、なにもできなくてごめんなさい。最後に発表用スライドに全力を尽くしたので許して…。
BoFのインフラ枠に来てくれた方、たどたどしい司会となってしまいましたが、自分は楽しかったです。
来年以降はもう少し時間が増えると、もっと楽しくできるんじゃないかなと思います。協議会の方、もし見ていらしたらお願いします。
あと話を持たせてくれたB-IIIの講師の方には本当に感謝です。来年は多分この講師の方のSecHackゼミに応募します。(本当)
この記事を見ている方(特にHUIT関係の方)には是非参加してもらいたいです。 年齢制限あるのでできるだけ早いうちに！
セキュリティ何もわからんって人でも、選択コースはセキュリティ啓発マンガ書くとか、実際の事例についての法律を学ぶとか、いろんな分野があるので楽しめると思います。来年以降は分からないですが、今年は好きなものを受けられました。
集中コースに行く人は……頑張ってください。
自分は来年のSecHack365参加に向けて今後も頑張ります！
以上、ayuminでした。
typescript入門者の戯言
typescriptはじめました
昨今JSの躍進が目覚ましい。 webページをちょっと動かすための言語だったはずが、今やReact / Vue などでwebページの中核を担っているし、サーバにも進出し始めた。
そんなわけで、JSには以前から関心はあった。だがイマイチモチベーションが上がらず、随分と放置していた。
モチベーションが上がらない理由は明確で、サーバサイドJSの環境をちゃんと把握できていないためである。
更に頻繁な機能追加を行いながらメンテをするようなものは今まで書いてこなかったので、今まで触る必要も感じていなかった。
環境の複雑さは、Go好きの人間としては中々耐え難い。
Nodeでインフラツールを作るのは酔狂だろう。元々webのための言語でツールに使う言語ではないと思う。
Goは一度作れば、よほどの事がない限り数年は使えるので、やはりインフラを考えると素晴らしく使い勝手が良い。
しかもGoなら外部ライブラリに依存せずとも、豊富な標準ライブラリで実装ができる。メンテがとても楽。
そんな理由があり、今まではGoを使うことが多かった。
これはサーバサイドJS/TSどちらにも言えることだが、Nodeに関してはLTSでも3年しかサポートされないという問題もある。
インフラは基本的に長期的なサポートが要求される。
環境を塩漬けせざるを得ないこともあるし、機能追加を頻繁にする場合もあれば、使えれば良いということもある。
なんでTS?
とはいえ、今後JSは間違いなくメジャー言語の1つになるだろう。
やはりフロントエンドという唯一無二の力を持つJSの力は大きい。
フロントではwasmが徐々に顔を出し始めたとはいえ、まだまだwasmの台頭には時間がかかる。
結局のところ、まだJSに頼るほかない。
JSでもIE対応は頭が痛い問題だろうが、まだ対応できるだけマシだ。wasmでは切り捨てる以外選択肢がない。
というところでJSはやらざるを得ないなぁという気にはなった。とはいえ動的型付け言語はあまり書きたくない。
型のない言語では極まれにperlを書くことはあるが、用途は一度しか使わない正規表現処理ぐらいのものだ。
運用するものに動的型付け言語を使いたいとは思えない。
となるとaltjs界では勿論、単一の言語としても採用例が増え続けており、シェアが伸び続ける可能性が高いTSをやるか、という結論に至った。
以上をまとめて一言で言うと、現状JS/TSをやると色々好都合そう、という話。
インフラ周りでも(特にAWS等クラウド周りを触るときに)JS/TSの知識が欲しくなる機会が増えそうだし。
フロントやるときにも知っておくと便利だろうし。(最近インフラに求められるもの多くない？)
言語としてのTS
言語仕様自体ではあまり困らない。JSの文法さえ理解していれば割と直感的に書けるな、という印象。
オブジェクト指向に慣れていないとはいえ、ES6以降の文法はかなり一般的なものである。 JSしか使えない概念を覚えるわけではないから、あまりモチベが下がることもない。
だがNodeの標準モジュールがTSの型に対応していないことがあり、互換性はあるとはいえJSだけの知識もまだ必要そうだ。
言語としてはES5までの文法で書かれたものとES6以降のものが別物なので、JS/TSよりもES6以降か否か、みたいなところがある。
これがあまり好きではないが、まぁそのうち慣れる気がする。
ちなみにJSとGoの一般的な実行速度はあまり変わらないそうだ。(自分で調べたわけではないが)
興味の変遷
6-7年前ぐらい
Minecraftのサーバを立てたくて、コマンドポチポチを始めた。
初めてシェルスクリプトに触れたが、当時if文すら理解できず、プログラミングとは…となった。
そもそもそれがプログラミングという行為であることすら知らなかった。
minecraftは結構特殊な実行環境で、自力でデーモン化しなきゃいけなかったり、色々良くわからんことがあった。
中でもscreenの使い方とか、systemdって何だとか、当時まだ情報がなくてなんとかコピペしながら作った記憶がある。
minecraftよりサーバ弄りにハマってしまい、wordpressを自力構築してみたりとかしていた。
この時期、自分の他にプログラム書ける人がなぜかtwitterの知り合いに複数人いた。 それに比べてしまい、自分は全然できない人間だ、才能ないから情報系行くのはやめようと幾度となく思った。
実際に情報系に行くのを諦めた理由の8割はこれ。
HUIT入部当初
この時はまだ「Linuxが好き」以外に特に知識も何もなかった。
あとはなんとなく読めるC言語の知識がうっすらあったぐらい。 そこでLinux関係の知識を付けようと、書籍とかtwitterを見漁っていた。
すると凄そうな人達はみんなLinuxカーネルを触っていた。
ここで自分は、「Linuxカーネルに強くなろう！」と思った。
ちょうどCを勉強していたので、中々良い目標ができたなーとこの時は思っていた。
入部2ヶ月後
何もできなかった。今考えると当然の話ではある。
自分が好きなのは「Linuxでサーバを立てること」であり、Linuxの仕組みにそこまで深く興味があったわけではなかった。
この辺で初めてインフラエンジニアという存在を知る。ここで自分の興味方向が違ったことをやっと理解した。
あとバイト(非エンジニア系)をやめた。
本格的に自分の方向性を考え始めたのもこの頃。つまり入ってから数か月間迷走していた。
入部3ヶ月後
コロナがやばくなった。まず大学がリモートになった。
ある程度方向性が固まってから(というかIT研に入ってから)のコロナ突入だったのはラッキーだった。
とはいえこの頃はまだ何が分からないか分からないような状態で、
特に進捗と呼べるものもなければ、具体的に何か行っていたわけでもない。
だが、ここでじっくり体を休めながら今後を考えられたため、その後様々なことがスムーズに進んだ。
HUITで会った人にインフラ系のバイトの情報を聞き、応募して面接を行ったのもこの頃。
素晴らしいタイミングでリモートでのアルバイトを見つけ、とても嬉しかった。
知識を最低限身に着けて挑みたかったこともあり、夏休みまで待ってもらってからのスタートになった。
入部6ヶ月後
この頃から本格的に手を動かす技術的な話が増え始める。
まずバイトを始まる。
お金だけでなく技術的な知識も手に入った。今の気ままに参考書を買える生活ができるようになった。
初めは1か月限定ということだったが、ありがたいことに今も働かせてもらっている。今後も頑張っていきたい。
サークルの人とisucon10に出たのもこの頃。
この辺からより本格的にコーディングに興味を持ち始める。Cに近くて読みやすいことからGoを書き始めた。
入部8ヶ月後
seccamp全国大会に出る。詳細は他で色々書いているので省略する。
入部10ヶ月後(現在)
IT研にとてもお世話になっていること、活動にも頻繁に参加していたことなどから、 自然とサークル運営にも興味が出始めた。
そういったこともあり、今はサークルの運営の1人として活動している。
技術面としては、seccampでJS/TSが全く書けなかったことからJSを学び始めた。
初めての本格的なオブジェクト指向言語なのでまだ難しいが、JSの言語仕様に翻弄されながら楽しく学んでいる。
今後も興味の対象が増えたり、変わったりすることはあると思うが、 サーバやネットワークから大きく離れることはないだろう。多分。
seccampとモチベーション
seccampが終わった
あと1週間あるが、ここ1か月やってきたseccampが終わった。
seccampは昔からの憧れで、参加できた時は本当に涙が出るほど嬉しかった。
技術力が足りていると思えたことは一度もなかったし、自分は本当に何もできなくて悔しい思いは幾度となくした。
それでも参加できたのは幸運だったと思う。楽しい1か月だった。
次何をするか
正直なところ、作りたいもの・やりたいこと・やらなければならないことが多くて困っている。
時間がないわけではないが、大学のレポートに時間がかかりすぎて、好きなことができていないのは確かだ。頑張らねば。
既に次開発するものは決まってるし、恐らくこれが終わるのは来年になるだろうが、いい感じに進めていきたい。
seccampは参加が目的ではないが、参加できたことは心から嬉しかった。これを糧に更に精進していきたい。
モチベーションについて
seccamp参加以降高すぎて困っているが、同時に生活リズムも崩れ始めた。
数日間肩の痛みが残る日ができたり、日常生活に少し問題が出てきているので、気を付けなければいけない。
サークル(HUIT)の方も色々進んできた。自分がITを学ぶきっかけとなったサークルなので、今後はより貢献していきたい。
Goでwebアプリケーション作る #1日目
1週間ほど前にGoプログラミング実践入門買った。それをしながらメモ。
Goプログラミング実践入門 標準ライブラリでゼロからWebアプリを作る impress top gearシリーズ
- 作者:Sau Sheong Chang,武舎 広幸,阿部 和也,上西 昌弘
- 発売日: 2017/03/17
- メディア: Kindle版
1.10 go installについて
Hello Worldで詰まった。本にある通りに
go install first_webapp
ができない。これはバージョンアップでGo Moduleを使うようになったことが理由らしい。
とりあえずserver.goのある場所で
go mod init first_webapp
すれば良いようだ。
なおパッケージ管理についてよく分かってないのでこれでいける理由の詳細は不明。
2.4.2 静的ファイル返送について
nginxみたいなことをさせたい場合、FileServer関数を使えば良いっぽい。
自分は多分nginxか静的ファイルの配信に適したクラウド(AWSでいうS3とcloud front)にさせると思うが、なるほどなぁという感じ。
コードみながらどういう構成が良いか考えるのは楽しい。
それにしてもこの本、バージョンが古いからかそのまま行かなくて辛いこと多いな…。
