Proof-carrying code is a software mechanism that allows a host system to verify properties about an application via a formal proof

Formal proof

A formal proof or derivation is a finite sequence of sentences each of which is an axiom or follows from the preceding sentences in the sequence by a rule of inference. The last sentence in the sequence is a theorem of a formal system...

 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

Security policy

Security policy is a definition of what it means to be secure for a system, organization or other entity. For an organization, it addresses the constraints on behavior of its members as well as constraints imposed on adversaries by mechanisms such as doors, locks, keys and walls...

 to determine whether the application is safe to execute. This can be particularly useful in ensuring memory safety, i.e. preventing buffer overflows  and other vulnerabilities common in some programming languages.

Proof-carrying code was originally described in 1996 by George Necula

George Necula

George Ciprian Necula is a Romanian computer scientist and professor at the University of California, Berkeley who does research in the area of programming languages and software engineering, with a particular focus on software verification and formal methods. He is best known for his Ph.D...

 and Peter Lee

Peter Lee

Peter Granville Lee, born at Arthingworth, Northamptonshire, on 27 August 1945, is a cricketer who played for Northamptonshire and Lancashire.Lee was a right-arm fast-medium bowler who moved the ball off the seam and took a lot of wickets in English county cricket in the 1970s...

.

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 all have severe performance disadvantages for code as frequently run as a packet filter.

With proof-carrying code, the kernel publishes a security policy specifying properties that any packet filter must obey: for example, will not access memory outside of the packet and its scratch memory area. A theorem prover or certifying compiler 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. The kernel 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).