alt.hn

1/17/2025 at 7:36:37 PM

Show HN: Compile C to Not Gates

 https://github.com/tomhea/c2fj

by tomhee

1/17/2025 at 8:14:08 PM

Reminds me of movfuscator [1]. This can compile programs to movs and only movs.

[1] https://github.com/Battelle/movfuscator

by bangaladore

1/17/2025 at 9:57:53 PM

Battelle is great. They also created some software called Cantor Dust [1] that turns files into images to allow humans to easily spot obfuscated data or files.

The sad thing about this kind of work, because I love it, is that to get paid to do it you need clearances and polygraphs and periodic reinvestigations/continuous monitoring and all sorts of things that I find unpleasant.

[1] https://github.com/Battelle/cantordust

by LPisGood

1/17/2025 at 11:12:42 PM

I'm not sure what you mean but I was a security researcher for a large company for a bit and required none of that. I was required to work airgapped at home, however.

by mmastrac

1/17/2025 at 11:14:52 PM

Really? You were doing offensive security work not for a government (/contractor)? What sorts companies, aside from some enterprise pen testers, employ these roles?

by LPisGood

1/18/2025 at 2:00:45 AM

The tools you’re talking about are not exclusive to offensive security. They’re plenty useful for malware analysis and other reverse engineering tasks.

by saagarjha

1/17/2025 at 11:20:34 PM

Email is in my profile -- happy to clarify/share some very rough details if you'd like.

by mmastrac

1/17/2025 at 11:51:09 PM

Agreed that is a fine piece of work. But the author is Chris Domas. Which is plain from the repo readme, but it’d be clearer to link to his repo.

by beng-nl

1/18/2025 at 1:37:07 AM

I was originally going to link their repo [1]. But I saw it was forked from the one I linked so I just gave that one instead.

[1] https://github.com/xoreaxeaxeax/movfuscator

by bangaladore

1/18/2025 at 2:01:38 AM

Chris used to (maybe still does?) work at Batelle.

by saagarjha

1/18/2025 at 5:48:34 AM

He went MIA after joining Intel, so I'm assuming he's still there.

by thegeekpirate

1/17/2025 at 8:51:39 PM

Am I right in deducing that this language gets its power from self-modifying code? I.e. flipping bits within addresses of the opcodes of the running program?

by tromp

1/17/2025 at 9:08:46 PM

You are indeed right

by tomhee

1/17/2025 at 9:18:32 PM

I would have expected the language documentation to focus more on this observation and to explain for instance how self modification is used to implement while loops. But I don't even see the term mentioned anywhere?!

by tromp

1/19/2025 at 7:45:13 AM

This was actually a not uncommon approach to implementing loops in earliest mainfraims.

by int_19h

1/19/2025 at 5:58:05 PM

Do you have any article that I can read about it? Sounds interesting!

by tomhee

1/17/2025 at 8:12:10 PM

There is also a brainfuck to flipjump compiler: https://github.com/tomhea/bf2fj

by tomhee

1/17/2025 at 10:03:59 PM

Ah, the convenience of brainfuck with the performance of flipjump. Excellent.

by david-gpu

1/17/2025 at 9:17:01 PM

By the way, as a challenge, try how you can program an "If" statement in Flipjump.

by tomhee

1/18/2025 at 12:57:05 PM

I wondered this as well.

Thinking about it, if all you have is "invert some (N>1?) bits somewhere and jump to somewhere" .. I could see maybe it might work if you use self modifying code and there's really a 2nd instruction that is a no-op? Seems like it might work more like a cellular automata?

Of course, one could just go look at the documentation, but where's the fun in that?

by greenbit

1/19/2025 at 8:39:31 AM

You don't need a no-op; you can always just flip a bit you don't care about (e.g. reserve a word just for that) and then jump to next instruction.

by int_19h

1/22/2025 at 6:26:53 PM

Would like to know the answer. Thx.

by alok-g

1/23/2025 at 8:49:44 PM

Alright - https://github.com/tomhea/flip-jump/wiki/Learn-FlipJump#memo...

by tomhee

1/25/2025 at 1:34:45 PM

To the best I now understand, the jump address is allowed to be an expression using a specified bit variable. That would mean that the language has means to compile an expression for evaluation at the run time. If I am understanding correctly, then the power of flip jump is coming from those expressions, not the base flipjump instruction itself.

If I haven't understood this right, then I still do not follow how if statement works with flipjump.

by alok-g

