I forgot to address a few more points:



It is exactly a type-safety problem.

In 6502 code, you can take a value and use it as a code pointer and jump to it.

In Java bytecode, you cannot take a numeric value and convert it to a code pointer and jump to it because of type verification performed by the bytecode verifier.

Pointer analysis on Java bytecode is much easier because pointer arithmetic is not allowed.
Pointer analysis on the 6502 is much more difficult because pointer arithmetic is allowed.

Two different cases.



The problem is that you're equating this to a constant propagation problem in a compiler.
The big picture view is they are not the same problem.

In a compiler, cprop starts with working code, and tries to improve it.
If cprop fails, a naive code sequence is generated.
The output code still works even if cprop fails.

In a 6502 static recompiler, if the target of a JMP (x) instruction cannot be identified, the fallback
case is to analyze 512k entry points, which is probably not practical. The fallback case is basically not usable.
So if the target of JMP (x) is not identifiable, then correct output code cannot be generated.

If you can't identify the target of a JMP (x) instruction reliably, then you will wind up with a static 6502 compiler which only works on simple NES games maybe like Duck Hunt, and crashes on all other NES games. That's not very useful.

Toshi

Two more problem cases I can think of with static recompilation of 6502 machine code from NES ROMs:

1) RTS

On the Apple II it was very common to write code such as this:

JSR PRINT
.ascii "blah blah blah blah", 0
...

Basically the PRINT routine would fetch the return value from the stack, and print the bytes until a zero or high-bit set characte or some other end-of-string marker, then push the pointer back onto the stack and execute RTS.

This is hard to handle for static analysis because the control flow is not strictly linear.

2) Simulating interrupts

With a 6502 interpreter, the interpreter can maintain a cycle count, and trigger an interrupt every N clocks.

With statically recompiled code, the output code (assuming it's C) would need to manually update a counter and check for a timer interrupt.

So code like this every line, or ever few lines:

if ((cycle_count += x) >= 29833)
interrrupt()

Toshi

Just to correct the URL of that talk:

Thanks for the link!
Ed

I just thought of something very twisted.
People will either love it or hate it.

6502 input code to static recompiler:



static recompiler output in C code:


This handles all the issues:

1) JMP (x) is handled properly.

JMP (x) will be compiled as pc = read_address(x) | (read_address(x+1) << 8 ); break;

2) JSR PRINT is handled properly

Basically same as case #1.

3) Self-modifying code is handled properly.

If the code jumps to a RAM address, the switch statement executes the default case, which jumps into a 6502 interpreter. When the 6502 interpreter detects a branch back to ROM, it returns back to the compiled code and updates the compiled code's registers.

4) Bank switching

For bank switching, instead of case values being 16-bit, the case value can be extended to include the bank bits.

I think this implementation solves all the outstanding problems.

Toshi

If nothing else, please understand my Java example, because that did work.


I am well aware of all the bytecodes. Invokestatic is obviously degenerate with regards to dispatch (I initially listed all the other invoke* instructions in my post but decided to shorten it), but the point remains with the others: It's a runtime dispatch based on the value held in a variable. In Java, the problem is determining the type that will be in that variable, in 6502 the problem is determining the address that will be in that vector. It's the exact same problem. There is a runtime dispatch on a variable whose value is not literally specified in the static code.

That is nothing that the JVM's static verification EVER looks at (it is PURELY a runtime check), and has nothing to do with the trust model of the bytecode itself. It has NOTHING to do with typesafety (the JVM guarantees it's always an Object reference and not a primitive, but that's as far as it goes), nor with converting numbers to pointers. It is about predicting where dispatch will go on platform-appropriate values (6502 = addresses, Java = instance types, NOT addresses).

Again:
#1, Java: What derived types will be stored in this base-typed variable?
#2, 6502: What addresses will be stored in this jump vector?

Exact same problem. Successful analysis in #1. The fact that programming style actually yields more limited ways in how #2's addresses get stored even makes it easier.

Those are both the same case, and are acknowledged in my previous post. Every static analysis technique hinges on the code areas being determinable, and has nothing to do with this algorithm in particular.

Hand-written 6502 assembly code most always has orderly code flow between the load & store when writing a literal value to a fixed location. Jump vector values are a set of enumerated literal addresses. Jump vectors are fixed locations. Non-constant stores to those fixed locations can have their presence detected. Longer propagation analysis than this triviality is unnecessary in order for this to work.

"Known code areas" are those that have been traced.

