NCSDIS: Control flow analysis failure in do-loop nested in while-loop

[lachjames]

Hi :)

There appears to be an issue in either the control flow analysis in ncsdis or (potentially) a bug in nwnnsscomp.exe (which was used to compile the file). The bug happens in a rather strange situation, where you have a do loop nested within a while loop. Ncsdis seems to disassemble the ncs alright, but the control flow analysis throws the following warning:

"WARNING: Control flow analysis failed Because: Loop blocks out of order: 00000073, 00000073, 000000A9"

Again, I'm not necessarily saying this is a bug with ncsdis as it might be an error with nwnnsscomp.exe (this is a fringe case, and was likely never tested); it's probably worth investigation either way. I've attached the script (apologies for the .txt extension but I can't submit .nss files).

ncsdis_fail.txt

[DrMcCoy]

Hmm, I can't reproduce this here with a current ncsdis and an nwnnsscomp for NWN (from this repo https://github.com/DrMcCoy/NWNTools , which is just a mirror of the old OpenKnights cvs repo with some compilation fixes).

• Which version of ncsdis are you using? And if you're using an older version, like from the 0.0.5 release package, please try the one from one of the newer ZIPs I gave you

• Which nwnnsscomp are you using? If you're using one of the modified ones for KotOR, that might be a bug in those (either newly added or due to it forking from the stock codebase). Can you give me the binary (and preferably the sources, but there's unfortunately modified versions of nwnnsscomp where the sources were never distributed)

That mess with the nwnnsscomp versions if one reason I'd really like my own NWScript compiler in xoreos-tools... :P

[lachjames]

I am using one of the modified KOTOR versions - that's probably the cause then. I've attached the binary here.

I've been working on a decompiler for NWScript and I was wondering whether it might be possible to create a "reversible compiler", which might kill two birds with one stone. I'm looking into it now and will let you know if I find anything interesting.

nwnnsscomp.zip

[DrMcCoy]

Okay, I see what's going on.

First of all, this only happens when invoking that nwnnsscomp with the --optimize flags. If that's left out, the fail isn't there.

That --optimize flags, well, it optimizes code generation a bit. Meaning, it'll drop blocks that are "useless", because they just jump to another block. And that's the crux of the matter: to recognize "Oh, this is a loop", the analysis in ncsdis does some simple pattern matching over the blocks.

I.e. "here's a block with a comparison, that branches off to two blocks that are only jumps, one of them jumps backwards and one forward, yeah, that's a loop". Of course, now that the optimize-flag got rid of one of the jump-blocks, this doesn't match anymore, so my pattern matching finds something that looks like a loop at first, but on further checking, it does something unexpected.

To resolve this, I need to see if I can adapt the pattern matching to also allow for the optimized case (without mis-identifying something else as well).

There's likely going to be more of those failures in ncsdis, since I never looked expected a NWScript compiler to optimize things.

[DrMcCoy]

I've been working on a decompiler for NWScript

Keep in mind that xoreos-tools already has the start of a decompiler, ncsdecomp, courtesy of @Nostritius. It's not particularily useful yet, though. For example, it fails to decompile this little example script, even when unoptimized.

and I was wondering whether it might be possible to create a "reversible compiler"

I have no idea what's that supposed to mean.

[DrMcCoy]

Hmm, looking at it a bit more, it's even worse: it completely mis-identifies the loop blocks, even in the unoptimized case. The cause is the nesting, and my simple pattern matching mixes the blocks of the inner and outer loop.

Not quite sure how to resolve that one, to be honest. If you have any ideas or would like to rewrite the detection to be more fool-proof, feel free to do so.

[lachjames]

Currently, my dencs tool is able to parse the control flow correctly using the techniques described in "A Structuring Algorithm for Decompilation" by Cristina Cifuentes. I'm hoping to have a complete dencs tool written within the next week or two, in Python. More generally, I've been following the approaches listed in Cifuentes's PhD thesis "Reverse Decompilation Techniques". Fortunately, decompiling NCS code is simpler than most languages because NSS has no "goto" statements, so a lot of the algorithms can be simplified significantly.

Currently, I have almost completed the control flow analysis, and I'm trying to nail down data flow analysis now. The main bottleneck is detecting variable assignments and changes in optimized code (because a lot of the optimizations just ignore some of the stack allocation commands used in the full NCS code). This shouldn't be too hard as NCS also doesn't have registers (so all I need to do is monitor the stack).

Once it's done, I'll make the source code public on Github. If you or another xoreos contributor want to port that to C++ and include it in xoreos (or alternatively create C++ bindings for my Python code), I'd be happy to help in any way I can, including (but not limited to) assisting with writing and debugging the code, and in-depth explanations of how my code works.

[DrMcCoy]

Ah, to be honest, I kinda hoped you'd work on the xoreos-tools dencs. Oh, well, I guess that's my fault for assuming.

But still, thanks for making it public and for that offer of assistance :). I might take you up on that in the future, when I find some time.

