New Fuzzing Biases for Action Policy Testing

Venue: icaps-conference_org_ICAPS_2024_Conference
Published: 2023-12-07 14:02:28

Abstract: Testing was recently proposed as a method to gain trust in learned
action policies in classical planning. Test cases in this setting are
states generated by a fuzzing process that performs random walks from
the initial state. A fuzzing bias attempts to bias these random walks
towards policy bugs, that is, states where the policy performs
sub-optimally. Prior work explored a simple fuzzing bias based on
policy-trace cost. Here, we investigate this topic more deeply. We
introduce three new fuzzing biases based on analyses of policy-trace
shape, estimating whether a trace is close to looping back on
itself, whether it contains detours, and whether its goal-distance
surface does not smoothly decline. Our experiments with two kinds of
neural action policies show that these new biases improve bug-finding
capabilities in many cases.

Main paper: 
 introduction 15: 
 Learned action policies, in particular ones represented by neural networks, are gaining traction in AI (e.g., Mnih et al. 2013; Silver et al. 2016 Silver et al. , 2018)) , and are being intensively explored in AI planning (Issakkimuthu, Fern, and Tadepalli 2018; Groshev et al. 2018; Garg, Bajpai, and Mausam 2019;  20 Toyer et al. 2020; Karia and Srivastava 2021; Ståhlberg, Bonet, and Geffner 2022a,b) . But how to gain trust that such a policy will yield desirable (or at least non-fatal) behavior?Policy testing is one natural answer to this question. Most work so far views the environment as an adversary, controlled by the testing mechanism in a way that tries to make the system fail (e.g., Dreossi et al. 2015; Akazaki et al. 2018; Koren et al. 2018; Ernst et al. 2019; Lee et al. 2020) . While this can be quite useful, it does not distinguish whether or not the failure is actually due to bad policy decisions, or is unavoidable given the environment behavior.Recent work (Steinmetz et al. 2022) addresses this in the context of classical planning, defining test cases as states s, and policy bugs as states on which the policy is sub-optimal (a better policy exists for s, e.g., avoiding failure). Given a test case s, test oracles are used to detect whether s is a bug, by evaluating sufficient criteria that avoid the need for a full optimal planning process (Eisenhut et al. 2023) . To generate test cases in the first place, a fuzzing process iteratively builds up a pool of test states by conducting random walks from the initial state. A fuzzing bias attempts to bias these random walks towards policy bugs, thus making the overall testing machinery more effective in finding bugs. Specifically, we consider bias functions mapping states to numbers, with higher numbers indicating more promising states.Prior work (Steinmetz et al. 2022 ) only explored a simple bias function, mapping a state s to the summed-up action cost of the policy trace in s. Here, we investigate this topic more deeply. We introduce three new fuzzing biases that aim at analyzing the policy-trace shape. In what we call the loopiness bias, we measure how close a trace is to looping back on itself, a typical reason for failure to reach the goal (in dead-end free domains, this is indeed the only reason). In the detour bias, we measure the largest detour (the most sub-optimal segment) along the trace. In the surface bias, we consider goal-distance along the trace as its surface, and measure the degree to which that surface does not smoothly decline along the path. All three measures rely on estimates of the distance between states (on the trace, respectively to the goal). We include an analysis of the idealized setting using the exact distance h ⋆ ; in practice, we use the delete relaxation heuristic h FF (Hoffmann and Nebel 2001) .Using h FF instead of h ⋆ of course makes the measurements inaccurate. In particular, "detours" and "goal distance increases" will often simply be due to h FF estimation errors, but biases may still contain information useful for bugfinding. Indeed, this is what our experiments show. We consider two kinds of neural action policies: ASNets (Toyer et al. 2018 , 2020 ), and Ståhlberg et al.'s (2022a; 2022b) GNN policies. We test these policies across a set of domains where they perform well. Our new fuzzing biases improve bug-finding capabilities in many of these cases.An FDR planning task is a tuple Π = ⟨V, A, I, G⟩. V is a finite set of variables, each variable V ∈ V has a finite domain dom(V ). A partial state p is a variable assignment over some variables V(p) ⊆ V; p[V ] is the value assigned to V ∈ V(p) in p. Given U ⊆ V, p[U ] denotes p restricted to U . A partial state s is a state if V(s) = V; Sif G = s[V(G)].A is a finite set of actions, a ∈ A is defined by its precondition pre(a), effect eff(a), and cost cost(a) ∈ R + 0 . Preconditions and effects are partial states. A[s] is the set of all actions applicable in s. The resulting state of applying an applicable action a in a state s is s ′ = a s s.t. s ′ [V ] = eff(a)[V ] for every V ∈ V(eff(a)), and s ′ [V ] = s[V ] otherwise. A sequence of actions ϕ = ⟨a 1 , . . . , a n ⟩ is applicable in s 0 ∈ S if there are states s 1 , . . . , s n s.t. a i is applicable in s i-1 and s i = a i s i-1 , the resulting state is ϕ s 0 = s n . Given ϕ applicable in s, the sequence ⟨s 0 , s 1 , . . . , s n ⟩ of the aforementioned states is called intermediate state sequence of ϕ. The cost of ϕ is defined as cost(ϕ) = n i=1 cost(a i ). ϕ applicable in s s.t.a ∈ A is appli- cable in s ∈ S if pre(a) = s[V(pre(a))]. Given s ∈ S,G = ϕ s [V(G)]is called s-plan, and I-plan is called plan.We consider heuristic functions h as estimators for costs of optimal s-plans, denoted as h(s), and optimal paths between two states s and t, denoted h(s, t). We assume all heuristics are safe, and h ⋆ (s) and h ⋆ (s, t) denote optimal costs. Deterministic policies π : S → A ∪ {∅} map states to applicable actions or null (∅) if there is no applicable action. The run (or trace) σ π (s) of a policy π on state s, is an action sequence σ π (s) = ⟨a 1 , . . . , a n ⟩ applicable in s (with its intermediate state sequence ⟨s 0 , . . . , s n ⟩) s.t.a i = π(s i-1 )for all 1 ≤ i ≤ n, all intermediate states differ from each other, and no s i is a goal state unless i= n. The cost of σ π (s) is cost π (s) = cost(σ π (s)) if σ π (s) s is a goal state, and cost π (s) = ∞ otherwise; cost π s0 (s i , s j ) (i < j) denotes the cost of the subsequence of σ π (s 0 ) between s i and s j .We adopt the testing framework of Steinmetz et al. (2022) : Given a task Π and a policy π, a state t is called a bug in π if cost π (t) > h ⋆ (t).1 To find bugs, policy testing (1) generates a pool P ⊆ S of test states using a fuzzing process, and (2) runs test oracles on each pool state. Here, we focus on (1) only. For (2), we fix the state-of-the-art oracle of Eisenhut et al. (2023) ("BMO-100 + Aras/EHC").The fuzzing process proposed by Steinmetz et al. uses random walks from I guided by a bias B, which is a function mapping states to numbers where higher numbers indicate more promising states (more likely to lead to a bug state). The fuzzer evaluates B on every successor state s, and obtains a probability distribution over the respective actions by normalizing the biases B(s). We adopt this fuzzing process here, though with some refinements as described in the next section. Steinmetz et al. only explored a simple bias B π (s) = cost π (s): the cost of the policy run. The fuzzing process with B π prefers to explore states with more costly policy traces. Under the assumption that such states are more likely to be bugs, this makes sense, and indeed it often increases the number of detected bugs in comparison to a uniform random fuzzer. Nevertheless, this bias encapsulates a rather naïve notion of "good" vs. "bad" policy traces. Here, we investigate this topic more deeply, through new fuzzing biases that aim at analyzing the shape of policy runs.We design a refined version of the fuzzer introduced by Steinmetz et The application of B is still straightforward. In each step of the random walk, we compute a set S ′ containing pairs (s ′ , b) of successor states s ′ and bias values b, ignoring goals and states with bias -∞. We then pick one of the states in S ′ 150 as follows (function weightedSelect): if there is any (s ′ , ∞) in S ′ , we pick one s ′ among all such s ′ uniformly at random. Otherwise, we determine the minimal bias value b min . If b min < 0, we increase all b by |b min | so that all b are nonnegative. Finally, we normalize the bias values to sum up to 155 1 and select s ′ according to this probability distribution.5 for i = 1 . . . l do 6 S ′ ← ∅; j ← Bexpansion; 7 for s ′ ∈ {s a | a ∈ A[s], G ̸ = s a [V(G)]} do 8 if h max (s ′ ) = ∞ then continue; 9 if B requires computing cost π s ′ then 10 if j ≤ 0 then break; 11 σ ← partialRun(π, s ′ , min(j, Bstate)); 12 b ← (∞ if π fails in σ else B(s ′ )); 13 j ← j -|σ|; 14 else b ← B(s ′ ); 15 if b > -∞ then S ′ ← S ′ ∪ {(s ′ , b)}; 16 if S ′ = ∅ thenFor biases that require computing the cost of partial policy runs (B π and all biases introduced next), our fuzzer includes further additions. For each successor state s ′ , we use the function partialRun(s ′ , π, k) to obtain the partial policy 160 trace σ of π on s ′ of at most k steps, which is then analyzed by B. If we can infer from σ that π fails on s ′ , we ignore B(s ′ ) and assign b = ∞ instead, i.e., we consider only policy runs that could lead to a goal state. As we ignore goal states, this also means B(s ′ ) is not computed if σ is empty. 165 Since evaluating policies is often very time-consuming, we introduce simple mechanisms bounding the number of policy evaluations. We limit the number of steps of individual policy runs by B state , and we limit the overall number of policy steps per successor state by B expansion .The only bias from prior work preferred policy traces with high cost, which may be due to bad policy behavior, but may just as well simply be due to high plan cost. Here, we instead introduce measures of policy-trace shape, encapsulating deeper notions of policy-trace quality. Specifically, we introduce what we call the loopiness bias, detour bias, and surface bias. All three biases consider pairs of states s i and s j on the policy trace, and maximize a measure of "traceshape badness" over all such state pairs. These measures all rely on heuristic functions h estimating state distances; we consider both, the idealized setting where h = h ⋆ , as well as h = h FF which we use in practice. As part of our experiments, we run the idealized biases with h ⋆ where feasible, to evaluate the impact of using h FF instead.We next introduce each bias in turn. In the following, let s denote the current state reached by a random walk as per Algorithm 1, let ⟨a 1 , . . . , a n ⟩ denote a non-empty partial run of the policy π on s, i.e., the first n steps of the policy run σ π (s), and let ⟨s 0 , . . . , s n ⟩ denote the respective intermediate state sequence where s = s 0 . We omit all proofs here; they are included in the accompanying technical report.Loopiness Bias The loopiness bias is geared at estimating whether, at some point along the policy trace, that trace is close to forming a loop. The bias is defined as follows:195 B loop h (s) = max 0≤i<j≤n cost π s (s i , s j ) -h(s j , s i ).For every state s i and later state s j along the policy trace, we measure (a) the cost of the policy path from s i to s j , minus (b) the estimated cost of a plan from s j back to s i . This measure will be high if s i and s j are distant on the policy trace, but only few steps are needed to go back from s j to s i .Note here that, while one may be tempted to use only (b) and minimize over its values, (a) is useful because states close to each other on the path may naturally have very small values for (b). Indeed, in invertible planning tasks where every action has a direct inverse of the same cost, this is necessarily 205 the case as (b) will be the cost of a single action for every state pair s i and s j with j = i + 1 along the trace.Invertible tasks also form a special case regarding the outcome of the maximization in the idealized setting:Proposition 1. In invertible planning tasks, B loop h ⋆ (s) = cost π s (s 0 , s n ) -h ⋆ (s n , s 0 ).Of course, this does not hold if we replace h ⋆ with h FF . We considered to save computational effort (avoiding maximization) for B loop h ⋆ by detecting invertible planning tasks automatically (e.g., Hoffmann 2005), but these automatic 215 tests failed to find any invertible tasks in our benchmark set.The detour bias aims to directly measure whether a policy trace is sub-optimal. We consider every segment from s i to s j on the trace and compare its cost under the policy to the estimated cost of a path from s i to s j :B detour h (s) = max 0≤i<j≤n cost π s (s i , s j ) -h(s i , s j )Large values of cost π s (s i , s j ) -h(s i , s j ) indicate that the policy trace "takes a detour" from s i to s j . Note that, syntactically, the only difference to the loopiness bias is the order of s i and s j in the call to h. That difference can lead to arbitrary differences in bias value however (even for h ⋆ and in invertible planning tasks, as there may be a much cheaper path from s j to s i than the inverted policy path).For h ⋆ (but not for h FF ), maximization here is not needed as any subpath detour is contained in the overall path:Proposition 2. B detour h ⋆ (s) = cost π s (s 0 , s n ) -h ⋆ (s 0 , s n ).It is furthermore easy to see that the idealized detour bias carries exact information about bugs and their optimality gap (note that unsolvable states can by definition not be bugs): Proposition 3. Let s be a solvable state. If B detour h ⋆ (s) > 0, then s is a bug. If s is a bug and ⟨a 1 , . . . , a n ⟩ reaches the goal, then B detour h ⋆ (s) > 0 and there exists a plan for s whose cost is at mostcost π s (s 0 , s n ) -B detour h ⋆ (s).Surface Bias Search space surface has previously been investigated as a way of examining the quality of heuristic functions (e.g., Hoffmann 2005 Hoffmann , 2011)) . Here we take a related perspective, considering the surface of the policy trace when taking h-values as the vertical dimension. On an optimal path to the goal and if h = h ⋆ , this surface will decline smoothly, i.e., it will reduce by cost(a i ) in each step. The surface bias aims at measuring the degree to which this is not the case:B surf h (s) = -∞ h(s) = ∞ max 0≤i<j≤n cost π s (s i , s j ) -(h(s i ) -h(s j )) h(s) ̸ = ∞ If h(s) = ∞,s is unsolvable, so we return the minimal bias value -∞. Otherwise, this measure includes (a) the cost of the policy path from s i to s j , minus (b) the decrease in h value from s i to s j . If (a) is larger than (b), then the policytrace surface between s i and s j does not decline as smoothly as it should. In particular, if s j is far from s i on the path, but is estimated to be further from the goal, i.e., h(s j ) > h(s i ), the surface bias will be very high, indicating that the trace is meandering around, not making progress towards the goal. Of course, outside the idealized h ⋆ setting such an indication may be misguided merely due to local minima in h. Again, maximization here is never needed forh = h ⋆ : Proposition 4. B surf h ⋆ (s) = cost π s (s 0 ,s n )-(h ⋆ (s 0 )-h ⋆ (s n )). The bug information in the idealized setting is even stronger than for the detour bias: Proposition 5. Let s be a solvable state. If B surf h ⋆ (s) > 0, then s is a bug. If s is a bug and ⟨a 1 , . . . , a n ⟩ reaches the goal, then B surf h ⋆ (s) > 0 and the optimal plan cost for s is exactly cost π s (s 0 , s n ) -B surf h ⋆ (s).The surface bias also has a desirable property in a nonidealized setting: Proposition 6. For any safe heuristic function h, B surf h (s) = ∞ only if ⟨a 1 , . . . , a n ⟩ ends in a dead-end state.For our experiments, we extend the testing framework by Eisenhut et al. (2023) , which builds on the one by Steinmetz et al. (2022) . As in their work, we test ASNets policies (Toyer et al. 2018 (Toyer et al. , 2020)) , but we use our own, less resource Policy Domain #ΠOracle coverage (practical biases) S Oracle coverage (all biases) intensive, C implementation of ASNets and a more comprehensive benchmark set. We also consider GNN policies (Ståhlberg, Bonet, and Geffner 2022a,b) . Here, we test the original policies provided by Ståhlberg, Bonet, and Geffner (2022b) on a subset of the original benchmark set. Both kinds of policies are run in separate processes with their own memory limit of 2 GiB for ASNets and 8 GiB for GNNs. The testing engine uses a limit of 2 GiB. A cluster with Intel E5-2660 processors was used. If this paper is accepted, we will make code and benchmarks publicly available. We compare our new biases (in h FF and h ⋆ configuration)B 0 B π B detour h FF B surf h FF B loop h FF B 0 B π B detour h FF B detour h ⋆ B surf h FF B surf h ⋆ B loop h FF B loop h ⋆with two baselines: the constant bias B 0 = 0 and B π defined as B π (s) = cost π s (s 0 , s n ). Given our additions to the fuzzer, B π differs from Steinmetz et al.'s definition in that it only computes the cost of partial runs.For each bias B and planning task, we run the fuzzer from Algorithm 1 for at most one hour to generate a pool P of up to N = 100 states. We limit the length of random walks to L = 5 and use the budgets B state = 50 and B expansion = 200.For the test oracle, as mentioned before we use the bestperforming oracle of Eisenhut et al. (2023) . We run this oracle for at most two hours per test pool P, to determine how many states in P can be classified as bugs.We refer to the percentage of tested pool states (across the entire domain) classified as bugs as oracle coverage. To foster comparison of oracle coverage across biases, we use the same number of test states across all biases for each problem instance. If we have, e.g., 90 pool states for B 1 but only 50 for B 2 , we consider only the first 50 pool states for B 1 .Table 1 shows the results. The left part shows the comparison of practical biases (not using h ⋆ ). In general, the behavior is highly domain specific and there is no bias that works best universally. However, in 7 of the 11 domains considered for ASNets and in 4 out of 6 domains for GNNs, one of the new biases achieves a higher oracle coverage than both baselines. The new biases perform significantly better than B 0 in 310 most cases, but usually provide only a slight advantage over B π . Note that the oracle coverage in general varies greatly between domains. For example, the coverage for ASNets in Elevator is not below 75% across all biases, but we do not detect a single bug state for ASNets in Gripper (we assume 315 the policy is optimal). We are able to increase the coverage by 10 percentage points (from B π ) in Woodworking, but the difference between all biases in Blocks is negligible.The right part shows the results when including all biases. As this includes h ⋆ based biases, the number of considered 320 states S is mostly much lower (e.g., the pools for ASNets in Blocksworld contain the initial state only). While there are cases where the h ⋆ variant outperforms its h FF proxy (e.g. B detour h ⋆ for ASNets in Scanalyzer), this is not the case in general which indicates that h FF works reasonably well 325 here in replacing h ⋆ . Note also that, here, there is only a single case (GNNs in Visitall) where a baseline achieves better results than all configurations of our new biases.With the proliferation of learned action policies, how to 330 meaningfully test them is becoming very relevant. We contribute more advanced fuzzing biases for policy testing in classical planning, measuring path-shape features instead of merely path cost, with promising results.We do not believe that much more can be gained by differ-335 ent fuzzing biases. The primary challenges for policy testing in our view remain fault analysis (which specific policy decisions cause sub-optimality), extension to richer planning paradigms, and connections to policy re-training.It covers both "quantitative" (π is sub-optimal on t) and "qualitative" (π does not solve solvable t) bugs used bySteinmetz et al. 
 
 Appendix:  