For this, I don't care about general variable manipulation, because 6502 programmers only used a few ways in the vast majority of cases for setting jump vectors in particular. The cases which do more complex computations in order to determine what value to write to a jump vector are relatively scarce. The cases where I've seen them come up are in the bigger productivity-type applications with very general, slower code, including interpreters. Most common applications, utilities, and games treat jump vectors for rerouting program flow between a few different possibilities, expressed as literal enums in the assembly code. This is by far the most common case, and thus is a very useful indicator in analysis.

Again, I'm not sure how much computational analysis work you've done, but if you try to have each and every step yielding completely proven results, and do not allow for partial premises and uncertainties, you will assume many things to be "impossible". Analysis is about resolving and testing possibilities amongst numerous overlapping indicators, if it has any hope of going anywhere substantial. This does not mean that the final output contains unmitigated uncertainties; it never should.

My 6502 experience is on the C64, and the majority of my observations and assumptions come out of that style, from lots and lots of reverse engineering of other people's software.



I'm under the impression that that's exactly how emulator JITs structure their output. Interesting take on having a static C representation of it with a switch to build the jump table for you.

I don't understand how it would handle self-modifying code, though. If the opcode (or operand thereof) changed at an already-known address, it would still jump to the statically defined version. It would seem to require getting the PC to a non-statically defined address within the routine in order for the interpreter to kick in and see the selfmods.

_________________
WFDis Interactive 6502 Disassembler
AcheronVM: A Reconfigurable 16-bit Virtual CPU for the 6502 Microprocessor

See his LinkedIn page at http://www.linkedin.com/in/tmorita
and his "Introduce yourself" post at viewtopic.php?f=1&t=1935&p=16504#p16504
They might not answer the question directly, but his qualifications are stunning.

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?

That's great to see. I was just trying to fight past the notion that I was implying casting ints to pointers in Java in my parallel. I'm also coming from more of an AI perspective than a straightforward manually-directed algorithmic perspective, which definitely yields differences in perspective.

_________________
WFDis Interactive 6502 Disassembler
AcheronVM: A Reconfigurable 16-bit Virtual CPU for the 6502 Microprocessor

Here's a sample from the 6502.org archives at:

http://6502.org/source/io/primm.htm



Just in case the argument is made that this is atypical code - Apple II ProDOS uses this same calling convention for disk I/O routines: http://www.dwheeler.com/6502/oneelkruns/asmfiles.html.
So this calling convention is very familiar to Apple II 6502 assembly language programmers.

Anyway:

1) Please convert the above 6502 code into equivalent Java bytecode.

2) please explain how the algorithm used for determining the derived types for a based-type variable in Java can be adapted to calculate the target of the indirect jump address in this code.

Toshi

First off, I never claimed that every use of JMP(ind) was analyzable through that particular algorithm. It's for analyzing what targets exist when indirect jumps are for an enumerated program flow state selection, which is the most common occurrence of JMP(ind) in the software that I've seen (including interrupt handlers and simple software indirection).

Stack return address manipulation is a separate field of indirection study, and thus this post has nothing to do with my prior specific point. I am not interested in 6502->Java conversion, as the idioms are too different to bother with automation. However, what you ask here is still possible. This PUTSTRI style is also very familiar to Commodore coders, as a routine like this is even in the C128's ROM, there called PRIMM (print immediate).


The final equivalent Java bytecode translation would put the character data into a parameter to not bother mucking with (or, more particularly to avoid the invalid operation of mucking with) the frame state.* Depending on implementation decision, and what types of callers are used, this parameter could either be an array (or string) or an index into a global memory array. The bytecode would thus end up idiomatic. I'm assuming an integer type to hold the memory offset, to avoid signedness issues, and I avoid using char type for non-char values, so 16-bit wrapping has to be inserted. The JIT's smart enough to collapse a lot of it down anyway.

(* = If I remember correctly, the inter-method return address is not even visible to the bytecode language. Intra-method subroutine return addresses are technically 'visible', but immutable from the bytecode.)