Can you do me a favour and attach a proper license to that code (preferably of course one that's compatible with the GPLv3+ for pulling it into xoreos-tools)? Just so that everything is on the up and up?

Also, I'd be grateful for any comments, explanations and documentation on how to replicate how you did that, so I can understand what's going on. I guess my starting point would be reading those theses? As should be obvious, I've been mostly going by my own thinking and experiences with the current dencs code instead of going by specific decompilation theory. That might have been a mistake :)

[lachjames]

I'd love to work on the xoreos-tools dencs myself, but I'm just not sure if I have the time at the moment to commit to a large project in C++ (Python is manageable as I'm able to simplify the code base significantly using some Pythonic tricks). For reference, I've decompiled the Java code for the original TSL dencs and it's about 50k lines of code (a few functions didn't properly decompile, but most of it did). I think some of that is auto-generated from a grammar definition for reading NCS files though. My Python implementation will be more code-efficient than this due to aforementioned language features, but I can only imagine what it'll be like to implement this in a language as sparse as C++. Of course, anything that can be done in Python can be done in C++ so I'm confident (with enough time) I or someone else can do it.

I've based the lexer/parser of my implementation on the dencs version, but I'm doing the rest from scratch (both because I want to learn decompilation for myself, and also because it's probably easier to learn it than to try to figure out a large, decompiled code base, even given the inclusion of function/variable names in the decompiled source). Any code I open source would be compatible with your license (my personal preference would be to make my code public domain, but I've heard that comes with problems of its own, so I'll just choose the most permissive license I can). I'm not sure what the licensing implications of my using the decompiled dencs code as a reference are, but I can confirm for sure that I wrote all the code I use (and have only used dencs as a reference for the lexer/parser grammar since the source included a complete grammar for reading ncs code - although I've modified it significantly for my purposes).

The literature on decompilation is more sparse than I expected, which I found very surprising as it's such an interesting field. I'm confident that I have a handle on the control flow side of things now, so I just need to figure out the stack analysis component (I reckon I'm halfway there though). I'll let you know as soon as I have something on GitHub.

[lachjames]

@DrMcCoy I've created a (currently private) repo for my version of dencs, and added you as a collaborator. Currently, it's working on almost all simple scripts but there is still some fine tuning to be done; however, the main structure is now present and (hopefully) the hard work is done.

Please feel free to contact me - the best place to talk is probably on Discord but I am also happy to chat on xoreos's IRC if you prefer.

[DrMcCoy]

Frankly, I prefer IRC. I like to have everything in one place, and especially archived in plaintext logs I can grep easily. That makes me not a fan of all these myriads of new-fangled chats :P

Still, I do have a Discord account. I primarily use it for voice chat during roleplaying via roll20 in some of my groups, and I usually only have it running then. I can't add you, btw, it says you're not accepting friends request. Unless I can write to you without going through the add friend route?

One immediate comment I can give you about your "Limitations" paragraph, concerning structs: I found that at least the original BioWare compiler (and at least in NWN) usually uses the DESTRUCT opcode when handling struct members. I.e. when copying the value of a struct member, the script usually copies the whole struct with all elements to a new stack position, then uses DESTRUCT to isolate the struct member it actually cares about.

Of course, it that's optimized away, that tell is of course gone. And I don't know if DESTRUCT is used for other usecases at all.

[lachjames]

Re discord, I’ve updated my preferences to allow invites from anyone (I was getting spam before so I set it to friends of friends only; I’ll just deactivate it again once you’ve successfully added me). Apologies for that.

Thanks for the info re the struct accesses; it’s very useful. If the decompiler can find structs in the original BioWare code, that’s good enough for me. I’ll do some experimenting and try to figure it out.

One other feature I’m hoping to add is include detection from all the NSS files included in the game(s); easier said than done and I’ll have to do some sort of functional pattern matching, but it should be possible. The easiest tell will be thanks to the original compiler including all global variables from includes whether they’re used or not, but that won’t work for optimised compilers (again, may or may not be an issue depending if I/we decide to support optimised compilers in the first place).

[DrMcCoy]

Hmm, since the functions should be compiled the same each time (at least for a given compiler [1]), you could maybe simply hash the compiled functions. Then store all hashes for all functions in all common includes files (produced by multiple compilers, even).

Otherwise... I know that the Interactive Disassembler IDA has a database of common libc function signatures (the so-called FLIRT database). They wrote about it here: https://www.hex-rays.com/products/ida/tech/flirt/in_depth/

[1] For NWN at least, there are multiple official compiler versions out there, producing different output. The one in the beta produces some wonky output (that short-circuiting bug Ive wrote about in my blog post), that was fixed in later public version. But some scripts distributed with the game still contain that bug.

[lachjames]

Thanks for your suggestion - I was also thinking along the same lines. You're right that the different compiler implementations (both first party and from the community) present a challenge here. My thinking is that I can create "fingerprints" for each NSS function, using heuristics such as:

• The function signature and return type
• The globals defined in the script (for compilers which include all globals from includes)
• Variable declarations in the function
• Control flow structure (number of loops, etc.)

Using this, I can heuristically compare a given decompiled function to this database of known includes, and find close (if not exact) matches fairly easily. This should also be robust to decompilation errors, which is good.

My ultimate goal here is to detect the includes for a given script, and replace them with #include directives at the top of the file. This will greatly simplify the decompiled code, as most functions in an NCS script are library functions to support the (generally relatively simple) main/StartingConditional function.

[DrMcCoy]

One issue I can see coming there is false positives. You matching on a function that's actually not imported from an include. This gets more likely the shorter the function is, of course.

This does happen with IDA on occasion, and it can create lots of confusion.

[lachjames]

Yeah I can imagine false positives being a problem, as you say. One fortunate thing is that there are actually only a few files which are actually used for includes. Some sort of interactivity so users can make choices when the function has multiple matches would also help; of course, I'd also have a button to turn it off altogether, which some might prefer. Another heuristic which could help is trying to choose the imports that reduce the number of includes (with the reasoning that if one function from a given include is used, another is more likely to be from that include too - just a heuristic but I think it's not unreasonable). Figuring out exactly how to use these heuristics would mainly be a matter of tuning/trial and error I guess.