＊「ふっかつのじゅもんがちがいます。」withぬこ

どうしても高速化したい処理があって久々にC++を書いています。

が、書いていてあれ？と思うことがあったので記事を書いてみます。

サンプルコードは以下のようなものです。

#include<iostream>
#include<string>
#include<map>

struct point { int x; int y; };

void disp(const point& pt) {
    std::cout << "(" << pt.x << ", " << pt.y << ")" << std::endl;
}

int main(){
    //garbage value
    point pt1;
    disp(pt1);

    // (0, 0)
    std::map<std::string, point> m;
    disp(m["hoge"]);

    // (0, 0) implicit constructor? 
    point pt2 = point();
    disp(pt2);

    // (0, 0) initialize 
    point pt3 = {};
    disp(pt3);

    return 0;
}

http://codepad.org/8qhpf4hW

    //garbage value
    point pt1;
    disp(pt1);

これがゴミを表示するのはCの感覚で言えば納得です。

ところが

    // (0, 0)
    std::map<std::string, point> m;
    disp(m["hoge"]);

なんとこれは "(0, 0)" と表示されるのでした。

std::map の operator[] は、キーに対応するエントリが存在しない場合にはデフォルトコンストラクタでオブジェクトを作る的な理解をしていましたが、pt1のケースと挙動が異なるわけです。

えっ？と思って使っているコンパイラのSTLのmapのソースなどを読んでみたり色々試していると、どうも

    // (0, 0) implicit constructor? 
    point pt2 = point();
    disp(pt2);

このような書き方では "(0, 0)"に初期化されるようなのでした。

C++の構造体はpublicがデフォルトである以外はclassと同じというのは知っています。

と言うことはC的な記述で構造体を宣言した場合は、コンパイラが暗黙のコンストラクタやらコピーコンストラクタなどを作ったりするのだろうという思い込んでいたのですが、しかし pt1 の書き方と pt2 の書き方は等価であると思っていました。

まあただ、以下のような書き方(これもpt1やpt2と等価でデフォルトコンストラクタが呼ばれると思っていました)はコンパイルエラーになったので何か勘違いしているのかもしれません。

    // compile error 
    point pt4();
    disp(pt4);

普通であれば class にしてコンストラクタも明示的に与えるべきなのでしょうが、高速化が目的なので可能でありかつ仕様に則った挙動であるならば余分なことを書かずに済ませたいのですが、いやはや・・・

プログラミング言語C++をざっと眺めただけでは、この挙動を正当化する記述は見つけられませんでした。となるとC++の仕様書を読むべきなのでしょう。~~あんまり読みたくないし、読んでも処理系が仕様に則っているかどうかも定かではないという。。~~

Permalink | コメント(0) | トラックバック(0) | 19:30

idトラックバック

2011-12-01

妥当性とは仕様の所作 - SQLインジェクション対策とバリデーション

繰り返しになりますが、妥当性検証は仕様の問題であってセキュリティ対策ではありません。

バリデーションは仕様の問題であってセキュリティ対策ではないとはどういうことか説明します。SQLインジェクションの対策は、1. SQLを文字列結合で作らない 2. プレースホルダを使うです。バリデーションは関係ありません。

簡単な例

Webアプリケーションで郵便番号を指定するフォームを考えましょう。

日本の郵便番号を指定するフォームの設計でよく見るものは大きく分けて2通りあり、上3桁と下4桁を別々に入力させるものと、1つのフォームにまとめて入力させるものです。住所から補完させる設計もありえますがここではおいておきます。

<input type="text" name="postal_code_1"> - 
<input type="text" name="postal_code_2">

<input type="text" name="postal_code"> 例：100-0001

どちらを選んでもよいのですが、選んだ設計によって仕様が変わることに注意してください。

クエリパラメタ postal_code_1 を受け取ったサーバは数値のみを妥当な入力として受け入れる仕様となるでしょう。その際にいわゆる半角数字のみを受け入れるのか、いわゆる全角数字が入力されたら適切に変換してあげるのかを決める必要があります。

