SataAgent.java
原始文件
1/*
2 * Copyright 2020 Advanced Software Technologies Lab at ETH Zurich, Switzerland
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16package com.android.commands.monkey.ape.agent;
17
18import static com.android.commands.monkey.ape.utils.Config.defaultEpsilon;
19import static com.android.commands.monkey.ape.utils.Config.doBackToTrivialActivity;
20import static com.android.commands.monkey.ape.utils.Config.fallbackToGraphTransition;
21import static com.android.commands.monkey.ape.utils.Config.fillTransitionsByHistory;
22import static com.android.commands.monkey.ape.utils.Config.trivialActivityRankThreshold;
23import static com.android.commands.monkey.ape.utils.Config.useActionDiffer;
24
25import java.util.ArrayList;
26import java.util.Arrays;
27import java.util.Collection;
28import java.util.Collections;
29import java.util.Comparator;
30import java.util.HashSet;
31import java.util.LinkedList;
32import java.util.IdentityHashMap;
33import java.util.Map;
34import java.util.List;
35import java.util.Set;
36
37import com.android.commands.monkey.MonkeySourceApe;
38import com.android.commands.monkey.ape.ActionFilter;
39import com.android.commands.monkey.ape.AndroidDevice;
40import com.android.commands.monkey.ape.AndroidDevice.Activity;
41import com.android.commands.monkey.ape.AndroidDevice.Stack;
42import com.android.commands.monkey.ape.AndroidDevice.Task;
43import com.android.commands.monkey.ape.BadStateException;
44import com.android.commands.monkey.ape.BaseActionFilter;
45import com.android.commands.monkey.ape.Subsequence;
46import com.android.commands.monkey.ape.SubsequenceFilter;
47import com.android.commands.monkey.ape.model.Action;
48import com.android.commands.monkey.ape.model.ActivityNode;
49import com.android.commands.monkey.ape.model.Graph;
50import com.android.commands.monkey.ape.model.ModelAction;
51import com.android.commands.monkey.ape.model.State;
52import com.android.commands.monkey.ape.model.StateActionDiffer;
53import com.android.commands.monkey.ape.model.StateTransition;
54import com.android.commands.monkey.ape.tree.GUITreeAction;
55import com.android.commands.monkey.ape.tree.GUITreeNode;
56import com.android.commands.monkey.ape.utils.Logger;
57import com.android.commands.monkey.ape.utils.RandomHelper;
58
59import android.content.ComponentName;
60
61public class SataAgent extends StatefulAgent {
62
63
64 SubsequenceFilter unsaturatedActionsFilter = new SubsequenceFilter() {
65
66 @Override
67 public boolean include(Subsequence path) {
68 if (path.isEmpty()) {
69 return false;
70 }
71 State last = path.getLastState();
72 return last.firstAction(ActionFilter.ENABLED_VALID_UNSATURATED) != null;
73 }
74
75 @Override
76 public boolean extend(Subsequence path, StateTransition edge) {
77 if (path.isClosed()) {
78 return false;
79 }
80 if (!ActionFilter.ENABLED_VALID.include(edge.action)) {
81 return false;
82 }
83 return edge.isStrong();
84 }
85 };
86
87 SubsequenceFilter backtrackSubsequenceFilter = new SubsequenceFilter() {
88
89 @Override
90 public boolean include(Subsequence path) {
91 if (path.isEmpty()) {
92 return false;
93 }
94 State last = path.getLastState();
95 if (isGreedyState(last)) {
96 return true;
97 }
98 if (isEntryState(last)) {
99 return true;
100 }
101 return false;
102 }
103
104 @Override
105 public boolean extend(Subsequence path, StateTransition edge) {
106 if (path.isClosed()) {
107 return false;
108 }
109 if (!edge.action.isBack()) { // only back action
110 return false;
111 }
112 if (!ActionFilter.ENABLED_VALID.include(edge.action)) {
113 return false;
114 }
115 return edge.isStrong();
116 }
117 };
118
119 SubsequenceFilter greedySubsequenceFilter = new SubsequenceFilter() {
120
121 @Override
122 public boolean include(Subsequence path) {
123 if (path.isEmpty()) {
124 return false;
125 }
126 State last = path.getLastState();
127 State prev;
128 if (path.size() > 1) {
129 prev = path.getLastLastState();
130 } else {
131 prev = path.getStartState();
132 }
133 if (isGreedyState(prev, last)) {
134 return true;
135 }
136 return false;
137 }
138
139 @Override
140 public boolean extend(Subsequence path, StateTransition edge) {
141 if (path.isClosed()) {
142 return false;
143 }
144 if (edge.action.isBack()) {
145 return false;
146 }
147 if (!ActionFilter.ENABLED_VALID.include(edge.action)) {
148 return false;
149 }
150 return edge.isStrong();
151 }
152 };
153
154 // Only Remote Greedy gains extra endpoints. Native edge traversal/costs and
155 // the filters used by local, ABA, backtracking and epsilon stay unchanged.
156 SubsequenceFilter remoteGreedySubsequenceFilter = new SubsequenceFilter() {
157 public boolean include(Subsequence path) {
158 if (path.isEmpty()) return false;
159 boolean probe = jev != null && jev.pendingProbeNavigationCandidate(path.getLastState());
160 return greedySubsequenceFilter.include(path) || probe;
161 }
162 public boolean extend(Subsequence path, StateTransition edge) {
163 return greedySubsequenceFilter.extend(path, edge);
164 }
165 };
166
167 SubsequenceFilter weakActionSubsequenceFilter = new SubsequenceFilter() {
168
169 @Override
170 public boolean include(Subsequence path) {
171 if (path.isEmpty()) {
172 return false;
173 }
174 StateTransition last = path.getLastStateTransition();
175 if (last.getStrength() == 0 && last.getVisitedCount() < 3) {
176 return true;
177 }
178 return false;
179 }
180
181 @Override
182 public boolean extend(Subsequence path, StateTransition edge) {
183 if (path.isClosed()) {
184 return false;
185 }
186 if (!ActionFilter.ENABLED_VALID.include(edge.action)) {
187 return false;
188 }
189 return edge.isStrong() || edge.getStrength() == 0;
190 }
191 };
192
193 static enum SataEventType {
194 TRIVIAL_ACTIVITY,
195 SATURATED_STATE, USE_BUFFER, EARLY_STAGE,
196 EPSILON_GREEDY, RANDOM, NULL, BUFFER_LOSS, FILL_BUFFER, BAD_STATE, PROBE;
197 }
198
199 /**
200 * Control the exploration and exploitation. The idea is borrowed from reinforcement learning.
201 */
202 private double epsilon;
203
204 private StateActionDiffer actionDiffer = new StateActionDiffer();
205
206 private int[] actionCounters;
207 private ActivityNode backToActivity;
208
209 public SataAgent(MonkeySourceApe ape, Graph graph) {
210 this(ape, graph, defaultEpsilon);
211 }
212
213 public SataAgent(MonkeySourceApe ape, Graph graph, double epsilon) {
214 super(ape, graph);
215 this.epsilon = epsilon;
216
217
218 this.actionCounters = new int[SataEventType.values().length];
219 }
220
221 protected boolean isEntryState(State state) {
222 return this.getGraph().isEntryState(state);
223 }
224
225 protected void logActionSelected(Action action, SataEventType type) {
226 Logger.iformat("Select action %s by strategy %s", action, type);
227 logEvent(type);
228 }
229
230 protected void logEvent(SataEventType type) {
231 int ordinal = type.ordinal();
232 actionCounters[ordinal] = actionCounters[ordinal] + 1;
233 }
234
235 // Only this selection round excludes rejected concretes. Native scoring and
236 // saturation always see the original actions and complete resolved node sets.
237 private Map<ModelAction, Binding> regionOriginals;
238 private Map<ModelAction, Set<GUITreeNode>> regionRejected;
239 private Set<ModelAction> regionExhausted;
240 private ModelAction regionFallback;
241 private SataEventType regionFallbackStrategy;
242 private Binding regionFallbackBinding;
243 private Boolean epsilonSelectionGreedy;
244
245 private static final class Binding {
246 final GUITreeAction concrete;
247 final GUITreeNode[] nodes;
248 Binding(ModelAction action) { concrete=action.getResolvedGUITreeAction(); nodes=action.getResolvedNodes(); }
249 void restore(ModelAction action, int timestamp) {
250 if(concrete==null)return;
251 action.resolveAt(timestamp,concrete.getThrotlle(),concrete.getGUITree(),concrete.getGUITreeNode(),nodes);
252 action.setResolvedGUITreeAction(concrete);
253 }
254 }
255
256 protected boolean regionAvailable(ModelAction action) {
257 return regionExhausted==null || !regionExhausted.contains(action);
258 }
259
260 private ActionFilter regionSelectionFilter(final ActionFilter nativeFilter) {
261 if(regionExhausted==null || regionExhausted.isEmpty())return nativeFilter;
262 return new BaseActionFilter() {
263 public boolean include(ModelAction action) {
264 return regionAvailable(action) && nativeFilter.include(action);
265 }
266 };
267 }
268
269 private void regionRejected(ModelAction action, SataEventType strategy, Binding rejectedBinding) {
270 if(regionRejected==null) {
271 regionRejected=new IdentityHashMap<ModelAction,Set<GUITreeNode>>();
272 regionOriginals=new IdentityHashMap<ModelAction,Binding>();
273 regionExhausted=Collections.newSetFromMap(new IdentityHashMap<ModelAction,Boolean>());
274 }
275 if(!regionOriginals.containsKey(action))regionOriginals.put(action,new Binding(action));
276 if(regionFallback==null) { regionFallback=action; regionFallbackStrategy=strategy; regionFallbackBinding=rejectedBinding; }
277 Set<GUITreeNode> rejected=regionRejected.get(action);
278 if(rejected==null) {
279 rejected=Collections.newSetFromMap(new IdentityHashMap<GUITreeNode,Boolean>());
280 regionRejected.put(action,rejected);
281 }
282 rejected.add(rejectedBinding.concrete==null?null:rejectedBinding.concrete.getGUITreeNode());
283 // Probe rejection restores its native binding inside JevRuntime.gate.
284 if(!rejected.contains(action.getResolvedNode()))return;
285 // State.resolveAction uses uniform concrete selection. Keep that rule for
286 // remaining siblings without narrowing the nodes used for saturation.
287 List<GUITreeNode> remaining=new ArrayList<GUITreeNode>();
288 if(action.getResolvedNodes()!=null)for(GUITreeNode node:action.getResolvedNodes())
289 if(!rejected.contains(node))remaining.add(node);
290 while(!remaining.isEmpty()) {
291 GUITreeNode node=RandomHelper.randomPick(remaining);
292 action.resolveAt(getTimestamp(),action.getThrottle(),action.getResolvedGUITree(),node,action.getResolvedNodes());
293 if(validateResolvedAction(action))return;
294 remaining.remove(node);
295 }
296 regionExhausted.add(action);
297 }
298
299 private void excludeRegionPaths(List<Subsequence> paths) {
300 if(regionExhausted!=null)for(java.util.Iterator<Subsequence> it=paths.iterator();it.hasNext();)
301 if(!regionAvailable(it.next().getFirstAction()))it.remove();
302 }
303
304 private boolean returnSelectedAction(Action action, SataEventType type) {
305 if (action == null) {
306 return false;
307 }
308 Binding attempted=action instanceof ModelAction?new Binding((ModelAction)action):null;
309 if (!acceptSelectedAction(action,type.name())) {
310 if(action instanceof ModelAction)regionRejected((ModelAction)action,type,attempted);
311 return false;
312 }
313 logActionSelected(action, type);
314 if (jev != null) {
315 if(jevDecisionEnabled())pendingSelectionStrategy=type.name();
316 else jev.recordSelectionDecision(type.name(), newState, action, actionBufferSize());
317 }
318 return true;
319 }
320
321 public void tearDown() {
322 super.tearDown();
323 printCounters();
324 }
325
326 protected void printCounters() {
327 SataEventType[] types = SataEventType.values();
328 for (SataEventType type : types) {
329 Logger.format("%6d %s", actionCounters[type.ordinal()], type);
330 }
331 }
332
333 protected ModelAction checkBackTrack() {
334 if (newState.isSaturated()) { // no forward unsaturated actions selected by EARLY_STAGE
335 Logger.iprintln("State is saturated: try to back track.");
336 boolean doBackTrack = false;
337 LinkedList<State> queue = new LinkedList<State>();
338 Set<State> visited = new HashSet<>();
339 queue.add(newState);
340 visited.add(newState);
341 State state = null;
342 outer: while (!queue.isEmpty()) {
343 state = queue.removeFirst();
344 ModelAction action = state.getBackAction();
345 Collection<StateTransition> sts = getGraph().getOutStateTransitions(action);
346 for (StateTransition st : sts) {
347 if (st.isCircle()) {
348 continue;
349 }
350 if (st.isStrong()) {
351 State target = st.getTarget();
352 if (!target.isSaturated()) {
353 doBackTrack = true;
354 break outer;
355 } else {
356 if (!visited.contains(state)) {
357 queue.addLast(target);
358 visited.add(state);
359 }
360 }
361 }
362 }
363 }
364 if (doBackTrack && newState != state) {
365 ModelAction action = moveToState(newState, state, true);
366 if (action != null) {
367 Logger.iprintln("Backtrack to an unsaturated state: " + state);
368 logActionSelected(action, SataEventType.SATURATED_STATE);
369 return action;
370 } else {
371 Logger.iformat("Cannot backtrack to %s", state);
372 }
373 }
374 }
375 return null;
376 }
377
378 protected boolean isDialogState(State state) {
379 Collection<StateTransition> edges = getGraph().getInStateTransitions(state);
380 int threshold = 5;
381 if (edges.size() <= threshold) {
382 return false;
383 }
384 return hasGreedyActionForward(state);
385 }
386
387 protected Action selectNewActionNonnull() {
388 Action selected=null;
389 epsilonSelectionGreedy=null;
390 regionOriginals=null;regionRejected=null;regionExhausted=null;regionFallback=null;
391 try { selected=selectNewActionInRound(); return selected; }
392 finally {
393 if(regionOriginals!=null)for(Map.Entry<ModelAction,Binding> entry:regionOriginals.entrySet())
394 if(entry.getKey()!=selected)entry.getValue().restore(entry.getKey(),getTimestamp());
395 regionOriginals=null;regionRejected=null;regionExhausted=null;regionFallback=null;regionFallbackBinding=null;epsilonSelectionGreedy=null;
396 }
397 }
398
399 private Action selectNewActionInRound() {
400 {
401 // Logging
402 printStrategy();
403 Logger.iprintln("Check global actions.");
404 for (ModelAction action : newState.targetedActions()) {
405 if (action.isVisited()) {
406 continue;
407 }
408 if (getGraph().isNameGlobalAction(action)) {
409 Logger.iformat("- %s", action);
410 }
411 }
412 }
413 Action resolved = null;
414 while ((resolved = selectNewActionFromBuffer()) != null) {
415 if (returnSelectedAction(resolved, SataEventType.USE_BUFFER))return resolved;
416 }
417 while ((resolved = selectNewActionBackToActivity()) != null) {
418 if (returnSelectedAction(resolved, SataEventType.TRIVIAL_ACTIVITY))return resolved;
419 }
420 while ((resolved = selectNewActionEarlyStageForABA()) != null) {
421 if (returnSelectedAction(resolved, SataEventType.EARLY_STAGE))return resolved;
422 }
423
424 boolean localRejected=false;
425 while ((resolved = selectNewActionEarlyStageForwardLocalGreedy()) != null) {
426 localRejected=true;
427 if (returnSelectedAction(resolved, SataEventType.EARLY_STAGE))return resolved;
428 }
429
430 // Probe the current page only between local greedy and native remote greedy.
431 // A rejected native local action is not a probe opportunity.
432 if(!localRejected && jevDecisionEnabled()) {
433 // Navigation and native local-greedy choices have priority. Only
434 // after both are exhausted may the current page enter semantic
435 // review; a synchronous review then completes in this same action
436 // cycle before ordinary fallback exploration resumes.
437 if (semanticReviewActive())
438 jev.prepareSemanticReviews(model,newState,newGUITree,new com.android.commands.monkey.ape.jev.JevRuntime.Validator(){
439 public boolean valid(ModelAction action){return validateResolvedAction(action);}
440 });
441 beginProbeSelection();
442 try {
443 while((resolved=selectProbe())!=null)
444 if(returnSelectedAction(resolved,SataEventType.PROBE))return resolved;
445 } finally {
446 endProbeSelection();
447 }
448 }
449
450 while ((resolved = selectNewActionEarlyStageForwardRemoteGreedy()) != null) {
451 if (returnSelectedAction(resolved, SataEventType.EARLY_STAGE))return resolved;
452 }
453 while ((resolved = selectNewActionForTrivialActivity()) != null) {
454 if (returnSelectedAction(resolved, SataEventType.TRIVIAL_ACTIVITY))return resolved;
455 }
456 while ((resolved = selectNewActionEarlyStageBackward()) != null) {
457 if (returnSelectedAction(resolved, SataEventType.EARLY_STAGE))return resolved;
458 }
459 while ((resolved = selectNewActionEpsilonGreedyRandomly()) != null) {
460 if (returnSelectedAction(resolved, SataEventType.EPSILON_GREEDY))return resolved;
461 }
462 while ((resolved = selectNullActionInRound()) != null) {
463 if (returnSelectedAction(resolved, SataEventType.NULL))return resolved;
464 }
465 if(regionFallback!=null) {
466 regionFallbackBinding.restore(regionFallback,getTimestamp());
467 // The chain is exhausted: restore its first native legal choice,
468 // bypassing only Region and preserving the original strategy receipt.
469 logActionSelected(regionFallback,regionFallbackStrategy);
470 if(jev!=null)pendingSelectionStrategy=regionFallbackStrategy.name();
471 return regionFallback;
472 }
473 throw new BadStateException("No available action on the current state");
474 }
475
476 private ModelAction selectNullActionInRound() {
477 if(regionFallback==null)return handleNullAction();
478 ModelAction action=newState.randomlyPickAction(getRandom(),regionSelectionFilter(validatedActionFilter));
479 return action==null?null:validateNewAction(action);
480 }
481
482 protected ModelAction selectNewActionEarlyStageBackward() {
483 return selectNewActionEarlyStageBackwardGreedy();
484 }
485
486 public void onBufferLoss(State actual, State expected) {
487 logEvent(SataEventType.BUFFER_LOSS);
488 }
489
490 protected ModelAction selectNewActionEpsilonGreedyRandomly() {
491 ModelAction back = newState.getBackAction();
492 if (back.isValid() && regionAvailable(back)) {
493 if (back.isUnvisited()) {
494 Logger.iprintln("Select Back because Back action is unvisited.");
495 return back;
496 }
497 }
498 if(epsilonSelectionGreedy==null)epsilonSelectionGreedy=egreedy();
499 if (epsilonSelectionGreedy) { // TODO: this is different from Sarsa.
500 Logger.iformat("Try to select the least visited action.");
501 return newState.greedyPickLeastVisited(regionSelectionFilter(ActionFilter.ENABLED_VALID));
502 }
503 Logger.iformat("Try to randomly select a visited action.");
504 return newState.randomlyPickAction(getRandom(), regionSelectionFilter(ActionFilter.ENABLED_VALID));
505 }
506
507 public void onRefillBuffer(Subsequence seq) {
508 logEvent(SataEventType.FILL_BUFFER);
509 }
510
511 protected ModelAction fillTransition(State[] states) {
512 return fillTransition(states, fillTransitionsByHistory, fallbackToGraphTransition);
513 }
514
515 protected ModelAction fillTransition(State[] states, boolean byHistory, boolean fallback) {
516 if (byHistory) {
517 Subsequence path = getGraph().fillTransitionsByHistory(states);
518 if (path != null) {
519 return refillBuffer(path);
520 }
521 Logger.println("Fill transitions by history failed!");
522 if (!fallback) {
523 return null;
524 }
525 }
526 List<Subsequence> selectedPaths = new ArrayList<Subsequence>();
527 getGraph().fillTransitions(selectedPaths, states);
528 if (!selectedPaths.isEmpty()) {
529 int total = selectedPaths.size();
530 int index = this.nextInt(total);
531 Subsequence path = selectedPaths.get(index);
532 return refillBuffer(path);
533 }
534 return null;
535 }
536
537 protected ModelAction moveToState(State start, State end, boolean includeBack) {
538 List<Subsequence> selectedPaths = new ArrayList<Subsequence>();
539 getGraph().moveToState(selectedPaths, start, end, includeBack, Integer.MAX_VALUE);
540 if (!selectedPaths.isEmpty()) {
541 Subsequence path = RandomHelper.randomPick(selectedPaths);
542 return refillBuffer(path);
543 }
544 return null;
545 }
546
547 /**
548 * ABA is a circle in the model graph, e.g., a path starting from A, B and eventualy ending at A.
549 * @param fromA
550 * @param toB
551 * @param verbose
552 * @return
553 */
554 protected boolean doABA(State fromA, State toB, boolean verbose) {
555 if (isDialogState(toB)) {
556 if (verbose) {
557 Logger.iformat("Never move to a saturated dialog state (%s) in ABA.", toB);
558 }
559 return false;
560 }
561 if (fromA.getActivity().equals(toB.getActivity())) {
562 if (toB.getVisitedCount() >= fromA.getVisitedCount()) {
563 if (verbose) {
564 Logger.iformat("Never move from a cold state (%s) to a hot state (%s) in ABA.", fromA, toB);
565 }
566 return false;
567 }
568 } else {
569 ActivityNode AA = getGraph().getActivityNode(fromA.getActivity());
570 ActivityNode BA = getGraph().getActivityNode(toB.getActivity());
571 if (BA.getVisitedCount() >= AA.getVisitedCount()) {
572 if (verbose) {
573 Logger.iformat("Never move from a cold activity (%s)(%s) to a hot activity (%s)(%s) in ABA.",
574 fromA, AA, toB, BA);
575 }
576 return false;
577 }
578 }
579 Logger.iformat("Move from A (%s) to B (%s).", fromA, toB);
580 return true;
581 }
582
583 protected List<ModelAction> getGreedyActions(State to) {
584 return getGreedyActions(null, to);
585 }
586
587 protected boolean isGreedyState(State to) {
588 return isGreedyState(null, to);
589 }
590
591 /**
592 * We will visited every ``unvisited action''.
593 * The identifier of an ``unvisited action'' may be its target (widget) only or
594 * the combination of its state (the set of all widgets) and target (widget).
595 * @param from
596 * @param to
597 * @return
598 */
599 protected List<ModelAction> getGreedyActions(State from, State to) {
600 if (useActionDiffer) {
601 return this.actionDiffer.getUnsaturated(from, to);
602 }
603 return to.collectActions(new BaseActionFilter() {
604
605 @Override
606 public boolean include(ModelAction action) {
607 if (!ActionFilter.ENABLED_VALID.include(action)) {
608 return false;
609 }
610 if (!action.requireTarget()) {
611 return false;
612 }
613 if (action.isScroll()) {
614 return action.isUnvisited();
615 }
616 return getGraph().isActionUnvisitedByName(action);
617 }
618
619 });
620 }
621
622
623 protected boolean isGreedyState(State from, State to) {
624 return !getGreedyActions(from, to).isEmpty();
625 }
626
627 protected ModelAction selectNewActionEarlyStageForABAInternal() {
628 if (currentState == null) {
629 return null;
630 }
631 State A = newState;
632 State B = currentState;
633 Logger.iprintln("Check A*BA->B, try to move from A to B.");
634 Logger.iformat("> - A: %s", A);
635 Logger.iformat("> - B: %s", B);
636 if (!doABA(A, B, true)) {
637 return null;
638 }
639 List<Subsequence> forwardPaths = getGraph().moveToState(A, B, false);
640 excludeRegionPaths(forwardPaths);
641 if (forwardPaths.isEmpty()) {
642 Logger.iprintln("A cannot reach B.");
643 return null;
644 }
645 List<Subsequence> backwardPaths = getGraph().moveToState(B, A, true);
646 if (backwardPaths.isEmpty()) {
647 Logger.iprintln("B cannot reach A.");
648 return null;
649 }
650 Subsequence path = randomPickShortest(forwardPaths);
651 Logger.iformat("Try to find a path (1/%d) to a greedy state that we want to greedily visit in ABA.", forwardPaths.size());
652 path.print();
653 StateTransition[] edges = path.getEdges();
654 int lastIndex = -1;
655 State lastTarget = null;
656 for (int i = 0; i < edges.length; i++) {
657 State source = edges[i].getSource();
658 State target = edges[i].getTarget();
659 if (!doABA(source, target, true)) {
660 break;
661 }
662 if (isGreedyState(source, target)) {
663 if (lastTarget == null) {
664 lastIndex = i;
665 lastTarget = target;
666 } else {
667 if (target.getActivity().equals(lastTarget.getActivity())) {
668 if (target.getVisitedCount() < lastTarget.getVisitedCount()) {
669 lastIndex = i;
670 lastTarget = target; // prefer colder state
671 }
672 } else { // prefer colder activity
673 ActivityNode an1 = getGraph().getActivityNode(target.getActivity());
674 ActivityNode an2 = getGraph().getActivityNode(lastTarget.getActivity());
675 if (an1.getVisitedCount() < an2.getVisitedCount()) {
676 lastIndex = i;
677 lastTarget = target;
678 }
679 }
680 }
681 }
682 }
683 if (lastIndex < 0) {
684 Logger.iprintln("No state or path that we want to greedily visit in ABA.");
685 return null;
686 }
687 if (lastIndex != edges.length - 1) {
688 List<StateTransition> newEdges = new ArrayList<>(lastIndex + 1);
689 for (int i = 0; i <= lastIndex; i++) {
690 newEdges.add(edges[i]);
691 }
692 path = new Subsequence(newEdges);
693 Logger.iformat("Update B from %s to %s", B, path.getLastState());
694 B = path.getLastState();
695 }
696 ModelAction action = refillBuffer(path);
697 if (action != null) {
698 Logger.iformat("Move from A (%s) to B (%s) for ABA within %d steps that start from action %s",
699 A, B, path.size(), action);
700 }
701 return action;
702 }
703
704 protected ModelAction selectNewActionBackToActivity() {
705 if (this.backToActivity == null) {
706 return null;
707 }
708 Stack stack = AndroidDevice.getFocusedStack();
709 if (stack.getTasks().isEmpty()) {
710 this.backToActivity = null;
711 return null;
712 }
713 if (stack.getTasks().get(0).getActivities().isEmpty()) {
714 this.backToActivity = null;
715 return null;
716 }
717 stack.dump();
718 int totalActivities = 0;
719 int onStackIndex = -1;
720 for (Task task : stack.getTasks()) {
721 for (Activity a : task.getActivities()) {
722 if (a.activity.getClassName().equals(backToActivity.activity)) {
723 onStackIndex = totalActivities;
724 }
725 totalActivities ++;
726 }
727 }
728 if (totalActivities == 1 || onStackIndex == -1) {
729 this.backToActivity = null;
730 return null;
731 }
732 if (totalActivities > 1) { // not the topmost
733 if (onStackIndex != 0) {
734 if (newState.isBackEnabled()) {
735 Logger.iformat("Backtrack to %s, total=%d", backToActivity.activity, totalActivities);
736 return newState.getBackAction();
737 }
738 } else { // top most trivial activity
739 Logger.iformat("Backtrack stopped at %s, total=%d", backToActivity.activity, totalActivities);
740 this.backToActivity = null;
741 return null;
742 }
743
744 }
745 return null;
746 }
747
748 /**
749 * Explore connected component first.
750 * @return
751 */
752 protected ModelAction selectNewActionEarlyStageForABA() {
753 return selectNewActionEarlyStageForABAInternal();
754 }
755
756 @Override
757 public String getLoggerName() {
758 return "SATA";
759 }
760
761 protected boolean egreedy() {
762 double v = ape.getRandom().nextDouble();
763 Logger.iformat("EGreedy value=%f, epsilon=%f.", v, epsilon);
764 if (v < epsilon) {
765 return false;
766 }
767 return true;
768 }
769
770 protected ModelAction selectNewActionEarlyStageForwardLocalGreedy() {
771 assertEmptyActionBuffer();
772 return findGreedyActionForwardLocal(currentState,newState);
773 }
774
775 protected ModelAction selectNewActionEarlyStageForwardRemoteGreedy() {
776 assertEmptyActionBuffer();
777 return findGreedyActionForwardRemote(currentState,newState);
778 }
779
780 protected Set<ActivityNode> collectTrivialActivities() {
781 ActivityNode[] activities = getGraph().getActivityNodes();
782 if (activities.length <= trivialActivityRankThreshold) {
783 return Collections.emptySet();
784 }
785 Arrays.sort(activities, new Comparator<ActivityNode>() {
786
787 @Override
788 public int compare(ActivityNode o1, ActivityNode o2) {
789 int ret = o1.getVisitedCount() - o2.getVisitedCount();
790 if (ret != 0) {
791 return ret;
792 }
793 return o1.activity.compareTo(o2.activity);
794 }
795
796 });
797 int median = getMedianVisitedCount(activities);
798 int mean = getMeanVisitedCount(activities);
799 int threshold = Math.max(median, mean);
800 Set<ActivityNode> trivialActivities = new HashSet<>();
801 for (int i = 0; i < activities.length; i++) {
802 if (activities[i].getVisitedCount() <= threshold) {
803 if (isTrivialActivity(activities[i])) {
804 trivialActivities.add(activities[i]);
805 }
806 } else {
807 break;
808 }
809 }
810 return trivialActivities;
811 }
812
813 /**
814 * A heuristic of identifying trivial activity.
815 * @param activityNode
816 * @return
817 */
818 private boolean isTrivialActivity(ActivityNode activityNode) {
819 int stateSize = activityNode.getStates().size();
820 float visitedRate = activityNode.getVisitedRate();
821 int visitCount = activityNode.getVisitedCount();
822 if (stateSize < 5) { // simple activity
823 if (visitCount > stateSize >> 2) { // hard to visit
824 if (visitedRate > 0.8) {
825 return false; // e.g., Login, About, Help, Feedback
826 } else {
827 return true;
828 }
829 } else {
830 return true;
831 }
832 } else {
833 if (visitCount > stateSize >> 2) {
834 if (visitedRate > 0.5) {
835 return false; // Login
836 } else {
837 return true;
838 }
839 } else { // less visited
840 return true;
841 }
842 }
843 }
844
845 protected ModelAction selectNewActionForTrivialActivity() {
846 final Set<ActivityNode> trivialActivities = collectTrivialActivities();
847 if (trivialActivities.isEmpty()) {
848 return null;
849 }
850 ActivityNode an = getGraph().getActivityNode(newState.getActivity());
851 if (trivialActivities.contains(an)) {
852 return null;
853 }
854 Logger.iprintln("List trivial activities.");
855 for (ActivityNode a : trivialActivities) {
856 Logger.iformat("- %s", a);
857 }
858 int pathLength = Integer.MAX_VALUE;
859 SubsequenceFilter filter = new SubsequenceFilter() {
860
861 @Override
862 public boolean include(Subsequence path) {
863 if (path.isClosed()) {
864 return false;
865 }
866 State last = path.getLastState();
867 ActivityNode an = getGraph().getActivityNode(last.getActivity());
868 if (!trivialActivities.contains(an)) {
869 return false;
870 }
871 if (isGreedyState(last)) {
872 return true;
873 }
874 return last.firstEnabledUnvisitedValidAction() != null;
875 }
876
877 @Override
878 public boolean extend(Subsequence path, StateTransition edge) {
879 if (edge.action.isBack()) {
880 return false;
881 }
882 if (!ActionFilter.ENABLED_VALID.include(edge.action)) {
883 return false;
884 }
885 return edge.isStrong();
886 }
887
888 };
889 {
890 List<Subsequence> selectedPaths = getGraph().findShortestPaths(newState, filter, pathLength);
891 excludeRegionPaths(selectedPaths);
892 if (!selectedPaths.isEmpty()) {
893 Subsequence path = RandomHelper.randomPick(selectedPaths);
894 Logger.iformat("Find a path (1/%d) to a trivial activity %s.", selectedPaths.size(),
895 getGraph().getActivityNode(path.getLastState().getActivity()));
896 return refillBuffer(path);
897 }
898 }
899 if (doBackToTrivialActivity) {
900 return backToTrivialActivity(trivialActivities);
901 }
902 return null;
903 }
904
905 private ModelAction backToTrivialActivity(Set<ActivityNode> trivialActivities) {
906 Stack taskStack = AndroidDevice.getFocusedStack();
907 taskStack.dump();
908 ActivityNode topActivity = null;
909 for (Task task : taskStack.getTasks()) {
910 for (Activity a : task.getActivities()) {
911 Logger.iformat("Checking activity %s", a.activity.getClassName());
912 ActivityNode taskAN = getGraph().getActivityNode(a.activity.getClassName());
913 if (taskAN != null && trivialActivities.contains(taskAN)) {
914 topActivity = taskAN;
915 }
916 }
917 }
918 if (topActivity == null) {
919 return null;
920 }
921 if (newState.isBackEnabled()) {
922 Logger.iformat("Try to backtrack to trivial activity %s", topActivity.activity);
923 backToActivity = topActivity;
924 return newState.getBackAction();
925 }
926 return null;
927 }
928
929 private int getMedianVisitedCount(ActivityNode[] activities) {
930 int total = activities.length;
931 if (total == 0) {
932 return -1;
933 }
934 return activities[total >> 1].getVisitedCount();
935 }
936
937 private int getMeanVisitedCount(ActivityNode[] activities) {
938 int total = activities.length;
939 if (total == 0) {
940 return -1;
941 }
942 int count = 0;
943 for (ActivityNode an : activities) {
944 count += an.getVisitedCount();
945 }
946 return count / total;
947 }
948
949 protected ModelAction selectNewActionEarlyStageBackwardGreedy() {
950 ModelAction action = findGreedyActionBackward(currentState, newState);
951 if (action != null) {
952 return action;
953 }
954 return null;
955 }
956
957 protected boolean hasGreedyActionForward(State state) {
958 List<ModelAction> actions = getGreedyActions(state);
959 if (!actions.isEmpty()) {
960 return true;
961 }
962 // 2). Greedy action in the neighbor hood.
963 List<Subsequence> selectedPaths = getGraph().findShortestPaths(state, greedySubsequenceFilter, Integer.MAX_VALUE);
964 if (!selectedPaths.isEmpty()) {
965 return true;
966 }
967 return false;
968 }
969
970 protected Subsequence randomPickShortest(List<Subsequence> subsequences) {
971 Collections.sort(subsequences, new Comparator<Subsequence>() {
972
973 @Override
974 public int compare(Subsequence o1, Subsequence o2) {
975 return o1.size() - o2.size();
976 }
977
978 });
979 return subsequences.get(0);
980 }
981
982 protected ModelAction findGreedyActionForwardLocal(State prev,State next) {
983 List<ModelAction> actions=new ArrayList<ModelAction>(getGreedyActions(prev,next));
984 if(regionExhausted!=null)actions.removeAll(regionExhausted);
985 if (!actions.isEmpty()) {
986 ModelAction action = RandomHelper.randomPickWithPriority(actions);
987 if (action != null) {
988 Logger.iprintln("Find a greedy action in 0-step");
989 // super.disableRestart();
990 checkDisableRestart(action);
991 return action;
992 }
993 }
994 return null;
995 }
996
997 protected ModelAction findGreedyActionForwardRemote(State prev,State next) {
998 for (ModelAction a : next.targetedActions()) {
999 if (!regionAvailable(a) || !ActionFilter.ENABLED_VALID_UNVISITED.include(a)) { // unvisited hence no transitions.
1000 continue;
1001 }
1002 State t = getGraph().getNameGlobalTarget(a);
1003 boolean probe = t != null && jev != null && jev.pendingProbeNavigationCandidate(t);
1004 if (t != null && (isGreedyState(next, t) || probe)) {
1005 Logger.iformat("Find a greedy state %s via a global action %s.", t, a);
1006 if (jev != null) jev.probeNavigationSelected(t, getTimestamp(), true);
1007 return a;
1008 }
1009 }
1010 // 2). Greedy action in the neighbor hood.
1011 List<Subsequence> selectedPaths = getGraph().findShortestPaths(next, remoteGreedySubsequenceFilter, Integer.MAX_VALUE);
1012 if (!selectedPaths.isEmpty()) {
1013 Subsequence path = randomPickShortest(selectedPaths);
1014 Logger.iformat("Find a path (1/%d) to a greedy state %s.", selectedPaths.size(), path.getLastState());
1015 if (path.size() <= 1) {
1016 ModelAction firstAction = path.getFirstAction();
1017 checkDisableRestart(firstAction);
1018 }
1019 ModelAction action = refillRemoteGreedyBuffer(path);
1020 if (jev != null) jev.probeNavigationSelected(path.getLastState(), getTimestamp(), false);
1021 return action;
1022 }
1023 return null;
1024 }
1025
1026
1027
1028 protected void checkDisableRestart(ModelAction action) {
1029 if (model.getGraph().isActionUnvisitedByName(action)) {
1030 super.disableRestart();
1031 }
1032 }
1033
1034 protected ModelAction findGreedyActionBackward(State prev, State next) {
1035 // 3). Back
1036 if (regionAvailable(next.getBackAction()) && ActionFilter.ENABLED_VALID_UNVISITED.include(next.getBackAction())) {
1037 Logger.iprintln("Find a greedy (unvisited) back action.");
1038 return next.getBackAction();
1039 }
1040 // 4). Backtrack to parent.
1041 List<Subsequence> selectedPaths = getGraph().findShortestPaths(next, backtrackSubsequenceFilter, Integer.MAX_VALUE);
1042 excludeRegionPaths(selectedPaths);
1043 if (!selectedPaths.isEmpty()) {
1044 Subsequence path = randomPickShortest(selectedPaths);
1045 Logger.iformat("Find a path (1/%d) to state %s for backtrack.", selectedPaths.size(), path.getLastState());
1046 if (path.size() <= 1) {
1047 checkDisableRestart(path.getFirstAction());
1048 }
1049 return refillBuffer(path);
1050 }
1051 return null;
1052 }
1053
1054 protected void printStrategy() {
1055 Logger.format("Sata Strategy: buffer size (%d)", actionBufferSize());
1056 printCounters();
1057 newState.printActions();
1058 }
1059
1060 @Override
1061 public void onActivityBlocked(ComponentName blockedActivity) {
1062
1063 }
1064
1065 @Override
1066 public boolean onVoidGUITree(int retryCounter) {
1067 return false;
1068 }
1069
1070 @Override
1071 public void onBadState(int lastBadStateCount, int badStateCounter) {
1072 logEvent(SataEventType.BAD_STATE);
1073 }
1074
1075}