今週のまとめ (2017/6/2)
プログラミング言語
libtins: C++ packet crafting and sniffing library
C++ でパケットをパースしたり生成したりするライブラリ。色々なレイヤーでのプロトコルを解析・生成できる。pcapの読み書きなども可能。
Rust from Scala
〇〇言語利用者から見たRustシリーズ Scala編。
MoonScript: a programming language that compiles to Lua.
MoonScript, a language that compiles to Lua
AltLua。言語としては CoffeeScript に近く、Python や Ruby の影響を受けている。
Imperative Haskell
HaskellにおいてSTモナドで命令言語的にクイックソートを実装してみた記事。
Tour of an open source Elm SPA
Elm で Qiitaのような情報共有サイトを SPA で実装したデモ。Elmについて 個人的には Farewell to FRP したのが悲しくてまだ引きずっている
アルゴリズム
A C++ library of Concurrent Data Structures
主に lock-free な各種並行データ構造の実装。論文リスト付き。
A GENERATIVE APPROACH TO SIMULATING WATERCOLOR PAINTS
水彩画のようなテクスチャをアルゴリズミックに生成する方法について。ソースは Quil という Processing を Clojure でやるものを用いている。
Web
A list of everything that could go in the
HTML の <head> に書くもの一覧。HTML自体の仕様にあるものから、Twitter Cards 等に対するサイト説明や特定のブラウザでの挙動指定まである。
数学
Elliptic curves as Python Objects
楕円曲線上の演算を Python の演算しオーバーロードを用いて実装する。
usl4j And You
スケーラビリティに関する数学的モデルについての考察。「リトルの法則」は待ち行列理論の文脈で聞いたことがあるがもっと踏み込んだ Universal Scalability Law という法則について考察している。
以下も参考になる。 How to Quantify Scalability
ひとこと: ReDoS について
今週 Atom を使っていたら突然固まって落ちるという現象があり、調べてみたら、検索で正規表現のバックトラックの数が膨大になり計算が止まらないという事態になっていたことがわかった。つまり邪悪な正規表現を入れた自分が悪かった。
こういったバックトラックが爆発することを Catastrophic Backtracking というらしく、またセキュリティの文脈においてはこれを利用してサービスを停止させる ReDOS (Regexp DoS) という攻撃があるらしい。
日本語の文献は以下が参考になる。*2
- 正規表現を使ったDoS – ReDoS | yohgaki's blog
- ReDoSの回避 | yohgaki's blog
- 正規表現でのメールアドレスチェックは見直すべき – ReDoS | yohgaki's blog
上にもあるように StackExchange がサービス停止した事例や、 Express.js の脆弱性 といった事例もあり、正規表現の取り扱いには気をつけたほうがいいということを認識した。
対策としては、
- (任意の)正規表現を入力として利用するシステムは絶対に作らない。
- Catastrophic Backtracking を起こす正規表現を用いない。
- 起こすかどうかを検査したり解析したりするツールもある
- 長い文字列を正規表現にかけない。
- Catastrophic Backtracking を起こさない正規表現エンジンを用いる。
- https://github.com/google/re2 は線形時間でマッチが終わるように作られている(らしい)
- Go は re2 が標準ライブラリにある言語です
等々。
*1: from:ヘンペルのカラス - Wikipedia image: https://www.flickr.com/photos/90678392@N00/305302998
*2: これらが十分詳しいのでこれをネタにして記事書いたろという気持ちがなくなってしまった