postal_codeの場合は数値のみ7桁の入力を受け入れるか、ハイフンを必須とするか、いわゆる全角のハイフンはどうかなどをさらに意思決定する必要があります。

ここでは以下の一連の意思決定をし、それを共有して仕様としたとします。

クエリパラメタ postal_code_1 は郵便番号上3桁の数値文字列を受け取る
クエリパラメタ postal_code_2 は郵便番号上4桁の数値文字列を受け取る
いわゆる全角文字の入力については、いわゆる全角数値がUTF8で表現されている場合のみ受け入れた上でサーバ側でいわゆる半角数値に変換する
入力が数値のみで構成されているが必要な桁数に満たない場合は、「7桁の郵便番号を入力してください」というメッセージを表示して再入力を促す
それ以外の入力については、「郵便番号を入力してください」というメッセージを表示して再入力を促す

ここで行うバリデーションは、postal_code_1/postal_code_2 それぞれが「数値」のみで構成されているかどうか、必要な桁数であるかどうか、になります。

ここまでの仕様をさだめないとバリデーション（妥当性検証）は定義できないことに注意してください。何をもって妥当とするかは仕様が定めるものであり、従って仕様がなければ妥当性を論じることはできません。また、postal_codeに7桁分入力される場合は全く異なるバリデーションを行うことになります。

バリデーションがセキュリティ対策とは異なる具体例

マイクロブログサービスを作るとしましょう。

ユーザのつぶやきは最大140文字（バイト数ではなく文字数）
空のつぶやきは受けつけない
妥当なUTF8エンコーディング文字列のみを受けつける
140文字を超えるつぶやきはメッセージを表示して再入力を促す

この仕様のもとでできるバリデーションは

つぶやきのエンコーディングが妥当かどうか
文字数が1文字以上140文字以下であるかどうか

だけです。「"K&R" from <O'Reilly>」のようなつぶやきは仕様上妥当な入力ですので受け入れる必要があります。

この入力にはSQLやHTMLとして特別な意味を持つ文字が含まれていますが、そもそもRDBMSとのやり取りで適切にプレースホルダを使用していたり、HTMLとして出力する直前にHTMLとして特別な意味を持つ文字を適切にエスケープしていれば気にする必要はありません。

ここで、「危険ｗｗｗな文字列を削除すればいいんじゃね？ｗｗｗ俺天才ｗｗｗｗｗ」として「KR from OReilly」のようにしてしまう愚行など、何が正しいか理解しないで不適切な対症療法をとることを専門用語で「サニタイズ脳」と言います。

バリデーションは仕様の問題であってセキュリティ対策ではないというのはこういう意味です。繰り返しになりますが、SQLインジェクションの対策は、1. SQLを文字列結合で作らない 2. プレースホルダを使うです。バリデーションは関係ありません。

文字列結合でSQLを構築するなど不適切な取り扱いをしている場合は、上記のような仕様ではバリデーションを行なってもおかしなSQLになることでしょう。

Permalink | コメント(0) | トラックバック(1) | 14:35

idトラックバック

2011-05-30

#tqrk03 で発表した内容がアレだったので、無限ストリームをrubyでやった

