4 ms·

That machine you have, because can do general computations (Turing Complete) can be attacked on that message until its stack dumps and you have access to perfor

That machine you have, because can do general computations (Turing Complete) can be attacked on that message until its stack dumps and you have access to perform general computations on the underlying system where that program was running.

drdeca 10y ago
Its stack? Just because it is Turing complete does not imply that it uses a stack. Consider: look_for := "some string"; n := len(look_for); send_out := "other string"; i := 0; while(true){ c=getInputChar(); if(c==None){ i=0; continue; } if(c==look_for[i]) { i+=1; continue; } if(i==n){ output(send_out); i=0; continue; } //else i=0; continue; } (Pseudo code. No specific language intended.) I see no reason that the above would require a stack (provided that the input and output features are hardware built ins rather than function calls. Just reading or writing from/to a pair of registers.) I see no way that such a program could be exploited (short of flaws in the machine). Causing the stack to dump wouldn't work, as it has no stack. It just cycles through a small number of states based on input. Now, some other program which is much more complicated could be written for the same machine, as the machine is Turing complete, but this particular program would not be vulnerable.
- sokoloff 10y ago
  If I send that code "some some string" or "ssome string", it fails to respond with "other string" due to a bug. If I send it "sssome string", it does work. (depending on how you interpret the // before the else; if that comments out the else, then brute forcing the input by cycling all characters on the input will eventually cause output.) So, there's a bug and now a maintainer has to go in and patch the bug, which may introduce a security flaw (either in the coding or the release deployment process). You also have the exposure of whatever getInputChar() and output() do internally. I'm not arguing there is an exploit just because of using Turing complete system, but observing that even simple systems tend to have bugs and get maintenance over time.
  - drdeca 10y ago
    I did mean that as a comment, yes. I put that as a comment because in either of the other cases it already has a continue statement, so it wouldn't get to after the else comment unless the other conditions weren't met. Also, you are right that I made a mistake, in that I forgot to check if a wrong next character was a correct first character and similar problems. Oops! Ok. What I was trying to argue was that it is possible for a program in a Turing complete system to have no exploits, not that it is easy to write a program like that. I thought it was being claimed that it is completely impossible to write a program with no exploits for a Turing complete machine, and I was trying to argue against that.
    - sokoloff 10y ago
      You're right and you communicated that point well. I took the thread to a slight diversion given the premise that it's easy to write bugs in even short, simple code snippets, and that those bugs then introduce the requirement for maintenance, which brings in further opportunities for exploits to be introduced.
- sebastianconcpt 10y ago
  Suppose the program you gave as example doesn't have a stack. Does the TCP/IP code of the underlying operative system that would run it have one? If so, then your unexploitable program can be exploited without it even noticing, correct?
  - drdeca 10y ago
    I was imagining the code (translated to some machine code version) being running on hardware. Of course, that isn't actually necessary for the argument. It doesn't matter whether the program is running on hardware directly or through some OS, so long as the thing running it is not broken. When one talks about a Turing machine running a program, one generally does not model the machine as occasionally not working as specified. Similarly here, the assumption is that the implementing thing, whether it be an OS or a circuit, works according to the spec that the program for it is based around.
    - sebastianconcpt 10y ago
      I see your point. Well even IBM Simon was running Datalight ROM-DOS. I can't imagine a device as complex as a smartphone, even with a fraction of its features running all directly on the metal, can you? https://en.wikipedia.org/wiki/Datalight#ROM-DOS https://en.wikipedia.org/wiki/Datalight#ROM-DOS
schoen 10y ago
> can be attacked on that message until its stack dumps This sounds like an attempt to combine intuitions about the pumping lemma with memory corruption vulnerabilities: that "any system" must have some inputs that are "too much" for it to interpret correctly (for many programs written in C, that could be a single input string that's "too long"). https://en.wikipedia.org/wiki/Pumping_lemma https://en.wikipedia.org/wiki/Pumping_lemma https://en.wikipedia.org/wiki/Buffer_overflow https://en.wikipedia.org/wiki/Buffer_overflow These intuitions are founded on good reasons because every computing system has different kinds of limitations, and some kinds of distinctions that it can't make correctly, and some kinds of failure modes if it's expected to make arbitrary distinctions. But there are ways out: * If we narrow the definition of the task that the system has to do, it may be possible for the system to do it perfectly, and it may even be possible to make a formal proof that the system performs that task perfectly, even though there are other more general tasks that it doesn't perform, or performs imperfectly. * If we allow the system to "give up" or indicate that it refuses or fails to answer certain questions, then it doesn't have to be "wrong" or exhibit wrong or unpredictable behavior. It can just say "sorry, not sure", which may be annoying but isn't a mistake and isn't necessarily a security vulnerability. (Maybe this is akin to those movie robots saying "does not compute" all the time.) Within these frameworks, a kind of perfection, or at least a kind of correctness, is possible for many computing tasks -- including some that involve Turing-completeness, either as a property of the environment they're implemented in or as a property of the machine they implement.

drdeca 10y ago

Its stack? Just because it is Turing complete does not imply that it uses a stack. Consider: look_for := "some string"; n := len(look_for); send_out := "other string"; i := 0; while(true){ c=getInputChar(); if(c==None){ i=0; continue; } if(c==look_for[i]) { i+=1; continue; } if(i==n){ output(send_out); i=0; continue; } //else i=0; continue; } (Pseudo code. No specific language intended.) I see no reason that the above would require a stack (provided that the input and output features are hardware built ins rather than function calls. Just reading or writing from/to a pair of registers.) I see no way that such a program could be exploited (short of flaws in the machine). Causing the stack to dump wouldn't work, as it has no stack. It just cycles through a small number of states based on input. Now, some other program which is much more complicated could be written for the same machine, as the machine is Turing complete, but this particular program would not be vulnerable.

sokoloff 10y ago
If I send that code "some some string" or "ssome string", it fails to respond with "other string" due to a bug. If I send it "sssome string", it does work. (depending on how you interpret the // before the else; if that comments out the else, then brute forcing the input by cycling all characters on the input will eventually cause output.) So, there's a bug and now a maintainer has to go in and patch the bug, which may introduce a security flaw (either in the coding or the release deployment process). You also have the exposure of whatever getInputChar() and output() do internally. I'm not arguing there is an exploit just because of using Turing complete system, but observing that even simple systems tend to have bugs and get maintenance over time.
- drdeca 10y ago
  I did mean that as a comment, yes. I put that as a comment because in either of the other cases it already has a continue statement, so it wouldn't get to after the else comment unless the other conditions weren't met. Also, you are right that I made a mistake, in that I forgot to check if a wrong next character was a correct first character and similar problems. Oops! Ok. What I was trying to argue was that it is possible for a program in a Turing complete system to have no exploits, not that it is easy to write a program like that. I thought it was being claimed that it is completely impossible to write a program with no exploits for a Turing complete machine, and I was trying to argue against that.
  - sokoloff 10y ago
    You're right and you communicated that point well. I took the thread to a slight diversion given the premise that it's easy to write bugs in even short, simple code snippets, and that those bugs then introduce the requirement for maintenance, which brings in further opportunities for exploits to be introduced.
sebastianconcpt 10y ago
Suppose the program you gave as example doesn't have a stack. Does the TCP/IP code of the underlying operative system that would run it have one? If so, then your unexploitable program can be exploited without it even noticing, correct?
- drdeca 10y ago
  I was imagining the code (translated to some machine code version) being running on hardware. Of course, that isn't actually necessary for the argument. It doesn't matter whether the program is running on hardware directly or through some OS, so long as the thing running it is not broken. When one talks about a Turing machine running a program, one generally does not model the machine as occasionally not working as specified. Similarly here, the assumption is that the implementing thing, whether it be an OS or a circuit, works according to the spec that the program for it is based around.
  - sebastianconcpt 10y ago
    I see your point. Well even IBM Simon was running Datalight ROM-DOS. I can't imagine a device as complex as a smartphone, even with a fraction of its features running all directly on the metal, can you? https://en.wikipedia.org/wiki/Datalight#ROM-DOS https://en.wikipedia.org/wiki/Datalight#ROM-DOS

schoen 10y ago

> can be attacked on that message until its stack dumps This sounds like an attempt to combine intuitions about the pumping lemma with memory corruption vulnerabilities: that "any system" must have some inputs that are "too much" for it to interpret correctly (for many programs written in C, that could be a single input string that's "too long"). https://en.wikipedia.org/wiki/Pumping_lemma https://en.wikipedia.org/wiki/Pumping_lemma https://en.wikipedia.org/wiki/Buffer_overflow https://en.wikipedia.org/wiki/Buffer_overflow These intuitions are founded on good reasons because every computing system has different kinds of limitations, and some kinds of distinctions that it can't make correctly, and some kinds of failure modes if it's expected to make arbitrary distinctions. But there are ways out: * If we narrow the definition of the task that the system has to do, it may be possible for the system to do it perfectly, and it may even be possible to make a formal proof that the system performs that task perfectly, even though there are other more general tasks that it doesn't perform, or performs imperfectly. * If we allow the system to "give up" or indicate that it refuses or fails to answer certain questions, then it doesn't have to be "wrong" or exhibit wrong or unpredictable behavior. It can just say "sorry, not sure", which may be annoying but isn't a mistake and isn't necessarily a security vulnerability. (Maybe this is akin to those movie robots saying "does not compute" all the time.) Within these frameworks, a kind of perfection, or at least a kind of correctness, is possible for many computing tasks -- including some that involve Turing-completeness, either as a property of the environment they're implemented in or as a property of the machine they implement.