Decision: The paper aims at finding states where a suboptimal action is taken by a learned policy. The authors use fuzzing to collect states to be tested via random walks guided by a bias function and introduce three novel bias functions. 

All the reviews agree that the paper is well written and tackles an interesting problem. Despite some doubts on the significance of the experimental results (that show modest improvements with respect to simpler bias functions), all the reviewers are in favor of acceptance.

Reviews: review: strength_weakness: strength_weakness: The clarity of the background section could be improved. Here are some suggestions:

- Use lowercase letters for single variables, e.g., “V” at line 75 and onwards. Keep uppercase letters for sets, such as “U”.
- Differentiate the “p[]” notation for single variables and sets of variables. You use p[v] to denote a value and p[U] (U set of variables) to denote a partial state. Use a different notation to avoid confusion.
- At line 85, why write pre(a) = s[V(pre(a)]? If pre(a) is a partial state and s a complete state, then you can write pre(a) \subseteq s. The same applies to goal G at line 96 and onwards.
- Is it necessary to use \phi to indicate a sequence of actions? This notation is only used in one paragraph. Also, consider changing the letter “\phi” as it commonly denotes logic formulas.

I suggest spending a few words explaining how the oracle works.

When explaining Algorithm 1, I suggest adding references to the lines of code in the text.
I suggest changing the notation “h^max” as it commonly denotes the admissible h max heuristic.

Consider moving “BMO-100 + Aras/EHC” to the experiments section.
questions: questions: 1) Is there any particular reason why you choose h^FF? Can you spend some words on the difference between using an admissible vs a non-admissible heuristic for your biases?