(Note: I know most java bytecode compilers wouldn't use dup/swap/pop as I do to retain the memory byte, but whatever, I'm hand-rolling this. Plus, static transforms of the 6502 code can avoid some of the +1 offset & postinc duplication; IOW, it's equivalent to inc DPL ... ldy #0, lda (DPL),y without the ora. However, my goals in analysis are on the original machine code, not recompilation.)

Now, the question is how to get to that point?

Loop detection works on PSINB - PSIX1 (of course, contingent on no additional entry points from external code), and variable propagation of .A and the Z flag through the lda/ora/beq instructions indicate the loop exit condition, so the meat of the function is relatively straightforward.

The code does a 16-bit pull off the stack, which is a nice clean transfer. Now, that means what happens is that in cases where PUTSTRI are entered is dependent on what's on the stack. For each case of JSR PUTSTRI, we take the knowledge of both the routine and the JSR's location (since PC+2 is pushed on the stack) to transform the JSR itself. Each other entry of PUTSTRI needs known values on the stack, or else it's intractable.

The bug in the ointment is that the pointer is transformed between the JSR PUTSTRI and the JMP back. In this case, the loop (increment until exit condition mem[ptr+1]==0) and final increment are the totality of transforms applied. This is simple enough to apply to the data per calling point, and is the meat of the transform which allows conversion to "normal" languages:


This is all tractable transformation. The only "difficulty" is creating an ontology which can express the pointer transformation sufficient for this case (ie, includes loops), and that's squarely in the known realms of symbolic AI, lambda calculus, and compiler intermediate representations.

Now, this still can fall apart if the data in the .byte statement is self-modified, or if PUTSTRI is or can be further self-modified from the outside, or if the transformation applied is not tractable given the analysis tools available, etc. However, the system can detect when such cases exist, but not what their outcomes would be, making it known-intractable.

The halting problem does not dictate that every single program (+input) is intractable to complete analysis; it only dictates the impossibility of a single system to analyze all possible programs. This approach simply builds up tractable scenarios for the subset of techniques that are actually encountered in the wild, not every possible theoretical program.

It would theoretically be possible to extend analysis to hypothetical, parametric RAM states to cover some of the problems I listed, but that's still pretty far out there.



To reiterate, this sort of problem must take advantage of whole-program analysis, not just looking at snippets of code in isolation. The strategies that are useful per piece of code depend on what is known from elsewhere, and the completeness of that knowledge.

Also to reiterate, I'm more about reverse engineering than recompilation, but in the case of recompilation there still isn't lenience for allowing incorrect code to be generated. Any final transformations are constrained to no known-unknowns, including disallowing specific transformation on the presence of completely separate known-unknown sections of code which might call or modify the code in question in different ways. Of course, these are tunable decisions depending on your "get something running" vs stability tradeoffs, and the platform-specific conventions (which on the 6502 are pretty much completely unconstrained, except maybe the decision to analyze NMOS illegal opcodes or just consider them non-code to avoid wasting time).

Also to reiterate further, the original fundraiser's presentation didn't include anything like this, and I do not hold that the technology he presented was sufficient to meet his goals, and that he seemed unaware of the limitations of his chosen approach. I do not state that development such that I present is complete in and of itself, but acknowledge that it needs human involvement to add general knowledge & strategies when it encounters cases it currently deems intractable with its tools, and adding software-specific knowledge & strategies is generally not a good idea. The concepts of "jump through a manipulated stack return address" vs "jump indirect to put a branch in the state flow" vs "jump using pha pha rts" etc are in my opinion general enough idioms to be described to a system for good reusability. Plus, the complexity of creating something capable of representing the required information to handle really bad situations can become human-intractable, and/or approach the halting problem.

_________________
WFDis Interactive 6502 Disassembler
AcheronVM: A Reconfigurable 16-bit Virtual CPU for the 6502 Microprocessor

I've said it over and over already: That algorithm does not apply to other uses of JMP(ind). It works on a common usage idiom of JMP(ind), just as the above post addresses a different usage surrounding JMP(ind). These are not specific to any particular software application's usage of JMP(ind), but general analysis tools on the usage style.

If a JMP(ind) is used in an unknown way with ind's values indeterminable, then its target is likewise indeterminable. But even including that, these methods yield far better results than avoiding doing any indirection analysis at all because you cannot prove that you can address all usage scenarios with simpler means, and because simpler means cannot reveal situational tractability.

As an aside, both of the cases that I present don't technically require the JMP(ind) instruction. The exact same analysis applies to JMP abs and branch instructions, where the target is self-modified.

_________________
WFDis Interactive 6502 Disassembler
AcheronVM: A Reconfigurable 16-bit Virtual CPU for the 6502 Microprocessor

_________________
x86?  We ain't got no x86.  We don't NEED no stinking x86!

You're avoiding the core issue, so let me restate #1.

What I meant was to write the PRIMM equivalent code in Java so a string can be printed using Java bytecode instructions like this:

invokestatic (index of PRIMM)
.ascii "Hello, world\n"
(execution continues here)

You can pretend there is no local stack frame to simplify the problem if necessary.

Once you try this, you will realize the Java case is not the same as 6502 case because of type-safety.

Toshi

So um, does the not repeating oneself ad nauseum principle apply to admonitions directed toward certain large extinct reptiles whose style is rather to the point?

Type safety has nothing to do with anything here. Please show how it is involved, because I show it isn't.

The issue is, and always has been in this entire field of study, the separation of code from data, finding out where the code flows, and what the data is used for. Java demands and strictly enforces code & data separation, and I've shown successful automated separation for the 6502 case, which allows it to be cleanly, conceptually, and fully expressed in Java (or any other common language) without type violations.

I honestly don't know what you're trying to prove with your tangent, as the "impossible" goal has been met, and the Java ended up being nicer than what you're trying to force. Trying to translate 6502 instruction-for-instruction and keeping that platform's structural artifacts in violation of Java's enforcement is pointless, and it has nothing to do with the common, shared analysis between the two platforms of the forest of what the code actually accomplishes (passing a zero-terminated string literal to a function), beyond the trees of low-level implementation tricks (combining return pointer & data pointer, which are again properly separated by static analysis and thus yield no type safety violations).


I think this is the main disconnect you're arguing about, that Java and 6502 are somehow too different to share analysis strategies, but what code does (in the broadest sense) on any given platform ends up generally being what code does on any other platform, once you understand how it's organized. Since 8-bit assembly typically has no standards of organization, the organizational notions must be re-inferred dynamically per instance, but concepts like detecting enumerations (since they manifest as simple non-manipulated literal writes) remain equivalent. Modern systems are not immune to needing this organizational discovery either since viruses, DRM, anti-reversing techniques, custom compiler output, etc, also wildly stray from common organizational assumptions that tools tend to use.

The other argument you bring up is that these techniques aren't always possible, depending on the situation. Well, that doesn't stop anybody from writing optimization strategies, which would also generate very incorrect code if their constraints were ignored. As long as some combination of application of situationally-appropriate analysis strategies attains coverage of the code, it doesn't matter which ones do not have their constraints met; the more potential strategies in the toolbox, the greater chance that fully automated means can achieve complete coverage. Even if complete coverage is not attained, for analysis & reverse engineering situations partial results are still incredibly useful.


What I've been saying is that many things which many consider impossible (or prohibitively difficult) regarding automated reverse engineering, or by extension recompilation, are potentially tractable if you allow for just slightly greater analysis beyond what's typically assumed from stock compiler tech. I've shown how to detect target values for a common type of dispatch vector (equivalent to enumeration detection), as well as analyze the boundaries of post-JSR immediate data, both of which people generally bring up as intractable issues that halt the very concept of static analysis. And neither are all that difficult, if the tools are allowed greater freedom to work.

_________________
WFDis Interactive 6502 Disassembler
AcheronVM: A Reconfigurable 16-bit Virtual CPU for the 6502 Microprocessor

No, you're missing my point.

My original point is that static code analysis problem on the 6502 is completely different from the static code analysis problem with Java bytecodes, because the Java bytecodes were designed for specifically to allow static analysis.

You insisted there was no difference between the two.

I then mentioned the PRIMM problem for two reasons:

1) To demonstrate the JMP (x) problem is not solvable via constant propogation.
2) To demonstrate that certain 6502 code sequences are not natively implementable in Java bytecode because Java bytecode is limited, because it is designed to allow static code analysis.

