formal verification

Bilingual

F*: A general-purpose proof-oriented programming language
2 months ago
- F* is a proof-oriented programming language combining dependent types with SMT solving and tactic-based interactive theorem proving.
- It compiles by default to OCaml and can be extracted to F#, C, Wasm, or assembly using various tools.
- F* is open source under Apache 2.0, available on GitHub, and installable via multiple methods including binaries, OPAM, Docker, Nix, or from source.
- Learning resources include an online book, a Low* tutorial, and course materials from seasonal schools.
- F* is used in industrial and academic projects such as Project Everest, HACL*, ValeCrypt, EverCrypt, and EverParse, with production deployments in Firefox, Linux kernel, Python, Azure, and more.
- Extensive research on F* covers semantics, effects, security, cryptography, systems, parsing, and program verification, with many published papers.
Software Foundations Series
2 months ago
- The Software Foundations series provides a broad introduction to the mathematical foundations of reliable software.
- Every detail in the series is fully formalized and machine-checked using the Rocq proof assistant.
- The series targets a wide audience from advanced undergraduates to researchers, assuming no prior logic or programming languages background.
- Volume 1 (Logical Foundations) covers functional programming, logic basics, and Coq theorem proving.
- Volume 2 (Programming Language Foundations) covers operational semantics, Hoare logic, and static type systems.
- Volume 3 (Verified Functional Algorithms) focuses on specifying and mechanically verifying fundamental data structures.
- Volume 4 (QuickChick) introduces property-based testing combined with formal specification in Coq.
- Volume 5 (Verifiable C) provides hands-on tutorials for verifying real-world C programs using the Princeton Verified Software Toolchain.
Three ways formally verified code can go wrong in practice
2 months ago
- Formally verified code can still have bugs if the proof itself is invalid, such as due to a bug in the theorem prover or using unproven assumptions (shortcuts).
- Bugs arise when the properties (specifications) being proven are wrong or weaker than needed, like the leftpad example proving string length instead of visual alignment for Unicode.
- Assumptions, such as environmental conditions or unverified dependencies, can break correctness even if the proof is valid, as seen in binary search overflow issues or reliance on external services.
Illegal vs Unwanted States
2 months ago
- Illegal states are never acceptable, while unwanted states are undesirable but can temporarily exist.
- Unwanted states, like scheduling conflicts or overbooked flights, may not lead to illegal states but still require resolution.
- Systems must represent unwanted states due to external inputs or intentional design, such as airlines allowing overbooking.
- Unwanted states can be necessary for workflows, like double-booking, and users should be alerted to manage them.
- Formally, illegal states violate invariants (always false), while unwanted states involve safety and liveness properties, like network partitions that must eventually heal.
Introduction to Formal Verification with Lean Part 1
2 months ago
- Formal verification uses tools like Lean to write machine-checked proofs, ensuring mathematical correctness.
- This tutorial covers basic Lean concepts and verifies the One-Time Pad (OTP) protocol, a Shannon cipher.
- Learners define bitstrings as vectors over GF(2), prove XOR properties (commutativity, associativity, identity, self-inverse), and implement a Shannon cipher structure.
- The goal is to translate cryptographic definitions from Boneh & Shoup's textbook into Lean, culminating in proving OTP is a Shannon cipher.
- Lean is a functional programming language and theorem prover that automates proof tasks and supports collaboration.
Formal verification might solve AI's review bottleneck
2 months ago
- A new software engineering paradigm combines formal verification and AI: humans specify requirements in a formal language like Lean, and AI writes code along with a machine-checkable proof of correctness, eliminating human review of generated code.
- AI alone faces a review bottleneck because it can write code at near-zero cost, but reviewing all that code becomes a new bottleneck; formal verification removes this by proving correctness automatically, with increased assurance as a side effect.
- The framework involves humans defining hard constraints (formal specification) and optimization objectives (benchmarks), while AI agents write code and proofs; human effort is minimal as constraints are proven and objectives measured automatically.
- Analogies to machine learning include risks like overfitting and specification gaming, where agents may exploit weaknesses in specs; tools like regularization and careful metric design are needed to manage these risks.
- A Hello World example (k-th smallest element) demonstrates the approach: Lean definitions capture correctness, agents fill in implementation and proof, and benchmarks optimize runtime; the agent improved from sorting to quickselect.
- A case study at powdr (autoprecompiles for zkVMs) shows success: 500 lines of Lean spec, benchmarks for optimization, and 100% AI-generated code and proofs without human review; circuit-size reduction matches previous implementation, and runtime improved significantly.
- The approach may generalize if writing specs is cheaper than maintaining code, and reusable spec libraries could help; integration via FFI allows incremental adoption, potentially shifting focus from code to requirements in software engineering.
ESBMC-Arduino: Closing the Deployment Gap for Formal Verification
2 months ago
- The paper introduces ESBMC-Arduino to close the deployment gap in formal verification for open-hardware PLCs running on microcontrollers like Arduino.
- It highlights that naive width-aware verification without hardware input models leads to false alarms, as demonstrated by 44% false alarms in 123 real programs.
- A hardware-faithful verification approach is proposed using a declarative HAL descriptor and sound lowering to interpret arithmetic at target width and constrain inputs to hardware-realizable ranges.
- The method, instantiated as ArduinoTool, eliminates all false alarms while preserving robustness proofs and detects rare width-dependent defects with realizable witnesses.
Lean Software Scaling Laws
3 months ago
- Proposal to measure how coding LLM perplexity scales with codebase context size, using Lean as a test case for formal languages.
- Aim to estimate scaling laws of 'predictability' by programming language, translating to security and safety improvements in software.
- Lean may have worse baseline performance but better scaling exponents, suggesting long-term benefits for program correctness and cybersecurity.
- Methodology involves empirical measurement via frozen LLMs, corpus construction, loss measurement, and scaling law fitting per language.
- Prediction: 'Weak' languages like Python excel at small scales but have worse scaling exponents, while 'strong' languages like Lean cross over at larger scales.
- Bias controls needed for programmer and domain differences; context learning and failure modes like ecosystem maturity effects are considered.
Leanstral 1.5: Proof Abundance for All
3 months ago
- Leanstral 1.5 is a free Apache-2.0 licensed model with 6B active parameters, offering a significant performance upgrade in formal verification.
- It achieves state-of-the-art results on benchmarks: 100% on miniF2F, 587/672 on PutnamBench, 87% on FATE-H, and 34% on FATE-X.
- The model undergoes a three-stage training process: mid-training, supervised fine-tuning, and reinforcement learning with CISPO, using multiturn and code agent environments.
- It demonstrates strong test-time scaling on PutnamBench, solving more problems as token budget increases, from 44 at 50k tokens to 587 at 4M tokens.
- Leanstral 1.5 excels in code verification, proving time complexity for AVL trees and uncovering 5 previously unknown bugs across 57 repositories tested.
- The model is fully open-sourced and available via Hugging Face and a free API, with recommendations for setup using Mistral Vibe and Lean LSP MCP.
Show HN: Salt – a systems language with Z3 theorem proving in the compiler
3 months ago
- Salt provides verified safety at compile time without runtime overhead using Z3-proven contracts.
- It uses arena allocation instead of garbage collection or a borrow checker, ensuring memory safety and preventing leaks.
- Salt achieves performance parity with clang -O3 across various benchmarks, including ML inference, kernels, networking, and rendering.
- The language features pipe operators for chaining, optional chaining for errors, and f-strings for type-safe formatting without allocation.
- Salt's package manager, sp, offers dependency verification, content-addressed caching, and monorepo support for fast, reliable builds.

formal verification

F*: A general-purpose proof-oriented programming language

Software Foundations Series

Three ways formally verified code can go wrong in practice

Illegal vs Unwanted States

Introduction to Formal Verification with Lean Part 1

Formal verification might solve AI's review bottleneck

ESBMC-Arduino: Closing the Deployment Gap for Formal Verification

Lean Software Scaling Laws

Leanstral 1.5: Proof Abundance for All

Show HN: Salt – a systems language with Z3 theorem proving in the compiler