1/25/2025 at 10:07:53 PM

@alok-g I'll be happy to explain - You don't understand it correctly. The flipjump assembly syntax does allow relating to an address with offsets/more advanced stuff, but that doesn't add anything to.the language. It' just adds comfort to the programmer - it's basically like adding labels to an assembly language - it's possible to write assembly without them, just much less convenient.

The power of flipjump results in self modifying code. If I jump to a address that have the [flip 0, jump 0x1000], then I'll get to 0x1000 afterwards, right? But if I flip some specific bit in this instruction before jumping to it, it will become [flip 0, jump 0x1080]. You can call this instruction "memory bit", and the part of jumping to it and resulting in one of two possible addresses 0x1000/0x1040 based on a specific bit in it - "read the memory bit". The action is reading as you get to different place based on the value stored in this instruction. This "read" can also be seen as an "if". How you write then? For example writing "1" whould be doing a "read", and in the "read 0" case - do a flip to this address, and in the "read 1" case don't flip this memory address bit.

by tomhee

1/26/2025 at 10:21:53 PM

I could follow the part you have explained. Thanks still though.

>> But if I flip some specific bit in this instruction before jumping to it

Isn't the 'if' really happening in the above phrase? The rest of it is a modified jump address based on the above 'if' and just jumps to the modified address.

Now if I understand this correctly, how to do the above 'if', i.e., flip the address bit or not based on some condition?

May be it would begin from some bit read from IO which modifies an address. I saw that memory-mapped IO is used.

by alok-g

1/17/2025 at 10:23:17 PM

Ah interesting.. wonder if you can model this with a recursively expanded algebraic expression. I've been thinking lately along similar lines about polynomials that encode pushdown automata, so this is cool to see.

by pizza

1/17/2025 at 10:27:37 PM

If you have an answer I'd be happy to hear it!

by tomhee

1/18/2025 at 3:17:16 PM

Wouldn't it be better to call it "compile C to Linux or BSD"?

I kid, I kid.

by Firehawke

1/18/2025 at 10:48:44 AM

It always amazes me that this is possible (to some extend anyway, I mean, the base layer is binary so obviously simpler higher-end CPU instructions are possible!)

Is there any potential performance win in this? What I mean is; since this general direction could, in principle if not in practise, enable the targeting of say, the 5-10 most efficient CPU instructions rather than attempting to use the whole surface area... would this potentially be a win?

by dingdingdang

1/18/2025 at 8:41:28 AM

I was expecting to see a way to translate hello_world.c into an electronic schematic full of NAND elements, kind of Mealy machine.

by eimrine

1/17/2025 at 11:57:14 PM

Looking forward to the poor security researcher who gets to reverse engineer some malware sample they compiles this into for obfuscation... Its going to be an interesting blog post.

by tonetegeatinst

1/17/2025 at 10:08:51 PM

I wonder if someone has already made a Reverse Engineering CTF challenge for this concept.

by jkrshnmenon

1/17/2025 at 10:18:42 PM

There actually was one with subleq: https://www.google.com/amp/s/blog.attify.com/flare-4-ctf-wri...

by tomhee

1/17/2025 at 11:16:30 PM

I would also be very curious to see if it's possible to make a decompiler for this type of obfuscated program.

by jkrshnmenon

1/18/2025 at 2:04:01 AM

Typically these obfuscators are applied in an automated fashion so yes.

by saagarjha

1/18/2025 at 5:32:00 AM

DEFCON Quals challenge incoming.

by jkrshnmenon

1/18/2025 at 7:07:05 AM

