{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# OpenDP Proof Initiation"
]
},
{
"attachments": {},
"cell_type": "markdown",
"metadata": {},
"source": [
"This notebook is an introduction to writing proofs in the OpenDP framework.\n",
"It assumes you have already read about the [programming framework in the user guide](https://docs.opendp.org/en/stable/user/programming-framework/index.html), and you have some familiarity with the library interfaces.\n",
"\n",
"Our goal is to prove that OpenDP produces stable transformations and private measurements. \n",
"This requires a large body of proofs, as constructor functions typically depend on other functions or traits that themselves need to be proven.\n",
"\n",
"\n"
]
},
{
"attachments": {},
"cell_type": "markdown",
"metadata": {},
"source": [
"## Proof Structure\n",
"\n",
"Each document should at least have these components:\n",
"\n",
"1. Hoare Triple \n",
" 1. Precondition\n",
" 2. Pseudocode\n",
" 3. Postcondition\n",
"2. Proof of postcondition, assuming precondition\n",
"\n",
"The precondition is a predicate function that captures any restrictions on the set of valid inputs to the function. \n",
"The (Python-esque) pseudocode may exploit the restrictions on the inputs provided by the precondition and make use of other functions or traits.\n",
"The postcondition is also a predicate function that sharply characterizes the guarantees the function makes on the output.\n",
"\n",
"This gets more involved for measurement and transformation constructor functions.\n",
"Constructor functions need to argue the correctness of the stability map or privacy map,\n",
"which refers to the behavior on a pair of inputs.\n",
"A LaTex macro is mentioned below that generates the expected postconditions for transformation and measurement constructors.\n",
"\n",
"The proof should show that, for any setting of the input arguments for which the precondition is true, the postcondition is also true."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"## Function Example\n",
"Let's imagine we wanted to add a new function to `rust/src/metrics/mod.rs` that computes the absolute distance:\n",
"\n",
"```rust\n",
"/// # Proof Definition\n",
"/// For any setting of the input parameters, \n",
"/// returns either `Ok(out)` where $out \\ge |a - b|$, or `Err(e)`.\n",
"fn absolute_distance(a: T, b: T) -> Fallible {\n",
" a.inf_sub(&b)?.alerting_abs()\n",
"}\n",
"```\n",
"`inf_sub` is provided by the `InfSub` trait, and it computes the subtraction of `b` from `a`. By the proof definition of `InfSub`, if the outcome is not exactly representable in `T`, then the outcome is rounded towards positive infinity, to the nearest value in `T` (think of when `T` is float and arithmetic is not closed). \n",
"\n",
"Again by the proof definition of `InfSub`, `inf_sub` returns an error if the computation overflows. \n",
"The type of things that *might* be an error is `Fallible`, which is an enum containing either `Ok(value)`, where `value` is of type `T`, or `Err(e)`, where `e` is the error details (backtrace, message, debug info).\n",
"\n",
"Both `inf_sub` and `alerting_abs` return a value of type `Fallible`.\n",
"After calling `inf_sub`, the question mark exits the function early with the error, if there is one, otherwise execution continues to `alerting_abs` with the value of type `T` stored inside the `Ok` variant.\n",
"\n",
"Notice that the function expects a return of type `Fallible`.\n",
"This is consistent with the two return sites of the function: the question mark after `inf_sub`, and the implicit return of the outcome of `alerting_abs`.\n",
"\n",
"When reading code in Rust for proof purposes, you can generally ignore references (`&`), dereferences (`*`, not multiplication) and clones (`.clone()`).\n",
"We consider these aspects of the code proven by the Rust compiler."
]
},
{
"attachments": {},
"cell_type": "markdown",
"metadata": {},
"source": [
"### LaTex Template\n",
"\n",
"To prove `fn absolute_distance`, we add a new file adjacent to the function we want to prove, named after the function we want to prove:\n",
"`rust/src/metrics/absolute_distance.tex`.\n",
" \n",
"Here's a template for `absolute_distance.tex`:\n",
"```latex\n",
"\\documentclass{article} % necessary for Overleaf to recognize the file\n",
"\\input{../lib.sty} % `rust/src/lib.sty` contains boilerplate and macros\n",
"\n",
"\\title{\\texttt{fn absolute\\_distance}}\n",
"\\author{Your Name(s) Here}\\date{}\n",
"\n",
"\\begin{document}\n",
"\\maketitle\\contrib\n",
"Proves soundness of \\rustdoc{transformations/fn}{absolute\\_distance} in \\asOfCommit{mod.rs}{f5bb719}.\n",
"\n",
"\\subsection*{Vetting history}\n",
"\\begin{itemize}\n",
" \\item \\vettingPR{519}\n",
"\\end{itemize}\n",
"\n",
"\\section{Hoare Triple}\n",
"\\subsection*{Preconditions}\n",
"\\subsection*{Pseudocode}\n",
"\\subsection*{Postcondition}\n",
"\n",
"\\section{Proof}\n",
"\n",
"\\end{document}\n",
"```\n",
"\n",
"This template uses several macros defined in `rust/src/lib.sty`:\n",
"\n",
"* `\\contrib` adds a header to the document indicating the proof is in `\"contrib\"`. \n",
"\n",
"* `\\rustdoc{path/to/fn}{ident}` creates a link to the rust documentation for the function we are proving.\n",
"When you build the document, it should emit a link to the latest build of the docs on docs.rs, [which may not exist yet](https://docs.rs/opendp/latest/opendp/transformations/fn.absolute_distance.html).\n",
"When we cut a release, the `docs.rs` site is updated, and the links in your document will be fixed to the released version of OpenDP.\n",
"The first argument to the macro is the subset of the path after `opendp/`, up to the dot, and the second argument is the identifier name.\n",
"\n",
"* `\\asOfCommit{relative/path}{commit_hash}` is how you specify which file you are proving, and the commit hash that last edited the file you are proving. You can retrieve the hash with `git log -n 1 --pretty=format:%h -- path/to/file.rs`. If you are proofwriting within the git repository, you can also find this hash in the footnote. The resulting LaTex output is a permalink to the file and an indicator on if the file has been updated since. This makes is possible for proof documents to self-report when they go out-of-date.\n",
"\n",
"* `\\vettingPR{PR_number}` is a simple macro to link a specific pull request.\n",
"\n",
"* `\\docsrs{crate}{path/to/fn}{ident}` is not used in this template. It has a similar syntax to `\\rustdoc`, but with an extra leading argument to name a crate. It builds links to documentation in external crates on [docs.rs](https://docs.rs).\n",
"\n",
"* `\\validTransformation{input_arguments}{function_name}` is not used in this template, but is useful when writing a proof for a transformation constructor.\n",
"\n",
"* `\\validMeasurement{input_arguments}{function_name}` same as above, but for measurements.\n",
"\n",
"\n",
"These macros are written such that your document will still compile without `--shell-escape` enabled. \n",
"\n",
"You can build this template with:\n",
"```shell\n",
"pdflatex --synctex=1 --interaction=nonstopmode --file-line-error --aux-directory=out --output-directory=out --shell-escape absolute_distance.tex\n",
"```\n",
"If you use VSCode, the \"Development Environment\" documentation contains some advice for integrating this with the LaTex-Workshop extension.\n",
"\n",
"These options emit the build artifacts to ./out, which is configured to be ignored by git.\n",
"**This is intentional, you should only include the `.tex` file when committing to OpenDP!**\n",
"A bot will attempt to build and link generated `.pdf` files from your PR.\n",
"\n",
"We now continue by filling out the proof sections."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"### Preconditions\n",
"The function we are proving has three input parameters, consisting of one generic (`T`) and two arguments (`a` and `b`), where the arguments `a` and `b` are of type `T`.\n",
"One may call this function with 32-bit signed integer arguments (`i32`):\n",
"```rust\n",
"absolute_distance(1i32, 2i32)\n",
"```\n",
"In this case, the setting of the input parameters is `(T=i32, a=1, b=2)`. The setting of `T` is inferred from the types of the arguments.\n",
"\n",
"The Rust syntax `T: InfSub + AlertingAbs` indicates that `T` is any type for which the `InfSub` and `AlertingAbs` traits are implemented. Thus, other valid types for `T` include the single-precision float `f32`, unsigned 32-bit integer `u32`, as well as other floats and integers with different bit depths. This may also extend to fixed-point types, bignum integers and rationals. \n",
"\n",
"Rust will only compile this code if the `InfSub` and `AlertingAbs` traits have been implemented for `T`. These bounds on the type `T` become part of the precondition for the function.\n",
"\n",
"```latex\n",
"\\subsection*{Preconditions}\n",
"\\begin{itemize}\n",
" \\item \\texttt{T} is a type with traits \\rustdoc{traits/trait}{InfSub} and \\rustdoc{traits/trait}{AlertingAbs}.\n",
"\\end{itemize}\n",
"```\n",
"\n",
"In other contexts, it may make sense to specify preconditions on the arguments as well."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Pseudocode\n",
"\n",
"The pseudocode should mimic the logic and usage of traits in the actual rust code.\n",
"The pseudocode isn't strictly-defined, it is a tool to communicate the algorithm in a way that is more accessible than Rust.\n",
"```latex\n",
"\\section{Pseudocode}\n",
"\\begin{lstlisting}[language = Python, escapechar=|]\n",
"def absolute_distance(a, b):\n",
" a.inf_sub(b).alerting_abs() |\\label{line:out}|\n",
"\\end{lstlisting}\n",
"```\n",
"\n",
"This code snip leverages the preconditions to make use of the `inf_sub` method on `a`."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Postcondition\n",
"\n",
"The postcondition is essentially the same as the proof definition on the Rust code.\n",
"```latex\n",
"For any setting of the input parameters for which the precondition holds, \\texttt{absolute_distance} returns either \\texttt{Ok(out)} where $out \\ge |a - b|$, or \\texttt{Err(e)}.\n",
"```\n",
"$|a - b|$ denotes an idealized quantity computed with infinite precision.\n",
"\n",
"Our goal is to use the pseudocode to prove that the postcondition is always true when the precondition is true."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Proof\n",
"\n",
"Start by assuming the preconditions are met!\n",
"```latex\n",
"\\section{Proof}\n",
"Assume the preconditions are met.\n",
"```\n",
"\n",
"In order to use the properties guaranteed in the proof definition of another function or trait, you must first prove that their preconditions hold.\n",
"`InfSub` and `AlertingAbs` don't have any preconditions.\n",
"\n",
"```latex\n",
"The preconditions for \\texttt{InfSub} and \\texttt{AlertingAbs} are trivially met.\n",
"```\n",
"\n",
"We now use these definitions to prove the postcondition:\n",
"```latex\n",
"\\begin{align*}\n",
" \\texttt{out} \n",
" &= a.inf_sub(b).alerting_abs() \\\\\n",
" &= max(a.inf_sub(b), -a.inf_sub(b)) && \\text{by \\texttt{AlertingAbs}} \\\\\n",
" &\\ge max(a - b, -a.inf_sub(b)) && \\text{by \\texttt{InfSub}} \\\\\n",
"\\end{align*}\n",
"```\n",
"At this point, we get stuck. \n",
"We can't show the inequality we expected because the code has a bug!\n",
"\n",
"If the sign of the difference is negative, the round towards infinity is a round towards zero, \n",
"resulting in a smaller absolute distance than the idealized absolute distance.\n",
"This breaks the guarantee in our proof definition. \n",
"A bug like this could be abused by an adversary with a sensitivity amplification widget; by carefully choosing constants that exploit the gaps between floating-point numbers with large magnitudes.\n",
"\n",
"This is why it is important to write proofsâ€” it is easy to miss a detail that can break privacy."
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3.8.13 ('psi')",
"language": "python",
"name": "python3"
},
"language_info": {
"name": "python",
"version": "3.8.13"
},
"orig_nbformat": 4,
"vscode": {
"interpreter": {
"hash": "3220da548452ac41acb293d0d6efded0f046fab635503eb911c05f743e930f34"
}
}
},
"nbformat": 4,
"nbformat_minor": 2
}