Comment by ogogmad

3 years ago

I've heard of seL4, but I don't think it gets used much in the software industry. Not getting used kind of defeats the point of it, unless we need another 20 years for the formal methods people to produce an OS kernel people will actually use, while the AIs are eliminating programming as a field altogether.

I'll need to think about the other stuff you said. I reserve a high level of skepticism to everything you've said.

The existence of seL4 and its ability to be used in real projects certainly proves that formal methods has been effectively used to improve safety and security in shipping products, which was the question you asked if I understood it correctly...

> while the AIs are eliminating programming as a field altogether.

Where? So far, GPT-4 gets confused when given a specification with more than a dozen logic variables, and confidently regurgitates things that are, best case, partially working, and worst case, completely broken, based on a generative model trained on Stack Overflow and other forums. It's a cute concept, but it's closer to Eliza than eliminating this field. I can give it a logic problem that a freshman CS student can solve, and it will confidently give me the wrong answer. While I'm sure that LLMs will get better over time, I personally think their current application in software development has been over-hyped. There are plenty of papers, including the (in)famous "Stochastic Parrots" paper that are quite scathing. Based on my own tire kicking experience, I'm not convinced that LLMs can replace much more than boilerplate programming unless there are significant breakthroughs well beyond the current state of the art. Not incremental changes, but a complete reinvention of the current science.

You can be skeptical regarding formal methods, but I use formal methods daily. It adds roughly 25% overhead over just unit testing to model check software, which easily covers 95% of the code base. The important parts -- enforcing function contracts, data flow, resource management, and correct usage patterns for things like cryptographic primitives -- are actually quite trivial to implement using an SMT solver. There is difficulty when dealing with loops, recursion, data structures, and algorithms, but most code out there can be abstracted away from these concepts. Contract enforcement at the library and framework level are certainly possible using tools as they exist today.

  • > The existence of seL4 and its ability to be used in real projects certainly proves that formal methods has been effectively used to improve safety and security in shipping products, which was the question you asked if I understood it correctly...

    No, I would expect evidence that seL4 actually gets used. Otherwise it's yet another purely academic proof of concept.

    > GPT-4 ... closer to Eliza ... over-hyped ... "Stochastic Parrots" paper

    You might want to look at this YouTube channel here, to see that LLMs are capable of imagination and complex logical reasoning: https://www.youtube.com/@aiexplained-official

    Who knows what the future holds? ¯\_(ツ)_/¯

    Anyway, it would be interesting to know a bit more about your field experience using formal methods - if possible. Thanks.

    • seL4 has seen use in military projects, including UAVs and drones. It's been endorsed by the Linux Foundation. I wouldn't really call it an academic proof of concept at this point.

      Regarding logic problems, I've tested GPT-4 and Bard. Both fail some pretty typical logic problems, because that's not what they were designed to solve. They match patterns. This is great for story telling, summarizing, and replication of plausible prose based on its training. But, these systems break down in subtle ways when prompted to perform logical reasoning. Don't take my word for it though.

      https://arxiv.org/abs/2205.11502

      Even logical reasoning we take for granted, like variable substitution, is difficult for an LLM.

      https://paperswithcode.com/paper/the-reversal-curse-llms-tra...

      I will agree with you, however, that making any predictions about where this technology will go in the future is difficult. My experience tells me that the current modeling of LLMs are on the wrong track, but a lot of money is being invested in this technology. If there is a way to improve it incrementally, and if these incremental improvements can cause a significant paradigm shift, then perhaps I'll be proven wrong.

      As for my field experience using formal methods, I currently build system software and firmware. I use model checking daily. I have built up abstract machine models using Coq and Lean 4 to constructively build data structures and algorithms that I can extract to C and machine code. Typically, these would include software cryptographic primitives, graph algorithms, data structures like binary trees, and file systems. I'd say that model checking covers about 95% of my usage of formal methods, and constructive proofs cover the remaining 5%. I use a combination of CBMC and Z3 to model check the software and firmware that I write. CBMC is used to model check software in C. Z3 is used to model check assembler and machine code.

      1 reply →