Is the valid state domain of a program a regular language?

Question

If you look at the call stack of a program and treat each return pointer as a token, what kind of automata is needed to build a recognizer for the valid states of the program?

As a corollary, what kind of automata is needed to build a recognizer for a specific bug state?

(Note: I'm only looking at the info that could be had from this function.)

---

My thought is that if these form regular languages than some interesting tools could be built around that. E.g. given a set of crash/failure dumps, automatically group them and generate a recognizer to identify new instances of know bugs.

---

Note: I'm not suggesting this as a diagnostic tool but as a data management tool for turning a pile of crash reports into something more useful.

• "These 54 crashes seem related, as do those 42."
• "These new crashes seem unrelated to anything before date X."
• etc.

---

It would seem that I've not been clear about what I'm thinking of accomplishing, so here's an example:

Say you have a program that has three bugs in it.

• Two bugs that cause invalid args to be passed to a single function tripping the same sanity check.
• A function that if given a (valid) corner case goes into an infinite recursion.

Also as that when the program crashes (failed assert, uncaught exception, seg-V, stack overflow, etc.) it grabs a stack trace, extracts the call sites on it and ships them to a QA reporting server. (I'm assuming that only that information is extracted because 1, it's easy to get with a one time per project cost and 2, it has a simple, definite meaning that can be used without any special knowledge about the program)

What I'm proposing would be a tool that would attempt to classify incoming reports as connected to one of the known bugs (or as a new bug).

The simplest thing would be to assume that one failure site is one bug, but in the first example, two bugs get detected in the same place. The next easiest thing would be to require the entire stack to match, but again, this doesn't work in cases like the second example where you have multiple pieces of (valid) valid code that can trip the same bug.

Answer 1

If your program is decorated with assert statements, then each assert statement defines a valid state. The program statements between the assertions define the valid state changes.

A program that crashes has violated enough assertions that something broken.

A program that's incorrect but "flaky" has violated at least one assertion but hasn't failed.

It's not at all clear what you're looking for. The valid states are -- sometimes -- hard to define but -- usually -- easy to represent as simple assert statements.

Since a crashed program has violated one or more assertions, a program with explicit, executable assertions, doesn't need an crash debugging. It will simply fail an assert statement and die visibly.

If you don't want to put in assert statements then it's essentially impossible to know what state should have been true and which (never-actually-stated) assertion was violated.

Unwinding the call stack to work out the position and the nesting is trivial. But it's not clear what that shows. It tells you what broke, but not what other things lead to the breakage. That would require guessing what assertions where supposed to have been true, which requires deep knowledge of the design.

---

Edit.

"seem related" and "seem unrelated" are undefinable without recourse to the actual design of the actual application and the actual assertions that should be true in each stack frame.

If you don't know the assertions that should be true, all you have is a random puddle of variables. What can you claim about "related" given a random pile of values?

Crash 1: a = 2, b = 3, c = 4 

Crash 2: a = 3, b = 4, c = 5 

Related? Unrelated? How can you classify these without knowing everything about the code? If you know everything about the code, you can formulate standard assert-statement conditions that should have been true. And then you know what the actual crash is.

Answer 2

The return pointer on the stack is just a pointer to memory. In theory if you look at the call stack of a program that just makes one function call, the return pointer (for that one function) can have different value for every execution of the program. How would you analyze that?

In theory you could read through a core dump using a map file. But doing so is extremely platform and compiler specific. You would not be able to create a general tool for doing this with any program. Read your compiler's documentation to see if it includes any tools for doing postmortem analysis.