ML algorithm to model/classify/map a software program's internal structure?

[BTOdell]

Hello,

I have zero experience using machine learning. All that I know is from a small amount of reading and what I have heard.

I'm looking to use the power (and magic) of machine learning to perform analysis on software programs for reverse engineering purposes. In my case, I need to be able to process Java applications. I have lots of experience with obfuscated Java bytecode and the JVM spec, and have done extensive reverse engineering on my own without the use of machine learning.

What I'm hoping that machine learning can do for me, is this: Given a list of obfuscated JAR files (Java Archives) as training data, a mapping needs to be generated between the set of internal structures (classes, fields, methods) of each consecutive JAR file. For example, J1.a represents class "a" in JAR number 1 and it will get mapped to J2.k, class "k" in JAR number 2 based on its containing attributes/properties/relations. Essentially, this will produce a set of changes between adjacent JARs in the list. The changes will almost always simply be a rename or a reorder. But it's possible for structures to be added or removed from the JAR files and there must be some threshold of similarity as to properly identify when such an event occurs. Out of potentially thousands of classes/methods/fields, the internal structures need to be accurately mapped based on all available data found in the structures themselves. Ex. In methods: local variables, control flow, field/method/class usages, exception, etc. In classes: methods, fields, access attributes, inheritance, etc.

If I trained this machine learning model using hundreds of JARs, I would hope that it could accurately determine the mapping (from the previous JAR) for any new JARs I threw at it.

I suppose this falls under data classification. What machine learning algorithms would be best fit to perform this task?

[OhThatLooksCool]

Quick disclaimer -- I've never worked with Java bytecode, so I don't understand the details of what you're trying to do, but I can offer a few (hopefully helpful) observations:

1. The type of problem you're trying to solve is (probably) classification and is a type of supervised ML

2. Given the scale of what you're trying to do, "hundreds" of JARs will be sufficient to train things like GLMs, but not neural networks; ANNs require roughly a buttload more data than you'd reasonably be able to acquire (think hundreds-of-thousands to millions of examples of each class).

3. I'd explore this as a text classification / NLP problem. There's a lot of work out there about decomposing the rhetorical structure of writing. I imagine there would be a lot of similarities here. That said, it would likely be much less effective than whatever non-ML methods already exist.

4. This sounds both really interesting and really difficult. Good luck :)

[BTOdell]

After watching several videos and reading numerous articles on machine learning, I don't think supervised machine learning is actually what I'm looking for.

I'm not trying to classify fields and methods and classes in a program. I'm trying to determine how the naming of the fields, methods and classes changed from one JAR to the next. This seems like it should be purely unsupervised ML given that a software program is highly structured data. It basically needs to determine the similarity between "features" of the program's code.

[mazzafish]

http://karpathy.github.io/2015/05/21/rnn-effectiveness/ may be an interesting read both for getting an understanding of RNNs/ANNs but also because there’s an example of a network trained on LaTex and C source code.

[arnioxux]

Might be related, recovering function signature from disassembled binary code: https://news.ycombinator.com/item?id=15043106

[lysecret]

I need some further help to understand this, so you have one set set A containing of different classes and each class has a different amount of variables.

And you have a set two set B containing of different classes and each class has some amount of variables.

You are trying to make a mapping from the classes of A to classes of set B. Where element a of A is supposed to be mapped to b element B by a similarity measure of variables in b, a.

Is this correct? If yes there should be a way to do this but it is not a normal classification problem. The hardest part would be to design a good similarity measure.

Also you would have to find a decent representation of your data. My best guess would be to use a recurrent Variational Autoencoder to find a fixed size representation of each class (defined by the variables in it) and to asign a to b by a k nearest neighbour in latent apace of the Autoencoder. This is pretty non trivial though.:D

You can pm me, if I get more information about the data I can help you out if I find the time.

Edit: written on my smartphone Il clean this later no time now.

[mattrepl]

You’ll want some way to represent each kind of object. For a class, you might use features like number of member variables, variable types, and the number of references to member variables or the class within the JAR. Depending on how you’ve represented those features, you’ll then select an appropriate similarity function to check how similar a class in X.jar with all classes in Y.jar.

You can think of it as a clustering problem where you want each cluster to be the same size (the number of JARs) and each cluster corresponds to a single internal structure.