Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

With the size of the proof object, a potential buffer overflow comes to mind.
 help



It doesn't seem execution was a problem. From Kevin Buzzard's blog:

I’ve compiled the code base and run comparator on it — it checks out. It is a gigantic proof (over 13.4 million lines of code) and takes nearly 20 times as long to compile as Lean’s mathematics library (on a machine with 96 cores!). Lean can be sluggish when jumping from file to file on a repo of this size (even on a machine with 500G of ram, which Anthropic also gave me access to), but Anthropic also supplied me with some html documents which are easier in practice to explore (clone the repo and open with a web browser).

500G of RAM is not actually that huge tbh (I was looking to buy a used 1TB server blade for some personal stuff a while ago but it was too much hassle) so I don't guess there was too much potential for buffer overflows.


Buffer overflows are trivial to check for at runtime (~proof-checking-time) and Lean does this. Just like Java does it.

I’d wager a million gazillion bucks that this is not the case.


So would you also say no chance of a stack overflow or any type of surreptitious storage overflow anywhere in the runtime do you think?

I would say it’s very unlikely to be the case here at least.

Of course some bugs in Lean may exist (I don’t have deep insight into Lean’s implementation and there have been bugs before), but I find it unlikely to be systematical or in a format that could affect the proof.

As I understand it, Lean is implemented in Lean and emits/compiles to C. In that C code, I’d be very surprised if any buffer overflows or stack overflows exist.

Such overflows are not difficult or expensive to detect, so if any were there, it should cause a crash instead of an incorrect result.

It’s not as in handwritten C where you can forget or omit a bounds check.

I’d say it is even less likely than seeing an overflow in the Core of Java cause an incorrect result (i.e. corruption instead of a crash) - because Lean uses the De Bruijn principle of reducing to a very small Core, that is easier to keep correct (others in this thread have expanded on this I better than I can I think).

Out of pure curiosity: Do you believe otherwise or have a reason to think I am mistaken?


No I don't have any reason to believe you are mistaken other than general suspicion.

Stack overflows are also trivial to check for, if one wants to. It's just comparing two pointers, plus checking for arithmetic overflow (in case the pointers run past the maximum value of the pointer type).



Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: