この記事は、Merpay & Mercoin Advent Calendar 2024 の記事です。
はじめに
メルペイBalanceチームでバックエンドエンジニアをしている@kobaryoと申します。
皆さんは日々の開発の中で静的解析を利用していますか？静的解析を利用することで、コードが何かしらのルールに従っているということを保証することができます。プログラムの中にコンパイル時に検出できない何かしらのルールがあり、それに違反していることにプログラムを動かして初めて気付く、という事態になる前に違反を検出することができます。本記事でこれから示す事例は、静的解析で検出すべき良い事例なのではないかと思います。
メルペイの多くのチームでは、データベースとしてSpannerを採用しています。しかしながらSpannerを扱う上で、「allow_commit_timestampである列にアプリケーション側で生成した現在時刻を入れてしまう」というミスがしばしば見られます。これをしてしまうとSpannerへの列の挿入や更新が確率的に失敗してしまうため、テストやQAでこのミスを発見できず、インシデントに繋がってしまう恐れがあります。
テストやQAでこのミスに気付く可能性もあるのですが、確率的にエラーが発生する性質上、実際にプログラムを動かしてこのミスを検出するのには限界があります。
そこで、Goのtime.Now()がSpannerのMutationに含まれてしまっているかをデータフロー解析で検知する静的解析ツールnowdetを作成しました。
本記事では、まずこのようなエラーが発生する背景から説明して、次にデータフロー解析の概要、nowdetの実装のコアな部分、最後に今後の展望について述べます。
背景
SpannerではTIMESTAMP型の列にallow_commit_timestampオプションを付けることができます。このような列にプレースホルダ文字列spanner.commit_timestamp()を挿入すると、その名の通りコミット時のタイムスタンプに置き換えられて保存されます。Spannerはexternal consistencyという強い一貫性を持っており、これによりトランザクションの順序とタイムスタンプの順序が一致します。そのため、変更履歴といった順序が重要となる処理を、単にコミットタイムスタンプを参照することで実装できます。
このallow_commit_timestampである列にはspanner.commit_timestamp()だけでなくアプリケーション側で生成したタイムスタンプを挿入することもできるのですが、過去のタイムスタンプでなければならないという制限があります。アプリケーションで現在時刻を生成しこの列に挿入しようとした場合、Spanner内のクロックとアプリケーションサーバーのクロックは一致していないために、アプリケーションで生成されたタイムスタンプがSpanner内部より未来のタイムスタンプになる可能性があります。この場合、Cannot write timestamps in the futureとエラーが発生してしまいます。
実際、私は当初この仕様を知らず、このオプションが付いている列にspanner.commit_timestamp()ではなく誤ってGoのtime.Now()で生成した値を挿入してしまっていました（幸いなことにテストでミスが発覚しました）。また、社内のSlackでCannot write timestamps in the futureで検索すると、多数のメッセージがヒットすることから、自分と同じミスをしている開発者は多いことが分かります。
経験上、このミスをした場合に実際にエラーが発生する可能性はそこまで低くないのでミスに気づきやすい、また一度このミスを経験すると同じミスは犯しにくいように感じます。しかしながら、やはり確率的にエラーが出るという点で、静的解析によってこのミスを検知する価値があると私は考えています。
データフロー解析
静的解析の手法の1つであるデータフロー解析は、プログラムの実行経路に沿って発生するデータの流れに関する情報を求める手法の総称のことです。例えば、変数がその実行経路を通っても更新されない、といったことを静的に検知する際に利用します。以下のようなプログラムについて考えます。
func example(b bool) (int, int){
var x = 0 // may be changed
var y = 0 // immutable
if b {
x = 1
}
return x, y
}この例のyの値は更新されていないので、yは実際には定数として定義しても問題ありません。この例では、データフロー解析で各プログラムポイントで各変数がどのポイントで定義された値を保持しているか（到達定義）を求めることで、このことを検知することができます。まず、上記のプログラムを制御フローグラフ (CFG)で表します。
このとき、各プログラムポイントにおける到達定義は以下のようになります。
P5のreturn文後のyの到達定義がP1のみであり、yはP1で定義されたものだったので、yを定数として定義しても問題ないということが分かりました。実際にはプログラムにループや再帰が含まれていて、到達定義を一度求めた後に再計算しなければならない可能性があり、到達定義が収束するまでこの処理を繰り返します。
今回のような定数で定義できる変数の検出以外にもデータフロー解析を利用することができます。例えばあるbool型の変数がどの実行経路を通っても常にfalseであることを検知したり、あるポインタをdereferenceする際、そのポインタがnilであるような実行経路が存在することを検知したりできます。この記事を読んでいる皆さんも、IDEや静的解析ツールでこのような機能を見たことがあるかと思います。
nowdetの実装
今回作成したnowdetも上記のnilポインタを検知する例とほぼ同様の処理をして、SpannerのMutationにtime.Now()が含まれる実行経路が存在するかどうかをチェックしています。
もう少し具体的な処理を例で示します。例えば、以下のような関数について考えます。
func insert(ctx context.Context, client *spanner.Client, isNow bool) error {
var now time.Time
if isNow {
now = time.Now()
} else {
now = time.Date(2020, 1, 1, 0, 0, 0, 0, time.UTC)
}
_, err := client.Apply(ctx, []*spanner.Mutation{
spanner.Insert(
"Users",
[]string{"name", "created_at"},
[]interface{}{"Alice", now},
),
})
return err
}この関数では、引数のisNowにtrueが与えられるとアプリケーション側で生成した現在時刻がSpannerのテーブルに挿入されてしまいます。このプログラムをCFGで表します。nowdetでは解析対象のGoプログラムを静的単一代入形式 (SSA)に変換し、それをデータフロー解析しているので、実際は以下のようになります（赤字がtime.Now()が関連している部分）。
基本的には、time.Now()が代入された変数をマークし、マークされた変数が他の変数に代入される、または含まれた際にその変数にもマークを伝播させるという方針になっています。
例えば、関数を呼び出した際にその関数がtime.Now()だった場合にマークをします。上記の例では、P1にt0 = time.Now()があるので、t0をマークします。その他にも、プログラムの実行経路によって変数の値が変わる場合、そのうちの一つがマークした変数から来たものであればマークします。上記の例のP3のt1 = phi [1: t0, 3: t20]では、t1はプログラムの実行経路によってt0かt20になることを表しているので、t1もマークします。
このような処理を繰り返し、最終的にP20でspanner.Insertの引数にマークされた変数t13が含まれるため、Mutationにtime.Now()が含まれたと判断されて、アラートを返すという流れになっています。
かなり細かい話をすると、実はスライスが関わる処理では単純にマークをするのではなく、グラフを作っています。上で示した例だと、t13がマークされていれば正しく検知ができて、そのt13はP19でt13 = slice t8[:]で定義されています。また、そのt8はP12のt8 = new [2]interface{} (slicelit)で定義されています。t8が定義された時点でt8がマークされていないと検知が成功しないのですが、実際にはt8が定義された後のP16からP18で、t11 = &t8[1:int]・t12 = make interface{} <- time.Time (t1)・*t11 = t12と、t8とマークされた変数t1が結びついています。そのため、プログラムを上から順に見ていくだけだとt8をマークすることができず、うまく検知することができません。
この問題を解決するため、スライスが関わる処理では、スライスから辺を辿って要素に到達できるようなグラフを生成することで対策をしています。具体的には、P16のt11 = &t8[1:int]と、P18の*t11 = t12の処理で以下のようなグラフが作られます。
そして、P19のt13 = slice t8[:]でt8がマークされているかをチェックする代わりに、このグラフをt8から辿り、マークされている変数に到達すればt13をマークする、という処理に変更します。このグラフはt12に到達し、t12はP17のt12 = make interface{} <- time.Time (t1)でマークされているため、t13をマークすることができます。
今後の展望
スキーマを取得し偽陽性を避ける
現在の実装では、実際に列がallow_commit_timestampオプションを持っているかどうかにかかわらずtime.Now()が挿入されうるかを検知しています。allow_commit_timestampオプションを利用せずアプリケーション側で生成した現在時刻を挿入するケースももちろんあるので、スキーマを取得し、allow_commit_timestampオプションを持っている列に関してのみ検知するようにしたいと考えています。
関数を跨いでtime.Now()を検出する
現在の実装では、同じ関数内でtime.Now()を呼び出し、それをMutationに入れている場合のみ検知します。異なる関数もしくはパッケージで呼び出したtime.Now()がMutationに入る場合にも検知できるようにしたいと考えています。懸念としては計算時間の増加があるのですが、究極的にはtime.Now()からMutationまでのフローのみをチェックすればよく、無駄な基本ブロック（CFGの頂点）を解析対象から外す方針にしたいです。
ポインタの扱い
スライスが絡んだ際にどのように検知しているかを上で述べたのですが、ポインタが関わるパターン一般に関してうまく動作するわけではありません。先述のグラフの例だと、t8とt12は一方から他方に辿れるというよりは、イコールになるべきです。全ての場合に対応するのは直観的には難しい気がしているので、実用上耐えうるような制限を設け、全ての場合は検知できないが有用ではある、という状態を目指したいです。
おわりに
以上、Goのtime.Now()がSpannerのMutationに含まれていないかを、nowdetがどのようにして検知しているかについて説明しました。Balanceチームでは（主に別の理由で）time.Now()がコードに含まれていないかをCIでgrepしてチェックしているのですが、誤検知が多いという問題があります。nowdetがこのgrepを置き換えられるよう、これからも開発を続けていきます。
次の記事は@orfeonさんです。引き続きお楽しみください。
