Safety Property

A property of a program or distributed system asserting that “nothing bad ever happens” (Lamport 1977). Formally, a safety property is one whose violation can be witnessed by a finite execution prefix: once the bad state is entered, no future behaviour can undo it.

Examples: mutual exclusion, partial correctness, absence of null-pointer dereference, “contract balance never drops below escrowed amount.” Dual: Liveness Property (“something good eventually happens”), whose violation requires an infinite trace.

Safety is semantically rich: on arbitrary programs, non-trivial safety properties are undecidable (Rice’s Theorem). This is why House on Rock - LangSec in Ethereum Classic argues that gas metering (a resource bound, decidable) cannot substitute for a safety guarantee (semantic, undecidable).

Tags

#verification #distributed-systems #safety-liveness

Summary

A LangSec critique of Ethereum aimed at the Ethereum Classic community, framed around the parable of the wise and foolish builders and Philip K. Dick’s “reality is that which, when you stop believing in it, doesn’t go away.” Patterson argues Ethereum was built on sand — an ad-hoc, non-executable yellow-paper semantics; a hand-rolled Solidity parser; a test suite with no coverage for delegatecall or invalid opcodes; a design culture that scorned formal methods until hundred-million-dollar losses forced the issue.

The central technical argument is that the gas mechanism does not do what the yellow paper claims it does. Gavin Wood’s stated purpose — “sidestep the inevitable issues stemming from Turing completeness” — confuses a resource bound (a non-semantic, decidable property) with a safety guarantee (a semantic property that Rice’s theorem makes undecidable in general). Gas cannot show a contract “does nothing malicious”; it can only show it eventually halts. Worse, gas creates an adversarial economic game with direct monetary reward for tricking the accounting, and a perverse incentive for honest developers to omit runtime sanity checks because conditionals cost gas.

Patterson’s prescription for Ethereum Classic: standardise on KEVM (an executable operational semantics in the K framework), fix the VM test suite’s gaps, build languages that don’t hide implicit behaviour (method visibility defaults, fallback methods, delegatecall as naked eval), and invest in developer tools — IDEs, live debuggers, verification — that surface what a contract can actually do. “Code is law” requires the meaning of the code to be unambiguous, executable, and visible.

Key Ideas

Rice’s theorem bounds what gas can mean. Non-trivial semantic properties of arbitrary programs are undecidable; resource bounds are non-semantic. Gas therefore cannot sidestep Turing-completeness-induced safety problems, contrary to the yellow paper.

Gas as adversarial game. The accounting is an attack surface, not a safety property; attackers are paid to win. Honest contract authors are weakly pushed toward removing checks to keep gas costs competitive.

LangSec programmer–machine contract. Inputs must have a formal grammar; two implementations of the same spec must accept/reject identical inputs; semantics must be executable so claims about behaviour can be verified mechanically.

Ad-hoc semantics breeds consensus failures. When the yellow paper and cpp-ethereum disagree, cpp-ethereum wins — the denotational semantics is decorative. Discrepancies between clients have already caused real Ethereum consensus failures.

Test suites are part of software design. Official VM tests have no coverage for invalid opcodes or delegatecall — the exact instruction at the heart of the Parity multisig hacks. “VM tests” is false advertising; downstream VM implementations inherit the blind spot.

Case studies of processing-fluency failure.

DAO: mutual recursion across a defender/attacker code boundary, missed in reviews because reviewers examine functions one at a time (cf. Leveson: accidents emerge from interactions).
Hacker Gold: =+ typed instead of += — a hand-rolled recursive-descent parser caught nothing; a Bison grammar would have surfaced a shift/reduce conflict.
Parity multisig (July 2017): fallback method × delegatecall × public-by-default visibility = naked eval on attacker-controlled payload; $31M drained, $150M saved only by counter-theft.
Parity multisig (Nov 2017): library contract re-initialised by an outsider then suicided, locking $153M in wallets whose code had vanished — “left-pad for multi-million-dollar table stakes.”

