ねぇうしくんうしくん

今週のまとめ (一週間で自分が見た技術系サイトのログ)が今のところメインです。プログラミング言語、人工知能、セキュリティ 等

今週のまとめ (2017/6/2)

f:id:z_kro:20170602234901p:plain *1

プログラミング言語

libtins: C++ packet crafting and sniffing library

libtins.github.io

C++ でパケットをパースしたり生成したりするライブラリ。色々なレイヤーでのプロトコルを解析・生成できる。pcapの読み書きなども可能。

Rust from Scala

beachape.com

〇〇言語利用者から見たRustシリーズ Scala編。

MoonScript: a programming language that compiles to Lua.

MoonScript, a language that compiles to Lua

AltLua。言語としては CoffeeScript に近く、PythonRuby の影響を受けている。

Imperative Haskell

Imperative Haskell

HaskellにおいてSTモナドで命令言語的にクイックソートを実装してみた記事。

Tour of an open source Elm SPA

dev.to

Elm で Qiitaのような情報共有サイトを SPA で実装したデモ。Elmについて 個人的には Farewell to FRP したのが悲しくてまだ引きずっている

アルゴリズム

A C++ library of Concurrent Data Structures

github.com

主に lock-free な各種並行データ構造の実装。論文リスト付き。

A GENERATIVE APPROACH TO SIMULATING WATERCOLOR PAINTS

www.tylerlhobbs.com

水彩画のようなテクスチャをアルゴリズミックに生成する方法について。ソースは Quil という Processing を Clojure でやるものを用いている。

Web

A list of everything that could go in the

github.com

HTML の <head> に書くもの一覧。HTML自体の仕様にあるものから、Twitter Cards 等に対するサイト説明や特定のブラウザでの挙動指定まである。

数学

Elliptic curves as Python Objects

jeremykun.com

楕円曲線上の演算を Python の演算しオーバーロードを用いて実装する。

usl4j And You

usl4j And You | codahale.com

スケーラビリティに関する数学的モデルについての考察。「リトルの法則」は待ち行列理論の文脈で聞いたことがあるがもっと踏み込んだ Universal Scalability Law という法則について考察している。

以下も参考になる。 How to Quantify Scalability

ひとこと: ReDoS について

今週 Atom を使っていたら突然固まって落ちるという現象があり、調べてみたら、検索で正規表現のバックトラックの数が膨大になり計算が止まらないという事態になっていたことがわかった。つまり邪悪な正規表現を入れた自分が悪かった。

こういったバックトラックが爆発することを Catastrophic Backtracking というらしく、またセキュリティの文脈においてはこれを利用してサービスを停止させる ReDOS (Regexp DoS) という攻撃があるらしい。

日本語の文献は以下が参考になる。*2

上にもあるように StackExchange がサービス停止した事例や、 Express.js の脆弱性 といった事例もあり、正規表現の取り扱いには気をつけたほうがいいということを認識した。

対策としては、

  • (任意の)正規表現を入力として利用するシステムは絶対に作らない。
    • 想定ケースとしては検索クエリとして正規表現を受理するシステムを作った場合、サーバーサイドで処理した場合は ReDOS でサイトが停止する可能性がある。またクライアントサイドの処理でもブラクラとして用いられる可能性がある。
  • Catastrophic Backtracking を起こす正規表現を用いない。
    • 起こすかどうかを検査したり解析したりするツールもある
  • 長い文字列を正規表現にかけない。
  • Catastrophic Backtracking を起こさない正規表現エンジンを用いる。
    • https://github.com/google/re2 は線形時間でマッチが終わるように作られている(らしい)
    • Go は re2 が標準ライブラリにある言語です

等々。

*1: from:ヘンペルのカラス - Wikipedia image: https://www.flickr.com/photos/90678392@N00/305302998

*2: これらが十分詳しいのでこれをネタにして記事書いたろという気持ちがなくなってしまった