Please no we’ve already suffered enough :(

by saagarjha

1/17/2025 at 11:54:54 PM

I read it as reverse engineering WTF challenge... cool stuff though, seriously.

by og2023

1/17/2025 at 9:22:04 PM

Maxim (now owned by Analog) actually manufactures a single-instruction processor series, called MAXQ. It uses a single move instruction, with a flag for literals, and a transport triggered architecture.

by dlcarrier

1/18/2025 at 7:00:00 AM

What is the intended use case for such a processor?

by Zamiel_Snawley

1/19/2025 at 6:34:42 AM

They are embedded microcontrollers, which run real-time deterministic tasks, with tens to hundreds of MIPS on fixed-point tasks. These are the kinds of microcontrollers used in products like household appliances or control systems.

by dlcarrier

1/18/2025 at 2:20:13 PM

Is the family of circuits using just NOT gates actually universal? Or is "flip" and "jump" secretly using a lot of other gates.

by jvanderbot

1/18/2025 at 2:56:34 PM

The power is within the self modification of the code. The jump might be implemented by a multiplexer, though it can be implemented in other ways too.

by tomhee

1/18/2025 at 8:10:06 PM

A CNOT is universal (transistor effectively) I don't think a NOT is universal.

I'm sure you can self modify your code so it executes only using XOR (bit flips), which is a CNOT, but I do not think this could be compiled down to an FPGA using only a billion not gates.

Actually I just convinced myself you can make an AND from three NOT gates if you can tie outputs together to get OR, so I believe you now. Sorry for the diversion! (Though I still dont see how bit flips and jumps directly can be built into a circuit, I know AND and NOT are universal so it's all good).

by jvanderbot

1/18/2025 at 12:56:52 PM

hey this could actually be pretty nice if we can convert flipjump into sqlite native instructions like how it is possible for brainfuck , then you are on to something huge!

You would create although highly inefficient , after many years , maybe the first , language like those lisps where you could store data in sqlite and run it fromt there (but with C)

by Imustaskforhelp

1/18/2025 at 1:00:28 PM

That's cool! And that's possible. Do you have any more data to read about it?

by tomhee

1/18/2025 at 7:15:50 PM

I really hope that you try this , this might be game changing !

by Imustaskforhelp

1/18/2025 at 2:48:20 PM

Did I miss something? I thought NAND was you're 'universal gate' ?

by Nevermnd

1/17/2025 at 9:32:31 PM

Id appreciate more explanations from the power of combined bitflip & goto

by artemonster

1/17/2025 at 8:48:54 PM

How is a jump realized by Not Gates?

by platz

1/17/2025 at 9:15:29 PM

I dont think that the jump can be realized by NOT gates, but it's essentially "where to find the next NOT command". The jump is indeed a crucial part of the language, as it allows going back, and especially to make self-modifying code.

by tomhee

1/17/2025 at 9:14:56 PM

I'm guessing by not jumping into a terminating/ halting NOOP.

The logic is within the branching.

by Jerrrry

1/17/2025 at 10:01:23 PM

AND, OR, NOT - pick 2

by jumploops

1/17/2025 at 10:22:00 PM

NOR - pick 1

by sroussey

1/18/2025 at 3:12:11 AM

Or equivalently NAND, leading to the usual recommendation about NAND to Tetris - https://www.nand2tetris.org/

by falcor84

1/17/2025 at 7:57:18 PM

Looks like we banned you and this domain because of the egregious vote manipulation and bogus comments at https://news.ycombinator.com/item?id=34856792.

That was a long time ago, though, and the project is interesting enough, so I'm going to assume you've learned your lesson and unban you. Please stop using multiple accounts for this though!

by dang

1/17/2025 at 8:10:57 PM

Thanks man, I appreciate it.

by tomhee

1/17/2025 at 8:09:28 PM

Dang, I have to know what triggered you to say this. It’s not the same user account so you would have had to have recognized the URL and written based on that.

Do you keep notes on each astroturfed submission and auto-trigger reposts to notify yourself? Or did you just happen to recognize this? 20 minutes from his post to your comment is absurdly good moderation.

by jimbob45

1/17/2025 at 8:24:24 PM

https://news.ycombinator.com/item?id=42742462 was on the front page. We got an email suggesting that the URL should be https://github.com/tomhea/c2fj instead of https://github.com/tomhea/flip-jump. That made sense, except it turned out that github.com/tomhea was banned. That seemed odd because we don't normally ban github domains, so I looked at the history https://news.ycombinator.com/from?site=github.com%2Ftomhea (most of which will only be visible to users who have 'showdead' set to 'yes' in their profile), and it was pretty easy to see that https://news.ycombinator.com/item?id=34856792 was, let's call it, the original sin in this chain of woe. It was also pretty obvious that the other submitting accounts were all related. Since the project itself is interesting I figured the best thing to do was give the submitter a second chance, so I picked the earlier post from today (the OP) and swapped it out for the other one (42742462).

I hope that answers your question!

by dang

1/17/2025 at 10:01:18 PM

You sir, are amazing. Thank you for being so utterly transparent.

by doormatt

1/17/2025 at 8:15:16 PM

[dead]

by chicken_grease

1/17/2025 at 10:50:12 PM

[dead]

by jpcookie

1/18/2025 at 7:00:36 AM

[flagged]

by kuringganteng