5 ms·

There are problems well beyond infinite compile times and infinite runtimes with a Turing-complete sublanguage hidden in something as innocuous looking as the t

There are problems well beyond infinite compile times and infinite runtimes with a Turing-complete sublanguage hidden in something as innocuous looking as the type system. Arbitrary code execution is the holy grail of exploits. If the type system is Turing complete or even nearly so you can encode arbitrary behavior into the types without using any of the language's mainstream operative syntax. One could put an entire subsystem of the running program into what looks like descriptive, conscriptive statements about the data the operative syntax is to use. This is ripe for hiding a source-level trojan in a part of the code that needs little to no support from the rest of the program. When you're first looking at code from others, is your first instinct before compiling it to check deeply in the types defined to make sure there's nothing untoward going on semantically? Looping forever is a very simple DoS or a very complex mistake. It would also be very simple to end the compilation run and investigate. Intentionally obfuscated malicious code would likely be able to pass unnoticed much longer and do much more damage. The halting problem, realistically, is a problem but is the least of your problems here. It's already quite easy to write a non-halting piece of code on purpose and it's possible accidentally. The big problem is the unexpected computational power of this sort of thing being abused, not that it's accidentally going to take forever to compile. Nobody's going to die of old age watching an uninterrupted compilation.

deleted 9y ago
[deleted]
deleted 9y ago
[deleted]
klodolph 9y ago
> There are problems well beyond infinite compile times and infinite runtimes with a Turing-complete sublanguage hidden in something as innocuous looking as the type system. This whole argument is nothing more than equivocation: the phrase "arbitrary code execution" means one thing in the security sense but it means something completely different when you are talking about theory of computation. A Turing machine can execute "arbitrary code" in the sense that it can evaluate any computation. That does not mean that it can effect arbitrary changes to a host computer emulating a Turing machine. That's why sandboxing works. Try writing an HTTP server with a Turing machine: you can't, because Turing machines have no facility for networking. Similarly, just because a type system lets you execute arbitrary code doesn't mean that you can write an exploit in that code, you would need some exploitable endpoint accessible from the type system. Or in short, just because you can simulate a Turing machine on someone else's computer doesn't mean you can take over their computer. And yes, nobody's going to die waiting for compilation, but if you can DoS somebody's CI server by making a change to an upstream module which makes compilation take forever, maybe your victim will be pretty unhappy about that.
- cestith 9y ago
  You have yourself one heck of a strawman there. Never did I say it enabled execution of arbitrary code injected from outside. What I said was that if you are able to hide arbitrary computation of an obfuscated form into what looks like a bunch of innocuous type definitions then run a program that takes over from that point, you can potentially hide malicious code in the type declarations before the program proper even begins to run. A Turing complete type system can theoretically change the initial state the rest of the compiled code starts under. Picture this: you clone a repo. There's a file that contains operative code in some paradigm (non-OO imperative, OO imperative, non-OO functional, OO functional, logic, whatever). There's another file that's just types used by that first file. How much attention do you honestly pay to the types before looking at the operative code and then compiling and running it? Now, let's assume someone's found a bit of a bug in your compiler that lets this Turing-machine equivalent type system change the memory addresses of some structures or fill certain parts of memory with machine language. After all, you've not written your compiler to check everything a Turing complete language might do. Then the operative code you're counting on, that you've assumed starts with a clean slate other than the types assumed to be straightforwardly declared, copies that memory somewhere, or seeds a state machine or eval with it. A Turing complete language means you can do anything any other Turing complete language can do. And having a Turing complete type system without making that clear to language users potentially means it can be obfuscated and effectively hidden. In TypeScript we're talking about a Turing complete subsystem (the type system) that feeds into a Turing complete system (the rest of the language) that translates into another Turing complete system (JavaScript), that gets compiled down to another Turing complete system (the JIT code for the VM). In all that complexity there be dragons. You might not be familiar with the concept of multi-layer attacks or think they're unlikely to work, but that doesn't mean they don't exist or aren't used in the field.

deleted 9y ago

[deleted]

deleted 9y ago

[deleted]

klodolph 9y ago

> There are problems well beyond infinite compile times and infinite runtimes with a Turing-complete sublanguage hidden in something as innocuous looking as the type system. This whole argument is nothing more than equivocation: the phrase "arbitrary code execution" means one thing in the security sense but it means something completely different when you are talking about theory of computation. A Turing machine can execute "arbitrary code" in the sense that it can evaluate any computation. That does not mean that it can effect arbitrary changes to a host computer emulating a Turing machine. That's why sandboxing works. Try writing an HTTP server with a Turing machine: you can't, because Turing machines have no facility for networking. Similarly, just because a type system lets you execute arbitrary code doesn't mean that you can write an exploit in that code, you would need some exploitable endpoint accessible from the type system. Or in short, just because you can simulate a Turing machine on someone else's computer doesn't mean you can take over their computer. And yes, nobody's going to die waiting for compilation, but if you can DoS somebody's CI server by making a change to an upstream module which makes compilation take forever, maybe your victim will be pretty unhappy about that.

cestith 9y ago
You have yourself one heck of a strawman there. Never did I say it enabled execution of arbitrary code injected from outside. What I said was that if you are able to hide arbitrary computation of an obfuscated form into what looks like a bunch of innocuous type definitions then run a program that takes over from that point, you can potentially hide malicious code in the type declarations before the program proper even begins to run. A Turing complete type system can theoretically change the initial state the rest of the compiled code starts under. Picture this: you clone a repo. There's a file that contains operative code in some paradigm (non-OO imperative, OO imperative, non-OO functional, OO functional, logic, whatever). There's another file that's just types used by that first file. How much attention do you honestly pay to the types before looking at the operative code and then compiling and running it? Now, let's assume someone's found a bit of a bug in your compiler that lets this Turing-machine equivalent type system change the memory addresses of some structures or fill certain parts of memory with machine language. After all, you've not written your compiler to check everything a Turing complete language might do. Then the operative code you're counting on, that you've assumed starts with a clean slate other than the types assumed to be straightforwardly declared, copies that memory somewhere, or seeds a state machine or eval with it. A Turing complete language means you can do anything any other Turing complete language can do. And having a Turing complete type system without making that clear to language users potentially means it can be obfuscated and effectively hidden. In TypeScript we're talking about a Turing complete subsystem (the type system) that feeds into a Turing complete system (the rest of the language) that translates into another Turing complete system (JavaScript), that gets compiled down to another Turing complete system (the JIT code for the VM). In all that complexity there be dragons. You might not be familiar with the concept of multi-layer attacks or think they're unlikely to work, but that doesn't mean they don't exist or aren't used in the field.