Is it possible to build an equivalent function just looking at the input and output of the original function?

Question

Imagine you are reverse engineering a software. This software uses a library, which is obfuscated and encrypted. The library contains a function, lets call it secret_function. This function is a pure function (i.e. it doesn't have any side effect and when called with the same arguments it returns always the same output).

Assuming i can call secret_function how may times i want, with whichever arguments i want, but i can't peek at the implementation, is it possible to build an equivalent function in another language (python for example), only analyzing the input and output values?

This is an example implementation of secret_function:

int secret_function(int a, int b) {
    if (a == 234) {
        return b*2 - a;
    }
    return a*b;
}

A way to archive this i thought of is to call the function with every possible argument, (in the example 2^32 * 2^32, assuming a 32 bit int) and store all of them, to return them based on the arguments, like a giant lookup table. But this doesn't seem very efficient, if at all possible.

UPDATE: You can assume that the function is working with fixed size arguments. So no strings or variable length arrays.

Answer 1

Your problem seems to be related to what Sibyl aim at doing (https://github.com/cea-sec/Sibyl). It tries based on the side effects of the function (return value, memory writes, ...) to identify a known function. Of course, you will need a kind of database to "learn" the function !

Answer 2

If you have all the possible input and all the expected outputs, and they're not indistinguishable from encrypted/compressed data, you can find more efficient storage mechanisms than just having a large lookup table. Even a simple genetic algorithm can very quickly get you to "use a * b, unless a == 234" (I've actually made a solver specifically for this kind of problem, though in a more general mathematical formula case). In the end, it's a rather ordinary optimization problem, where you're balancing off the storage space, computation and preparation time needed to give the correct result. More complicated algorithms can take longer to solve, which is one of the reasons why encryption works - those algorithms are specifically designed to make it extremely labor intensive to go from a set of known inputs and outputs to the private key used for the encryption.

But in any case, to have certainty, you must try all possible inputs. That's easy enough (though certainly laborious) for a couple integers, but quickly gets untenable for something like a string.

Answer 3

Unless you try all the input possibilities, as you suggested, you can only get an approximation of the function. This is basically one of the basic problems in the machine learning field, so I would look that way instead of trying to generate a lookup table for 2^32 * 2^32 values.

You should obviously be careful that you won't have 100% guarantee that the function is equivalent and also remember that in particular fields how the output is computed is as important as the output itself. Take encryption functions: having the same outputs but exposing informations (due to memory leaks, power usage spikes and so on) for side channel attacks means that the "equivalent" function is in fact far worse than the original (to the point it might not be a suitable replacement).

Answer 4

This problem essentially describes the field of sequential analysis coupled with curve fitting.

If you are able to make some assumptions about the inputs to the secret function that your model needs to be good for, you can use this to guide your choice of algorithm for generating new values to try as inputs to the function.

If you are able to make some assumptions about the characteristics of the function, you can use this to guide your choice of function to fit to the outputs of the secret function, which will determine how the resulting function behaves when you subject it to inputs you haven't tried yet.

Even the "simple" example given might be interpreted many different ways in these fields. For instance:

• If you can't assume anything about the function and your model of it must reproduce exactly the correct value, you have no choice but to evaluate all 2^64 possibilities. You don't necessarily have to store them all as you go if you correctly guess a function that can reproduce every value with the right parameters.
• If you know that there is exactly one value of a that changes the function, and that it is one of two linear functions of a and b depending on this value then you'll need on average 2^31 trials to find the magic a value, significantly shrinking the problem.
• If you don't require an exact reproduction then you can begin reasoning from a value judgement about what errors are acceptable. For instance, a function which is completely wrong 2^-32 of the time might be perfectly acceptable, so if you know that the special case is no bigger than this you can just pick a few random values (almost certainly not accidentally picking a = 234) and solve the linear equations.
• You might not reasonably know that the function has linear parts, but know that it's no more complex than some other function. The parameters to this more complex function, when fitted to outputs from the secret function, would produce a function which matches linear behaviour for the values obtained from the function, but wouldn't necessarily be guaranteed to behave linearly for untested values; the possible behaviours of any function you choose to fit must hence endeavour to match the range of behaviours that can be considered plausible under your assumptions.

These are big fields, and there are plenty of options that may be available to you with the benefit of the specifics of your problem.