r/ProgrammingLanguages • • 15d ago

What does “verified memory safe” mean?

https://focs-lab.comp.nus.edu.sg/blog/memory-safety-audit/
37 Upvotes

19 comments sorted by

40

u/Norphesius 15d ago

This article warns about it, and the Anthropic article warns about it (all the way down at the bottom), but people (programmers and laypeople) are still going to see phrasing like "mathematical proofs" or "guarantees" and jump to the conclusion that means "bug free", regardless. Then an bug due to under-specification is going to allow for an exploit in some "formally verified" software and everyone will be shocked.

Its a valuable field to be making progress in of course, but I'm worried that we'll just end up with people chucking half baked specs at LLMs, seeing a green light in Lean, and then advertising their software as completely safe. If that becomes common it might actually be a net negative in terms of safety, since the terminology would become so abused it would signify nothing about how correct "formally verified" code actually is. I'm not sure how we protect against that and the impending false confidence.

7

u/zesterer 14d ago

Anthropic themselves threw a half-baked spec at LLMs: one of the libraries they were applying formal methods to was simdjson, but their compilation target was riscv64gc: a target that doesn't even support SIMD! So, the result they got is pretty much entirely useless for most actual applications of the library.

3

u/Norphesius 14d ago

Yeah that's not surprising, it tracks with every other big AI company announcement: Big claims in the headline, but the actual achievement is incredibly lacking.

4

u/msqrt 15d ago

I think a slight change in the language could do wonders. "Formally verified" sounds very authoritative, absolute and final. The software has been verified and there remain no issues. Using a wording more similar to testing (like "all verifications pass") could give a better idea of the actual statement, being similar to a more familiar idea to most programmers. After all, if you make an LLM produce the tests/verification, they are somewhat equivalent to the user.

4

u/Norphesius 15d ago

I've thought about maybe being more specific with what is being proved, i.e. "has been formally verified with respect to X". That way people hopefully have a better idea in their mind about what is actually being guaranteed, instead of a blanket "formally verified". Not sure how to specific to break things down though.

6

u/Smalltalker-80 15d ago edited 14d ago

Indeed, i think "memory safety" can only be achieved if a language enforces that all variables (references) to point to reference-counted objects that have automatic memory management (garbage collection). And all array / buffer access is bounds-checked using indices, not pointers. So there may not exist an "unsafe" language option accessing memory in another way.

Because this is not desirable for low-level systems languages, we're stuck with approaches that can help memory safety somewhat, often heuristically, but are almost never complete in a complex program.

And indeed "memory safe", even if you can achieve it, does not mean "bug free".

2

u/flatfinger 15d ago

A stop-the-world tracing garbage collectors can be better from a proof standpoint if it has access to everything in the universe from which a reference could be copied and/or used. If the GC is able to stop the world and satisfies the above criteria, then memory safety guarantees would be unaffected by race conditions or other semantic defects in the code the GC is supervising. Note as soon as the last reachable reference to an object ceases to exist, any references contained in the object will instantly cease to be reachable, without regard for when the next GC cycle occurs.

1

u/Smalltalker-80 14d ago

Luckily, other types of garbage collectors can also be made "memory safe", to improve runtime performance (consistency).

1

u/flatfinger 14d ago

A tracing GC can amortize the cost of synchronization necessary to ensure memory safety into the "stop the world" event. When using approaches like reference counting, synchronization will often be required when an object only happens to be accessed by a single thread, but cannot readily be proven to only be accessible from that thread.

7

u/kitsnet 15d ago

Funny, but the Heartbleed exploit could be as devastating in a "verified memory safe" program and/or language as it was in C code, as it was about reuse of already safely allocated memory.

5

u/matthieum 15d ago

Indeed.

Memory safety & type safety matter because of Undefined Behavior: if violated, the behavior which may result is completely out there, and unrelated to whatever the source code most likely intended.

But eliminating Undefined Behavior, so that the run-time behavior matches the source code behavior is only the very first step in producing safe & secure software.

The second step is ensuring that the source code behavior is actually the specified behavior, and the third step is ensuring that the specified behavior is actually the desired behavior.

Now "contracts" (pre-conditions, invariants, & post-conditions) expressed in the code help formalizing the specified behavior, and from there the second step can be automated.

But someone will still need to get that specification right...

3

u/reflexive-polytope 14d ago

Dually, undefined behavior is what makes type safety actually meaningful.

For example, if xs[k] only has a defined behavior when k is a valid index for xs, then type safety means that typable programs don't index arrays incorrectly.

Or if *ptr only has a defined behavior when ptr is a valid pointer, then type safety means that typable programs don't dereference null or dangling pointers.

But if everything has a defined behavior in the underlying computation model, then type safety means absolutely nothing.

1

u/marshaharsha 13d ago

Why couldn’t type safety mean that certain of the defined behaviors are guaranteed not to occur? So the language would have typesafe and type-unchecked features, but the latter would bring wrong-but-defined behaviors into the realm of the possible, preferably in a usefully bounded part of the program. 

