5 ms·
M/o/Vfuscator: A single instruction C compiler
- folmar 3y agoPrevious discussion: May 19, 2021 - https://news.ycombinator.com/item?id=27202801 https://news.ycombinator.com/item?id=27202801 (40 comments)
- musicale 3y ago"It is well-known that the x86 instruction set is baroque, overcomplicated, and redundantly redundant. We show just how much fluff it has by demonstrating that it remains Turing-complete when reduced to just one instruction." – MOV is Turing-complete, Stephen Dolan, 2013 discussion (2013) https://news.ycombinator.com/item?id=6309631 https://news.ycombinator.com/item?id=6309631 [While I concur that x86 MOV is impressively powerful, it is also well-known that simple NAND gates can be combined to compute arbitrary logic functions. There are also many simple single instruction/operation CPU designs.]
- loxias 3y ago> [While I concur that x86 MOV is impressively powerful, it is also well-known that simple NAND gates can be combined to compute arbitrary logic functions. There are also many simple single instruction/operation CPU designs.] Strong agree. My fav example in the same category as "all circuits can be made with just nand" and "all you need is x86 MOV" is the iota formal language. If the lambda calculus is too luxurious, and SKI combinators are too bloated, try using iota for all your language theory needs! No unnecessary concepts, or the two redundant operators of SKI! just one "simple" primitive: i := λf.((fλa.λb.λc.((ac)(bc)))λd.λe.d) There, now you're turning complete. ;-)
- tromp 3y agoiota just packages S and K together in a tuple. The simpler A = λx.λy.λz.x z(y (λ_.z)) suffices for Turing completeness. (tough) Challenge: derive S and K from A.
- loxias 3y ago1. <3 Thanks! This fact is now filed with the same neuron that fires for "wang tiles", "rule 110" and that new "hat" tile. 2. Does that simpler "A" combinator have a name, or something I can google for or find in mathworld and read more about? My interest, and estimate of ability, level is right at "not gonna do the work myself, but I'd enjoy following the proof/paper". ;-) 3. see: #1. I love learning about abstract and completely useless and impractical mathematical constructions, as a contrast to my day job making computers be useful. :)
- tromp 3y agoNo, it doesn't have a standard name. The "A" is just a placeholder name. It was only discovered last year as a shortest possible one-point basis, and hasn't been publicized much.
- loxias 3y agoI just realized you're likely the same person who made a more recent and compact binary encoding, for algorithmic information theory/Chaitin's constant purposes!! I'm humbled, and have been a fan of the field for a long time. :D I'm no mathematician, just most of my family and friends ;-) ~23 years ago I (and some other math major and grad student friends at college -- "my people") would get into great enjoyable late night chats about AIT. Mostly with me arguing "there's something cool/legit math here!" and them being healthily skeptical. I've always had a penchant for the computational and experimental discovery, of course my brother is the polar opposite. I'd be honored to collaborate on, well, anything, should you ever need the skills (pro bono, of course) of an professional, experienced, HPC/C++ scientific programmer who knows a bit of math as well. ;-)
- tromp 3y agoYep, that's me. I got interested in AIT when one of the luminaries of the field taught a course on it in University and I went on to do a PhD under him. Would have been happy to join in your late night chats:-) As you can see on my home page, I love to do research related programming myself, but also welcome other people contributing with their expertise.
- nielsbot 3y agoBranching with only MOV? How does that work? Is there no actual flow control but instead conditional manipulation (MOVs) of values?
- vlovich123 3y agoIt 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 agoThere 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 agoBut 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 agoIt 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).
- 3y ago
- edgyquant 3y agoAs with the last time, the side by side comparison with GCC, especially the control flow, is hilarious.
- colatkinson 3y agoFor anyone else who immediately thought, "I've gotta try that!" and hit compilation errors: there appears to be a more maintained fork at [0]. And if you're on a 64-bit system, you'll want to make sure it finds the 32-bit libc and libm binaries (see [1]). On Arch, the following worked for me: ./build/movcc -L/usr/lib32 test.c [0]: https://github.com/xoreaxeaxeax/movfuscator https://github.com/xoreaxeaxeax/movfuscator [1]: https://github.com/xoreaxeaxeax/movfuscator/issues/39 https://github.com/xoreaxeaxeax/movfuscator/issues/39
- azalemeth 3y agoIf you haven't seen it, the original conference talk on the Movfuscator is excellent – https://www.youtube.com/watch?v=R7EEoWg6Ekk https://www.youtube.com/watch?v=R7EEoWg6Ekk – it goes through it in detail and describes how version 0.0 had Brainfuck as a totally legitimately valid intermediate language ;-)
- nerpderp82 3y agoI want Christopher Domas for an older brother, in the 90s.
- thegeekpirate 3y agoHe's my favorite speaker (watch all his talks... they're worth it!), but he seems to have gone MIA (possibly after joining Intel? I don't know the timeline), much to my dismay.
- Mr_Twinkles 3y agoYes, you got the timeline right, he went MIA after joining Intel. Turns out a great way to stop vulnerability disclosures is to protect them behind an NDA, plus for any that are found you can give first dibs to all of the 3-letter agencies that are shoveling money your way.
- thegeekpirate 3y agoMakes sense. Although unfortunate for us, I'm happy for him. Appreciate the reply!
- bombcar 3y agohttps://github.com/xoreaxeaxeax/movfuscator/blob/6342ae76b580c174eb35e612ec9fc0013be7859d/validation/doom/README.md https://github.com/xoreaxeaxeax/movfuscator/blob/6342ae76b58... Related. > The mov-only DOOM renders approximately one frame every 7 hours, so playing this version requires somewhat increased patience.