F*: 一般目的の証明指向プログラミング言語
F*: A general-purpose proof-oriented programming language (fstar-lang.org)
要約
F*は、純粋関数型プログラミングと効果的プログラミングの両方をサポートする、一般目的の証明指向プログラミング言語です。依存型とSMTソルバーや戦術ベースの対話型定理証明に基づいた証明自動化を組み合わせ、OCaml、F#、C、Wasm、アセンブリなどへの抽出が可能です。Microsoft Research、Inria、コミュニティによって活発に開発されており、HACL*、ValeCrypt、EverCrypt、EverParseといった高信頼性ソフトウェア開発プロジェクトで利用されています。
全文翻訳
Introduction
F*(エフスターと発音)は、純粋関数型プログラミングと効果型プログラミングの両方をサポートする、汎用の証明指向プログラミング言語です。依存型の表現力と、SMTソルバーに基づく証明自動化、および戦術ベースの対話型定理証明を組み合わせています。
Fプログラムは、デフォルトでOCamlにコンパイルされます。また、KaRaMeLというツールによって、Fの様々な断片をF#、C、またはWasmに抽出したり、Valeツールチェーンを使用してアセンブリに抽出したりすることも可能です。FはF自身で実装されており、OCamlを使用してブートストラップされています。
F*はGitHubでオープンソースとして公開されており、Microsoft Research、Inria、およびコミュニティによって活発に開発が進められています。
Download
FはApache 2.0ライセンスの下で配布されています。Windows、Linux、Mac OS X用のバイナリは、GitHubのリリースページに定期的に投稿されています。OPAM、Docker、NixからFをインストールしたり、INSTALL.mdの指示に従ってソースからビルドしたりすることも可能です。
Learn F*
オンライン書籍「Proof-oriented Programming In F*」が執筆されており、定期的にオンラインで更新情報が投稿されています。以下の画像をクリックして、ブラウザで例や演習を試しながら読むことをお勧めします。
Low*
また、KaRaMeLによってCにコンパイル可能なF*の低レベルサブセットであるLow*のチュートリアルも提供しています。
Course Material
F*のコースは、様々な季節学校でしばしば開催されています。それらの講義や教材も有用なリソースです。
- Embedding Proof-oriented Programming Languages in F*
- Formal Verification with F* and Meta-F*
- ECI 2019での講義とチュートリアル:講義ノート、スライド、コード
- Verifying Low-Level Code for Correctness and Security
- Program Verification with F*
- 2018 EUTypes Summer Schoolでのコース、2018年8月8~12日、オフリド、マケドニア コース教材
Community
F*に関する質問やアナウンスについては、GitHub Discussionsをご利用ください。
以前はSlackインスタンスを使用していましたが、オンラインコミュニティをこの公開Zulip上のフォーラムに統合することを目指しています。
トラフィックは非常に少ないですが、メーリングリストもあります。fstar-mailing-listで購読できます。
ユーザーと開発者の会議であるF* PoP Up Seminarは、どなたでも参加できます。月に一度の開催を目指していますが、スケジュールは不規則です。ぜひご参加ください。
F*のメンテナーには、fstar-maintainers@googlegroups.comまでご連絡ください。
Uses
Fは、産業界および学術界のいくつかのプロジェクトで使用されています。ここではその一部を紹介します。ご自身のプロジェクトでFを使用している場合は、fstar-mailing-listにご連絡ください。
Project Everest
Project Everestは、Fで高保証のセキュア通信ソフトウェアを開発する包括的なプロジェクトでした。Fの開発の大部分は、Project Everestが対象としたシナリオによって動機付けられました。論文「Project Everest: Perspectives from Developing Industrial-Grade High-Assurance Software」(TOPLAS 2026)は、TLS、暗号化、パーサーを含む検証済みセキュア通信ソフトウェアの開発と展開に関する約10年間の経験を振り返り、F*および関連する検証ツールを産業界で利用する上での教訓を共有しています。Project Everestからのいくつかの派生プロジェクトは、以下に示すものも含め、独自のプロジェクトとして継続しています。
HACL*, ValeCrypt, and EverCrypt
HACL*は、Fで記述されCに抽出された高保証暗号プリミティブのライブラリです。ValeCryptは、Fに埋め込まれた検証済みアセンブリ言語プログラミングのフレームワークであるValeで、暗号プリミティブの形式的に証明された実装を提供します。EverCryptは、これらを単一の暗号プロバイダーに統合したものです。これらのプロジェクトのコードは現在、Mozilla Firefox、Linuxカーネル、Python、mbedTLS、Tezosブロックチェーン、ElectionGuard電子投票SDK、Wireguard VPNなど、いくつかのプロジェクトで本番使用されています。
EverParse
EverParseは、形式的に証明されたF*から生成されたCコードを出力するバイナリフォーマット用のパーサー生成器です。EverParseからのパーサーは、Windows Hyper-Vなど、Azureクラウドプラットフォームを通過するすべてのネットワークパケットがEverParseによって生成されたコードで最初に解析および検証されるいくつかのプロジェクトで本番使用されています。EverParseは、ebpf-for-windowsなど、他の本番環境でも使用されています。
Research
F*は、プログラミング言語と形式手法のコミュニティ、およびセキュリティとシステムのコミュニティにおける応用という両方の観点から、活発な研究トピックです。以下にその一部を挙げます。これらの論文の完全な引用は、この参考文献リストで入手できます。このリストに論文を含めたい場合は、fstar-maintainers@googlegroups.comまでご連絡ください。
The Design of F* and its DSLs
- Dependent Types and Multi-monadic Effects in F* (POPL 2016) これはF*システムを説明する標準的な参考文献です。言語は2016年以降大きく進化しましたが、そのコアデザインと実装はこの論文に基づいています。
- Verified Low-level Programming Embedded in F* (ICFP 2017) は、Fの低レベルサブセットであり、KaRaMeLによってCにコンパイル可能なFの低レベルフラグメントであるLow*について説明しています。
- A Verified, Efficient Embedding of a Verifiable Assembly Language (POPL 2019) は、F*に埋め込まれた検証済みアセンブリ言語であるVale言語について説明しています。
- Meta-F*: Proof Automation with SMT, Tactics, and Metaprograms (ESOP 2019) は、F内のメタプログラミングシステムであるMetaFについて説明しており、その戦術エンジンから型クラスのサポートまで、F*の様々な側面を実装するために使用されています。
- Programming and Proving with Indexed Effects (TR 2021) は、Fのユーザー定義効果サポートのデザインを説明し、Fの論理コアを記述する計算式を提供します。
- Steel: Proof-oriented Programming in a Dependently Typed Concurrent Separation Logic (ICFP 2021) は、Steel言語とその並行分離論理を用いた命令型プログラムの証明への利用について説明しています。
Semantics and Effects
- Verifying Higher-order Programs with the Dijkstra Monad (PLDI 2013) は、F*の効果システムの中核機能であるDijkstraモナッドの概念を導入しています。
- Dijkstra Monads for Free (POPL 2017) は、継続渡し変換を使用して、計算モナッドのクラスに対するDijkstraモナッドを自動的に導出する方法を示しています。
- A Monadic Framework for Relational Verification: Applied to Information Security, Program Equivalence, and Optimizations (CPP 2018) は、Dijkstra Monads for Freeの研究に基づいて、複数のプログラムまたはプログラム実行を関連付けるプロパティを証明するためのフレームワークを構築しています。
- Dijkstra Monads for All (ICFP 2019) は、Dijkstraモナッドの概念を一般化し、モナッドの射を用いて計算モナッドと仕様モナッドを体系的に関連付ける方法を示しています。
- Recalling a Witness: Foundations and Applications of Monotonic State (POPL 2018) は、状態が単調に進化するプログラム(例:追記専用ログ)を推論するためのプログラム論理のデザインを説明しています。この論理は、Low*とSteelの両方の基盤となっています。
- SteelCore: An Extensible Concurrent Separation Logic for Effectful Dependently Typed Programs (ICFP 2020) は、Steel DSLの基盤となるSteelCore並行分離論理について説明しています。
- USSL: A Universe-Stratified, Predicative Concurrent Separation Logic は、F*に浅く埋め込まれた、宇宙レベルの階層に従って述語を層別化し、動的述語と高階ゴースト状態を予測的な設定でサポートする、基礎的で公理フリーな並行分離論理です。
- PulseCore: An Impredicative Concurrent Separation Logic for Dependently Typed Programs (PLDI 2025) は、Fに浅く埋め込まれた、基礎的で公理フリーな並行分離論理であり、動的述語と高階ゴースト状態をサポートし、予測不可能な述語と後続クレジットを備えています。PulseCoreは、並行分離論理における証明指向プログラミングのためのFに埋め込まれた言語であるPulseの基盤です。
Applications in Security and Cryptography
セキュリティと暗号化におけるF*の応用に関する多くの論文は、Project Everestの参考文献で見つけることができます。ここでは、特に注目すべきものや、Project Everestに関連しない他の応用例をいくつか紹介します。
- WYS*: A DSL for Verified Secure Multi-party Computations (POST 2017) は、検証済みの混合モードセキュアマルチパーティ計算を記述するためのドメイン固有言語であるWYS*について説明しています。
- Implementing and Proving the TLS 1.3 Record Layer (S&P 2017) は、Low*におけるTLS-1.3レコードレイヤーの検証済み実装について説明しています。
- HACL*: A Verified Modern Cryptographic Library (CCS 2017) は、Lowで実装された検証済み暗号ライブラリHACLについて説明しています。
- Formally Verified Cryptographic Web Applications in WebAssembly (S&P 2019) は、KaRaMeLによってWasmにコンパイルされた、HACLを使用したFによるSignalプロトコルの実装であるLibSignal*を開発しています。
- EverCrypt: A Fast, Verified, Cross-Platform Cryptographic Provider (S&P 2020) は、HACL*とValeからのCおよびアセンブリコードを組み合わせた暗号プロバイダーであり、Microsoft Azure CCFの初期バージョンで使用された検証済み高性能メルクルツリーを含む、その上に構築されたいくつかのアプリケーションが含まれています。
- HACL×N: Verified Generic SIMD Crypto (for all your favorite platforms) (CCS 2020) は、暗号プリミティブのベクトル化されたバージョンをメタプログラミングし、「一度書けば、無料でベクトル化されたバージョンが得られる」というスタイルを可能にします。
- A Security Model and Fully Verified Implementation for the IETF QUIC Record Layer (S&P 2021) は、Dafnyで実装されたプロトコルロジックと組み合わせたLow*でのQUICレコードレイヤーの検証済み実装です。
- DICE*: A Formally Verified Implementation of DICE Measured Boot (USENIX Security 2021) は、EverCryptとEverParseを使用し、Low*で実装されたマイクロコントローラー向けのDICE測定ブートプロトコルの正当性とセキュリティを証明しています。
- DY*: A Modular Symbolic Verification Framework for Executable Cryptographic Protocol Code (Euro S&P 2021) は、F*で開発された暗号プロトコル実装の実行可能なシンボリックセキュリティ分析のための型ベースのフレームワークです。
- A Tutorial-Style Introduction to DY* (LNCS 2021) は、DY*のチュートリアル形式の入門です。
- An In-Depth Symbolic Security Analysis of the ACME Standard (CCS 2021) は、DY*を使用してACME証明書発行および管理プロトコルのモデルのセキュリティを証明しています。
- Noise*: A Library of Verified High-Performance Secure Channel Protocol Implementations (S&P 2022) は、セキュアチャネルプロトコルのファミリーに対する証明可能なセキュアな実装をメタプログラミングします。
- TreeSync: Authenticated Group Management for Messaging Layer Security (USENIX Security 2023) は、DY*フレームワークを使用して証明されたMLSの参照実装です。
- Modularity, Code Specialization, and Zero-Cost Abstractions for Program Verification (ICFP 2023) は、HACL*で使用される証明工学技術について説明しており、Cでの多くの具体的な実装に繰り返し特化できる暗号化構成の汎用実装を可能にします。ここで使用された技術は、Pythonプログラミング言語のライブラリへの検証済み暗号コードの採用につながりました。
- Verifying Indistinguishability of Privacy-Preserving Protocols (OOPSLA 2023) は、ネットワークプロトコルの通信トレースに対する不可識別性の証明を可能にするWaldoというF*のライブラリを提供します。
- Comparse: Provably Secure Formats for Cryptographic Protocols (CCS 2023) は、シンボリックプロトコルアナライザーとの使用に適したデータフォーマット用の解析ライブラリを提供します。Comparseはフォーマットのビットレベルで正確なアカウンティングを提供し、DY*プロトコル分析フレームワークが具体的なメッセージを推論し、以前は見落としていたプロトコルの欠陥を特定できるようにします。
- Formal Security and Functional Verification of Cryptographic Protocol Implementations in Rust (CCS 2025) は、ポスト量子機能を持つTLS-1.3のRust実装であるBert13を開発し、Haxを使用してFを含むさまざまなプロバーバックエンドへの翻訳を通じてその正当性とセキュリティを証明します。FはRustコードのパニックフリーを証明し、トランスクリプトフォーマットが単射であることを証明するために使用されます。
- DY* Unchained: Now with Composable Security Proofs and Precise Compromise Scenarios (S&P 2026) は、セキュリティ証明の合成のためのモジュラートレース不変量と、より正確な侵害シナリオの表現のための汎用セキュリティラベルを備えた、FベースのDYプロトコル検証フレームワークを拡張します。
Applications in Systems
- Provably-Safe Multilingual Software Sandboxing using WebAssembly (USENIX 2022) は、Low*とRustにおけるWebAssemblyモジュールのサンドボックスの検証済み実装について説明しています。
- FastVer: Making Data Integrity a Commodity (SIGMOD 2021) は、F*でデータ整合性監視プロトコルを形式化しています。
- FastVer2: A Provably Correct Monitor for Concurrent, Key-Value Stores (CPP 2022) は、SteelにおけるFastVerプロトコルの低レベル並行実装の正当性を証明しています。
- Pipit on the Post: Proving Pre- and Post-Conditions of Reactive Systems (ECOOP 2024) は、F*にリアクティブ言語を埋め込み、リアルタイムで実行される一部の制御システムを検証するために使用しています。
- StarMalloc: Verifying a Modern, Hardened Memory Allocator (SPLASH 2024) は、実際のプロジェクトでドロップイン交換として使用できる、セキュリティ指向の並行メモリアロケーターであり、Steelで検証されています。
- Kuiper: Correct and Efficient GPU Programming with Dependent Types and Separation Logic (PLDI 2026) は、CPU/GPUプログラミングをF*に埋め込み、Pulseを拡張して、カーネル起動および同期全体でのメモリ安全性、データ競合の自由、および機能的正確性を証明します。テンソルコアを使用したタイルド行列乗算を含む検証済みカーネルは、手書き実装と同等のパフォーマンスを持つ特殊化されたCUDAコードにコンパイルされます。
Applications in Parsing
- EverParse: Verified Secure Zero-Copy Parsers for Authenticated Message Formats (USENIX Security 2019) は、Cコードを生成するバイナリフォーマット解析用のパーサー生成器EverParseについて説明しています。
- Hardening Attack Surfaces with Formally Proven Binary Format Parsers (PLDI 2022) は、EverParseを使用してWindowsネットワーク仮想化およびHyper-Vにおけるネットワークパケットパーサーを強化しています。
- ASN1*: Provably Correct Non-Malleable Parsing for ASN.1 DER (CPP 2022) は、F*でASN.1 DERフォーマットを形式化し、EverParseでのそのパーサーの正当性を証明しています。
- Secure Parsing and Serializing with Separation Logic Applied to CBOR, CDDL, and COSE (CCS 2025) は、CBORバイナリオブジェクトフォーマットおよびCDDLデータ記述言語のRFCをF*で形式化し、CBOR用の証明可能な正当かつ安全なパーサーとフォーマッター、およびCDDL仕様用のコンパイラを開発し、すべてPulseで実装され、COSE署名オブジェクトの検証を含むさまざまなアプリケーションに適用されています。
Applications in Programming, Program Proof, and Program Analysis
- Verified Compilation of Space-Efficient Reversible Circuits (CAV 2018) は、F*で正当性が証明されたリバーシブル回路のコンパイラReVerCを提示しています。
- Verified Transformations and Hoare Logic: Beautiful Proofs for Ugly Assembly Language (VSTTE 2020) は、Valeフレームワークにおけるアセンブリプログラムの検証済み変換を開発しています。
- Statically verified refinements for multiparty protocols (OOPSLA 2020) は、Fで形式化されたマルチパーティプロトコル用のセッション型プログラミング言語であるSessionを提示しています。
- Verified Functional Programming of an Abstract Interpreter (SAS 2021) は、F*で開発された非常にコンパクトな健全性証明を持つ命令型言語の抽象解釈フレームワークを開発しています。
- Catala: a programming language for the law (ICFP 2021) では、コンパイラの中核部分が形式化され、F*で正当性が証明されています。
- Verification of a Merkle Patricia Tree Library Using F* は、OCamlからF*にメルクルツリーライブラリを移植し、バグを発見して修正し、最終的にその正当性を証明しています。
- Certified mergeable replicated data types (PLDI 2022) は、分散プログラミングで使用されるレプリケートデータ型を構築するためのフレームワークであるPEEPULを提示しており、F*で形式化されています。
- Aeneas: Rust verification by functional translation (ICFP 2022) は、Rustを純粋なF*に翻訳し、関数的正確性証明を可能にします。
- Q*: Implementing Quantum Separation Logic in F* (PlanQC 2022) は、SteelCore分離論理を量子プログラミング言語で使用できるように適応させています。
- Pipit: Reactive Systems in F* (Extended Abstract) (TyDe 2023) は、リアクティブシステムの検証のための埋め込みDSLについて説明しています。
- Securing Verified IO Programs Against Unverified Code in F* (POPL 2024) は、入出力(IO)を実行する静的に検証されたプログラムのための形式的に安全なコンパイルフレームワークであるSCIO*を提示しています。
- SecRef*: Securely Sharing Mutable References between Verified and Unverified Code in F* (ICFP 2025) は、静的に検証されたステートフルプログラムのための形式的に安全なコンパイルフレームワークであるSecRef*を提示しています。また、単調状態のためのDijkstraモナッドも提示しています。
- Automatically Verifying Replication-Aware Linearizability (OOPSLA 2025) は、マージ可能なレプリケートデータ型に対するレプリケーションを認識した線形化可能性を検証するための新しい完全に自動化された技術を開発しており、F*での証明とOCamlに抽出された検証済みコードが含まれています。
- A Mechanically Verified Garbage Collector for OCaml (JAR 2025) は、FとLowで検証された、OCaml用のストップ・ザ・ワールド・マーク・アンド・スイープGCを開発しています。
- Misquoted No More: Securely Extracting F* Programs with IO (ICFP 2026) は、IOとリファインメント型を持つ浅く埋め込まれたFプログラムを安全に抽出するためのフレームワークであるSEIOを提示しています。これは、生成された型付け導出を検証するリレーショナル引用と、検証済みコード生成を組み合わせ、抽出されたプログラムが敵対的なコードとリンクされてもセキュリティプロパティを維持することを証明します。
AI-assisted Programming
- Towards Neural Synthesis for SMT-Assisted Proof-Oriented Programming (ICSE 2025) は、940KLOCのF*コードと証明のデータセットをキュレーションし、プログラムと証明の合成を自動化するためのAIモデルを開発しています。
- 3DGen: AI-Assisted Generation of Provably Correct Binary Format Parsers は、混合された非公式な入力(RFCなどの自然言語ドキュメントや例入力)をEverParseで使用されるデータフォーマット仕様言語である3Dに変換するためのAIエージェントを開発しています。
- Proofs Promptly: Proof-Oriented Programming with AI Agents (Experience Report) (ICFP 2026) は、AIエージェントが機械チェック済みのF*およびPulseコード(検証済みデータ構造、推論された仕様、移植された証明を含む)を開発した経験について報告しています。人間がエージェントをガイドし、仕様をレビューする効果的なワークフローを説明しており、手動の証明工学の労力を大幅に削減します。
- The ART of Agentic Proof-Oriented Programming: Audits, Rubrics, and Templates (プレプリント, 2026) は、エージェントによって生成されたコード、仕様、および証明のレビューを容易にするための方法論を提案しています:証明指向監査は意図を評価し、ルーブリックは仕様チェックを自動化し、テンプレートはエージェントを再利用可能な証明パターンに導きます。F*とPulseでのケーススタディには、教科書的なアルゴリズムとデータ構造、およびTLS-1.3を使用したステートフルなインタラクティブシステムが含まれます。
Miscellaneous
- A Theorem Proving Approach to Programming Language Semantics (ICSE-SEET 2023) は、F*を使用してオペレーショナル、デノテーショナル、および公理的セマンティクスを学生に教えた経験について報告しています。
Papers about an older version of F*
Fというシステムを最初に紹介した論文は2011年です。現在のFバージョンは2015年に再設計・実装されましたが、完全性のためにこれらの古い論文もここに含めます。
- Secure Distributed Programming with Value-dependent Types (ICFP 2011) は、JFPにも掲載された長いバージョンがあります。
- Self-certification: bootstrapping certified typecheckers in F* with Coq (POPL 2012) は、F型チェッカーの正当性をF自身でプログラムし、Coqを使用して約7GBの証明を約24マシン日でチェックすることでブートストラップするプロセスを証明しています。
- Fully abstract compilation to JavaScript (POPL 2013) は、F*でJavaScriptの部分集合をモデル化し、MLライクな言語からJavaScriptへのセキュアなコンパイラを開発しています。
- Gradual typing embedded securely in JavaScript (POPL 2014) は、敵対的なコンテキストにおける段階的型の健全性を保証するための防御的チェックを備えたJavaScriptのソース・トゥ・ソース・コンパイラを開発しており、F*で正当性が証明されています。
- Probabilistic relational verification for cryptographic implementations (POPL 2014) は、非干渉やゲームベースの暗号証明などのセキュリティプロパティを証明するのに役立つ、言語のリレーショナル方言であるRF*を開発しています。