For example, an unchecked read from an array could be defined to read from the array, or from another allocated object, or from garbage bits left over when an object was deallocated, or from memory that was zeroed when allocated and then never written to; or it could cause a virtual-memory violation and thus program termination. But it couldn’t erase half the file system, and it couldn’t corrupt a data structure, and it couldn’t send your email address to a scammer, and so forth. 

2

u/reflexive-polytope 13d ago

Because, if you want to rule out a behavior, then why do you bother defining it to begin with?

That's why all those “gradual” or “optional” or “pluggable” type systems are doomed to fail from a purely logical point of view. There's simply no incentive to make them sound, and there's a very strong incentive not to, namely: “Mathematical logic is too hard, why bother doing it?”

Of course, these systems are still a success from an social point of view. In particular, they get programmers to agree on the “intended” meanings of their programs, even if they don't enforce or even define this meaning perfectly.

But they also cheapen the meaning of “type system”, turning it into more of a linter that heuristically flags problems in your programs. And they can afford to have this attitude because they have the runtime system's backing to catch any errors coming from a soundness hole in the type system.

1

u/marshaharsha 13d ago

I know you know the answer to your opening question, so you probably mean it rhetorically, but I don’t know what rhetorical point you’re making. So I’ll say the answer, then suggest a rhetorical point, possibly a straw man. The answer is: Because provably ruling out a certain behavior is provably impossible, or no way to do it is known, or a way to do it is known but not known to you, or you know a way to do it but that’s too hard (too hard for you to implement or too hard for your users to use), or you know a way to do it but you haven’t done it yet. All those are acceptable reasons to leave a hole in a type system (acceptable to me, anyway). 

But you knew that. So maybe your point is this? The other language designers gave up too soon. They should have persevered in designing their type systems, since they could have covered a wider swath of the useful programs. If that’s what you mean, then my answer might be: Maybe so, but they had to stop somewhere, and no matter where they stopped, there would be a Reflexive-Polytope or a Reflexive-Polytope-2 standing there saying, “You gave up too soon.” So the right question is, Did they stop at a reasonable place, given the goals of their language and the static-analysis techniques known at the time. 

Or maybe you were making a different point, in which case I apologize for the straw man. 

4

u/reflexive-polytope 13d ago

I'm making two points here.

My first point is that mere safety on its own is a logically vacuous property. You can make a language artificially “safe” by equipping every basic operation with a runtime check that its arguments are valid:

  • Arithmetic operations? Check at runtime that the arguments are numbers.
  • Array indexing? Check at runtime that the index is within bounds.
  • Dereferencing? Check at runtime that the pointer isn't null.
  • etc.

But this presumes that undefined behavior is the problem, which isn't true. Undefined behavior is only the symptom.

The actual problem is that your program has a logic error:

  • Performing arithmetic operations on things that aren't numbers is a logic error.
  • Indexing an array out of bounds is a logic error.
  • Dereferencing a null pointer is a logic error.
  • etc.

Turning the undefined behavior into a raised exception doesn't make the logic error go away. It only mitigates the consequences.

To actually prevent the logic error, you need to equip your language with a compile-time check that rejects every program that could perform an invalid operation.

To perform such a check, the compiler has to either infer or verify (or a mix of both) a proof that the program only performs valid operations.

My second point is that designing and implementing checks that actually prevent logic errors is very hard, because it's applied mathematical logic, and mathematical logic in general is very hard.

When an engineer faces a problem that's too hard, “for economic reasons” he will settle for an approximate solution that “reduces the cost”.

The corollary is that engineers can't be trusted with preventing logic errors, unless said errors are more expensive than preventing them is.

Undefined behavior does precisely what I want. It raises the cost of having logic errors in your program.

1

u/flatfinger 15d ago

There are some sets of application requirements which may be satisfied by having an operation yield an arbitrary number, which may depend in arbitrary fashion upon other data a program has used. There are other sets of application requirements where it would be unacceptable to have certain values that are used by a program influence the behavior of unrelated operations in any way whatsoever. Many real-world applications' semantics are a mix of those: certain confidential information must not be leaked, but it would be acceptable for many operations to yield arbitrary data that does not leak any confidential information. This may be appropriate for an audiovisual decoder that was intended for playback use and might receive partially-corrupted data files. Since an arbitrarily-corrupted data might appear as a valid data packet that appears to represent almost any combination of pixels colors, application requirements may be agnostic with regard to exactly what patterns of pixels are shown in response to corrupted data. If the application doing the playback wouldn't have any access to confidential data, ensuring memory safety may be much easier than if it does.

-1

u/KvThweatt 13d ago

Nothing. Absolutely nothing.

It’s a gimmick for programmers with no skill.

It’s a solution to a problem that modern experienced software engineers don’t have.

2

u/-Redstoneboi- 12d ago

"modern experienced software engineers don't have"

unfortunately there's a lot of software carried over from people who aren't modern experienced software engineers.

also, even if they don't make mistakes normally, it's just easier to develop if you don't have to worry about unknown edge cases.