by telekid on 4/11/20, 1:32 AM with 49 comments
by zokier on 4/11/20, 8:49 PM
I take issue with the statement that TC means that something could "do anything". It means it can theoretically compute anything, but Turing completeness does not in itself give access to any additional resources; being TC does not magically allow something to talk to internet or write to disk or spawn new processes, or possibly not even allocate new memory. Computers do so much more than just compute; TC might be the first step towards being able to "do anything" but it certainly is not the final step.
From security point of view, what TC can (but not necessarily!) is open the host to denial of service by excessive resource consumption, or by non-terminating program. But as another comment noted, also non-TC systems can consume impractically large amounts of resources even if their resource consumption is not theoretically unbounded (as it is afaik with Turing machines).
by tdullien on 4/11/20, 9:29 PM
This does not detract from this post being a good, fun, and interesting read, but for anyone that is puzzled why “Turing complete” should imply “insecure”: It doesn’t.
by cryptonector on 4/12/20, 4:42 AM
!!!
!!!!!!!!!!!
From the SVG 1.2 draft:
> Note that these interfaces expose possible security concerns. The security model that these interfaces work under is defined by the user agent. However, there are a well-known set of common security guidelines used by the browser implementations in this area. For example, most do not allow access to hosts other than the host from which the document was retrieved. > > The next draft of SVG 1.2 will clearly list the minimum set of security features that an SVG user agent should put in place for these interfaces.
"Possible security concerns". No kidding. At least they were going to address them in the next draft version... though probably not by removing the ability to open sockets. Words fail me.
by moreati on 4/11/20, 10:04 PM
My research/tinkering so far is https://github.com/moreati/pickle-fuzz
by joe_the_user on 4/11/20, 9:07 PM
My head swims when the situation is described with this level of vagueness. I mean, sure the task of proving a theorem using the modern version of the Peano postulates is undeciable and so I'd assume a map from theorems in the Peano system to proofs of theorems would be Turing complete.
But a computation system based on calculating the values of simple arithmetic expressions isn't Turing complete. An express involving just adding and multiplying constant integer values will terminate.
by Complexicate on 4/11/20, 10:31 PM
"...mov, which copies data between the CPU & RAM, can be used to implement a transport-triggered-architecture one instruction set computer, allowing for playing Doom..."
Click on "Doom" link and read:
"The mov-only DOOM renders approximately one frame every 7 hours, so playing this version requires somewhat increased patience."
by pjscott on 4/11/20, 9:09 PM
https://www.gwern.net/Turing-complete#how-many-computers-are...
by mappu on 4/12/20, 7:24 AM
From https://docs.microsoft.com/en-us/typography/opentype/spec/tt... looks to have 32-bit words, a dynamic heap, unrestricted JMP targets, a generous number of math functions, ...
by arithma on 4/12/20, 3:27 PM
by saagarjha on 4/11/20, 8:28 PM
Note that ROP attacks in general tend to jump into the middle of functions because they have partially-cobbled together call states. ROP "chains" join together a couple of instructions followed by a return into something useful, but with "return-into-libc" it's usually to just jump straight midway into system and spawn a shell.
> Pokemon Yellow: “Pokemon Yellow Total Control Hack” outlines an exploit of a memory corruption attack which allows one to write arbitrary Game Boy assembler programs by repeated in-game walking and item purchasing. (There are similar feats which have been developed by speedrun aficionados, but I tend to ignore most of them as they are ‘impure’: for example, one can turn the SNES Super Mario World into an arbitrary game like Snake or Pong but you need the new programs loaded up into extra hardware, so in my opinion, it’s not really showing SMW to be unexpectedly TC and is different from the other examples.
I fail to see the difference; as far as I understood it, the Sumer Mario World examples were done by just playing the game? (By the way, I hear that Ocarina of Time has something like this now, too.)
> This matters because, if one is clever, it provides an escape hatch from system which is small, predictable, controllable, and secure, to one which could do anything. It turns out that given even a little control over input into something which transforms input to output, one can typically leverage that control into full-blown TC. This matters because, if one is clever, it provides an escape hatch from system which is small, predictable, controllable, and secure, to one which could do anything.
You can still prove sandboxing guarantees about executing Turing-complete programs.
by waynecochran on 4/11/20, 9:19 PM
by bertr4nd on 4/11/20, 10:13 PM
Basically, if I wanted to provide someone with a Turing complete language, what’s the simplest/easiest thing I could provide, that would still be useful?
by hirundo on 4/11/20, 9:57 PM
So Turing completeness implies recursive Turing completeness. It is the theoretical threshold at which a device is capable of reproduction, a sort Schwarzschild radius for complex, heritable behavior, aka life.
by greesil on 4/11/20, 7:43 PM