I'm guessing you don't understand my point in trying to do a conversion of PRIMM to Java because you don't understand the functionality of the bytecode verifier. So here's a quick explanation of the relevant functionality.

The functionality of the bytecode verifier which is relevant to this discussion is the tracking of types. The bytecode verifier keeps a record of the types of the values which are stored in all stack slots, local variables, etc.

In order to implement PRIMM natively in Java, this requires popping the return address off the stack and storing it in a stack slot or local variable. At this point, the stack slot or local variable is tagged as holding a return address.

There's two operations which must be performed on this value:

1) It needs to be converted to an array reference so it can be dereferenced. However, this value
is tagged as a return address, and it cannot be converted to an array reference.
So this is a type conversion issue.

2) It needs to be incremented. The iadd instruction adds together two ints. So in order to
increment this value, it needs to be converted to an int. There is no return-value-to-int
conversion instruction. So this is another type conversion issue.

IF the Java bytecode instruction set contained a return-address-to-array-reference conversion instruction, then this could be used to overwrite Java bytecode instructions and execute arbitrary code, which is difficult to detect in static code analysis. So this instruction is not supported in the Java bytecode instruction set.

Likewise, if the Java bytecode instruction set contained a return-value-to-int conversion instruction, it would only be useful if a symmetric int-to-return-value conversion instruction existed. This could be used to execute arbitrary code, which is difficult to detect with static code analysis. So these instructions are not supported in the Java bytecode instruction set either.

So static code analysis for 6502 code and Java bytecodes are very different problems.

Toshi