5

Let $M=(\Sigma,S,s_0,\delta)$ be an (unknown) deterministic finite-state automaton (DFA), with alphabet $\Sigma$, statespace $S$, start state $s_0 \in S$, and transition relation $\delta$. I want to explore $M$, i.e., visit every state of $M$, or as many states as possible. Unfortunately, I'm not given $M$; I only have the ability to send inputs to $M$.

In particular, what I can do is specify some input strings $x,y,\dots \in \Sigma^*$. The string $x$ will drive $M$ down some path, namely, down the sequence of states $s_0,s_1,s_2,\dots$ where $s_{i+1} = \delta(s_i,x_i)$. I can specify as many input strings as I want.

The cost to me is the sum of the lengths of the input strings. In other words, each transition costs me \$1.

The benefit to me is the fraction of $M$'s states that are visited at least once in response to at least one of these input strings.

I have complete freedom to choose the set of input strings, but I am not given any feedback (I can't see the sequence of states that $M$ follows, I don't learn when I've visited a new state, etc.). I'm hoping to get as much coverage of $M$'s statespace as possible.

How should I choose the set of input strings to maximize the coverage while minimizing the cost? For instance, given a fixed budget, what's the best set of input strings that will give the best benefit? Is there a reasonable strategy, or any theory to help guide the choice of input strings?

Of course, I realize that the worst-case coverage, taken over all possible DFAs, might be very poor. But I would be satisfied with any approach that one can argue is close to optimal, in any meaningful sense. For instance, maybe one metric might be to use a regret ratio, where the regret of strategy 1 compared to strategy 2 is the maximum, over all DFA's $M$, of the benefit of strategy 2 on $M$ divided by the benefit of strategy 1 on $M$. Or maybe you can suggest some other way to formulate this in a principled way that admits an interesting solution. I'm open to suggestions about how to formulate the problem in a way that permits analysis.

If it's helpful, I'll promise that the alphabet is small (say, $|\Sigma| \le 10$), the number of states is not too large (say, $|S| \le 1000$), and the diameter of the graph is small (say, at most 10).

I'm also interested in the variant where $M$ is a NFA instead of a DFA, but I thought I'd start with the simpler case.

This is an attempt at an application of theory to practice. The application is randomized testing of UI-driven applications, where we think of the application as a DFA and the inputs represent user actions (e.g., tapping on a particular portion of the screen). The problem above is an idealization of the problem where we don't get any feedback as we go (which is motivated by the fact that it's not trivial to observe anything reliable about the state of the application).

D.W.
  • 12,054
  • 2
  • 34
  • 80
  • After sending an input do I get as feedback the percentage of state visited? – Marzio De Biasi Oct 25 '13 at 22:04
  • @MarzioDeBiasi, no, you don't. (In practice you might get some feedback, but it's very unreliable, which is why I wanted to start to see how good you can do without any feedback at all. So I'd prefer to say "no" and see how good a solution we can get without any feedback.) – D.W. Oct 25 '13 at 22:10
  • D.W. ok, what is exactly the "total" benefit function to maximize (it should be a function of both the transition cost, and the final percentage of covered states) ? – Marzio De Biasi Oct 25 '13 at 22:12
  • P.S. I'm not an expert, but perhaps the problem is similar to the cover time in a Markov-chain (with n-states and equal probability on the outgoing transitions). See also cover time of DAGs (e.g. http://cstheory.stackexchange.com/questions/2908/cover-time-of-directed-graphs) – Marzio De Biasi Oct 25 '13 at 22:29
  • 1
    I fear you may need a lot more features from this model to get good results. As an adversary, I'd pick $s$, the shortest string that doesn't appear as a prefix in your set of words. Then, I'd construct $M$ to force all inputs not containing $s$ as a prefix into a single sink state and put as many states as I'd like corresponding to strings with $s$ as a prefix. To beat this adversary, all you could do is pick your set of words to be the set of all words (of a given length). – mhum Oct 25 '13 at 23:26
  • @mhum, yup, agreed, that's why I said the worst-case performance (i.e., taken over all $M$'s) of any fixed strategy will surely be very bad -- I was thinking of the same sort of example. Thank you for highlighting this. Nonetheless, I still have an intuition that some collections of strings are better than others. Does that seem right, and is there any way to formalize this? For instance, maybe we can normalize relative to the coverage that would be achieved by a single random walk, or something like that? – D.W. Oct 26 '13 at 00:28
  • @MarzioDeBiasi, if you want a well-specified objective function to maximize, the formulation I would recommend is: you are given a fixed budget (an upper bound on the allowed cost), and you want to find the strategy with the best possible benefit (final coverage) subject to the restriction that you must live within your budget. – D.W. Oct 26 '13 at 00:29
  • @D.W. Without any restriction on $M$, my feeling is that you won't be able to do any better than straight brute force (i.e.: all strings of a given length). However, it's possible that your real-life scenario may have some subtle restrictions on the structure of $M$. The adversarial argument relies on the possibility of pathologically bad $M$'s. Maybe you can introduce some criteria on $M$ to exclude such weirdness? – mhum Oct 28 '13 at 19:32

0 Answers0