くりーむわーかー

プログラムとか。作ってて ・試しててハマった事など。誰かのお役に立てば幸いかと。 その他、いろいろエトセトラ。。。

正規表現

10億人が笑うSVGからナゼか正規表現の話

Billion laughs攻撃っていうのがある。

XMLで参照を多重に定義して、メモリを食いつぶさせてPCとかアプリを固まらさせるやつ。

で、これってSVGでも可能だったんですね。

下の画像をFireFoxで見るとFireFoxのタブが固まる。(Chromeは大丈夫だった)

https://github.com/cirosantilli/web/blob/master/svg-billion-laughs.svg

上の画像をDLして、例えばパワーポイントとかに画像挿入しようとするとパワポも固まる。


上の画像のソースを見ればわかりますが、この程度の参照の組み方だけで、

組み合わせ爆発でヤバイ事になるという訳なんですが、

参照をネストさせるようなものはやっぱり考え物って事ですね。

正規表現なんかも、例えば

(a|b|c)(e|d|f)

みたいに組み合わせで色々やるとエライこっちゃになるパターンがあったと思う。

↑だけじゃ再現させられなかったんですが、昔どこかのコードで見たんだよなー。

組み合わせ爆発って怖いですね。結構意識せずにやっちゃいそうな気もする。


正規表現でいうとMSDNの正規表現のベストプラクティスのページがすごく面白かった。

長さが 5 文字を超えると、文字列の文字が 1 文字増えるたびに処理時間が約 2 倍に増加します。 つまり、有効に近い文字列の長さが 28 文字になると処理に 1 時間以上かかり、33 文字になるとほぼ 1 日かかることになります。

確かに正規表現作ってる時って、正しい文字列ばっかり考慮してるきらいがありますよね。

「*」とか「+」とかのネストとかもやばそう。

正規表現だと楽ーとか早いとかいう話は良く見聞きしますが、

やっぱり一概にそうも言えないですよね。

C# 正規表現のパフォーマンス

最近、正規表現でちょろちょろ判定をしてたんだけど、書き方によって相当パフォーマンスに影響あるんですね。当たり前か。

ホントにかなり変わる。例えば、

string reg1 = @"(パンダ|ライオン|デザイン)(。|\d|\s)";

みたいな正規表現はクソ重い。何となく、「(a|b|c)(x|y|z)」みたいな組合せがすごい増えるとやれる感じがする。上の例でいうと、

string reg2 = @"パンダ(。|\d|\s)";
string reg3 = @"ライオン(。|\d|\s)";
string reg4 = @"デザイン(。|\d|\s)";

って書いてそれぞれ個別に判定した方が数段早かったりする。上の例で計測してみると、だいたい2.6倍早くなった。

組合せを何個も使うような正規表現は考え物ですね。当たり前なのかもしれませんが。。。

C#でutf-16の外字領域の文字があるか調べる

最近、文字コードで色々あった。とりあえず外字。utf-16の文字列内にUnicodeの私用領域の文字が含まれているか調べる正規表現。

public void hoge(string wkStr)
{
	string regexp = @"[\uE000-\uF8FF]";
	if(System.Text.RegularExpressions.Regex.IsMatch(wkStr,reqexp))
	{
	     Console.WriteLine("外字");
	}
}

そーいえば、バイナリエディタで見るとバイトの並びって逆になるのだろうか。いまいち分かってない。 エディタにもよるのかしら。

Bzで見ると「E0 00 F8 FF」⇒「00 E0 FF F8」で見える。

問合せ