4 ms·

Branching with only MOV? How does that work? Is there no actual flow control but instead conditional manipulation (MOVs) of values?

vlovich123 3y ago
It depends on x86 addressing modes, but tldr lookup tables: > mov eax, [base + eax*4] You load 1 address if eax is 0 and a different on if it’s 1. There’s also a jump instruction so you can implement a conditional jump through mov. This is based on the Stephen Dolan paper: https://harrisonwl.github.io/assets/courses/malware/spring2017/papers/mov-is-turing-complete.pdf https://harrisonwl.github.io/assets/courses/malware/spring20...
acegopher 3y ago
There can be control flow. MOV an address into the right spot in the interrupt vector table then do a MOV that causes a fault that calls the right interrupt (such as a page fault).
- anyfoo 3y ago
  But now you're just employing another machine, which is not just made out of MOVs. The video describes in detail what actually happens. I encourage watching it, it's pretty genius, but the very short version is that you turn execution "off" for any code that is not in the "current" branch by switching over all MOVs to target a scratch space instead of their real targets, which means they still execute, but don't have an actual effect. Before each possible branch target, you check whether to turn execution "on", if it's the current one, i.e. making the instructions which are part of that branch affect "actual" memory again.
  - SpaghettiCthulu 3y ago
    It could be argued that the IVT is part of the MOV instruction seeing as the MOV instruction will directly use it for page faults (if I understand correctly).
- userbinator 3y ago
  Incidentally, the fault handling (presumably done in microcode) is itself Turing-complete: https://news.ycombinator.com/item?id=5261598 https://news.ycombinator.com/item?id=5261598
meindnoch 3y ago
X86 MOV is quite a beast.
- anyfoo 3y ago
  I'm not entirely through with the video yet, but the core of the idea doesn't need that much from the MOV instruction. No control flow happens in the traditional sense from the CPUs point of view, it's all just linear execution. Instead, there's an abstraction on top that implements control flow by making all code that is not part of the current branch ineffective (but still executed).
okanat 3y ago
"All problems in computer science can be solved by another level of indirection." - David Wheeler Basically the branching points are pointers where one writes a junk memory address or the actual one to operate on. Where to get the correct addresses? A lookup table, the addresses moved into registers. I think this could be a hack that's repeatable to a pretty good degree in many architectures. If you'd like to see how exactly, watch the presentation. The presentation links were already shared in discussion and searching movfuscator in Youtube also gets you the result.
- charcircuit 3y ago
  That trick doesn't work for writing an infinite loop.
LegionMammal978 3y ago
Others have described how branching works. But I'm not convinced it's possible to loop around to the beginning using only MOV instructions. movfuscator as currently implemented performs a CALL at the beginning to set up a signal handler, under the justification that it's not part of the real program and could be done with only MOVs, if the program were running in ring 0. (Even if you got rid of libc, it would still take an INT 0x80, SYSENTER, or SYSCALL to pass control to the kernel.) However, it seems to me like if you booted the processor directly into the program instead of having a bootloader and kernel to help you, then you'd run into a brick wall trying to move from 16-bit real mode to 32-bit protected mode, since doing so requires setting up a global descriptor table (GDT), and the only way I know of to do that is with the LGDT instruction. Unless I'm forgetting something?
- themoonisachees 3y ago
  What would be the roadblocks to simply running the program in 16-bit real mode? Like yes, obviously it isn't best practices but we're way past that.
ordu 3y ago
Hmm... you can try to move branches around. If you .code is writable of course. Though without 'rep movs' it could take a lot of code to move a branch.

vlovich123 3y ago

It depends on x86 addressing modes, but tldr lookup tables: > mov eax, [base + eax*4] You load 1 address if eax is 0 and a different on if it’s 1. There’s also a jump instruction so you can implement a conditional jump through mov. This is based on the Stephen Dolan paper: https://harrisonwl.github.io/assets/courses/malware/spring2017/papers/mov-is-turing-complete.pdf https://harrisonwl.github.io/assets/courses/malware/spring20...

acegopher 3y ago

There can be control flow. MOV an address into the right spot in the interrupt vector table then do a MOV that causes a fault that calls the right interrupt (such as a page fault).

anyfoo 3y ago
But now you're just employing another machine, which is not just made out of MOVs. The video describes in detail what actually happens. I encourage watching it, it's pretty genius, but the very short version is that you turn execution "off" for any code that is not in the "current" branch by switching over all MOVs to target a scratch space instead of their real targets, which means they still execute, but don't have an actual effect. Before each possible branch target, you check whether to turn execution "on", if it's the current one, i.e. making the instructions which are part of that branch affect "actual" memory again.
- SpaghettiCthulu 3y ago
  It could be argued that the IVT is part of the MOV instruction seeing as the MOV instruction will directly use it for page faults (if I understand correctly).
userbinator 3y ago
Incidentally, the fault handling (presumably done in microcode) is itself Turing-complete: https://news.ycombinator.com/item?id=5261598 https://news.ycombinator.com/item?id=5261598

meindnoch 3y ago

X86 MOV is quite a beast.

anyfoo 3y ago
I'm not entirely through with the video yet, but the core of the idea doesn't need that much from the MOV instruction. No control flow happens in the traditional sense from the CPUs point of view, it's all just linear execution. Instead, there's an abstraction on top that implements control flow by making all code that is not part of the current branch ineffective (but still executed).

okanat 3y ago

"All problems in computer science can be solved by another level of indirection." - David Wheeler Basically the branching points are pointers where one writes a junk memory address or the actual one to operate on. Where to get the correct addresses? A lookup table, the addresses moved into registers. I think this could be a hack that's repeatable to a pretty good degree in many architectures. If you'd like to see how exactly, watch the presentation. The presentation links were already shared in discussion and searching movfuscator in Youtube also gets you the result.

charcircuit 3y ago
That trick doesn't work for writing an infinite loop.

LegionMammal978 3y ago

Others have described how branching works. But I'm not convinced it's possible to loop around to the beginning using only MOV instructions. movfuscator as currently implemented performs a CALL at the beginning to set up a signal handler, under the justification that it's not part of the real program and could be done with only MOVs, if the program were running in ring 0. (Even if you got rid of libc, it would still take an INT 0x80, SYSENTER, or SYSCALL to pass control to the kernel.) However, it seems to me like if you booted the processor directly into the program instead of having a bootloader and kernel to help you, then you'd run into a brick wall trying to move from 16-bit real mode to 32-bit protected mode, since doing so requires setting up a global descriptor table (GDT), and the only way I know of to do that is with the LGDT instruction. Unless I'm forgetting something?

themoonisachees 3y ago
What would be the roadblocks to simply running the program in 16-bit real mode? Like yes, obviously it isn't best practices but we're way past that.

ordu 3y ago

Hmm... you can try to move branches around. If you .code is writable of course. Though without 'rep movs' it could take a lot of code to move a branch.