Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

CVE-2021-32471 – Input validation in Marvin Minsky 1967 Turing Machine

cve.mitre.org

Post reply on HN
Print view View original

31–40 of 43 posts

Re: CVE-2021-32471 – Input validation in Marvin Minsky 1967 Turing Machine

#31

Post by magmastonealex »

qsort wrote: post #22
ludamad wrote: post #21

Earlier quoted context omitted.

A non-TC language can be achieved just by forcing proofs. Oh, you want that program to run? Just prove that it is bounded memory and can't halt, etc

Yeah, but that's the 'cumbersome' part. Could we imagine a non-TC language with simple syntax that's suitable for at least some of the task you'd use a TC language for?

C compiled down to eBPF (as implemented with the Linux kernel) is not turing-complete. eBPF has a wide variety of uses from network filtering to hooking into certain syscalls.

The bytecode is theoretically turing-complete, but the verifier present in the kernel ensures that the code contains no loops and accesses no out-of-bounds memory.

With `clang`, you can compile C down to eBPF bytecode. It's a subset of C, with a lot of restrictions, but it is familiar and capable of some remarkable things past just simple packet parsing & filtering.

Re: CVE-2021-32471 – Input validation in Marvin Minsky 1967 Turing Machine

#32

Post by qsort »

UncleMeat wrote: post #25
qsort wrote: post #10

Earlier quoted context omitted.

Yes, that's the joke.

No it isn't. The paper forces the universal turing machine to execute a different machine than the one on the input tape by providing crafted input to the intended simulated machine. It isn't a joke paper. U is fed machine T and input I. By only changing I you can force U to execute a different machine X.

Sure, but you achieve that by specifying I in a way you aren't really supposed to. You are effectively invoking undefined behavior.

The implications of this are well understood. You'd have similar vulnerabilities if you ran raw machine code on, say, an x86 processor. Enforcing checks and sanitization in such a way that the 'exploit' can't happen is the exact kind of job you'd have to do in order to write an operating system.

Re: CVE-2021-32471 – Input validation in Marvin Minsky 1967 Turing Machine

#33

Post by qsort »

magmastonealex wrote: post #31
qsort wrote: post #22

Earlier quoted context omitted.

Yeah, but that's the 'cumbersome' part. Could we imagine a non-TC language with simple syntax that's suitable for at least some of the task you'd use a TC language for?

C compiled down to eBPF (as implemented with the Linux kernel) is not turing-complete. eBPF has a wide variety of uses from network filtering to hooking into certain syscalls. The bytecode is theoretically turing-complete, but the verifier present in the kernel ensures that the code contains no loops and accesses no out-of-bounds memory. With `clang`, you can compile C down to eBPF bytecode. It's a subset of C, with…

I had no idea, this is fascinating. Thanks for sharing.

Re: CVE-2021-32471 – Input validation in Marvin Minsky 1967 Turing Machine

#34

Post by al2o3cr »

Meh. The "exploit" seems to rely on passing input that contains cells with values that are valid for the universal machine's tape alphabet, but not the simulated machine's.

It's as if you could pass a "null terminator" in a Unicode string that didn't match the "normal" null character.

Re: CVE-2021-32471 – Input validation in Marvin Minsky 1967 Turing Machine

#35

Post by chaganated »

userbinator wrote: post #20

I think this should be considered a satire of what the "security industry" has become: finding any little thing that they can claim is exploitable, regardless of actual significance, and all the while using paranoia to slowly destroy general-purpose computing and user freedom.

best comment, last comment

Re: CVE-2021-32471 – Input validation in Marvin Minsky 1967 Turing Machine

#36

Post by buitreVirtual »

yabones wrote: post #3

> NOTE: the discoverer states "this vulnerability has no real-world implications." At least they're honest about it with this CVE...

I'm not so sure. Some banks and airlines might still be running those machines.

Re: CVE-2021-32471 – Input validation in Marvin Minsky 1967 Turing Machine

#37

Post by zitterbewegung »

tester34 wrote: post #26
zitterbewegung wrote: post #8

Sure this CVE sounds like a joke but if you create a programming language that is non Turing complete it is much easier to secure than a Turing complete language. Making a language that have the expressive power of finite state machines could be an example.

What does Turing completness even mean in practice when it comes to non-theoretical languages?

You can't do anything like recursion.

Re: CVE-2021-32471 – Input validation in Marvin Minsky 1967 Turing Machine

#38

Post by toxik »

OskarS wrote: post #12
qsort wrote: post #10

Earlier quoted context omitted.

Yes, that's the joke.

I get that the CVE is a joke, but are you saying the paper is as well?

It’s not a joke, people saying otherwise did not understand the paper. The significance is debatable, it’s mostly a kind of collective facepalm for theoretical computer scientists.

The CVE is a joke in the sense that you don’t really need a CVE for a universal Turing machine, as they are quite literally only academic.

Re: CVE-2021-32471 – Input validation in Marvin Minsky 1967 Turing Machine

#39

Post by klyrs »

zitterbewegung wrote: post #37
tester34 wrote: post #26

Earlier quoted context omitted.

What does Turing completness even mean in practice when it comes to non-theoretical languages?

You can't do anything like recursion.

I spent a while trying to parse this, and it doesn't make a lick of sense.

Brainfuck is a classical example of a turing complete language that doesn't have a notion of functions. What does "recursion" mean here? Nothing, I think. So you don't need recursion for Turing completeness.

Some people work on languages that support functions as first class objects, which don't natively support recursion. This is nice from a language design standpoint, because functions only see the scope of their arguments and can't look any further. The "Y Combinator" pattern is used to bootstrap recursion into these languages. You may have heard of it.

Turing-incomplete languages can also support unlimited recursion. For example, take a Turing complete language, and equip it with a state of the art theorem prover. Before entering a loop, or calling a function, the theorem prover is allowed to spend up to 1 minute proving that the loop or function call will terminate. If the theorem prover times out, the program halts with an error. Some functions, such as a naive implementation of factorial, can be easily proved to halt for all inputs. So this language allows recursion, but by construction, all programs terminate, so it's turing incomplete.

Post reply on HN