東急Ruby会議(#tqrk03)に遊びに行ったら、@tadasyの罠にハメられて無意味に3分LTすることになった。

なんの準備もしてなかったので、空気を読まずに前の記事に書いたHaskellがすげえっていう話をすることにした。

だってRubyわかんねーんだもん。

んで、みんな酒が入った勢いで笑ってたが何一つ意味分からなかったと思われるので、無限ストリームのやつをRubyに移植した。私はRubyまったくわからないので、なんかおかしな書き方だったら教えてほしい。

プログラムだけ書いて力尽きたので、解説が必要な人はSICPを読んでほしい。

class Stream
	def initialize(car, &cdr)
		@car = car
		@cdr = cdr
	end

	def car
		@car
	end

	def cdr
		@cdr.call
	end

	def take(n)
		(n == 0) ? [] : (cdr.nil?) ? [@car] : cdr.take(n-1).unshift(@car)
	end

	def ref(n)
		(n == 0) ? @car : cdr.nil? ? nil : cdr.ref(n-1)
	end

	def map(&f)
		Stream.new(f.call(@car)) { cdr.map(&f) }
	end
end

class << Stream
	def zipWith(s1, s2, &f)
		car = f.call(s1.car, s2.car)
		new(car) { zipWith(s1.cdr, s2.cdr, &f) }
	end

	def repeat(x)
		new(x) { repeat(x) }
	end

	def integerStartinFrom(n)
		new(n) { integerStartinFrom(n+1) }
	end

	def integer
		integerStartinFrom(1)
	end

	def add(s1, s2)
		zipWith(s1, s2) {|a, b| a + b }
	end

	def mul(s1, s2)
		zipWith(s1, s2) {|a, b| a * b }
	end

	def partialSums(s)
		new(s.car) { add(repeat(s.car), partialSums(s.cdr)) }
	end
end

class Series
end

class << Series
	def integrate(s)
		Stream.zipWith(s, Stream.integer) {|a, b| a / b }
	end

	def exp
		Stream.new(1.0) { integrate(exp) }
	end
	def cos
		Stream.new(1.0) { integrate(sin.map{|a| -a }) }
	end
	def sin
		Stream.new(0.0) { integrate(cos) }
	end
end

def sum(array)
	array.inject(0) {|a, b| a + b }
end

ones = Stream.repeat(1)
integer = Stream.integer

p ones.take(10)
p integer.take(10)
p Stream.add(ones, integer).take(10)
p Stream.mul(integer, integer).take(10)
p Stream.partialSums(integer).take(10)

p Stream.partialSums(Series.exp).ref(10)
p Math.exp(1)
p Stream.partialSums(Series.sin).ref(10)
p Math.sin(1)
p Stream.partialSums(Series.cos).ref(10)
p Math.cos(1)

Permalink | コメント(0) | トラックバック(1) | 00:10

idトラックバック

2011-05-29

HaskellでSICP3章のストリームを書いてみたらすごかった

言語仕様を見て、これならSICP3章だろうと思ってやってみたら、ほとんどが2行（うち型宣言が1行）で書けてわろた。あとで解説とか書くかもしれないし書かないかもしれない。

module Main where

addStream :: Num a => [a] -> [a] -> [a]
addStream = zipWith (+)

scaleStream :: Num a => a -> [a] -> [a]
scaleStream factor = map (*factor)

mulStream :: Num a => [a] -> [a] -> [a]
mulStream = zipWith (*)

integersStartingFrom :: Num a => a -> [a]
integersStartingFrom n = n : integersStartingFrom (n + 1)

ones :: Num a => [a]
ones = repeat 1

integers :: Num a => [a]
integers = integersStartingFrom 1

partialSums :: Num a => [a] -> [a]
partialSums (x:xs) = x : addStream (repeat x) (partialSums xs)

integrateSeries :: Fractional a => [a] -> [a]
integrateSeries xs = mulStream xs (map recip integers)

expSeries = 1.0 : integrateSeries expSeries
cosSeries = 1.0 : integrateSeries (map negate sinSeries)
sinSeries = 0.0 : integrateSeries cosSeries

mulSeries :: Num a => [a] -> [a] -> [a]
mulSeries (a:as) (b:bs) = a*b :
	addStream (scaleStream a bs) (mulSeries as (b:bs))

sqrtStream :: Fractional a => a -> [a]
sqrtStream x = guesses
	where
		guesses = 1.0 : map improve guesses
		improve guess = average guess (x/guess)
		average a b = (a+b)/2

eularTransform :: Fractional a => [a] -> [a]
eularTransform (x0:x1:x2:xs) = x' : eularTransform (x1:x2:xs)
	where
		x' = x2 - (square (x2 - x1)) / (x0 - 2*x1 + x2)
		square x = x * x

piSummands :: Fractional a => a -> [a]
piSummands n = 1.0/n : map negate (piSummands (n+2))

piStream :: Fractional a => [a]
piStream = scaleStream 4 (partialSums (piSummands 1))

makeTableau :: ([a]->[a]) -> [a] -> [[a]]
makeTableau t xs = xs : makeTableau t (t xs)

acceleratedSequence :: ([a]->[a]) -> [a] -> [a]
acceleratedSequence t xs = map head (makeTableau t xs)

ln2Summands :: Fractional a => a -> [a]
ln2Summands n = 1/n : map negate (ln2Summands (n+1))

ln2Stream :: Fractional a => [a]
ln2Stream = partialSums (ln2Summands 1)

geometricSeris :: Num a => a -> a -> [a]
geometricSeris a r = map ((a*).(r^)) (integersStartingFrom 0)

polySeries :: Num a => a -> [a]
polySeries = geometricSeris 1

applySeries :: Num a => [a] -> a -> [a]
applySeries series x = (partialSums (mulStream series (polySeries x)))

integral :: Num a => [a] -> a -> a -> [a]
integral integrand initial dt = int where
	int = initial : addStream (scaleStream dt integrand) int

solve' :: Num a => (a->a) -> a -> a -> [a]
solve' f y0 dt = y where
	y = integral dy y0 dt
	dy = map f y

solve :: Fractional a => (a->a) -> a -> Int -> a
solve f y0 n = (solve' f y0 dt) !! n
	where dt = 1 / (fromIntegral n)

solve2nd :: Num a => a -> a -> a -> a -> a -> [a]
solve2nd a b dt y0 dy0 = y
	where
		y   = integral dy y0 dt
		dy  = integral ddy dy0 dt
		ddy = addStream (scaleStream a dy) (scaleStream b y)

solve2nd_gen :: Num a => (a -> a -> a) -> a -> a -> a -> [a]
solve2nd_gen f dt y0 dy0 = y
	where
		y   = integral dy y0 dt
		dy  = integral ddy dy0 dt
		ddy = zipWith f dy y

Permalink | コメント(0) | トラックバック(0) | 16:05

idトラックバック

2011-04-22

世の中から名刺をなくしたい。

名刺交換とかうざい。

私は営業職とかじゃないからだろうが、もらっても99.9％電話もメールもしない。

だからここ数年名刺は持ち歩かないことにして、「すいません切らしてまして」ということにしている。

実際に連絡を取る人にとっても、無駄の多い馬鹿げたプロトコルだ。（私はそんなことしないで捨てるが）いちいち名刺を見て氏名と電話番号、メアドを連絡先アプリに手で打ち込むとかやってられないし、OCRかけるとかバカげている。はなから電子データで交換すればいいのだ。

そもそも連絡先交換ならTwitterだのFacebookだののIDでも教えてくれれば十分なのだ。むしろこちらのほうがつぶやきから人となりが分かったりアバターなんかで視覚的な識別が可能なぶん情報量が多い。

というわけで世の中から名刺を撲滅するためのサービスを妄想してみた

機能仕様：

スマフォアプリとして実装する
Bumpのようなやり方で事前に設定した連絡情報を交換できる
iPhone <-> Android間でも交換できる
連絡先情報はサーバ側に保存され、連絡先を更新しても、すでに交換した人たちは常に最新の情報を参照する
ただしスマフォがオフラインになったりサーバがダウンしてもいいようにクライアント側にもキャッシュする
クライアントサイドで検索したり電話したりメールを出したりTwitterのDMだしたりできる

Plaxoみたいな感じかもしれない。

でもこのモデルは機能しないことがすぐ分かる。これだけではこのサービスのユーザ同士でしか連絡先を交換できない。しかしはじめて会う人がこのサービスを利用しているかどうか知るすべがない。

このサービスを使ってる人と使ってない人の間でも上手く機能するやり方を考えなければいけない。

追加機能：ユーザ <-> 非ユーザ間での交換

後方互換モードとして名刺のOCR機能を提供する
- 携帯のカメラで名刺を撮影するとOCRかけて検索したりできるようになる
- つまり、最初は単独の名刺管理アプリとしても使えるようにする
非ユーザが写真を撮ることを許可してくれたら、その場で携帯のカメラで撮影して名刺と関連付けて顔画像を保存できるようにする
その場で相手を招待するメールを送れる

二番目の機能は必須だ。典型的な成功ストーリーは次のようになる：

普通に名刺交換する
普通にミーティングする
普通にミーティング終わる
最後にちょっと声をかける
「ちょっといいですか。実はこういう名刺管理アプリを使っているんですが（名刺と顔写真が並んでいるアプリを見せる）、顔写真を取らせていただいていいですか？」
「いいですよ。面白そうなアプリですね。私も使ってみようかな」
「お、それでは招待しましょうか？」

私はヘビー名刺ユーザじゃないので伝聞なのだが、大量の名刺を交換する人たちのライフハックとして、「名刺にその人の特徴をメモっておく」というのがあるらしい。しばらくするとどういう人だか忘れてしまうから。

そう考えると、失礼に当たらなければ顔写真と名刺を関連付けておくのは便利な機能のように思える。（一般的に言って失礼かどうかは良く解らん）

そして、ユーザがこのアプリについて説明して顔写真を撮らせてもらうというインセンティブを用意すると、これは無料でアプリの宣伝をしてもらっているようなものである。撮られる側も何百人かにひとりは「へえ、ちょっといいじゃん。使ってみようかな」と思ってくれるかもしれない。もし撮られるのが嫌なら拒否すればよい。あるいは最初はスルーかもしれないが、同じような体験を何回もすれば認知度が上がっていくはずだ。

こういうのは何でもそうだが、ユーザが少ないうちは誰も見向きもしない。ところがウランの臨界のように、ある狭いコミュニティ内でのユーザ数があるしきい値を超えると、むしろ使っているほうが普通、みたいになるはずだ。そうなればコミュニケーションの1stフェイズはこのアプリでの連絡先交換となり、名刺はまだ使ってない人に対するfallbackになる。ここまでくれば時間の問題で名刺を撲滅できる。そうできなければ凡百のサービスと同じように、単に終わる。

業界によっては難しいだろうが、ギーク層とかネット業界とかの新しい物好きクラスタではそれなりに受け入れられそうな気もする。

とか妄想した金曜の昼。

Permalink | コメント(3) | トラックバック(0) | 13:27

idトラックバック

2011-03-25

ソフトウェアエンジニアが知っておくべき偉大な30人

@ockeghem「ケン・トンプソンとデニス・リッチーを知らない…」をトリガーとして、ソフトウェアエンジニアが知っておくべき偉大な30人とか誰か書かないかな。もうある?

http://twitter.com/ockeghem/status/51110649429889024

適当に挙げてみた。ケン・トンプソンやK&R辺りからの連想なので粒度がまちまち。こういうラインアップだと、チューリングとかシャノンとかノイマンとかはなんか違う感じ。

名前	特に有名なand/or影響が大きい実績
ケン・トンプソン	C, Unix
デニス・リッチー	C, K&R, Unix
ブライアン・カーニハン	C, K&R
アラン・ケイ	オブジェクト指向, Smalltalk
ダイクストラ	構造化プログラミング
ジョン・マッカーシー	Lisp (関数型言語)
ドナルド・クヌース	TeX, the art of computer programing
リチャード・ストールマン	GPL, Emacs
ティム・バーナーズ・リー	www, URI, HTTP, HTML
マーク・アンドリーセン	Mosaic, Netscape
リヌス・トーバルス	Linux
ビル・ゲイツ	MS-Dos, Windows
ディッフィーとヘルマン	公開鍵暗号モデル
RSAの3人	公開鍵暗号の実装

世界初の高級言語 FORTRANのジョン・バッカスとかどうなのよ？とか言われそうだけど、僕は調べるまで名前を知らなかった。

それなりにメジャーな言語の発明者系だとストラウストラップ(C++) ゴスリン(Java) ラードフ(PHP) ラリー(Perl) 松本(Ruby) とかは↑の人たちと比べると影響度がやや小さい気がする。

<追記>

気が向いたときに追記

名前	功績
アントニー・ホーア	クイックソート, CSP
ニクラウス・ヴィルト	Pascal,「アルゴリズム＋データ構造＝プログラム」
ジョンバッカス	FORTRAN, BNF記法
エドガー・F・コッド	リレーショナルモデル(RDB)
ビル・ジョイ	BSD, vi, csh, SUN
アンドリュー・タネンバウム	MINIX

Permalink | コメント(8) | トラックバック(0) | 13:30

idトラックバック

2010-05-26

【速報】減量終了のお知らせ

本日の計測で体重57.75kg 体脂肪率15.4%を記録いたしました。これをもちましてご好評を賜っておりました減量を終了させていただきますことをお知らせします。

開始：2/13 71.55kg 26.3%

終了：5/26 57.75kg 15.4%

以上、よろしくお願いします。

Permalink | コメント(2) | トラックバック(1) | 15:58

idトラックバック

2010-04-20

社内SICP読書会読了

社内SICP読書会、読了しました。

社内、っつーのが、我ながらすごいよね。よく社内で読了したなあと思います。それはそれで秘訣があるけど秘密。

Permalink | コメント(0) | トラックバック(0) | 00:25

idトラックバック

2010-04-09

[SQLインジェクション対策]Webアプリケーションとかの入門本みたいのを書く人への心からのお願い。

SQLインジェクションについて書くときに以下のメッセージを必ず含めて欲しいです。

単にプリペアドステートメントを使え
絶対に文字列結合でSQLを構築しようとしてはいけない
IPAの「安全なSQLの呼び出し方」を読むこと

なんでこんなことを書くかというと、同僚が献本されてた「プロになるためのWeb技術入門」なる本のSQLインジェクションの項で、SQLインジェクションの対策として以下のように書いてあったからです*1。

a) 値をバリデーションする
b) プリペアドステートメントを使う

