how to identify patterns in program execution flows?

Question

Consider a library, that is used by different programs. Under certain (unknown) circumstances, an error can occur. I want to feed execution traces of faulty programs to some kind of an algorithm / framework so it learns about the "pattern" which led to the error. It should then, when fed a live trace, detect when that error will occur and halt the program execution.

So what I have is a list of totally ordered invocations of library functions with their parameters and return value. A simple fault program, where a memory area is used after being freed, may look like

mylib_allocate()=0x100
mylib_dosomething() // unrelated "noise"
mylib_free(0x100)
mylib_dosomething() // unrelated "noise"
mylib_set(0x100, 0); // error here

So my question is: Are there any existing frameworks that could be fed with that kind of data, which tries to automatically identify patterns from many traces leading to the same error (e.g. "use after free"), and which produces some output which could be used to detect the error (i.e. trigger an event if such an error is going to happen)?

I looked through some data mining approaches, but it seems like they all target "manual" analysis for pattern identification, e.g. by graphic processing to visualize potential "cluster". Then I tried to look at "process mining", but this seemed to be a dead-end as well, because - as far as I understand - my invocation data with an arbitary amount of parameters doesn't fit into that "process" schema. At least I didn't get any reasonable results with ProM.

Answer 1

There's probably no existing turnkey solution that will do what you want, out of the box. I suspect this would be a research-level task, so you might want to start by searching the research literature to see if anyone else has tried to do something like this. (Google Scholar is useful.)

If you some advice on how to pursue this yourself, my advice would be:

1. Try to narrow the scope. Rather than trying to detect all bugs, pick a single class of bugs (e.g., use-after-free would be a fine choice) and see if you can have any success detecting those, as a first step. If you're successful then you could broaden the scope.

2. Think now about how you'll obtain enough data to work with. I suspect one of the biggest challenges will be how to obtain a large training set with known labels, that have many instances of in-the-wild use-after-free bugs, as well as many other traces with no instances of those type of bugs, labelled with whether there was a bug or not and which function invocations were responsible.

3. Take a look at association rule learning, sequential pattern mining, grammar induction and automata learning (e.g., my links here; e.g., you might try to learn a small automaton that detects use-after-free bugs), and recurrent neural networks (especially LSTM).

4. Also, you might need to do some feature engineering. For instance, when you have pointers or handles (like 0x100), you might want to canonicalize them, as the only useful information is whether two calls used the same pointer or a different pointer -- the actual value of the pointer is irrelevant. Since you have domain knowledge of that fact, by transforming the data before you feed it to the data mining / machine learning framework, you can help it learn a lot faster and more effectively.