After yesterday's discussion about the use of Turing-Complete in exploitation papers, and realizing how commonly the other important term close to my heart, "weird machine", is misunderstood, I wrote a (rather unpolished) blog post about it. addxorrol.blogspot.com/2018/…
8
76
12
151
oh boy, for how many years did i want to write (about) this! another aspect many people miss is that TC computation requires the result on the *same* tape, not some subset of it. think about what it means for exploitation ;).
1
3
6
Same tape vs subset is a slightly different argument (someone would argue that that subset can define a different TM and claim TC on it [infiniteness aside, because the larger tape isn't infinite either]). Ppl just replace "cond branching + ability to change arb memory" with TC
2
1
there's no TC on a finite tape and finite TMs are not at all equal for that same reason. security boundaries are breached when one finite TM breaks out of its own finite tape. i.e., we don't call executing a simpe python script on the python interpreter a security breach per se.
1
1
2
define tape. security boundaries are breached when one finite TM breaks out of its own definition (not merely tape -- tape is just one part of the machine) into another (picture: bigger) finite TM. this differentiation is possible precisely because finite TMs are not at all equal
1
1
Replying to @xerub @halvarflake
tape is what the TM defines as the tape ;). in practice that's *all* storage the given TM has access to. and no, there's no other part of the machine, it's just the tape, everything else lives in some abstract space.

Oct 3, 2018 · 8:16 PM UTC

1
1
Replying to @paxteam @halvarflake
um, no. how does a TM work with no other part except the tape? bonus q: altering the TM transition function gives a new machine or not? can that be considered a security boundary breach?
2
1
you were talking about 'breaking out of its own definition' and a TM cannot do that, all it can read/write is the tape, that's all. now that's the maths, physical implementations don't quite follow this abstraction but then that's the whole point made by Halvar ;).
1
1
more replies