Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Sign up for free
Menu
Search
Features
All features
Private URLs
Password Protection
Custom URLS
Scheduled publishing
Remove Branding
Restrict embedding
Deck Collections
Notes
Features
All features
Private URLs
Password Protection
Custom URLS
Scheduled publishing
Remove Branding
Restrict embedding
Deck Collections
Notes
Explore
Featured decks
Featured speakers
Programming
Technology
Storyboards
Explore
Featured decks
Featured speakers
Programming
Technology
Storyboards
Pricing
Search
Sign in
Sign up for free
NilAway による静的解析で「10 億ドル」を節約する #kyotogo / Kyoto ...
Search
y_taka_23
December 14, 2024
Technology
1.1k
7
Share
Embed
Copy iframe code
Copy JS code
Copy link
Start on current slide
NilAway による静的解析で「10 億ドル」を節約する #kyotogo / Kyoto Go 56th
Kyoto.go #56 オフライン忘年 LT 会で使用したスライドです。
y_taka_23
December 14, 2024
Transcript
22 slides
#kyotogo NilAway による静的解析で 「10 億ドル」を節約する チェシャ猫 (@y_taka_23) Kyoto.go #56 オフライン忘年
LT 大会 (15th Dec. 2024)
#kyotogo 第 1 問(初級)
#kyotogo 何が起こる? 1. 改行のみ出力して正常終了 2. 何も出力せず正常終了 3. panic になる
#kyotogo 何が起こる? 1. 改行のみ出力して正常終了 2. 何も出力せず正常終了 3. panic になる【正解】
#kyotogo 第 2 問(中級)
#kyotogo 何が起こる? 1. 改行のみ出力して正常終了 2. 何も出力せず正常終了 3. panic になる
#kyotogo 何が起こる? 1. 改行のみ出力して正常終了 2. 何も出力せず正常終了 3. panic になる【正解】
#kyotogo 第 3 問(上級)
#kyotogo あなたは nil 判定をどうやって解いた?
#kyotogo 無効な参照によるエラー • 10 億ドルの過ち(The Billion Dollar Mistake) ◦ null
を「発明」した Hoare による 2009 年の後悔の言 ◦ Dijkstra 「独身者が全員一人の null と重婚した状態」 • nil 参照は実行時エラーとしてはかなり厄介 ◦ あらゆる型に対し nil チェックが必要になってしまう ◦ 原因と結果がコード的にも時間的にも遠く離れがち 参考:https://www.infoq.com/presentations/Null-References-The-Billion-Dollar-Mistake-Tony-Hoare/
#kyotogo 実行前に静的に nil 参照を検出したい
#kyotogo NilAway by Uber https://github.com/uber-go/nilaway
#kyotogo NilAway の特徴 • ソースコードから静的に nil エラーを発見 ◦ 関数やパッケージを跨いだエラーが検知可能 ◦
nil になり得る具体的な原因をメッセージとして表示 • go/analysis パッケージを使用 ◦ 内部は複数の Analyzer でモジュール化され並列動作 ◦ golangci-lint や bazel+nogo などのツールから呼び出し可能 参考:静的解析のモジュール化(https://zenn.dev/tenntenn/books/d168faebb1a739/viewer/9d590e)
#kyotogo NilAway による検査結果 • ソースコードの nil flow を解析 ◦ foo()
が nil リテラルを返却(10 行目) ◦ foo() を参照(6 行目)
#kyotogo nil flow による因果推論 • nil の発生と参照の因果関係を辺としたグラフを構築 ◦ 発生:nil リテラル、var
宣言、関数の引数など ◦ 参照:デリファレンス、フィールドアクセスなど • 各ノードに対して「nil であり得るか」をマーク ◦ 発生側を true、参照側を false として伝播・確定させていく ◦ true かつ false の矛盾したノードが現れたら nil エラー
#kyotogo *foo(x, bar()) bar() foo の x foo の y
foo(x, y) main の x bar の nil リテラル var 宣言 引数 return 引数 デリファレンス return if x == nil
#kyotogo *foo(x, bar()) bar() foo の x foo の y
foo(x, y) main の x bar の nil リテラル var 宣言 引数 return 引数 デリファレンス return if x == nil 赤は nil 確定 緑は nil 不可能 黒は矛盾
#kyotogo *foo(x, bar()) bar() foo の x foo の y
foo(x, y) main の x bar の nil リテラル var 宣言 引数 return 引数 デリファレンス return if x == nil 赤は nil 確定 緑は nil 不可能 黒は両方(矛盾)
#kyotogo というかそれは自明では?
#kyotogo 冒頭の第 3 問への回答 • ちゃんとした形式化の複雑さ ◦ 人間も基本的には因果関係を辿って nil を発見
◦ 意外なトリックがあるという感じではない ◦ しかしアルゴリズムに落とし込むとなると割と複雑 • 計算機科学の裏付けによるスケール可能性 ◦ 因果グラフ推論は 2-SAT 問題とみなせ、線形時間で判定可能
#kyotogo まとめ • nil 参照は厄介なタイプの実行時エラー ◦ 考案者 Hoare 自身も後に「10 億ドルの過ち」と認める
• NilAway により静的に解析が可能 ◦ nil の可能性を制約としてグラフ上で伝播させ矛盾を検出 • 人間が頭の中で行う「普通にわかる」の形式化 ◦ 意外と複雑な処理だが、厳密に記述できればスケール可能
#kyotogo Save the Billion Dollars by NilAway! Presented by チェシャ猫
(@y_taka_23)
More Decks by y_taka_23
See All by y_taka_23
なぜ「決定性」が 決定的に重要なのか? Durable Execution 基盤の数理的理解 #serverlessjp / ServerlessDays Tokyo 2026
ytaka23
4
1.8k
形式手法特論:Hyperproperty とモデル検査 #kernelvm / Kernel VM Study Tokyo 19th
ytaka23
1
1.2k
形式手法特論:公平性制約の位相的特徴づけ #kernelvm / Kernel VM Study Kansai 12th
ytaka23
1
1.1k
形式手法特論:SMT ソルバで解く認可ポリシの静的解析 #kernelvm / Kernel VM Study Tsukuba No3
ytaka23
1
1.4k
形式手法特論:コンパイラの「正しさ」は証明できるか? #burikaigi / BuriKaigi 2026
ytaka23
17
8.9k
形式手法特論:CEGAR を用いたモデル検査の状態空間削減 #kernelvm / Kernel VM Study Hokuriku Part 8
ytaka23
3
1k
形式手法特論:位相空間としての並行プログラミング #kernelvm / Kernel VM Study Tokyo 18th
ytaka23
3
2.6k
AWS と定理証明 〜ポリシー言語 Cedar 開発の舞台裏〜 #fp_matsuri / FP Matsuri 2025
ytaka23
13
7.1k
問 1:以下のコンパイラを証明せよ(予告編) #kernelvm / Kernel VM Study Kansai 11th
ytaka23
3
1.3k
Other Decks in Technology
See All in Technology
攻撃と守りは何が変わり、何が変わらないのか~最近の不正アクセスから考える、リスク評価と標準の使いどころ
oidfj
2
300
パスワードのない鍵で、 データを手元に置く
ginjihayashi
0
390
認知負荷の減らし方 ~開発にも日常業務にも活かせるノウハウ~
minorun365
PRO
15
9.6k
文書画像からの情報抽出を行うエージェントを、軌跡の正解データ無しで作れるか
sansantech
PRO
2
220
市販IoT機器や自作IoT機器とHomeAssistantを駆使して家の電気代をできる限り見える化する方法の考案
harutiro
0
410
コピーオンライト型ファイルシステムと ランダム書き込み
sat
PRO
2
130
Go でトランザクション、どう書いてますか?
knwoop
1
210
Del vibe coding a un Desarrollo (agéntico) fiable
jcabot
0
200
社内アプリ基盤「Quartz」による、 非エンジニアとAIに本番デプロイを 任せても壊れないプラットフォームの設計
staka121
PRO
1
180
20261113_JAWS_Osaka
takuyay0ne
1
600
おうち環境でも「なるべく止めたくない!」 ― おうち環境の機器冗長化の理想と現実
yuutosi
1
640
HTTP QUERY時代の型安全な検索APIをKotlinで設計する
sansantech
PRO
1
120
Featured
See All Featured
Sharpening the Axe: The Primacy of Toolmaking
bcantrill
46
3.1k
The Cult of Friendly URLs
andyhume
79
7.1k
Accessibility Awareness
sabderemane
1
310
The Myth of the Modular Monolith - Day 2 Keynote - Rails World 2024
eileencodes
28
3.8k
What the history of the web can teach us about the future of AI
inesmontani
PRO
3
830
Side Projects
sachag
456
43k
Connecting the Dots Between Site Speed, User Experience & Your Business [WebExpo 2025]
tammyeverts
11
1.1k
Statistics for Hackers
jakevdp
799
230k
Are puppies a ranking factor?
jonoalderson
2
4.2k
Java REST API Framework Comparison - PWX 2021
mraible
34
9.8k
Data-driven link building: lessons from a $708K investment (BrightonSEO talk)
szymonslowik
1
1.4k
Practical Orchestrator
shlominoach
192
12k