engineering

Proof-carrying code

Proof-carrying code is a engineering topic covered in the lgStudy science library. This page brings together a partial reference excerpt, illustrations, worked examples, real-world applications and a short study plan, so you can understand Proof-carrying code rather than just read about it. In short: Proof-carrying code (PCC) is a software mechanism that allows a host system to verify properties about an application via a formal proof that accompanies the application's executable code. The host system can quickly verify the validity of the proof, and it can compare the conclusions of the proof to its own security policy to determine whether the application is safe to execute.

Key takeaways

Proof-carrying code belongs to engineering; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Proof-carrying code to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Proof-carrying code from memory before moving on to harder problems.

Reference excerpt

Proof-carrying code (PCC) is a software mechanism that allows a host system to verify properties about an application via a formal proof that accompanies the application's executable code. The host system can quickly verify the validity of the proof, and it can compare the conclusions of the proof to its own security policy to determine whether the application is safe to execute. This can be particularly useful in ensuring memory safety (i.e. preventing issues like buffer overflows). Proof-carrying code was originally described in 1996 by George Necula and Peter Lee.

Packet filter example The original publication on proof-carrying code in 1996 used packet filters as an example: a user-mode application hands a function written in machine code to the kernel that determines whether or not an application is interested in processing a particular network packet. Because the packet filter runs in kernel mode, it could compromise the integrity of the system if it contains malicious code that writes to kernel data structures. Traditional approaches to this problem include interpreting a domain-specific language for packet filtering, inserting checks on each memory access (software fault isolation), and writing the filter in a high-level language which is compiled by the kernel before it is run. These approaches have performance disadvantages for code as frequently run as a packet filter, except for the in-kernel compilation approach, which only compiles the code when it is loaded, not every time it is executed. With proof-carrying code, the kernel publishes a security policy specifying properties that any packet filter must obey: for example, the packet filter will not access memory outside of the packet and its scratch memory area. A theorem prover is used to show that the machine code satisfies this policy. The steps of this proof are recorded and attached to the machine code which is given to the kernel program loader. The program loader can then rapidly validate the proof, allowing it to thereafter run the machine code without any additional checks. If a malicious party modifies either the machine code or the proof, the resulting proof-carrying code is either invalid or harmless (still satisfies the security policy).

See also Typed assembly language Program derivation Formal verification Berkeley Packet Filter

References

George C. Necula and Peter Lee. Proof-Carrying Code. Technical Report CMU-CS-96-165, November 1996. (62 pages) George C. Necula and Peter Lee. Safe, Untrusted Agents Using Proof-Carrying Code. Mobile Agents and Security, Giovanni Vigna (Ed.), Lecture Notes in Computer Science, Vol. 1419, Springer-Verlag, Berlin, ISBN 3-540-64792-9, 1998. George C. Necula. Compiling with Proofs. PhD thesis, School of Computer Science, Carnegie Mellon Univ., Sept. 1998.

Worked examples

Example 1 — a first encounter with Proof-carrying code

Start with the simplest possible case. Write down what Proof-carrying code claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In engineering, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Proof-carrying code before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Proof-carrying code ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Proof-carrying code

In research: Proof-carrying code appears in engineering research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Proof-carrying code in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Proof-carrying code is common in secondary-school and first-year university syllabi. It links to neighbouring topics Cybersecurity engineering, Dependently typed programming, Formal methods, so understanding it makes those chapters shorter.
In everyday life: Look for Proof-carrying code outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

Affiliate

Preply — study more efficiently by working with a personal tutor. 50% off.

How to study Proof-carrying code in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Proof-carrying code means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Proof-carrying code out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Proof-carrying code in simple terms?

Why does Proof-carrying code matter?

Because it connects several engineering ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Proof-carrying code?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Proof-carrying code.