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
形式手法の 10 メートル手前 #kernelvm / Kernel VM Study Hok...
Search
Sponsored
·
Your Podcast. Everywhere. Effortlessly.
Share. Educate. Inspire. Entertain. You do you. We'll handle the rest.
→
y_taka_23
November 09, 2024
Technology
1.8k
7
Share
Embed
Copy iframe code
Copy JS code
Copy link
Start on current slide
形式手法の 10 メートル手前 #kernelvm / Kernel VM Study Hokuriku Part 7
Kernel / VM 探検隊 @ 北陸 Part 7 で使用したスライドです。
y_taka_23
November 09, 2024
Transcript
71 slides
形式手法の 10 メートル手前 チェシャ猫 (@y_taka_23) Kernel / VM 探検隊 @
北陸 Part 7 9th Nov. 2024
前回(8 月)の Kernel / VM 探検隊
r1ru さん (@ri5255) Rust で自作モデル検査器 https://speakerdeck.com/riru/symbolic-model-checker-from-scratch-in-rust
かなり 本格的な 解説
偶然居合わせたチェシャ猫 「参考文献の著者です」 https://speakerdeck.com/riru/symbolic-model-checker-from-scratch-in-rust?slide=46
参考文献の その「先」へ
しかし得てして 難しめ
「先」だけでなく 「手前」についても
勢いと割り切りで
手前側 10 メートルを キーワード 10 個で 雰囲気解説
仕様を自動的に検証 https://speakerdeck.com/riru/symbolic-model-checker-from-scratch-in-rust?slide=3
【残り 10 m】 単体テスト
0 を入れると 42 が返る getAnswerOfEverything(0) == 42
人間は 「入力と出力の対応」 を記述
バグをピンポイントに 引き当てる必要性
【残り 9 m】 プロパティベーステスト
テストケースは ランダム生成
人間は 「関数の性質」 を記述
エンコードしてから デコードすると元に戻る decode(encode(x)) == x
最適化の前後で 結果が変わらない naiveImpl(x) == optimizedImpl(x)
これで確実に テスト可能?
近頃はそうでもない
【残り 8 m】 非決定性
マルチスレッドの タイミング系バグ
分散システムの サーバ故障
ネットワーク 通信の遅延
コントロール不能
再現性のあるテスト が書けない
ならば何を テストする?
【残り 7 m】 グラフ構造
二つのスレッド A と B A: 0, B: 0
A が 1 step 動いた世界線 A: 0, B: 0 A:
1, B: 0
B が 1 step 動いた世界線 A: 0, B: 0 A:
0, B: 1
全パターン網羅すると グラフ構造が現れる A: 0, B: 0 A: 1, B: 0
A: 0, B: 1 A: 2, B: 0 A: 1, B: 1 A: 0, B: 2 A: 3, B: 0 A: 2, B: 1 A: 1, B: 2 A: 0, B: 3
【残り 6 m】 時相論理
グラフを見ると 「時間経過」 が表現できる
どう辿っても 「ずっと」成立
どう辿っても 「いずれ必ず」成立
【残り 5 m】 安全性と活性
悪いことが 「ずっと起こらない」 安全性
良いことが 「いずれ起こる」 活性
両方合わせて仕様
なぜ両方?
何もしないシステムは 安全だが無意味
グラフに対する テストフレームワーク が欲しい
【残り 4 m】 モデル検査
仕様を グラフの性質 として表現
グラフアルゴリズムで 自動的に検査可能
アルゴリズムの詳細は r1ru さんのスライド参照 https://speakerdeck.com/riru/symbolic-model-checker-from-scratch-in-rust
【残り 3 m】 形式手法
数学チックな 検査手法の総称(雑)
モデル検査以外にも 定理証明など
そうそう
「型」も形式手法です
【残り 2 m】 モデル検査ツール
TLA+ https://lamport.azurewebsites.net/tla/tla.html
Alloy https://alloytools.org/
SPIN https://spinroot.com/spin/whatispin.html
【残り 1 m】 採用事例
TLA+ 大人気
AWS で使ってる https://www.amazon.science/publications/how-amazon-web-services-uses-formal-methods
MS Azure でも使ってる https://github.com/Azure/azure-cosmos-tla
難しそう?
たかが 10 メートル
冬休みの自由研究に
自分へのクリスマス プレゼントに
お歳暮に
モデル検査
形式手法
おすすめです
【残り 0 m】 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
メール到達性を支える、リンク先URLのドメイン評価の扱い方
wind111
0
190
OWASP AI Agentic Top10に準拠するクラウドネイティブなガードレールの実践(CNDW 2026)
keitah
1
420
実測データからサービスの成長余力を測る。負荷シナリオ・テストデータ・限界値の設計
kazatohiei
0
130
市販IoT機器や自作IoT機器とHomeAssistantを駆使して家の電気代をできる限り見える化する方法の考案
harutiro
0
410
常時稼働エージェントの作り方(Claude公式ブログを資料化)
minorun365
PRO
18
29k
HTTP QUERY時代の型安全な検索APIをKotlinで設計する
sansantech
PRO
1
120
落とし穴にハマってわかった 開発生産性を測るときに気をつけたいこと
munakata
3
480
変更差分を読むために環境を整備しよう
pipepasta
1
610
AWS Client VPNの設定でハマったポイントとその過程での気づき
amarelo_n24
1
430
現地速報! Microsoft Ignite アップデートレポート
kasada
1
410
Terraform 0 to 100:100個以上のリポジトリを常に最新にし続けるための自動化
sue445
3
1.3k
文書画像からの情報抽出を行うエージェントを、軌跡の正解データ無しで作れるか
sansantech
PRO
2
220
Featured
See All Featured
Intergalactic Javascript Robots from Outer Space
tanoku
273
28k
A Guide to Academic Writing Using Generative AI - A Workshop
ks91
PRO
1
570
Connecting the Dots Between Site Speed, User Experience & Your Business [WebExpo 2025]
tammyeverts
11
1.1k
The Myth of the Modular Monolith - Day 2 Keynote - Rails World 2024
eileencodes
28
3.8k
The AI Revolution Will Not Be Monopolized: How open-source beats economies of scale, even for LLMs
inesmontani
PRO
3
3.8k
We Analyzed 250 Million AI Search Results: Here's What I Found
joshbly
2
2.1k
Groundhog Day: Seeking Process in Gaming for Health
codingconduct
0
490
ピンチをチャンスに:未来をつくるプロダクトロードマップ #pmconf2020
aki_iinuma
128
56k
Responsive Adventures: Dirty Tricks From The Dark Corners of Front-End
smashingmag
254
23k
XXLCSS - How to scale CSS and keep your sanity
sugarenia
250
1.3M
How People are Using Generative and Agentic AI to Supercharge Their Products, Projects, Services and Value Streams Today
helenjbeal
2
400
Learning to Love Humans: Emotional Interface Design
aarron
275
41k