KEVM (K framework operational semantics) gives Ethereum an executable semantics; generated interpreter ~20× slower than cpp-ethereum but usable, and supports reachability-based proof of safety/liveness claims.

Cognitive-science constraint. Miller’s 7±2 bounds how much implicit state a programming language can demand before human reasoning fails. Solidity’s implicit defaults (public methods, fallback dispatch, implicit conversions) exceed that budget.

“Worse is better” is unconscionable in a financial system. Sacrificing correctness and completeness to ship first transfers the cost of undefined behaviour onto users.

Connections

Making Smart Contracts Smarter — same semantic gap diagnosis; OYENTE is the symbolic-execution complement to Patterson’s formal-semantics prescription.

Formalise Blockchain Interoperability Patterns — companion move: formalise what was informal.

Security Applications Of Formal Language Theory — the Sassaman/Bratus/Patterson LangSec manifesto this talk operationalises for smart contracts.

The Halting Problems of Network Stack Insecurity — parallel argument that parser/semantics weakness is the root cause of whole vulnerability classes.

Exploit Programming - From Buffer Overflows To Weird Machines — “weird machines” framing applies directly to contracts driven off-spec via delegatecall.

PKI Layer Cake - Kaminsky Patterson Sassaman — Patterson’s earlier demonstration that grammatical discrepancies between implementations are exploitable (SSL CA forgery); same mechanism, different domain.

A Language-Based Approach To Prevent DDoS — language-theoretic remediation as a general pattern.

Operational Semantics, Denotational Semantics, EVM, Solidity, TheDAO, Reentrancy — background concepts.

An Unsolvable Problem of Elementary Number Theory — Church 1936; LangSec’s undecidability heritage behind the Rice’s-theorem argument against gas-as-safety.

Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I — Gödel 1931; the incompleteness ancestor of the semantic-limit arguments.

Rice’s Theorem

A foundational result in computability theory (Henry Gordon Rice, 1951–53): every non-trivial semantic property of the partial function computed by a program is undecidable. Source paper: Classes of Recursively Enumerable Sets and Their Decision Problems. “Non-trivial” means the property holds for some computable functions but not others; “semantic” means it depends on the input/output behaviour, not on the syntactic form of the program.

Put differently: you cannot in general decide, by inspecting a program, whether it belongs to any interesting class defined by what it does. Halting is one such property (Halting Problem), but so is “produces output X on input Y,” “terminates for all inputs,” “implements function f,” “contains no unreachable states,” and so on.

Rice’s theorem is the formal frontier against which static-analysis, verification, and capability-bounding claims must be measured. Any tool promising to decide a non-trivial semantic property on arbitrary programs is — by Rice — either restricting the program class (e.g. Finite-state Grammars, typed or total subsets) or approximating (sound-but-incomplete analyses). Whole research programs — LangSec, Formal Verification, Static Analysis, Weird Machine — are organised around this constraint.

Concrete implication cited in House on Rock - LangSec in Ethereum Classic: Ethereum’s gas mechanism cannot “sidestep Turing completeness” to deliver a safety guarantee, because safety is a semantic property and Rice’s theorem makes semantic properties of arbitrary programs undecidable. Gas is a resource bound (non-semantic, decidable) masquerading as a safety property (semantic, undecidable).

Liveness Property

A property of a program or distributed system asserting that “something good eventually happens” (Lamport 1977; Alpern & Schneider 1985). Unlike a Safety Property, a liveness property cannot be falsified by any finite prefix — one must observe (or reason about) infinite behaviours.

Examples: eventual delivery (“every sent message is eventually received”), progress (“every enabled thread eventually runs”), termination (“every well-formed input produces output”). Proving liveness typically requires a well-founded ordering or a fairness assumption.

Alpern–Schneider’s decomposition theorem: every trace property is the intersection of a safety property and a liveness property. This factoring structures verification: safety is proved by invariants, liveness by well-founded descent or fairness-conditioned reasoning.

Safety Property

Tags

Backlinks