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

21–30 of 43 posts

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

#21

Post by ludamad »

qsort wrote: post #14
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.

We are doing this already. - Configuration languages (JSON, YAML, XML) are pure combinatorial logic. - Regular expressions are... mostly not actually regular, but you get the idea. - Some templating languages are deliberately less powerful than Turing machines, e.g. ST4 is context-free. - Prepared SQL statements are a similar idea on a different axis. The real question is whether a non-TC language could be useful for…

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

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

#22

Post by qsort »

ludamad wrote: post #21
qsort wrote: post #14

Earlier quoted context omitted.

We are doing this already. - Configuration languages (JSON, YAML, XML) are pure combinatorial logic. - Regular expressions are... mostly not actually regular, but you get the idea. - Some templating languages are deliberately less powerful than Turing machines, e.g. ST4 is context-free. - Prepared SQL statements are a similar idea on a different axis. The real question is whether a non-TC language could be useful for…

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?

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

#23

Post by OskarS »

segfaultbuserr wrote: post #13
OskarS wrote: post #9

Earlier quoted context omitted.

Haven't looked into this paper deeply, but this reads very strange to me: > This paper reports on the discovery of an accidental arbitrary code execution vulnerability in Marvin Minsky's 1967 implementation of the universal Turing machine. By submitting crafted data, the machine may be coerced into executing user-provided code. It's a universal Turing machine. Its whole purpose is running "user-provided code". That's…

> This is a little bit like saying "we found a weakness in the Python interpreter whereby you can feed it specially crafted input that allows you to run arbitrary Python programs". If my understanding is correct, it's more like, "we found a weakness in the Python interpreter whereby you can feed it a specially crafted input to a Python script that allows you override that script and forces the Python interpreter to d…

Ah, that makes a ton of sense. Thanks!

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

#24

Post by jradd »

mycall wrote: post #11
qsort wrote: post #10

Earlier quoted context omitted.

Yes, that's the joke.

Wait until they try unicode, then the joke will be on them.

I cannot fathom how complicated arbitrary code execution could get with multi byte characters that could use shift registers, null bytes and byte order marks with determinism in a NOP slide on a heap spray.

Filtering only printable user input helps but even bit map images can expose a heap to a sensitive registers that will execute some target specific generated shell code.

https://en.m.wikipedia.org/wiki/NOP_slide.

https://en.m.wikipedia.org/wiki/Heap_spraying

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

#25

Post by UncleMeat »

qsort wrote: post #10
OskarS wrote: post #9

Earlier quoted context omitted.

Haven't looked into this paper deeply, but this reads very strange to me: > This paper reports on the discovery of an accidental arbitrary code execution vulnerability in Marvin Minsky's 1967 implementation of the universal Turing machine. By submitting crafted data, the machine may be coerced into executing user-provided code. It's a universal Turing machine. Its whole purpose is running "user-provided code". That's…

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.

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

#26

Post by tester34 »

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?

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

#28

Post by UncleMeat »

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?

A useful subset of SQL is not turing-complete and is suitable for meaningful computational tasks. Datalog is also not turing-complete and is similarly useful.

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

#29

Post by qsort »

UncleMeat wrote: post #28
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?

A useful subset of SQL is not turing-complete and is suitable for meaningful computational tasks. Datalog is also not turing-complete and is similarly useful.

Sure, more examples are CSP solvers and AMPL. They are all somewhat specific though. I was wondering if it would be possible to make one that's "general purpose" in the same sense you call programming languages "general purpose", i.e. one you'd write application software in.

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

#30

Post by UncleMeat »

qsort wrote: post #29
UncleMeat wrote: post #28

Earlier quoted context omitted.

A useful subset of SQL is not turing-complete and is suitable for meaningful computational tasks. Datalog is also not turing-complete and is similarly useful.

Sure, more examples are CSP solvers and AMPL. They are all somewhat specific though. I was wondering if it would be possible to make one that's "general purpose" in the same sense you call programming languages "general purpose", i.e. one you'd write application software in.

Datalog would be the closest I can think of. A bunch of static analysis engines are implemented in it.
Post reply on HN