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).
It seems like folks are very quick to confuse the expressiveness of a machine with the expressiveness of analyzing programs for that machine; usually, a program is far harder to analyze than to run.
I think that a better way to view the post's author's point is by unpredictability. Given a short program in a weak setting, we can not only predict what the program will do, but what the program cannot do, usually because it is too short or too simple. In a Turing-complete setting, though, there are short programs with very unpredictable behavior.
http://www.haskellforall.com/2020/01/why-dhall-advertises-ab...
My comment:
That is, it’s fine (and often necessary) for a config language to be Turing complete. (This doesn’t mean it needs global variables or mutation, etc.)
The real issue is side effects (I/O), which is not technically related to Turing-completeness.
https://lobste.rs/s/gcfdnn/why_dhall_advertises_absence_turi...
And for some bizarre reason a couple people replying keep insisting that this serves some purpose, even though the post basically admits it's the wrong issue, but they're doing it as "signaling mechanism" (i.e. marketing to people who hold a misconception about computer science.)
But that's not even the end of it -- as mentioned:
not only is the messaging focused on an irrelevant thing, but the language design is too! It would almost make more sense if the messaging were the only odd thing.
Now I could claim on the contrary that whenever you're using "security" and "non-Turing completeness" in that way together, the only thing you're actually signaling is that you don't know WTF you're talking about.
In many cases it is the final step.
If you're trying to secure something that lacks any good reason to access the internet, it shouldn't be able to. And yet so many things like that still have internet access.
This creates a problem when you have a program which is only supposed to process some sensitive data and not export it off to the attacker, because as soon as the attacker can execute their own code, the process already had access to the sensitive data and to the internet. Or there is no sensitive data but the process already had access to the internet, so now the attacker is using your hardware to mine cryptocurrency or route their network traffic through your IP address.
We could stop giving network access to processes that otherwise shouldn't need it, but that requires overcoming the incumbent economic forces that use network access for telemetry and advertising. So there are a lot of people hoping that making things that aren't Turing-complete is easy. But it turns out to be pretty hard. So we may have to start pushing back against those economic forces.
That's where your thinking goes wrong. TC does not mean that the program can take over the host process control flow.
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.
!!!
!!!!!!!!!!!
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.
My research/tinkering so far is https://github.com/moreati/pickle-fuzz
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.
"...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."
https://www.gwern.net/Turing-complete#how-many-computers-are...
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, ...
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.
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?
Simplifying, to have a TC programming language you need two things: RAM and the ability to decide your next state based on the memory contents.
I’m probably just looking for Lisp, really. It’s easy to implement and usable enough.
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.
The answer is not always, but sometimes: discovering unintended states or transitions in the execution contract of a program is a common building block for exploits. However, proving that the execution contract of a program can be coerced into representing computations in a TC language doesn't necessarily prove that you can do anything interesting.
Complex formats like PDF are a good example of this: you can probably contrive a PDF input such that the parser's state represents a minimal (and TC) language while interpreting it (e.g. a language with a few mathematical operators and a "store" primitive), but that doesn't magically get you network access or arbitrary memory read/writes. You need to show that said language, when programmed in, can affect the overall execution contract in a way that violates high-level assumptions.
Some resources (FD: my company's) on the subject:
* https://blog.trailofbits.com/2019/11/01/two-new-tools-that-t...
* https://blog.trailofbits.com/2018/10/26/the-good-the-bad-and...
One, can certain input data cause a large usage of computing resources (processing time or memory)? Non-TC mechanisms have repeatedly failed this test: ZIP bombs and XML entity bombs are notorious examples. On the other hand, you can easily put a resource cap on an interpreter of a theoretically TC language and be safe.
Two, can the untrusted code access resources that it shouldn’t (memory, files, sockets)? That’s mostly a quality of implementation issue, not one of Turing completeness. JavaScript interpreters have certainly been vulnerable to various exploits, but so have JPEG decoders. I don’t think TC is the issue here. (However, this is complicated a bit by side-channel attacks à la Spectre. I’m not sure how TC factors into those.)
In summary, I’m not convinced that Turing completeness is all that relevant for security. Am I wrong here?