2) Can you briefly explain how the oracle you used works?

3) You state (line 224) “That difference can lead to arbitrary differences in bias value however (even for h* and in invertible planning tasks, as there may be a much cheaper path from s_j to s_i than the inverted policy path)”. I thought that for invertible tasks and h* the term h(s_i, s_j) is equal to h(s_j, s_i), making B^detour equal to B^loop (in this case). Can you clarify this?
strength_weakness: strength_weakness: There are some places definitions would help, at least for non-specialists.  What is "FDR planning?"  A brief explanation of test oracles would help, too.
questions: questions: The main question I have regarding this paper is how general the result is.  In particular, what is the basis for the assertion that not much more can be gained by considering alternative fuzzing biases?  Are the variants evaluated in this paper somehow representative of a space of alternatives?  Are the authors rethinking the utility of fuzzing biases at all?  Or is it that addressing the other challenges cited in the conclusion is more likely to lead to improved testing performance?
strength_weakness: strength_weakness: The experimental results are a bit underwhelming. However, this could also be due to the experiment design since it's unclear how much any method could improve over the previous best methods. When computing oracle coverage, couldn't you ignore the states proven optimal by some method? It would be good to see whether a domain even allows for further improvement, or not.

The introduction briefly mentions test oracles, but to understand the relevance of the work, it would be good to include at least a superficial discussion of test oracles and why no optimal planning processes is needed for proving a state suboptimal.

It's a pity that there's no space for the proofs, not even proof sketches. To make the paper self-contained, I recommend buying an extra page and including proof sketches.


Minor comments:

Define "safety" of a heuristic.

The use of h^max in Algorithm 1, line 8 should be motivated in the text. And a citation for h^max would be good.

Bias paragraphs: since they span multiple paragraphs, they should be subsections instead.
questions: questions: 1) Why don't you treat quantitative and qualitative suboptimality separately? In my opinion, there is a big difference between a policy that fails to reach the goal and a policy that reaches the goal but requires suboptimal cost.
2) Have you considered or even tested other aggregation functions apart from "max"?
3) Roughly how large was the standard deviation for the results in Table 1?
4) Do your results for the GNN domains match the results in their original paper? I think a short discussion would benefit the paper.
5) How much faster or memory-efficient is your C implementation of ASNets compared to the original Python implementation? Were you able to reproduce the results from the original paper with your implementation?