ダメです。間違っています。単に間違っているだけでなく救いがたく間違っています。正しいSQLインジェクション対策はこう書くべきです。

単にプリペアドステートメントを使え
文字列結合でSQLを構築するな

イケてない本を書く人はなんで値のバリデーションをプリペアドステートメントよりも先に書くんですか？値のバリデーションは必要ですが、それはプログラムの正常な挙動を担保するためであって、SQLインジェクション対策のためではありません。*2

そもそもSQLインジェクションされる脆弱性というのは、単にマヌケがプリペアドステートメントを使わずに文字列結合でSQLを作るようなバグプログラムを書いたというだけです。SQLインジェクションはクラッカーの巧妙な攻撃手法とかではありません。単なるバグです。対策はプリペアドステートメントを使うことだけです。大事なことなので何回も言いました。詳しく知らない人は上記の「安全なSQLの呼び出し方」を読みましょう。

なお上記の本とは関係ないのですが、"SQLのメタキャラクタを適切にエスケープせよ"というメッセージは、字面だけ見れば正しいのですが、現実的には間違っています。私は10年プログラマをしていますが、Web系でプリペアドステートメントがサポートされていないような環境でプログラムを書けといわれたことは一度たりともありません。だから初心者向けの本では「単にプリペアドステートメントを使え」というメッセージで十分だと思います。

SQLのメタキャラクタを適切にエスケープしてSQLを作らなければならない、作るべき場合というのは、ぱっと思いつくのは以下のような場合です*3。

あなたが作ったRDBMSにはプリペアドステートメント機構がないのでプリペアドステートメントを実装している
あなたが作ったプログラミング言語にはRDBMSへ繋ぐクライアントライブラリの既存の実装がなく、Cで書かれたライブラリを呼び出すこともできない設計なので仕方なく自分で実装している
あなたの製品が動く環境は組み込みデバイスなので、既存のRDBMSのクライアントライブラリがコンパイルできず、相当するものを自分で作っている

いずれも初心者が遭遇するような場面ではありません。病的な例外と言ってもいいです。したがって、SQLインジェクションの対策メッセージは、現実的にはこうなります。

「単にプリペアドステートメントを使え」

それ以外のSQLインジェクションの文脈では些末すぎること（バリデーションやエスケープ）が書いてある本は燃やしてもいいのではないかと思います。